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

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

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

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

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

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

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

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

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

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

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

11、告路由的，即我們把一個路由器送來的通告看成它在說：“我可以到達距離為D的目的地V”。 路由表每個路由器都保持一張路由表，表中為路由器知道的每一個目標網(wǎng)絡(luò)設(shè)置一條記錄。該記錄由目標網(wǎng)絡(luò)的IP地址、到達目標的最短距離（用“跳數(shù)”表示）和下一跳（為了到達最后目標應(yīng)將數(shù)據(jù)包轉(zhuǎn)送給它的下一個路由器）三個部分組成。跳數(shù)是指數(shù)據(jù)包到達最后目標所進入的網(wǎng)絡(luò)數(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)報文（message）進行更新。以下是RIP所使用的更新算法： 接收：一個RIP響應(yīng)報文1 為每個advertised（被發(fā)布）的目標增加一個跳數(shù)值；2 對每個advertised的目標重復(fù)以下步驟： IF （目標不在路由表中） 將advertised的信息添加到路由表中。 ELSE IF （下一跳字段相同） 用advertised的記錄替換表中的記錄 ELSE IF（advertised跳數(shù)小于表中的跳數(shù)） 把它加到路由表中(更新） ELSE 什么都不做3 返回 報文由序偶（報文由序偶（IP網(wǎng)絡(luò)地址，到達該網(wǎng)絡(luò)的距離）組成網(wǎng)絡(luò)地址，到達該網(wǎng)絡(luò)的距離）組成

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

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

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

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

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

18、路徑環(huán)（路徑環(huán)（Routing Loop）問題）問題這條錯誤的路由信息在這條錯誤的路由信息在C與與B之間不斷復(fù)制和修改，之間不斷復(fù)制和修改，并在網(wǎng)絡(luò)中傳播（殃及并在網(wǎng)絡(luò)中傳播（殃及A），形成路徑傳播的環(huán)路。），形成路徑傳播的環(huán)路。 1 1ACB40.0.0.0 down時時間間ABC刷刷新新初初始始210信信宿宿可可達達40.0.0.0斷斷開開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到達信宿到達信宿40.0.0.0的路由變化的路由變化嚴重后果：計數(shù)至無窮大嚴重后果：計數(shù)至無窮大 1 1ACB40.0.0.0 down時時間間ABC刷刷新新初初始始210信信宿宿可可達達40.0.0.0斷斷開開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 步步不不可可達達16不不可可達達CB，15+1=16第第 16 步步不不可可達達扔扔棄棄到達信宿到達信宿40.

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

21、生變化時，不必等到30秒，可立即將更新報文廣播出去秒，可立即將更新報文廣播出去v抑制更新抑制更新 Hold-Down timers 收到某網(wǎng)絡(luò)不可達的信息后，在一段時間內(nèi)（收到某網(wǎng)絡(luò)不可達的信息后，在一段時間內(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提供了一條過時的、錯誤的路由信息。提供了一條過時的、錯誤的路由信息。 能否避免事件發(fā)生？能否避免事件發(fā)生？ B必須經(jīng)由必須經(jīng)由C方可到達網(wǎng)絡(luò)方可到達網(wǎng)絡(luò)40.0.0.0，B不可能向不可能向C提

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

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

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

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

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

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

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

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

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

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