在過去的幾年里，因特網的規(guī)模以每年近100%的速度在增長，而因特網通信量的增長速度更高達每年400%。伴隨著網絡規(guī)模的不斷擴大，路由器在溝通子網連接和實現信息交換方面的重要作用逐漸被人們所認知。但是，路由器究竟是如何交換信息的呢？

本文主要介紹兩種基本的路由算法，即距離向量法和鏈路狀態(tài)算法。這里要注意的是，路由協(xié)議和路由算法只適用于動態(tài)路由。

距離向量法(Distance Vector Routing)

在距離向量法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當網絡拓撲結構發(fā)生變化時，路由器之間也將及時地相互通知有關變更信息。

在圖1中，每一個路由器從與之直接相鄰的路由器處獲得對方的路由表。例如，路由器B從路由器A和C獲得路由信息后，對自己的路由表進行加工，加工后的路由表再傳送給路由器A和C。路由器通過這種方法不斷地積累路由信息，直到最終收斂為止。

圖1 路由表傳遞示意

1. 路由表的建立與更新

在圖2中，有三個路由器：A、B和C。路由器A的兩個網絡接口E0和S0分別連接在10.1.0.0和10.2.0.0網段上；路由器B的兩個網絡接口S0和S1分別連接在10.2.0.0和10.3.0.0網段上；路由器C的網絡接口S0和E0分別連接在10.3.0.0和10.4.0.0網段上。

圖2 路由表內容列表

如圖2中各路由器路由表的前兩行所示，通過路由器的網絡接口到與之直接相連的網段的網絡連接，其向量距  離設置為0。這即是最初的路由表。

當路由器B和A以及B和C之間相互交換路由信息后，它們會更新各自的路由表。例如，路由器B通過網絡端口S1收到路由器C的路由信息（10.3.0.0,S0,0）和（10.4.0.0,E0,0）后，在自己的路由表中增加一條（10.4.0.0,S1,1）路由信息。該信息表示: 通過路由器B的網絡接口S1可以訪問到10.4.0.0網段，其向量距離為1，該向量距離是在路由器C的基礎上加1獲得的。同樣的道理，路由器B還會產生一條（10.1.0.0,S0,1）路由，這條路由是通過網絡端口S0從路由器A獲得的。如此反復，直到最終收斂，形成圖2所示的路由表。

概括地說，距離向量算法要求每一個路由器把它的整個路由表發(fā)送給與它直接連接的其他路由器。路由表中的每一條記錄都包括目標邏輯地址、相應的網絡接口和該條路由的向量距離。當一個路由器從它的鄰居處收到更新信息時，它會將更新信息與本身的路由表相比較。如果該路由器比較出一條新路由或是找到一條比當前路由更好的路由時，它會對路由表進行更新：將從該路由器到鄰居之間的向量距離與更新信息中的向量距離相加作為新路由的向量距離。

2. 收斂

所謂收斂，是指直接或間接交換路由信息的一組路由器在網絡的拓撲結構方面或者說在網絡的路由信息方面達成一致。路由協(xié)議必須通過某種算法使各路由器盡快達到收斂狀態(tài)。

要實現收斂，必須解決路由器之間的路由環(huán)路（Routing Loops）問題。下面比較直觀地舉例講述路由環(huán)路問題的產生。

假設在圖2中，網絡10.4.0.0發(fā)生故障，在網絡發(fā)生故障前，路由器A、B、C的路由表已經收斂為圖2的狀態(tài)。

網絡發(fā)生故障后，路由器C檢測到故障，停止通過接口E0向外發(fā)送數據包，并通過接口S0通知路由器B。在路由器A沒有收到故障通知前，它仍然相信可以通過路由器B訪問到10.4.0.0（路由器A路由表的最后一行），這條路徑的距離為2。

由于路由器B的路由表中指示有一條通往10.4.0.0的路徑，因此，如果路由器B在收到路由器C的故障通知前將路由表發(fā)送到C，C會認為通過B可以訪問10.4.0.0,并在此基礎上修改自己的路由表，將路由表中第二條記錄修改為（10.4.0.0,S0,2）,其中S0表示通過接口S0可以訪問10.4.0.0,其距離為2。

這樣一來，路由器A、B、C都認為通過其他的路由器存在著一條通往10.4.0.0的網絡路徑，結果導致目標地址為10.4.0.0的數據包在這三個路由器之間來回地傳遞，從而造成一條路由環(huán)路。

一般地，人們采用4種方法解決路由環(huán)路問題。

（1） 水平分割（split horizon）

