路由算法：距离向量 vs 链路状态

2026 大纲 四（二）1~4 路由算法，并承载 四（五）1 自治系统与 四（五）2 域内路由与域间路由的概念部分。具体协议在 RIP、OSPF、BGP 三篇。

一、先问"这是哪根轴上的问题"

路由表里那些"目的网络 → 下一跳"是怎么来的？这一篇讲的就是算它们的算法。开头要先把分类理顺，否则后面很容易把两个不相干的概念硬凑成一对。

路由算法有三根互相正交的分类轴，一个协议同时带三个标签。比如 RIP 是"动态 + 距离向量 + 域内"。

第一根轴问"路由表由谁产生"：管理员手工配置的是静态路由（也叫非自适应路由选择），路由协议自动学出来的是动态路由（自适应路由选择）。

第二根轴问"邻居之间交换什么信息"：交换"我到各处有多远"这个结论的，是距离向量 DV；交换"我这几条链路什么状态"这个原料的，是链路状态 LS。

第三根轴问"协议的作用域"：全网一视同仁是平面路由，先分自治系统再分内外是层次路由。

混淆几乎都来自把不同轴的对立面凑成一对。最容易碰上的一句是"静态 vs 距离向量"——这两个根本不成对立，静态路由不交换任何信息，它压根不在第二根轴上。

顺带纠一个偏见：静态路由不是"低端"。 判据是"备选路径有没有多于一条"——只有一条出口时，动态路由带来的全部是开销：周期或触发的报文要占 CPU、内存和带宽，还多出一个可能被伪造路由通告欺骗的攻击面，而算来算去只有那一条路可走。末端网络接入 ISP 的出口、需要强制路径的合规与计费场景，都大量使用静态路由。动态路由的价值只在拓扑会变、且确实有多条备选路径时才兑现。

二、距离向量

递推式与它的来历

距离向量算法的全部内容就是一个递推式：

$$D_x(y)=\underset{v\in N(x)}{min}[c(x,v)+D_v(y)]$$

其中 $N(x)$ 是 $x$ 的直连邻居集合，$c(x,v)$ 是直连链路的代价，$D_v(y)$ 是邻居 $v$ 自己声称的到 $y$ 的距离。

这个 $min$ 从哪来的？ 来自最短路的最优子结构：设 $X$ 是节点 $A$ 到 $B$ 的最短路径上的一个节点，把路径拆成 $A\to X$ 与 $X\to B$ 两段，则每一段也分别是最短路径。

用在"$x$ 到 $y$ 的最短路"上：这条路的第一跳必定是 $x$ 的某个直连邻居 $v$；一旦第一跳定了，剩下的 $v\to y$ 那段必定是 $v$ 到 $y$ 的最短路，也就是 $D_v(y)$。而第一跳只有 $|N(x)|$ 种选择，全试一遍取最小就是全局最小。

式子里有一处最容易代错：$c$ 和 $D$ 绝不能混用。 $c(\cdot ,\cdot )$ 是链路属性，永远不变；$D_x(\cdot )$ 是计算结果，每轮都在变。代入时前一项必须用直连链路的原始代价，用了本轮算出的 $D$ 就等于把某段路重复计了一次。

在四节点拓扑上逐轮跑到收敛

拓扑（自造数据）：$c(A,B)=2$、$c(B,C)=1$、$c(C,D)=3$、$c(A,C)=5$，A 与 D 之间没有直连链路，链路双向对称。所有节点同时启动，只知道自己的直连链路。

第 0 轮：初始化。 只填直连链路代价，其余记 $\mathrm{\infty }$——距离向量算法的全部输入就是"我自己的直连链路代价"，谁都还没和别人说过话。注意 D 只有一个邻居 C，它对 A、B 一无所知。

各自的距离表	到 A	到 B	到 C	到 D
A	0	2	5	$\mathrm{\infty }$
B	2	0	1	$\mathrm{\infty }$
C	5	1	0	3
D	$\mathrm{\infty }$	$\mathrm{\infty }$	3	0

