1、TCP/IP協議族（英文版）第13章路由協議（RIP,OSPFf口BGP所謂“互聯網絡”（internet）是指由路由器連接而成的多個網絡的組合體。當數據報從一個源端傳送到一個目標端時，可能需要通過很多個路由器才到達與目標網絡連接的路由器。路由器的作用是從一個網絡中接收數據包（packet,分組），然后將它傳送給另一個網絡。一個路由器通常與幾個網絡連接，這樣，當它收到一個數據包時，應該將數據包轉發給哪個網絡呢？路由器是按最佳化原則進行判定：哪個可用的路徑是最佳路徑？人們用metric來表示通過某個網絡時所指定的“成本”（cost,代價）。一個特定路由的總metric，等于包含了該路由的多個網絡

2、的metric之和。路由器根據最短（最小）的metric來選擇路由。分配給每個網絡的metric取決于協議的類型。某些簡單的協議，如“路由信息協議”（RIP），將每個網絡同等處理，即通過每個網絡的cost是一樣的，或者說都是一個“跳數”（onehopcount）。所以如果一個數據包通過10個網絡才到達目標端，其總cost就是10個“跳數”。其他協議，如“開放最短路徑優先協議”（OSPF），則允許管理員根據所需的服務類型，為通過一個網絡指定cost。通過某個網絡的路由可以具有不同的cost（metric）。例如，如果所需的服務類型是“最大吞吐量”（throughput），一條衛星鏈路就比一條光纖

3、鏈路具有更低的metric。另一方面，如果所需的服務類型是“最小延遲”，一條光纖鏈路就比一條衛星鏈路具有更低的metric。OSPF允許每個路由器根據所需的服務類型擁有幾個路由表。其他協議定義metric的方法則完全不同。在“邊緣網關協議”（BGP）中，評定的標準是可以由管理員設置的所謂“策略”（policy）。“策略”定義了應該選擇的是哪個路徑。不管metric是如何確定的，路由器在準備轉發數據包時，都必須使用路由表。路由表應為數據包規定最佳路徑。不過，路由表可以是靜態的，也可以是動態的。“靜態路由表”是那種不經常變化的路由表。而“動態路由表”是那種當互聯網絡中的某處出現變化時能自動更新的路

4、由表。今天，互聯網絡需要的是動態路由表。這種路由表要求互聯網絡出現變化時即被盡快更新。例如，當某個路由關閉（down）時，需要進行更新；而當一個更好的路由建立后，也需要進行更新。各種路由協議都是為了動態路由表的需要而制定的。一個路由協議是一組規則和程序的組合，用于使互聯網絡中的路由器們相互告知有關的變化情況。它使路由器們共享它們所掌握的互聯網絡或相鄰路由器的情況。這種信息的共享使得舊金山市的某個路由器可以知道德克薩斯州的網絡出現故障了。路由協議還包含了將從其他路由器接收的信息綜合起來的處理程序。13.1內部和外部路由今天，一個互聯網絡可能很大，以致一個路由協議無法完成為所有路由器更新路由表的任

5、務。為此，需要將一個互聯網絡分為若干“自治系統”（autonomoussystems，AS）。一個“自治系統”是指由同一個管理員管理的一組網絡和路由器。自治系統內部的路由稱為“內部路由”，自治系統之間的路由稱為“外部路由”。每個自治系統都可以選擇一個內部路由協議來處理該自治系統內部的路由。但是，自治系統之間的路由通常只能使用一個外部路由協議來處理。現在使用的內部和外部路由協議很多。本章只介紹最常用的幾種。下面討論兩個內部路由協議（RIP和OSPF）和一個外部路由協議（BGP）。RIP和OSPF可用于自治系統內部路由表的更新。BGP可用于為連接自治系統的各個路由器進行路由表更新。圖13.2中，路

6、由器R1，R2，R3和R4使用一個內部路由協議和一個外部路由協議。其他路由器只使用內部路由協議。細實線表示使用內部路由協議的各路由器間的通信連接。虛線則表示使用外部路由協議的各路由器間的通信連接。13.2RIP（路由信息協議）路由信息協議是一個用于自治系統內部的所謂“內部路由協議”。它是一種非常簡單的協議，基于所謂“距離向量路由”（使用Bellman-Ford算法來計算路由表）技術。在本節中，我們首先研究RIP所應用的“距離向量路由”的原理，然后討論RIP協議本身。距離向量路由在“距離向量路由”中，每個路由器都定期地和其相鄰的路由器們共享它們對整個互聯網絡掌握的情況。理解這一算法的工作原理有三

