【正文】
主機(jī)的( IP) 協(xié)議地址 ? 網(wǎng)關(guān) – 算法框架 ? 檢查宿協(xié)議地址 ? if 不知道 – then 丟棄分組,返回 ICMP/3: 宿不可達(dá) – else 轉(zhuǎn)發(fā)到下一跳:物理地址將改成下一跳網(wǎng)關(guān)的物理地址 ? 在整個(gè)運(yùn)送過(guò)程中源宿協(xié)議地址一直不變 – 供各網(wǎng)關(guān)確定下一跳 NetID – 到達(dá)宿網(wǎng)絡(luò)后,供網(wǎng)關(guān)將該分組遞交宿主機(jī) 2020/6/16 Nanjing university of industry WuJun 49 分組運(yùn)送 ? 分組運(yùn)送過(guò)程圖例 SHost R1 R2 R3 Dhost To: DHost (IP) R11 (MAC) 1 2 3 4 To: DHost (IP) R22 (MAC) To: DHost (IP) R33 (MAC) To: DHost (IP) DHost (MAC) 2020/6/16 Nanjing university of industry WuJun 50 算法設(shè)計(jì)目標(biāo) ? 路由算法一般追求下列(通常不可能是全部)目標(biāo) ? 優(yōu)化 – 選擇最佳路徑。 2020/6/16 Nanjing university of industry WuJun 77 “距離”的定義 ? 從一路由器到直接連接的網(wǎng)絡(luò)的距離定義為 1。RIP 選擇一個(gè)具有最少路由器的路由 ( 即最短路由 ) , 哪怕還存在另一條高速 (低時(shí)延 )但路由器較多的路由 。 2020/6/16 Nanjing university of industry WuJun 81 距離向量算法 收到相鄰路由器(其地址為 X)的一個(gè) RIP 報(bào)文: (1) 先修改此 RIP 報(bào)文中的所有項(xiàng)目:將 “ 下一跳 ” 字段中的地址都改為 X,并將所有的 “ 距離 ” 字段的值加 1。 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 S1 S1 S0 5 1 0 0 Solution: Defining a Maximum ? Define a limit on the number of hops to prevent infinite loops A B C E0 S0 S0 S1 S0 E0 X Routing Table S0 S0 S0 S0 1 2 0 16 Routing Table E0 S0 S0 S0 1 16 0 0 Routing Table S0 S1 S1 S0 16 1 0 0 Solution 1: Split Horizon ? It is never useful to send information about a route back in the direction from which the original packet came A B C E0 S0 S0 S1 S0 E0 X X X Routing Table S0 S0 S0 S0 1 2 0 0 Routing Table E0 S0 S0 S0 1 2 0 0 Routing Table S0 S1 S1 E1 1 2 0 0 Solution 2: Route Poisoning ? Routers set the distance of routes that have gone down to infinity A B C E0 S0 S0 S1 S0 E0 X Routing Table S0 S0 S0 S0 1 2 0 Infinity Routing Table E0 S0 S0 S0 1 2 0 0 Routing Table S0 S1 S1 E1 1 2 0 0 Solution 2: Poison Reverse ? Poison Reverse overrides split horizon A B C E0 S0 S0 S1 S0 E0