|
|
|
4-7 鏈路狀態繞路法
4-7-1 鏈路狀態繞路簡介 『鏈路狀態路徑選擇』（Link-State Routing，LS Routing）是屬於動態演算法。路由器必須隨時依照最新消息計算出路由路徑，也隨時更新路由表。它是一種『半集中式』（Quasi-centralized）的路徑選擇演算法（Routing algorithm）。首先每一個路由器必須定期測量它和鄰近路由器之間的費用，這費用可能和佇列延遲、頻寬等因素有關，不同通訊協定都有各自的定義。這費用又稱為『鏈路費用』（Link Cost）。當每一路由器測出相鄰之間的費用後，定期廣播給其他『所有』路由器，該廣播的訊息又稱為『鏈路狀態』（Link State）訊息。同樣的，任何一部路由器也會接收到其他路由器廣播的鏈路狀態，再依照這些訊息計算出到達其他路由器的最短路徑，並建構路由表。路由表上註明欲往哪一個路由器的下一個路由器位置（如圖 4-8 所示）。因此在LS Routing演算法下每一個路由器建立路由表的步驟如下： (1) 利用 Hello 封包查詢相鄰路由器 (2) 計算鏈路費用 (3) 建立鏈路狀態封包並廣播給所有路由器 (4) 計算出最短路徑及更新路由表 以下分別說明各步驟的處理程序： 4-7-2 利用 Hello 封包查詢相鄰路由器 當路由器啟動後，立即發送 Hello 封包（Hello Request）給所有相鄰路由器（或定期發送）。當其它路由器收到 Hello 封包後，必須立即回覆該 Hello 封包（Hello Response），並告知路由器名稱。如圖 4-10 所示，路由器 A 發送 Hello 查詢封包（H_Re）給相鄰路由器（B、C、D），相鄰路由器也回應 Hello 封包（H_Rp）給它。路由器因為這樣而知道有哪些路由器和它相鄰。 圖 4-10 發送 Hello 封包查詢及回應 4-7-3 計算鏈路費用 發送 Hello 之路由器，由相鄰路由器的回應 Hello 封包，而得知它們之間的路徑費用。再由這些訊息計算出到達相鄰路由器之間的鏈路費用。依照各種通訊協定的需求，針對路徑費用的定義也不盡相同，可能採用傳輸延遲、佇列延遲、或頻寬容量等等因素，但最容易取得的是傳輸延遲。當路由器發送查詢 Hello 封包（H_Re）後，到它收到某一路徑回應（H_Rp）的時間，計算之間差異，再取一半的值（除以 2），這就是該路徑的傳輸延遲時間，一般都以微秒（ms）為單位。在圖 4-11 之中，我們假設所有路由器都經過廣播 Hello 封包後，計算出它們之間的路徑費用（也是鏈路狀態），並假設鏈路兩端所計算費用都相同（如，A → B 和B → A）。 圖 4-11 鏈路狀態範例 4-7-4 建立鏈路狀態封包並廣播給所有路由器 由上一步驟，各路由器已得知相鄰路由器之間的狀態值（如圖 4-11），並各自建立鏈路狀態封包，如圖 4-12 所示。 圖 4-12 鏈路狀態封包範例 各路由器再將它的鏈路狀態封包廣播給網路上『所有』路由器。同樣的，每一部路由器也收到所有其他路由器的鏈路狀態封包，再由這些訊息計算出欲往某一路由器的最佳路徑，也建立了路由表。既然任何一部路由器都可由網路收到所有鏈路狀態，並算出自己的路由表，因此我們稱之為『半集中式』的路徑選擇法。 針對廣播鏈路狀態封包可能造成廣播風暴（Broadcast Storm）的問題，其類似熱馬鈴薯方法發送。每一個路由器收到封包後，便往其他路徑複製轉送，才可以將封包廣播到所有路由器上。因此，我們必須在封包上編有封包序號和時間戳記（Time-stamp）。當封包進入路由器後檢查該封包是否來過，如果來過便將其拋棄不再轉送。還有時間戳記是用來更新封包序號紀錄，決定是否可以刪除。 4-7-5 計算出最短路徑及更新路由表 當每一路由器收到其他所有路由器的鏈路狀態封包，必須計算出它到達任何一部路由器的最佳路徑。在圖形理論中，有許多尋找最短路徑的演算法，較被常用的是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
N = {A} For all nodes v If v adjacent to A Then D(v) = c(A, v) Else D(v) = ∞
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 我們用圖 4-11為範例，每一路由器所收到的鏈路狀態封包如圖 4-12 所示。又以路由器 A 為例，尋找最短路徑的步驟如圖 4-13 所示。所有路由器演算法演算後所建立的路由表如圖 4-14 所示。 圖 4-11 以路由器 A 為範例之演算過程
圖 4-12 所有路由器之路由表（以圖 4-11 為例） 4-7-6 鏈路狀態的異常狀態 鏈路狀態之路徑選擇方法雖然簡單，但會有下列異常狀態： (1) 廣播風暴（Broadcast Storm）：網路上每一個路由器必須隨時計算相鄰之間的鏈路費用，並廣播給網路上所有的路由器。如果每次廣播的時間間隔太長，則網路上任何變更將無法即時反映給所有路由器，會造成連結上困難；但廣播間隔時間太短容易造成廣播風暴。而且為了廣播路徑狀態給所有路由器也會佔用不少頻寬。 (2) 報喜不報憂：對每個路由器都是主動廣播它所計算的鏈路狀態。任何路由器啟動時都會按時發送鏈路狀態。但當中某一路由器發生故障，它便失去廣播狀態之能力；其它路由器要能偵測出這一條鏈路是故障的，這可能要經過一段不短的時間，在這期間內也容易造成連結上的錯誤。 當然，上列的異常狀況有許多方法來克服，還不至於太困難。但一般來說，任何一個路由器要將它的鏈路狀況廣播給網路上所有路由器，在較大的網路上使用也太不夠經濟，何況，網路上路由器愈多，所佔用的頻寬也就愈大。
|
翻轉工作室：粘添壽
電腦網路與連結技術：
翻轉電子書系列：
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
