路由協議與架構/鏈路狀態演算法

距離向量演算法	路由協議與架構	分層路由
	鏈路狀態演算法

鏈路狀態 (LS) 演算法基於在整個網路中分發有關路由器鄰域的資訊。每個節點都可以建立網路地圖（所有節點都一樣），從中獲得路由表。

元件

鄰居問候
鏈路狀態
泛洪演算法
Dijkstra 演算法
鄰接建立

鄰居問候

鄰居問候是相鄰節點之間定期交換的訊息，用於收集有關鄰接的資訊。每個節點

傳送鄰居問候以向其鄰居報告其存在；
接收鄰居問候以瞭解其鄰居以及到達鄰居的成本。

鄰居問候基於連續未收到鄰居問候的最大數量來實現故障檢測

快速：鄰居問候可以以高頻率傳送（例如每 2 秒一次），以在很短的時間內識別鄰接的變化
- 一旦收到，它們就不會被傳播，而是停止在第一跳→它們不會使網路飽和；
- 它們是小型資料包，因為它們不包含除生成節點之外的節點資訊；
- 它們對路由器來說開銷很低，路由器不必在收到這些資料包時重新計算其路由表；
可靠：它不依賴於“鏈路建立”訊號，在存在集線器的情況下不可用。

鏈路狀態

每個路由器都會生成一個 LS，它是一組鄰接-成本對

鄰接：生成節點的所有鄰居；
成本：生成路由器與其鄰居之間鏈路的成本。

每個節點將來自網路中所有節點的所有 LS 儲存在鏈路狀態資料庫中，然後掃描所有鄰接的列表，並透過合併節點（路由器）和邊（鏈路）來構建圖，以便構建網路地圖。

LS 生成主要基於事件：當本地拓撲（= 路由器鄰域）發生變化時，就會生成一個 LS

路由器獲得了新的鄰居；
到達鄰居的成本發生了變化；
路由器已失去與先前可達的鄰居的連線。

基於事件的生成

允許更好地利用網路：它不消耗頻寬；
它需要基於鄰居問候的“hello”元件，因為路由器不能再使用週期性生成來檢測其鄰居的故障。

此外，路由器還實現週期性生成，頻率非常低（以幾十分鐘為單位）

這提高了可靠性：如果一個 LS 由於某種原因丟失，它可以重新發送，而不必等待下一個事件；
這允許包含“年齡”欄位：與已消失的目的地相關的條目保留在路由表中，資料包會繼續傳送到該目的地，直到資訊在沒有重新整理之前變老，足以將其刪除。

泛洪演算法

每個 LS 必須以“廣播”方式傳送到網路中的所有路由器，所有路由器都必須以不變的形式接收它→真正的協議實現了一種選擇性泛洪，它代表了使用相同資料到達所有路由器的唯一方法，並且開銷最小。廣播僅限於 LS，以避免網路飽和。

LS 傳播速度很快：與 DV 不同，每個路由器都可以立即傳播接收到的 LS，並在稍後本地處理它。

真實協議為 LS 傳播實現了可靠機制：每個 LS 必須透過確認“逐跳”確認，因為路由器必須確保傳送到其鄰居的 LS 已被接收，還要考慮 LS 是以低頻率生成的。

Dijkstra 演算法

在從其鄰接列表構建網路地圖後，每個路由器都可以使用Dijkstra 演算法來計算圖的生成樹，即以該節點為根的成本最小的路徑樹：在每次迭代中，都會考慮所有連線已選擇節點與未選擇節點的鏈路，並選擇最近的相鄰節點。

所有節點都具有相同的鏈路狀態資料庫，但每個節點都有一個不同的到達目的地的路由樹，因為獲得的生成樹會隨著選擇的根節點的不同而變化

更好的流量分配：合理地，沒有未使用的鏈路（與生成樹協議不同）；
顯然，路由樹必須在各個節點之間保持一致。

鄰接建立

在檢測到新鄰接時，需要建立鄰接以同步路由器的鏈路狀態資料庫

新節點連線到網路：相鄰節點向其傳達所有與網路相關的 LS，以填充其鏈路狀態資料庫，它將能夠從中計算其路由表；
兩個分割槽子網（例如由於故障）重新連線在一起：鏈路端點處的兩個節點中的每一個都向另一個節點傳達與其子網相關的全部 LS。

過程

“hello”協議檢測到新的鄰接，該協議控制鄰接；
同步是點對點過程，即它僅影響新鏈路端點處的兩個路由器；
以前未知的 LS 以泛洪方式傳送到網路中的其他節點。

在廣播資料鏈路層網路上的行為

LS 演算法將網路建模為一組點到點鏈路 → 它在存在廣播 ^[1] 資料鏈路層網路（例如乙太網）的情況下會遇到問題，在這些網路中，任何實體都可以直接訪問同一資料鏈路上的任何其他實體（共享匯流排），從而建立一組完全連線的鄰接關係（ $N$ 個節點 → ${\tfrac {N\left(N-1\right)}{2}}$ 個點到點鏈路）。

大量的鄰接關係對 LS 演算法有嚴重的影響

計算問題: Dijkstra 演算法的收斂速度取決於鏈路的數量（ $L\cdot \log {N}$ ），但在廣播網路中，鏈路的數量會激增；
傳播 LS 時不必要的開銷: 當路由器需要在廣播網路上傳送其 LS 時，它必須生成 $N-1$ 個 LS，每個鄰居一個，即使只在共享通道上傳送一次就能讓所有鄰居收到，然後每個鄰居又會多次傳播接收到的 LS（ $\sim N^{2}$ ）；
建立鄰接關係時不必要的開銷: 每當一個新的路由器新增到廣播網路中時，它必須啟動 $N-1$ 個建立階段，每個鄰居一個，即使只需要與其中一個重新對齊資料庫就足夠了。