第七章 網(wǎng)絡(luò)互連 之 路由協(xié)議

1、路由協(xié)議（RIP，OSPF和BGP） “互聯(lián)網(wǎng)絡(luò)”（internet）是路由器連接而成的多個(gè)網(wǎng)絡(luò)的組合體。當(dāng)數(shù)據(jù)報(bào)從一個(gè)源端傳送到一個(gè)目標(biāo)端時(shí)，可能需要通過(guò)很多個(gè)路由器才到達(dá)與目標(biāo)網(wǎng)絡(luò)連接的路由器。 路由器的作用是從一個(gè)網(wǎng)絡(luò)中接收數(shù)據(jù)包（packet，分組），然后將它傳送給另一個(gè)網(wǎng)絡(luò)。一個(gè)路由器通常與幾個(gè)網(wǎng)絡(luò)連接，這樣，當(dāng)它收到一個(gè)數(shù)據(jù)包時(shí)，應(yīng)該將數(shù)據(jù)包轉(zhuǎn)發(fā)給哪個(gè)網(wǎng)絡(luò)呢？路由器是按最佳化原則進(jìn)行判定：哪個(gè)可用的路徑是最佳路徑？ 人們用metric來(lái)表示通過(guò)某個(gè)網(wǎng)絡(luò)時(shí)所指定的“成本”（cost，代價(jià)）。一個(gè)特定路由的總metric，等于包含了該路由的多個(gè)網(wǎng)絡(luò)的metric之和。路由器根據(jù)最短（最

2、?。┑膍etric來(lái)選擇路由。Metric電信專業(yè) n. 米制的,量度的計(jì)算機(jī)專業(yè) 度量，尺度；公制 分配給每個(gè)網(wǎng)絡(luò)的metric取決于協(xié)議的類型。某些簡(jiǎn)單的協(xié)議，如“路由信息協(xié)議”（RIP），將每個(gè)網(wǎng)絡(luò)同等處理，即通過(guò)每個(gè)網(wǎng)絡(luò)的cost是一樣的，或者說(shuō)都是一個(gè)“跳數(shù)”（one hop count）。所以如果一個(gè)數(shù)據(jù)包通過(guò)10個(gè)網(wǎng)絡(luò)才到達(dá)目標(biāo)端，其總cost就是10個(gè)“跳數(shù)”。 其他協(xié)議，如“開(kāi)放最短路徑優(yōu)先協(xié)議”（OSPF），則允許管理員根據(jù)所需的服務(wù)類型，為通過(guò)一個(gè)網(wǎng)絡(luò)指定cost。通過(guò)某個(gè)網(wǎng)絡(luò)的路由可以具有不同的cost（metric）。例如，如果所需的服務(wù)類型是“最大吞吐量”（thro

3、ughput），一條衛(wèi)星鏈路就比一條光纖鏈路具有更低的metric。另一方面，如果所需的服務(wù)類型是“最小延遲”，一條光纖鏈路就比一條衛(wèi)星鏈路具有更低的metric。OSPF允許每個(gè)路由器根據(jù)所需的服務(wù)類型擁有幾個(gè)路由表。 其他協(xié)議定義metric的方法則完全不同。在“邊緣網(wǎng)關(guān)協(xié)議”（BGP）中，評(píng)定的標(biāo)準(zhǔn)是可以由管理員設(shè)置的所謂“策略”（policy）?！安呗浴倍x了應(yīng)該選擇的是哪個(gè)路徑。 不管metric是如何確定的，路由器在準(zhǔn)備轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，都必須使用路由表。路由表應(yīng)為數(shù)據(jù)包規(guī)定最佳路徑。不過(guò)，路由表可以是靜態(tài)的，也可以是動(dòng)態(tài)的。 “靜態(tài)路由表”是那種不經(jīng)常變化的路由表。 “動(dòng)態(tài)路由表”是

4、那種當(dāng)互聯(lián)網(wǎng)絡(luò)中的某處出現(xiàn)變化時(shí)能自動(dòng)更新的路由表。 今天，互聯(lián)網(wǎng)絡(luò)需要的是動(dòng)態(tài)路由表。這種路由表要求互聯(lián)網(wǎng)絡(luò)出現(xiàn)變化時(shí)即被盡快更新。例如，當(dāng)某個(gè)路由關(guān)閉（down）時(shí)，需要進(jìn)行更新；而當(dāng)一個(gè)更好的路由建立后，也需要進(jìn)行更新。 各種路由協(xié)議都是為了動(dòng)態(tài)路由表的需要而制定的。 一個(gè)路由協(xié)議是一組規(guī)則和程序的組合， 用于使互聯(lián)網(wǎng)絡(luò)中的路由器們相互告知有關(guān)的變化情況。它使路由器們共享它們所掌握的互聯(lián)網(wǎng)絡(luò)或相鄰路由器的情況。這種信息的共享使得武漢的某個(gè)路由器可以知道上海的網(wǎng)絡(luò)出現(xiàn)故障了。 路由協(xié)議還包含了將從其他路由器接收的信息綜合起來(lái)的處理程序。 內(nèi)部和外部路由 今天，一個(gè)互聯(lián)網(wǎng)絡(luò)可能很大，以致一個(gè)

