分組交換路由選擇（routing in packet switching），是分組交換網內任一節點（源節點或中繼節點）在接收到一個分組後，確定一條後繼路徑傳送該分組到目的接點的一個決策過程。
基本介紹
- 中文名：分組交換路由選擇
- 外文名：routing in packet switching
- 套用學科：計算機、通信
簡介,路由選擇算法,典型的實現方式,
簡介
分組交換路由選擇，是分組交換網內任一節點（源節點或中繼節點）在接收到一個分組後，確定一條後繼路徑傳送該分組到目的接點的一個決策過程。路由選擇是影響網路性能的重要因素之一，因為它直接決定分組通過網路所經歷的平均時延。
路由選擇的操作過程與分組交換網所提供的業務類型有關。如提供數據報業務，對每收到的一個分組都作一次路由選擇，同一個源節點連續發出的多個分組可能經過不同的路由而到達同一目的節點；當提供虛電路業務時，通常只在建立虛電路時才進行路由選擇，一旦虛電路建立後，在用戶會話期間對所有報文分組均沿著同一路由進行傳送。比較起來，虛電路業務的路由選擇頻度較低。
路由選擇算法
路由選擇方法的精確描述，屬於網路軟體的一部分。對它的要求是正確、簡單、可靠、穩定、公平和最佳化。
路由選擇算法可分為自適應型和非自適應型兩大類。自適應型的特點在於它的路由選擇能在一定程度上隨網路運行狀態（如流量和拓撲）而改變，可避開出現異態的節點或鏈路。非自適應型採用靜態路由選擇算法。常見的非自適應型有擴散式、隨機式、固定式等；而自適應型有集中式、孤立式、分散式等。
固定式是一種套用範圍比較廣的非自適應型路由選擇算法。它是根據網路拓撲和信息流量的統計模型事先確定各節點的路由表，每個節點的路由表指明從該節點出發到某個目的節點所應該選擇的輸出鏈路以及下一節點。路由表由算法確定，而在固定式中是事先預定的。
最短路徑算法為最常用的算法，它尋求在源節點和目的節點之間能沿著長度最短的路徑來傳送分組。這裡所指的“長度”賦於特別含義，既可以是實際距離，也可以是平均時延或者鏈路費用。長度參數是路由表的依據，如果參數值來自網路運行的當前狀態，路由表變為動態生成，這樣的路由選擇算法就屬於自適應型。
Dijkstra(迪傑斯特拉)算法是典型的最短路徑路由算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這裡均採用永久和臨時標號的方式。注意該算法要求圖中不存在負權邊。
首先，引進一個輔助向量D，它的每個分量D[i]表示當前所找到的從始點v到每個終點vi的的長度：如D[3]=2表示從始點v到終點3的路徑相對最小長度為2。這裡強調相對就是說在算法過程中D的值是在不斷逼近最終結果但在過程中不一定就等於長度。它的初始狀態為：若從v到vi有弧，則D為弧上的權值；否則置D為∞。顯然，長度為 D[j]=Min{D | vi∈V} 的路徑就是從v出發的長度最短的一條。此路徑為(v,vj)。 那么，下一條長度次短的是哪一條呢？假設該次短路徑的終點是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權值，或者是D[j]和從vj到vk的弧上的權值之和。 一般情況下，假設S為已求得的終點的集合，則可證明：下一條最短路徑（設其終點為X）或者是弧(v,x)，或者是中間只經過S中的頂點而最後到達頂點X的路徑。因此，下一條長度次短的的長度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的權值，或者是D[k](vk∈S)和弧(vk,vi)上的權值之和。
算法描述如下：
1）arcs表示弧上的權值。若不存在，則置arcs為∞。S為已找到從v出發的的終點的集合，初始狀態為空集。那么，從v出發到圖上其餘各頂點vi可能達到的度的初值為D=arcs[Locate Vex(G,v),i] vi∈V
2）選擇vj，使得D[j]=Min{D | vi∈V-S} 3）修改從v出發到集合V-S上任一頂點vk可達的最短路徑長度。
典型的實現方式
各國公用分組交換網大多採用自適應型算法。法國的TRANSPAC網包含數十個節點，路由選擇採取集中式自適應型為主兼有孤立式特點，基於最短路徑算法，以鏈路長度定義為鏈路通信容量與緩衝存儲器佇列長度的函式。每個節點通過測量和估算，求得各條輸出鏈路的長度；網內設一集中式網路管理中心，負責收集來自各節點的網路狀態信息，並計算出任何兩節點之間的最短路徑及其長度。美國ARPA網採用基於最短路徑算法的分布與集中相結合的自適應實現方式，每一節點每隔10秒鐘更新一次與它相連線的各條鏈路的時延值，同時每一節點收到其他節點送來的鏈路時延更新值後，就重新計算其路由表。
