計(jì)算機(jī)網(wǎng)絡(luò)原理與實(shí)踐課件ch4

1、第4章網(wǎng)絡(luò)互聯(lián)解放軍理工大學(xué)陳 鳴 博士 計(jì)算機(jī)網(wǎng)絡(luò)原理課程課堂研討：分組到達(dá)到目的地的好算法第13講路由選擇協(xié)議及其算法教學(xué)提示教學(xué)目的掌握基礎(chǔ)性問(wèn)題：異構(gòu)網(wǎng)絡(luò)互聯(lián)、路由選擇和分組轉(zhuǎn)發(fā)重要知識(shí)點(diǎn)虛擬互聯(lián)網(wǎng)方法編址路由選擇移動(dòng)IP學(xué)習(xí)方法理解重要概念，掌握基礎(chǔ)性問(wèn)題4計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐第3章 直連連接的網(wǎng)絡(luò)分組轉(zhuǎn)發(fā)地址映射方法路由器MPLS計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐5路由選擇路由選擇算法的圖論抽象:結(jié)點(diǎn)是路由器邊是物理鏈路鏈路代價(jià): 時(shí)延、費(fèi)用或擁塞等級(jí)目的：決定從源到目的地通過(guò)網(wǎng)絡(luò)的“好的路徑(路由器序列)”路由選擇協(xié)議“好的”路徑:通常是最小費(fèi)用的路徑可以有其他定義是從源結(jié)點(diǎn)到目的結(jié)點(diǎn)的一

2、棵樹(shù)第3章 直連連接的網(wǎng)絡(luò)aedcbf2213112535默認(rèn)路由器源路由器目的路由器AB路由選擇算法分類(lèi)：自治系統(tǒng)內(nèi)或外？第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐6計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐7路由選擇算法分類(lèi)：分布式或集中式？分散或全局的信息?分散的: 路由器知道物理相連的鄰居、到鄰居的鏈路費(fèi)用計(jì)算的迭代過(guò)程，與鄰居交換信息“距離矢量 (distance-vector, DV) ”算法全局的:所有路由器具有完全的拓?fù)?、鏈路費(fèi)用信息“鏈路狀態(tài)(link state algorithm, LS)”算法其他分類(lèi)：靜態(tài)或動(dòng)態(tài)的?靜態(tài): 路由隨時(shí)間緩慢變化動(dòng)態(tài): 路由更快地變化周期的更新適應(yīng)鏈路費(fèi)用變

3、化第3章 直連連接的網(wǎng)絡(luò)第4章：內(nèi)容提要4.1網(wǎng)絡(luò)層概述4.2網(wǎng)絡(luò)服務(wù)模型4.3網(wǎng)際協(xié)議(IP)4.4路由選擇協(xié)議及其算法RIP和距離矢量路由選擇算法OSPF和鏈路狀態(tài)路由選擇算法BGP和層次路由選擇4.5路由器工作原理4.6移動(dòng)IP技術(shù)4.7MPLS4.8IP多播4.9小結(jié)第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐8RIP(路由選擇信息協(xié)議)距離矢量算法包括在1982中的 BSD-UNIX Distribution距離測(cè)度: 跳的數(shù)量(最大 = 15跳)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐9DCBAuvwxyz 目的 跳 u 1 v 2 w 2 x 3 y 3 z 2 RIP特點(diǎn)：僅與相鄰路由器交換信息

4、交換本路由器選路表中的更新信息按固定時(shí)間間隔交換信息，約30秒根據(jù)更新信息，對(duì)本地RIP表進(jìn)行處理第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐10RIP例子 目的子網(wǎng)下一跳路由器到目的子網(wǎng)的跳數(shù)wR12yR32zR36x-1vR42R2中初始選路表目的子網(wǎng)下一跳路由器到目的地的跳數(shù)zR13w-x-來(lái)自路由器R1的通告目的子網(wǎng)下一跳路由器到目的地的跳數(shù)wR12yR32zR14x-1vR42R2更新后的轉(zhuǎn)發(fā)表第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐11距離向量算法基本思想基本思想: 如果鄰居知道到達(dá)目的地的距離，且自己知道到達(dá)鄰居的距離，則能算出自己到達(dá)目的地的距離每個(gè)結(jié)點(diǎn)周期性地向其鄰居發(fā)送

5、自己距離矢量當(dāng)結(jié)點(diǎn)x接收到來(lái)自鄰居的新DV估計(jì)，它使用Bellman-Ford方程更新其自己的DV :Dx(y) minv c(x,v) + Dv(y) 對(duì)每個(gè)結(jié)點(diǎn)y N在規(guī)模較小、正常的條件下，估計(jì)值Dx(y)收斂在實(shí)際最小費(fèi)用 dx(y) 第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐12距離矢量算法例子Bellman-Ford方程(動(dòng)態(tài)規(guī)劃)定義dx(y) := 從x到y(tǒng)最低費(fèi)用路徑的費(fèi)用則dx(y) = minv c(x,v) + dv(y) 其中min對(duì)u的所有鄰居uyxwvz2213112535其中 dv(z) = 5, dx(z) = 3, dw(z) = 3du(z) = min