5、路由協(xié)議無(wú)法完成為所有路由器更新路由表的任務(wù)。為此，需要將一個(gè)互聯(lián)網(wǎng)絡(luò)分為若干“自治系統(tǒng)”（autonomous systems，AS）。 一個(gè)“自治系統(tǒng)”是指由同一個(gè)管理員管理的一組網(wǎng)絡(luò)和路由器。 自治系統(tǒng)內(nèi)部的路由稱為“內(nèi)部路由”， 自治系統(tǒng)之間的路由稱為“外部路由”。 每個(gè)自治系統(tǒng)都可以選擇一個(gè)內(nèi)部路由協(xié)議來(lái)處理該自治系統(tǒng)內(nèi)部的路由。但是，自治系統(tǒng)之間的路由通常只能使用一個(gè)外部路由協(xié)議來(lái)處理。 路由器R1，R2和R3使用一個(gè)內(nèi)部路由協(xié)議和一個(gè)外部路由協(xié)議。其他路由器只使用內(nèi)部路由協(xié)議。 陰影部分表示使用內(nèi)部路由協(xié)議的各自治系統(tǒng)。細(xì)實(shí)線表示使用內(nèi)部路由協(xié)議的各路由器間的通信連接。 粗實(shí)線表

6、示使用外部路由協(xié)議的各路由器間的通信連接。 現(xiàn)在使用的內(nèi)部和外部路由協(xié)議很多。本章只介紹最常用的幾種。下面討論兩個(gè)內(nèi)部路由協(xié)議（RIP和OSPF）和一個(gè)外部路由協(xié)議（BGP）。 RIP和OSPF可用于自治系統(tǒng)內(nèi)部路由表的更新。 BGP可用于為連接自治系統(tǒng)的各個(gè)路由器進(jìn)行路由表更新。路由算法路由算法：根據(jù)網(wǎng)絡(luò)拓?fù)溆?jì)算路由的方法。：根據(jù)網(wǎng)絡(luò)拓?fù)溆?jì)算路由的方法。 或路由表的生成方法?；蚵酚杀淼纳煞椒?。兩種路由算法：兩種路由算法： 矢量矢量- -距離（距離（ V-DV-D）算法）算法 如如RIP（路由信息）（路由信息） 鏈路狀態(tài)（鏈路狀態(tài)（L-SL-S）算法）算法 如如OSPF（開(kāi)放最短路徑優(yōu)先）（

7、開(kāi)放最短路徑優(yōu)先）矢量-距離（ V-D）算法路由表中列出所有已知的路由啟動(dòng)時(shí)路由器對(duì)每個(gè)與自己直連的網(wǎng)絡(luò)生成一個(gè)表項(xiàng)每個(gè)路由器周期地向直接相連的其他路由器發(fā)送自己的 路由表每個(gè)路由器根據(jù)其他路由器發(fā)來(lái)的路由更新消息，相應(yīng) 修改自己的路由表周期性傳送的信息包括： （目的網(wǎng)絡(luò)地址(矢量)V，到達(dá)該網(wǎng)絡(luò)的距離D） 這就是矢量-距離算法名稱的來(lái)源不需要傳送路由信息，只需： 1）檢測(cè)所有相鄰相鄰路由器的狀態(tài)(相鄰：通過(guò)同一網(wǎng)絡(luò)連接的兩個(gè)路由器相鄰：通過(guò)同一網(wǎng)絡(luò)連接的兩個(gè)路由器) -周期地向相鄰路由器發(fā)送“Hello”報(bào)文，詢問(wèn)其工作狀態(tài) 2）周期地向其他路由器通告自己了解到的鏈接狀態(tài)信息 -鏈路類型、鏈

