距離向量算法

距離向量算法
中文名	距離向量算法
英文名	Distance Vector Algorithm
別名	分布式Bellman-Ford算法、Bellman-Ford路由算法、Ford-Fulkerson算法
類別	路由算法
核心原理	通過相鄰節點交換距離矢量，基於Bellman-Ford方程計算最短路徑
主要特徵	分布式計算、僅與鄰居交換路由信息、周期性完整路由表更新
典型協議	RIP、IGRP、EIGRP、Babel
主要問題	無窮計數、路由環路

距離向量算法（Distance Vector Algorithm，DV） 是計算機網絡路由協議中的一類核心算法，亦稱為分布式Bellman-Ford算法（Distributed Bellman-Ford）、Bellman-Ford路由算法或Ford-Fulkerson算法。該類算法採用分布式計算模式，網絡中的每個路由器僅與直連的相鄰節點交換路由信息，且通常以周期性方式向鄰居廣播其完整路由表。距離向量算法因其實現簡單、資源占用率較低的特性而被廣泛應用於小型網絡環境，其典型實現包括路由信息協議（RIP）、內部網關路由協議（IGRP）及其增強版EIGRP等。

算法原理

基本思想

距離向量算法的基本思想是：每個路由器維護一張距離矢量表，表中記錄了到達網絡中每個已知目的地的最佳距離（由度量值表示）以及到達該目的地應使用的下一跳路由器（方向）。路由器的名稱源於其以「矢量」——即距離和方向——的形式通告路由信息，其中距離由跳數、延遲、帶寬等度量標準定義，方向由下一跳路由器確定。這類協議也常被稱作「依據傳聞的路由協議」（routing by rumor），因為每台路由器在信息上都依賴於自己的相鄰路由器，而相鄰路由器又是通過它們自己的相鄰路由器學習路由，依此類推。

Bellman-Ford方程

距離向量算法的核心數學基礎是Bellman-Ford方程。記 D(i,j) 為路由器 i 到目的地 j 的最優距離（代價），d(i,k) 為路由器 i 到其鄰居 k 的直接鏈路開銷，D(k,j) 為鄰居 k 到目的地 j 的距離。則 D(i,j) 通過以下遞推關係確定：

D(i,j) = min{ d(i,k) + D(k,j) }，對所有鄰居 k 取最小值

該方程的含義是：路由器 i 到目的地 j 的最優路徑，等於先從 i 經由某個鄰居 k 一步到達 k 的代價，再加上 k 到 j 的最優路徑代價，並在所有可能的鄰居中選擇總代價最小的方案。由於每個路由器根據鄰居通告的信息進行本地更新，該算法被稱為分布式Bellman-Ford算法。

路由表更新機制

距離向量算法通過以下流程實現路由表的動態維護：

• 初始狀態：每個路由器僅知曉自身直連鏈路的信息。直連網絡的距離為0（到達自身）或1（到達直接相連的鄰居，視度量定義而定）。
• 周期性通告：每個路由器以固定時間間隔（典型值為30秒，參見RIP協議規範）向其所有相鄰路由器發送完整的距離矢量表。
• 接收與更新：相鄰路由器收到通告後，將收到的矢量信息與自身的路由表進行比較：
  • 若發現到達某目的地的新路由，則將其加入路由表；
  • 若發現到達某已知目的地且開銷更小的新路徑，則用新路徑替換原有條目；
  • 若更新信息來自當前使用的下一跳路由器且該條目的開銷發生了變化，則無論新開銷是否增大均進行更新（這是避免環路的重要機制之一）。
• 迭代收斂：各路由器重複上述過程，經過若干輪更新後，全網絡最終達成一致的最優路由視圖，此過程稱為收斂。

收斂與無窮計數問題

收斂

收斂（Convergence）是路由算法中的關鍵概念，指當網絡拓撲發生變化（如鏈路故障或新節點加入）後，網絡中所有路由器重新計算並最終達成一致的最優路由視圖的過程。在距離向量算法中，收斂速度相對較慢，原因在於路由信息需要逐跳傳播，且每一跳都受到周期性更新間隔的限制。

無窮計數問題

距離向量算法面臨的最主要缺陷是無窮計數（Count to Infinity）問題。當網絡中的鏈路發生故障（斷開）時，由於各節點僅依賴鄰居告知的信息，且無法得知自身是否被包含在鄰居到目的地的路徑中，可能導致錯誤的路由信息在相鄰節點之間來回傳遞，使得路由度量值逐步遞增直至達到協議定義的最大值（在RIP中為16跳），才會判定目的地不可達。該過程的典型演進路徑如下：

• 鏈路AB斷開後，B更新其到A的距離為無窮大。
• B收到C的通告，其中C聲稱經過B可到達A（但B已失去與A的連接），B據此錯誤地更新路由。
• B的通告又促使C更新其路由表，路由度量值逐輪遞增。
• 如此反覆，直到兩節點到達A的度量值「增長」到協議預定義的最大值（如RIP中的無窮大為16跳）。
• 此後，兩節點才最終確認A不可達。

無窮計數問題的根源在於：距離向量僅包含距離信息而不記錄完整的路徑信息，當B更新其經由A到達C時，B無法意識到A到達C的路徑實際上正是經過B自身的。也就是說，距離向量中隱藏了路徑上的依賴關係，導致下游路由器無法識別路徑環路。

