metric是路由算法用以確定到達目的地的最佳路徑的計量標準，如路徑長度。為了幫助選路，路由算法初始化並維護包含路徑信息的路由表，路徑信息根據使用的路由算法不同而不同。
基本介紹
- 中文名：路徑選擇
- 外文名：The path selection
- 所屬技術：電信技術
1．最小支撐樹,2．最佳路由(點間最短路徑),3．迂迴路由算法,
在進行通信網網路設計和規劃時，經常會遇到這樣的問題，路徑的選擇和網路的方案可以有很多種，但是如何在保證所有站點都可靠地連通的前提下，選擇費用最小的網路結構，這裡就有一個路徑最佳化問題。
路由算法根據許多信息來填充路由表。目的/下一跳地址對告知路由器到達該目的最佳方式是把分組傳送給代表“下一跳”的路由器，當路由器收到一個分組，它就檢查其目標地址，嘗試將此地址與其“下一跳”相聯繫。路由表還可以包括其它信息。路由表比較metric以確定最佳路徑，這些metric根據所用的路由算法而不同，下面將介紹常見的metric。路由器彼此通信，通過交換路由信息維護其路由表，路由更新信息通常包含全部或部分路由表，通過分析來自其它路由器的路由更新信息，該路由器可以建立網路拓撲細圖。路由器間傳送的另一個信息例子是連結狀態廣播信息，它通知其它路由器傳送者的連結狀態，連結信息用於建立完整的拓撲圖，使路由器可以確定最佳路徑。
1．最小支撐樹
給定連通圖G=(V，X)，w(x)是定義在X上的非負函式，稱w(x)是x的權。設T=(V，XT)是G的一個支撐樹，定義樹的權為
最小支撐樹就是w(T)為最小的一顆支撐樹。權值可以是距離、費用，或根據各種因素綜合評定後得出的數據。
下面介紹兩種最小支撐樹的算法。
（1）算法一
在賦權圖G中任取一個迴路，然後去掉這個迴路中權最大的邊，如此繼續進行，直到G中不再有迴路為止。這時剩下的邊組成的子圖就是最小支撐樹。此法最適合於圖上操作，當圖較大時，可以幾個人同時在各子圖上工作，比較實用，方便。
（2）算法二
這是Kruskal在1956提出的最小支撐樹的算法，又稱Kruskal法，具體步驟如下：設圖G有n個點。
① 把賦權圖G的各條邊按權的遞增順序排列，如表01所示。
② 取最小權值的邊作樹枝。
③ 重複第2步，如果與已選邊不形成迴路，作為新的樹枝，否則刪去。
④ 至選出n－1條邊結束。
圖1給出了圖G及根據算法二求出的最小費用網路拓撲圖。
圖1 算法二示例
表1的各邊按權遞增排列
順序 | 邊 | 權值 | 順序 | 邊 | 權值 |
1 | (v1,v3) | 1 | 6 | (v6,v5) | 4 |
2 | (v1,v5) | 2 | 7 | (v4,v5) | 5 |
3 | (v4,v6) | 2.6 | 8 | (v2,v3) | 6 |
4 | (v1,v6) | 3 | 9 | (v1,v2) | 7 |
5 | (v6,v3) | 3.2 |
2．最佳路由(點間最短路徑)
在通信網的網路結構確定以後，選擇最佳路由（用圖論的術語就是選擇點間最短路徑），便要提到日程上來。選擇最佳路由的方法很多，套用也很廣。
下面介紹一種在數據通信網中常用的最佳路由的選擇方法。以圖2中的節點v6為例。
圖2 最佳路由算法
（1）從v6點出發，畫出指向各鄰近節點v1，v7，v5的箭頭，並在節點處，記下它們的權數。
（2）然後，從這3個鄰近節點v1，v7，v5出發，向各相鄰的節點畫出箭頭，如從v7向v3畫箭頭，v3節點處標上的權數，應是(v6,v7)和(v7,v3)之權數之和6。如到達某一節點的箭頭有2個或2個以上，則選取最小的一個。
（3）直至找到從v6出發到達所有其他的節點為止。圖2.32(b)給出了從v6到所有其他節點的最短路徑。
可以用同樣的步驟找出節點v1,v2,…等通向其餘各節點的最短路徑，編制出最小權數路由表。
3．迂迴路由算法
在通信網中除了要求最佳路由之外，還須計算迂迴路由，以便在通信網某兩點間出現故障後發生擁塞時使用。
迂迴路由的算法是在計算出的最佳路由上，去掉某一條或幾條邊，然後在剩下的圖中求最佳路徑，所得即為迂迴路由，依次可求出第二，第三迂迴路由。圖3中分別給出了去掉(v6,v1)，以及同時去掉(v2,v7)、(v6,v1)的迂迴路由。
圖3 迂迴路由
