《计算机网络》中，出现的那些算法设计 - 01

从《计算机网络》（谢希仁）出发，讨论其中体现的算法设计思想，并介绍CRC、DP、LPM等算法在网络算法中的软硬件实现方式以及工程情况中算法迭代的体现。

Loading…

《计算机网络》中，出现的那些算法设计 - 01

我的学校计算机网络和算法设计与分析开在了同一个学期，所以在学习网络相关的知识时，我察觉到有非常多软件方面的设计与算法设计中的思路高度重合。所以本文想聊一聊网络中的那些经典算法，探究下他的原理以及说明他是如何实现的。

由于我的学校使用的计算机网络学习路径是自底向上的，所以本文会先讲解物理层、数据链路层以及网络层的经典算法，对于传输层与应用层，我会放到接下来的博客中来聊，故本系列预计有两篇文章。

1. 网络算法与通用软件算法的异同

在开始解读具体算法前，先要明确下网络算法相较于我们之前博客里说的比较多的通用软件算法的一些特性。

首先是输入的不同。像我们之前博客里聊过的回溯搜索、Tarjan算法等这些运行在本机软件层的算法，他们面对的往往是一个有限的、短期内静态的数据：输入一组用户的信息、输入一些节点的数据，输入集在算法开始运行前就给齐了，在运行结果出来前输入集也不会改动。但是对于网络算法来说不一样：包是分批次抵达的、数据报是连续传送的，他没有像通用软件那样固定的“输入结束”的时刻，所以他面对的是连续的、动态的输入集；而网络算法需要面对连续输入时，在有限的截至时间内得出“包从哪个端口转发”、“转发表是否要更新/怎样更新”、“这个包是否要丢弃”等结论。

其次是算法流程。网络中，一个功能往往不是独立的一个算法实现的，甚至都不一定是在一个平面中完成的，导致其并非是通用软件那种常见的单机算法，而更像一套分布式系统。例如 OSPF 中选取路由，控制面上软件实现了 Dijkstra 算法，但是最终选取路由是在数据面的硬件或者内核快路径通过查表来完成选取。这样设计的原因是对于数据面来说，由于同时要处理大量的包，每个包的处理时延被要求在纳秒级别，这种速度是软件难以企及的；对于 Dijkstra 以及哈希查询，这些操作在软件上是毫秒甚至秒级的，所以不能让一个功能完全由一个平面完成。所以网络算法会形成一个独特的结构：控制面的软件实现秒级/事件级的算法，为数据面提供数据基础；数据层则通过走硬件或内核快路径，在纳秒级/单包级的时间中完成最长前缀匹配、ACL、CRC等算法，并不要求控制面能跟上他的速度，只需要在网络结构或者网络情况变化时，控制面能及时提供更新；管理面通过软件，在分钟级的处理频率下完成对网络的配置、监控等。

另外一个重要区别就是算法的具体实现。由于网络算法的流程里有赖多个平面的协作，所以算法设计是需要考虑在硬件上的实现是否快速、稳定、方便。比如像最长前缀匹配，在计算机软件上的更优实现是二叉Trie，相同时间复杂度下它更省内存，但是由于 IPv4 最坏要走 32 层，每层一次访存，而且后一次访存依赖前一次的结果，可能会导致指针追逐、延迟叠满；所以最长前缀匹配在硬件上的实现被 Multibit Trie 取代，它虽然耗费内存，但是可以压低层数；之后 Multibit Trie 又被 TCAM 取代，使用并行的计算方式，以更小的容量但更高的功耗成为了当前网络算法中前缀匹配的常用算法。

但是归结到算法核心思想，网络算法和通用软件算法其实是相同的，只不过网络中的算法设计说是Algorithm Designing，其实更像是Algorithm Engineering，它很难像通用软件算法那样去追求理论最优，而是需要结合现实情况选取抗逆性更强的方案。

2. 物理层

很多人刚学物理层的时候，会觉得这一层基本就是硬件工程师的领地——全是电压、双绞线、光纤、接口引脚定义，跟“算法”没什么关系。但如果我们顺着第一节说的“流式输入”往下想，物理层其实面临着两个非常棘手的前置问题：

发送方把一串 0 和 1 变成高低电平发出去，中间并没有额外拉一根专门的“时钟线”告诉接收方每一拍有多长；如果数据里恰好出现了一长串连续的 0 或者连续的 1，接收方看着一条毫无波澜的水平电压线，怎么知道里面到底有几个 0？
如果多台设备接在同一个物理信道、甚至使用同一个频段同时发信号，电磁波在空间里直接叠成了一团乱麻，接收方又该怎么把各自原本的 0 和 1 拆出来？

这两个问题，分别对应了物理层里最经典的基带线路编码与 CDMA（码分多址）。

2.1 基带编码与曼彻斯特编码：多约束下的流式状态编码

先看第一个问题。在基带传输里，最符合直觉的编码方式是不归零制（NRZ，Non-Return-to-Zero）：高电平代表 1，低电平代表 0，一个比特周期内电平保持不变。

这种做法的优点是不言而喻的：每个比特周期最多只需要改变一次电平状态，码元速率（波特率）就等于比特率，频带利用率拉满。但在真实的物理信道上，NRZ 根本没法直接裸跑。原因有两个：

时钟失步（Clock Drift）：接收端的晶振和发送端的晶振永远不可能做到物理意义上的绝对同步。哪怕两边的时钟频率只差百万分之一，只要数据流里出现几十个连续的 0 或 1，电平长时间不发生跳变，接收端就找不到校准节拍的参考点，多读一位或少读一位就会导致整帧后续比特全部错位；
直流分量累积（DC Wander）：如果一段数据里 1 明显多于 0，信号平均电压就会长期偏正；而网卡接口处的隔直电容、脉冲变压器是通高频阻低频的，长期偏置会让接收端的判决基线发生漂移，干扰对接收信号的判断。

换句话说，物理层需要一种编码算法，把输入的任意 0/1 比特流 $b_0, b_1, b_2 \dots$ 实时映射成电平序列，同时满足两个硬约束：不能出现长串无跳变的水平线，且正负电平出现的时间必须严格对半抵消。

10 Mb/s 传统以太网采用的曼彻斯特编码给出的解法非常直接：把“时钟信号”和“数据信号”用异或揉进同一个波形里。

它的编码规则是：不再用“高/低电平本身”表示 0 和 1，而是强制要求每一个比特周期的正中间必须发生一次电平跳变。在如我们学校采用的《计算机网络》（谢希仁）教材采用的以太网约定中：

位周期中心由高向低跳变（下跳） 代表比特 1（即前半周期高电平 +V，后半周期低电平 -V）；
位周期中心由低向高跳变（上跳） 代表比特 0（即前半周期低电平 -V，后半周期高电平 +V）。

而它的改进版差分曼彻斯特编码则在此基础上做了一步“相对化”：位周期中心的跳变只纯粹充当时钟信号，至于数据是 0 还是 1，看的是当前位周期开始处相对于上一位末尾有没有发生跳变；边界有跳变代表 0，边界不跳变代表 1。这样即使传输双绞线的正负极不小心接反导致电平整体上下翻转，只要看跳变关系，依然能正确还原出数据，抗干扰能力更强。

基带信号编码对比

不归零制（NRZ）、曼彻斯特编码与差分曼彻斯特编码对比：中心强制跳变天然携带时钟节拍

如果用算法状态机的视角来看，这两种编码其实就是两个 $O(1)$ 状态的流式转换器（Mealy 状态机）：每读入 1 个数据比特 $b_i$ ，输出 2 个半周期的电平码元 $(s_{2i}, s_{2i+1})$ ：

cpp

// 输入一个比特 b (0 或 1)，输出两个半周期电平 (+1 或 -1)
// 1. 曼彻斯特编码：无状态映射（等同于数据比特与时钟方波做异或）
pair<int, int> manchester_encode(int b) {
    if(b == 1) return {+1, -1}; // 中心下跳为 1
    else return {-1, +1}; // 中心上跳为 0
}
 
// 2. 差分曼彻斯特编码：带 1-bit 历史状态的流式状态机
struct

仔细看这两个函数返回的电平对，无论是 {+1, -1} 还是 {-1, +1}，每一个比特内部的正负电平之和永远等于 $0$ ，直流分量被彻底清零，不会因为直流分量的偏移而无法正确解析接收信号；而且通过一个比特周期内强跳变，最长不跳变的时间不会超过一个比特周期，接收端靠锁相环（PLL）盯着中心跳变就能稳定锁住时钟。

如此一来，我们就很好回答一个关于以太网帧的问题：以太网 MAC 帧为什么只有帧开始定界符，却不需要帧结束定界符？ 就是因为只要发送方发完最后一个比特、停止驱动信道，总线上不再出现每周期必有的中心跳变，接收方只要检测到超过一定时间没有跳变，就能判定“这一帧结束了”。

但是曼彻斯特编码也有自己的代价，为了塞进时钟，这种编码把原本 1 个码元就能传 1 bit 的信道，拆成了 2 个半周期码元传 1 bit——也就是说，波特率（码元速率）变成了比特率的 2 倍，频带利用率只有 50%。在 10 Mb/s 以太网上，网卡实际需要以 20 MBaud 的速率翻转电平。到了百兆以太网（100BASE-TX，IEEE 802.3u规范）和光纤网络，把 100 Mb/s 以太网实际需要 200 MBaud 电平翻转速率会超出当时五类双绞线的频率上限；于是工程师把思路升级成了 4B/5B 编码与 8B/10B 编码：不再死板地每1位插1次跳变，而是查一张精心构造的哈希/映射表，把每 4 位数据映射成 5 位码字（在 $2^5 = 32$ 种组合里挑出 16 个“开头最多 1 个 0、结尾最多 2 个 0”的码字），确保拼接后永远不会出现超过 3 个连续的 0。这样只多花 25% 的冗余码元，就把频带利用率从 50% 拉回到了 80%。

