【正文】 RTD (2)每臺(tái)路由器的 LSDB (3)由鏈路狀態(tài)數(shù)據(jù)庫生成 帶權(quán)有向圖 C A B D 1 2 3 5 C A B D 1 2 3 C A B D 1 2 3 C A B D 1 2 3 C A B D 1 2 3 RTA RTB (1)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu) (4)每臺(tái)路由器分別以自己為根節(jié)點(diǎn)計(jì)算最小生成樹 RTC RTD 3 2 1 5 16 運(yùn)行 SPF算法計(jì)算路由 ?每個(gè)路由器根據(jù)搜集到的 LSDB，使用 SPF算法來計(jì)算路由。遇到類型為 StubNet的 link，其中包含的就是路由信息，填加到路由表中（但由于這些路由信息都是本機(jī)的直連路由，所以不會(huì)生效）。 3. 打開該條 LSA，遇到類型為 StubNet的 link，其中包含的就是路由信息，填加到路由表中。 4. 如果遇到類型為 router的 link，則繼續(xù)跳轉(zhuǎn)，直至某條 LSA的全部信息都被計(jì)算完畢，此時(shí)再跳回到上一條的 LSA。 18 OSPF協(xié)議原理 ?OSPF協(xié)議基礎(chǔ) ?通過 LSA描述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) ?用 SPF算法計(jì)算路由 ?鄰居狀態(tài)機(jī) ?DR和 BDR ?劃分區(qū)域 19 兩臺(tái)路由器之間建立鄰接關(guān)系的過程 RT1 RT2 Down Down Hello( DR = ,Neighbors Seen = 0) Hello( DR = RT2,Neighbors Seen = RT1) DD (Seq = x,I = 1, M = 1, MS = 1) DD (Seq = y,I = 1, M = 1, MS = 1) DD (Seq = y,I = 0, M = 1, MS = 0) DD (Seq = y+1,I = 0, M = 1, MS = 1) DD (Seq = y+1,I = 0, M = 1, MS = 0) DD (Seq = y+n,I = 0, M = 0, MS = 1) DD (Seq = y+n,I = 0, M = 0, MS = 0) LS Request LS Update LS Ack ExStart ExStart Init Exchange Exchange Loading Full Full 20 OSPF的鄰居狀態(tài)機(jī) Down Attempt Init 2way ExStart Exchange Loading Full ? 紫色的狀態(tài)機(jī)可能是長(zhǎng)期存在的狀態(tài)。 21 OSPF的五種協(xié)議報(bào)文 ? Hello報(bào)文 ?發(fā)現(xiàn)及維持鄰居關(guān)系，選舉 DR， BDR。 ? LSR報(bào)文 ?向?qū)Χ苏?qǐng)求本端沒有或?qū)Χ说母碌?LSA （只包含 LSA的Head信息） 。 ? LSAck報(bào)文 ?收到 LSU之后，進(jìn)行確認(rèn)（只包含 LSA的 Head信息） 。 24 通過選舉 DR來解決問題 M= n(n1)/2 = 28 M= (n2) 2+1 = 13 DR BDR ? 為了解決同一個(gè)網(wǎng)段內(nèi)過多的鄰接關(guān)系數(shù)量， OSPF協(xié)議提出了 DR（ Designated Router） 的概念。 25 DR的選舉過程 ? DR是整個(gè)網(wǎng)段中所有的路由器選舉出來的，選舉方法與 選舉村長(zhǎng) 十分類似。 ?終身制 ?DR一旦當(dāng)選，除非路由器故障，否則不會(huì)更換，即使后來的路由器 priority更高。 27 NBMA 和點(diǎn)到多點(diǎn) ?在某種情況下（非全連通的 NBMA網(wǎng)絡(luò)），由于選舉 DR會(huì)導(dǎo)致路由信息不能正確學(xué)習(xí)，此時(shí)需要管理員手工將網(wǎng)絡(luò)類型改為 PTMP，不再選舉 DR了。為協(xié)議本身帶來如下變化： ?將廣播和 NBMA網(wǎng)段內(nèi) LSDB同步的次數(shù)由 O(N)2減少為 O(N)。 ?路由器之間的關(guān)系分為 Unknown、 Neighbor、 Adjacency。 DR及 BDR與本網(wǎng)段內(nèi)的所有路由器建立Adjacency關(guān)系，鄰居狀態(tài)機(jī)會(huì)達(dá)到 Full狀態(tài)。 ?增加了一種新的 LSA類型： NetworkLSA，由 DR生成，描述了本網(wǎng)段的鏈路狀態(tài)信息。 ? DR是針對(duì)一個(gè)網(wǎng)段內(nèi)的設(shè)備選舉的，對(duì)于一臺(tái)路由器來說，可能它在某個(gè)接口上是 DR，在其它接口上是BDR、 DROther，或者因?yàn)槭?PTP的鏈路而不參加DR的選舉。 ? 一個(gè)網(wǎng)段中即使只有一臺(tái)路由器，也要選舉 DR。 30 OSPF協(xié)議原理 ?OSPF協(xié)議基礎(chǔ) ?通過 LSA描述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) ?用 SPF算法計(jì)算路由 ?鄰居狀態(tài)機(jī) ?DR和 BDR ?劃分區(qū)域 31 鏈路狀態(tài)算法的四宗罪 ? 相比較 DV算法，鏈路狀態(tài)存在如下缺點(diǎn)： ?鏈路狀態(tài)算法除了需要攜帶路由信息之外，還要挾帶網(wǎng)絡(luò)拓?fù)湫畔?，這樣會(huì)占用路由器大量的存儲(chǔ)空間并且使路由同步時(shí)間加長(zhǎng)。 ?鏈路狀態(tài)算法對(duì)網(wǎng)絡(luò)拓?fù)渥兓置舾?，網(wǎng)絡(luò)中任何拓?fù)渥兓紩?huì)導(dǎo)致全網(wǎng)中所有運(yùn)行 OSPF的路由器重新啟動(dòng)路由計(jì)算。 ? 上述缺點(diǎn)在網(wǎng)絡(luò)規(guī)模小的時(shí)候并不突出，但在網(wǎng)絡(luò)規(guī)模較大時(shí)，會(huì)給網(wǎng)絡(luò)帶來很嚴(yán)重的后果，甚至導(dǎo)致網(wǎng)絡(luò)不可用。 32 OSPF解決方案：引入?yún)^(qū)域的概念 Area0 Area1 Area3 ABR ABR ? 分而治之 ， 將整個(gè) OSPF域劃分成若干區(qū)域 ， 每個(gè)區(qū)域用不同的Area ID(32位整數(shù) )來標(biāo)識(shí) ， 其中 Area0區(qū)域稱為骨干區(qū)域 。 33 區(qū)域間的路由計(jì)算 ? 每個(gè)區(qū)域有自己的 LSDB， SPF運(yùn)算獨(dú)立運(yùn)行。 ? 注意： ABR的工作方式?jīng)Q定 OSPF在區(qū)域內(nèi)是 LS算法，在區(qū)域間算是 DV算法。 OSPF實(shí)際是通過要求所有的區(qū)域必須與骨干區(qū)域互聯(lián)，所有的跨區(qū)域路由必須通過骨干區(qū)域來防止路由環(huán)路。 ?骨干區(qū)域必須是連續(xù)非斷開的。 ?兩個(gè)普通區(qū)域之間的通訊必須通過骨干區(qū)。 ? 虛連接： virtuallink，一條虛擬的“物理鏈路”，兩端的設(shè)備必須是 ABR，屬于骨干區(qū)域。 ? 需要手工顯式配臵：兩端的 ABR及需要穿越的非骨干區(qū)域。 SPF計(jì)算時(shí)，下一跳指向生成該 LSA的 ASBR。 ? 為了解決該問題，由 ASBR所在區(qū)域的 ABR負(fù)責(zé)生成一條 Tpye4的LSA，不描述任何路由及拓?fù)湫畔?，只是挾帶本區(qū)域的 ASBR的router id， metric為該 ABR到達(dá)區(qū)域內(nèi)的 ASBR的 metric。 ? NetworkLSA，由 DR生成，描述了本網(wǎng)段的鏈路狀態(tài)，傳遞到整個(gè)區(qū)域。 ? AsbrSummaryLSA，由 ABR生成，描述了 ASBR的 router id信息路由，傳遞到除本區(qū)域外的其他區(qū)域。 ? 我們?cè)?