Dynamic routing 動態繞路簡介

網路規劃與管理技術：第七章路由規劃與設定上一頁 下一頁

7-4 動態繞路簡介

內容：

7-4-1 鏈路狀態繞路法

7-4-2 距離向量繞路法

所謂『動態繞路』(Dynamic Routing)？即是『網路上各個路由器隨時互相傳遞網路最新狀態，每個路由器收到相鄰之間路由器的訊息，再依照這些資料建立路由表。』由此可見，動態路由表會隨時依照網路狀態變化中。

在網路大環境隨時變動情況下，使用靜態路由選擇非常不方便，必須針對網路情況，隨時修改路由表。動態路徑選擇會依照網路情況隨時修正路由表，當網路上有任何更動，動態路由選擇器會隨時更新資料，而計算出下一個路徑應該是哪一個路由器的效率最高。雖然動態路由選擇能隨時提供最佳路徑，但為了維持這個功能，必須隨時在網路上收集最新資訊，也是會浪費不少頻寬。

目前較常用的路徑選擇技術有下列兩種：

● 鏈路狀態繞路法（Link-State Routing, LS Routing）

● 距離向量繞路法（Distance Vector Routing, DV routing）

以下分別介紹之。

7-4-1 鏈路狀態繞路法

『鏈路狀態繞路』（Link-State Routing，LS Routing）是屬於動態演算法。路由器必須隨時依照最新消息計算出路由路徑，也隨時更新路由表。它是一種『半集中式』（Quasi-centralized）的路徑選擇演譯法（Routing algorithm）。首先每一個路由器必須定期測量它和鄰近路由器之間的費用，這費用可能和佇列延遲、頻寬等因素有關，不同通訊協定都有各自的定義。這費用又稱為『鏈路費用』（Link Cost）。當每一路由器測出相鄰之間的費用後，定期廣播給其他『所有』路由器，該廣播的訊息又稱為『鏈路狀態』（Link State）訊息。同樣的，任何一部路由器也會接收到其他路由器廣播的鏈路狀態，再依照這些訊息計算出到達其他路由器的最短路徑，並建構路由表。路由表上註明欲往哪一個路由器的下一個路由器位置（如圖 7-6 所示）。因此在LS Routing演譯法下每一個路由器建立路由表的步驟如下：

(A) 利用 Hello 封包查詢相鄰路由器

當路由器啟動後，立即發送 Hello 封包（Hello Request）給所有相鄰路由器（或定期發送）。當其它路由器收到 Hello 封包後，也必須立即回覆 Hello 封包（Hello Response），並告知路由器名稱。如圖 7-6 所示，路由器 A 發送 Hello 查詢封包（H_Re）給相鄰路由器（B、C、D），相鄰路由器也回應 Hello 封包（H_Rp）給它。路由器也因這樣而知道有哪些路由器和它相鄰。

圖 7-6 發送 Hello 封包查詢及回應

(B) 計算鏈路費用

發送 Hello 之路由器，由相鄰路由器的回應 Hello 封包，而得知它們之間的路徑費用。再由這些訊息計算出到達相鄰路由器之間的鏈路費用。依照各種通訊協定的需求，針對路徑費用的定義也不盡相同，可能採用傳輸延遲、佇列延遲、或頻寬容量等等因素，但最容易取得的是傳輸延遲。當路由器發送查詢 Hello 封包（H_Re）後，到它收到某一路徑回應（H_Rp）的時間，計算之間差異，再取一半的值（除以 2），這就是該路徑的傳輸延遲時間，一般都以毫秒（ms）為單位。在圖 7-7 之中，我們假設所有路由器都經過廣播 Hello 封包後，計算出它們之間的路徑費用（也是鏈路狀態），並假設鏈路兩端所計算費用都相同（如，A → B 和B → A）。

圖 7-7 鏈路狀態範例

(C) 建立鏈路狀態並廣播給所有路由器

由上一步驟，各路由器已得知相鄰路由器之間的狀態值（如圖 7-6），並各自建立鏈路狀態封包，如圖 7-8 所示。

圖 7-8 鏈路狀態封包範例

各路由器再將它的鏈路狀態封包廣播給網路上『所有』路由器。同樣的，每一部路由器也收到所有其他路由器的鏈路狀態封包，再由這些訊息計算出欲往某一路由器的最佳路徑，也建立了路由表。既然任何一部路由器都可由網路收到所有鏈路狀態，並算出自己的路由表，因此我們稱之為『半集中式』的路徑選擇法。

針對廣播鏈路狀態封包可能造成廣播風暴（Broadcast Storm）的問題，其類似熱馬鈴薯方法發送。每一個路由器收到封包後，便往其他路徑複製轉送，才可以將封包廣播到所有路由器上。因此，我們必須在封包上編有封包序號和時間戳記（Time-stamp）。當封包進入路由器後檢查該封包是否來過，如果來過便將其拋棄不再轉送。還有時間戳記是用來更新封包序號紀錄，決定是否可以刪除。

(D) 計算出最短路徑及更新路由表

當每一路由器收到其他所有路由器的鏈路狀態封包，必須計算出它到達任何一部路由器的最佳路徑。在圖形理論中，有許多尋找最短路徑的演算法，其中較被常用的是Dijkstra’s shortest path algorithm。(請參考 TCP/IP 協定與 Internet 網路)

7-4-2 距離向量繞路法