2.2 CDMA 码分多址：正交向量空间里的信号解耦

聊完一根线上的单路编码，我们再来看多路复用。

当多个用户需要共享同一条物理信道时，频分复用（FDM）的思路是“按频率切蛋糕”，每人占一段频带；时分复用（TDM）的思路是“按时间排班表”，每人轮流占几毫秒。但这两种方案本质上都是在物理维度上把用户隔开，有没有一种在信息表示方式上就能实现区分的算法？

CDMA（Code Division Multiple Access，码分多址） 走了一条完全反直觉的路：所有用户在同一时间、使用完全相同的频段一起发送数据。但是失去了频率、时间等直观的物理属性，接收端如何从混杂的信息流中找到自己的信源？

除去通信术语的外壳，CDMA 就是线性代数里正交向量空间与内积投影的应用。

1. 码片序列与正交基构造

在 CDMA 系统中，每一个比特时间被进一步细分成 $m$ 个短间隔，称为码片（Chip），通常教材举例取 $m = 8$ （现在真实商用系统如 IS-95 中通常取 $m = 64$ 或 $128$ ）。

系统给每个站点指派一个唯一的、长度为 $m$ 的码片序列。为了方便做代数运算，我们把码片序列里的 0 写成 -1，1 写成 +1。于是，每个站点的码片序列就成了一个 $m$ 维向量 $\mathbf{S} = (s_1, s_2, \dots, s_m) \in \{-1, +1\}^m$ 。

为了避免干扰，分配给不同站点的码片向量必须严格满足两两正交（Orthogonal）。用教材里的“规格化内积（Normalized Inner Product）”来定义，对于任意两个站点 $S$ 和 $T$ 的码片向量 $\mathbf{S}$ 、 $\mathbf{T}$ ，必须满足两条性质：

自身与自身的规格化内积恒为 $1$ ： $\frac{1}{m} \mathbf{S} \cdot \mathbf{S} = \frac{1}{m} \sum_{i=1}^{m} s_i^2 = \frac{1}{m} \sum_{i=1}^{m} (\pm 1)^2 = 1$ 自然地，自身与自身反相向量的规格化内积为。

这让我联想到机器学习，把 1 个比特扩频成 $m$ 维码片向量，很像神经网络里的 Embedding 将离散符号升维映射到高维向量空间的过程；只不过大模型里的 Embedding 追求的是在余弦相似度非 0的前提下，让语义相近的词在空间里靠得更近，而 CDMA 追求的是彻底的解耦——它分配给各个基站的码片向量，严格构成了 $m$ 维空间里的一组标准正交基（两两正交且规格化自内积为 $1$ ），任何叠加信号都能在这组正交基下唯一地线性表出。

如果有 $m$ 个基站，该怎么快速构造出 $m$ 个长度为 $m$ 且两两正交的 $\pm 1$ 向量？利用 沃尔什-阿达马矩阵。它的构造过程是一个极其标准的分治法。当 $m = 2^k$ 时，我们可以从 1 阶矩阵 $H_{1} = [1]$ 出发，每次把规模扩大一倍，将原矩阵复制到左上、右上、左下三个象限，右下象限取相反数：

$H_1 = \begin{bmatrix} +1 \end{bmatrix}, \quad H_2 = \begin{bmatrix} +1 & +1 \\ +1 & -1 \end{bmatrix}, \quad H_{2n} = \begin{bmatrix} H_n & H_n \\ H_n & -H_n \end{bmatrix}$

不难用数学归纳法证明， $H_m$ 的任意两行（比如上半部分第 $i$ 行 $[row_i, row_i]$ 与下半部分对应行）做内积，前半段乘积与后半段乘积符号相反、恰好完全抵消，内积恒为；这就保证了我们总能在线性时间内生成一整套完备的正交码表。

2. 扩频发送、信道叠加与内积解调

有了正交码片向量，CDMA 的收发算法就非常简洁了：

