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

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

一、動態(tài)路由算法

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

1.距離矢量路由算法

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

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

2.鏈路狀態(tài)路由算法

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

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

二、路由算法的改進

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

1.Dijkstra路由選擇算法

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

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

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

2.Floyd路由選擇算法

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

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

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

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

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

表示加入了路由器C

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

A——C： ABC6

A——B： BCA5

B——C： CAB7

參考文獻：

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

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