淺析路由協議的實現算法

2019-11-04 12:05:55

字體：大中小

來源：轉載

供稿：網友

　伴隨著網絡規模的不斷擴大，路由器在溝通子網連接和實現信息交換方面的重要作用逐漸被人們所認知。本文將以Cisco路由器為例簡要闡述路由器之間交換路由信息的兩種主要算法：距離向量法（Distance Vector Routing）和鏈路狀態算法（Link-State Routing）。
　　

　　一、路由協議（Routing PRotocol）
　　
　　　　路由協議是路由器之間實現路由信息共享的一種機制，它答應路由器之間相互交換和維護各自的路由表。當一臺路由器的路由表由于某種原因發生變化時，它需要及時地將這一變化通知與之相連接的其他路由器，以保證數據的正確傳遞。路由協議不承擔網絡上終端用戶之間的數據傳輸任務。Cisco路由器中用于TCP/ip的路由協議包括RIP（路由信息協議，Routing Information Protocol）、IGRP（內部網關路由協議，Interior Gateway Routing Protocol）、OSPF（Open Shortest Path First）、NLSP（Netware鏈路服務協議，Netware Link Services Protocol）和EIGRP（增強IGRP）。
　　
　　二、靜態路由和動態路由的概念
　　
　　1、靜態路由
　　
　　　　靜態路由是指由網絡治理員手工配置的路由信息。當網絡的拓撲結構或鏈路的狀態發生變化時，網絡治理員需要手工去修改路由表中相關的靜態路由信息。靜態路由信息在缺省情況下是私有的，即它不會傳遞給其他的路由器。當然，你也可以通過對路由器進行設置使之成為共享的。靜態路由一般適用于比較簡單的網絡環境，因為在這樣的環境中，網絡治理員易于清楚地了解網絡的拓撲結構，便于設置正確的路由信息。下面是兩個適合使用靜態路由的實例。
　　　

　　　　在左圖中，假設Network 1之外的其他網絡需要訪問Network1時必須經過路由器A和路由器B，則可以在路由器A中設置一條指向路由器B的靜態路由信息，這樣做的好處在于可以減少路由器A和路由器B之間WAN鏈路上的數據傳輸量，因為使用靜態路由后，路由器A和B之間沒有必要進行路由信息的交換。
　　
　　　　在一個支持DDR（dial-on-demand routing）的網絡中，撥號鏈路只在需要時才撥通，因此不能為動態路由信息表提供路由信息的變更情況。這種情況下，也適合使用靜態路由。
　　
　　　　使用靜態路由的另一個好處在于其安全保密性。使用動態路由時，需要路由器之間頻繁地交換各自的路由表，而通過對路由表的分析可以揭示網絡的拓撲結構和網絡地址等信息，因此，出于安全方面的考慮也可以采用靜態路由。
　　
　　　　在大型和復雜的網絡環境中，往往不宜采用靜態路由，一方面因為網絡治理員難以全面地了解整個網絡的拓撲結構；另一方面，當網絡的拓撲結構和鏈路狀態發生變化時，需要大范圍地調整路由器中的靜態路由信息，這一工作的難度和復雜程度是可想而知的。
　　
　　2、動態路由
　　
　　　　動態路由使路由器能夠自動地建立起自己的路由表，并且能夠根據情況的變化適時地進行調整。
　　
　　動態路由機制的運做依靠路由器的兩個基本功能：
　　
　　對路由表的維護
　　
　　路由器之間適時的路由信息交換
　　　

