通信工程師交換技術(shù)考試鏈路狀態(tài)路由算法

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

1.鏈路狀態(tài)路由算法
ARPANET-直采用距離向董路由算法，直到1979年它才被鏈路狀態(tài)路由算法替代。兩個(gè)主要問題導(dǎo)致了距離向童路由算法的消亡。第一，采用時(shí)延（隊(duì)列長(zhǎng)度）作為距離的度量值，在選擇路由時(shí)沒有將鏈路的帶寬考慮進(jìn)去；第二，節(jié)點(diǎn)間采用定時(shí)方式交換路由信息，所以距離向量路由算法的收斂速度比較慢，甚至出現(xiàn)像水平分裂算法那樣的假象。因此，它被一種全新的鏈路狀態(tài)路由（LinkStateRouting)算法所替代。
鏈路狀態(tài)路由算法的思想十分簡(jiǎn)單，可以分五部分加以描述。每個(gè)路由器必須：
①發(fā)現(xiàn)它的鄰居節(jié)點(diǎn)，并獲取其網(wǎng)絡(luò)地址；
②測(cè)量到各鄰居節(jié)點(diǎn)的時(shí)延（或代價(jià)）；
③組裝一個(gè)分組通告它剛知道的路由信息；
④將這個(gè)分組發(fā)送給所有其他網(wǎng)絡(luò)節(jié)點(diǎn)；
⑤計(jì)算到所有其他節(jié)點(diǎn)的最短路徑。
事實(shí)上，完整的拓?fù)浣Y(jié)構(gòu)和所有的鏈路時(shí)延都通過試驗(yàn)測(cè)量獲得，并發(fā)布到網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)。于是各個(gè)節(jié)點(diǎn)可以用Dijkstra算法來找出它到所有其他節(jié)點(diǎn)的最短路徑。下面，我們將更詳盡地討論上述五個(gè)步驟。
①發(fā)現(xiàn)鄰居節(jié)點(diǎn)
當(dāng)一個(gè)節(jié)點(diǎn)被激活以后，它的第一個(gè)任務(wù)就是要知道誰是它的鄰居，這是通過向每條點(diǎn)到點(diǎn)鏈路發(fā)送特殊的Hello分組來實(shí)現(xiàn)的。在另一端的節(jié)點(diǎn)應(yīng)發(fā)回一個(gè)應(yīng)答分組，以說明它是誰。所有網(wǎng)絡(luò)節(jié)點(diǎn)的名字必須是全局。
當(dāng)兩個(gè)或多個(gè)節(jié)點(diǎn)通過一個(gè)局域網(wǎng)（LAN)連接起來時(shí)，情況就稍為復(fù)雜一些。如圖24(a)所示，一個(gè)LAN將3個(gè)節(jié)點(diǎn)A,C和F直接連接起來。每個(gè)節(jié)點(diǎn)又與其他的節(jié)點(diǎn)相連。
可以想象用一個(gè)節(jié)點(diǎn)代表LAN。如圖5-24(b)所示，引人了一個(gè)新的虛擬節(jié)點(diǎn)N，與A,C和F相連。從A經(jīng)LAN到C的路徑在這里表示為路徑ANC。

如果是重復(fù)的，則丟棄它。如果一個(gè)分組的順序號(hào)比目前已到達(dá)的最大的順序號(hào)還小，則被認(rèn)為是過時(shí)信息而加以廢棄。在分組擴(kuò)散過程中，壽命字段每單位時(shí)間遞減一次，如果壽命為0,則刪除該分組，以保證沒有任何分組可以在網(wǎng)絡(luò)中無限長(zhǎng)地存活下去。
為了防止節(jié)點(diǎn)之間的鏈路出故障引起問題，規(guī)定所有的鏈路狀態(tài)分組都需要應(yīng)答。由于鏈路狀態(tài)分組以洪泛方式擴(kuò)散，這就要求毎個(gè)節(jié)點(diǎn)對(duì)接收到的鏈路狀態(tài)分組能夠自行確定需要向哪些鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)、需要對(duì)哪些鄰節(jié)點(diǎn)進(jìn)行應(yīng)答，所以每個(gè)節(jié)點(diǎn)需要構(gòu)造一個(gè)如圖5-26所示的分組處理數(shù)據(jù)結(jié)構(gòu)。該圍是圖5-25(a)所示子網(wǎng)中節(jié)點(diǎn)B所用的數(shù)據(jù)結(jié)構(gòu)，每一行對(duì)應(yīng)于一個(gè)新近到達(dá)，但尚未完全處理完畢的鏈路狀態(tài)分組。數(shù)據(jù)結(jié)構(gòu)表記錄了分組來自何處、它的順序號(hào)和壽命以及描述鏈路狀態(tài)的數(shù)據(jù)。另外，對(duì)應(yīng)于B的每條輸出鏈路（到A,C和F)各有一組發(fā)送標(biāo)志位和應(yīng)答標(biāo)志位。發(fā)送標(biāo)志位表示該鏈路狀態(tài)分組必須發(fā)送給哪些鄰節(jié)點(diǎn)，應(yīng)答標(biāo)志位表示應(yīng)給哪些鄰節(jié)點(diǎn)發(fā)送應(yīng)答消息。
在圖5-26中，如標(biāo)志位所示，從A來的鏈路狀態(tài)分組直接到達(dá)B,它必須被送往C和F,并且向A發(fā)應(yīng)答。類似地，從F來的分組必須轉(zhuǎn)發(fā)給A和C，并向F發(fā)應(yīng)答。但是，當(dāng)?shù)谌齻€(gè)來自節(jié)點(diǎn)E的分組到達(dá)時(shí)就有所不同。由于該分組已經(jīng)到達(dá)兩次，一次經(jīng)過EAB,-次經(jīng)過EFB。因此，它只需發(fā)往C,但要向A和F發(fā)應(yīng)答，如標(biāo)志位所示。如果在原始分組還在緩沖器中處理時(shí)就到達(dá)一個(gè)它的副本，標(biāo)志位就得進(jìn)行一下修改。例如，在表中的第四個(gè)來自C節(jié)點(diǎn)的分組被轉(zhuǎn)發(fā)之前，又有一個(gè)C的狀態(tài)信息分組的副本從F到達(dá)，那么六個(gè)標(biāo)志位就應(yīng)改為100011，表示不必再轉(zhuǎn)發(fā)給FT,而應(yīng)向F發(fā)應(yīng)答。

⑤計(jì)算新路由
每個(gè)節(jié)點(diǎn)獲得所有的鏈路狀態(tài)分組后，便可以構(gòu)造整個(gè)網(wǎng)絡(luò)拓?fù)鋱D，每一鏈路的兩個(gè)方向都將標(biāo)出時(shí)延（或代價(jià)）值。此時(shí)每個(gè)節(jié)點(diǎn)就可以在本地運(yùn)行Dijkstra算法，從而確定到達(dá)所有目的節(jié)點(diǎn)的最短路徑（或最小代價(jià)路徑），并形成分組轉(zhuǎn)發(fā)路由表。
鏈路狀態(tài)路由算法在實(shí)際網(wǎng)絡(luò)中得到了廣泛的應(yīng)用，如在Intemet中應(yīng)用廣泛的OSPF協(xié)議使用的就是該算法。另一個(gè)使用該算法的重要協(xié)議是IS-IS(IntermediateSystem-IntermediateSystem)協(xié)議，該協(xié)議應(yīng)用于多種Intemet骨干網(wǎng)（包括老的NSFNET骨干網(wǎng)）和一些數(shù)字蜂窩系統(tǒng)中。

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

編輯推薦：

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

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

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