第 1 轮：每个节点收到全部邻居的第 0 轮向量，代入递推式。 以 A 为例（邻居是 B、C）：到 C 取 $min\{5,2+1=\mathbf{3}\}=3$，绕道 B 反而更短；到 D 取 $min\{2+\mathrm{\infty },5+3=\mathbf{8}\}=8$。

距离表	到 A	到 B	到 C	到 D	本轮变化
A	0	2	3	8	到 C 由 5 降为 3（改走 B）；到 D 由 $\mathrm{\infty }$ 变 8
B	2	0	1	4	到 D 由 $\mathrm{\infty }$ 变 4（走 C）
C	3	1	0	3	到 A 由 5 降为 3（改走 B）
D	8	4	3	0	第一次知道 A、B 的存在

第 1 轮结束时，每个节点掌握的是最多 2 跳可达范围内的最短距离。A 到 D 需要 3 跳（A-B-C-D），所以此刻的 8 还不是最终答案——它是"经过 C 这一个中转"能得到的最好结果。

第 2 轮：把新向量再交换一次。

$$D_A(D)=min\{\underset{2+4=6}{\underbrace{c(A,B)+D_B(D)}},\underset{5+3=8}{\underbrace{c(A,C)+D_C(D)}}\}=6$$

第二项里的 $c(A,C)$ 必须用直连链路的原始代价 5，不能用第 1 轮算出的 $D_A(C)=3$——这正是上面说的那处坑。

距离表	到 A	到 B	到 C	到 D	本轮变化
A	0	2	3	6	8 → 6（B 报告它到 D 只要 4）
B	2	0	1	4	无
C	3	1	0	3	无
D	6	4	3	0	8 → 6（C 报告它到 A 只要 3）

A→D 的真实最短路是 A-B-C-D $=2+1+3=6$，需要 3 跳。只有等 B 先在第 1 轮学会"我到 D 是 4"，A 才能在第 2 轮学到 6——这是"按跳数逐层扩散"最直观的证据。

第 3 轮：所有向量与第 2 轮完全相同，无更新 → 收敛。 4 个节点、直径 3 跳，有效更新 2 轮。放在 RIP 上每轮 30 s，收敛就是分钟量级——这就是"慢"的具体数字。

从这个过程可以直接读出一条重要性质：收敛轮数由跳数决定，与代价大小无关。 每一轮的结果恰好等于"最多用 $k$ 跳时的最短距离"，$k$ 逐轮加 1，所以代价不变时至多 $n-1$ 轮收敛；把所有链路代价乘以 100，收敛轮数一轮也不会变。

但这个保证只在代价不变时成立。 代价变大或链路断掉时它就不成立了——那正是无穷计数的入口。

无穷计数：根因只有一句

链路代价变小时好消息一轮就能传开；链路断掉时就完全不同了。设稳态是 R1 直连 Net1、R2 经 R1 到 Net1，现在 Net1 断了：

第一步，R1 把到 Net1 的距离置为不可达。第二步，在 R1 的坏消息传到 R2 之前，R2 的周期性更新先到了 R1，报文里写着"我到 Net1 距离 2"。第三步，R1 一看：我现在到不了，而 R2 说它能到、代价 2，加一跳变 3，比不可达好，于是更新为 3，下一跳指向 R2。第四步，可 R2 那条"路"本来就是经过 R1 的，于是成了 R1 → R2 → R1 → …，环路形成。第五步，下一轮 R2 收到 R1 的 3，而 R2 到 Net1 的下一跳正是 R1，必须无条件接受，更新为 4。此后两边你来我往每轮加 1，一路涨到协议约定的上限才停。

具体涨多少轮、耗时多久，RIP 那篇有完整的逐轮表（上限 16，需 15 轮更新、约 7.5 分钟）。