8、路標(biāo)識(shí)、通告該鏈路的路由器地址每個(gè)路由器根據(jù)其他路由器發(fā)來(lái)的鏈路狀態(tài)報(bào)文，相應(yīng)地更新自己 的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)庫(kù)最終每個(gè)路由器都具有同樣的網(wǎng)絡(luò)拓?fù)渥罱K每個(gè)路由器都具有同樣的網(wǎng)絡(luò)拓?fù)?結(jié)構(gòu)數(shù)據(jù)庫(kù)（即共享一個(gè)公共的連接狀態(tài)數(shù)據(jù)庫(kù)），稱為收斂結(jié)構(gòu)數(shù)據(jù)庫(kù)（即共享一個(gè)公共的連接狀態(tài)數(shù)據(jù)庫(kù)），稱為收斂路由器使用Dijkstra最短路徑算法對(duì)網(wǎng)絡(luò)拓?fù)鋱D求最短路徑計(jì) 算到達(dá)其他網(wǎng)絡(luò)的最短路徑最后用計(jì)算出來(lái)的最短路徑更新自己的路由表D-V和和L-S算法的比較算法的比較D-V 通過(guò)與鄰居的信息交換通過(guò)與鄰居的信息交換獲得網(wǎng)絡(luò)拓?fù)渲R(shí)獲得網(wǎng)絡(luò)拓?fù)渲R(shí) 路由計(jì)算是增加路由器路由計(jì)算是增加路由器之間的站點(diǎn)數(shù)（之間的站點(diǎn)數(shù)

9、（hops） 定期刷新路由：收斂慢定期刷新路由：收斂慢 向相鄰站點(diǎn)傳送路由表向相鄰站點(diǎn)傳送路由表的副本的副本L-S 全網(wǎng)獲得共同的全局性全網(wǎng)獲得共同的全局性網(wǎng)絡(luò)拓?fù)渲R(shí)（網(wǎng)絡(luò)拓?fù)渲R(shí)（L-S圖）圖） 計(jì)算到達(dá)其他站點(diǎn)的最計(jì)算到達(dá)其他站點(diǎn)的最短路徑（短路徑（SPF準(zhǔn)則）準(zhǔn)則） 觸發(fā)刷新：收斂快觸發(fā)刷新：收斂快 向其他站點(diǎn)發(fā)送鏈路狀向其他站點(diǎn)發(fā)送鏈路狀態(tài)的動(dòng)態(tài)變化態(tài)的動(dòng)態(tài)變化RIP（路由信息協(xié)議） 路由信息協(xié)議是一個(gè)用于自治系統(tǒng)內(nèi)部的 “內(nèi)部路由協(xié)議”。它是一種非常簡(jiǎn)單的協(xié)議，基于 “距離向量路由” 技術(shù)。 距離向量路由在“距離向量路由”中，每個(gè)路由器都定期地和其相鄰的路由器們共享它們對(duì)整個(gè)互聯(lián)網(wǎng)

10、絡(luò)掌握的情況。理解這一算法的工作原理有三個(gè)關(guān)鍵，如下：1、 共享整個(gè)自治系統(tǒng)的情況 每個(gè)路由器都和其相鄰的路由器們共享它們對(duì)整個(gè)互聯(lián)網(wǎng)絡(luò)掌握的情況。開(kāi)始時(shí)，一個(gè)路由器掌握的情況可能是很少的，便是它知道多少并不重要；它發(fā)送它所知道的所有情況。2、 只和相鄰的路由器共享 每個(gè)路由器只向相鄰的路由器發(fā)送自己掌握的情況。它通過(guò)自己的所有端口發(fā)送自己知道的所有情況。3、 定期地共享 每個(gè)路由器都定期地（如每隔30秒）向相鄰的路由器發(fā)送自己掌握的情況。術(shù)語(yǔ)“距離向量”起源于定期信息發(fā)送，一個(gè)報(bào)文包含有成對(duì)的列表（V，D），這里的V表示目的地（叫做向量），D是到達(dá)那個(gè)目的地的距離。注意距離向量是以第一人稱報(bào)

11、告路由的，即我們把一個(gè)路由器送來(lái)的通告看成它在說(shuō)：“我可以到達(dá)距離為D的目的地V”。 路由表每個(gè)路由器都保持一張路由表，表中為路由器知道的每一個(gè)目標(biāo)網(wǎng)絡(luò)設(shè)置一條記錄。該記錄由目標(biāo)網(wǎng)絡(luò)的IP地址、到達(dá)目標(biāo)的最短距離（用“跳數(shù)”表示）和下一跳（為了到達(dá)最后目標(biāo)應(yīng)將數(shù)據(jù)包轉(zhuǎn)送給它的下一個(gè)路由器）三個(gè)部分組成。跳數(shù)是指數(shù)據(jù)包到達(dá)最后目標(biāo)所進(jìn)入的網(wǎng)絡(luò)數(shù)目。路由表中還含有諸如該記錄最后更新時(shí)間等其他信息。示例如下：距離跳數(shù)下一跳其他信息163.5.0.07172.6.23.4 197.5.13.05176.3.6.17 189.45.0.04200.5.1.6 115.0.0.06131.4.7.19 R

