路由協議和架構/距離向量演算法

距離向量 (DV) 演算法基於在路由器鄰域內分發有關整個網路的資訊。

每個路由器定期生成一個 DV，它是一組目標-成本對

• 目標: 生成路由器已知的目標 (在實際 IP 網路中，它們是帶子網掩碼的網路地址)；
• 成本: 從生成路由器到目標路徑的成本。

接收路由器從每個 DV 中瞭解

• 可達目標: 它們將新增到本地已知的目標中；
• 方向: 這些目標可以透過生成路由器訪問；
• 成本: 生成路由器報告的成本加上接收路由器和生成路由器之間鏈路的成本。

每個節點儲存來自其鄰居的所有 DV，並透過為每個目標選擇最佳成本，以構建其路由表和 DV

生成節點 A 的路由表和新 DV 的過程。

基本演算法

• 主流程
  1. DV 被宣佈給相鄰路由器；
  2. 它等待超時；
  3. 它返回到步驟 1；
• 收到新的 DV 時
  1. DV 被儲存到記憶體中；
  2. DV 與儲存的 DV 合併；
• 當鏈路發生故障 (在物理層檢測到) 時
  1. 來自該鏈路的所有 DV 都被刪除；
  2. 剩餘的 DV 被合併；
• 當在超時時間內未收到 DV 時
  1. 丟失的 DV 被刪除；
  2. 剩餘的 DV 被合併。

備註

• 可靠性: 超時避免使用鏈路啟動訊號，這些訊號可能並不總是可用 (例如，如果故障發生在集線器之外)；
• 效率: 當鏈路發生故障時，路由器會在不與相鄰節點交換任何 DV 的情況下獲得其新的路由表；
• 收斂速度: 當路由器更改其 DV 時，它不會宣佈它，直到主程序的下一個超時 (沒有觸發更新)。

觸發更新

路由器可以在更新其路由表後立即傳送其更新的 DV，而不必等待預設超時，以提高收斂時間。它可以宣佈整個 DV，或者，就像在實際實現中更常見的那樣，只宣佈更改的路由。

觸發更新不會重置主程序的超時，以避免路由器同時開始生成 DV (同步)。

無窮計數

無窮計數示例。

當到達不再可達的目標的成本逐漸增加到無窮大時，就會觸發無窮計數。

示例

在側邊圖中，A 和 B 之間鏈路的故障會觸發無窮計數

1. B 在物理層檢測到故障並刪除來自 A 的 DV，但 C 無法在物理層檢測到故障；
2. C 向 B 宣佈，它可以透過成本為 2 的路徑到達 A，這實際上是穿過 B 的舊路徑；
3. B 更新來自 C 的 DV，表明 A 現在可以透過穿過 C 的替代路徑到達，成本為 3；
4. B 反過來將其 DV 傳送給 C，C 更新它並將成本增加到 4，依此類推。

效果

B 認為它可以透過 C 訪問 A，而 C 認為它可以透過 B 訪問 A → 傳送到 A 的資料包開始在 B 和 C 之間彈跳 (彈跳效應)，使 B 和 C 之間的鏈路飽和，直到其 TTL 降至 0。

原因

與黑洞和路由迴圈不同，無窮計數是 DV 演算法的特定問題，因為 DV 中包含的資訊沒有考慮網路拓撲。

可能的解決方案

• 無窮閾值: 無窮計數的上限；
• 附加演算法: 它們可以防止無窮計數，但會使協議更繁重，並傾向於降低其可靠性，因為它們無法預見所有可能的故障
  • 路由中毒: 不好的訊息勝過沒有訊息；
  • 分隔視野: 如果 C 透過 B 訪問目標 A，B 沒有必要嘗試透過 C 訪問 A；
  • 路徑保持: 讓謠言平靜下來，等待真相。

無窮閾值

可以定義一個閾值: 當成本達到閾值時，目標將被認為不再可達。

