第18講路由選擇協(xié)議RIP1計(jì)算機(jī)網(wǎng)絡(luò)原理

第18講謝鈞教授

網(wǎng)絡(luò)工程教研室第18講路由選擇協(xié)議RIP2回顧及問題的引入主機(jī)A主機(jī)B網(wǎng)1R1R2R4R3目的下一站網(wǎng)1 R2網(wǎng)2 R4…R1的路由表網(wǎng)2如何得到路由表？網(wǎng)3網(wǎng)4網(wǎng)5網(wǎng)6網(wǎng)1,主機(jī)B網(wǎng)7網(wǎng)1,主機(jī)B

自動(dòng)計(jì)算到達(dá)每個(gè)網(wǎng)絡(luò)的最佳路徑（路由選擇）路由器第4章網(wǎng)絡(luò)層3靜態(tài)路由選擇和動(dòng)態(tài)路由選擇靜態(tài)路由選擇——即非自適應(yīng)路由選擇，其特點(diǎn)是簡(jiǎn)單和路由器開銷較小，但不能及時(shí)適應(yīng)網(wǎng)絡(luò)狀態(tài)的變化，只能用于簡(jiǎn)單的小型網(wǎng)絡(luò)。動(dòng)態(tài)路由選擇——對(duì)于復(fù)雜多變的大型網(wǎng)絡(luò)必須采用動(dòng)態(tài)路由選擇。動(dòng)態(tài)路由選路能適應(yīng)網(wǎng)絡(luò)狀態(tài)的不斷變化，但實(shí)現(xiàn)起來較為復(fù)雜，路由器的開銷也比較大。

要實(shí)現(xiàn)動(dòng)態(tài)路由，路由器之間就必須互相交換網(wǎng)絡(luò)拓?fù)浜蜖顟B(tài)信息！第4章網(wǎng)絡(luò)層4動(dòng)態(tài)路由選擇的基本方法路由器之間要互相不斷交換網(wǎng)絡(luò)拓?fù)浜蜖顟B(tài)信息，然后根據(jù)這些信息求出到所有目的地的最佳路由路由選擇協(xié)議要解決的5個(gè)問題Best，什么是最佳路由？Who，和誰進(jìn)行交換信息？What，交換什么信息？When，何時(shí)進(jìn)行交換信息？How，如何計(jì)算和更新路由表？課堂討論題每個(gè)路由器開始僅知道與它直接連接的網(wǎng)絡(luò)，因此路由器知道如何轉(zhuǎn)發(fā)到其直接連接的網(wǎng)絡(luò)的分組，對(duì)于不直接連接的網(wǎng)絡(luò)，有什么辦法（不用集中控制）讓路由器知道該網(wǎng)絡(luò)的存在，并能找到一條到該網(wǎng)絡(luò)“好”的路徑？網(wǎng)1網(wǎng)6網(wǎng)5網(wǎng)2網(wǎng)3網(wǎng)4R1R2R3第5章網(wǎng)絡(luò)層6課堂討論題將自己想象成一個(gè)路由器僅知道直接連接的網(wǎng)絡(luò)可以和鄰居交流如何知道其他網(wǎng)絡(luò)？如何選擇最好的路徑？第18講路由選擇協(xié)議RIP74.5.2路由信息協(xié)議RIP

(RoutingInformationProtocol)經(jīng)過路由器最少的路由RIP中“距離”的定義：一個(gè)路由器到某網(wǎng)絡(luò)的距離定義為到該網(wǎng)絡(luò)所經(jīng)過的路由器數(shù)加1。1.RIP協(xié)議中的最佳路由第18講路由選擇協(xié)議RIP8RIP中距離的定義主機(jī)A主機(jī)B網(wǎng)1R1R2R4R3網(wǎng)2網(wǎng)3網(wǎng)4網(wǎng)5網(wǎng)6網(wǎng)7路由器R1到網(wǎng)3的距離為1，到網(wǎng)1的距離為2第18講路由選擇協(xié)議RIP92.RIP協(xié)議的基本思路

網(wǎng)絡(luò)NR......源目的第18講路由選擇協(xié)議RIP102.RIP協(xié)議的基本思路

網(wǎng)絡(luò)NR......

如果一個(gè)路由器知道其所有鄰居到目的網(wǎng)絡(luò)的最短距離，則可計(jì)算出它到該目的網(wǎng)絡(luò)的最短距離和下一路由器