12、IP更新算法路由表根據(jù)收到的RIP響應(yīng)報(bào)文（message）進(jìn)行更新。以下是RIP所使用的更新算法： 接收：一個(gè)RIP響應(yīng)報(bào)文1 為每個(gè)advertised（被發(fā)布）的目標(biāo)增加一個(gè)跳數(shù)值；2 對(duì)每個(gè)advertised的目標(biāo)重復(fù)以下步驟： IF （目標(biāo)不在路由表中） 將advertised的信息添加到路由表中。 ELSE IF （下一跳字段相同） 用advertised的記錄替換表中的記錄 ELSE IF（advertised跳數(shù)小于表中的跳數(shù)） 把它加到路由表中(更新） ELSE 什么都不做3 返回 報(bào)文由序偶（報(bào)文由序偶（IP網(wǎng)絡(luò)地址，到達(dá)該網(wǎng)絡(luò)的距離）組成網(wǎng)絡(luò)地址，到達(dá)該網(wǎng)絡(luò)的距離）組成

13、用步跳數(shù)表示到達(dá)目的網(wǎng)絡(luò)的距離；用步跳數(shù)表示到達(dá)目的網(wǎng)絡(luò)的距離；1-16，1表示直連，表示直連，16表示不可表示不可達(dá)（即只要步跳數(shù)大于等于達(dá)（即只要步跳數(shù)大于等于16就認(rèn)為路徑為無(wú)窮遠(yuǎn)）就認(rèn)為路徑為無(wú)窮遠(yuǎn)）路由器收到路由更新報(bào)文后應(yīng)更新自己的路由表路由器收到路由更新報(bào)文后應(yīng)更新自己的路由表 例如，例如，R2從從R1收到的路由更新報(bào)文為收到的路由更新報(bào)文為(net1,1)、(net2,2)、(net3,1)，則，則R2的路由表更新為的路由表更新為(net1,R1,2)、(net2,R1,3)、(net3,R1,2)RIP協(xié)議的時(shí)鐘協(xié)議的時(shí)鐘 路由刷新周期路由刷新周期 每個(gè)路由器每隔每個(gè)路由器每

14、隔30秒刷新和廣播自己的路由表。秒刷新和廣播自己的路由表。 路由失效計(jì)時(shí)路由失效計(jì)時(shí) 一條路由表項(xiàng)未被更新的時(shí)間達(dá)一條路由表項(xiàng)未被更新的時(shí)間達(dá)3分鐘（分鐘（180秒），秒），則視其為失效信息，將本路由表項(xiàng)的距離置為無(wú)窮則視其為失效信息，將本路由表項(xiàng)的距離置為無(wú)窮大（毒性逆轉(zhuǎn)）。大（毒性逆轉(zhuǎn)）。 路由保持計(jì)時(shí)路由保持計(jì)時(shí) 發(fā)現(xiàn)一條路由失效信息后，立即啟動(dòng)保持計(jì)時(shí)，發(fā)現(xiàn)一條路由失效信息后，立即啟動(dòng)保持計(jì)時(shí)，60秒之后刪除此條目。秒之后刪除此條目。算法不能明確的檢測(cè)出循環(huán)路由，會(huì)產(chǎn)生慢收斂和無(wú)限計(jì)數(shù)問(wèn)題算法不能明確的檢測(cè)出循環(huán)路由，會(huì)產(chǎn)生慢收斂和無(wú)限計(jì)數(shù)問(wèn)題步跳數(shù)不能反映鏈路的真實(shí)開(kāi)銷，例如步跳數(shù)為

15、步跳數(shù)不能反映鏈路的真實(shí)開(kāi)銷，例如步跳數(shù)為4的的LAN路徑不一路徑不一定比步跳數(shù)為定比步跳數(shù)為1的的64K DDN鏈路差。鏈路差。網(wǎng)絡(luò)1R1R2R31.R1與網(wǎng)絡(luò)與網(wǎng)絡(luò)1直接相連。直接相連。2.通過(guò)周期性路由廣播，通過(guò)周期性路由廣播，R1、R2、R3都建立了到網(wǎng)絡(luò)都建立了到網(wǎng)絡(luò)1的路由的路由(a)3.某時(shí)刻，某時(shí)刻， R1到網(wǎng)絡(luò)到網(wǎng)絡(luò)1的路由消失的路由消失(b)4.但是但是R2對(duì)對(duì)R1的路由通告引起了選路的循環(huán)的路由通告引起了選路的循環(huán): : 更新報(bào)文會(huì)在更新報(bào)文會(huì)在R1，R2來(lái)回傳輸直到距離值到達(dá)來(lái)回傳輸直到距離值到達(dá)RIP規(guī)定的上限。規(guī)定的上限。 網(wǎng)絡(luò)1R1R2R3(a)(b)R1直接與網(wǎng)

16、絡(luò)1相連，因此在路由表中具有一個(gè)到網(wǎng)絡(luò)1的路由，跳數(shù)為0，在它廣播后，R2獲得到網(wǎng)絡(luò)1的路由，跳數(shù)為0+1=1，最后R3則通過(guò)R2的廣播得到到網(wǎng)絡(luò)1的路由，跳數(shù)為1+1=2，同時(shí)，R1也會(huì)收到R2的廣播，但是由于在R1中到網(wǎng)絡(luò)1的跳數(shù)為0，比R2的小，因此不會(huì)更新。如果網(wǎng)絡(luò)1到R1的連接故障，則R1把到網(wǎng)絡(luò)1的跳數(shù)設(shè)為16，并廣播，使其它路由器更新。但是，由于所有路由器都會(huì)周期性廣播路由信息，因而可能會(huì)出現(xiàn)這種情況：在R1廣播跳數(shù)16之前，先收到了來(lái)自 R2的廣播，計(jì)算到網(wǎng)絡(luò)1的跳數(shù)為1+1=2，比16小，因此在還沒(méi)有廣播之前已經(jīng)被更新了，等到下一個(gè)廣播周期時(shí)，R2的更新為2+1=3。到下一輪

17、廣播，R1又是收到R2的廣播跳數(shù)變?yōu)?+1=4，而后又廣播給R2，使R2到網(wǎng)絡(luò)1的跳數(shù)更新為4+1=5，如此，不斷增加，要經(jīng)過(guò)一個(gè)較長(zhǎng)的時(shí)間（大于14*30秒）之后，才會(huì)發(fā)現(xiàn)網(wǎng)絡(luò)1從這里是不可達(dá)的，而這段時(shí)間內(nèi)到網(wǎng)絡(luò)1的流量仍被引導(dǎo)到這個(gè)不可能的方向。這就是慢收斂問(wèn)題 (壞消息傳得慢)網(wǎng)絡(luò)1R1R2R3網(wǎng)絡(luò)1R1R2R3 1 1ACB40.0.0.0 down時(shí)時(shí)間間ABC刷刷新新初初始始210信信宿宿可可達(dá)達(dá)40.0.0.0斷斷開(kāi)開(kāi)212BC，1+1=2第第 1 步步232CB，2+1=3第第 2 步步434BC，3+1=4BA，3+1=4到達(dá)信宿到達(dá)信宿40.0.0.0的路由變化的路由變化