『距離向量繞路法』（Distance Vector Routing，DV Routing）是一種動態的分散式路徑選擇演算法。由此演算法所實現的通訊協定之下的路由器，它們的路由表是由鄰近相鄰路由器之中共同建立而成，因此稱之為『分散式』。網路上每一個路由器都必須維護一個二維的『向量表』（Vector Table），向量表格內紀錄本身路由器到每一個路由器的已知的最佳距離。路由器定期和鄰近路由器交換向量表（並不廣播給所有路由器）來建立路由表。當路由器接收到鄰近傳來的向量表時再修正本身的向量表，向量表的內容就一直修正再傳送，整個網路狀況也就能漸漸地傳遞到每一個路由器上。隨著時間路由器上之路由表的資料漸漸完備，也漸漸能找出最佳路徑。向量表只傳送給相鄰的路由器，對網路的頻寬也佔用較少，也不會造成廣播風暴。

對於向量表中各個欄位，如果使用路由器之間距離的數值，稱之為『距離向量』（Distance Vector）。表示兩個路由器之間相距幾個路由器，向量表又稱為『距離表』（Distance Table）。但目前使用之DV routing並不只估計相鄰之間的距離，我們會將各個路由器之間的佇列延遲、頻寬和網路壅塞情況來計算成為相鄰之間的『距離費用』（Distance Cost）。假設路由器已知它相鄰路由器之『距離』，如果距離費用是封包跳躍次數，則其值剛好為 1；如果距離費用為佇列長度，則路由器僅需計算每個佇列；如果距離費用是延遲時間，則路由器可利用一個特殊的 Echo 封包要求鄰近路由器回應，再計算要求和回應之間時間的差距，再取它的一半值就是延遲時間。歸納如下：

(1) 每各路由器都須維護一只『距離向量表』，並依此表建立『路由表』。

(2) 將『路由表』傳遞給相鄰路由器。

(3) 路由器收到『路由表』後，結合原有『距離向量表』成為新的『距離向量表』，再建立新的『路由表』，並傳遞給下一個路由器。

(4) 依此類推，路由器定期將路由表傳遞給相鄰路由表。

我們以圖 7-9 為範例來說明路由器之間距離向量的傳遞，和路由表建立的過程。在圖中兩個端點（如，A、B）之間的標示值（如，6），為該兩端點之間的距離費用，其值的來由也許經過：跳躍次數、延遲時間等等因素所計算出來的。並假設距離向量傳遞路徑為：A → B → C → D → E。當距離向量進入某一路由器後，便和本身的路由表搜尋出所有可能到達的路徑，再由新建立的路由表之中尋找出最短路徑。緊接著，又將該最短路徑的路由表傳遞給下一個路由器。一直到最後，觀察路由器 E 的路由表的變化結果，便可瞭解距離向量演算法的運作情形。

圖 7-9 距離向量演算法範例

圖 7-10 (a) ~ (e) 為各個路由器的起始距離向量表，並假設所有路由器都未和其他路由器交換訊息。針對每一個向量表，我們記錄了：從該路由器到其他路由器所經由不同相鄰路由器的費用。例如DE(A, B)是從 E 到 A 經由 B 的費用。其他空白部份表示沒有訊息，也可說是路徑費用無限大（∞）。

圖 7-10 (a) ~ (c) 路由器的起始路由表

圖 7-11 (d)、(e) 路由器的起始路由表

向量表傳遞後，路由器依照進入的向量表和本身路由表，建構新的路由表，其步驟如下：

(1) 路由器（如 B）首先登錄自己和進入向量表的路由器（如 A）之間的費用（DB(A, A) = 6）。

(2) 再搜尋向量表（如圖 7-9-1 (a)）中可能到達的端點（其值不是 ∞），兩個路徑費用的合如小於表中內所紀錄的值，便取代它。

(3) 搜尋索有路徑後，建立新的路由表，再由新的路由向量表找出最短路徑，再將其傳遞給下一個路由器。

我們以圖 7-9 為例子，來推演距離向量演算法建構新路由表的過程，而距離傳遞方向假設只有單一路徑，其方向為： A → B → C → D → E。我們以下列步驟來觀察推演的過程：

(A) 路由器 A 建構起始路由表

路由器 A 沒有收到其他路由器的向量表，依照自己向鄰近路由器查詢之距離費用（如 6-10 (a)）建構出路由表。如圖 7-12 所示，其中最短路徑是由距離向量表中，查出每列的向量值最低者，並將其建立成路由表。如圖中，它可經由 B 到達 B 的費用是 6（DA(B, B)）為該列最小值；又 DA(E, E) = 1 也是該列最小值。路由器 A 建構路由表後，再將該路由表傳遞給 B（A → B），緊接著下一步驟。

圖 7-12 路由器 A 自行建構路由表

(B) 路由器 A 傳送給路由器 B（A → B）

路由器 A 將路由表（圖 7-12）傳遞給路由器 B，B 起始距離向量表如圖 6-10 (b)，再利用這兩個向量表建立出新的距離向量表。首先，B 由路由表中查出它自己經由 A 到 A 的費用（DB(A, A) = 6）。再由 A 的向量表中查詢可能到達的端點（B、E），得知可經由 A 到達 E（DA(E, E) = 1）。則將兩個端點路徑費用的和（DB(A, A) + DA(E, E) = 7）填入經由 A 到 E 的欄位內。再由表中的每一列的最小值，找到最短路徑（如第四列），建構出路由表如圖 7-13 所示。並將路由表傳遞給 C（B → C），接下一步驟。