這種方法規(guī)定，路由器必須有選擇地將路由表中的路由信息發(fā)送給相鄰的其他路由器，而不是發(fā)送整個路由表。具體地說，即一條路由信息不會被發(fā)送給該信息的來源方向。這里仍以圖2為例。圖3是圖2中路由器B的路由表，通過圖3中的注釋我們可以看到，每一條路由信息都不通過該條路由信息中所指的網絡端口向外發(fā)送。這樣就可以避免路由環(huán)路的產生。

（2） 定義一個最大值

定義一個向量距離的最大值，可以在一定程度上防止形成路由環(huán)路，例如RIP協(xié)議定義Hop Count的最大值為16。使用這種方法，路由協(xié)議在向量距離超過協(xié)議允許的最大值前，允許路由環(huán)路的存在，一旦路由信息的向量距離超過規(guī)定的最大值，該路由信息將被標記為不可到達。

與此相關的另外一個概念是TTL（Time To Live）。TTL是一個包含在數據包中的參數，數據包每經過一次路由器的路由處理，TTL值減1，當TTL值等于0時，路由器將放棄對該數據包的處理，這樣會避免數據包在某個環(huán)路中無休止的傳遞。

圖3 路由內容選擇示意

（3） 掛起計數器（Hold-Down Timers）

所謂掛起計數器是指路由器需要將某些可能導致路由環(huán)路的網絡狀態(tài)的變化值保留一段時間，在這段時間內，路由器將視情況對這些網絡狀態(tài)的變化所產生的路由信息進行更改。下面是掛起計數器的具體工作過程。

● 當一個路由器從它的鄰居處收到以前某個可訪問的網絡現在變?yōu)椴豢稍L問的信息時，路由器將指向該網絡的路由設置為不可訪問，同時啟動計數器。

● 如果在計數器到期前，該路由器又從同一個鄰居處收到該網絡可以訪問的信息，則它會重新將網絡標記為可訪問，并刪除計數器。

● 如果該路由器從另外一個鄰居處收到一條比原路由更好的訪問該網絡的路由信息，它同樣將該網絡標記為可訪問，以新的路由替代原路由，并刪除計數器。

● 如果在計數器到期前，該路由器從另外一個鄰居處收到一條訪問該網絡的比原路由差的路由信息，這條信息將被忽略。這樣做能夠使“網絡不可訪問”的信息有更多的時間在整個網絡上傳播。

● 計數器到期后，該路由標記為不可到達，如果這時收到該網絡可以訪問的路由信息，路由器的處理方式同上。

需要注意的是，計數器計數時間應該略大于路由信息傳遍整個網絡所需的時間。

（4） 觸發(fā)式更新（Triggered Updates）

觸發(fā)式更新已經不是新概念，簡單地說，觸發(fā)式更新是指路由器之間不單純按照預定的時間周期進行路由信息交換，而是在路由表發(fā)生變化的時候及時地進行路由信息交換。觸發(fā)式更新普遍地應用在各種路由協(xié)議中。

一般來說，路由表在沒有發(fā)生變化的情況下，將按照預定的時間周期進行交換，例如IP RIP協(xié)議規(guī)定路由器之間每隔30秒交換一次路由信息，IPX RIP協(xié)議則規(guī)定為60秒。但是當路由表由于某種原因發(fā)生變化時，路由器立刻將路由表的變化情況通知鄰近的路由器，再由它們去通知其他的路由器，這樣一波接一波，在不發(fā)生意外的情況下就可以將該路由的變化通知到網絡中所有的路由器。這里的意外情況包括路由更新信息在網絡傳輸過程中丟失或者路由更新信息沒有及時地發(fā)出，這些都有可能導致路由環(huán)路的產生。

觸發(fā)式更新經常與掛起計數器技術結合在一起來解決路由環(huán)路問題。

圖4 有問題的網絡結構

鏈路狀態(tài)算法（Link-State Routing）

鏈路狀態(tài)算法，有時也稱為最短路徑優(yōu)先算法（SPF，Shortest Path First）。與向量距離算法不同的是，這種算法需要每一個路由器都保存一份最新的關于整個網絡的網絡拓撲結構數據庫，因此路由器不僅清楚地知道從本路由器出發(fā)能否到達某一指定網絡，而且在能夠到達的情況下，還可以選擇出最短的路徑以及采用該路徑將經過的路由器。使用鏈路狀態(tài)算法的路由協(xié)議有NLSP、OSPF和IS-IS。