18、路徑環(huán)（路徑環(huán)（Routing Loop）問(wèn)題）問(wèn)題這條錯(cuò)誤的路由信息在這條錯(cuò)誤的路由信息在C與與B之間不斷復(fù)制和修改，之間不斷復(fù)制和修改，并在網(wǎng)絡(luò)中傳播（殃及并在網(wǎng)絡(luò)中傳播（殃及A），形成路徑傳播的環(huán)路。），形成路徑傳播的環(huán)路。 1 1ACB40.0.0.0 down時(shí)時(shí)間間ABC刷刷新新初初始始210信信宿宿可可達(dá)達(dá)40.0.0.0斷斷開(kāi)開(kāi)212BC，1+1=2第第 1 步步232CB，2+1=3第第 2 步步434BA，BC，3+1=4第第 3 步步454CB，4+1=5第第 13 步步141514CB，14+1=15第第 14 步步161516BA， BC， 15+1=16 Count

19、 to Infinity到達(dá)信宿到達(dá)信宿40.0.0.0的路由變化的路由變化嚴(yán)重后果：計(jì)數(shù)至無(wú)窮大嚴(yán)重后果：計(jì)數(shù)至無(wú)窮大 1 1ACB40.0.0.0 down時(shí)時(shí)間間ABC刷刷新新初初始始210信信宿宿可可達(dá)達(dá)40.0.0.0斷斷開(kāi)開(kāi)212BC，1+1=2第第 1 步步232CB，2+1=3第第 2 步步434BA，BC，3+1=4第第 3 步步454CB，4+1=5第第 13 步步141514CB，14+1=15第第 14 步步161516BA， BC， 15+1=16第第 15 步步不不可可達(dá)達(dá)16不不可可達(dá)達(dá)CB，15+1=16第第 16 步步不不可可達(dá)達(dá)扔扔棄棄到達(dá)信宿到達(dá)信宿40.

20、0.0.0的路由變化（定義的路由變化（定義Hop最大值為最大值為16）解決辦法：定義距離的最大值解決辦法：定義距離的最大值收斂！收斂！解決解決RIP存在的問(wèn)題的幾種方法存在的問(wèn)題的幾種方法v視野分離（水平分割）視野分離（水平分割） Split-Horizon 從一個(gè)接口收到的路由信息不會(huì)再通過(guò)該接口送回去從一個(gè)接口收到的路由信息不會(huì)再通過(guò)該接口送回去v毒性逆轉(zhuǎn)毒性逆轉(zhuǎn) Poison Reverse 從一個(gè)接口收到的路由信息可以再通過(guò)該接口送回去，但距離為從一個(gè)接口收到的路由信息可以再通過(guò)該接口送回去，但距離為16v觸發(fā)更新觸發(fā)更新 Trigged updates 路由發(fā)生變化時(shí)，不必等到路由發(fā)