例如，RIP 的閾值等於 16: 級聯中超過 15 個路由器不能連線。

具有複雜指標 (例如 IGRP) 的協議需要非常高的閾值才能考慮差異化的成本: 例如，基於頻寬的指標可能會導致廣泛的成本值範圍。

如果彈跳效應發生在低成本鏈路上，則需要相當長的時間才能將成本增加到閾值 → 同時可以使用兩個指標

• 一個用於路徑成本的指標 (例如，基於鏈路頻寬)；
• 一個用於無窮計數的指標 (例如，基於跳數)。

當用於無窮計數的指標返回 '無窮大' 時，無論路徑成本如何，目標都將被認為不可達。

路由中毒

檢測到故障的路由器將不再可達的目標的成本傳播為無窮大 → 其他路由器會聽到故障並反過來傳播 '中毒' 資訊。

分隔視野

每個路由器都區分發送給其鄰居的 DV: 在每個 DV 中，它會省略那些可以透過穿過它正在傳送 DV 的鄰居的路徑訪問的目標 → 它不會觸發 '虛假' 路徑出現在不再可達的目標方向，因為在 DV 中傳送了過時的資訊。

特點

• 它避免了兩個節點之間的無窮計數 (除非是特定的迴圈)；
• 它提高了 DV 演算法的收斂時間；
• 路由器必須為每個鏈路計算不同的 DV。

帶有中毒反向的分隔視野

在實際實現中，DV 可能被分成多個數據包 → 如果 DV 中的某些條目被省略，接收節點不知道這些條目是被分隔視野機制有意省略，還是包含它們的包丟失了。

在帶有中毒反向的分隔視野中，目標不會被省略，而是被傳輸，但被 '中毒'，成本為無窮大，因此接收節點可以確定它已收到構成 DV 的所有資料包 → 這會延長收斂時間。

路徑保持

如果到目標的路徑成本增加，它很可能觸發無窮計數 → 該條目將被 '凍結' 一段特定時間，等待網路其餘部分找到可能的替代路徑，然後，如果沒有人繼續宣佈該目標，它將被視為不可達，並且其條目將被刪除。

DUAL

擴散更新演算法 (DUAL) 是一種旨在透過保證即使在瞬態情況下也不存在路由迴圈來提高 DV 演算法可擴充套件性的附加演算法。

• 正狀態變化: 如果任何鄰居節點宣佈一條具有更低成本的替代路徑，則會立即接受，因為它肯定不會導致路由迴圈；
• 負狀態變化: 如果
  • 當前的下一跳宣佈當前路由的成本增加（忽略其他鄰居節點的更差宣佈），
  • 或者路由器在物理層檢測到當前路由所屬鏈路的故障，

  那麼 DUAL 演算法必須被啟用。

  1. 選擇可行後繼者: 只有當它保證透過它的替代路徑不會導致路由迴圈時，才會選擇另一個鄰居；
  2. 擴散過程: 如果找不到可行後繼者，節點將進入一種“恐慌模式”，並向其鄰居求助，等待有人報告通往該目的地的可行路徑。

選擇可行後繼者

如果當前路由由於負狀態變化而不再可用，則只有在可以證明新路徑不會建立迴圈的情況下才會選擇替代路徑，也就是說，只有在確定新的下一跳不使用該節點本身到達目的地的情況下才選擇替代路徑。

鄰居節點 $K$ 是路由器 $R$ 的可行後繼者當且僅當它到目的地 $D$ 的距離小於路由器 $R$ 在狀態變化之前所擁有的距離。

$d\left(K,D\right)<d\left(R,D\right)$

這保證了鄰居 $K$ 可以使用不經過路由器 $R$ 的路徑到達目的地 $D$: 如果路徑 $K\rightarrow D$ 經過 $R$，它的成本不能低於子路徑 $R\rightarrow D$ 的成本。

