鏈路狀態算法以圖論作為理論基礎，用圖來表示網路拓撲結構，並利用圖論中的最短路徑算法來計算網路間的最佳路由，因此鏈路狀態算法又被稱作最短路徑優先算法SPF。
基本介紹
- 中文名：鏈路狀態路由算法
- 外文名：Link State Routing
- 要求：結點必須有完整的網路拓撲信息
- 任務：主動測試所有鄰結點的狀態。
算法思想,算法工作原理,算法特徵,用途及算法,算法的優缺點,優點,缺點,
算法思想
鏈路狀態算法的思想是要求網路中所有參與鏈路狀態路由協定的路由器都掌握網路的全部拓撲結構信息，並記錄在路由資料庫中。鏈路狀態算法中路由資料庫實質上是一個網路結構的拓撲圖，該拓撲圖由一個節點的集合和一個邊的集合構成。在網路拓撲圖中，結點代表網路中路由器，邊代表路由器之間的物理鏈路。在網路拓撲結構圖中，每一條鏈路上可以附加不同的屬性，例如鏈路的狀態、距離或費用等。如果沒一個路由器所保存的網路拓撲結構圖都是一致的，那么個路由器生成的路由表也是最佳的，不存在錯誤路由或循環路由。
算法工作原理
鏈路狀態選路算法的工作原理如下
（1）在參與鏈路狀態選路的路由器集合中，每個路由器都需要通過某種機制來了解自己所連線的鏈路及其狀態。
（2）各路由器都能夠將其所連線的鏈路的狀態信息通知給網路中的所有其他路由器，這些鏈路信息包括鏈路狀態、費用以及鏈路兩端的路由器等。
（3）鏈路狀態信息的通過鏈路狀態分組（LSP）來向整個網路發布。一個LSP通常包含源路由器的標識符、相鄰路由器的標識符，以及而知之間鏈路的費用。每一個LSP都將被網路中的所有的路由器接收，並用於建立網路整體的統一拓撲資料庫。由於網路中所有的路由器都傳送LSP，經過一段時間以後，每一個路由器都保持了一張完整的網路拓撲圖，再在這個拓撲圖上，利用最短通路算法（例如Dijkstra算法等），路由器就可以計算出從任何源點到任何目的地的最佳通路。
這樣，每一個路由器都能夠利用通路最短的原則建立一個以本路由器為根、分支到所有其他路由器的生成樹，依據這個生成樹就可以很容易地計算出本路由器的路由表。
算法特徵
鏈路狀態路由算法有三個特徵：
1.向本自治系統中的所有路由器傳送信息。這裡使用的方法是洪泛法（Flooding），即路由器通過所有的輸出連線埠向所有的相鄰路由器傳送信息。而每一個路由器又將此信息發往其所有的相鄰的路由器（但不包括剛剛發來信息的那個路由器）。
2.傳送的信息就是本路由器相鄰的所有路由器的鏈路狀態，但這只是路由器所知道的部分信息。所謂“鏈路狀態”就是說明本路由器和那些路由器相鄰，以及該鏈路的“度量”（Metric）。對於OSPF，鏈路狀態的“度量”主要用來表示費用、距離、時延、頻寬等。
用途及算法
由於一個路由器的鏈路狀態只涉及與相鄰的路由器的聯通狀態，因而與整個網際網路的規模並無直接關係，因此鏈路狀態路由算法可以用於大型的或路由信息變化劇烈的網際網路環境。
典型的鏈路狀態路由算法是OSPF算法。
算法的優缺點
優點
（1）與距離向量算法相比，鏈路狀態算法具有更快的收斂速度。由於LSP的發布是面向整個網路，使所有路由器都能夠利用LSP來迅速建立整個網路拓撲的一個準確視圖。這可以有效防止無限技術問題的出現。其次，鏈路狀態路由算法還具有更小的網路開銷。LSP只有在網路拓撲發生變化時才發布，LSP的發布反應的是網路的變化，而不是對整個路由資料庫的發布和傳輸。LSP僅攜帶與本路由器直接相連的鏈路，報文長度都很小，且與網際網路中的網路數無關，可見鏈路狀態算法更適於大規模網際網路。
（2）鏈路狀態算法具有更好的功能擴展能力，很容易地在鏈路狀態中加入新的屬性和參數，而無需改變路由交換的規則，是路由計算中能夠引用不同的參數來實現新的功能。在鏈路狀態算法中，各路由器使用相同的路由資料庫來獨立計算路由，而不依賴於其他的路由器，相比距離向量具有更好的防止錯誤傳播的能力。由於LSP在傳輸過程中不會被其他路由器修改，易於調試。路由器在本地計算路由，也確保了路由算法的收斂性。
（3）路由狀態算法還提供了更好的在規模上的可升級性，鏈路狀態算法允許在一個大型網路中劃分選路層次。例如，可以將網路中的路由器劃分成若干組，在同一組中的路由器之間相互交換LSP，並建立一個該組統一的拓撲資料庫。為了在不同的組之間交換拓撲信息，組內的一個特殊路由器的子集首先總結出該組的拓撲資料庫，然後將這些總結性的拓撲資料庫在一個LSP鐘傳送給鄰近組中的特定路由器。通過這種方式，減少網路中路由信息交換的開銷，同時也將組內拓撲結構的變化對其他族中的路由器隱藏起來。分級的概念是在鏈路狀態路由協定（如OSPF）實現過程中的一個十分重要的概念。
缺點
每個路由器需要有較大的存儲空間，用以存儲所收到的每一個節點的鏈路狀態分組；計算工作量大，每次都必須計算最短路徑。