21、生變化時(shí)，不必等到30秒，可立即將更新報(bào)文廣播出去秒，可立即將更新報(bào)文廣播出去v抑制更新抑制更新 Hold-Down timers 收到某網(wǎng)絡(luò)不可達(dá)的信息后，在一段時(shí)間內(nèi)（收到某網(wǎng)絡(luò)不可達(dá)的信息后，在一段時(shí)間內(nèi)（60秒）忽略任何關(guān)于秒）忽略任何關(guān)于該網(wǎng)絡(luò)的路由信息該網(wǎng)絡(luò)的路由信息水平分割方法的思路水平分割方法的思路 1 1ACB40.0.0.0 down 分析路徑環(huán)產(chǎn)生的原因分析路徑環(huán)產(chǎn)生的原因 B向向C提供了一條過(guò)時(shí)的、錯(cuò)誤的路由信息。提供了一條過(guò)時(shí)的、錯(cuò)誤的路由信息。 能否避免事件發(fā)生？能否避免事件發(fā)生？ B必須經(jīng)由必須經(jīng)由C方可到達(dá)網(wǎng)絡(luò)方可到達(dá)網(wǎng)絡(luò)40.0.0.0，B不可能向不可能向C提

22、供任何有提供任何有價(jià)值的路由信息。價(jià)值的路由信息。 修改修改B對(duì)對(duì)C提供的路由，禁止提供的路由，禁止B向向C提供關(guān)于此信宿的路由信息。提供關(guān)于此信宿的路由信息。水平分割法水平分割法（Split Horizons） 1 1ACB40.0.0.0 down收斂！收斂！時(shí)時(shí)間間ABC刷刷新新初初始始210信信宿宿可可達(dá)達(dá)40.0.0.0斷斷開(kāi)開(kāi)21 C 主主動(dòng)動(dòng)改改距距離離為為 第第 1 步步2 CB， 第第 2 步步 BA， 到達(dá)信宿到達(dá)信宿40.0.0.0的路由變化的路由變化水平分割法利用的是路由報(bào)文發(fā)送的選擇性；一個(gè)路由器必須識(shí)別不同的水平分割法利用的是路由報(bào)文發(fā)送的選擇性；一個(gè)路由器必須識(shí)別

23、不同的端口。如果一個(gè)路由器已經(jīng)從某個(gè)端口處接收到了路由更新信息，那么這端口。如果一個(gè)路由器已經(jīng)從某個(gè)端口處接收到了路由更新信息，那么這同一個(gè)更新信息就不能通過(guò)此端口再發(fā)送回去。如果一個(gè)端口已經(jīng)發(fā)送信同一個(gè)更新信息就不能通過(guò)此端口再發(fā)送回去。如果一個(gè)端口已經(jīng)發(fā)送信息以幫助某個(gè)路由器進(jìn)行更新，這種更新的信息不得回送；它是已知的，息以幫助某個(gè)路由器進(jìn)行更新，這種更新的信息不得回送；它是已知的，所以是不需要的。所以是不需要的。l水平分裂雖然廣泛使用，但有時(shí)候會(huì)失敗。l如右圖。n開(kāi)始時(shí)，A和B到D的距離都為2，C到D的距離為1。n假設(shè)CD線路斷了，使用水平分裂，A和B都告訴C，它們不能到達(dá)D，同時(shí)C自己

24、也發(fā)現(xiàn)直達(dá)D的線路斷了，于是C很快認(rèn)定D不可達(dá)了。n但是，A認(rèn)為B有一條通向D長(zhǎng)度為2的路徑，通過(guò)B經(jīng)過(guò)3個(gè)結(jié)點(diǎn)可到達(dá)D。類似，B也這樣認(rèn)為。于是兩個(gè)結(jié)點(diǎn)每交換一次信息，到達(dá)D的距離就增加1，直至加大無(wú)窮。 1 1ACB40.0.0.0 down此法是水平分割法的一個(gè)變種。在本辦法中，路由器收到的此法是水平分割法的一個(gè)變種。在本辦法中，路由器收到的信息被用于更新路由表，然后轉(zhuǎn)發(fā)到所有端口。但是，從某個(gè)信息被用于更新路由表，然后轉(zhuǎn)發(fā)到所有端口。但是，從某個(gè)端口傳來(lái)的路由表記錄如果通過(guò)同一個(gè)端口出去，它的跳數(shù)值端口傳來(lái)的路由表記錄如果通過(guò)同一個(gè)端口出去，它的跳數(shù)值被設(shè)為被設(shè)為16。 反向抑制法反向