　　前面提到，路由器之間的路由信息交換是基于路由協議實現的。通過左圖可以直觀地看到路由信息交換的過程。交換路由信息的最終目的在于通過路由表找到一條數據交換的“最佳”路徑。每一種路由算法都有其衡量“最佳”的一套原則。大多數算法使用一個量化的參數來衡量路徑的優劣，一般說來，參數值越小，路徑越好。該參數可以通過路徑的某一特性進行計算，也可以在綜合多個特性的基礎上進行計算，幾個比較常用的特征是：
　　
　　路徑所包含的路由器結點數（hop count）
　　
　　網絡傳輸費用（cost）
　　
　　帶寬（bandwidth）
　　
　　延遲（delay）
　　
　　負載（load）
　　
　　可靠性（reliability）
　　
　　最大傳輸單元MTU（maximum transmission unit）
　　
　　三、路由協議的實現算法
　　
　　　　本文主要介紹兩種基本的路由算法，即距離向量法（Distance Vector Routing）和鏈路狀態算法（Link-State Routing）。路由協議和路由算法只針對動態路由。
　　
　　（一）、距離向量法（Distance Vector Routing）
　　
　　　　在距離向量法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當網絡拓撲結構發生變化時，路由器之間也將及時地相互通知有關變更信息。
　　
　　　　在圖3中，每一個路由器從與之直接相鄰的路由器那兒獲得對方的路由表。例如，路由器B從路由器A和C那里獲得路由信息后，根據其所得到的信息對自己的路由表進行加工，然后將加工后的路由表再傳送給路由器A和C。路由器通過這種方法不斷地積累路由信息，直到最終收斂為止。值得一提的是，在這種算法中，路由器不可能獲知整個網絡確切的拓撲結構。路由器是如何根據收到的路由信息對自身路由表進行加工，又是如何達到收斂的呢？
　　　

　　1、路由表的建立與更新
　　
　　　　在圖4中，有三個路由器：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網段上。

　　　

　　如圖4中各路由器路由表的前兩行所示，通過路由器的網絡接口到與之直接相連的網段的網絡連接，其向量距離設置為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獲得的。如此反復，直到最終收斂，形成圖4所示的路由表。
　　
　　　　概括地說來，距離向量算法要求每一個路由器把它的整個路由表發送給與它直接連接的其他路由器。路由表中的每一條記錄都包括目標邏輯地址、相應的網絡接口和該條路由的向量距離。當一個路由器從它的鄰居那兒收到更新信息時，它將更新信息與本身的路由表相比較，假如它能從鄰居那兒找到一條它以前不曾知道的新的路由或是找到一條比當前路由更好的路由時，路由器會對路由表進行更新：將從該路由器到鄰居之間的向量距離與更新信息中的向量距離相加作為新路由的向量距離。上例中將相鄰路由器之間的向量距離設置為1。
　　
　　2、收斂
　　
　　　　所謂收斂，是指直接或間接交換路由信息的一組路由器在網絡的拓撲結構方面或者說在網絡的路由信息方面達成一致。路由協議必須通過某種算法使各路由器盡快達到收斂狀態。
　　
　　要實現收斂，必須解決路由器之間的路由環路（Routing Loops）問題。下面的例子比較直觀地講述了路由環路問題的產生。假設在圖4中，網絡10.4.0.0發生故障，在網絡發生故障前，路由器A、B、C的路由表已經收斂為圖4的狀態。情況按照下面的描述一步步發生：
　　
　　　　（1）網絡發生故障后，路由器C檢測到故障，停止通過接口E0向外發送數據包，并通過接口S0通知路由器B。在路由器A沒有收到故障通知前，它仍然相信可以通過路由器B訪問到10.4.0.0（路由器A路由表的最后一行），這條路徑的距離為2。
　　
　　　　（2）由于路由器B的路由表中指示有一條通往10.4.0.0的路徑，因此，假如路由器B在收到路由器C的故障通知前將路由表發送到C的話，C會認為通過B可以訪問10.4.0.0,并在此基礎上修改自己的路由表，將路由表中第二條記錄修改為（10.4.0.0,S0,2）,其中S0表示通過接口S0可以訪問10.4.0.0,其距離為2。
　　
　　　　（3）這樣一來，路由器A、B、C都認為通過其他的路由器存在著一條通往10.4.0.0的網絡路徑，結果導致目標地址為10.4.0.0的數據包在這三個路由器之間往返地傳遞，從而造成一條路由環路。
　　
　　解決路由環路問題可以采用以下幾種方法：
　　
　　　　（1）水平分割（split horizon）
　　
　　　　這種方法規定，路由器必須有選擇地將路由表中的路由信息發送給相鄰的其他路由器，而不是發送整個路由表。具體一點，即對于某條路由信息來說，不將它發送給該條路由信息的來源方向。仍以圖4為例。圖5是圖4中路由器B的路由表，通過圖5中的注釋可以看到，每一條路由信息都不通過該條路由信息中所指的網絡端口向外發送。
　　
　　這樣就可以避免路由環路的產生。
　　　

