鏈路狀態路由協定

鏈路狀態路由選擇協定又稱為最短路徑優先協定或分散式資料庫協定，它基於Edsger Dijkstra的最短路徑優先（SPF）算法。它比距離矢量路由協定複雜得多，但基本功能和配置卻很簡單，算法易理解。鏈路狀態協定從網路或者網路的限定區域內的所有其他路由器處收集信息，最終每個鏈路狀態路由器上都有一個相同的有關網路的信息。並且每台路由器都可以獨立的計算各自的最優路徑。

基本介紹

• 中文名：鏈路狀態路由協定
• 外文名：link state routing protocol
• 別稱：最短路徑優先協定
• 基礎算法：Edsger Dijkstra
• 定義：最短路徑優先（SPF）算法

路由協定

鏈路狀態路由協定是層次式的，網路中的路由器並不向鄰居傳遞“路由項”，而是通告給鄰居一些鏈路狀態。與距離矢量路由協定相比，鏈路狀態協定對路由的計算方法有本質的差別。距離矢量協定是平面式的，所有的路由學習完全依靠鄰居，交換的是路由項。鏈路狀態協定只是通告給鄰居一些鏈路狀態。運行該路由協定的路由器不是簡單地從相鄰的路由器學習路由，而是把路由器分成區域，收集區域的所有的路由器的鏈路狀態信息，根據狀態信息生成網路拓撲結構，每一個路由器再根據拓撲結構計算出路由。

工作過程

一、了解直連網路

每台路由器了解其自身的鏈路（即與其直連的網路）。這通過檢測哪些接口處於工作狀態（包括第3層地址）來完成。

對於鏈路狀態路由協定來說，直連鏈路就是路由器上的一個接口，與距離矢量協定和靜態路由一樣，鏈路狀態路由協定也需要下列條件才能了解直連鏈路：正確配置了接口IP位址和子網掩碼並激活接口，並將接口包括在一條network語句中。

二、向鄰居傳送Hello數據包

每台路由器負責“問候”直連網路中的相鄰路由器。與EIGRP路由器相似，鏈路狀態路由器通過直連網路中的其他鏈路狀態路由器互換Hello數據包來達到此目的。

路由器使用Hello協定來發現其鏈路上的所有鄰居，形成一種鄰接關係，這裡的鄰居是指啟用了相同的鏈路狀態路由協定的其他任何路由器。這些小型Hello數據包持續在兩個鄰接的鄰居之間互換，以此實現“保持激活”功能來監控鄰居的狀態。如果路由器不再收到某鄰居的Hello數據包，則認為該鄰居已無法到達，該鄰接關係破裂。

三、建立鏈路狀態數據包

每台路由器創建一個鏈路狀態數據包（LSP），其中包含與該路由器直連的每條鏈路的狀態。這通過記錄每個鄰居的所有相關信息，包括鄰居ID、鏈路類型和頻寬來完成。一旦建立了鄰接關係，即可創建LSP，並僅向建立鄰接關係的路由器傳送LSP。LSP中包含與該鏈路相關的鏈路狀態信息、序列號、過期信息。

四、將鏈路狀態數據包泛洪給鄰居

每台路由器將LSP泛洪到所有鄰居，然後鄰居將收到的所有LSP存儲到資料庫中。接著，各個鄰居將LSP泛洪給自己的鄰居，直到區域中的所有路由器均收到那些LSP為止。每台路由器會在本地資料庫中存儲鄰居發來的LSP的副本。

路由器將其鏈路狀態信息泛洪到路由區域內的其他所有鏈路狀態路由器，它一旦收到來自鄰居的LSP，不經過中間計算，立即將這個LSP從除接收該LSP的接口以外的所有接口發出，此過程在整個路由區域內的所有路由器上形成LSP的泛洪效應。距離矢量路由協定則不同，它必須首先運行貝爾曼-福特算法來處理路由更新，然後才將它們傳送給其他路由器;而鏈路狀態路由協定則在泛洪完成後再計算SPF算法，因此達到收斂狀態的速度比距離矢量路由協定快得多。LSP在路由器初始啟動期間、或路由協定過程啟動期間、或在每次拓撲發生更改（包括鏈路接通或斷開）時、或是鄰接關係建立、破裂時傳送，並不需要定期傳送。

五、構建鏈路狀態資料庫

每台路由器使用資料庫構建一個完整的拓撲圖並計算通向每個目的網路的最佳路徑。就像擁有了地圖一樣，路由器現在擁有關於拓撲中所有目的地以及通向各個目的地的路由的詳圖。SPF算法用於構建該拓撲圖並確定通向每個網路的最佳路徑。所有的路由器將會有共同的拓撲圖或拓撲樹，但是每一個路由器獨立確定到達拓撲內每一個網路的最佳路徑。

在使用鏈路狀態泛洪過程將自身的LSP傳播出去後，每台路由器都將擁有來自整個路由區域內所有鏈路狀態路由器的LSP，都可以使用SPF算法來構建SPF樹。這些LSP存儲在鏈路狀態資料庫中。有了完整的鏈路狀態資料庫，即可使用該資料庫和最短路徑優先（SPF）算法來計算通向每個網路的首選（即最短）路徑。

協定優點