6、 c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) = min 2 + 5, 1 + 3, 5 + 3 = 4根據(jù)B-F 方程:取最小的結(jié)點(diǎn)是在最短路中的下一跳 轉(zhuǎn)發(fā)表第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐13距離矢量算法分布式迭代迭代、異步: 每次引起本地迭代的原因: 本地鏈路費(fèi)用改變DV從鄰居更新報(bào)文分布式:每個(gè)結(jié)點(diǎn)僅當(dāng)其DV改變時(shí)通知鄰居如果必要，鄰居則通知它們的鄰居等待 (來(lái)自鄰居本地費(fèi)用報(bào)文的變化)重新計(jì)算估計(jì)值如果到任何目的地的DV已經(jīng)變化, 通知鄰居 每個(gè)結(jié)點(diǎn):第3章 直連連接的網(wǎng)絡(luò)距離向量算法(DV算法)1.在每個(gè)結(jié)點(diǎn)x:2.初

7、始化3. 對(duì)所有在N中的目的地y4. Dx(y) = c(x,y) /*如果y不是鄰居則c(x,y) = */5. 對(duì)每個(gè)鄰居w6. Dw(y) = 對(duì)所有在N中的目的地y7. 對(duì)每個(gè)鄰居w8. 向w發(fā)送距離矢量 Dx = Dx(y): N中的y9.loop10. wait (直到發(fā)現(xiàn)對(duì)某個(gè)鄰居w鏈路費(fèi)用變化或從某鄰居w收到一距離矢量)11. 對(duì)在N中的每個(gè)y：12. Dx(y) = minv c(x, v) +Dv(y)13. if Dx(y) 對(duì)任何目的地y變化14. 向所有鄰居發(fā)送距離矢量 Dx = Dx(y): N中的y15.forever第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐1

8、4x y zxyz0 2 7fromcost tofromfromx y zxyz0 x y zxyzcost tox y zxyz710cost to2 0 1 2 0 17 1 0timexz127ynode xtableDx(y) = minc(x,y) + Dy(y), c(x,z) + Dz(y) = min2+0 , 7+1 = 2Dx(z) = minc(x,y) + Dy(z), c(x,z) + Dz(z) = min2+1 , 7+0 = 332 node ytablenode ztablecost tofrom第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐15x y zxy

9、z0 2 3fromcost tox y zxyz0 2 7fromcost tox y zxyz0 2 3fromcost tox y zxyz0 2 3fromcost tox y zxyz0 2 7fromcost to2 0 17 1 02 0 13 1 02 0 13 1 02 0 13 1 02 0 13 1 0timex y zxyz0 2 7fromcost tofromfromx y zxyz0 x y zxyzcost tox y zxyz710cost to2 0 1 2 0 17 1 0timexz127ynode xtableDx(y) = minc(x,y) + D

10、y(y), c(x,z) + Dz(y) = min2+0 , 7+1 = 2Dx(z) = minc(x,y) + Dy(z), c(x,z) + Dz(z) = min2+1 , 7+0 = 332 node ytablenode ztablecost tofrom第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐16計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐17距離矢量算法存在的問(wèn)題及解決鏈路費(fèi)用變化:好消息傳播得快壞消息傳播得慢“計(jì)數(shù)到無(wú)窮”問(wèn)題!在算法穩(wěn)定前，反復(fù)迭代解決方法：毒性逆轉(zhuǎn)如果Z路由通過(guò)Y到 X :Z告訴Y它(Zs)到X的距離是無(wú)窮，使Y將不能采用經(jīng)Z到X的路由這將完全解決計(jì)數(shù)到無(wú)窮問(wèn)題? xz1

11、450y第3章 直連連接的網(wǎng)絡(luò)60第4章：內(nèi)容提要4.1網(wǎng)絡(luò)層概述4.2網(wǎng)絡(luò)服務(wù)模型4.3網(wǎng)際協(xié)議(IP)4.4路由選擇協(xié)議及其算法RIP和距離矢量路由選擇算法OSPF和鏈路狀態(tài)路由選擇算法BGP和層次路由選擇4.5路由器工作原理4.6移動(dòng)IP技術(shù)4.7MPLS4.8IP多播4.9小結(jié)第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐18計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐19OSPF (開(kāi)放最短路優(yōu)先)“open”: 公共免費(fèi)可用使用鏈路狀態(tài)(link state)算法：網(wǎng)絡(luò)拓?fù)浜退墟溌返馁M(fèi)用都已知，可作為L(zhǎng)S算法的輸入LS算法依靠?jī)煞N機(jī)制進(jìn)行路由計(jì)算：LS信息的可靠傳輸積累的鏈路狀態(tài)知識(shí)OSPF兩個(gè)技術(shù)要點(diǎn)

