鏈路狀態路由算法

鏈路狀態算法的思想是要求網絡中所有參與鏈路狀態路由協議的路由器都掌握網絡的全部拓撲結構信息，並記錄在路由數據庫中。鏈路狀態算法中路由數據庫實質上是一個網絡結構的拓撲圖，該拓撲圖由一個節點的集合和一個邊的集合構成。在網絡拓撲圖中，結點代表網絡中路由器，邊代表路由器之間的物理鏈路。在網絡拓撲結構圖中，每一條鏈路上可以附加不同的屬性，例如鏈路的狀態、距離或費用等。如果每一個路由器所保存的網絡拓撲結構圖都是一致的，那麼個路由器生成的路由表也是最佳的，不存在錯誤路由或循環路由。 ^[1] 

鏈路狀態選路算法的工作原理如下 ^[2] 

（1）在參與鏈路狀態選路的路由器集合中，每個路由器都需要通過某種機制來了解自己所連接的鏈路及其狀態。

（2）各路由器都能夠將其所連接的鏈路的狀態信息通知給網絡中的所有其他路由器，這些鏈路信息包括鏈路狀態、費用以及鏈路兩端的路由器等。

（3）鏈路狀態信息的通過鏈路狀態分組（LSP）來向整個網絡發佈。一個LSP通常包含源路由器的標識符、相鄰路由器的標識符，以及而知之間鏈路的費用。每一個LSP都將被網絡中的所有的路由器接收，並用於建立網絡整體的統一拓撲數據庫。由於網絡中所有的路由器都發送LSP，經過一段時間以後，每一個路由器都保持了一張完整的網絡拓撲圖，再在這個拓撲圖上，利用最短通路算法（例如Dijkstra算法等），路由器就可以計算出從任何源點到任何目的地的最佳通路。

這樣，每一個路由器都能夠利用通路最短的原則建立一個以本路由器為根、分支到所有其他路由器的生成樹，依據這個生成樹就可以很容易地計算出本路由器的路由表。

鏈路狀態路由算法有三個特徵：

1.向本自治系統中的所有路由器發送信息。這裏使用的方法是洪泛法（Flooding），即路由器通過所有的輸出端口向所有的相鄰路由器發送信息。而每一個路由器又將此信息發往其所有的相鄰的路由器（但不包括剛剛發來信息的那個路由器）。

2.發送的信息就是本路由器相鄰的所有路由器的鏈路狀態，但這只是路由器所知道的部分信息。所謂“鏈路狀態”就是説明本路由器和那些路由器相鄰，以及該鏈路的“度量”（Metric）。對於OSPF，鏈路狀態的“度量”主要用來表示費用、距離、時延、帶寬等。

3.只有當鏈路狀態發生改變時，路由器才用洪泛法向所有路由器發送此信息。

由於一個路由器的鏈路狀態只涉及與相鄰的路由器的聯通狀態，因而與整個互聯網的規模並無直接關係，因此鏈路狀態路由算法可以用於大型的或路由信息變化劇烈的互聯網環境。

典型的鏈路狀態路由算法是OSPF算法。

（1）與距離向量算法相比，鏈路狀態算法具有更快的收斂速度。由於LSP的發佈是面向整個網絡，使所有路由器都能夠利用LSP來迅速建立整個網絡拓撲的一個準確視圖。這可以有效防止無限技術問題的出現。其次，鏈路狀態路由算法還具有更小的網絡開銷。LSP只有在網絡拓撲發生變化時才發佈，LSP的發佈反應的是網絡的變化，而不是對整個路由數據庫的發佈和傳輸。LSP僅攜帶與本路由器直接相連的鏈路，報文長度都很小，且與互聯網中的網絡數無關，可見鏈路狀態算法更適於大規模互聯網。 ^[1] 

（2）鏈路狀態算法具有更好的功能擴展能力，很容易地在鏈路狀態中加入新的屬性和參數，而無需改變路由交換的規則，是路由計算中能夠引用不同的參數來實現新的功能。在鏈路狀態算法中，各路由器使用相同的路由數據庫來獨立計算路由，而不依賴於其他的路由器，相比距離向量具有更好的防止錯誤傳播的能力。由於LSP在傳輸過程中不會被其他路由器修改，易於調試。路由器在本地計算路由，也確保了路由算法的收斂性。

（3）路由狀態算法還提供了更好的在規模上的可升級性，鏈路狀態算法允許在一個大型網絡中劃分選路層次。例如，可以將網絡中的路由器劃分成若干組，在同一組中的路由器之間相互交換LSP，並建立一個該組統一的拓撲數據庫。為了在不同的組之間交換拓撲信息，組內的一個特殊路由器的子集首先總結出該組的拓撲數據庫，然後將這些總結性的拓撲數據庫在一個LSP鍾發送給鄰近組中的特定路由器。通過這種方式，減少網絡中路由信息交換的開銷，同時也將組內拓撲結構的變化對其他族中的路由器隱藏起來。分級的概念是在鏈路狀態路由協議（如OSPF）實現過程中的一個十分重要的概念。

每個路由器需要有較大的存儲空間，用以存儲所收到的每一個節點的鏈路狀態分組；計算工作量大，每次都必須計算最短路徑。