Appearance
路由算法：距离向量 vs 链路状态
考情分析
路由算法是网络层的算法层面知识，与具体协议（RIP、OSPF、BGP）相辅相成——算法是骨架，协议是肉。本文聚焦"算法层面"的通论，具体协议见 RIP、OSPF、BGP。
题型集中在三类：
- 距离向量更新过程（2010, 2016）——给出邻居的距离向量，问本机更新后的路由
- 链路状态算法的最短路计算（2021）——给出全网拓扑，模拟 Dijkstra
- 静态 / 动态 / 层次路由的概念辨析
考频：★★★
路由算法的分类轴
408 大纲把路由算法按三个独立的轴划分，每个轴都可能出题。
| 划分轴 | 类别 1 | 类别 2 |
|---|---|---|
| 是否随网络变化自适应 | 静态路由（手工配置） | 动态路由（协议自动算） |
| 邻居信息交换方式 | 距离向量（DV） | 链路状态（LS） |
| 是否分层 | 平面路由 | 层次路由（AS 内 / AS 间） |
三个轴是正交的——同一个路由协议可以同时被几个轴标记，比如"RIP = 动态 + 距离向量 + 域内（在 AS 内部用）"。
静态路由 vs 动态路由
| 维度 | 静态路由 | 动态路由 |
|---|---|---|
| 配置者 | 网络管理员手动配置 | 路由协议自动学习 |
| 反应链路变化 | 不能（除非人工改） | 能（协议自动收敛） |
| 协议开销 | 0（无需通信） | 周期性或事件触发的协议报文 |
| 适用场景 | 小型、稳定、对路径有刻意控制要求的网络 | 中大型、拓扑可能变的网络 |
| 安全性 | 高（手动控制） | 受协议本身漏洞影响 |
静态路由不是"过时"——大型骨干网仍会用静态路由强制特定路径，特别是出口指向 ISP 的默认路由几乎都是静态的。
距离向量算法
基本思想（Bellman-Ford）
每台路由器维护一张"到所有目的网络的距离表"，周期性把整张表发给所有直连邻居。收到邻居发来的距离向量后，按下式更新自己：
含义：x 到 y 的距离 = 在所有直接邻居 v 里挑一个，使得"x 到 v 的链路代价 + v 自己声称到 y 的距离"最小。
RIP 中的实例
RIP 是距离向量算法的代表，约定俗成：
- 度量值 = 跳数（hop count）
- 16 = 不可达（实际可达跳数最大 15）
- 每 30 s 向邻居广播一次完整的距离表
- 180 s 内未收到某邻居的更新，则认为该邻居失联
2016 真题第 37 题：R3 直连 Net2，距离 0；R2 邻居 R3，距离 1；R1 邻居 R2，距离 2。这是个故障恢复场景——R3 检测到 Net2 不可达后，按 RIP 规则发出"我到 Net2 距离 = 16（不可达）"的距离向量。R2 收到 R3 的更新（R3 是 R2 通向 Net2 的下一跳），必须接受这个坏消息，把自己到 Net2 的距离更新为 17，但 RIP 把 ≥16 全部当成不可达 → 答案 16（C）。
这里有个细节：R2 是否会按"R3 不可达就 R2 也不可达"逻辑直接置 16？关键看"R3 是不是 R2 到 Net2 的当前下一跳"。是 → 必须更新；不是 → 不受影响。
距离向量的两个老大难
1. 无穷计数（count-to-infinity）问题
A→B→C 的链路里，C 故障后，B 把"到 C 距离 = ∞"告诉 A；但如果 A 此前因周期性更新先告诉 B "我到 C 距离 = 2（经过 B）"，B 可能误以为"我经过 A 还能到 C"而更新成 3，A 又跟着变 4……如此累加到 16 才能停止收敛。
RIP 用"16 = 不可达"截断这种发散，代价是网络规模被限制在 15 跳之内。
2. 慢收敛
每 30 s 才一次更新 + 经过多跳传递，距离向量协议的收敛常常是数十秒级的。
防环措施（了解性）
- 水平分割（split horizon）：不把从某邻居学来的路由再发回去
- 毒性逆转（poisoned reverse）：不仅不发回去，还把距离改成 16 主动告诉邻居"别走我"
- 触发更新（triggered update）：度量值变化时不等周期，立即发更新
链路状态算法
基本思想（Dijkstra）
每台路由器只把"自己的本地链路状态"（直连了哪些邻居、各链路代价）洪泛给整个 AS 内的所有路由器。每台路由器收到所有这些"链路状态通告"后，各自独立构建出完整的网络拓扑图，然后跑 Dijkstra 算出到所有目的的最短路。
OSPF 中的实例
- 链路状态通告（LSA, Link State Advertisement）：链路变化时立刻向所有路由器洪泛
- 每个路由器都拥有全网相同的链路状态数据库
- 在数据库上跑 Dijkstra，得到本机的最短路径树
- 收敛快（秒级）
2021 真题第 37 题：拓扑给了 E 到邻居 A、B、C、D 的直连代价（8、10、12、6），又给了邻居们向 E 报告的"邻居到各目的网络的距离向量"（注意题面虽给"距离向量"，但算法本质是 LS —— 因为这相当于 E 已经拥有全网拓扑信息，在自己头脑里独立跑 Dijkstra）。
E 到 Net1：候选路径 {E→A→Net1 = 8+1=9, E→B→Net1 = 10+23=33, E→C→Net1 = 12+20=32, E→D→Net1 = 6+22=28}，最小 9。 E 到 Net2：min(8+12, 10+35, 12+30, 6+28) = 20。 E 到 Net3：min(8+24, 10+18, 12+16, 6+36) = 28。 E 到 Net4：min(8+36, 10+30, 12+8, 6+24) = 20。
答案 D：9, 20, 28, 20。
距离向量 vs 链路状态（核心对照）
| 维度 | 距离向量（DV） | 链路状态（LS） |
|---|---|---|
| 算法本质 | Bellman-Ford | Dijkstra |
| 每个路由器看到的"全局" | 不完整，只知道"邻居说它能到哪" | 完整网络拓扑图 |
| 发送什么信息 | 自己的整张距离向量 | 自己的链路状态 |
| 发给谁 | 仅直连邻居 | 洪泛到全 AS |
| 何时发 | 周期性（30 s）+ 触发 | 链路状态变化时立刻 |
| 收敛速度 | 慢，可能"无穷计数" | 快 |
| 协议开销 | 每条更新很大（整张表），更新频率低 | 每条更新很小（一条链路），更新频率事件驱动 |
| 内存占用 | 小（只存路由表） | 大（存完整拓扑数据库） |
| 典型协议 | RIP | OSPF |
记忆口诀："DV 是聋子摸象，LS 是上帝视角"。
层次路由
为什么要分层？因特网规模太大，所有路由器跑同一个全局协议会内存爆炸、收敛灾难。
自治系统（AS）
AS（Autonomous System）：一群在同一管理实体下、采用统一域内路由协议的路由器集合。每个 AS 有一个 AS 号。
域内 vs 域间
| 层次 | 协议类型 | 代表 | 关注点 |
|---|---|---|---|
| 域内路由（IGP） | Interior Gateway Protocol | RIP、OSPF | AS 内最短路径 |
| 域间路由（EGP） | Exterior Gateway Protocol | BGP | AS 之间的路由策略（不只看最短，还看商业关系） |
路径向量（path vector）
BGP 用的是路径向量算法——既不是纯距离向量，也不是链路状态。每条 BGP 路由不只带"距离"，还带完整经过的 AS 序列，这样：
- 看到自己的 AS 号在序列里 → 直接丢弃，避免环路
- 可以基于"路径是否经过某些 AS"做策略
通论考点速查
| 算法 | 信息来源 | 计算者 | 算法核心 | 典型协议 |
|---|---|---|---|---|
| 距离向量 | 邻居告诉我"它的距离" | 路由器本机迭代 | Bellman-Ford | RIP |
| 链路状态 | 全网洪泛 LSA | 路由器本机独立跑 | Dijkstra | OSPF |
| 路径向量 | 邻居 AS 告诉路径列表 | 路由器本机按策略过滤 | DV 的扩展 | BGP |
易错点
1. 距离向量协议不需要邻居知道全网拓扑
每台路由器只知道"经过某邻居能到哪、多少代价"，不知道邻居之间的拓扑。这是 DV 简单但收敛慢的根本原因。
2. 链路状态协议中"每个路由器都有相同的链路状态数据库"是关键不变量
如果数据库不一致，路由器算出的路径就会不一致，可能产生环路。OSPF 通过严格的 LSA 同步机制保证数据库一致。
3. RIP 的 16 不是"很大的数"，是"不可达"的约定
学生看到 16 容易理解成"距离很远"，应当理解为协议层面的特殊值。15 跳就是 RIP 网络的最大直径。
4. 链路状态算法不"逐跳"传递路由信息
LSA 是洪泛（flooding）——每个收到 LSA 的路由器都向除来源外的所有接口转发，不像 DV 那样"我告诉邻居，邻居告诉邻居"。
5. 静态路由不是"低端"，骨干网大量使用
大型 ISP 出口、跨 AS 边界、需要强制路径的安全网络都用静态路由。"静态/动态"是选型问题，不是优劣问题。
6. AS 内可以同时跑多种协议
实务中一个 AS 可能内部跑 OSPF + 部分静态路由 + 与外部对等点用 BGP。"AS 用什么协议"不是单选题。
高频考点清单
- 三个分类轴（静态/动态、DV/LS、平面/层次）
- DV 的递推公式
- RIP 中 16 = 不可达，最大 15 跳
- 无穷计数问题与防环措施（水平分割、毒性逆转、触发更新）
- LS 算法的洪泛 LSA + 各自跑 Dijkstra
- DV 与 LS 的全方位对比（信息范围、算法、收敛速度、典型协议）
- AS / IGP / EGP / 路径向量的概念