发送端编码规则：若站点 $S$ 要发送比特 1，就在信道上直接发出自己的码片向量 $+\mathbf{S}$ ；若要发送比特 0，就发出反相码片向量 $-\mathbf{S}$ ；若当前周期不发数据，则发出全零向量 $\mathbf{0}$ 。
公共信道叠加：假设信道上有 $N$ 个站点同时工作，每个站点发出的信号向量为 $X_{i} \in {+$ 。只要电磁波处于线性工作区，空间中合成为总信号向量：

\begin{aligned} \frac{1}{m} \mathbf{S}_k \cdot \mathbf{X} &= \frac{1}{m} \mathbf{S}_k \cdot \left( d_1 \mathbf{S}_1 + \dots + d_k \mathbf{S}_k + \dots + d_N \mathbf{S}_N \right) \\ &= d_1 \underbrace{\left(\frac{1}{m}\mathbf{S}_k \cdot \mathbf{S}_1\right)}_{=0} + \dots + d_k \underbrace{\left(\frac{1}{m}\mathbf{S}_k \cdot \mathbf{S}_k\right)}_{=1} + \dots + d_N \underbrace{\left(\frac{1}{m}\mathbf{S}_k \cdot \mathbf{S}_N\right)}_{=0} \\ &= d_k \end{aligned}

从“拿一个专属模板去把无关信息抹零”的思想有点像后面网络层里的子网和超网，使用子网掩码与 IP 地址做按位与来提取网络号；但比掩码更精妙的是，子网掩码是靠按比特位做网络号和主机号的划分，而 CDMA 里每一个码片位置上都同时混着所有人的信号，它是靠整个向量的正负对称相消，在全局求和后让其他基站的干扰信号自动坍缩到 $0$ 。这样一来，如果最终算出来的结果是 $+1$ ，说明站点 $k$ 发了比特 1；如果是 $-1$ ，说明发了比特 0；如果是 $0$ ，说明目标站点 $k$ 这一轮没有发出信息。

CDMA 正交码片扩频、信道线性叠加与内积解调

CDMA 完整计算过程：发送端扩频为正交向量，信道上线性相加，接收端靠内积投影无损剥离各站数据

我们可以用一段简短的 C++ 代码把包含 Walsh 矩阵构造、多站叠加和内积解调的全过程模拟出来（这里使用的具体数值例子就是上图的数值）：

cpp

#include <iostream>
#include <vector>
using namespace std;
 
// 分治法生成 m×m 的 Walsh-Hadamard 正交码片矩阵 (m 为 2 的幂)
vector<vector<int>> build_walsh(int m) {
    if (m == 1) return {{1}};
    auto half = build_walsh(m / 2);
    vector<vector

从算法与工程的结合来看，CDMA 最迷人的地方在于它换了一个维度看“冲突”：既然在时间（TDM）和频率（FDM）这两个一维坐标轴上躲不开碰撞，那就通过 $m$ 倍扩频，把信号映射到 $m$ 维线性空间里的一组标准正交基上。虽然数据速率被码片速率稀释了 $m$ 倍（需要占用更宽的频带，即扩频通信），但换来的是 $m$ 个用户可以在同一时频资源上并行传输，甚至连外来的窄带噪声在做完内积除以 $m$ 后也会被平均摊薄。

3. 数据链路层

如果说物理层眼里只有连续流淌的电压波形与正交向量，那么到了数据链路层，数据的基本单位就变成了有头有尾的帧（Frame），视野也扩展到了“一条链路的收发两端”以及“同一个局域网内的多个竞争站点”。

在这一层里，我们将依次看到三种截然不同的算法范式：

在网卡硬件数据面以纳秒级速度运行的流式状态机与有限域 $\text{GF}(2)$ 多项式代数（零比特填充与 CRC）；
在没有中心裁判的广播总线上靠概率破除对称死锁的分布式随机化算法（CSMA/CD 与截断二进制指数退避）；
在交换机网络中靠局部消息收敛出全局无环拓扑的在线缓存学习与分布式最小生成树（交换机自学习与 STP）。

3.1 透明传输与 CRC 循环冗余校验：流式自动机与 $\text{GF}(2)$ 多项式除法

1. 边界：帧定界与零比特填充 - 流式状态机

数据链路层要干的第一件事是“封装成帧”。比如在同步串行链路（HDLC 或 PPP 同步传输）上，协议规定用一串特殊的 8 位比特组合 01111110（即十六进制 0x7E）作为每一帧开头和结尾的标志字段（Flag）。

那老问题马上就来了：如果上层传下来的 IP 数据报正文里，恰好也长了一段 01111110，接收方读到这儿不就误以为这一帧已经提前结束了吗？这就是教材里说的**透明传输（Transparency）**问题（之所以叫“透明”，是指数据链路层对上层交付的数据应当像透明玻璃一样“视而不见”，无论上层数据里出现什么样的比特组合，链路层都不能把它误判成控制指令而截断，保证层间互不干扰）。

类比到我们写计算机软件，比如在 C++ 等语言中处理字符串，我们会用 \ 转义符把特殊字符（比如 "、\ 本身等）转化成普通字符；异步 PPP 里也是完全相同的思路，通过使用字节填充，把正文里出现的定界符 0x7E 转义成 0x7D 0x5E，即若正文里出现转义符 0x7D 本身，则转义成 0x7D 0x5D。但如我们前言所说，在按比特流式收发的同步硬件链路上，不可能把整帧存下来慢慢查找替换，必须做到边收边转、只看当前 1 个比特就能立刻决定动作。

**零比特填充法（Bit Stuffing，又称“逢五插零”）**实现了这一点：

发送端状态机：维护一个只记连续 1 个数的 3-bit 计数器 ones。每发出 1 个数据比特，若为 1 则 ones++，若为 0 则 ones = 0；一旦发现 ones == 5，不管下一位数据是什么，硬件当场强行往信道里多塞一个 0，并将计数器清零。这样一来，正文数据里绝对不可能出现连续 6 个 1，定界符 01111110 的唯一性就被锁死了；
接收端状态机：同样数连续 1 的个数。一旦数到 5 个连续的 1，就看紧接着的第 6 位：如果是，说明这一定是发送端塞进来的填充位，直接丢弃即可；如果是（再配第 7 位，凑成），说明真的撞上了帧尾定界符，当前帧接收完毕。

仅仅靠一个 3-bit 的寄存器，就在连续比特流上实现了无二义性的可逆编解码，这就是数据面流式算法的一个经典设计。

2. 检验：CRC 为什么要用“模 2 除法”？

帧的边界切出来了，接下来要解决“比特在路上被噪声翻转了怎么发现”的问题，在计算机组成原理中我了解过多种检验方法，比如奇偶校验、海明校验等等，在链路层我们常用的是 CRC 循环冗余检验。

CRC的计算方式老生常谈：“生成多项式化成二进制除数 $P$ $\to$ 数据后面补 $r$ 个 $0$ $\to$ 做不借位的异或除法求余数 $R$ ”（对于CRC的计算方法，我非常推荐b站的这条视频[CRC校验]手算与直观演示，up 把 CRC 的计算过程讲的很细，并附上了硬件上的抽象实现）。但应该有不少人在学习时好奇过：为什么偏偏要把它看成多项式？为什么加减法不进位也不借位？为什么这样算出来的余数贴在帧尾，就能把传输错误抓出来？

要解释清楚这件事，我们得走进抽象代数里的二元有限域 $\text{GF}(2)$ （即伽罗瓦域 $\mathbb{F}_2$ ），这有点越过了CS学生本科阶段的学习内容，但是为了知根知底，还是需要深入探究一下。

在平时熟悉的实数域里，数字有无穷多个，加减法要满十进一、退一当十；而在只包含 $\{0, 1\}$ 两个元素的有限域 $\text{GF}(2)$ 中，加法和减法都是在模 2 意义下进行的： $0 \pm 0 = 0, \quad 1 \pm 0 = 1, \quad 0 \pm 1 = 1, \quad 1 \pm 1 = 0$ 你会发现一件很有趣的事：！没有进位，也没有借位，每一位都完全独立。

在这个域上，任意一串长度为 $k$ 的二进制数据 $M = m_{k-1}m_{k-2}\dots m_1m_0$ ，都可以唯一对应成一个最高次幂为的多项式，其中比特值就是每一项的系数：例如谢希仁先生教材上的例子（共 6 位），对应的多项式就是。

现在，收发双方预先约定好一个最高次幂为 $r$ 的生成多项式 $G(x)$ （比如 $G(x) = x^3 + x^2 + 1$ ，对应，二进制系数串，共位）。CRC 的核心构造只有四步：

左移腾位置：在数据 $M$ 尾部补上 $r$ 个 0。在多项式看来，这相当于给 $M(x)$ 乘上了 $x^r$ ，得到了 $M(x)\cdot x^r$ ，把最低的个次幂位置空出来留给校验码；

这个式子说明了：接收端算出来的余数是否为0，只取决于差错多项式 $E(x)$ 能不能被生成多项式 $G(x)$ 整除。

只要 $G(x)$ 挑得好，常见的错误模式 $E(x)$ 就几乎不可能被 $G(x)$ 整除：

单比特错： $E(x) = x^i$ 。只要 $G(x)$ 至少包含两项（首尾都是 1），就绝不可能整除单项式 $x^i$ ，100% 检出；
任意奇数个比特错：只要我们在设计 $G(x)$ 时让它包含因式，那么任何含有奇数个的差错多项式在代入时在下值为，必然不含因式，从而绝不可能被整除，；

CRC 循环冗余校验：GF(2) 模 2 多项式除法与硬件 LFSR 实现

左：教材经典例题的 GF(2) 模 2 竖式推演；右：对应生成多项式在网卡数据面的 LFSR 硬件电路实现

如果我们在本机软件里用 C++ 写一个完全忠于上述数学原理的逐位模 2 除法，代码其实就是一个带着异或掩码的滑动窗口：

cpp

#include <iostream>
#include <cstdint>
using namespace std;
 
// 计算数据 M 的 r 位 CRC 校验码（以教材例题 M = 101001, G = 1101, r = 3 为例）
uint32_t crc_remainder(uint32_t M, int k, uint32_t G, int r) {
    uint32_t dividend = M << r; // 1. 左移 r 位，相当于乘以 x^r（尾补 r 个 0）
    // 2. 从最高位 (k + r - 1) 往下逐位扫描到第 r 位
    for (int i = k +

顺带一提，在实际软件工程（如 zlib、Linux 内核）里计算以太网的 32 位 CRC-32（生成多项式最高次幂 $r=32$ ）时，一位一位异或还是太慢了；因为异或满足结合律和交换律，软件上通常会预先把“连续异或 8 次的所有 256 种可能结果”算好存进一张大小 256 的静态数组（Sarwate 查表法），每次直接按字节（8 bit）查表异或，速度能快近八倍。

而如果我们回到第一节聊到的“数据面硬件实现”，就会明白为什么所有二层协议（以太网、PPP、Wi-Fi）的帧尾无一例外全都选了 CRC，而没有选普通的算术校验和：

在普通算术加法里，低位相加产生的进位必须沿着“进位链”一路传到高位，位宽越宽，硬件门电路的传播延迟就越大；而在 $\text{GF}(2)$ 模 2 除法中，每左移一位并判断最高位是否为 1 异或 $G(x)$ 这个动作，翻译成硬件电路就是一个线性反馈移位寄存器（LFSR，见上图右侧，也可见上文推荐的视频）：只需 $r$ 个串联的触发器寄存器，在生成多项式系数为 $1$ 的次幂位置放几个异或门，把最右侧溢出的最高位反馈回去即可。

这意味着网卡在收发以太网帧的时候，根本不需要先把 1500 字节的帧存进内存再去算 CRC，比特流像流水一样从网线流进网卡物理层芯片，每过 1 个时钟周期流过 1 bit，LFSR 里的异或门就跳一次；等帧的最后一个数据比特流完的那一纳秒，寄存器里躺着的 $r$ 个比特，就已经是算好的 FCS 余数了，直接打开开关把它跟在帧屁股后面推上网线就行，做到了真正意义上的零等待流式计算。

3.2 CSMA/CD 与截断二进制指数退避：无中心环境下的随机化对称破缺

如果一条链路上只有两台机器点对点连着（比如 PPP），那把帧定好界、挂上 CRC 就可以放心发了。但是早期局域网（也就是传统总线型以太网）也要面对多台主机接入总线的情况：几十台主机直接挂在同一根同轴电缆（广播信道）上，没有中心交换机，也没有管理员给每台主机排使用时间表。要是两台主机同时往电缆上推电平，两股波形撞在一起就会相互篡改，变成一堆废码，这就是碰撞（冲突，Collision）。

为了解决这个无中心抢信道的问题，以太网发布了著名的 CSMA/CD（载波监听多点接入/碰撞检测） 协议。这个协议的核心就16个字：“先听后发、边听边发、冲突停发、随机重发”。

如果从算法设计的角度把这16个字拆开，里面其实藏着两处精彩的推导：前半句边听边发用物理传播时延倒推出了数据帧的空间下界（ $2\tau$ 时间）；后半句（随机重发）则用随机化算法解决了分布式系统的对称性死锁。

1. 争用期 $2\tau$ 与最短帧长 64B：时间窗口如何转化为空间下界？

首先想一个问题：既然大家都已经守规矩地“先听后发”（检测到总线空闲才发帧）了，为什么还是会撞车？不难想到是电磁波的有限传播速度（在铜线里大约是 $2 \times 10^8\text{ m/s}$ ，即每公里耗时约 $5\ \mu\text{s}$ ）。主机站在总线的某段听到“当前信道空闲”，只代表此时此刻还没有别人的电磁波传到你家门口，但此时可能已经有若干条电磁波跑在总线上了。

那发送方 A 发出一个帧之后，最晚要盯多久才能保证“我这一帧在路上绝对没跟任何人撞上”？我们可以做一个最坏情况的时空边界推演：

设总线两端最远的两个站点 A 和 B 之间单程传播时延为 $\tau$ 。在 $t = 0$ 时刻，A 监听到信道空闲，开始往总线上发送数据帧；
电磁波以速度 $v$ 向 B 推进。就在波前即将抵达 B 的前一瞬间——即 $t = \tau - \varepsilon$ （ $\varepsilon \to 0^+$ ）时刻，B 自己家门口的电缆依然是安静的，于是 B 也判定信道空闲，在开始发帧；

这个端到端的往返传播时延 $2\tau$ ，就是以太网里的争用期（Contention Period，又称碰撞窗口）。只要熬过了 $2\tau$ 时间还没听到碰撞，此时 A 发出的信号已经铺满了整根电缆，其他所有站点都能监听到信道正忙，不会发送自己的电磁波，后面就可以安心发完了。

但这个过程可以成立的前提是A 必须在“自己还没把这帧数据发完”的时候，收到传回来的碰撞信号；因为以太网没有确认帧，如果一帧数据太短，A 花了 $0.5\tau$ 就把整帧发完就去处理下一个帧，结果到了 $t = 2\tau$ 碰撞信号才慢悠悠地回来，A 不知道刚才早已发出去的那帧其实在半路上已被撞碎，自然也就不会触发重传。

于是，为了实现“边听边发”，需要给数据帧的长度 $L_{\min}$ 加上帧的发送时延 $T_{\text{send}} = \frac{L}{R}$ 必须不小于争用期 ，即：

$\frac{L_{\min}}{R} \ge 2\tau \implies L_{\min} = 2\tau \times R$

在 10 Mb/s 以太网标准中，规定最大端到端争用期 $2\tau = 51.2\ \mu\text{s}$ 。代入后计算： $L_{\min} = 51.2 \times 10^{-6}\text{ s} \times 10 \times 10^6\text{ bit/s} = 512\text{ bit} = 64\text{ 字节}$ 这就是为什么以太网规定（如果上层 IP 包太短，链路层必须往里面塞入无意义的填充字节凑够 64 字节才能发；而接收端只要收到任何小于 64 字节的残帧，会在链路层被直接丢弃）。

CSMA/CD 争用期时空推导与截断二进制指数退避

左：极限情况下碰撞信号需经历往返时延 2τ 才传回发送端；右：截断二进制指数退避的采样窗口随冲突次数指数扩张

2. 截断二进制指数退避：如何用局部冲突次数估算全局负载？

现在看后半段。发送者 A 和发送者 B 在争用期内都检测到了碰撞，双双立刻停止发送（并发出 32/48 bit 的人为干扰信号强化碰撞）。接下来，它们俩手里都攒着刚才没发出去的那一帧，该在什么时候重传？

假如算法设计成确定性的——比如“检测到碰撞后，等信道变空闲就立刻重传”，或者“统一等待固定的 $2\tau$ 后重传”的话，那 A 和 B 就像走廊里迎面撞上的两个人，同时往左迈一步、又同时往右迈一步，陷入对称性死锁（Symmetry Deadlock），会反复触发碰撞。要想在传统总线式局域网这种没有中心协调者的分布式环境里打破对称性，我们需要引入随机化（Randomization）。

随机化地等待时间不能完全随便选。如果把随机等待窗口限定在一些小常数（比如在 $\{0, 1, 2, 3\}$ 里抽签），当总线上主机数较多时依旧会频发碰撞；但如果把窗口定成 $\{0, 1, \dots, 1023\}$ ，如果总线上活跃主机少就会白白等待、徒增时延。而且在纯广播总线上，没有任何一个节点知道当前到底有几台机器（ $N$ ）正在一起抢信道；所以我们需要设计一个能让主机去试图“感知”总线上有多少台活跃主机的方法。

以太网采用的截断二进制指数退避算法（Truncated Binary Exponential Backoff），本质上就是用 “当前帧已经连续撞车的次数 $c$ ”作为全局竞争人数 $N$ 的局部隐式估计量。

对当前准备发送的帧维护一个局部冲突计数器 $c$ （初始 $c = 0$ ）；
每发生一次碰撞， $c \leftarrow c + 1$ 。若 $c == 16$ ，认为网络已严重拥塞或链路故障，直接丢弃该帧并向上层报告错误（防止无限重试拖垮系统）；
取指数截断值 $k = \min (c,$ （即重传次数不超过 10 时，超过 10 次后封顶在 10，不再继续扩大）；

可以估计一下这个方案的期望：

当网络很闲、只有 A 和 B 两台主机偶发碰撞时，第 1 次冲突后 $k = 1$ ， $r \in \{0, 1\}$ 。两人抽到不同数字当场错开的概率是 $1 - \frac{1}{2^1} = 50\%$ ，胜出者平均只需多等；

用十几行 C++ 代码就能把这套退避状态机完整写出来：

cpp

#include <random>
 
struct CSMACD_Sender {
    static constexpr int SLOT_TIME_US = 51; // 10Mbps 以太网争用期 2τ ≈ 51.2 μs
    static constexpr int MAX_RETRIES  = 16; // 最大重传上限 16 次
    static constexpr int BACKOFF_CAP  = 10; // 指数截断上限 k <= 10
 
    mt19937 rng{random_device{}()};
 
    // 传入当前帧已遭遇的碰撞次数 c (1 <= c <= 16)，返回需要退避的微秒数；返回 -1 表示放弃
    int on_collision(int c) {

后来指数退避的方案几乎成了整个计算机工程界的通用范式；无论你在写微服务 RPC 调用失败后的重试策略，还是写高并发下乐观锁（CAS）自旋冲突的退避，用的全是这套 Exponential Backoff with Jitter（带随机抖动的指数退避）。

不过，如果以严格的算法工程眼光审视，纯 CSMA/CD 的指数退避其实藏着一个明显的缺陷：捕获效应（Capture Effect，即短期的极度不公平性）。

设想 A 和 B 撞了 3 次，两站的 $c$ 都涨到了 $3$ ；结果其中一次 A 运气好抽到了 $r = 0$ 先把帧发了出去，B 抽到了 $r = 4$ 还在等 $8\tau$ 的倒计时。一旦 A 发送成功，A 的冲突计数器 $c$ 会立刻重置回 。如果这时 A 手里紧接着又有第 2 个帧要发，并与刚倒计时结束的 B 再次撞上。在接下来的退避抽签里，刚重置的 A 是从（）里抽签，而倒霉的 B 已经连撞 4 次，得从（）里抽签，A 抢赢信道并让 B 继续等待的概率在以上。

这个“赢家通吃、输家越输越惨”的工程痛点，到了教材第 9 章无线局域网（802.11 Wi-Fi）的 CSMA/CA（碰撞避免） 中得到了针对性的修正：在 CSMA/CA 里，当倒霉的站点 B 抽到了一个较大的退避计数器（比如 $r = 12$ ）并在等待期间发现信道被 A 抢走变忙时，B 的退避计时器会当场“冻结”，等 A 发完、信道重新空闲 DIFS 时间后，B 直接从上次剩下的剩余时间（比如还剩 $7$ 个时隙）接着往下减，而不是作废重抽；这样一来，先来的老节点手里的剩余倒计时会越来越短，再也不会被新来的节点无限插队了。

3.3 交换机自学习与生成树协议（STP）：在线缓存学习与分布式最小生成树

CSMA/CD 虽然巧妙，但只要几十台电脑还挂在同一根总线上或者插在物理层的集线器上，整个网络就仍然处于同一个冲突域里，同一时刻只能有一个人说话。

为了彻底解决总线碰撞，现代局域网全面转向了工作在数据链路层的以太网交换机（Switch，早期称透明网桥 Bridge）。交换机为每个端口提供独立的冲突域和全双工通道，并且“即插即用（Plug-and-Play）”，买回来插上网线就能精准转发，完全不需要管理员手动配置路由表。

这种便利的背后靠的是一对相辅相成的算法；数据面的交换机自学习算法（Backward Learning）以及控制面的生成树协议（STP，Spanning Tree Protocol）。

1. 交换机自学习算法：靠“来路”反推“去路”的在线缓存

一台刚拆封上电的交换机，内部的 MAC 地址表（转发表） 是完全空白的。它怎么知道哪台主机插在自己的哪个端口上？

如果让每台主机定期广播声明自己的位置，既浪费带宽，又要改主机协议栈。交换机自学习算法如是想：既然每一个以太网帧的首部都同时带着“源 MAC 地址（Src MAC）”和“目的 MAC 地址（Dst MAC）”，那只要有一个源地址为 A 的帧从端口 1 流了进来，就说明主机 A 一定连接在端口 1 这一侧。

于是，每当交换机从某个入端口 in_port 收到一个数据帧，它都会在极短的时间内先登记源地址，再查目的地址：

逆向学习（登记源 MAC）：把映射关系 Src_MAC -> (in_port, 当前时间戳) 写入 MAC 地址表。若表中已有 Src_MAC，则更新其端口号并刷新时间戳；每条记录带有一个老化时间 TTL（注意这里的老化时间是实打实的倒计时秒数，和后面网络层 IP 首部里那个虽叫 TTL 但实际按跳数递减的字段不同），默认通常为 300 秒，超时未刷新则自动清除，以应对主机拔掉网线换座位的情况；
查表转发（查询目的 MAC）：在 MAC 表中查找 Dst_MAC（且未过期）：
- 命中，且记录的出端口 out_port == in_port：说明源主机和目的主机本来就在同一个端口连接的网段内，无需交换机插手，直接丢弃；
- 命中，且 out_port != in_port：精准地只把该帧从 out_port 单播转发出去；
- 未命中（未知单播），或 Dst_MAC 本身就是全 F 广播地址：交换机还不知道目标在哪，只能退化为向除 in_port 以外的所有其他端口泛洪。

用 C++ 写出来，是一个带惰性过期清理的哈希表（在真实交换机硬件中，这张表直接存储在支持单周期并行比对的 CAM 芯片里）：

cpp

#include <unordered_map>
#include <vector>
#include <cstdint>
using namespace std;
 
struct MacEntry {
    int port;
    uint64_t timestamp;
};
 
class EthernetSwitch {
    int num_ports;
    uint64_t ttl = 300; // 老化时间 300 秒
    unordered_map<uint64_t, MacEntry> mac_table; // MAC 地址 -> (端口, 时间戳)
 
public:

2. 当“未知泛洪”撞上“物理环路”：为什么必须剪出一棵生成树？

单看上面的自学习算法，感觉设计的非常完美：第一个包未知泛洪探路，对方只要回一个包，往返路径上所有交换机的 MAC 表就全学会了，后续全部走精准单播。但在真实的机房工程里，如果只用孤零零的一条线把交换机串成一排，一旦有一段通路被切断，会导致大量主机下线。为了更高的可用性，交换机之间一定会多插几根备用网线，连成带有冗余的环路拓扑（Cyclic Graph）。

可一旦物理拓扑里有了环，上面那个“查不到目的地址就向除入端口外的所有端口泛洪”的规则，就可能会引发一系列的问题：

广播风暴（Broadcast Storm）：假设图中有三台交换机 S1 - S2 - S3 连成一个三角形环路。主机发出一帧广播（或未知单播），S1 把它泛洪给 S2 和 S3；S2 收到后又转给 S3，S3 又转给 S1……别忘了，二层以太网帧的首部里没有像三层 IP 数据报那样的 TTL（生存时间）字段 ，所以这个帧在环路里不但永远不会自然消亡，反而每经过一台多端口交换机还会被复制放大，顺时针一圈、逆时针一圈，几毫秒之内就会把所有交换机的内存缓冲和链路带宽彻底塞爆（谢希仁教材中以两台交换器形成的环为例，和这个例子中的原理其实一样）；
MAC 地址表震荡（MAC Table Flapping）：在广播风暴中，帧绕着环路传输的过程里 S1 一会儿从左边的端口收到源地址为 A 的复制帧，把表改成；下一微秒又从右边的端口收到反方向绕过来的复制帧，又把表改成，转发表彻底失灵。

交换机环路风暴与 STP 生成树收敛

左：无 TTL 的二层泛洪在环路中引发广播风暴与 MAC 表震荡；右：STP 通过四元组字典序比较在逻辑上阻塞冗余端口

要想既保留物理上的冗余备份网线，又不让数据帧在里面绕圈子，唯一的办法就是在转发数据之前，先在逻辑上把某些冗余端口阻塞，把一张有环连通图 $G = (V, E)$ 剪成一棵无环连通的生成树（Spanning Tree），这样就可以将冗余的连线在正常连通时不通信号；一旦哪天某条工作链路真的断了，再把之前堵死的备用端口重新放开。这就是由 Radia Perlman 设计的 STP（Spanning Tree Protocol，IEEE 802.1D）。

3. STP 与算法课里的 Prim / Kruskal 有什么区别？

听到最小生成树，作为 CS 专业的学生肯定会先想到 Kruskal 算法（把所有边按权重排序 + 并查集判环）和 Prim 算法（从起点维护优先队列向外贪心扩展）。

但交换机网络面对的信息条件，跟单机算法题完全不同：

没有全局视图：每台交换机刚通电的时候，根本不知道整个机房里有几台交换机、网线是怎么连的，手里没有一个存着所有边的 edges[] 数组可以拿来 sort；
不能有中心节点：不能指望某一台主控电脑收集全网信息算好生成树再下发，因为那台主控电脑本身要通信也得先靠二层网络联通且无环。

所以，STP 实际上是一个纯分布式的、异步迭代收敛的生成树算法。它不追求把全网所有树边的总权重加起来最小，而是追求构造一棵以全网编号最小的交换机为根的最短路径树（Shortest-Path Tree，SPT），并且保证每一条物理网段（边）上至多只有一个端口负责向下游转发。

为了在完全局部的视野下达成全局一致，STP 定义了一个极其核心的数据结构——包含在 BPDU（网桥协议数据单元） 报文里的 四元组优先级向量（Configuration Vector）：

$\text{Vector} = \big(\ \underbrace{\text{Root\_ID}}_{\text{我认定的根桥 ID}},\quad \underbrace{\text{Root\_Path\_Cost}}_{\text{我到根桥的累计路径开销}},\quad \underbrace{\text{Sender\_BID}}_{\text{发送该报文的交换机 ID}},\quad \underbrace{\text{Sender\_Port\_ID}}_{\text{发送该报文的端口 ID}}\ \big)$

其中，每台交换机的唯一标识 BID（Bridge ID） 由“2 字节优先级 + 6 字节交换机 MAC 地址”拼成，因此全网每一台交换机的 BID 都是天然严格不相等的；同一台交换机上的每个端口 Port_ID 也是严格不相等的。

STP 的核心规则是：两个四元组比大小，严格按照从左到右的字典序（Lexicographical Order）比较，数值越小越优（Better）。

在这个全序关系（Total Order，可保证绝不会出现平局）下，全网交换机每隔 2 秒向邻居发送一次自己当前认为最优的 BPDU，自动完成以下三步收敛：

选举唯一的根桥（Root Bridge，生成树的根）：刚上电时，每台交换机 $u$ 都认定自己为根桥，向外广播 (Root_ID = u, Cost = 0, Sender = u, Port)。一旦某台交换机从邻居收到了一个 Root_ID 比自己当前认定的更小的 BPDU，它就把自己的根桥更新为那个更小的 Root_ID，并在转发时累加上入端口的链路开销 Cost。经过有限轮广播，全网 BID 最小的那台交换机（如上图中的 S1, BID=10）便成为唯一根桥。
每个非根交换机选举唯一的根端口（Root Port，RP，指向父节点的树边）：每台非根交换机（如 S2、S3）在自己的所有端口上，对比收到的外部 BPDU 四元组，挑选出**字典序最小（即离根桥最近；若距离相同则上游交换机 BID 更小；再相同则上游端口号更小）**的那一个端口作为自己的 根端口（RP）。因为树中每个非根节点有且仅有一个父节点，这一步直接确定了每个节点连向根桥的唯一主干树枝（上图中连向的端口、连向的端口当选为，路径开销均为）。

经过以上过程，我们就可以将机房内原来的联通有环图变化成一棵生成树，删去了平行边以及环；我们可以把交换机在每个端口上的 BPDU 字典序的比较逻辑写成以下 C++ 代码：

cpp

#include <tuple>
 
// STP 的四元组优先级向量：直接利用 std::tuple 天然支持从左到右的字典序比较 (< 即更优)
struct BPDU {
    uint64_t root_id;        // 1. 树根交换机 BID
    uint32_t root_path_cost; // 2. 到达根桥的累计路径开销
    uint64_t sender_bid;     // 3. 发送方交换机 BID
    uint16_t sender_port_id; // 4. 发送方端口 ID
 
    bool is_better_than(const BPDU& other) const {
        return tie(root_id, root_path_cost, sender_bid, sender_port_id)
             < tie(other.root_id, other.root_path_cost, other.sender_bid, other.sender_port_id);

你看，正因为 (Root_ID, Cost, Sender_BID, Port_ID) 四元组里的后两项是全球唯一的硬件/端口编号，任何一条网段上的两个端口比大小，永远不会平局；这就从数学上严格保证了在没有中心控制器的情况下，无论网络拓扑长得多么奇形怪状，异步交换 BPDU 最终一定能收敛到唯一确定的不动点、得到一棵覆盖全网且绝无环路的生成树。

而一旦某天 S1 - S3 之间的网线断了，S3 的根端口收不到心跳（或收到拓扑变更 TCN），原本处于 BLK 阻塞状态的备用端口就会被唤醒，切换回转发状态接管流量。控制面用秒级的分布式定点迭代维护好一棵无环的树，数据面就只需要在这棵树上运行纳秒级的 MAC 表哈希查找；这两个算法一慢一快、一控制一转发，但是却可以融洽配合，正体现了前言中所说的网络算法与通用软件算法在流程上的不同；STP 不像 Prim 或者 Kruskal 那样追求找到总代价最小的生成树，而是追求工程上的可达性以及网络的抗逆性。

4. 网络层

如果说物理层关心的是怎么在一根线上把比特流送过去，数据链路层关心的是怎么在同一个局域网里把帧交给邻居，那么到了网络层，视野就真正扩大到了由成千上万个异构网络交织而成的互联网。

这一层涉及的算法对于信息竞赛有所了解的朋友应该会有很强的既视感。控制面上，路由器要在复杂的网络拓扑图里算出通往各个目的网络的最短路径，其中RIP 对应了基于 Bellman-Ford 的动态规划（DP），OSPF 对应了基于全图视野的 Dijkstra 贪心与区域分治；而在数据面上，路由器拿到一个目的 IP 地址后，又必须在几纳秒内从几十万条 CIDR 路由表项里找出最具体的那一条，这直接催生了从二进制公共前缀、二叉 Trie、Multibit Trie 到硬件 TCAM 的查找算法演进。

我们先从一个问题切入：同样是求图上的最短路径，为什么网络层会同时存在 RIP（动态规划）和 OSPF（贪心）两套截然不同的路由算法？

答案在于信息边界；也就是一台路由器在做决策时，手里到底掌握了多少全网信息。

4.1 RIP、Bellman Ford 与 DP：只有“邻居传闻”时的异步迭代

在自治系统（AS）内部，最早广泛使用的路由协议是 RIP（Routing Information Protocol，路由信息协议）。

站在 RIP 路由器的视角看世界，它是非常“盲目”的，它手里从来没有一张全网拓扑图，也不知道远方有几台路由器、怎么连线。它唯一能确定的，只有自己身边直接相连的几个邻居路由器，以及这些邻居每隔 30 秒通过 UDP 的 520 端口给它发过来的路由表。

换句话说，RIP 路由器听到的永远是邻居口口相传的二手信息，大概类似：“邻居 $V$ 告诉我，它到目的网络 $N$ 的距离是 $D_V(N)$ ”。

在“不知道全图，只知道邻居的信息”的条件下，路由器 $X$ 要算出自己到目的网络 $N$ 的最短距离 $D_X(N)$ 正是动态规划中经典的最优子结构性质：从 $X$ 出发到达目的网络 $N$ 的最短路径，必定要先经过的某一个直接邻居，然后再沿着从到的最短路径走完剩下的路程。写成状态转移方程，就是著名的：

$D_X(N) = \min_{V \in \text{Neighbors}(X)} \big\{\ c(X, V) + D_V(N)\ \big\}$

在 RIP 协议中，链路代价 $c(X, V)$ 统一按“跳数（Hop Count）”计算，每经过一台路由器跳数加 $1$ （即 $c(X, V) = 1$ ），且规定最大合法跳数为 $15$ ，距离等于 $16$ 即代表不可达（相当于算法题里的）。

1. 从单机 Bellman-Ford 到 RIP 的路由表更新状态机

在《算法设计与分析》课里写单机版 Bellman-Ford 算法时，我们的代码通常是外层循环 $|V|-1$ 轮，内层遍历每一条边 $(u, v)$ 做松弛操作：dist[v] = min(dist[v], dist[u] + w)。

但把 Bellman-Ford 搬到分布式网络里变成 RIP 时有两处关键变化：

没有一个全局的 for (int step = 1; step < n; ++step) 主循环，而是每台路由器各自独立运行，每收到邻居 $V$ 发来的距离向量报文，就触发一次本地松弛更新；
现实网络中的链路代价是会动态变大甚至断开的，如果只写 dist = min(dist, new_dist)，当原有的最短路断掉，也就是距离变成 16时，由于 $16 > \text{旧距离}$ ，路由器永远不会更新这个坏消息。

因此，谢希仁教材第 4 章在讲解 RIP 的距离向量算法时，将单机 DP 的松弛操作改造成了一个三分支状态机。当路由器 $X$ 收到相邻路由器 $V$ 发来的路由报文时，先把 $V$ 表中的每一条记录 (目的网络 N, 距离 d) 加上 $1$ 跳，并将下一跳标记为 $V$ ，得到候选项 (N, d' = min(d + 1, 16), 下一跳 = V)，然后对照本机现有的路由表按以下三条规则处理：

情况 A - 首次发现：本机路由表中原本没有目的网络 $N$ 且 $d' < 16$ ，直接把这条新路由插入表中；
情况 B - 同源强制覆盖：本机路由表中已有目的网络 $N$ ，且原有的下一跳路由器本来就是 $V$ ，那不管新的 $d'$ 是变小了还是变大了，都用新表项覆盖原表项。你去往的路本来就是指望带你走的，邻居比本机掌握着通往那个网络更新的信息，所以他的信息更新了，本机路由表也要跟着更新；

RIP 距离向量算法状态转移与无穷计数陷阱

左：RIP 接收邻居路由表时的三分支更新状态机；右：链路断开时异步 DP 陷入「坏消息传得慢」的无穷计数过程

用 C++ 把 RIP 路由器的这个更新状态机实现：

cpp

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
static constexpr int RIP_INF = 16; // RIP 规定 16 跳即为不可达
 
struct RouteEntry {
    int dist;         // 到达目的网络的跳数 (1 ~ 16)
    string next_hop;  // 下一跳路由器名称 ("DIRECT" 表示直连)
};
 
// 邻居发来的一条距离向量通告
struct RipAdvertisement {

2. 异步分布式 DP 的致命伤：“好消息传得快，坏消息传得慢”

把上面这段代码放到一个静态拓扑里跑，不论网络怎么连，最多经过“网络直径”轮次的 30 秒交换，所有路由器的表都会完美收敛到最短路不动点。但在真实的动态网络里，RIP 有一个工程顽疾，通俗的说法是 “好消息传得快，坏消息传得慢”，在算法上称为无穷计数问题（Count-to-Infinity）。

为什么在通用软件算法中 Bellman-Ford 不会产生这种问题，一放到网络层就出事了？

我们对照上图右侧的时间轴来看：假设拓扑是 网1 --- R1 --- R2。正常收敛时，R1 到 网1 是直连（距离 1），R2 经由 R1 到 网1（距离 2，下一跳 R1）。

某一个瞬间 $t_0$ ，R1 连往 网1 的网线突然断了：

R1 立刻察觉直连网线断开，把自己的表项改成 (网1, 距离 = 16, 不可达)；
但因为 RIP 是异步周期广播的，恰巧在 R1 把这个坏消息发出去之前，不知情的 R2 先把自己的周期路由表发给了 R1，里面写着：我 R2 到网 1 的距离是 2；
关键漏洞出现：R1 收到 R2 的信息后，给距离加 $1$ 得到 (网1, 距离 = 3, 下一跳 = R2)。R1 并不知道 手里那个距离其实是从自己这儿学过去的旧历史数据。在只看数字不看路径的 DP 方程眼里，，于是触发“情况 C”，以为背后另有一条通往的其他通路，把自己的路由表改成了；

从动态规划的角度看，这是因为在单机 DP 里，状态是从无到有、单调向下松弛的；而在持续运行的网络里，节点内存中残留着上一代拓扑遗留下来的“历史最优值（陈旧状态）”。当底层约束突然收紧比如某条边断了的时候，两个相邻节点会拿着彼此的旧状态左脚踩右脚陷入了虚假的自激循环；直到数到 16，才终于会意识到通路不存在。

为了解决 RIP 坏消息传得慢的问题，工程师们提出了三种补丁：

水平分割（Split Horizon）：既然坏消息是因为“R2 把从 R1 学来的路由传给了 R1”导致两台路由器之间的陈旧状态来回交换，那就规定凡是从某个接口学到的路由，绝不再从该接口往回发送；
毒性逆转（Poison Reverse）：路由器从某接口学习到路由后，将该路由的开销值设为 16（类似于给原路由器下毒），并从原接口回传至邻居设备；在上述的例子中，既然 R2 是靠 R1 才能去 网1，那 R2 对着 R1 发信息时就撒谎说“我到 网1 的距离是 $16$ ”，这样就避免了 R1 指望从绕路到的情况；

即便打了“水平分割 + 毒性逆转”补丁，如果三个路由器 R1 - R2 - R3 连成三角形环路，当通往外网的唯一出口断开时，水平分割只能拦住两个节点间的陈旧状态互传，拦不住顺着三角形绕圈的间接欺骗，依然会出现无穷计数。想要从根源上解决无穷计数问题，还是需要让每个路由器都能看到全网的状态，也就是 OSPF 算法所做的事。

4.2 OSPF 与 Dijkstra：用通信开销换取“上帝视角”的贪心与分治

既然 RIP 的一切问题源于“手里没有地图，只能听邻居传话”，那 OSPF（Open Shortest Path First） 就让每个路由器把自己的邻接关系广播给全网，让每台路由器都在本地拼出一张完整的全网地图，然后各自在地图上跑一遍单机 Dijkstra 最短路算法。

1. 第一步：可靠洪泛如何拼出全网地图 LSDB？

在 OSPF 中，每台路由器向全网广播自己的邻接表，也就是本机连着哪些相邻路由器/网段，每条链路的代价是多少。这份局部邻接表被称为 LSA（链路状态通告）。当链路状态发生变化时，路由器通过洪泛法把 LSA 发给自治系统内的所有路由器；收到 LSA 的路由器将其复制并转发给除入接口以外的所有相邻路由器。

看到“洪泛”，你可能马上会联想到上一章说的交换机广播风暴：网络层的拓扑本来就是允许有环的，OSPF 全网洪泛 LSA，难道不会像二层交换机那样引发无限绕圈的广播风暴吗？

答案是不会。因为在控制面协议包里，OSPF 为每一条 LSA 都打上了 (通告路由器 ID, 链路状态 ID, 32 位递增序列号 Sequence Number, 老化时间 Age) 的唯一指纹，并在每台路由器内存里维护了一张哈希表“链路状态数据库（LSDB）”。

每当路由器收到一份 LSA，它会先查自己的 LSDB：

如果这份 LSA 的序列号 小于或等于 数据库里已有的同源 LSA 序列号，说明这是一份顺着环路绕回来的旧重复包，直接静默丢弃，不再转发；
只有当它是从未见过的新 LSA，或者序列号严格大于已有记录时，才更新本地 LSDB，向邻居回发确认，并继续从其他接口向外转发。

从图论算法来看，这套带序列号去重的可靠洪泛就是在有环图上跑了一次带以 (Node_ID, Seq_Num) 为 Key的 visited 哈希集合的 BFS。每条新 LSA 在全网每条链路上最多只会走一次，不会绕圈。

2. 第二步：在全网地图 LSDB 上跑 Dijkstra 贪心并提取“第一跳”

等洪泛在毫秒级时间内平息下来，自治系统里的每一台路由器手里，都有了一份完全相同的链路状态数据库 LSDB，足以让每台路由器在本地拼凑出一张完整的带权有向图 $G = (V, E)$ 。此时，分布式问题已经被彻底还原成了我们在算法课上最熟悉的单机图论问题。每台路由器只需要以自己为源点 $s$ ，在本地内存里的图 $G$ 上跑一遍 Dijkstra 单源最短路径算法就可以得到所有路由。

这里可以放心使用贪心策略是因为 Dijkstra 的正确性建立在两个前提之上：

全局拓扑已知（已由 LSDB 满足）；
所有边权严格非负（ $w(u, v) \ge 0$ ）。在 OSPF 中，链路的代价 Cost 通常按接口带宽反比折算（谢希仁教材中只是提到链路的代价由管理员自行规定；但是实际应用中通常按接口带宽反比折算：例如 Cisco 默认公式 $\text{Cost} = \frac{10^8\text{ bit/s}}{\text{Bandwidth}}$ ，最小为），全部是，不存在负权边。因此，每一步从优先队列里弹出的当前距离最小的未确定节点，其最短路径必然已经敲定，后续不可能再通过其他局部更远点绕路松弛变小。

不过，路由器的 Dijkstra 比算法竞赛里的板子题多了一步非常关键的工程细节：算法题只要求输出 dist[v]（最短距离是多少），而路由器真正要写进内核数据面转发表（FIB）里的，是通往目的节点 $v$ 的最短路径树上的“第一跳邻居（first_hop[v]）”。

为了把到达每一个路由终点的第一跳节点取出来，需要在松弛边 $u \to v$ 时加一行状态继承逻辑：

如果起点就是源点自己（ $u == s$ ），那么到达邻居 $v$ 的第一跳显然就是 $v$ 本身（first_hop[v] = v）；
如果 $u$ 不是源点（ $u \neq s$ ），那么既然从到的最短路径是顺着走过来的，去往的第一跳就必然（）。

OSPF 协议：洪泛同步全网地图 + 本地 Dijkstra + 区域分治

左：OSPF 先用 LSA 洪泛同步全网带权图 LSDB，再各自以本机为根跑 Dijkstra 提取第一跳；右：大网络下的 Area 区域分治

把这套带第一跳继承的 OSPF Dijkstra 写成 C++ 代码，和我们常见的 Dijkstra 几乎一样，但是相较《数据结构》中的板子，此处使用了堆优化：

cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
const int INF = 1e9;
 
struct Edge {
    int to;
    int cost; // OSPF 链路度量值，可保证都是正数
};
 
struct OspfResult {
    vector<int> dist;      // 到各节点的最短路径总代价
    vector<int> first_hop;

3. 当全图太大时怎么办？—— OSPF 的“区域（Area）”分治法

对比 RIP 和 OSPF，类似与算法设计中“空间换时间”的取舍，OSPF 也是在用通信换计算（Information vs. Computation Trade-off）：为了把分布式信息不对称抹平，OSPF 前期多花了一笔洪泛 LSA 的通信开销，从而换来了毫秒级的收敛速度和绝对无环的贪心最短路。但如果一个大型运营商网络里有 $10,000$ 台路由器，全网所有路由器一起洪泛 LSA、维护一张一万个节点的巨型图，会引起一系列的工程问题：

任何一根小网线抖动一下，全网一万台机器都要跟着收发 LSA、重跑一遍 Dijkstra；
洪泛报文的数量随网络规模呈 $O(V \cdot E)$ 增长，内存里的 LSDB 和优先队列开销也会急剧膨胀。

对此，谢希仁教材 4.5.3 节里讲的 OSPF 划分区域（Area），利用算法设计上的分治法（Divide and Conquer）与层次化图切分，解决了大图洪泛问题：

把一个庞大的自治系统切分成若干个规模较小的下属区域 Area 1, Area 2 等等，每个区域控制在几十到两百台路由器以内；
全图洪泛 LSA 和本地运行 Dijkstra 的范围被严格限制每个小区域内部，即 Area 1 里的路由器只知道 Area 1 内部长什么样，不考虑 Area 2 的内部拓扑细节；
区域与区域之间通过顶层的**主干区域（书上称为 Backbone Area 0，标识符 0.0.0.0）相连，由跨在边界上的区域边界路由器（ABR）**把本区域内部算好的最短距离打包汇总成一个简单的距离标量，通告给其他区域。

在每个小区域内部，OSPF 用的是“全图链路状态 + Dijkstra 贪心”；而在跨越不同区域的宏观层面上，ABR 对外只报汇总距离、屏蔽内部拓扑，其实又退回到了类似距离向量的摘要思想。通过分治把大图切成两层，既保住了区域内的快速收敛，又避免了跨区域的洪泛爆炸。

补充一下 BGP（边界网关协议，对应教材 4.5.4；课程上对这个不做要求，因为他很难称得上一种算法，而更像一个规则集）。把视野再往上抬一层，到了全球各大 ISP 自治系统之间互联时，连 OSPF 的分治都也不好用；因为不同国家、不同运营商之间不可能把内部拓扑共享给你，而且跨国路由往往首先服从商业结算与安全策略（比如“哪怕绕远路，也绝不把流量转给竞争对手 AS”），目标函数不再是单纯的“最短距离”。因此 BGP 既没用 Dijkstra 也没用纯距离向量，而是采用了路径向量（Path Vector）：在广播可达性时，直接把沿途经过的完整自治系统编号序列 AS-PATH（如 [AS1, AS2, AS3]）全部带上。收到路由时只用看列表里有没有自己的 AS 号，就能以 $O(\text{路径长度})$ 的代价杜绝环路，同时根据路径属性灵活执行策略过滤。

4.3 CIDR 路由聚合与最长前缀匹配：从二进制公共前缀、Trie 树到硬件 TCAM

前面聊的 RIP 和 OSPF 都在解决控制面（Control Plane）的问题，也就是“怎么把路由表算出来”。现在，路由表已经算好并下发到了路由器的数据面（Data Plane）转发表里。此时此刻，一个目的 IP 地址为 D 的数据包从网线冲进了网卡，路由器必须在极短的时间内查表决定这个包到底该从哪个接口转发。

在早期分类 IP 编址（也就是区分 A/B/C 类地址）时代这件事很简单，直接看首字节属于哪一类、取固定长度的网络号去哈希表里查找就行。但随着 IPv4 地址危机爆发，互联网全面转向了谢希仁教材 4.3 节重点介绍的 CIDR（无分类域间路由选择），查找问题变得复杂。

1. CIDR 路由聚合（构造超网）：位运算求最长公共前缀

CIDR 废除了固定的 A/B/C 类边界，改用斜线记法 IP/n（如 206.0.68.0/22），表示前 $n$ 位是网络前缀，后 $32 - n$ 位是主机号，一个地址块包含 $2^{32-n}$ 个连续地址。为了防止全球核心路由器的路由表被成百上千个零碎的小网络撑爆，CIDR 引入了路由聚合（Route Aggregation，又称构造超网）：如果一个组织或 ISP 手里握有多个连续的 CIDR 地址块，且它们的下一跳出口完全相同，就可以把它们合并成一条前缀更短、覆盖范围更大的路由表项。

比如教材习题：某 ISP 拥有 212.56.132.0/24、212.56.133.0/24、212.56.134.0/24、212.56.135.0/24 四个子网，如何聚合成一条路由？把第三字节化成二进制对比：

132 = 10000100
133 = 10000101
134 = 10000110
135 = 10000111

可以看出，前两个字节（16 位）加上第三字节的前 6 位（100001）完全相同，只有最后两位从 00 变到了 11。所以这四个 /24 地址块的**最长公共前缀（LCP）**长度是 $16 + 6 = 22$ 位，聚合后的超网就是 212.56.132.0/22。

如果写成算法代码，给定一组地址块的最小起始 IP ip_min 和最大结束 IP ip_max，求它们的最长公共前缀长度连循环都不用跑：直接把 ip_min 和 ip_max 做一次按位异或（ip_min ^ ip_max）；凡是相同的最高位异或后全是 0，第一个不同的位异或后为 1；随后调用一条 CPU 硬件指令 __builtin_clz（Count Leading Zeros，统计前导零个数），就能在 $O(1)$ 时间内算出聚合前缀长度：

cpp

#include <cstdint>
 
// O(1) 求区间 [ip_min, ip_max] 的最长公共前缀长度 n 与聚合后的网络地址
pair<uint32_t, int> cidr_aggregate(uint32_t ip_min, uint32_t ip_max) {
    uint32_t diff = ip_min ^ ip_max;  // 相同高位全为 0，首个不同位为 1
    int prefix_len = (diff == 0) ? 32 : __builtin_clz(diff); // CPU 指令求前导 0 的个数即公共前缀长度
    uint32_t mask =

2. 路由聚合的后遗症：最长前缀匹配（Longest Prefix Match, LPM）

路由聚合虽然给控制面省下了大量表项，却给数据面的查表转发留了个小问题：同一张转发表里，可能会同时存在多条前缀长度不同、但具有包含关系的路由规则。

教材上给出的例子如下：假设ISP把聚合后的大地址块 206.0.68.0/22 指派给了某大学（下一跳走接口 0），但后来这所大学的计算机系独立迁到了另一个校区，单独拉了一条专线，于是路由表里又专门为计算机系加了一条更具体的特例路由 206.0.71.128/25（下一跳走接口 1）。

一个发往目的地址 D = 206.0.71.130 的数据包到了路由器。拿 /22 的掩码跟 D 相与：结果为 206.0.68.0，匹配成功；拿 /25 的掩码跟 D 相与：结果为 206.0.71.128，也匹配成功。两条规则同时命中，网络层转发遵循最长前缀匹配（LPM），即在所有匹配成功的路由表项中，必须选择**网络前缀 $n$ 最长（掩码里 1 最多）**的那一条，因为前缀越长，代表地址块越小、指向的目的地越具体（这里 /25 > /22，故必须走接口 1 交给计算机系）。

3. 数据面算法工程演进：从 $O(N)$ 扫描、二叉 Trie、Multibit Trie 到硬件 TCAM

在期末考试卷子上，转发表只有四五行，我们肉眼逐行做按位与运算几秒钟就能算出来；但在真实的互联网骨干路由器上，BGP 转发表动辄有百万级别条前缀，一个 100 Gbps 的端口每秒钟要处理近 1.48 亿个最小帧（64B），平均留给每个包做最长前缀匹配的截止时间只有 6.7 纳秒！

如果用 $O(N)$ 逐行遍历，100 万次比较大概要花几毫秒，与截止时间相比慢了六个数量级。算法工程师最后是如何把耗时压入纳秒级的呢？

最长前缀匹配（LPM）的三代实现演进

最长前缀匹配的三级演进：① 二叉 Trie 按位深搜 → ② Multibit Trie 跨步压低层数 → ③ 硬件 TCAM 三态并行匹配

第一阶段：软件算法最优解 —— 二叉前缀树（Binary Trie，步长 1 bit）

要找“最长公共前缀”，在数据结构里最对口的工具是 字典树（Trie / 前缀树）。

我们把每一条路由前缀看作一个由 0 和 1 组成的二进制字符串（最长 32 位），从根节点开始往二叉 Trie 里插入：遇到 0 走左子树，遇到 1 走右子树，走到前缀末尾的第 $n$ 层节点时，把该节点打上标记并存入对应的 next_hop 端口号。

当数据包到达时，我们拿着 32 位目的 IP 地址从最高位（第 31 位）往最低位（第 0 位）顺着树往下走：

每经过一个带有合法路由标记的节点，就用它的 next_hop 覆盖当前的 best_match 变量；
直到走到空指针 nullptr或者走完 32 层为止。因为我们是从浅到深往下走的，最后一次覆盖 best_match 的那个节点，一定就是匹配成功的、深度最深（前缀最长）的路由。

用 C++ 写出来，查询时间复杂度直接与路由表总条数 $N$ 解耦，降到了严格与地址位宽相关的 $O(W)$ （IPv4 中 $W = 32$ ）：

cpp

#include <iostream>
#include <cstdint>
using namespace std;
 
struct TrieNode {
    TrieNode* child[2] = {nullptr, nullptr};  // 0 走左，1 走右
    int next_hop = -1;  // -1 表示该节点不是一条完整路由前缀的终点
};
 
class BinaryTrieLPM {
    TrieNode* root = new

第二阶段：对抗内存瓶颈 —— 多比特前缀树（Multibit Trie，空间换时间）

在纯软件算法课里， $O(32)$ 就是常数时间 $O(1)$ 。但在第一节我们提到过，放到真实的硬件访存体系下，二叉 Trie 有一个致命的物理瓶颈，指针追逐（Pointer Chasing）。

看上面的 curr = curr->child[bit]，下一层去哪完全依赖上一层从内存里读出来的指针地址，CPU 根本没法并行预取；最坏情况下查一个 IPv4 地址要连续访问 32 次内存，如果是 128 位的 IPv6 更是要访存 128 次。而现代 DRAM 内存哪怕只发生一次 Cache Miss，延迟就在 $50 \sim 100\text{ ns}$ 左右，这样走完 32 层早就超时几十倍了。那该怎么减少访存次数？最直接的工程手段就是把步长（Stride）从每次看 1 bit 扩大到每次同时看 $k$ bits（例如 $k = 4$ 或 $k = 8$ ），这就是 Multibit Trie：

如果取步长 $k = 8$ ，每个节点不再是 child[2]，而是一个大小 $2^8 = 256$ 的指针数组 child[256]；
每次直接切下 IP 地址的 1 个字节（8 位）作为数组下标一步到位；原本 32 层的二叉树，瞬间被压扁成了最多只需 4 层，即最多只需 4 次访存的 256 叉树；
如果某条路由的前缀长度恰好卡在半中间（比如 /22，既不是 16 也不是 24），那就做一次前缀展开（Prefix Expansion），把 /22 后面补上、、、展开成条等价的表项填进第 3 层数组里（若同一个槽位里同时有原本更具体的路由，则保留那个更具体的）。

这正是典型的以空间换时间：宁可多消耗几倍的 SRAM 内存空间，也要换取更小的深度。

第三阶段：更进一步 —— TCAM（三态内容寻址存储器）

到了核心骨干网的高端交换机和路由器芯片里，4 次串行访存还是太慢，那就把并行发挥到极致，直接用硬件电路把整张表在同一纳秒内全部比对完。

这就是我们在第一节里提到的 TCAM（Ternary Content-Addressable Memory，三态内容寻址存储器）。

普通的内存（RAM）是“你给我一个下标地址，我返回里面存的数据”；而内容寻址存储器（CAM）正好反过来：“你给我一个待查的数据，芯片内部每一行存储单元都自带独立的硬件比较器（异或门阵列），在同一个时钟周期内全表并行比对，直接返回匹配成功的行号”。

二层交换机查 48 位固定长度的 MAC 地址，用普通的二态 CAM（只存 0 和 1）就够了；但三层 IP 路由有子网掩码，主机位是不需要参比通配的。于是 TCAM 在硬件电路上引入了第三种逻辑状态：X（Don't Care，不关心位 / 掩码为 0 的位）：

一条 CIDR 路由 11010000.../5，存进 TCAM 就是前 5 位存 11010，后面 27 位全存 X；
芯片里的所有行按照前缀长度从长到短（从 /32 到 /0）严格降序排列；
当目的 IP 到达时，电路在一个时钟周期内同时点亮所有匹配成功的行（比如同时点亮了 /25、/22 和 /0 三行），紧接着由硬件**优先级编码器（Priority Encoder）**直接输出排在最上面（即前缀最长）的那一行对应的下一跳端口。

从软件的 $O(N)$ 线性扫描，到 $O(32)$ 的二叉 Trie，再到 $O(4)$ 的 Multibit Trie，最后落脚到 $O(1)$ 单时钟周期硬件并行的 TCAM，算法的改造围绕着真实工况以及硬件的水平逐代更替，体现了我们在前言所述“网络算法为何是 Algorithm Engineering”的精髓。

5. 总结

顺着自底向上的脉络把物理层、数据链路层和网络层大致过了一遍（~~其实一点都不大致，对于算法原理其实比谢希仁先生的教材更加详细~~），让我们汇总一下：

协议层次	网络协议 / 机制	对应的核心算法 / 数学模型	运行平面与时间尺度	面对的工程约束与妥协
物理层	曼彻斯特 / 差分曼彻斯特 / 4B5B	流式有限状态机（Mealy FSM）、受限查表编码	数据面硬件（纳秒 / 单比特级）	无独立时钟线、防直流漂移 $\to$ 牺牲频带利用率换取时钟自同步
物理层	CDMA 码分多址	线性代数正交基投影、分治法构造 Walsh 矩阵	数据面硬件（码片级实时相关）	同频同时多站混叠 $\to$ 用 $m$ 倍带宽扩频换取正交无损解耦

在网络中，选取算法往往不是简单的追求时空复杂度的最优，而是依赖站在哪一层、手里能看见多少信息、工况下给了多久的时间预算等条件，选取最适合的方案。例如物理层只看得见眼前的电平波形，所以算法变成了内嵌时钟的状态编码与正交向量投影；数据链路层只看得见一条链路和同样向要发送电磁波的其他竞争站点，所以算法变成了有限域上的异或除法、冲突后的随机退避、以及靠局部四元组比大小长出来的生成树；而到了网络层，你可以选择只看邻居的最优子结构 RIP，也可以选择全局贪心的 OSPF，根据掌握信息不同发展出出了 Bellman-Ford 动态规划和 Dijkstra 贪心两套完全不同的路由策略。

至于这篇博客为什么只讲底下的三层，是因为学校的进度尚且至此，并且但现在为止的篇幅已经有点过长（这应该是我个人博客建立以来最长的文章），但其内容我个人较为满意，对于虽然标题如此，但是本文内容涉及了计算机领域很多方面的知识，比教材更深一层，更广一度。等在接下来一两个月后的 《计算机网络》中，出现的那些算法设计 - 02 中，我们将往上走入端系统的内部，聊聊运输层与应用层里那些同样精彩的设计：面对一个随时可能丢包、乱序、拥塞的黑盒网络，TCP 是如何靠滑动窗口、指数加权移动平均（Karn / Jacobson RTT 估计）以及 AIMD 拥塞控制状态机在两端之间搭起一条可靠管道的。敬请期待！

H_1 = [1]

S_{i}

,

-

S_{i}

,

0

}

\mathbf{X}_i \in \{+\mathbf{S}_i, -\mathbf{S}_i, \mathbf{0}\}

10

)

k = \min(c,\ 10)

X

X

R2

《计算机网络》中，出现的那些算法设计 - 01

1. 网络算法与通用软件算法的异同

2. 物理层

2.1 基带编码与曼彻斯特编码：多约束下的流式状态编码

2.2 CDMA 码分多址：正交向量空间里的信号解耦

1. 码片序列与正交基构造

2. 扩频发送、信道叠加与内积解调

3. 数据链路层

3.1 透明传输与 CRC 循环冗余校验：流式自动机与 GF(2)\text{GF}(2)GF(2) 多项式除法

1. 边界：帧定界与零比特填充 - 流式状态机

2. 检验：CRC 为什么要用“模 2 除法”？

3.2 CSMA/CD 与截断二进制指数退避：无中心环境下的随机化对称破缺

1. 争用期 2τ2\tau2τ 与最短帧长 64B：时间窗口如何转化为空间下界？

2. 截断二进制指数退避：如何用局部冲突次数估算全局负载？

3.3 交换机自学习与生成树协议（STP）：在线缓存学习与分布式最小生成树

1. 交换机自学习算法：靠“来路”反推“去路”的在线缓存

2. 当“未知泛洪”撞上“物理环路”：为什么必须剪出一棵生成树？

3. STP 与算法课里的 Prim / Kruskal 有什么区别？

4. 网络层

4.1 RIP、Bellman Ford 与 DP：只有“邻居传闻”时的异步迭代

1. 从单机 Bellman-Ford 到 RIP 的路由表更新状态机

2. 异步分布式 DP 的致命伤：“好消息传得快，坏消息传得慢”

4.2 OSPF 与 Dijkstra：用通信开销换取“上帝视角”的贪心与分治

1. 第一步：可靠洪泛如何拼出全网地图 LSDB？

2. 第二步：在全网地图 LSDB 上跑 Dijkstra 贪心并提取“第一跳”

3. 当全图太大时怎么办？—— OSPF 的“区域（Area）”分治法

4.3 CIDR 路由聚合与最长前缀匹配：从二进制公共前缀、Trie 树到硬件 TCAM

1. CIDR 路由聚合（构造超网）：位运算求最长公共前缀

2. 路由聚合的后遗症：最长前缀匹配（Longest Prefix Match, LPM）

3. 数据面算法工程演进：从 O(N)O(N)O(N) 扫描、二叉 Trie、Multibit Trie 到硬件 TCAM

第一阶段：软件算法最优解 —— 二叉前缀树（Binary Trie，步长 1 bit）

第二阶段：对抗内存瓶颈 —— 多比特前缀树（Multibit Trie，空间换时间）

第三阶段：更进一步 —— TCAM（三态内容寻址存储器）

5. 总结

3.1 透明传输与 CRC 循环冗余校验：流式自动机与 $\text{GF}(2)$ 多项式除法

1. 争用期 $2\tau$ 与最短帧长 64B：时间窗口如何转化为空间下界？

3. 数据面算法工程演进：从 $O(N)$ 扫描、二叉 Trie、Multibit Trie 到硬件 TCAM