7、個關鍵，如下：1、 共享整個自治系統的情況每個路由器都和其相鄰的路由器們共享它們對整個互聯網絡掌握的情況。開始時，一個路由器掌握的情況可能是很少的，便是它知道多少并不重要；它發送它所知道的所有情況。2、 只和相鄰的路由器共享每個路由器只向相鄰的路由器發送自己掌握的情況。它通過自己的所有端口發送自己知道的所有情況。3、 定期地共享每個路由器都定期地（如每隔30秒）向相鄰的路由器發送自己掌握的情況。術語“距離向量”起源于定期信息發送，一個報文包含有成對的列表（V，D），這里的V表示目的地（叫做向量），D是到達那個目的地的距離。注意距離向量是以第一人稱報告路由的，即我們把一個路由器送來的通告看成它在

8、說：“我可以到達距離為D的目的地V”。（計算機網絡習題與解析P183）路由表每個路由器都保持一張路由表，表中為路由器知道的每一個目標網絡設置一條記錄。該記錄由目標網絡的IP地址、到達目標的最短距離（用“跳數”表示）和下一跳（為了到達最后目標應將數據包轉送給它的下一個路由器）三個部分組成。跳數是指數據包到達最后目標所進入的網絡數目。路由表中還含有諸如該記錄最后更新時間等其他信息。示例如下:表13.1距離向量路由表距離跳數下一跳其他信息163.5.0.07172.6.23.4197.5.13.05176.3.6.17189.45.0.04200.5.1.6115.0.0.06131.4.7.19R

9、IP更新算法路由表根據收到的RIP響應報文（message進行更新。以下是RIP所使用的更新算法：接收：一個RIP響應報文1 .為每個advertised（被發布）的目標增加一個跳數值；2 .對每個advertised的目標重復以下步驟：1 .如果（目標不在路由表中）1 .將advertised的信息添加到路由表中。2 .否則1 .如果（下一跳字段相同）1 .用advertised的記錄替換表中的記錄2 .否則1.如果（advertised跳數小于表中的跳數）1 .把它加到路由表中2 .否則2.什么都不做3.返回在圖13.3中，一個路由器從路由器C處收到一個RIP報文。該報文列出了目標網絡及其

10、相應的跳數。要求更新算法，第一步是將跳數加1,然后將這個更新了的RIP數據包與原Net1,因為來的路由表比較。結果是產生了一個使用到達每個目標最新跳數的路由表。對沒有新信息，所以Net1的記錄保持不變。對Net2,表中的信息和報文中的信息確定是同一個“下一跳”（路由器C）。雖然路由表中的跳數（2）小于報文中的跳數（5）,按算法還是選擇了從報文中接收來的跳數，因為原始的值來自路由器C。這個值現在無效了，因為路由器C正在宣告一個新值。Net3是一個新增的目標。對Net6,RIP數據包含有一個較低的跳數，于是該值出現在新路由表中。Net8和Net9保留原來的值，因為報文中對應的跳數并無任何改進。路由

11、表的初始化將一臺路由器剛加入到網絡中時，它使用自己的配置文件來初始化自己的路由表。此路由表只含有直接連接的網絡和跳數（初始值均為1）。“下一跳”字段則為空白。圖13.4表示了一個小自治系統中各初始的路由表。更新路由表每個路由表都使用上述的RIP更新算法，根據所接收的RIP報文進行更新。圖示了上面那個自治系統的最新路由表。13. 5 表重復命令版本保留協議族全為0網絡地址全為0全為0距離規定報文類型：請求（1）響應（2）RIP報文格式RIP報文的格式如下: 命令（ 版本（ 協議族 地址（ 距離（8位）8位）（16 位）14字節）32位）規定RIP版本，此處為版本1（還有版本2）規定所用協議族。T

12、CP/IP為2。0。規定目標網絡的地址。IP只用四個字節，其余均填上規定了從advertising路由器到目標網絡的跳數。O我們將它稱為“一條記錄”注意：每個目標網絡均重復報文的一部分（陰影部分）請求和響應RIP使用兩種報文：請求和響應請求請求報文是由剛啟動的路由器發出，或者由某些記錄已超時的路由器發出。請求可以是針對部分記錄，也可以是針對全部記錄。命令：1版本保留協議族全為0網絡地址全為0全為0全為0a.針對部分記錄的請求（陰影部分重復）命令：1版本保留協議族全為0全為0全為0全為0全為0b.針對全部記錄的請求響應響應可以是solicited或unsolicited的。所謂"sol

