408 > 计算机网络 > 路由算法：距离-向量路由

一、定位信息

• 所属圈层：核心层
• 前置知识：需了解路由表的基本概念（目的网络、下一跳、距离/代价），以及图论中"最短路径"的基本含义
• 知识网络位置：距离-向量路由是最基本的路由算法之一，是理解RIP协议的直接基础，向上承接路由选择功能，向下引出链路状态路由的对比
• 考点热度等级：H级（高频重点） — 距离-向量与链路状态路由的对比是408常考知识点，近五年多次出现在选择题和综合题中

二、知识点讲解

2.1 基本概念

距离-向量路由（Distance-Vector Routing，DV）是一种分布式、迭代式的路由算法。其核心思想是：每个路由器维护一张路由表，表中记录到达每个目的网络的最短距离和下一跳。路由器周期性地将自己的路由表信息发送给所有邻居，邻居收到后根据Bellman-Ford方程更新自己的路由表。

Bellman-Ford方程：设 $d_x(y)$ 表示从节点 $x$ 到目的 $y$ 的最短距离，则：

$d_x(y) = \min_{v \in N(x)} \{ c(x,v) + d_v(y) \}$

其中 $N(x)$ 是 $x$ 的邻居集合，$c(x,v)$ 是 $x$ 到邻居 $v$ 的链路代价，$d_v(y)$ 是邻居 $v$ 到 $y$ 的最短距离。

2.2 工作过程

1. 初始化：每个路由器只知道直接相连的网络，距离为链路代价；未知目的距离设为无穷大（$\infty$）。
2. 周期性通告：每个路由器每隔固定周期（如RIP为30秒），将自己的完整路由表发送给所有邻居。
3. 接收更新：路由器收到邻居的路由表后，对每个目的网络，计算"经该邻居到达目的的距离"。
4. 更新路由表：如果计算出的距离比当前路由表中的距离更短，或当前路由表中没有该目的网络，则更新路由表。
5. 收敛：经过多轮迭代，所有路由器的路由表趋于稳定，此时称为"收敛"。

2.3 计数到无穷问题与毒性逆转

距离-向量路由存在一个经典问题——计数到无穷（Count to Infinity）。当某条链路失效时，可能出现路由环路，导致距离值不断增大直到达到定义的"无穷大"（如RIP中为16）。

解决方案：

• 毒性逆转（Poisoned Reverse）：如果路由器A通过邻居B到达目的网络N，则A在向B发送路由更新时，将到N的距离设为无穷大，从而避免B经过A到达N形成环路。
• 定义最大距离：如RIP将最大跳数限制为16，超过即认为不可达，防止无限计数。
• 触发更新：当路由表发生变化时立即发送更新，不必等待周期定时器。

2.4 特点总结

• 优点：实现简单，开销小，易于理解
• 缺点：收敛速度慢，存在路由环路风险，每次发送完整路由表带宽消耗大

---

三、记忆与理解辅助

1. 口诀："距离向量看邻居，Bellman方程来更新；毒性逆转防环路，计数到无穷要当心。"
2. 类比记忆：距离-向量路由就像"小道消息传播"——每个人只知道邻居告诉自己的信息，经过多轮传递才能了解全貌。传播慢，且可能以讹传讹（路由环路）。
3. 对比速记表（DV vs LS 将在下一单元详细展开，此处给出核心差异速记）：

特征	距离-向量（DV）	链路状态（LS）
信息范围	只看邻居	了解全网拓扑
计算方式	Bellman-Ford	Dijkstra
收敛速度	慢	快
代表协议	RIP	OSPF

4. 数字记忆：RIP中无穷大=16跳，周期更新=30秒

四、例题与精解

例题1（基础巩固）

题目：在距离-向量路由算法中，路由器X有三个邻居A、B、C。当前X的路由表显示到目的网络N的距离为5（下一跳为A）。现在X收到邻居B发来的路由更新，其中到N的距离为2，且X到B的链路代价为1。请问X的路由表应如何更新？