根因归结成一句话：距离向量报的是"我到 $y$ 有多远"，没有报"我是怎么去的"。 于是 A 无法察觉 B 声称的那条路正好要穿过 A 自己。

三种缓解措施，边界各不相同：

措施	做法	挡住什么	挡不住什么
水平分割	从邻居 $v$ 学来的到 $y$ 的路由，不再从这个接口发回给 $v$	两节点之间的环	三个及以上节点绕成的环
毒性逆转	不仅不发回，还主动告诉 $v$："我到 $y$ 不可达"	同上，且更快——不用等 $v$ 的表项老化	同上
触发更新	度量值一变就立刻发更新，不等周期	不挡环，只压缩传播时间	环本身

水平分割为什么只挡两点环：它处理的是"从谁学来的就不告诉谁"。环是 A→B→C→A 时，信息绕一圈才回到 A，A 无从知道源头就是自己。要结构性地解决，必须让路由本身记录走过的节点——那就是后面要讲的路径向量。

三、链路状态与两类算法对照

链路状态算法的工作流分三步：发现邻居与链路代价（用问候分组探测）→ 洪泛链路状态（链路状态发生变化时、或每隔一段时间如 30 分钟刷新一次，收到者向除来路外的所有接口转发）→ 各自跑 Dijkstra（各机最终拥有内容完全相同的数据库，即"全网的拓扑结构图"，各自以自己为根算最短路）。

维度	距离向量（DV）	链路状态（LS）
算法本质 / 典型协议	Bellman-Ford / RIP	Dijkstra / OSPF
每台路由器的"视野"	不完整：只知道"邻居说它能到哪、多远"	完整的网络拓扑图
发送的信息	整张距离向量（结论），随规模线性增长	本机的链路状态（原料），与规模无关
发给谁、何时发	仅直连邻居；周期性，没变化也发	洪泛到全区域；事件驱动，没变化基本不发
信息传播	逐跳，每跳延迟一个更新周期	洪泛，不等周期，几乎以链路速率扩散
收敛速度	与直径 × 更新周期成正比，可能无穷计数	洪泛 + 一次 Dijkstra，实测小于 100 ms
环路 / 内存 / CPU	会有，靠水平分割等缓解；内存与 CPU 都小	靠数据库一致性避免；内存大、CPU 大

LS 靠什么防环？靠一致性。 它的关键不变量是全区域链路状态数据库必须一致——一旦不一致，各机算出的最短路互相矛盾，环路就会出现。OSPF 之所以要给链路状态通告编序号、要求确认、还要周期性刷新，全是为了守住这个不变量。

LS 的错误为什么不会传染？ 因为链路状态通告只描述本地事实（我这几条链路是什么状态），不含任何计算结果；而 DV 是"结论套结论"，一处算错就顺着链路一路扩散。顺带澄清一个混淆：洪泛不等于逐跳传递路由信息——洪泛时内容原封不动，DV 则是内容每跳都在变。

这笔交换换了什么：LS 用内存和 CPU 换来带宽和收敛时间。路由器的 CPU 与内存都不贵，广域链路带宽与故障恢复时间很贵——这就是 OSPF 取代 RIP 成为主流 IGP 的工程原因。一句话概括两者的差别：DV 是盲人摸象（只听邻居转述），LS 是各自拿到同一张地图。

Dijkstra 的骨架与"挑最小就能定死"的正确性反证（想弄清这一步凭什么成立时展开）

骨架（以 $s$ 为根）：① 已确定集合 $S=\{s\}$，$d(s)=0$，其余 $d(\cdot )=\mathrm{\infty }$；② 在 $S$ 之外挑 $d$ 最小的节点 $u$ 加入 $S$，此刻 $d(u)$ 被认定为最终值；③ 松弛：对 $u$ 的每个邻居 $v$，若 $d(u)+c(u,v)<d(v)$ 就改小 $d(v)$ 并记下前驱是 $u$；④ 回到第 ② 步，直到所有节点入 $S$。

