波仔
📚 第七章 路由协议
📄 一句话概括

每台路由器先拼出「整张地图」，再自己算最短路树。 它知道全局，所以不会互相骗——代价是要存图和算 Dijkstra。

📝 本节和前面几节的关系

7.3.1 讲了「只信邻居」的毛病，这一节讲另一种答法。 这是 OSPF 和 IS-IS 的内核，也是「为什么要泛洪」的答案。

一、把「结论」换成「原料」

距离向量告诉邻居「我到各处多远」，链路状态告诉邻居「我周围有哪些链路、代价多少」。 前者是结论，后者是原料。 这个改变带来的第一个后果是「消息变多了」： 一条链路的状态要在全网扩散（泛洪），而不是只告诉邻居。 第二个后果是「每台都能自己验算」——因为手里有全图，算出来的路不依赖任何人的说法。 这就是它不会「计数到无穷」的根本原因： A 拿到全图之后，一眼就看到「C 后面那个网段没有链路连着」。 它不需要等 B 告诉它「我没路了」，它自己算出来就没有。 信息完整，骗局就无从发生。

二、Dijkstra 怎么算

算法只有三步，反复做：

一、在所有「还没定」的点里，挑「当前距离最小」的那个，把它定下来。 二、拿它去刷新邻居的距离（如果经它走更近就更新）。 三、回到第一步，直到所有点都定下来。

「定下来的点不会再改」是这个算法最关键的性质， 因为「任何绕远路的走法都比现在这条长」—— 既然现在这条已经是最小的，那就不可能存在更短的绕法。 这个推理成立的前提是「所有链路代价非负」，所以 Dijkstra 不能处理负权边（网络里没有负代价， 所以没关系）。 复杂度是「点数平方」，用堆优化可以到「边数加点数乘对数」。 对一张几千个节点的图，一次计算几毫秒——所以「收敛快」不只是「报文发得快」，也是「算得快」。

三、代价是什么

第一是内存：每台都要存整张图。 一百台路由器，每台要存一百条链路状态——这在一万台规模的网络里就是「每台存一万条」。 所以链路状态协议必须「划区域」（7.5.4），把图切小，让每台只需要存自己那个区域。 第二是泛洪：一条链路变了，要在全网扩散。 网络越大，这一波越猛。 所以链路状态协议都有「抑制频繁变化」的机制——比如「同一条链路 5 秒内只泛洪一次」。 第三是「初次同步慢」：两台路由器刚建邻居时，要把各自的图对齐，这个过程要传不少数据。 所以链路状态的路由器「刚起来的那几十秒」是最忙的—— 这也是「重启路由器要等一会儿才能恢复流量」的原因。

四、两种算法怎么选

不是「新的赢」，是「看规模」：

场景 距离向量 链路状态
小网（十来台） 够用、简单 过剩
中网（几十到几百） 收敛慢、易出环 合适
大网（上千） 不行 必须划区域
内存极小设备 能跑 存不下图

第四行是距离向量「至今没死透」的原因： 有些嵌入式设备、老工控设备，内存只有几十 KB，存不下拓扑图。 它们只能跑 RIP，而 RIP 在这些场景里也确实够用——因为网本来就小。 所以「技术选型」这件事，从来不是比参数，而是「在你的约束下，哪个代价更小」。 约束包括内存、带宽、人的水平、排错工具——最后一项常被忽略，但它往往是决定性的。

五、动手 Demo：链路状态算法怎么算最短路

六节点九条边的图，从 A 出发跑一遍 Dijkstra。 每一行是「这一轮定下了哪个点，剩下的候选变成多少」。

E = [('A','B',4), ('A','C',2), ('B','C',1), ('B','D',5),
     ('C','D',8), ('C','E',10), ('D','E',2), ('D','F',6),
     ('E','F',3)]
g = {n: {} for n in 'ABCDEF'}
for a, b, c in E:
    g[a][b] = g[b][a] = c

