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

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

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

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

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

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

編輯推薦：

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

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

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