第 ② 步为什么"挑最小的就能定死"？ 反证：假设此刻 $d$ 最小的是 $u$，但真实最短距离比 $d(u)$ 还小。那条更短的路必然要先离开 $S$，它离开 $S$ 时经过的第一个节点 $w$ 满足 $d(w)\le$ 该路径长度 $<d(u)$——但 $u$ 是 $S$ 外 $d$ 最小的，矛盾。

这个反证依赖一个前提：所有链路代价非负。 代价为负时 Dijkstra 就失效（后加入的节点可能把已定死的距离再拉小）。网络里的代价是带宽、时延、跳数，天然非负，所以这个前提永远成立——但知道它是个前提，才算真的懂了这个算法。

带完整逐步表的算例（含一条链路断掉后重算、最短路径树怎么变）在 OSPF。

四、层次路由

不分层会同时崩在三处：路由表规模（主干网路由器的转发表项目数可达 50 万个网络前缀）、协议流量（交换路由信息的带宽会把链路吃饱）、计算量（对这么大的图跑 Dijkstra 太慢）。还有一条非技术的硬约束：许多单位不愿意让外界了解自己网络的布局细节和所采用的路由选择协议——分层给了它们"对外只暴露可达性、对内自己说了算"的边界。

分层的单位是自治系统 AS，它的定义有三个要件。单一技术管理：能统一选协议、统一定度量。内部统一度量：AS 内"代价 1000"的含义处处相同，最短路才有意义。对外一致：外界只需要知道"经过这个 AS 能到哪些前缀"。实务中一个 AS 常常内部跑 OSPF、少量网段配静态、边界跑 BGP——"统一"指的是管理与度量口径，不是"只准跑一种协议"。

AS 内部的路由叫域内路由，用的协议统称 IGP（内部网关协议），代表是 RIP 和 OSPF，目标是找最短路径。AS 之间的路由叫域间路由，用的协议统称 EGP（外部网关协议），代表是 BGP-4，目标是找可达且符合策略的路径。每个 AS 自己决定内部跑哪种 IGP，但都要有一台或多台边界路由器，除了跑本 AS 的 IGP，还要跑 BGP-4 和相邻 AS 交换路由信息。

为什么域间不能沿用 IGP 那一套？因为跨 AS 的代价没有可比性。 对某个 AS 来说代价 1000 可能表示一条比较长但可用的路由，对另一个 AS 却可能表示不可接受的坏路由。既然度量口径不通约，域间就只能交换可达性而不是距离——这正是 BGP 必须单独存在、不能把 OSPF 拉大了用的核心理由。

两处术语坑顺便说清。EGP 既是协议类别名，又曾是一个具体协议的名字（早期那个已被 BGP 取代的协议）；有些书把 IGP/EGP 改写成 IRP/ERP，指的是同一件事。

路径向量是第三种算法。 每条 BGP 路由不只带"能到"，还带完整经过的 AS 序列 AS-PATH，换来两件距离向量做不到的事：结构性防环（发现 AS-PATH 里有自己的 AS 号就直接丢弃；不像水平分割只挡两点环，任意长度的环都挡得住，因为环必然让本 AS 号出现在路径里），以及能做策略（按"是否经过某个 AS"接受或拒绝，而不只是比大小）。

也正因为它做的是策略而不是最优化，BGP 的口径要说准：它力求选出一条能够到达目的网络前缀且比较好的路由（不兜圈子），并非要计算出一条最佳路由。"BGP 找最短路"是错的。

算法	交换什么	发给谁	算法核心	典型协议
距离向量	我到各处的距离（结论）	仅直连邻居	Bellman-Ford	RIP
链路状态	我的链路状态（原料）	洪泛全区域	Dijkstra	OSPF
路径向量	可达前缀 + AS 序列	BGP 对等体	DV 的扩展 + 策略过滤	BGP

