分組交換路由選擇路由選擇算法

路由選擇方法的精確描述，屬于網(wǎng)路軟件的一部分。對(duì)它的要求是正確、簡(jiǎn)單、可靠、穩(wěn)定、公平和優(yōu)化。

路由選擇算法可分為自適應(yīng)型和非自適應(yīng)型兩大類。自適應(yīng)型的特點(diǎn)在于它的路由選擇能在一定程度上隨網(wǎng)路運(yùn)行狀態(tài)（如流量和拓?fù)洌┒淖?，可避開出現(xiàn)異態(tài)的節(jié)點(diǎn)或鏈路。非自適應(yīng)型采用靜態(tài)路由選擇算法。常見的非自適應(yīng)型有擴(kuò)散式、隨機(jī)式、固定式等；而自適應(yīng)型有集中式、孤立式、分布式等。

固定式是一種應(yīng)用范圍比較廣的非自適應(yīng)型路由選擇算法。它是根據(jù)網(wǎng)路拓?fù)浜托畔⒘髁康慕y(tǒng)計(jì)模型事先確定各節(jié)點(diǎn)的路由表，每個(gè)節(jié)點(diǎn)的路由表指明從該節(jié)點(diǎn)出發(fā)到某個(gè)目的節(jié)點(diǎn)所應(yīng)該選擇的輸出鏈路以及下一節(jié)點(diǎn)。路由表由算法確定，而在固定式中是事先預(yù)定的。

最短路徑算法為最常用的算法，它尋求在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間能沿著長(zhǎng)度最短的路徑來傳送分組。這里所指的“長(zhǎng)度”賦于特別含義，既可以是實(shí)際距離，也可以是平均時(shí)延或者鏈路費(fèi)用。長(zhǎng)度參數(shù)是路由表的依據(jù)，如果參數(shù)值來自網(wǎng)路運(yùn)行的當(dāng)前狀態(tài)，路由表變?yōu)閯?dòng)態(tài)生成，這樣的路由選擇算法就屬于自適應(yīng)型。

Dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號(hào)方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時(shí)標(biāo)號(hào)的方式。注意該算法要求圖中不存在負(fù)權(quán)邊。

首先，引進(jìn)一個(gè)輔助向量D，它的每個(gè)分量D[i]表示當(dāng)前所找到的從始點(diǎn)v到每個(gè)終點(diǎn)vi的的長(zhǎng)度：如D[3]=2表示從始點(diǎn)v到終點(diǎn)3的路徑相對(duì)最小長(zhǎng)度為2。這里強(qiáng)調(diào)相對(duì)就是說在算法過程中D的值是在不斷逼近最終結(jié)果但在過程中不一定就等于長(zhǎng)度。它的初始狀態(tài)為：若從v到vi有弧，則D為弧上的權(quán)值；否則置D為∞。顯然，長(zhǎng)度為 D[j]=Min{D | vi∈V} 的路徑就是從v出發(fā)的長(zhǎng)度最短的一條。此路徑為(v,vj)。 那么，下一條長(zhǎng)度次短的是哪一條呢？假設(shè)該次短路徑的終點(diǎn)是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長(zhǎng)度或者是從v到vk的弧上的權(quán)值，或者是D[j]和從vj到vk的弧上的權(quán)值之和。 一般情況下，假設(shè)S為已求得的終點(diǎn)的集合，則可證明：下一條最短路徑（設(shè)其終點(diǎn)為X）或者是弧(v,x)，或者是中間只經(jīng)過S中的頂點(diǎn)而最后到達(dá)頂點(diǎn)X的路徑。因此，下一條長(zhǎng)度次短的的長(zhǎng)度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的權(quán)值，或者是D[k](vk∈S)和弧(vk,vi)上的權(quán)值之和。

算法描述如下：

1）arcs表示弧上的權(quán)值。若不存在，則置arcs為∞。S為已找到從v出發(fā)的的終點(diǎn)的集合，初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點(diǎn)vi可能達(dá)到的度的初值為D=arcs[Locate Vex(G,v),i] vi∈V

2）選擇vj，使得D[j]=Min{D | vi∈V-S} 3）修改從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長(zhǎng)度。

分組交換路由選擇，是分組交換網(wǎng)內(nèi)任一節(jié)點(diǎn)（源節(jié)點(diǎn)或中繼節(jié)點(diǎn)）在接收到一個(gè)分組后，確定一條后繼路徑傳送該分組到目的接點(diǎn)的一個(gè)決策過程。路由選擇是影響網(wǎng)路性能的重要因素之一，因?yàn)樗苯記Q定分組通過網(wǎng)路所經(jīng)歷的平均時(shí)延。

