通信工程師交換技術非自適應路由選擇

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

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

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

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

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

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

編輯推薦：

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

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

通信工程師考試培訓交換理論基確匯總