本节小结

1. 三根轴正交：静态/动态分"路由表由谁产生"，DV/LS 分"交换什么信息"，平面/层次分"作用域"。静态路由的判据是"备选路径有没有多于一条"。
2. DV 的递推式来自最短路的最优子结构：第一跳只有有限种选择、剩下那段必然也是最短路，枚举取最小即可；轮数由跳数决定、与代价大小无关。无穷计数的根因是"传结论不传路径"——水平分割与毒性逆转只挡两点环，触发更新根本不挡环；要结构性解决必须记录走过的节点，那就是路径向量。
3. LS 交换的是原料而非结论，所以错误不传染，关键不变量是全区域数据库一致，靠它而不是靠防环措施避免环路；这是一笔用内存和 CPU 换带宽与收敛时间的交换。层次路由的三要件是单一管理、内部统一度量、对外一致；因为跨 AS 的代价没有可比性，域间只交换可达性。

考点速记

路由算法本身在真题里被考过的形式只有一种：给一张邻居距离向量表，要你把递推式代一遍。

距离向量算法的一轮更新（cn-2021-37）。E 与邻居 A、B、C、D 的直连链路距离分别是 8、10、12、6，四个邻居各报来一张到 Net1~Net4 的距离向量，问 E 更新后到四个网络的距离。逐个网络取 $min$：

• Net1：$min\{8+1,10+23,12+20,6+22\}=min\{9,33,32,28\}=\mathbf{9}$（经 A）
• Net2：$min\{8+12,10+35,12+30,6+28\}=min\{20,45,42,34\}=\mathbf{20}$（经 A）
• Net3：$min\{8+24,10+18,12+16,6+36\}=min\{32,28,28,42\}=\mathbf{28}$（经 B 或 C 都是 28）
• Net4：$min\{8+36,10+30,12+8,6+24\}=min\{44,40,20,30\}=\mathbf{20}$（经 C）

答 D（9, 20, 28, 20）。

这道题的四个选项设计得很有针对性：A 项 (9, 10, 12, 6) 是把"到邻居的链路距离"直接当成了"到目的网络的距离"，等于漏掉了加法；B 项和 C 项各自在两个网络上取错了最小值。能拿全分靠的不是技巧，是把 $c(E,v)+D_v(y)$ 这四项老老实实全算一遍再比——只算"看起来最近的那个邻居"必错，Net4 就是反例：D 的链路最短（6），可 C 那条 $12+8=20$ 才是最优。

本篇练习区里还会出现另外两道题，它们都落在 RIP 的具体规则上，机制讲在 RIP 路由协议：cn-2010-35 考收到距离 16 意味着什么，cn-2016-37 考网络不可达后一轮更新的距离值。

链路状态算法这一侧——Dijkstra 的骨架、洪泛、数据库一致性——在本篇不单独成题，它们在真题里都是以 OSPF 的形式出现的——cn-2014-43 与 cn-2026-37 都不在本篇的练习区里，讲解分别在 OSPF 与网络层功能。

易错：代入递推式时 $c$ 用直连链路的原始代价，不能用本轮算出的 $D$。 混用等于把某段路重复计了一次。

易错：四个邻居必须全算一遍再取最小。 直连链路最短的邻居未必给出最优结果。

易错：收敛轮数由跳数决定，与代价大小无关——但这个保证只在链路代价不变时成立，链路断掉时就是无穷计数。

易错：无穷计数的根因是"报距离不报路径"，不是"更新太慢"。加快更新只会让错误的值涨得更快。

易错：水平分割和毒性逆转只挡两点环，触发更新根本不挡环。 三点以上的环要靠路径向量。

易错："静态 vs 距离向量"不成对立。 静态路由不交换信息，不在第二根轴上。

易错：BGP 求的是"可达且比较好"，不是最短路。 跨 AS 的代价没有可比性。