與距離矢量路由協定相比，有如下優點：

創建拓撲圖

鏈路狀態路由協定會創建拓撲圖，即SPF樹，而距離矢量路由協定沒有網路的拓撲圖，僅有一個網路列表，其中列出了通往各個網路的開銷（距離）和下一跳路由器（方向）。因為鏈路狀態路由協定會交換鏈路狀態信息，所以SPF算法可以構建網路的SPF樹，有了SPF樹，路由器可獨立確定通向每個網路的最短路徑。

快速收斂

有幾個原因使得鏈路狀態路由協定比距離矢量路由協定具有更快的收斂速度。收到一個鏈路狀態數據包（LSP）後鏈路狀態路由協定便立即將該LSP從除接收該LSP的接口以外的所有接口泛洪出去。使用距離矢量路由協定的路由器需要處理每個路由更新，並且在更新完路由表後才能將更新從路由器接口泛洪出去，即使對觸發更新也是如此。因此鏈路狀態路由協定可更快達到收斂狀態。不過EIGRP是一個明顯的例外。

事件驅動更新

在初始LSP泛洪之後，鏈路狀態路由協定僅在拓撲發生改變時才發出LSP。該LSP僅包含受影響鏈路的信息。與某些距離矢量路由協定不同的是，鏈路狀態路由協定不會定期傳送更新。

層次式設計

鏈路狀態路由協定，如OSPF和IS-IS使用了區域的概念。多個區域形成了層次化的網路結構，這有利於路由聚合（匯總），還便於將路由問題隔離在一個區域內。

協定要求

現代鏈路狀態路由協定設計旨在儘量降低對記憶體、CPU和頻寬的影響。使用並配置多個區域可減小鏈路狀態資料庫。劃分多個區域還可限制在路由域內泛洪的鏈路狀態信息的數量，並可僅將LSP傳送給所需的路由器。

記憶體要求

與距離矢量路由協定相比，鏈路狀態路由協定通常需要占用更多的記憶體、CPU處理時間和頻寬。對記憶體的要求源於鏈路狀態資料庫的使用和創建SPF樹的需要。

處理器要求

與距離矢量路由協定相比，鏈路狀態路由協定可能還需要占用更多的CPU處理時間。與Bellman-Ford等距離矢量算法相比，SPF算法需要更多的CPU處理時間，因為鏈路狀態路由協定會創建完整的拓撲圖。

頻寬要求

鏈路狀態數據包泛洪會對網路的可用頻寬產生負面影響。這應該只出現在路由器初始啟動過程中，但在不穩定的網路中也可能導致問題。

協定比較

如今，用於IP路由的鏈路狀態路由協定有兩種。

最短路徑優先（OSPF）

OSPF由IETF的OSPF工作組設計，OSPF的開發始於1987年，如今正在使用的有OSPFv2和OSPFv3兩個版本。OSPF的大部分工作由John Moy完成。

中間系統到中間系統（IS-IS）

IS-IS由ISO設計的，它的雛形由DEC開發，名為DECnet Phase V，首席設計師是Radia Perlman.

IS-IS最初是為OSI協定簇而非TCP/IP協定簇而設計的，後來，集成化IS-IS，即雙IS-IS添加了對IP網路的支持，儘管IS-IS路由協定一直主要供ISP和電信公司使用，但已有越來越多的企業開始使用IS-IS。

兩者既有很多共同點，也有很多不同之處。有很多分別擁護OSPF和IS-IS的派別，它們從未停止過對雙方優缺點的討論和爭辯。

ospf與is-is的相似之處

無類別；

使用鏈路狀態資料庫和Dijkstra算法；

用Hello分組來建立和維護毗鄰關係；

用區域來組建層次化拓撲；支持區域間路由匯總；

在多路訪問型網路中選舉指定路由器；

鏈路狀態的表示方式、時效（aging）和度量值；

更新，判斷和洪泛擴散；

收斂能力；

用與isp主幹網路；

ospf與is-is的不同之處

is-is不會選舉BDR；

當有新的路由器加入時；isis會重新選舉；

每當DR發生改變時，就會洪泛一批新的LSA；

isis路由器和全部鄰接路由器都建立毗鄰關係，而不只和DR建立；

ospf與is-is區域間的其它不同之處

ospf基於一個主幹中心，其他區域都連結在主幹上（區域邊界落在ABR之內，每一條鏈路只屬於一個區域）；

isis中區域邊界落在鏈路上（每一個isis路由器完全屬於一個第2層區域）；

ospf單個區域支持50個路由器，isis支持100個；

ospf有更多特性，包括路由標籤、完全末梢區域、NSSA、以及虛擬鏈路。

對於isis來說，區域邊界位於鏈路上，這樣可以顯著減少協定數據單元PDU(LSP)的使用，從而使一個區域中有更多的路由器。就cpu的使用效率和路由更新處理來說，isis更有效率，不僅是因為isis的鏈路狀態通告比ospf少，還因為isis添加和刪除前綴的操作比較少。isis對區域中的每台路由器只使用一個鏈路狀態分組，其中包括重發布前綴。使用默認定時器，isis比ospf更快的發現路由失效，從而收斂更快。isis中的定時器比ospf的更具可調性，所以能達到更精確的調節粒度。