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

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

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

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

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

編輯推薦：

通信專業實務考試終端與業務教程匯總

通信專業實務考試設備與環境教程匯總

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