25、抑制法 (毒性逆轉(zhuǎn)毒性逆轉(zhuǎn) Poison Reverse） 1 1ACB40.0.0.0 down 當(dāng)當(dāng)C發(fā)現(xiàn)網(wǎng)絡(luò)發(fā)現(xiàn)網(wǎng)絡(luò)40.0.0.0發(fā)生故障時(shí)，不等下一刷新周發(fā)生故障時(shí)，不等下一刷新周期到來(lái)，立刻更改路由為期到來(lái)，立刻更改路由為“信宿不可達(dá)信宿不可達(dá)” 引起全網(wǎng)的連鎖反映，迅速刷新引起全網(wǎng)的連鎖反映，迅速刷新觸發(fā)刷新法觸發(fā)刷新法網(wǎng)絡(luò)網(wǎng)絡(luò)40.0.0.0不可達(dá)不可達(dá)網(wǎng)絡(luò)網(wǎng)絡(luò)40.0.0.0不可達(dá)不可達(dá)網(wǎng)絡(luò)網(wǎng)絡(luò)40.0.0.0不可達(dá)不可達(dá)距離向量算法小結(jié)距離向量算法小結(jié) 路徑選擇采用最短路徑準(zhǔn)則，計(jì)算路徑選擇采用最短路徑準(zhǔn)則，計(jì)算D信宿信宿(距離，下站距離，下站)； 每個(gè)站點(diǎn)只知道自己和鄰居

26、的局部信息，在自己的刷新每個(gè)站點(diǎn)只知道自己和鄰居的局部信息，在自己的刷新周期到來(lái)時(shí)，根據(jù)鄰居的路由變化重新啟動(dòng)算法；周期到來(lái)時(shí)，根據(jù)鄰居的路由變化重新啟動(dòng)算法； 算法的收斂速度慢（特別是對(duì)網(wǎng)絡(luò)崩潰）造成全網(wǎng)信息算法的收斂速度慢（特別是對(duì)網(wǎng)絡(luò)崩潰）造成全網(wǎng)信息的不一致，導(dǎo)致產(chǎn)生路徑環(huán)，使計(jì)數(shù)至無(wú)窮大；的不一致，導(dǎo)致產(chǎn)生路徑環(huán)，使計(jì)數(shù)至無(wú)窮大； 當(dāng)路徑環(huán)產(chǎn)生時(shí)，定義距離的最大值可防止算法進(jìn)入死當(dāng)路徑環(huán)產(chǎn)生時(shí)，定義距離的最大值可防止算法進(jìn)入死循環(huán)，解決計(jì)數(shù)至無(wú)窮大問(wèn)題；循環(huán)，解決計(jì)數(shù)至無(wú)窮大問(wèn)題； 各種加速收斂方法的目的在于避免路徑環(huán)的形成，但不各種加速收斂方法的目的在于避免路徑環(huán)的形成，但不能從根

27、本上杜絕這一現(xiàn)象的發(fā)生；能從根本上杜絕這一現(xiàn)象的發(fā)生； 在具體的路由協(xié)議中，各種加速收斂方法往往綜合使用。在具體的路由協(xié)議中，各種加速收斂方法往往綜合使用。開(kāi)放最短路徑優(yōu)先（開(kāi)放最短路徑優(yōu)先（OSPF）協(xié)議OSPF協(xié)議的基本概念協(xié)議的基本概念Open Shortest Path First 采用鏈接狀態(tài)（采用鏈接狀態(tài)（L-S）算法）算法 由由IETF工作小組研制工作小組研制 1990年成為標(biāo)準(zhǔn)（年成為標(biāo)準(zhǔn)（RFC1247） 改進(jìn)改進(jìn)RIP協(xié)議的問(wèn)題協(xié)議的問(wèn)題 計(jì)數(shù)至無(wú)窮大計(jì)數(shù)至無(wú)窮大 收斂速度慢收斂速度慢 開(kāi)放最短路徑優(yōu)先（開(kāi)放最短路徑優(yōu)先（OSPF）協(xié)議： 使用SPF算法，基于鏈路狀態(tài)。 (

28、Shortest Path First) 提供路由服務(wù)類型：如可要求低延遲或高吞吐量，路由時(shí)不僅依據(jù)路由目的，還要依據(jù)服務(wù)類型要求 ，OSPF將均分負(fù)載給各個(gè)路徑 提供網(wǎng)絡(luò)的“域”劃分能力，一個(gè)域?qū)ν獠渴峭该鞯?，因而可?dú)立管理，這就提供了靈活的網(wǎng)絡(luò)擴(kuò)展能力，易于規(guī)?；?OSPF規(guī)定路由器之間的信息交換需要有授權(quán)，提高安全性。RIP中任意路由都可廣播路由信息，易被利用。 支持指向特定主機(jī)、特定子網(wǎng)的路由，當(dāng)然還有對(duì)網(wǎng)絡(luò)的路由，以滿足不同需要。 支持子網(wǎng) 支持CIDR 支持虛鏈路。 . 最短路徑優(yōu)先最短路徑優(yōu)先(Shortest Path First)算法： 該算法利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)（基于鏈路狀態(tài)）