如果存在多個可行後繼者，則選擇提供通往目的地 $D$ 的最低成本路徑的鄰居 $X$

$\min {\{L\left(R,X\right)+d\left(X,D\right)\}}$

其中

• $L\left(R,X\right)$ 是路由器 $R$ 與其鄰居 $X$ 之間的鏈路的成本；
• $d\left(X,D\right)$ 是鄰居節點 $X$ 到目標節點 $D$ 的距離。

選擇的可行繼任節點不一定是通往目標節點的最佳路徑所經過的鄰居節點。如果機制沒有選擇最佳的鄰居節點，後者將繼續廣播實際上是最優的路徑，且不改變其成本→路由器會識別到新的、更好的路徑，但該路徑沒有被選擇，並會採用新的路徑（狀態發生積極變化）。

擴散過程

如果路由器 $R$ 無法為目標節點找到任何可行的繼任節點

1. 它會在路由表中臨時凍結與目標節點相關的條目→資料包會繼續走舊路徑，該路徑絕對沒有環路，並且可能不再能到達目標節點；
2. 它會進入活動狀態
   1. 它會向其所有鄰居（除了舊路徑的下一跳節點）傳送查詢訊息，詢問它們是否能找到比舊路徑更好的路徑，並且該路徑絕對沒有環路；
   2. 它會等待從每個鄰居接收回覆訊息；
   3. 它會選擇最佳路徑並退出活動狀態。

每個收到路由器 $R$ 查詢訊息的鄰居路由器 $X$ 會發送包含其 DV（與透過該鄰居的路徑相關）的回覆訊息

• 如果路由器 $R$ 不是其通往目標節點的下一跳節點，因此其通往目標節點的路徑成本沒有改變，那麼路由器 $X$ 會報告路由器 $R$ 可以使用該路徑；
• 如果路由器 $R$ 是其通往目標節點的下一跳節點，那麼路由器 $X$ 應該依次開始尋找新的路徑，可以透過選擇可行的繼任節點或也進入活動狀態。

優點和缺點

優點

• 非常容易實現，基於 DV 演算法的協議易於配置；
• 它需要的處理資源有限→路由器使用廉價的硬體；
• 適用於小型且穩定的網路，且網路中負狀態變化頻率不高；
• DUAL 演算法保證網路無環路：即使在瞬態狀態下，也不會出現路由環路（雖然黑洞仍然會被容忍）。

缺點

• 該演算法的最壞情況時間複雜度為指數級，其正常時間複雜度介於 $O\left(n^{2}\right)$ 和 $O\left(n^{3}\right)$ 之間；
• 收斂速度可能相當慢，與網路中最慢的鏈路和最慢的路由器成正比；
• 很難理解和預測其在大而複雜的網路中的行為：沒有節點擁有網路的拓撲圖→很難檢測到潛在的路由環路；
• 由於拓撲結構的特定變化，它可能會引發路由環路；
• 用於改進其行為的附加技術會使協議更加複雜，而且它們也不能完全解決拓撲知識缺失的問題；
• '無窮大'閾值限制了該演算法只能用於小型網路（例如，具有少量跳數的網路）。

路徑向量演算法

路徑向量（PV）演算法添加了關於宣佈的路由的資訊：它也會宣佈路徑，即路徑上的 經過的節點列表。

生成節點 A 路由表和新 PV 的過程。

交叉節點列表可以避免路由迴圈的出現：接收節點可以透過觀察其識別符號是否出現在列表中來檢測到宣佈的路由是否經過它，從而將其丟棄而不是傳播它 → 兩次經過同一個節點的路徑無法形成。

路徑向量是距離向量和鏈路狀態之間的中間演算法：它添加了關於宣佈路徑的嚴格必要資訊，而無需像鏈路狀態那樣需要了解整個網路拓撲結構的複雜性。

應用

PV 演算法在 BGP 協議的域間路由中使用： B5. 邊界閘道器協議#路徑向量演算法.