發(fā)表日期:2006-8-08
更新日期:2006-8-08
作者文章閱讀次數(shù):3755
路由協(xié)議:路由協(xié)議（Routing Protocol）是路由器之間實(shí)現(xiàn)路由信息共享的一種機(jī)制，它允許路由器之間相互交換和維護(hù)各自的路由表。當(dāng)一臺路由器的路由表由于某種原因發(fā)生變化時，它需要及時地將這一變化通知與之相連接的其他路由器，以保證數(shù)據(jù)的正確傳遞。路由協(xié)議不承擔(dān)網(wǎng)絡(luò)上終端用戶之間的數(shù)據(jù)傳輸任務(wù)。Cisco路由器中用于TCP/IP的路由協(xié)議包括RIP（路由信息協(xié)議，Routing Information Protocol）、IGRP（內(nèi)部網(wǎng)關(guān)路由協(xié)議，Interior Gateway Routing Protocol）、OSPF（Open Shortest Path First）、NLSP（Netware鏈路服務(wù)協(xié)議，Netware Link Services Protocol）和EIGRP（增強(qiáng)IGRP）。 在過去的幾年里，因特網(wǎng)的規(guī)模以每年近100%的速度在增長，而因特網(wǎng)通信量的增長速度更高達(dá)每年400%。伴隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，路由器在溝通子網(wǎng)連接和實(shí)現(xiàn)信息交換方面的重要作用逐漸被人們所認(rèn)知。但是，路由器究竟是如何交換信息的呢？
本文主要介紹兩種基本的路由算法，即距離向量法和鏈路狀態(tài)算法。這里要注意的是，路由協(xié)議和路由算法只適用于動態(tài)路由。
距離向量法(Distance Vector Routing)
在距離向量法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時，路由器之間也將及時地相互通知有關(guān)變更信息。
在圖1中，每一個路由器從與之直接相鄰的路由器處獲得對方的路由表。例如，路由器B從路由器A和C獲得路由信息后，對自己的路由表進(jìn)行加工，加工后的路由表再傳送給路由器A和C。路由器通過這種方法不斷地積累路由信息，直到最終收斂為止。
圖1 路由表傳遞示意 1. 路由表的建立與更新
在圖2中，有三個路由器：A、B和C。路由器A的兩個網(wǎng)絡(luò)接口E0和S0分別連接在10.1.0.0和10.2.0.0網(wǎng)段上；路由器B的兩個網(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中各路由器路由表的前兩行所示，通過路由器的網(wǎng)絡(luò)接口到與之直接相連的網(wǎng)段的網(wǎng)絡(luò)連接，其向量距 離設(shè)置為0。這即是最初的路由表。
當(dāng)路由器B和A以及B和C之間相互交換路由信息后，它們會更新各自的路由表。例如，路由器B通過網(wǎng)絡(luò)端口S1收到路由器C的路由信息（10.3.0.0,S0,0）和（10.4.0.0,E0,0）后，在自己的路由表中增加一條（10.4.0.0,S1,1）路由信息。該信息表示: 通過路由器B的網(wǎng)絡(luò)接口S1可以訪問到10.4.0.0網(wǎng)段，其向量距離為1，該向量距離是在路由器C的基礎(chǔ)上加1獲得的。同樣的道理，路由器B還會產(chǎn)生一條（10.1.0.0,S0,1）路由，這條路由是通過網(wǎng)絡(luò)端口S0從路由器A獲得的。如此反復(fù)，直到最終收斂，形成圖2所示的路由表。
概括地說，距離向量算法要求每一個路由器把它的整個路由表發(fā)送給與它直接連接的其他路由器。路由表中的每一條記錄都包括目標(biāo)邏輯地址、相應(yīng)的網(wǎng)絡(luò)接口和該條路由的向量距離。當(dāng)一個路由器從它的鄰居處收到更新信息時，它會將更新信息與本身的路由表相比較。如果該路由器比較出一條新路由或是找到一條比當(dāng)前路由更好的路由時，它會對路由表進(jìn)行更新：將從該路由器到鄰居之間的向量距離與更新信息中的向量距離相加作為新路由的向量距離。
2. 收斂
所謂收斂，是指直接或間接交換路由信息的一組路由器在網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)方面或者說在網(wǎng)絡(luò)的路由信息方面達(dá)成一致。路由協(xié)議必須通過某種算法使各路由器盡快達(dá)到收斂狀態(tài)。
要實(shí)現(xiàn)收斂，必須解決路由器之間的路由環(huán)路（Routing Loops）問題。下面比較直觀地舉例講述路由環(huá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檢測到故障，停止通過接口E0向外發(fā)送數(shù)據(jù)包，并通過接口S0通知路由器B。在路由器A沒有收到故障通知前，它仍然相信可以通過路由器B訪問到10.4.0.0（路由器A路由表的最后一行），這條路徑的距離為2。
由于路由器B的路由表中指示有一條通往10.4.0.0的路徑，因此，如果路由器B在收到路由器C的故障通知前將路由表發(fā)送到C，C會認(rèn)為通過B可以訪問10.4.0.0,并在此基礎(chǔ)上修改自己的路由表，將路由表中第二條記錄修改為（10.4.0.0,S0,2）,其中S0表示通過接口S0可以訪問10.4.0.0,其距離為2。
這樣一來，路由器A、B、C都認(rèn)為通過其他的路由器存在著一條通往10.4.0.0的網(wǎng)絡(luò)路徑，結(jié)果導(dǎo)致目標(biāo)地址為10.4.0.0的數(shù)據(jù)包在這三個路由器之間來回地傳遞，從而造成一條路由環(huán)路。
一般地，人們采用4種方法解決路由環(huán)路問題。
（1） 水平分割（split horizon）
這種方法規(guī)定，路由器必須有選擇地將路由表中的路由信息發(fā)送給相鄰的其他路由器，而不是發(fā)送整個路由表。具體地說，即一條路由信息不會被發(fā)送給該信息的來源方向。這里仍以圖2為例。圖3是圖2中路由器B的路由表，通過圖3中的注釋我們可以看到，每一條路由信息都不通過該條路由信息中所指的網(wǎng)絡(luò)端口向外發(fā)送。這樣就可以避免路由環(huán)路的產(chǎn)生。
（2） 定義一個最大值
定義一個向量距離的最大值，可以在一定程度上防止形成路由環(huán)路，例如RIP協(xié)議定義Hop Count的最大值為16。使用這種方法，路由協(xié)議在向量距離超過協(xié)議允許的最大值前，允許路由環(huán)路的存在，一旦路由信息的向量距離超過規(guī)定的最大值，該路由信息將被標(biāo)記為不可到達(dá)。
與此相關(guān)的另外一個概念是TTL（Time To Live）。TTL是一個包含在數(shù)據(jù)包中的參數(shù)，數(shù)據(jù)包每經(jīng)過一次路由器的路由處理，TTL值減1，當(dāng)TTL值等于0時，路由器將放棄對該數(shù)據(jù)包的處理，這樣會避免數(shù)據(jù)包在某個環(huán)路中無休止的傳遞。
圖3 路由內(nèi)容選擇示意 （3） 掛起計數(shù)器（Hold-Down Timers）
所謂掛起計數(shù)器是指路由器需要將某些可能導(dǎo)致路由環(huán)路的網(wǎng)絡(luò)狀態(tài)的變化值保留一段時間，在這段時間內(nèi)，路由器將視情況對這些網(wǎng)絡(luò)狀態(tài)的變化所產(chǎn)生的路由信息進(jìn)行更改。下面是掛起計數(shù)器的具體工作過程。
● 當(dāng)一個路由器從它的鄰居處收到以前某個可訪問的網(wǎng)絡(luò)現(xiàn)在變?yōu)椴豢稍L問的信息時，路由器將指向該網(wǎng)絡(luò)的路由設(shè)置為不可訪問，同時啟動計數(shù)器。
● 如果在計數(shù)器到期前，該路由器又從同一個鄰居處收到該網(wǎng)絡(luò)可以訪問的信息，則它會重新將網(wǎng)絡(luò)標(biāo)記為可訪問，并刪除計數(shù)器。
● 如果該路由器從另外一個鄰居處收到一條比原路由更好的訪問該網(wǎng)絡(luò)的路由信息，它同樣將該網(wǎng)絡(luò)標(biāo)記為可訪問，以新的路由替代原路由，并刪除計數(shù)器。
● 如果在計數(shù)器到期前，該路由器從另外一個鄰居處收到一條訪問該網(wǎng)絡(luò)的比原路由差的路由信息，這條信息將被忽略。這樣做能夠使“網(wǎng)絡(luò)不可訪問”的信息有更多的時間在整個網(wǎng)絡(luò)上傳播。
● 計數(shù)器到期后，該路由標(biāo)記為不可到達(dá)，如果這時收到該網(wǎng)絡(luò)可以訪問的路由信息，路由器的處理方式同上。
需要注意的是，計數(shù)器計數(shù)時間應(yīng)該略大于路由信息傳遍整個網(wǎng)絡(luò)所需的時間。
（4） 觸發(fā)式更新（Triggered Updates）
觸發(fā)式更新已經(jīng)不是新概念，簡單地說，觸發(fā)式更新是指路由器之間不單純按照預(yù)定的時間周期進(jìn)行路由信息交換，而是在路由表發(fā)生變化的時候及時地進(jìn)行路由信息交換。觸發(fā)式更新普遍地應(yīng)用在各種路由協(xié)議中。
一般來說，路由表在沒有發(fā)生變化的情況下，將按照預(yù)定的時間周期進(jìn)行交換，例如IP RIP協(xié)議規(guī)定路由器之間每隔30秒交換一次路由信息，IPX RIP協(xié)議則規(guī)定為60秒。但是當(dāng)路由表由于某種原因發(fā)生變化時，路由器立刻將路由表的變化情況通知鄰近的路由器，再由它們?nèi)ネㄖ渌穆酚善?，這樣一波接一波，在不發(fā)生意外的情況下就可以將該路由的變化通知到網(wǎng)絡(luò)中所有的路由器。這里的意外情況包括路由更新信息在網(wǎng)絡(luò)傳輸過程中丟失或者路由更新信息沒有及時地發(fā)出，這些都有可能導(dǎo)致路由環(huán)路的產(chǎn)生。
觸發(fā)式更新經(jīng)常與掛起計數(shù)器技術(shù)結(jié)合在一起來解決路由環(huán)路問題。
圖4 有問題的網(wǎng)絡(luò)結(jié)構(gòu) 鏈路狀態(tài)算法（Link-State Routing）
鏈路狀態(tài)算法，有時也稱為最短路徑優(yōu)先算法（SPF，Shortest Path First）。與向量距離算法不同的是，這種算法需要每一個路由器都保存一份最新的關(guān)于整個網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)庫，因此路由器不僅清楚地知道從本路由器出發(fā)能否到達(dá)某一指定網(wǎng)絡(luò)，而且在能夠到達(dá)的情況下，還可以選擇出最短的路徑以及采用該路徑將經(jīng)過的路由器。使用鏈路狀態(tài)算法的路由協(xié)議有NLSP、OSPF和IS-IS。
鏈路狀態(tài)算法使用LSP（鏈路狀態(tài)數(shù)據(jù)包，Link-State Packets）、網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)庫、SPF路徑選擇算法、SPF樹，最終計算出從該路由器到其他目標(biāo)網(wǎng)絡(luò)的最短路徑，這些路徑就構(gòu)成了路由表。該算法要求每個路由器具備唯一的名字或標(biāo)識。
1. 鏈路狀態(tài)網(wǎng)絡(luò)發(fā)現(xiàn)機(jī)制
該機(jī)制用于創(chuàng)建整個網(wǎng)絡(luò)的一幅全景圖，所有的路由器都保存該圖的一個副本，從而保持一致。其具體工作過程如下。
（1）每個路由器都必須知道它的鄰居是誰，這一點(diǎn)需要相鄰的路由器之間互相通知。
（2）每個路由器都將LSP（鏈路狀態(tài)數(shù)據(jù)包）發(fā)送給網(wǎng)絡(luò)上其他的路由器，LSP的內(nèi)容包括該路由器通過哪些網(wǎng)絡(luò)與哪些路由器直接連接，以及相應(yīng)連接的傳輸代價。以圖2中所示的網(wǎng)絡(luò)為例，路由器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連接（這里假設(shè)相鄰路由器之間的傳輸代價為1）。
（3）路由器根據(jù)收到的LSP逐步地構(gòu)建起網(wǎng)絡(luò)的拓?fù)鋽?shù)據(jù)庫（即SPF樹，樹的根接點(diǎn)為該路由器本身）。
（4）路由器根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)庫判斷目標(biāo)網(wǎng)絡(luò)是否可到達(dá)以及確定其最短路徑。
（5）路由器將第4步計算出的最短路徑以及所使用的該路由器的網(wǎng)絡(luò)端口信息添加到路由表中。
（6）鏈路狀態(tài)算法要求各路由器的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)庫相互一致。因此，當(dāng)鏈路狀態(tài)發(fā)生變化時，最先檢測到這一變化的路由器需要將變化的情況發(fā)送給其他的路由器。每當(dāng)路由器收到新的LSP，它都會重新計算最短路徑并更新路由表，保證各路由器在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)方面重新達(dá)成一致。
2. 重點(diǎn)考慮因素
在采用鏈路狀態(tài)算法時，網(wǎng)管員應(yīng)當(dāng)考慮以下兩方面的因素。
(1) 路由器的存儲空間和處理能力
由于采用鏈路狀態(tài)算法時路由器不但要保存來自其他路由器的LSP，而且還要保存網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和路由表，所以其存儲空間一定要大。另外，根據(jù)SPF樹計算最短路徑的算法較為復(fù)雜，因此要求路由器的處理能力要強(qiáng)。
(2) 帶寬
在建立SPF樹的最初階段，有大量的LSP需要通過網(wǎng)絡(luò)進(jìn)行傳輸，這對網(wǎng)絡(luò)帶寬的要求較高。如果帶寬不夠，不僅影響路由器收斂的速度，而且會影響正常的數(shù)據(jù)傳輸。
3. 可能出現(xiàn)的問題及解決辦法
與距離向量算法類似的是，鏈路狀態(tài)算法同樣必須保證所有的路由器能夠收到所有必需的LSP。圖4給出了一個可能發(fā)生問題的案例。
假設(shè)路由器C首先檢測到C和D之間的Network 1發(fā)生故障，那么，路由器C將把該故障情況以LSP的方式發(fā)送給網(wǎng)絡(luò)上的其他路由器B、D、和A（該LSP設(shè)為LSP1）。假設(shè)Network 1很快恢復(fù)正常，而且路由器D先檢測到，那么路由器D將把Network 1恢復(fù)正常的情況以LSP的形式再發(fā)送給路由器A、C和B（設(shè)為LSP2）。如果由于某種原因（比如不同網(wǎng)絡(luò)的傳輸速度不同或傳輸路徑不同等），LSP2先于LSP1到達(dá)路由器A。這時，問題就出現(xiàn)了，路由器A究竟應(yīng)該把哪一個LSP作為反映最終情況的LSP呢？
鏈路狀態(tài)算法可以采用以下幾種技術(shù)來解決這些潛在問題。
● 延長LSP的發(fā)送周期。
● 以多點(diǎn)發(fā)送LSP（Multicast）代替廣播發(fā)送LSP（Broadcast）。在由多個LAN互連組成的網(wǎng)絡(luò)中，可以指定一個或多個路由器用于存放各路由器發(fā)送的LSP，其他的路由器通過這些指定路由器獲得一致的拓?fù)鋽?shù)據(jù)。
● 在大型網(wǎng)絡(luò)中，可以設(shè)定一個由不同區(qū)域組成的層次結(jié)構(gòu)。某一級區(qū)域中的路由器不必存儲和處理來自所有不同區(qū)域路由器的LSP。
● 使用LSP時間戳、順序號等手段來解決LSP發(fā)送過程中的順序問題。
兩種算法的比較
距離向量算法和鏈路狀態(tài)算法各有千秋，兩種算法的差別基本上可以歸結(jié)為下表中的四點(diǎn),我們可以以此作為具體應(yīng)用中選擇路由協(xié)議的技術(shù)依據(jù)。
表 兩種算法的比較
