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

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

距離向量法(Distance Vector Routing)

在距離向量法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，路由器之間也將及時(shí)地相互通知有關(guān)變更信息。

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

圖1 路由表傳遞示意

1. 路由表的建立與更新

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

圖2 路由表內(nèi)容列表

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

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

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

2. 收斂

所謂收斂，是指直接或間接交換路由信息的一組路由器在網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)方面或者說(shuō)在網(wǎng)絡(luò)的路由信息方面達(dá)成一致。路由協(xié)議必須通過(guò)某種算法使各路由器盡快達(dá)到收斂狀態(tài)。

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

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

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

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

這樣一來(lái)，路由器A、B、C都認(rèn)為通過(guò)其他的路由器存在著一條通往10.4.0.0的網(wǎng)絡(luò)路徑，結(jié)果導(dǎo)致目標(biāo)地址為10.4.0.0的數(shù)據(jù)包在這三個(gè)路由器之間來(lái)回地傳遞，從而造成一條路由環(huán)路。

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

（1） 水平分割（split horizon）

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

（2） 定義一個(gè)最大值

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

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

圖3 路由內(nèi)容選擇示意

（3） 掛起計(jì)數(shù)器（Hold-Down Timers）

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

● 當(dāng)一個(gè)路由器從它的鄰居處收到以前某個(gè)可訪問(wèn)的網(wǎng)絡(luò)現(xiàn)在變?yōu)椴豢稍L問(wèn)的信息時(shí)，路由器將指向該網(wǎng)絡(luò)的路由設(shè)置為不可訪問(wèn)，同時(shí)啟動(dòng)計(jì)數(shù)器。

● 如果在計(jì)數(shù)器到期前，該路由器又從同一個(gè)鄰居處收到該網(wǎng)絡(luò)可以訪問(wèn)的信息，則它會(huì)重新將網(wǎng)絡(luò)標(biāo)記為可訪問(wèn)，并刪除計(jì)數(shù)器。

● 如果該路由器從另外一個(gè)鄰居處收到一條比原路由更好的訪問(wèn)該網(wǎng)絡(luò)的路由信息，它同樣將該網(wǎng)絡(luò)標(biāo)記為可訪問(wèn)，以新的路由替代原路由，并刪除計(jì)數(shù)器。

● 如果在計(jì)數(shù)器到期前，該路由器從另外一個(gè)鄰居處收到一條訪問(wèn)該網(wǎng)絡(luò)的比原路由差的路由信息，這條信息將被忽略。這樣做能夠使“網(wǎng)絡(luò)不可訪問(wèn)”的信息有更多的時(shí)間在整個(gè)網(wǎng)絡(luò)上傳播。

● 計(jì)數(shù)器到期后，該路由標(biāo)記為不可到達(dá)，如果這時(shí)收到該網(wǎng)絡(luò)可以訪問(wèn)的路由信息，路由器的處理方式同上。

需要注意的是，計(jì)數(shù)器計(jì)數(shù)時(shí)間應(yīng)該略大于路由信息傳遍整個(gè)網(wǎng)絡(luò)所需的時(shí)間。

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

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

一般來(lái)說(shuō)，路由表在沒(méi)有發(fā)生變化的情況下，將按照預(yù)定的時(shí)間周期進(jìn)行交換，例如IP RIP協(xié)議規(guī)定路由器之間每隔30秒交換一次路由信息，IPX RIP協(xié)議則規(guī)定為60秒。但是當(dāng)路由表由于某種原因發(fā)生變化時(shí)，路由器立刻將路由表的變化情況通知鄰近的路由器，再由它們?nèi)ネㄖ渌穆酚善鳎@樣一波接一波，在不發(fā)生意外的情況下就可以將該路由的變化通知到網(wǎng)絡(luò)中所有的路由器。這里的意外情況包括路由更新信息在網(wǎng)絡(luò)傳輸過(guò)程中丟失或者路由更新信息沒(méi)有及時(shí)地發(fā)出，這些都有可能導(dǎo)致路由環(huán)路的產(chǎn)生。

