通信工程師交換技術(shù)非自適應(yīng)路由選擇

 　在線輔導(dǎo)　面授招生　考試大綱　指定教材　報名時間

5.3.2 非自適應(yīng)路由選擇
1.固定路由法
這種方法是在每個節(jié)點(diǎn)上保持一張路由表，表上標(biāo)明去每一個‘目的節(jié)點(diǎn)的分組應(yīng)從哪條鏈路進(jìn)行轉(zhuǎn)發(fā)。這些表是在整個系統(tǒng)進(jìn)行配置時生成的，并且在此后的一段相當(dāng)時間內(nèi)保持固定不變。當(dāng)網(wǎng)絡(luò)拓?fù)涔潭ú蛔儾⑶彝ㄐ帕髁恳蚕鄬Ψ€(wěn)定時，采用固定路由法是適當(dāng)?shù)摹?br />那么如何制作這樣的路由表呢？常用的方法是將網(wǎng)絡(luò)內(nèi)任何兩個節(jié)點(diǎn)之間的最短路徑事先計算好，然后根據(jù)這些最短路徑制成路由表，存放在各個節(jié)點(diǎn)中。每一個分組都可在所到達(dá)的節(jié)點(diǎn)中查找到下一步應(yīng)轉(zhuǎn)發(fā)到哪一個節(jié)點(diǎn)（即下一節(jié)點(diǎn)或后繼節(jié)點(diǎn)）?？梢娺@種路由選擇策略的關(guān)鍵就是要算出給定網(wǎng)絡(luò)中任意兩個節(jié)點(diǎn)之間的最短路徑。
下面介紹一種常用的求最短路徑的算法，這是由Dijkstra提出的，也叫Dijkstra算法。已知條件是整個網(wǎng)絡(luò)的拓?fù)浜透麈溌返拈L度。
需要指出，若將已知的各鏈路長度改為鏈路的代價或時延，這就相當(dāng)于求任意兩節(jié)點(diǎn)之間具有最小代價或最小時延的路徑。因此，求最短路徑的路由算法具有普遍的應(yīng)用價值。

下面以圖5-17所示的網(wǎng)絡(luò)為例來討論這種算法，即尋找從源節(jié)點(diǎn)到網(wǎng)絡(luò)中其他各節(jié)點(diǎn)的最短路徑。為方便起見，設(shè)源節(jié)點(diǎn)為節(jié)點(diǎn)1。然后一步一步地尋找，每次找一個節(jié)點(diǎn)到源節(jié)點(diǎn)的最短路徑，直到把所有的節(jié)點(diǎn)都找到為止。

令D(V)為源節(jié)點(diǎn)（節(jié)點(diǎn)1)到節(jié)點(diǎn)v的距離，它就是沿某一路徑的所有鏈路的長度之和。再令j(i，j)為節(jié)點(diǎn)i至節(jié)點(diǎn)j之間的距離。整個算法有以下步驟。

圖5-18給出了Dijkatra算法迭代求解步驟的詳細(xì)圖解。可以看出，上述的步驟②共執(zhí)行了5次。第一次迭代找出節(jié)點(diǎn)1通過鏈路（1,4)到達(dá)節(jié)點(diǎn)4的距離最小，如圖5-18(c)所示。第二次迭代找出下一個最近的節(jié)點(diǎn)是5,如圖5-18(d)所示。第三次迭代找出下一個最近節(jié)點(diǎn)3,如圖5-18(e)所示。第四次迭代找出下一個最近節(jié)點(diǎn)2，如圖5-18(f)所示。最后一次迭代找出最后一個最近節(jié)點(diǎn)6,如圖5-18(g)所示。至此，所有節(jié)點(diǎn)都包含到網(wǎng)絡(luò)節(jié)點(diǎn)集合況中，計算過程即告結(jié)束。最后就得出以節(jié)點(diǎn)1為根的最短路徑樹，如圖18(g)所示，于是很容易生成如圖5-18(b)所示的節(jié)點(diǎn)1的路由表。從最短路徑樹可淸楚地看出從源節(jié)點(diǎn)（節(jié)點(diǎn)1)到網(wǎng)內(nèi)任何一個節(jié)點(diǎn)的最短通路。此路由表指出對于發(fā)往某個目的節(jié)點(diǎn)的分組，從節(jié)點(diǎn)1發(fā)出后的下一節(jié)點(diǎn)應(yīng)當(dāng)是賽個節(jié)點(diǎn)。當(dāng)然，像這樣的路由表,在所有其他各節(jié)點(diǎn)中都應(yīng)當(dāng)有一個。但這就需要分別以這些節(jié)點(diǎn)為源節(jié)點(diǎn)，重新執(zhí)行算法,然后才能找出對應(yīng)的最短路徑樹以及相應(yīng)的路由表。

返回目錄： 通信專業(yè)交換技術(shù)考試培訓(xùn)分組交換匯總

編輯推薦：

通信專業(yè)實務(wù)考試終端與業(yè)務(wù)教程匯總

通信專業(yè)實務(wù)考試設(shè)備與環(huán)境教程匯總

通信工程師考試培訓(xùn)交換理論基確匯總