教材出处

• 谢希仁《计算机网络》（第 8 版）4.6.1 有关路由选择协议的几个基本概念，印刷版 p158–p159：
  • 静态与动态的划分见 p158——"静态路由选择也叫作非自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化"；"动态路由选择也叫作自适应路由选择……适用于较复杂的大网络"。
  • 分层次路由选择的两条理由（互联网规模太大导致路由表过大、交换路由信息占满带宽；许多单位不愿意外界了解自己网络的布局细节）同在 p158。
  • AS 的定义见 p158——"自治系统 AS 是在单一技术管理下的许多网络、IP 地址以及路由器，而这些路由器使用一种自治系统内部的路由选择协议和共同的度量。每一个 AS 对其他 AS 表现出的是一个单一的和一致的路由选择策略"；同页给出 IGP / EGP 的划分与"域间路由选择 / 域内路由选择"的命名。
  • IGP / EGP 名词的历史混乱（EGP 既是类别名也曾是具体协议名；IGP/EGP 与 IRP/ERP 的对应）见 p159。
• 谢希仁《计算机网络》（第 8 版）4.6.2 内部网关协议 RIP，印刷版 p161：Bellman-Ford 的最优子结构表述——"设 X 是节点 A 到 B 的最短路径上的一个节点。若把路径 A→B 拆成两段路径 A→X 和 X→B，则每一段路径 A→X 和 X→B 也都分别是节点 A 到 X 和节点 X 到 B 的最短路径"。
• 谢希仁《计算机网络》（第 8 版）4.6.3 内部网关协议 OSPF，印刷版 p164–p167：
  • LS 与 DV 交换内容的根本差别见 p164——OSPF "发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息"，而"对于协议 RIP，发送的信息是：'到所有网络的距离和下一跳路由器'"；同页给出洪泛法的定义与"当链路状态发生变化或每隔一段时间（如 30 分钟），路由器向所有路由器用洪泛法发送链路状态信息"。
  • 链路状态数据库同步与"这个数据库实际上就是全网的拓扑结构图……这个拓扑结构图在全网范围内是一致的"见 p164–p165。
  • 收敛速度的实测量级见 p167——"由于 OSPF 没有'坏消息传播得慢'的问题，据统计，其响应网络变化的时间小于 100 ms"。
• 谢希仁《计算机网络》（第 8 版）4.6.4 外部网关协议 BGP，印刷版 p168–p169：
  • 跨 AS 不能用"代价"作度量的理由见 p168——"对某 AS 来说，代价为 1000 可能表示一条比较长的路由。但对另一 AS，代价为 1000 却可能表示不可接受的坏路由。因此，对于自治系统 AS 之间的路由选择，要用'代价'作为度量来寻找最佳路由也是很不现实的"；同页给出主干网转发表"项目数甚至可达到 50 万个网络前缀"。
  • BGP 的目标口径见 p169——"边界网关协议 BGP 只能是力求选择出一条能够到达目的网络前缀且比较好的路由（不能兜圈子），而并非要计算出一条最佳路由"；同页点明"BGP 采用了路径向量（path vector）路由选择协议"。

相关知识

网络层功能：路由、转发与异构网络互联｜RIP 路由协议｜OSPF 路由协议｜BGP 路由协议｜路由器与三层转发

上一篇网络层功能：路由、转发与异构网络互联下一篇IP 数据报格式

相关文章

• 网络层功能：路由、转发与异构网络互联
• IP 数据报格式
• IP 编址与子网划分
• IP 分片与重装
• ARP 地址解析协议
• ICMP 协议
• RIP 路由协议
• OSPF 路由协议
• BGP 路由协议
• NAT 网络地址转换
• IPv6
• IP 多播与 IGMP
• 移动 IP
• 路由器与三层转发
• SDN 软件定义网络

真题练习

相关真题（3题）

2021Q372分2016Q372分2010Q352分