計(jì)算機(jī)網(wǎng)絡(luò)網(wǎng)絡(luò)層路由算法

1、BACDEGFHIJ路由器B的匯集樹假設(shè)使用延遲作為距離度量，并且路由器知道他到每個(gè)鄰居的延遲。每隔T秒每個(gè)路由器向他的每個(gè)鄰居發(fā)送一個(gè)表，該表記錄了它到每個(gè)目標(biāo)的延遲，同時(shí)它也從鄰居那里收到一個(gè)類似的表。交換距離信息更新路由表示例 第第1 1次交換后次交換后 第第3 3次交換后次交換后A AB BC CD DE E1 12 23 34 4 初始時(shí)初始時(shí)3 32 23 34 4 第第1 1次交換后次交換后3 34 43 34 4 第第2 2次交換后次交換后5 54 45 54 4 第第3 3次交換后次交換后5 56 65 56 6 第第4 4次交換后次交換后7 76 67 76 6 第第5 5

2、次交換后次交換后7 78 87 78 8 第第6 6次交換后次交換后（b b）. . . .A AB BC CD DE E 初始時(shí)初始時(shí)1 11 12 2 第第2 2次交換后次交換后1 12 23 31 12 23 34 4 第第4 4次交換后次交換后（a a）問題的核心在于當(dāng)X告訴Y自己有一條通往某個(gè)地方的路徑的Y不知道自己是否在這條路徑上。發(fā)現(xiàn)鄰居 在每一條點(diǎn)到點(diǎn)的線路上發(fā)送一個(gè)特殊的HELLO數(shù)據(jù)包，線路另一端的路由器返回一個(gè)應(yīng)答說明自己是誰。 兩個(gè)或多個(gè)路由器通過一個(gè)廣播鏈路連接的情況：鏈路狀態(tài)包一個(gè)網(wǎng)絡(luò)示例路由器路由器B B的狀態(tài)包緩沖區(qū)的狀態(tài)包緩沖區(qū)特殊情況特殊情況：如果一個(gè)重復(fù)數(shù)

3、據(jù)包到來時(shí)，原來：如果一個(gè)重復(fù)數(shù)據(jù)包到來時(shí)，原來的數(shù)據(jù)包仍然在緩沖區(qū)。此時(shí)標(biāo)志位的變化。的數(shù)據(jù)包仍然在緩沖區(qū)。此時(shí)標(biāo)志位的變化。C的副本從的副本從F到達(dá)，那么標(biāo)志位變?yōu)榈竭_(dá)，那么標(biāo)志位變?yōu)?00011.計(jì)算新路由計(jì)算新路由：利用：利用Dijikstra算法。算法。鏈路狀態(tài)路由算法優(yōu)點(diǎn)：沒有慢收斂問題。鏈路狀態(tài)路由算法優(yōu)點(diǎn)：沒有慢收斂問題。1A完整表完整表1A層次表層次表區(qū)域區(qū)域1區(qū)域區(qū)域5區(qū)域區(qū)域4區(qū)域區(qū)域3區(qū)域區(qū)域2兩級(jí)分層實(shí)例路由器收到廣播分組，看到來那條路徑是否是用來給廣播源發(fā)送分組的那條線路，是，轉(zhuǎn)發(fā)到其他所有線路上，否則，丟棄。逆向路徑轉(zhuǎn)發(fā)的優(yōu)點(diǎn)：有效而且易于實(shí)現(xiàn)。 (a) 網(wǎng)絡(luò)實(shí)例

4、. (b) 最左邊路由器的一顆生成樹. (c) 組1的一顆組播樹 (d) 組2的一顆組播樹組1的選播路由路由協(xié)議看到的拓?fù)浣Y(jié)構(gòu)11111發(fā)送者發(fā)送者2往家鄉(xiāng)地址發(fā)送數(shù)據(jù)包往家鄉(xiāng)地址發(fā)送數(shù)據(jù)包1注冊(cè)轉(zhuǎn)交地址注冊(cè)轉(zhuǎn)交地址3隧道到轉(zhuǎn)交地址隧道到轉(zhuǎn)交地址家鄉(xiāng)代理家鄉(xiāng)代理移動(dòng)主機(jī)移動(dòng)主機(jī)4應(yīng)答應(yīng)答發(fā)送者發(fā)送者5隧隧道道到到轉(zhuǎn)轉(zhuǎn)交交地地址址n(a) Range of As broadcast.n(b) After B and D have received As broadcast.n(c) After C, F, and G have received As broadcast.n(d) After E, H, and I have received As broadcast.Shaded nodes are new recipients. Arrows show possible reverse routes.每個(gè)節(jié)點(diǎn)周期性的廣播一個(gè)HELLO消息并期望它的鄰