命题意图：考查对Bellman-Ford方程的基本应用能力。

精解：

1. 审题分析：已知 $d_X(N) = 5$（经A），$d_B(N) = 2$，$c(X,B) = 1$。求经B到达N的距离，并与当前值比较。
2. 解题思路：应用Bellman-Ford方程，计算经B到达N的新距离，与当前值5比较。
3. 完整步骤：
   • 经B到达N的距离 = $c(X,B) + d_B(N) = 1 + 2 = 3$
   • 当前 $d_X(N) = 5$（经A）
   • 因为 $3 < 5$，所以更新路由表
   • 更新结果：到目的网络N，距离改为3，下一跳改为B
4. 方法反思：距离-向量路由的核心就是比较"走旧路"和"走新路"哪个代价更小，每次收到邻居更新都要重新计算。

例题2（中等提升）

题目：如下图所示的网络拓扑（用文字描述），各链路代价如标注。假设采用距离-向量路由算法，所有路由器初始路由表仅包含直接相连的网络。请给出经过第一轮和第二轮路由更新后，路由器A的路由表变化。

【图示说明】：网络拓扑为 A--1--B--1--C，即A与B之间链路代价为1，B与C之间链路代价为1。A、B、C为三个路由器。

命题意图：考查距离-向量路由的迭代更新过程，检验对收敛过程的理解。

精解：

1. 审题分析：三个路由器A、B、C线性连接。需要跟踪A的路由表经过两轮更新后的变化。
2. 解题思路：逐轮模拟路由表更新过程，每轮路由器将路由表发给邻居并更新。
3. 完整步骤：

初始状态：

目的	A的路由表	B的路由表	C的路由表
A	0, -	1, A	$\infty$, -
B	1, B	0, -	1, B
C	$\infty$, -	1, C	0, -

第一轮更新（各路由器向邻居发送路由表）：

• A收到B的表：B→C距离1，所以A经B到C = 1+1 = 2
• A更新：目的C，距离2，下一跳B
• A的路由表：{A:0/-, B:1/B, C:2/B}

第二轮更新：

• A的路由表已无变化（C距离2已是最短路径）
• 收敛完成

4. 方法反思：在简单拓扑中，距离-向量算法收敛较快。但在大规模网络或存在环路的拓扑中，收敛可能需要很多轮迭代，且容易出现计数到无穷问题。

五、考情分析

• 考查频次：近5年在408真题中出现3-4次，属于高频考点
• 常见题型：以选择题为主，偶尔出现在综合题中作为路由部分的一个小问
• 分值占比：选择题约2分，综合题中约3-5分
• 命题趋势：距离-向量与链路状态的对比是经典命题角度，近年来更倾向于结合具体协议（RIP vs OSPF）进行考查，需要考生不仅理解算法原理，还要知道实际应用中的差异

六、易错点提醒

1. 错误表现：混淆"距离-向量"和"链路状态"算法的工作方式

   • 错误原因：两者都是路由算法，概念相近容易混淆
   • 正确理解：距离-向量是"每个路由器只知道邻居的信息"，链路状态是"每个路由器知道全网拓扑"。记住：DV看邻居，LS看全局

2. 错误表现：在应用Bellman-Ford方程时忘记加上本地链路代价

   • 错误原因：直觉上觉得邻居告诉你的距离就是你应该记录的距离
   • 正确理解：经邻居到达目的的总距离 = 到邻居的链路代价 + 邻居到目的的距离

3. 错误表现：认为毒性逆转可以完全消除路由环路

   • 错误原因：对毒性逆转的机制理解不全面
   • 正确理解：毒性逆转只能防止两节点间的简单环路，对于三个及以上节点形成的复杂环路无能为力，需要配合定义最大距离等其他机制

七、来源标注

• 依据2026考研统考大纲
• 依据《计算机网络（第8版）》谢希仁版
• 依据《计算机网络：自顶向下方法》Kurose & Ross版