13、icited響應”只能答復一個請求。它含有相應請求中規定的目標的信息。而所謂“unsolicited響應“則是每隔30秒定時發送，含有整個路由表的信息。下圖是由一個RIP響應報文發布的有關三個網絡的信息。RIP中的定時器(TimersinRIP)更新計時器路由限時器RIP使用三個定時器來支持它的操作： 定期（periodic）定時器2535秒 過期（expiration）定時器180秒 垃圾搜集（garbagecollection）定時器120秒路由清除計時器“定期”定時器“定期”定時器控制“定期更新報文”的發布。雖然協議規定這個定時器必須設置為30秒,這個工作模型實際使用的是一個2535秒之

14、間的隨機數，以防止由于路由器同時更新而在互聯網上形成同步從而導致過載。每個路由器都有一個定期定時器，它被隨機地設置為2535之間的某個數，采用倒計數制。當計數值為零時，更新報文就被發出，然后定時器又被隨機地設置一次。如果RIP使用其他附加的定時方法來發送更新信息（如“觸發更新”，見下），定期定時器的工作并不受影響。定期更新報文按原定時間間隔發出，與其他定時系統的更新報文互不相干。“過期”定時器過期定時器決定了路由的有效性。如果一個路由器接收到某個路由更新信息，過期定時器將被設置為180秒（專為此特定路由）。每次收到該路由的最新的更新信息，定時器就被復位。在通常情況下，更新信息是30秒出現一次。

15、但是，如果互聯網絡上出現問題，在所規定的180秒時間內沒收到更新信息，該路由的跳數就被設置為16（表示目標是不可到達的）。每一個路由都有它自己的過期定時器。“垃圾搜集”定時器當與某個路由有關的信息變成無效時，路由器并不立即從其路由表中清除該路由，而是以metric值16繼續發布該路由。同時，一個稱為“垃圾搜集定時器”的定時器被設置為120秒（專為此路由）。當計數值變成0時，該路由才從路由表中被清除。這個定時器使相鄰的路由器們可以在某個路由被清除前便知道該路由已經失效了。慢收斂(SlowConvergence)使用RIP時遇到的一個問題是“慢收斂”問題，這意味著在互聯網絡中某處的改變非常緩慢地傳

16、遞到該互聯網絡的其他部分。例如，假設圖3.10中的網絡1中發生了某種改變，路由器R1立即自我更新。但是，因為每個路由器每隔30秒才發送其定期更新報文，這意味平均需要15秒（在030秒范圍內平均）的時間才能到達R2。到達R3,則需要另外15秒,以此類推。當更新信息最后到達路由器Rn時，需要經過15Xn秒時間。如果n是20,則需要300秒。而在300秒時間內，一個ATM網絡可以發送十幾億個二進制位的信息。如果這種改變對這些信息有影響，那就意味有十億個位的信息丟失了。克服RIP問題的一個方法是將跳數限制在15以內。這樣做可以防止數據包在互聯網絡中長久游蕩，引進網絡阻塞。一個使用RIP的自治系統被限制

17、在跳數為15的范圍內；所以跳數為16時，表示無限大，用來表示一個不可到達的網絡（見圖13.11）。不穩定性（Instability）使用RIP時一個更嚴重的問題是不穩定性，即一個運行RIP的互聯網絡可能變得不穩定了。如果出現這個問題，數據包可能在路由器間循環傳送。將跳數限制在15將改善穩定性，但不能完全解決問題。為了理解這個問題，假定圖13.12中與Net1的連接失效了。路由器A的路由表中到Net1的cost是1。路由器B只能通過路由器A訪問Net1，所以到Net1的cost是2。路由器A訪問Net1失敗時，立即作出響應，并將到Net1的cost改為16（無限遠）。但是，它需要多達30秒時間才

18、能將它的更新信息發送出去。在此期間，可能發生這樣的事：路由器B向路由器A發送自己的更新報文。于是路由器A便有了兩個與Net1有關的記錄：本身路由表中的跳數值是16，而路由器B報告的信息卻是2。路由器A因此而受騙，認為還可以通過路由器B從“后門”訪問Net1，于是就將到Net1的跳數值改為3（2+1），并將此更新信息發送給路由器B。這樣路由器B就有兩個到達Net1的跳數值3（來自A）和2（自身路由表）。路由器B知道只能通過路由器A才能訪問Net1，所以就忽略了自身路由表中較低的跳數值，將該跳數值改為4（3+1）。這種來回更新持續發生，一直到兩個路由器都達到跳數值16。到了此時，路由器們才明白到N