路由選擇的操作過程與分組交換網(wǎng)所提供的業(yè)務(wù)類型有關(guān)。如提供數(shù)據(jù)報(bào)業(yè)務(wù)，對(duì)每收到的一個(gè)分組都作一次路由選擇，同一個(gè)源節(jié)點(diǎn)連續(xù)發(fā)出的多個(gè)分組可能經(jīng)過不同的路由而到達(dá)同一目的節(jié)點(diǎn)；當(dāng)提供虛電路業(yè)務(wù)時(shí)，通常只在建立虛電路時(shí)才進(jìn)行路由選擇，一旦虛電路建立后，在用戶會(huì)話期間對(duì)所有報(bào)文分組均沿著同一路由進(jìn)行傳送。比較起來，虛電路業(yè)務(wù)的路由選擇頻度較低。

各國(guó)公用分組交換網(wǎng)大多采用自適應(yīng)型算法。法國(guó)的TRANSPAC網(wǎng)包含數(shù)十個(gè)節(jié)點(diǎn)，路由選擇采取集中式自適應(yīng)型為主兼有孤立式特點(diǎn)，基于最短路徑算法，以鏈路長(zhǎng)度定義為鏈路通信容量與緩沖存儲(chǔ)器隊(duì)列長(zhǎng)度的函數(shù)。每個(gè)節(jié)點(diǎn)通過測(cè)量和估算，求得各條輸出鏈路的長(zhǎng)度；網(wǎng)內(nèi)設(shè)一集中式網(wǎng)路管理中心，負(fù)責(zé)收集來自各節(jié)點(diǎn)的網(wǎng)路狀態(tài)信息，并計(jì)算出任何兩節(jié)點(diǎn)之間的最短路徑及其長(zhǎng)度。美國(guó)ARPA網(wǎng)采用基于最短路徑算法的分布與集中相結(jié)合的自適應(yīng)實(shí)現(xiàn)方式，每一節(jié)點(diǎn)每隔10秒鐘更新一次與它相連接的各條鏈路的時(shí)延值，同時(shí)每一節(jié)點(diǎn)收到其他節(jié)點(diǎn)送來的鏈路時(shí)延更新值后，就重新計(jì)算其路由表。

所謂交換指當(dāng)一臺(tái)主機(jī)向另一臺(tái)主機(jī)發(fā)送數(shù)據(jù)包時(shí)，源主機(jī)通過某種方式獲取路由器地址后，通過目的主機(jī)的協(xié)議地址（網(wǎng)絡(luò)層）將數(shù)據(jù)包發(fā)送到指定的路由器物理地址（介質(zhì)訪問控制層）的過程。

通過使用交換算法檢查數(shù)據(jù)包的目的協(xié)議地址，路由器可確定其是否知道如何轉(zhuǎn)發(fā)數(shù)據(jù)包。如果路由器不知道如何將數(shù)據(jù)包轉(zhuǎn)發(fā)到下一個(gè)節(jié)點(diǎn)，將丟棄該數(shù)據(jù)包；如果路由器知道如何轉(zhuǎn)發(fā)，就把物理目的地址變換成下一個(gè)節(jié)點(diǎn)的地址，然后轉(zhuǎn)發(fā)該數(shù)據(jù)包。在傳輸過程中，其物理地址發(fā)生變化，但協(xié)議地址總是保持不變。

路由選擇就是構(gòu)建網(wǎng)絡(luò)節(jié)點(diǎn)路由表的過程，無(wú)論哪種分組網(wǎng)絡(luò)，路由選擇都是由網(wǎng)絡(luò)提供的基本功能，但咋X.25建議中對(duì)路由選擇并未作出明確規(guī)定，對(duì)不同的分組網(wǎng)允許有不同的路由選擇算法，如何確立路由選擇算法的好壞呢？分組的路由選擇的基本原則如下：算法簡(jiǎn)單，易于實(shí)現(xiàn)，以減少額外開銷；算法對(duì)所有用戶都是公平的；應(yīng)選擇性能最佳的傳輸路徑，使得端到端時(shí)延盡量小，個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)工作量均衡，最大限度提高網(wǎng)絡(luò)資源利用率；網(wǎng)絡(luò)出現(xiàn)故障時(shí)，在網(wǎng)絡(luò)拓?fù)涓淖兊那闆r下，算法仍能正常工作，自動(dòng)選擇迂回路由。