dist = {n: 10**9 for n in g}
dist['A'] = 0
done = []
while len(done) < len(g):
    cur = min((n for n in g if n not in done), key=lambda n: dist[n])
    done.append(cur)
    for nb, c in g[cur].items():
        if dist[cur] + c < dist[nb]:
            dist[nb] = dist[cur] + c
    print(cur, dist[cur], {n: dist[n] for n in g if n not in done})

实跑输出：

--------------------------------------------------------------------
链路状态算法怎么算最短路
--------------------------------------------------------------------
**链路状态（Dijkstra）走的是另一条路**：**每台路由器先把「整张地图」拼出来，再自己算最短路树。**
**它知道全局，所以不会互相骗。**

  链路      代价
  ---------------
  A — B     4
  A — C     2
  B — C     1
  B — D     5
  C — D     8
  C — E     10
  D — E     2
  D — F     6
  E — F     3

  选中的点     它到 A 的距离     剩下的候选（点 距离）
  -------------------------------------------------------
  A            0                 B 4、C 2、D ∞、E ∞、F ∞
  C            2                 B 3、D 10、E 12、F ∞
  B            3                 D 8、E 12、F ∞
  D            8                 E 10、F 14
  E            10                F 13
  F            13                —

**每一轮都挑「当前最近的那个点」定下来，然后拿它去刷新邻居。**
**定下来的点不会再改**——**因为「任何绕远路的走法都比现在这条长」。**
**这是 Dijkstra 正确的核心，也是它不会出现「互相骗」的原因。**

  目的地     最短路                    总代价
  --------------------------------------------
  B          A → C → B                 3
  C          A → C                     2
  D          A → C → B → D             8
  E          A → C → B → D → E         10
  F          A → C → B → D → E → F     13

**注意 A 到 E 那条**：
**直观看 A→C→E 是 2 加 10 等于 12，但 A→C→B→D→E 是 2 加 1 加 5 加 2 等于 10。**
**「看起来更近」不等于「代价更小」**——**这就是为什么要算，不能靠眼估。**

每一轮都挑「当前最近的那个点」定下来，然后拿它去刷新邻居。 定下来的点不会再改——因为「任何绕远路的走法都比现在这条长」。 这是 Dijkstra 正确的核心，也是它不会出现「互相骗」的原因。 注意 A 到 E 那条： 直观看 A→C→E 是 2 加 10 等于 12，但 A→C→B→D→E 是 2 加 1 加 5 加 2 等于 10。 「看起来更近」不等于「代价更小」——这就是为什么要算，不能靠眼估。 这个例子还说明一件事： Dijkstra 算出来的不是「一条路」，是「一棵树」—— 从 A 到所有点的最短路，合起来正好是一棵树（叫最短路树）。 路由器真正存的就是这棵树：「去每个目的地，下一跳是谁」。 所以它算完一次，就能填满整张路由表。

30 秒实验

  1. 算一下：A 到 E 走 A→C→E 和 A→C→B→D→E 各是多少？
  2. 想一下：为什么「定下来的点不会再改」？这个性质依赖什么前提？
  3. 想一下：一万台路由器的网，每台存一万条链路状态，内存吃得消吗？

常见误区

  1. 以为「链路状态不用泛洪」。 泛洪是它的核心动作，只是「有变化才泛洪」。
  2. 以为「Dijkstra 能处理负权边」。 不能，它的正确性依赖「代价非负」。
  3. 以为「算出来的是一条路径」。 是一棵树，从自己到所有点的最短路。
自测三问（点开对答案） 1. 链路状态和距离向量最本质的区别？ —— **邻居告诉我的是「结论」还是「原料」**，后者能自己验算。 2. 为什么它不会计数到无穷？ —— **手里有全图**，路断了一眼看得出来，不靠传闻。 3. Dijkstra 的三个代价是什么？ —— **存图占内存、泛洪占带宽、初次同步慢。**

下一节把三种协议摆在一起对比。

相关笔记