距离向量算法

距离向量算法
中文名	距离向量算法
英文名	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）相继被提出并逐步替代了纯距离向量协议在大型网络中的核心地位，但距离向量算法仍因其简单高效的特质而广泛应用于小型网络和边缘路由场景。