TCP/IP 協定與 Internet 網路：第六章 IP Routing 協定  上一頁           下一頁

翻轉工作室：粘添壽

6-4 Link-Static Routing

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

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

(2) 計算鏈路費用

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

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

以下分別說明各步驟的處理程序：

6-4-1 利用 Hello 封包查詢相鄰路由器

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

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

6-4-2 計算鏈路費用

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

圖 6-4 鏈路狀態範例

6-4-3 建立鏈路狀態並廣播給所有路由器

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

圖 6-5 鏈路狀態封包範例

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

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

6-4-4 計算出最短路徑及更新路由表

當每一路由器收到其他所有路由器的鏈路狀態封包，必須計算出它到達任何一部路由器的最佳路徑。在圖形理論中，有許多尋找最短路徑的演算法，其中較被常用的是Dijkstra’s shortest path algorithm。其演譯法如下

## Dijkstra’s shortest path algorithm

Define:

N: set of all nodes such that shortest path from source to these nodes is known. N initially is empty.

D(v): cost of known least cost path from source to node v.

c(i, j): cost of link i to j, c(i, j)=∞ if i, j not directly connected.

p(v): previous node (neighbor of v) along shortest path from source to v.

Algorithm:

source node: A

iterative: after k steps know shortest path to nearest k neighbors

(1) Initialization:

N = {A}

For all nodes v

If v adjacent to A

             Then D(v) = c(A, v)

Else D(v) = ∞

(2) Loop

find w not in N such that D(w) is smallest

add w into N

update D(v) for all not in N:

        D(v) = min(D(v), D(w)+c(w, v))

Until all nodes in N

## end of algorithm

我們用圖 6-4 為範例，每一路由器所收到的鏈路狀態封包如圖 6-5 所示。又以路由器 A 為例，尋找最短路徑的步驟如圖 6-6 所示。所有路由器演譯法演算後所建立的路由表如表 6-2 所示。

圖 6-6 以路由器 A 為範例之演算過程

表 6-2 所有路由器之路由表（以圖 6-4 為例）

6-4-5 鏈路狀態的異常狀態

鏈路狀態之路徑選擇方法雖然簡單，但會有下列異常狀態：

● 廣播風暴（Broadcast Storm）：網路上每一個路由器必須隨時計算相鄰之間的鏈路費用，廣播給網路上所有的路由器。如果每次廣播的時間間隔太長，則網路上任何變更將無法即時反映給所有路由器，會造成連結上困難。但廣播間隔時間太短容易造成廣播風暴。而且為了廣播路徑狀態給所有路由器也會佔用不少頻寬。

● 報喜不報憂：對每個路由器都是主動廣播它所計算的鏈路狀態。任何路由器啟動時都會按時發送鏈路狀態。但當中某一路由器發生故障，它便失去廣播狀態之能力。其它路由器要能偵測出這一條鏈路是故障的，這可能要經過一段不短的時間，在這期間內也容易造成連結上的錯誤。

當然，上列的異常狀況有許多方法來克服，還不至於太困難。但一般來說，任何一個路由器要將它的鏈路狀況廣播給網路上所有路由器，在較大的網路上使用也太不夠經濟，網路上路由器愈多佔用的頻寬也就愈大。

<GOTOP>