19、et1原來是“無路可通”！改進不穩定性的一些補救技術已經提出了一些補救技術來改進穩定性，但是沒有一種是百分之百有效的。觸發更新法（TriggeredUpdate）如果網絡中沒有什么變化，更新信息按正常的30秒間隔發送。但是，如果出現變化，路由器便立即動作發送自己的新路由表，這個過程叫做“觸發更新”。觸發更新可以改善穩定性。每個收到表明網絡發生改變更新信息的路由器都立即發出新的信息，其時間大大小于15秒的平均值。如在圖13.12中，當路由器A認識到Net1是不可訪問時，便將自身路由表中的跳數值改為16，然后立即發送給路由器B。然后是路由器B修改路由表，這樣兩個路由表中到Net1的跳數值都是16了

20、。發送含有遞增跳數值的更新報文可以避免上述循環問題。雖然觸發更新可以極大地改進路由問題，但它不能解決所有的路由問題。例如，用這樣方法無法處理路由器的故障問題。水平分割法（SplitHorizons）水平分割法是第二種用于改善穩定性的方法，它利用的是路由報文發送的選擇性；一個路由器必須識別不同的端口。如果一個路由器已經從某個端口處接收到了路由更新信息，那么這同一個更新信息就不能通過此端口再發送回去。如果一個端口已經發送信息以幫助某個路由器進行更新，這種更新的信息不得回送；它是已知的，所以是不需要的。圖13.13是這個概念的示意圖。圖中，路由器B通過其左端口已經接收到關于Net1和Net2的信息；

21、這個信息被更新，并通過右端口（而非左端口）傳送出去。同樣，路由器B接收到的關于Net3的信息被更新，并且只能通過路由器B的左端口傳送出去。水平分割法肯定可以改善穩定性。假定圖13.12中Net1對路由器A是不可訪問的。路由器B從路由器A收到關于Net1的信息；它并不將關于Net1的信息發送給路由器A。所以路由器A不僅有一條關于Net1的記錄（跳數值16）,而且不會再受騙認為要到達Net1可以通過什么“后門”。路由器A將自身的路由表發送給B,最后兩者對Net1的跳數都成為16了。反向抑制法（PoisonReverse）此法是水平分割法的一個變種。在本辦法中，路由器收到的信息被用于更新路由表，然后

22、轉發到所有端口。但是，從某個端口傳來的路由表記錄如果通過同一個端口出去，它的跳數值被設為16。圖13.14是這個概念的示意圖：路由器B已通過其左端口接收到關于Net1和Net2的信息；所以它以跳數16發送關于這些網絡的信息。同樣，關于Net3的信息從右端口進來，在右向的更新報文中Net3的cost被設為16。使用本法后穩定性被改善了。假定圖13.12中Net1對路由器A是不可訪問的。路由器B從A收到關于Net1的信息。它對A沒有影響，如果Net1是可以訪問的，因為路由器A并不選擇B的Net1記錄。但是如果Net1失效了，二者的跳數值都是16,從而避免了不穩定性。RIP第2版RIP第2版被設計用

23、來克服第1版存在的某些問題。第2版的設計者們并不增加每條記錄報文的長度，只是用新的字段替代了第1版中供TCP/IP協議由0填充的各個字段。報文格式圖13.15為RIP第2版的報文格式。這個報文的新字段如下：命令版本保留協議族路由標簽(route tag)網絡地址子網掩碼下一跳地址距離圖13.15 RIP第2版格式 路由標簽本字段帶有諸如自治系統編號等信息。它可以用來使RIP能接收來自某個外部路由協議的信息。 子網掩碼四字節字段，存放子網掩碼。 下一跳地址本字段規定了下一跳的地址。例如，這個字段在兩個自治系統共享一個網絡（主干，backbone）特別有用。此外報文可以規定在同一個自治系統或其他自

24、治系統中，數據包下一步應發送給哪個路由器。認證(authentication)為了阻止未經許可的路由發布，數據包中加入認證功能，但并沒有增加新的字段，只是將報文的第一條記錄留出來存放認證信息。為了表示該記錄是認證信息而不是路由信息,其協議字段值取FFFF16（下圖）。第二個字段是認證類型，它規定了認證所用的方法，第三個字段則為具體的認證數據。圖13.16認證命令版本保留FFFF認證類型認證數據多播第1版RIP采用廣播形式向每一個網絡鄰居發布RIP報文，這種情況下，不僅網絡上所有的路由器接收到數據包，而且所有主機也接收到數據包。而第2版RIP使用多播地址224.0.0.9將RIP報文僅向網絡中的

