動態路由算法的性能研究

[摘 要] 本文在分析靜態和動態路由算法的基礎上，重點研究了動態路由算法中的鏈路狀態路由，提出了鏈路狀態路由中路由選擇的一種更簡潔方法。Dijkstra路由選擇算法適合于計算一個路由器到其他各個路由器的最短路徑。但在計算機網絡中更多的是點對點的連接，Floyd路由選擇算法更適合計算兩個路由器之間的最短距離，在計算機網絡中更實用。

[關鍵詞] 路由算法 迪杰斯特拉 弗洛伊德

一、動態路由算法

由于靜態路由算法不考慮網絡的當前負載情況，目前計算機網絡通常使用動態的路由算法。通常的動態路由算法有兩種：距離矢量路由算法和鏈路狀態路由算法。

1.距離矢量路由算法

在這種算法中每個路由器維護一張表，它以子網中的每個路由器為索引，并且每一個路由器對應一個表項，表中列出了當前已知的到每個目標的最佳距離，以及所使用的線路。所使用的距離度量單位可以是跳數或者時間延遲或沿著路徑排隊的分組數目等。通過在鄰居之間相互交換信息，路由器不斷地更新它們內部的表。

在距離矢量路由算法中有一個很嚴重的缺陷：雖然這種算法總能得到正確的答案，但是它收斂得到正確答案的速度非常慢。原因是在這種算法中，同一個網絡中相鄰的兩臺路由器之間不知道是相鄰的。這樣就造成了在網絡斷開的時候，所有的路由器之間的交換次數會趨于無窮大的數值。問題的核心在于當X路由器告訴Y路由器它有一條路徑的時候，Y無從知道它自己是否就在這條路徑上。

2.鏈路狀態路由算法

由于距離矢量路由算法中存在著兩個問題：距離矢量路由算法需要很長時間才能收斂到穩定狀態（無窮計算的問題）；選擇路徑的時候并沒有考慮線路帶寬。由于這些原因距離矢量路由算法被一個全新的算法所替代，該算法稱為鏈路狀態路由。每一個路由器必須完成的工作是：

（1)發現它的鄰居節點，并知道其網絡地址：發現鄰居節點需要在每一條點到點線路上發送一個特殊的HELLO分組，線路另一端送回一個應答來說明它是誰。（2)測量到各鄰居節點的延遲或者開銷：用一個發送出去的ECHO到接收到ECHO分組的時間除以2，就可以得到一個合理的延遲估計值。（3)構造一個分組，分組中包含所有它剛剛知道的信息：每一個路由器創建一個由發送方標識序列號和年齡及一個鄰居列表組成的分組。（4)將這個分組發送到所有其他的路由器：使用擴散法來發布鏈路狀態分組。（5)計算出到每一個其他路由器的最短路徑：在路由器得到了全部的鏈路狀態分組之后，就可以構造出完整的子網圖，在每一臺路由器上運行Dijkstra算法，以便計算出到所有可能目標的最短路徑。

二、路由算法的改進

由于動態的路由算法把計算機網絡鏈路上的負載和流量考慮在內，所以與靜態的路由算法相比適應性更強，應用范圍也更廣。而兩種動態路由算法的區別就在于能否發現相鄰的路由器，距離矢量路由算法中不能準確判斷鄰居節點造成了無窮計算問題，而鏈路狀態路由算法中用一個特殊的HELLO分組可以做到這一點。

1.Dijkstra路由選擇算法

下圖中用ABCDE代表計算機網絡中的路由器，每個路由器都連接到一個或者多個其他的路由器 上。用一個源路由器到其他路由器的最短路徑來說明這種算法的思想。

假設路由器A到各路由器的距離如下面的所示的鄰接矩陣（其中的距離可以是時間延遲或者跳數）∞代表兩個路由器之間的距離不存在。運用Dijkstra算法可以依次找到從A到各路由器的最短路徑是依路徑長度遞增的序列。

從A到各路由頂點運行Dijkstra算法的過程如下表2：S為已經求得的最短路徑的集合然后在每個路由頂點運行一遍Dijkstra算法就會得到各個路由器到其他路由器的最短路徑。

2.Floyd路由選擇算法

在計算機網絡中更常用的是兩個路由器之間的點對點的連接。一個解決辦法是在一個有n個頂點的網絡中每次以一個頂點為源點，重復執行Dijkstra算法n次，就可以求得每一對頂點之間的最短路徑。總的執行時間的時間復雜度為O（n3）。雖然時間復雜度相同但用Floyd算法要比Dijkstra算法形式更簡單。

三個路由器的距離如下表3所示：

其中A、B、C的三個路由器的序號分別是0、1、2；D [i][j]代表從Vi 到Vj的中間頂點的序號不大于k的最短路徑的長度。

則運用Floyd算法有如下表4的計算過程：

表中P代表路徑，D(0) 表示從初始狀態加入了路由器A，D(1) 表示加入了路由器B，D(2)

表示加入了路由器C

最終的各頂點路由器之間的最短路徑和路徑長度依次為：

A——C： ABC6

A——B： BCA5

B——C： CAB7

參考文獻：

[1]計算機安全學．(美)Matt Bishop.電子工業出版社

[2]潘愛民:計算機網絡.清華大學出版社