29、，作如下抽象： 把網(wǎng)絡(luò)中的每個(gè)路由器看成一個(gè)節(jié)點(diǎn), 若兩個(gè)路由器之間存在直接的連接,就認(rèn)為它們之間存在一條邊 這樣整個(gè)網(wǎng)絡(luò)拓?fù)渚涂沙橄鬄橐粋€(gè)只含有節(jié)點(diǎn)和邊的圖 參與SPF算法的路由器執(zhí)行如下兩個(gè)任務(wù)以獲得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)： 周期性地測(cè)試與相鄰路由器的連接狀態(tài) 周期性地把連接狀態(tài)廣播給其他路由器 每個(gè)路由器在獲得整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)后，就可以各自獨(dú)立地使用Dijkstra最短路徑算法來(lái)計(jì)算從本路由到其他路由的最短路。AEDCB212113Dijkatra最短路徑算法最短路徑算法F3552Dijkatra算法計(jì)算結(jié)果算法計(jì)算結(jié)果AEDCB212113計(jì)計(jì)算算BCDEF02,A5,A1,A ,- ,-12

30、,A4,D2,D ,-22,A4,D4,E33,E4,E44,E源點(diǎn)源點(diǎn)A到所有結(jié)點(diǎn)的最短路徑到所有結(jié)點(diǎn)的最短路徑F3552DFEABC11212L-S圖圖SPF樹(shù)樹(shù) 每個(gè)路由器周期性地收集和發(fā)送信息每個(gè)路由器周期性地收集和發(fā)送信息 主動(dòng)測(cè)試其到所有鄰居的鏈接狀態(tài)（度量值）主動(dòng)測(cè)試其到所有鄰居的鏈接狀態(tài)（度量值） 向所有的路由器發(fā)送（廣播）自己擁有的狀態(tài)信息向所有的路由器發(fā)送（廣播）自己擁有的狀態(tài)信息 得到一個(gè)全網(wǎng)的、動(dòng)態(tài)的邏輯鏈路狀態(tài)（得到一個(gè)全網(wǎng)的、動(dòng)態(tài)的邏輯鏈路狀態(tài)（L-S）圖）圖 每個(gè)路由器刷新自己的路由表每個(gè)路由器刷新自己的路由表 當(dāng)當(dāng)L-S變化時(shí)，用最短路徑優(yōu)先變化時(shí)，用最短路徑優(yōu)

31、先(SPF)算法重新計(jì)算本地路由算法重新計(jì)算本地路由DCAB鏈路狀態(tài)算法的基本概念鏈路狀態(tài)算法的基本概念_路路由由表表SPF算法算法拓?fù)鋽?shù)據(jù)庫(kù)拓?fù)鋽?shù)據(jù)庫(kù)（L-S圖）圖）SPF樹(shù)樹(shù)L-S包包OSPF劃分編號(hào)區(qū)域（劃分編號(hào)區(qū)域（Area）國(guó)家主干國(guó)家主干Area1Area0Area2AreaN地區(qū)主干地區(qū)主干主干路由器主干路由器域邊界路由器域邊界路由器域內(nèi)路由器域內(nèi)路由器.域內(nèi)路由器域內(nèi)路由器 只擁有本域的路由信息；只擁有本域的路由信息； 具有相同的具有相同的L-S圖，采用相同的圖，采用相同的SPF算法；算法； 采用擴(kuò)散方式廣播自己獲得的網(wǎng)絡(luò)知識(shí)采用擴(kuò)散方式廣播自己獲得的網(wǎng)絡(luò)知識(shí)（鄰居和開(kāi)銷）；（鄰居和開(kāi)銷）； 根據(jù)擴(kuò)散的信息修改根據(jù)擴(kuò)散的信息修改L-S圖，計(jì)算到域內(nèi)圖，計(jì)算到域內(nèi)其他路由器的最短路徑；其他路由器的最短路徑； 根據(jù)計(jì)算機(jī)結(jié)果維護(hù)各自的路由表。根據(jù)計(jì)算機(jī)結(jié)果維護(hù)各自的路由表。域邊界路由器域邊界路由器 具有域內(nèi)路由器的功能；具有域內(nèi)路由器的功能； 擁有相鄰域的擁有相鄰域的L-S信息，并計(jì)算到達(dá)相鄰域的信息，并計(jì)算到達(dá)相鄰域的最短路徑；最短路徑； 域間的分組交換都通過(guò)其進(jìn)行路徑選擇和數(shù)據(jù)域間的分組交換都通過(guò)其進(jìn)行路徑選擇和數(shù)據(jù)交換。交換。例如：例如： 本域的路由器通過(guò)域邊界路由器把分組送往主