相鄰結(jié)點(diǎn)間互相不斷通告到目的網(wǎng)絡(luò)的目前已知的最短距離，不斷計(jì)算新的最短距離源目的第18講路由選擇協(xié)議RIP113.RIP協(xié)議的具體算法每個(gè)路由器定期（如每隔30秒）將自己當(dāng)前知道的到所有目的網(wǎng)絡(luò)的距離通告給所有相鄰路由器。每個(gè)路由器根據(jù)收到的路由信息計(jì)算最短路徑并更新自己的路由表。?第18講路由選擇協(xié)議RIP12網(wǎng)NdRIP協(xié)議路由表的更新XY我到網(wǎng)N的距離為d路由器Y通過X到網(wǎng)N的距離為d+1目的下一站距離N X d+1Y的路由表：第18講路由選擇協(xié)議RIP13RIP協(xié)議路由表的更新XY網(wǎng)N路由器Y通過X到網(wǎng)N的距離為d+1目的下一站距離N Z bN X d+1(若d+1<b)Y的路由表：Z我到網(wǎng)N的距離為d第18講路由選擇協(xié)議RIP14目的下一站距離N X bRIP協(xié)議路由表的更新XY網(wǎng)N我到網(wǎng)N的距離為dN X d+1(采用最新信息)該算法被稱為：距離向量算法將新路由表發(fā)送給他的所有鄰居?路由器Y通過X到網(wǎng)N的距離為d+1Y的路由表：第18講路由選擇協(xié)議RIP15距離向量算法以Bellman-Ford算法為基礎(chǔ)RichardBellman(1920～1984)美國(guó)數(shù)學(xué)家，美國(guó)全國(guó)科學(xué)院院士，動(dòng)態(tài)規(guī)劃的創(chuàng)始人。1957年他的專著《動(dòng)態(tài)規(guī)劃》出版后，被迅速譯成俄文、日文、德文和法文，對(duì)控制理論界和數(shù)學(xué)界有深遠(yuǎn)影響。將網(wǎng)絡(luò)抽象成一個(gè)圖第4章網(wǎng)絡(luò)層16將網(wǎng)絡(luò)抽象成一個(gè)圖第4章網(wǎng)絡(luò)層172111522335ABCDEFBellman-Ford：若A到C的最短路徑為ADEC，則ADE，和EC也一定分別是A到E和E到C的最短距離。第18講路由選擇協(xié)議RIP18R2R1網(wǎng)A網(wǎng)C網(wǎng)B網(wǎng)A1網(wǎng)A2R1說：“我到網(wǎng)

A距離為1”R2說：“我到網(wǎng)

A距離為2”RIP協(xié)議交互過程舉例R3

的更新路由表為“A,3,R2”

。但R1

不會(huì)更改到網(wǎng)A的距離。R3網(wǎng)D網(wǎng)A2第18講路由選擇協(xié)議RIP19R2R1網(wǎng)A網(wǎng)C網(wǎng)B網(wǎng)A

網(wǎng)A2R1

說：“我到網(wǎng)A的距離是無窮（表示無法到達(dá)）”R2

在收到R1

的更新報(bào)文之前，可能會(huì)先發(fā)送自己的路由信息給R1

。RIP協(xié)議交互過程舉例?(A,1,-)(A,2,R1)(A,

,-)第18講路由選擇協(xié)議RIP20R2R1網(wǎng)A網(wǎng)C網(wǎng)B網(wǎng)A

網(wǎng)A2R1收到R2的更新報(bào)文后，誤認(rèn)為可經(jīng)過R2

到達(dá)網(wǎng)A，于是更新自己的路由表，說：“我到網(wǎng)A的距離是3”。然后將此更新信息發(fā)送給R2。網(wǎng)A3RIP協(xié)議交互過程舉例第18講路由選擇協(xié)議RIP21RIP協(xié)議交互過程舉例R2R1網(wǎng)A網(wǎng)C網(wǎng)B網(wǎng)A

網(wǎng)A2R2以后又更新自己的路由表為“A,4,R1”，表明“我到網(wǎng)A距離是4，下一跳經(jīng)過R1”。網(wǎng)A3網(wǎng)A4?RIP規(guī)定當(dāng)距離為16時(shí)表示不可達(dá)第18講路由選擇協(xié)議RIP22RIP協(xié)議交互過程舉例R2R1網(wǎng)A網(wǎng)C網(wǎng)B…網(wǎng)A16網(wǎng)A3網(wǎng)A5網(wǎng)A16網(wǎng)A2網(wǎng)A4網(wǎng)A16…這樣不斷更新下去，直到R1和R2到網(wǎng)A的距離都增大到16時(shí)，R1和R2才知道網(wǎng)A是不可達(dá)的。這就是好消息傳播得快，而壞消息傳播得慢。網(wǎng)絡(luò)出故障的傳播時(shí)間往往需要較長(zhǎng)的時(shí)間(例如數(shù)分鐘)。這是RIP的一個(gè)主要缺點(diǎn)。會(huì)帶來什么樣的后果？在算法收斂前會(huì)導(dǎo)致錯(cuò)誤的路由：路由環(huán)路。第18講路由選擇協(xié)議RIP234.“壞消息傳播得慢”問題R2R1網(wǎng)A網(wǎng)C網(wǎng)B…網(wǎng)A16網(wǎng)A3網(wǎng)A5網(wǎng)A16網(wǎng)A2網(wǎng)A4網(wǎng)A16…水平分割：如果R2到某網(wǎng)絡(luò)的下一站為R1，則R2不向R1通告它到該網(wǎng)絡(luò)的距離。有沒有辦法解決該問題？第18講路由選擇協(xié)議RIP244.“壞消息傳播得慢”問題R2R1網(wǎng)A網(wǎng)C網(wǎng)B…網(wǎng)A16網(wǎng)A3網(wǎng)A5網(wǎng)A16網(wǎng)A2網(wǎng)A4網(wǎng)A16…能徹底解決該問題嗎？第5章網(wǎng)絡(luò)層254.“壞消息傳播得慢”問題R2R1網(wǎng)A網(wǎng)C網(wǎng)B