　　 2）定義一個最大值
　　
　　　　定義一個向量距離的最大值，可以在一定程度上防止形成路由環路，例如RIP協議定義Hop Count的最大值為16。使用這種方法，路由協議在向量距離超過協議答應的最大值前，答應路由環路的存在，一旦路由信息的向量距離超過規定的最大值，該路由信息將被標記為不可到達。與此相關的另外一個概念是TTL（Time To Live）。TTL是一個包含在數據包中的參數，數據包每經過一次路由器的路由處理，TTL值減1，當TTL值等于0時，路由器將放棄對該數據包的處理，這樣會避免數據包在某個環路中無休止的傳遞。
　　
　　（3）掛起計數器（Hold-Down Timers）　　所謂掛起計數器是指路由器需要將某些可能導致路由環路的網絡狀態的變化保留一段時間，在這段時間內，路由器將視情況對這些網絡狀態的變化所產生的路由信息進行更改。下面看一下掛起計數器是如何工作的：
　　
　　當一個路由器從它的鄰居那兒收到以前某個可訪問的網絡現
　　
　　在變為不可訪問的信息時，路由器將指向該網絡的路由設置為不可訪問，同時啟動計數器。
　　
　　假如在計數器到期前，該路由器又從同一個鄰居那兒收到該網絡可以訪問的信息，則它會重新將網絡標記為可訪問，并刪除計數器。
　　
　　假如該路由器從另外一個鄰居那兒收到一條比原路由更好的訪問該網絡的路由信息，它同樣將該網絡標記為可訪問，以新的路由替代原路由，并刪除計數器。
　　
　　假如在計數器到期前，該路由器從另外一個鄰居那兒收到一條訪問該網絡的比原路由差的路由信息，這條信息將被忽略。這樣做能夠使“網絡不可訪問”的信息有更多的時間在整個網絡上傳播。
　　
　　計數器到期后，該路由標記為不可到達，假如這時收到該網絡可以訪問的路由信息，路由器的處理方式同上。
　　
　　計數器計數時間的長短應該略大于路由信息傳遍整個網絡所需的時間。
　　
　　（4）觸發式更新（Triggered Updates）
　　
　　　　觸發式更新在這里已經不是新概念，因為我們在前面談到路由器之間的路由信息交換和上述三種解決路由環路的方法時，已經不止一次地使用了這一概念，盡管那時沒有明確這種提法。簡單的說，觸發式更新是指路由器之間不單純按照預定的時間周期進行路由信息交換，而是在路由表發生變化的時候及時地進行路由信息交換。觸發式更新普遍地應用在各種路由協議中。
　　
　　　　一般說來，路由表在沒有發生變化的情況下，將按照預定的時間周期進行交換，例如IP RIP協議規定路由器之間每隔30秒交換一次路由信息，IPX RIP協議則規定為60秒。但是當路由表由于某種原因發生變化時，路由器馬上將路由表的變化情況通知鄰近的路由器，再由它們去通知其他的路由器，這樣一波接一波，在不發生意外的情況下就可以將該路由的變化通知到網絡中所有的路由器。意外情況包括路由更新信息在網絡傳輸過程中的丟失或者路由更新信息沒有及時地發出，這都有可能導致路由環路的產生，譬如在介紹“收斂”時所舉的例子。

　　
　　觸發式更新經常與掛起計數器技術結合在一起來解決路由環路問題。
　　
　　(二)鏈路狀態算法（Link-State Routing）
　　
　　　　鏈路狀態算法，有時也稱為最短路徑優先算法（SPF-Shortest Path First）。與向量距離算法不同的是，這種算法需要每一個路由器都保存一份最新的關于整個網絡的網絡拓撲結構數據庫，因此路由器不僅清楚地知道從本路由器出發能否到達某一指定網絡，而且在能到達的情況下，還能選擇出最短的路徑以及使用該路徑將經過哪些路由器。使用鏈路狀態算法的路由協議有NLSP，OSPF和IS-IS。　
　　
　　　　鏈路狀態算法使用LSP（鏈路狀態數據包，Link-State Packets），網絡拓撲數據庫，SPF路徑選擇算法，SPF樹，最終計算出從該路由器到其他目標網絡的最短路徑，這些路徑就構成了路由表。在算法中，需要給每個路由器一個唯一的名字或標識。
　　
　　1、鏈路狀態網絡發現機制　　該機制用于創建整個網絡的一幅全景圖，所有的路由器都保存該圖的一個副本，從而保持一致。其具體工作步驟如下：
　　
　　（1）每個路由器都必須知道它的鄰居是誰，這一點需要相鄰的路由器之間互相通知。
　　
　　（2）每個路由器都將LSP（鏈路狀態數據包）發送給網絡上其他的路由器，LSP的內容包括該路由器通過哪些網絡與哪些路由器直接連接，以及相應連接的傳輸代價。以圖4中所示的網絡為例，路由器B向外發送的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）接下來，根據網絡的拓撲結構數據庫來判定目標網絡是否可到達及其最短路徑（常用算法為Dijikstra算法）。
　　
　　（5）路由器將第4步計算出的到這些目標網絡的最短路徑及其所使用的該路由器的網絡端口添加到路由表中。
　　
　　（6）鏈路狀態算法要求各路由器的網絡拓撲結構數據庫要一致。因此當鏈路狀態發生變化時，最先檢測到這一變化的路由器需要將變化的情況發送給其他的路由器。每當路由器收到新的LSP，它都會重新計算最短路徑并更新路由表，這樣才能保證各路由器在網絡拓撲結構方面重新達成一致。
　　
　　2、考慮的因素
　　
　　在采用鏈路狀態算法時，應當考慮以下兩方面的因素：
　　
　　路由器的存儲空間和處理能力
　　
　　　　由于采用鏈路狀態算法時路由器不但要保存來自其他路由器的LSP，而且還要保存網絡的拓撲結構和路由表，所以其存儲空間一定要大。另外，根據SPF樹計算最短路徑的算法較為復雜，因此要求路由器的處理能力要強。
　　
　　帶寬
　　
　　　　在建立SPF樹的最初階段，有大量的LSP需要通過網絡進行傳輸，因此對網絡帶寬的要求較高。假如帶寬不夠，不僅影響路由器收斂的速度，而且會影響正常的數據傳輸。
　　
　　3、可能出現的問題及解決辦法
　　
　　　　與距離向量算法類似的是，鏈路狀態算法同樣必須保證所有的路由器能夠收到所有必需的LSP。圖6給出了一個可能發生問題的案例。假設路由器C首先檢測到C和D之間的Network 1發生故障，那么象前面說的那樣，路由器C將把該故障情況以LSP的方式發送給網絡上的其他路由器B、D、和A（為了講述方便，稱該LSP為LSP1）。假設Network 1很快地就恢復了正常，而且路由器D先檢測到，那么路由器D將把Network 1恢復正常的情況以LSP的形式再發送給路由器A、C和B（稱之為LSP2）。假如由于某種原因（比如不同網絡的傳輸速度不同或傳輸路徑長度不同等），LSP2先于LSP1到達路由器A。這時，問題就出現了，路由器A究竟應該把哪一個LSP作為反映最終情況的LSP呢？
　　　

　　　　也許大家會說這里的巧合也太多了吧！其實不然，在實際的應用中，網絡的拓撲結構要復雜的多，而且各方面因素的影響也很多，比如：路由器啟動順序的先后將影響到LSP發送的順序，大型網絡中不同子網的網絡傳輸速度也可能有較大差別等等。
　　
　　鏈路狀態算法可以采用以下幾種技術來解決這些潛在問題:
　　
　　延長LSP的發送周期。
　　
　　以多點發送LSP（Multicast）代替廣播發送LSP（Broadcast）。
　　
　　在由多個LAN互連組成的網絡中，可以指定一個或多個路由器用于存放各路由器發送的LSP，其他的路由器通過這些指定路由器獲得一致的拓撲數據。
　　
　　在大型網絡中，可以設定一個由不同區域組成的層次結構。某一級區域中的路由器不必存儲和處理來自不同區域路由器的LSP。　　
　　
　　　　使用LSP時間戳、順序號等手段來解決LSP發送過程中的順序問題。
　　
　　(三)兩種算法的比較
　　
　　上述兩種算法的差別基本上可以歸結為下表中的四點,可以以此作為具體應用中選擇路由協議的技術依據。
　　