【正文】 SPF算法將每一個路由器作為根來計算其到每一個目的地路由器的距離，每一個路由器根據(jù)一個。 2020/6/16 Nanjing university of industry WuJun 112 自治系統(tǒng) AS 主干路由器 區(qū)域 區(qū)域 主干區(qū)域 至其他自治系統(tǒng) R9 R7 R6 R5 R4 R3 R2 R1 網(wǎng) 8 網(wǎng) 6 網(wǎng) 3 網(wǎng) 2 網(wǎng) 1 網(wǎng) 7 區(qū)域 網(wǎng) 4 網(wǎng) 5 R8 2020/6/16 Nanjing university of industry WuJun 113 自治系統(tǒng) AS 區(qū)域邊界路由器 區(qū)域 區(qū)域 主干區(qū)域 至其他自治系統(tǒng) R9 R7 R6 R5 R4 R3 R2 R1 網(wǎng) 8 網(wǎng) 6 網(wǎng) 3 網(wǎng) 2 網(wǎng) 1 網(wǎng) 7 區(qū)域 網(wǎng) 4 網(wǎng) 5 R8 LinkState Routing Protocols ? After initial flood, pass small eventtriggered linkstate updates to all other routers LinkState Packets SPF Algorithm Topological Database Shortest Path First Tree Routing Table C A D B 2020/6/16 Nanjing university of industry WuJun 115 SPF算法是 OSPF路由協(xié)議的基礎(chǔ)。主干區(qū)域的標(biāo)識符規(guī)定為 。 ? OSPF 使用層次結(jié)構(gòu)的區(qū)域劃分。 2020/6/16 Nanjing university of industry WuJun 110 自治系統(tǒng) AS OSPF 劃分為兩種不同的區(qū)域 區(qū)域 區(qū)域 主干區(qū)域 至其他自治系統(tǒng) R9 R7 R6 R5 R4 R3 R2 R1 網(wǎng) 8 網(wǎng) 6 網(wǎng) 3 網(wǎng) 2 網(wǎng) 1 網(wǎng) 7 區(qū)域 網(wǎng) 4 網(wǎng) 5 R8 2020/6/16 Nanjing university of industry WuJun 111 劃分區(qū)域 ? 劃分區(qū)域的好處就是將利用洪泛法交換鏈路狀態(tài)信息的范圍局限于每一個區(qū)域而不是整個的自治系統(tǒng)，這就減少了整個網(wǎng)絡(luò)上的通信量。 ? 每一個區(qū)域都有一個 32 bit 的區(qū)域標(biāo)識符（用點分十進(jìn)制表示）。 OSPF 的更新過程收斂得快是其重要優(yōu)點。 ? 這個數(shù)據(jù)庫實際上就是全網(wǎng)的拓?fù)浣Y(jié)構(gòu)圖，它在全網(wǎng)范圍內(nèi)是一致的（這稱為鏈路狀態(tài)數(shù)據(jù)庫的同步）。 ? 只有當(dāng)鏈路狀態(tài)發(fā)生變化時，路由器才用洪泛法向所有路由器發(fā)送此信息。 ? 發(fā)送的信息就是與本路由器相鄰的所有路由器的鏈路狀態(tài)，但這只是路由器所知道的部分信息。 ? 是分布式的鏈路狀態(tài)協(xié)議。 2020/6/16 Nanjing university of industry WuJun 106 內(nèi)部網(wǎng)關(guān)協(xié)議 OSPF (Open Shortest Path First) OSPF 協(xié)議的基本特點 ? “開放”表明 OSPF 協(xié)議不是受某一家廠商控制，而是公開發(fā)表的。 ? RIP 限制了網(wǎng)絡(luò)的規(guī)模 ， 它能使用的最大距離為 15（ 16 表示不可達(dá) ） 。 2020/6/16 Nanjing university of industry WuJun 105 RIP 協(xié)議的優(yōu)缺點 ? RIP 存在的一個問題是當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時 ， 要經(jīng)過比較長的時間才能將此信息傳送到所有的路由器 。 ? 路由標(biāo)記填入自治系統(tǒng)的號碼 ， 這是考慮使RIP 有可能收到本自治系統(tǒng)以外的路由選擇信息 。 每個路由信息需要用 20 個字節(jié) 。 但轉(zhuǎn)發(fā) IP 數(shù)據(jù)報的過程是在網(wǎng)絡(luò)層完成的 。 消除路由循環(huán)的基本方法： 2020/6/16 Nanjing university of industry WuJun 102 RIP 協(xié)議的位置 ? RIP 協(xié)議使用運(yùn)輸層的用戶數(shù)據(jù)報 UDP進(jìn)行傳送 （ 使用 UDP 的端口 520） 。 觸發(fā)更新 當(dāng)路由表發(fā)生變化時，更新報文立即廣播給相鄰的所有路由器，而不是等待 30秒的更新周期。 Distance Vector Routing Protocols ? Pass periodic copies of routing table to neighbor routers and accumulate distance vectors C D B A C B A D Routing Table Routing Table Routing Table Routing Table Distance— How far Vector— In which direction ? Routers discover the best path to destinations from each neighbor A B C E0 S0 S0 S1 S0 E0 Routing Table 0 0 S0 S1 Routing Table S0 0 E0 0 Routing Table E0 S0 0 0 Distance Vector— Sources of Information and Discovering Routes ? Routers discover the best path to destinations from each neighbor A B C E0 S0 S0 S1 S0 E0 Routing Table Routing Table 0 0 1 1 S0 S1 S1 S0 Routing Table S0 0 E0 0 S0 1 E0 S0 S0 1 0 0 Distance Vector— Sources of Information and Discovering Routes Distance Vector— Sources of Information and Discovering Routes ? Routers discover the best path to destinations from each neighbor A B C E0 S0 S0 S1 S0 E0 Routing Table Routing Table 0 0 1 1 S0 S1 S1 S0 Routing Table S0 0 E0 0 S0 S0 1 2 E0 S0 S0 S0 1 2 0 0 Distance Vector— Maintaining Routing Information ? Updates proceed stepbystep from router to router A Process to update this routing table Topology change causes routing table update Distance Vector— Maintaining Routing Information ? Updates proceed stepbystep from router to router A Process to update this routing table Router A sends out this updated routing table after the next period expires Topology change causes routing table update Distance Vector— Maintaining Routing Information ? Updates proceed stepbystep from router to router A B Process to update this routing table Process to update this routing table Topology change causes routing table update Router A sends out this updated routing table after the next period expires Maintaining Routing Information Problem— Routing Loops ? Each node maintains the distance from itself to each possible destination work A B C E0 S0 S0 S1 S0 E0 Routing Table S0 E0 S0 S0 1 2 0 0 Routing Table E0 S0 S0 S0 1 2 0 0 Routing Table S0 S1 S1 S0 1 1 0 0 Maintaining Routing Information Problem— Routing Loops ? Slow convergence produces inconsistent routing A B C E0 S0 S0 S1 S0 E0 X Routing Table S0 E0 S0 S0 1 2 0 Down Routing Table E0 S0 S0 S0 1 2 0 0 Routing Table S0 S1 S1 S0 1 1 0 0 Router C concludes that the best path to work is through Router B Maintaining Routing Information Problem— Routing Loops A B C E0 S0 S0 S1 S0 E0 X Routing Table S0 S0 S0 S0 1 2 0 2 Routing Table E0 S0 S0 S0 1 2 0 0 Routing Table S0 S1 S1 S1 1 1 0 0 Router A updates its table to reflect the new but erroneous hop count Maintaining Routing Information Problem— Routing Loops A B C E0 S0 S0 S1 S0 E0 X Routing Table S0 S0 S0 S0 1 2 0 2 Routing Table E0 S0 S0 S0 1 4 0 0 Routing Table S0 S1 S1 S0 3 1 0 0 Symptom: Counting to Infinity ? Packets for work bounce between routers A, B, and C ? Hop count for work counts to infinity A B C E0 S0 S0 S1 S0 E0 X Routing Table S0 S0 S0 S0 1 2 0 4 Routing Table E0 S0 S0 S0 1 6 0 0 Routing Table S0