觸發(fā)式更新經(jīng)常與掛起計(jì)數(shù)器技術(shù)結(jié)合在一起來(lái)解決路由環(huán)路問(wèn)題。

圖4 有問(wèn)題的網(wǎng)絡(luò)結(jié)構(gòu)

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

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

鏈路狀態(tài)算法使用LSP（鏈路狀態(tài)數(shù)據(jù)包，Link-State Packets）、網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)庫(kù)、SPF路徑選擇算法、SPF樹，最終計(jì)算出從該路由器到其他目標(biāo)網(wǎng)絡(luò)的最短路徑，這些路徑就構(gòu)成了路由表。該算法要求每個(gè)路由器具備唯一的名字或標(biāo)識(shí)。

1. 鏈路狀態(tài)網(wǎng)絡(luò)發(fā)現(xiàn)機(jī)制

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

（1）每個(gè)路由器都必須知道它的鄰居是誰(shuí)，這一點(diǎn)需要相鄰的路由器之間互相通知。

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

（3）路由器根據(jù)收到的LSP逐步地構(gòu)建起網(wǎng)絡(luò)的拓?fù)鋽?shù)據(jù)庫(kù)（即SPF樹，樹的根接點(diǎn)為該路由器本身）。

（4）路由器根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)庫(kù)判斷目標(biāo)網(wǎng)絡(luò)是否可到達(dá)以及確定其最短路徑。

（5）路由器將第4步計(jì)算出的最短路徑以及所使用的該路由器的網(wǎng)絡(luò)端口信息添加到路由表中。

（6）鏈路狀態(tài)算法要求各路由器的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)庫(kù)相互一致。因此，當(dāng)鏈路狀態(tài)發(fā)生變化時(shí)，最先檢測(cè)到這一變化的路由器需要將變化的情況發(fā)送給其他的路由器。每當(dāng)路由器收到新的LSP，它都會(huì)重新計(jì)算最短路徑并更新路由表，保證各路由器在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)方面重新達(dá)成一致。

2. 重點(diǎn)考慮因素

在采用鏈路狀態(tài)算法時(shí)，網(wǎng)管員應(yīng)當(dāng)考慮以下兩方面的因素。

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

由于采用鏈路狀態(tài)算法時(shí)路由器不但要保存來(lái)自其他路由器的LSP，而且還要保存網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和路由表，所以其存儲(chǔ)空間一定要大。另外，根據(jù)SPF樹計(jì)算最短路徑的算法較為復(fù)雜，因此要求路由器的處理能力要強(qiáng)。

(2) 帶寬

在建立SPF樹的最初階段，有大量的LSP需要通過(guò)網(wǎng)絡(luò)進(jìn)行傳輸，這對(duì)網(wǎng)絡(luò)帶寬的要求較高。如果帶寬不夠，不僅影響路由器收斂的速度，而且會(huì)影響正常的數(shù)據(jù)傳輸。

3. 可能出現(xiàn)的問(wèn)題及解決辦法

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

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

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

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

● 以多點(diǎn)發(fā)送LSP（Multicast）代替廣播發(fā)送LSP（Broadcast）。在由多個(gè)LAN互連組成的網(wǎng)絡(luò)中，可以指定一個(gè)或多個(gè)路由器用于存放各路由器發(fā)送的LSP，其他的路由器通過(guò)這些指定路由器獲得一致的拓?fù)鋽?shù)據(jù)。

● 在大型網(wǎng)絡(luò)中，可以設(shè)定一個(gè)由不同區(qū)域組成的層次結(jié)構(gòu)。某一級(jí)區(qū)域中的路由器不必存儲(chǔ)和處理來(lái)自所有不同區(qū)域路由器的LSP。

● 使用LSP時(shí)間戳、順序號(hào)等手段來(lái)解決LSP發(fā)送過(guò)程中的順序問(wèn)題。

兩種算法的比較

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

表 兩種算法的比較