鏈路狀態(tài)算法使用LSP（鏈路狀態(tài)數據包，Link-State Packets）、網絡拓撲數據庫、SPF路徑選擇算法、SPF樹，最終計算出從該路由器到其他目標網絡的最短路徑，這些路徑就構成了路由表。該算法要求每個路由器具備唯一的名字或標識。

1. 鏈路狀態(tài)網絡發(fā)現機制

該機制用于創(chuàng)建整個網絡的一幅全景圖，所有的路由器都保存該圖的一個副本，從而保持一致。其具體工作過程如下。

（1）每個路由器都必須知道它的鄰居是誰，這一點需要相鄰的路由器之間互相通知。

（2）每個路由器都將LSP（鏈路狀態(tài)數據包）發(fā)送給網絡上其他的路由器，LSP的內容包括該路由器通過哪些網絡與哪些路由器直接連接，以及相應連接的傳輸代價。以圖2中所示的網絡為例，路由器B向外發(fā)送的LSP包括(（B,A,10.2.0.0）,(B,C,10.3.0.0)),這表示B通過10.2.0.0與A連接，通過10.3.0.0與C連接（這里假設相鄰路由器之間的傳輸代價為1）。

（3）路由器根據收到的LSP逐步地構建起網絡的拓撲數據庫（即SPF樹，樹的根接點為該路由器本身）。

（4）路由器根據網絡的拓撲結構數據庫判斷目標網絡是否可到達以及確定其最短路徑。

（5）路由器將第4步計算出的最短路徑以及所使用的該路由器的網絡端口信息添加到路由表中。

（6）鏈路狀態(tài)算法要求各路由器的網絡拓撲結構數據庫相互一致。因此，當鏈路狀態(tài)發(fā)生變化時，最先檢測到這一變化的路由器需要將變化的情況發(fā)送給其他的路由器。每當路由器收到新的LSP，它都會重新計算最短路徑并更新路由表，保證各路由器在網絡拓撲結構方面重新達成一致。

2. 重點考慮因素

在采用鏈路狀態(tài)算法時，網管員應當考慮以下兩方面的因素。

(1) 路由器的存儲空間和處理能力

由于采用鏈路狀態(tài)算法時路由器不但要保存來自其他路由器的LSP，而且還要保存網絡的拓撲結構和路由表，所以其存儲空間一定要大。另外，根據SPF樹計算最短路徑的算法較為復雜，因此要求路由器的處理能力要強。

(2) 帶寬

在建立SPF樹的最初階段，有大量的LSP需要通過網絡進行傳輸，這對網絡帶寬的要求較高。如果帶寬不夠，不僅影響路由器收斂的速度，而且會影響正常的數據傳輸。

3. 可能出現的問題及解決辦法

與距離向量算法類似的是，鏈路狀態(tài)算法同樣必須保證所有的路由器能夠收到所有必需的LSP。圖4給出了一個可能發(fā)生問題的案例。

假設路由器C首先檢測到C和D之間的Network 1發(fā)生故障，那么，路由器C將把該故障情況以LSP的方式發(fā)送給網絡上的其他路由器B、D、和A（該LSP設為LSP1）。假設Network 1很快恢復正常，而且路由器D先檢測到，那么路由器D將把Network 1恢復正常的情況以LSP的形式再發(fā)送給路由器A、C和B（設為LSP2）。如果由于某種原因（比如不同網絡的傳輸速度不同或傳輸路徑不同等），LSP2先于LSP1到達路由器A。這時，問題就出現了，路由器A究竟應該把哪一個LSP作為反映最終情況的LSP呢？

鏈路狀態(tài)算法可以采用以下幾種技術來解決這些潛在問題。

● 延長LSP的發(fā)送周期。

● 以多點發(fā)送LSP（Multicast）代替廣播發(fā)送LSP（Broadcast）。在由多個LAN互連組成的網絡中，可以指定一個或多個路由器用于存放各路由器發(fā)送的LSP，其他的路由器通過這些指定路由器獲得一致的拓撲數據。

● 在大型網絡中，可以設定一個由不同區(qū)域組成的層次結構。某一級區(qū)域中的路由器不必存儲和處理來自所有不同區(qū)域路由器的LSP。

● 使用LSP時間戳、順序號等手段來解決LSP發(fā)送過程中的順序問題。

兩種算法的比較

距離向量算法和鏈路狀態(tài)算法各有千秋，兩種算法的差別基本上可以歸結為下表中的四點,我們可以以此作為具體應用中選擇路由協(xié)議的技術依據。

表 兩種算法的比較