不同的分組交換網(wǎng)有可能采取不同的路由選擇。路由選擇可分為動(dòng)態(tài)法和靜態(tài)法兩類。

路由選擇器靜態(tài)法

(1)擴(kuò)散式路由法，分組從原始節(jié)點(diǎn)發(fā)往與之相鄰的節(jié)點(diǎn)，接受該分組的節(jié)點(diǎn)檢查它是否收到過該分組，如果已經(jīng)收到過，則將它拋棄；如果未收到，只要該分組的目的節(jié)點(diǎn)不是該節(jié)點(diǎn)，就將此分組對(duì)相鄰節(jié)點(diǎn)進(jìn)行廣播，最終該分組必將到達(dá)目的節(jié)點(diǎn)。其中，最早到達(dá)目的節(jié)點(diǎn)的分組所經(jīng)歷的過程必定是一條最佳路徑。采用擴(kuò)散式路由法，路由選擇與網(wǎng)絡(luò)拓?fù)錈o(wú)關(guān)，即使網(wǎng)絡(luò)嚴(yán)重故障。只要有一條通路存在，分組也能到達(dá)終點(diǎn)，因此分組的傳輸?shù)目煽啃院芨摺５秉c(diǎn)是分組的無(wú)效傳輸量很大，網(wǎng)絡(luò)的額外開銷也大，網(wǎng)絡(luò)中業(yè)務(wù)量的增加會(huì)導(dǎo)致排隊(duì)時(shí)延的加大。

(2)固定路由表法，在每個(gè)節(jié)點(diǎn)交換機(jī)中設(shè)置一個(gè)包含路由目的節(jié)點(diǎn)地址和對(duì)應(yīng)輸出邏輯信道號(hào)的路由表，他指明從該節(jié)點(diǎn)到網(wǎng)絡(luò)中的任何終點(diǎn)應(yīng)當(dāng)選擇的路徑。呼叫請(qǐng)求分組根據(jù)分組的目的地址查找該路由表，這樣可以獲得各轉(zhuǎn)接節(jié)點(diǎn)的輸出邏輯信號(hào)，從而形成一條端到端的虛電路。為防止網(wǎng)絡(luò)故障或通路阻塞，路由表中可以規(guī)定主用路由和備用路由。

路由選擇器動(dòng)態(tài)法

(1)自適應(yīng)路由選擇網(wǎng)，自適應(yīng)路由選擇法是指路由選擇根據(jù)網(wǎng)絡(luò)情況的變化而變化。路由是由若干段鏈路串接而成的，自適應(yīng)路由選擇法是用迭代法逐段選取虛鏈路，從而形成一條端到端的虛電路。但在這種算法中，要求各節(jié)點(diǎn)存有全網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)，而且每條鏈路的變化信息必須廣播給網(wǎng)絡(luò)所有的節(jié)點(diǎn)。自適應(yīng)路由選擇算法對(duì)減少網(wǎng)絡(luò)時(shí)延、平滑網(wǎng)絡(luò)負(fù)載、防止網(wǎng)絡(luò)阻塞是有利的，但是路由表的頻繁更換可能引起網(wǎng)絡(luò)的不穩(wěn)定，產(chǎn)生分組循環(huán)或者使分組在一對(duì)節(jié)點(diǎn)之間來回穿梭，自適應(yīng)路由選擇算法是X.25分組網(wǎng)中應(yīng)用最為普遍的一種選路方式。

(2)集中式路由交換，網(wǎng)管中心負(fù)責(zé)全網(wǎng)狀態(tài)信息的采集、路由計(jì)算以及路由表的下載。在分組交換網(wǎng)中，交換機(jī)之間一般有多條路由可選擇。如何獲得一條較好的路由，除了要有一個(gè)通過網(wǎng)絡(luò)的平均時(shí)延較短和平衡網(wǎng)內(nèi)業(yè)務(wù)量能力較強(qiáng)的路由算法外，同時(shí)還要考慮網(wǎng)內(nèi)資源的利用和網(wǎng)絡(luò)結(jié)構(gòu)的適應(yīng)能力。 2100433B

路由選擇包括兩個(gè)基本操作，即最佳路徑的判定和網(wǎng)間信息包的傳送（交換）。兩者之間，路徑的判定相對(duì)復(fù)雜。