25、路由器發布。封裝RIP報文被封裝在UDP用戶數據報中。RIP報文中沒有指示報文長度的字段，長度由UDP數據包中相應字段規定。分配給UDP中RIP使用的公認端口號是520。RIP通過公認端口號520使用UDFfl艮務。13.3OSPF協議“開放最短路徑優先"（OSPFOpenShortestPathFirst）是另一種現在正在流行的內部路由協議。它同樣適合在一個自治系統內部使用。某些稱為“自治系統邊界路由器”的特殊路由器用來阻止（dissipating）其他自治系統的信息進入當前系統。為了提高路由傳送效率，并采用定時方式，OSPFW一個自治系統分成若干個區域（area）。區域所謂“區域

26、”是指某個自治系統內部若干網絡、主機和路由器的一種組合。一個自治系統可以分成許多個不同的區域。一個區域內的所有網絡必須相連。一個區域內的路由器向整個區域廣播（flood）路由信息。在區域邊界處，若干稱為“區域邊界路由器”的特殊路由器將整個區域的信息加以匯總，然后轉發給其他區域。在自治系統內區域之間有一個特殊的區域叫做"backbone”（主干區），一個自治系統內的所有區域都必須與這個主干區相連。換言之，主干區起主區域的作用，其他區域則為從區域的作用。不過這并不表示各區域內的路由器不能彼此相連。主干區內的路由器稱為“主干區路由器”（backbonerouters）。注意，一個主干區路由

27、器也可以同時是一個區域邊界路由器。如果由于某些問題，主干區和區域間的連接中斷了，管理員必須在路由器間建立一條“虛擬鏈路”（virtuallink）以確保主干區作為主區域的功能得以保持。每個區域都有一個區域標識號。主干區的標識號是0。圖13.17為某個自治系統及其各個區域。度量值（Metric）OSP劭議允許管理員為每一個路由分配一個被稱為“度量值”的cost（開銷數）。這種度量值可以按服務類型（最小延遲、最大吞吐量等）。事實上，一個路由器可能有幾份路由表，每份基于不同的服務類型。鏈路狀態路由OSP準用“鏈路狀態路由”算法來更新區域內的各路由表。在具體討論OSPF協議之前，讓我們先討論一下“鏈路

28、狀態路由”算法，它用來使一個區域內的每個路由器與其他路由器共享情況。共享它們對相鄰路由器的掌握情況。理解這一算法的工作原理有三個關鍵，如下：1、共享關于相鄰路由器的情況每個路由器都向區域內的所有其他的路由器發送其“鄰居的狀態”。2、和每個路由器共享每個路由器都向區域內的所有其他的路由器發送其“鄰居的狀態”，方法是進行“廣播”（flooding），即將信息發給它的所有相鄰路由器（通過它的所有輸出端口）。每個相鄰的路由器也向它的所有“鄰居”發送數據包，以此類推。每一個接收到該數據包的路由器又將該數據報復制后發給它的“鄰居”。最后，每個路由器（無一例處地）都收到了同樣的信息。3、 狀態改變信息共享每

29、個路由器僅在路由狀態發生改變時才共享相鄰路由器的狀態。這個規則與距離向量算法正好相反，后者是不管路由狀態是否改變，總是定時發送路由信息。所以鏈路狀態路由算法的這個特性使得互聯網絡的流量低于使用距離向量算法時的流量。鏈路狀態路由的思想是：每一個路由器都應該對每一時刻整個互聯網絡的拓撲情況有一個精確的了解。換言之，每個路由器都應該有一張整個互聯網絡的“拓撲圖”。根據這個拓撲，路由器可以計算出它本身和每一個網絡之間最短的路徑。這里的拓撲圖實際上是由結點和edges（線段）組成的圖。不過，要用圖來表示一個互聯網絡，我們還需要更多的定義。鏈路類型在OSP沐語中，一個網絡稱為一個“鏈路”（link）。現在

30、已經定義的鏈路狀態有四種：點對點（point-to-point），transient，stud和virtual。點對點鏈路一個點對點的鏈路連接兩個路由器，中間沒有任何其他主機或路由器。換言之，此鏈路（網絡）的作用就是用來連接兩個路由器。這種鏈路的一個例子就是通過電話線或T線路連接兩個路由器。對這種鏈路類型無需分配網絡地址。用圖形表示，路由器是各個結點，鏈路則為連接結點的一條雙向線段。在線段兩端，標出其度量值（通常兩端是一樣的）換言之，每個路由器在鏈路的另一端只有一個鄰居（見下圖）。44點對點網絡 Transient （瞬態）鏈路一個transient鏈路是一個連接了幾個路由器的網絡。數據可以通過任何一