通信工程師傳輸與接入考試路由選擇方法

7.3.2  路由選擇方法
1．確定型算法
1) 擴(kuò)散式路由選擇
擴(kuò)散式路由選擇又稱為洪泛法(Flooding)，是歐洲RAND公司提出的軍用分組交換網(wǎng)采用的路由選擇方法。其基本思想是，當(dāng)節(jié)點(diǎn)機(jī)收到一個(gè)分組后，只要該分組的目的節(jié)點(diǎn)不是本節(jié)點(diǎn)，就將此分組轉(zhuǎn)發(fā)到全部(或部分)鄰接節(jié)點(diǎn)。擴(kuò)散式分為完全擴(kuò)散和選擇擴(kuò)散兩種。
完全擴(kuò)散式除了輸入分組的那條鏈路之外，向所有輸出鏈路同時(shí)發(fā)送分組。而選擇擴(kuò)散則是向著分組的目的地方向選擇幾條鏈路發(fā)送分組。最終該分組必會(huì)到達(dá)目的節(jié)點(diǎn)，而且最早到達(dá)的分組歷經(jīng)的必定是一條最佳路由，由其他路徑陸續(xù)到達(dá)的同一分組將被目的節(jié)點(diǎn)丟棄。為了避免分組在網(wǎng)絡(luò)中傳送時(shí)發(fā)生環(huán)路，任何中間節(jié)點(diǎn)發(fā)現(xiàn)同一分組第二次進(jìn)入時(shí)，即予以丟棄。
洪泛法十分簡(jiǎn)單，不需要路由表，且不論網(wǎng)絡(luò)發(fā)生什么故障，它總能自動(dòng)找到一條路由到達(dá)目的地，可靠性很高。但它會(huì)造成網(wǎng)絡(luò)中無(wú)效負(fù)荷的劇增，導(dǎo)致網(wǎng)絡(luò)擁塞。因此這種方法一般只用在可靠性要求特別高的軍事網(wǎng)絡(luò)中。
2) 隨機(jī)路由選擇
在這種方法中，當(dāng)節(jié)點(diǎn)收到一個(gè)分組后，除了輸入分組的那條鏈路之外，按照一定的概率從其他鏈路中選擇某一鏈路發(fā)送分組。選擇第i條鏈路的概率Pi如下：
隨機(jī)式路由選擇同洪泛法一樣，不需要使用網(wǎng)絡(luò)路由信息，并且在網(wǎng)絡(luò)故障時(shí)，分組也能到達(dá)目的地，網(wǎng)絡(luò)具有良好的健壯性。同時(shí)，路由選擇是根據(jù)鏈路的容量進(jìn)行的，這有利于通信量的平衡。但這種方法的缺點(diǎn)是顯然的，所選的路由一般并不是最優(yōu)的，因此網(wǎng)絡(luò)必須承擔(dān)的通信量負(fù)荷要高于最佳的通信量負(fù)荷。
3) 固定路由表算法
這是靜態(tài)路由法中最常用的一種。其思想是：在每個(gè)節(jié)點(diǎn)上事先設(shè)置一張路由表，表中給出了該節(jié)點(diǎn)到達(dá)各終點(diǎn)的路由的下一個(gè)節(jié)點(diǎn)。當(dāng)分組到達(dá)該節(jié)點(diǎn)并需要轉(zhuǎn)發(fā)時(shí)，即可按它的目的地查路由表，將分組轉(zhuǎn)發(fā)至下一節(jié)點(diǎn)，下一節(jié)點(diǎn)再繼續(xù)進(jìn)行查表、選路、轉(zhuǎn)發(fā)，直到將分組轉(zhuǎn)發(fā)至終點(diǎn)。在這種方式中，路由表是在整個(gè)系統(tǒng)進(jìn)行配置時(shí)生成的，并且在此后的一段時(shí)間內(nèi)保持不變。
這種算法簡(jiǎn)單，當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)固定不變并且業(yè)務(wù)量也相對(duì)穩(wěn)定時(shí)，采用此法比較好。但它不能適應(yīng)網(wǎng)絡(luò)的變化，一旦被選路由出現(xiàn)故障，就會(huì)影響信息正常傳送。
固定路由表算法的一種改進(jìn)方法是在表中提供一些預(yù)備的鏈路和節(jié)點(diǎn)，即給每個(gè)節(jié)點(diǎn)提供到各目的節(jié)點(diǎn)的可替代的下一個(gè)節(jié)點(diǎn)。這樣，當(dāng)鏈路或節(jié)點(diǎn)故障時(shí)，可選擇替代路由來(lái)進(jìn)行數(shù)據(jù)傳輸。
下面給出固定路由表算法的例子。圖7.18(c)為網(wǎng)絡(luò)結(jié)構(gòu)，表7.4為網(wǎng)絡(luò)控制中心計(jì)算得到的全網(wǎng)的路由表。該表列出了所有節(jié)點(diǎn)到各個(gè)目的節(jié)點(diǎn)所確定的發(fā)送路由。實(shí)際上，對(duì)于每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)僅需存儲(chǔ)其中相應(yīng)的一列即可。圖7.18(a)、(b)分別為節(jié)點(diǎn)1和節(jié)點(diǎn)4的路由表。

我們來(lái)看具體的路由選擇過(guò)程。如圖7.18(c)所示，假設(shè)源節(jié)點(diǎn)為1號(hào)節(jié)點(diǎn)，終節(jié)點(diǎn)為6號(hào)節(jié)點(diǎn)。
1號(hào)節(jié)點(diǎn)機(jī)收到DTE A 的呼叫請(qǐng)求時(shí)，判斷出被叫終端與6號(hào)節(jié)點(diǎn)機(jī)相連，故選路的目的地為6號(hào)節(jié)點(diǎn)機(jī)。1號(hào)節(jié)點(diǎn)查詢自己的路由表，即圖7.18(a)，得知1號(hào)到6號(hào)的下一節(jié)點(diǎn)(轉(zhuǎn)接節(jié)點(diǎn))是4號(hào)節(jié)點(diǎn)，故將呼叫請(qǐng)求轉(zhuǎn)發(fā)至4號(hào)節(jié)點(diǎn)。4號(hào)節(jié)點(diǎn)再進(jìn)行選路，查詢路由表，即圖7.18(b)，得到6號(hào)的路由為直達(dá)路由，因此直接轉(zhuǎn)發(fā)至6號(hào)節(jié)點(diǎn)，由6號(hào)節(jié)點(diǎn)機(jī)進(jìn)行接續(xù)。

返回目錄：通信工程師傳輸與接入分組交換網(wǎng)匯總

編輯相關(guān)推薦:

通信工程師考試培訓(xùn)傳輸與接入自動(dòng)交換光網(wǎng)絡(luò)

通信工程師考試培訓(xùn)光傳輸常用儀器及測(cè)試

通信工程師考試培訓(xùn)無(wú)線通倍技術(shù)匯總