12、：使用洪泛鏈路狀態(tài)信息的鏈路狀態(tài)協(xié)議Dijkstra最低費(fèi)用路徑算法第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐20OSPF特色安全性: 所有OSPF報(bào)文經(jīng)鑒別(以防攻擊) 允許多條費(fèi)用相同的路徑(而RIP僅一條路徑)對(duì)每條鏈路，對(duì)不同的TOS(服務(wù)類(lèi)型)，設(shè)置多種費(fèi)用測(cè)度(如衛(wèi)星鏈路費(fèi)用置為用于盡力而服務(wù)為“低”，高為實(shí)時(shí)服務(wù))綜合的單播和多播支持: 多播OSPF (MOSPF)使用與OSPF相同的拓?fù)鋽?shù)據(jù)庫(kù)在大規(guī)模網(wǎng)絡(luò)中，用層次的OSPF第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐21具有4個(gè)區(qū)域的層次結(jié)構(gòu)OSPF自治系統(tǒng)第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐22層次OSPF兩級(jí)層次

13、: 本地, 主干鏈路狀態(tài)通告僅在本地每個(gè)結(jié)點(diǎn)具有詳細(xì)的區(qū)域拓?fù)洌粌H知道到其他區(qū)域網(wǎng)絡(luò)的方向(最短路)區(qū)域邊界路由器 : “摘要”到在自己區(qū)域網(wǎng)絡(luò)的距離，向其他區(qū)域邊界路由器通告主干路由器 : 運(yùn)行OSPF 路由選擇限制到主干邊界路由器 : 連接到其他AS第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐23一種鏈路狀態(tài)路由選擇算法Dijkstra算法知道網(wǎng)絡(luò)所有結(jié)點(diǎn)的拓?fù)?、鏈路費(fèi)用經(jīng)“鏈路狀態(tài)廣播”所有結(jié)點(diǎn)具有相同信息從一個(gè)結(jié)點(diǎn)(源)到所有其他結(jié)點(diǎn)計(jì)算最低費(fèi)用路徑給出對(duì)這些結(jié)點(diǎn)轉(zhuǎn)發(fā)表迭代: k次迭代后，得知到k個(gè)目的地的最低費(fèi)用路徑概念:c(x,y): 從結(jié)點(diǎn)x到y(tǒng)的鏈路費(fèi)用; = 如果非直接鄰居D

14、(v):從源到目的地v路徑費(fèi)用的當(dāng)前值p(v): 從源到v沿路徑的前任結(jié)點(diǎn)N: 已知在最小費(fèi)用路徑中的結(jié)點(diǎn)集合第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐24Dijsktra算法1 初始化: 2 N = u 3 對(duì)所有結(jié)點(diǎn)v 4 if v 鄰近u 5 then D(v) = c(u,v) 6 else D(v) = 7 8 Loop 9 找出w不在N中使得D(w)最小 10 將w加入N 11 對(duì)于所有v臨近w并不在N中，更新D(v): 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* 到v的新費(fèi)用或是到v的老費(fèi)用或到w加上從w到v的已知最短路費(fèi)用*/ 15

15、until 所有結(jié)點(diǎn)在 N中 第3章 直連連接的網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)：原理與實(shí)踐25LS例子：結(jié)點(diǎn)d建立轉(zhuǎn)發(fā)表的過(guò)程步驟證實(shí)表試探表注釋1(d,0,-)因?yàn)閐是證實(shí)表中唯一新成員，等待鏈路狀態(tài)報(bào)文2(d,0,-)(b,11,b)(c,2,c)鏈路狀態(tài)報(bào)文告訴d，可以費(fèi)用11通過(guò)b到達(dá)b，這是表中最好的路徑，因此將其加入試探表中。同理c也加入。3(d,0,-)(c,2,c)(b,11,b)將試探表中費(fèi)用最小的記錄c加入證實(shí)表中。檢查證實(shí)表中新成員c的鏈路狀態(tài)報(bào)文。4(d,0,-)(c,2,c)(b,5,c)(a,12,c)通過(guò)c到達(dá)b的費(fèi)用是5,記錄(b,11,b)被替換為(b,5,c)。c的鏈路狀態(tài)報(bào)文告知可以費(fèi)用12到達(dá)a。5(d,0,-)(c,2,c)(b,5,c)(a,12,c)把試探表中費(fèi)用最小的記錄b加入證實(shí)表中，觀察它的鏈路狀態(tài)報(bào)文。6(d,0,-)(c,2,c)(b,5,c)(a,10,c)因?yàn)榻?jīng)過(guò)b可以費(fèi)用5到達(dá)a，所以替換試探表中的記錄。7(d,0,-)(c,2,c)(b,5,c) (a,10,c)把試探表中費(fèi)用最小的記錄a移入證實(shí)表中，結(jié)束。第3章 直連連接的網(wǎng)絡(luò)小 結(jié)已學(xué)習(xí)網(wǎng)絡(luò)互聯(lián)的內(nèi)容:RIP使用最早AS內(nèi)部路由選擇協(xié)議，適用范圍較小距離矢量路由選擇算法根據(jù)相鄰信息得到全局最優(yōu)路徑OSPF廣泛應(yīng)用AS內(nèi)部的路由選擇協(xié)議，適用范圍較大將AS