優化機制

為緩解無窮計數和路由環路問題，距離向量協議引入了以下改進機制：

• 水平分割（Split Horizon）：路由器不從某個接口通告從該接口學習到的路由信息，即避免將路由信息返回給發送該信息的鄰居，從而降低環路形成的可能性。
• 毒性反轉（Poison Reverse）：更激進的策略——路由器將從某鄰居學習到的路由信息通告回該鄰居時，明確將其距離設為無窮大（「毒性」），以明確告知鄰居該路徑不可用。
• 定義最大跳數：通過為度量值設置一個上限（RIP中為16跳），將大於該上限的距離視為「無窮遠」，從而強制終止無窮計數過程。
• 觸發更新（Triggered Update）：當網絡拓撲發生變化時，路由器立即發送路由更新而不等待周期性更新計時器，以加速收斂。
• 抑制計時器（Holddown Timer）：在路由從不可靠狀態恢復之前，暫時抑制接收可能包含錯誤信息的更新，防止路由表頻繁振盪。

距離向量與鏈路狀態算法的對比

距離向量算法與鏈路狀態算法是動態路由協議的兩大基本分類。兩者的核心差異體現在信息交換方式和網絡視圖上：

• 信息交換範圍：距離向量算法僅與直連鄰居交換完整路由表，而鏈路狀態算法通過泛洪機制在全網範圍內交換鏈路狀態信息，使每個節點都能獲得完整的網絡拓撲圖。
• 網絡視圖：距離向量算法中的每個路由器只掌握通往各目的地的距離和下一跳（「傳聞式」視圖），缺乏對整個網絡拓撲的全面了解；鏈路狀態算法中的每個路由器通過鏈路狀態資料庫可以精確繪製整個網絡的拓撲結構。
• 收斂速度：距離向量算法由於依賴周期性更新和逐跳信息傳遞，收斂較慢；鏈路狀態算法採用事件觸發的增量更新，收斂更快。
• 資源消耗：距離向量算法對CPU和內存的要求較低，適合資源受限的小型網絡；鏈路狀態算法需要維護鏈路狀態資料庫並運行SPF計算，資源占用較高。
• 環路處理：距離向量算法容易因信息傳播延遲而產生臨時路由環路，需要通過水平分割、毒性反轉等輔助機制加以緩解；鏈路狀態協議可以通過自身機制避免永久環路。

應用協議

距離向量算法及其變體被廣泛應用於多種動態路由協議中。

路由信息協議（RIP）

路由信息協議（Routing Information Protocol, RIP）是距離向量算法最經典的實現。RIP使用跳數作為度量值，最大允許15跳，16跳視為無窮大。RIPv1的原始規範於1988年在RFC 1058中發布，採用有類路由，使用廣播進行路由通告。RIPv2於1993年引入，增加了對可變長子網掩碼（VLSM）和無類別域間路由（CIDR）的支持，使用組播地址224.0.0.9發送更新，並加入了認證機制。RIPng（RIP下一代）於1997年在RFC 2080中定義，是對IPv6網絡的支持版本，其度量限制為15跳的基本特徵保持不變。

RIP使用UDP協議進行報文交換，埠號為520。路由器每隔30秒發送一次更新報文。RIPv1使用廣播，RIPv2使用組播，後者有效減少了不運行RIP的主機對更新報文的處理開銷。

內部網關路由協議（IGRP）

內部網關路由協議（Interior Gateway Routing Protocol, IGRP）是Cisco Systems開發的專有距離向量協議，引入了帶寬、延遲、負載、可靠性等複合度量標準替代RIP中單一的跳數度量，支持多路徑負載均衡，適用於更大規模的網絡。

增強型內部網關路由協議（EIGRP）

增強型內部網關路由協議（Enhanced Interior Gateway Routing Protocol, EIGRP）是Cisco專有的高級距離向量協議，在保留距離向量基本特性的基礎上，引入了擴散更新算法（Diffusing Update Algorithm, DUAL），通過維護可行後繼者（Feasible Successor）機制實現了無環路快速收斂，且支持IP、IPX、AppleTalk等多協議環境。

Babel協議

Babel是基於距離向量算法構建的路由協議，為無線網狀網絡等場景提供了良好的適應性。其在分布式Bellman-Ford算法的基礎上增加了環路避免和飢餓避免機制，有效消除了傳統距離向量協議中的無窮計數問題。Babel支持在同一協議實例中同時承載IPv6和IPv4等多種地址族路由信息。

歷史發展

距離向量算法是ARPANET網絡最早使用的路由算法。20世紀60年代至70年代，Richard Bellman、Lester Ford和D. R. Fulkerson等學者在圖論和最短路算法領域的研究成果為距離向量協議奠定了理論基礎。1988年，RIP協議的RFC 1058規範正式將距離向量算法標準化，使其成為TCP/IP網絡中最廣泛部署的動態路由方案之一。隨著網絡規模的快速擴張，距離向量算法在收斂速度、環路防護以及擴展性方面的局限性逐漸顯現，為滿足大型和複雜網絡的需求，鏈路狀態算法以及混合型算法（如EIGRP）相繼被提出並逐步替代了純距離向量協議在大型網絡中的核心地位，但距離向量算法仍因其簡單高效的特質而廣泛應用於小型網絡和邊緣路由場景。