距離矢量算法解析ppt課件.ppt

1、距離矢量算法解析,主要內(nèi)容,1、什么是動(dòng)態(tài)路由 2、動(dòng)態(tài)路由根據(jù)算法的分類 3、距離矢量算法詳解 4、路由環(huán)路 5、水平分割,動(dòng)態(tài)路由協(xié)議,動(dòng)態(tài)路由協(xié)議特點(diǎn) 向其他路由器傳遞路由信息 接收其他路由器的路由信息 根據(jù)收到的路由信息計(jì)算出到每個(gè)目的網(wǎng)絡(luò)的最優(yōu)路徑，并由此生成路由表 根據(jù)網(wǎng)絡(luò)拓樸變化及時(shí)調(diào)整路由表，同時(shí)向其他路由器宣告拓樸改變的信息,動(dòng)態(tài)路由協(xié)議,根據(jù)路由所執(zhí)行的算法分類 距離矢量路由協(xié)議 鏈路狀態(tài)路由協(xié)議,距離矢量路由協(xié)議,路由器每經(jīng)過(guò)特定時(shí)間周期向鄰居發(fā)送自己的路由表 距離：有多遠(yuǎn) 矢量：從哪個(gè)方向,R1,R2,R,我能夠到達(dá)路由器R，距離是5,我通過(guò)R2可以到達(dá)路由器R，R2到

2、R之間的具體細(xì)節(jié)我不清楚,距離矢量詳解,R1,R2,距離矢量算法思想： 矢量距離算法（簡(jiǎn)稱VD算法）的思想是：網(wǎng)關(guān)周期性地向外廣播路徑刷新報(bào)文，主要內(nèi)容是由若干（V，D）序偶組成的序偶表；（V，D）序偶中的V代表“向量”，標(biāo)識(shí)網(wǎng)關(guān)可到達(dá)的信宿（網(wǎng)關(guān)或主機(jī)），D代表距離，指出該網(wǎng)關(guān)去往信宿V的距離；距離D按驛站的個(gè)數(shù)計(jì)。其他網(wǎng)關(guān)收到某網(wǎng)關(guān)的（V，D）報(bào)文后，據(jù)此按照最短路徑原則對(duì)各自的路由表進(jìn)行刷新,RIP工作原理 - 距離矢量算法,路由算法 D( i, j)= 0 D( i, j) =MIN d(i, k)+ D(k, j) k為所有與i相鄰的路由器 圖示距離矢量算法,距離矢量詳解,A,B,C

3、,F,G,D,E,1、對(duì)距離向量路由所做的初始假設(shè)是每個(gè)結(jié)點(diǎn)都知道其鄰接點(diǎn)得鏈路開 銷。 到不相鄰結(jié)點(diǎn)的鏈路開銷被指定為無(wú)窮大； 2、每條路徑的開銷為1，所以開銷最小的路徑就是包含跳數(shù)最少的路徑。,距離矢量詳解包含到其他所有結(jié)點(diǎn)開銷,存儲(chǔ)在每個(gè)結(jié)點(diǎn)中的初始距離,距離矢量詳解發(fā)送包含自己距離表的消息給其他鄰接點(diǎn),1、結(jié)點(diǎn)F告訴A它可以到結(jié)點(diǎn)G，開銷為1，A也知道它能以開銷1到達(dá)F，因此二者相加就可以知道經(jīng)F到G的開銷；A到G的總開銷2小于當(dāng)前的開銷無(wú)窮大，因此A記錄它可經(jīng)F到達(dá)G，開銷為2； 2、類似的，A從C得知，C能以開銷1到達(dá)D；A將此與到C的開銷1相加，決定可通過(guò)C以開銷2到達(dá)D，優(yōu)于舊

4、的開銷無(wú)窮大 3、同時(shí)，A從C得知，C能以開銷1到達(dá)B，因此它推斷經(jīng)C到B的開銷為2，這比當(dāng)前A到B的開銷1大，因此新的信息被忽略。,距離矢量詳解發(fā)送包含自己距離表的消息給其他鄰接點(diǎn),結(jié)點(diǎn)A的初始路由表,結(jié)點(diǎn)A的最終路由表,距離矢量詳解,存儲(chǔ)在每個(gè)結(jié)點(diǎn)的最終距離,路由環(huán)路1,R1,R2,R3,10.0.0.0,20.0.0.0,30.0.0.0,40.0.0.0,.1,.1,.2,.2,路由環(huán)路2,R1,R2,R3,10.0.0.0,20.0.0.0,30.0.0.0,40.0.0.0,.1,.1,.2,.2,發(fā)送40.0.0.0的跳數(shù)為1的更新信息,被標(biāo)記為無(wú)效,路由環(huán)路3,R1,R2,R3

5、,10.0.0.0,20.0.0.0,30.0.0.0,40.0.0.0,.1,.1,.2,.2,發(fā)送40.0.0.0的路由更新，跳數(shù)為2,將跳數(shù)改變?yōu)?跳，下一條地址為30.0.0.1,路由環(huán)路4,R1,R2,R3,10.0.0.0,20.0.0.0,30.0.0.0,40.0.0.0,.1,.1,.2,.2,產(chǎn)生路由環(huán)路，直到跳數(shù)增加到16為止,將跳數(shù)改變?yōu)?跳,解決路由環(huán)路的方法,水平分割 毒性反轉(zhuǎn) 觸發(fā)更新 Hold-down倒計(jì)時(shí),10.1.0.0,10.2.0.0,10.3.0.0,10.4.0.0,E0,S0,S0,S1,S0,E0,X,X,X,C,B,A,水平分割,RIP從某個(gè)

6、接口學(xué)到的路由不再?gòu)脑摻涌诎l(fā)布給其他路由器,當(dāng)一條路徑信息變?yōu)闊o(wú)效之后，路由器并不立即將它從路由表中刪除，而是用16，即不可達(dá)的度量值將它廣播出去。缺點(diǎn)增加了路由表的大小。,毒性反轉(zhuǎn),10.1.0.0,10.2.0.0,10.3.0.0,E0,S0,S0,S1,S0,E0,X,Subnet 10.4.0.0 metric 16,A,B,C,觸發(fā)更新,10.2.0.0,10.3.0.0,10.4.0.0,E0,S0,S0,S1,S0,E0,X,subnet 10.4.0.0, metric 16,10.1.0.0,subnet 10.4.0.0, metric 16,subnet 10.4.0.

7、0, metric 16,A,C,B,得知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生改變,不等待發(fā)送周期 ,立刻通告更新后全部的路由表,Hold-down倒記時(shí),10.1.0.0,10.2.0.0,10.3.0.0,10.4.0.0,E0,S0,S0,S1,S0,E0,X,hold-down倒記時(shí)以后更新路由表,A,B,C,等待網(wǎng)絡(luò)中其它路由器收斂,在該時(shí)間內(nèi)不學(xué)習(xí)任何與該網(wǎng)絡(luò)相關(guān)的路由信息(RIP缺省180秒),在倒記時(shí)其間繼續(xù)向其它路由器發(fā)送毒化信息,RIP,講解RIP時(shí)注意幾個(gè)數(shù)字 520，RIP協(xié)議是應(yīng)用層協(xié)議，基于UDP，端口520 15，RIP協(xié)議規(guī)定兩點(diǎn)間最大跳數(shù)為15 16，當(dāng)RIP產(chǎn)生路由信息metric為16時(shí)，表示該路由信息不可達(dá) 30，RIP協(xié)議每隔30秒發(fā)送一次更新報(bào)文 180，路由器如果180沒(méi)有收到來(lái)