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

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

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

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

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

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

編輯推薦：

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

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

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