路徑選擇

在進行通信網網絡設計和規劃時，經常會遇到這樣的問題，路徑的選擇和網絡的方案可以有很多種，但是如何在保證所有站點都可靠地連通的前提下，選擇費用最小的網絡結構，這裏就有一個路徑優化問題。

路由算法根據許多信息來填充路由表。目的/下一跳地址對告知路由器到達該目的最佳方式是把分組發送給代表“下一跳”的路由器，當路由器收到一個分組，它就檢查其目標地址，嘗試將此地址與其“下一跳”相聯繫。路由表還可以包括其它信息。路由表比較metric以確定最佳路徑，這些metric根據所用的路由算法而不同，下面將介紹常見的metric。路由器彼此通信，通過交換路由信息維護其路由表，路由更新信息通常包含全部或部分路由表，通過分析來自其它路由器的路由更新信息，該路由器可以建立網絡拓撲細圖。路由器間發送的另一個信息例子是鏈接狀態廣播信息，它通知其它路由器發送者的鏈接狀態，鏈接信息用於建立完整的拓撲圖，使路由器可以確定最佳路徑。

給定連通圖G=(V，X)，w(x)是定義在X上的非負函數，稱w(x)是x的權。設T=(V，X_T)是G的一個支撐樹，定義樹的權為

最小支撐樹就是w(T)為最小的一顆支撐樹。權值可以是距離、費用，或根據各種因素綜合評定後得出的數據。

下面介紹兩種最小支撐樹的算法。

（1）算法一

在賦權圖G中任取一個迴路，然後去掉這個迴路中權最大的邊，如此繼續進行，直到G中不再有迴路為止。這時剩下的邊組成的子圖就是最小支撐樹。此法最適合於圖上操作，當圖較大時，可以幾個人同時在各子圖上工作，比較實用，方便。

（2）算法二

這是Kruskal在1956提出的最小支撐樹的算法，又稱Kruskal法，具體步驟如下：設圖G有n個點。

① 把賦權圖G的各條邊按權的遞增順序排列，如表01所示。

② 取最小權值的邊作樹枝。

③ 重複第2步，如果與已選邊不形成迴路，作為新的樹枝，否則刪去。

④ 至選出n－1條邊結束。

圖1給出了圖G及根據算法二求出的最小費用網絡拓撲圖。

圖1 算法二示例

表1的各邊按權遞增排列

在通信網的網絡結構確定以後，選擇最佳路由（用圖論的術語就是選擇點間最短路徑），便要提到日程上來。選擇最佳路由的方法很多，應用也很廣。

下面介紹一種在數據通信網中常用的最佳路由的選擇方法。以圖2中的節點v₆為例。

圖2 最佳路由算法

（1）從v₆點出發，畫出指向各鄰近節點v₁，v₇，v₅的箭頭，並在節點處，記下它們的權數。

（2）然後，從這3個鄰近節點v₁，v₇，v₅出發，向各相鄰的節點畫出箭頭，如從v₇向v₃畫箭頭，v₃節點處標上的權數，應是(v₆,v₇)和(v₇,v₃)之權數之和6。如到達某一節點的箭頭有2個或2個以上，則選取最小的一個。

（3）直至找到從v₆出發到達所有其他的節點為止。圖2.32(b)給出了從v₆到所有其他節點的最短路徑。

可以用同樣的步驟找出節點v₁,v₂,…等通向其餘各節點的最短路徑，編制出最小權數路由表。

在通信網中除了要求最佳路由之外，還須計算迂迴路由，以便在通信網某兩點間出現故障後發生擁塞時使用。

迂迴路由的算法是在計算出的最佳路由上，去掉某一條或幾條邊，然後在剩下的圖中求最佳路徑，所得即為迂迴路由，依次可求出第二，第三迂迴路由。圖3中分別給出了去掉(v₆,v₁)，以及同時去掉(v₂,v₇)、(v₆,v₁)的迂迴路由。

圖3 迂迴路由