一、链路层的位置与服务
1.1 术语
⭐ 节点（node） = 主机或路由器
⭐ 链路（link） = 沿通信路径连接【相邻】节点的信道
⭐ 帧（frame） = 链路层的数据单元（封装了一个网络层数据报）
⚠️ 关键认识：
一个数据报从源到目的，可能在不同的链路上由不同的链路层协议承载。
主机 ──WiFi──▶ 家用路由器 ──以太网──▶ 调制解调器 ──DOCSIS──▶ ISP ──光纤──▶ ...
802.11 802.3 DOCSIS SONET/OTN
⭐ 每一跳都要重新成帧、重新做差错检测。这正是第 4 讲例题里「MAC 地址逐跳更换」的物理原因。
1.2 六种服务
| 服务 | 说明 | 是否所有链路都提供 |
|---|---|---|
| ⭐ 成帧（framing） | 把数据报封装成帧，加头加尾 | 是 |
| 链路接入（link access） | 共享介质上的 MAC 协议（第 24 讲） | 共享介质才需要 |
| 可靠交付 | 在链路上做确认与重传 | ⭐ 否，看链路误码率 |
| 差错检测 | 检出比特翻转 | 是 |
| 差错纠正 | 不仅检出，还能定位并修复 | 否，无线链路常用 |
| 流量控制 | 相邻节点间的速率匹配 | 部分链路 |
| 半双工/全双工 | 是否能同时双向传输 | — |
⭐ 关于「可靠交付」的重要判断：
低误码率链路（光纤、同轴、双绞线）：
⚠️ 通常【不做】链路层可靠交付
理由：误码罕见，为它增加开销和时延不划算，交给 TCP 处理即可
高误码率链路（无线）：
⭐ 【做】链路层重传（802.11 有 ACK 与重传，第 25 讲）
理由：让 TCP 用 RTT 级的超时去恢复一个无线误码，代价太大
📌 这是第 4 讲端到端原则的精确应用：端到端的检查必须做，网络内部只在有明确性能收益时才重复做。无线链路就是那个"明确的性能收益"。
1.3 实现在哪里
⭐ 链路层的主体实现在【网络适配器（网卡/NIC）】中，是硬件。
┌────────────────────────────┐
│ 主机（CPU + 内存） │
│ 应用层 / 传输层 / 网络层 │ ← 软件
│ 链路层的【上半部分】 │ ← 驱动程序（软件）
└─────────────┬──────────────┘
│ 总线（PCIe）
┌─────────────▼──────────────┐
│ 网络适配器 NIC │
│ ⭐ 链路层的主体（硬件） │ ← 成帧、CRC、MAC 协议
│ 物理层 │
└────────────────────────────┘
为什么必须是硬件？因为它要在线速下完成 CRC 计算、载波侦听、碰撞检测——这些操作对时间极其敏感（微秒甚至纳秒级），软件跟不上。
📌 这也解释了为什么链路层可以用"昂贵"的 CRC——它由专用电路完成，几乎不消耗 CPU（第五节会回到这一点）。
二、成帧与字节填充
2.1 问题
链路上传的是一串连续的比特。接收方怎么知道一帧从哪里开始、到哪里结束？
方案：用特殊的标志字节（flag）作为定界符。
[FLAG][ 帧内容 ][FLAG]
⚠️ 新问题：如果帧内容里恰好出现了 FLAG 这个字节呢？
2.2 字节填充（Byte Stuffing）
发送方：
在数据中每遇到一个 FLAG 或 ESC 字节
→ ⭐ 在它前面插入一个转义字节 ESC
接收方：
遇到 ESC → 丢弃 ESC，把下一个字节当作【普通数据】而非定界符
例（用 ~ 表示 FLAG，\ 表示 ESC）：
原始数据: A B ~ C \ D
填充后: A B \ ~ C \ \ D
↑ ↑
转义 FLAG 转义 ESC
接收方还原: A B ~ C \ D ✅
📌 ⭐ 这与第 8 讲 SMTP 的「点填充」是完全相同的问题和完全相同的解法。
「如何在数据流中标记边界，同时允许数据里出现边界符号」——这个问题在应用层（SMTP）、链路层（PPP/HDLC）都出现了，解法都是转义。
这是本课程的一条重要暗线：同一个结构性问题会在不同层反复出现。你已经见过三次（队头阻塞、边界标记、层次化汇总）。
三、差错检测的框架
发送方: [ 数据 D ][ 差错检测比特 EDC ] ──── 信道 ────▶
接收方: 收到 D' 和 EDC'
⭐ 用 D' 重新计算 EDC，与 EDC' 比较
不一致 → 检出差错
一致 → 【认为】没有差错 ⚠️ 注意用词
⚠️ 差错检测永远不是 100% 可靠的。
⭐ 检测算法只能保证：某些【特定模式】的差错一定被检出。
总存在一些差错模式恰好使重算结果不变，从而漏检。
EDC 越长 → 漏检概率越低 → 开销越大
四、三种差错检测方法
4.1 一维奇偶校验
偶校验：加一位使【1 的总数为偶数】
数据: 1011 0001 （1 的个数 = 4，偶数）
校验位: 0
发送: 1011 0001 0
数据: 1011 0011 （1 的个数 = 5，奇数）
校验位: 1
发送: 1011 0011 1
能力：
- ✅ 检出任意奇数个比特错误
- ❌ 检不出偶数个错误（两位翻转，奇偶性不变）
⚠️ 而实际链路上的差错常常是突发的（一连串比特同时出错），恰恰容易是偶数个。一维奇偶校验在真实链路上几乎没用。
4.2 二维奇偶校验
把数据排成矩阵，对每行和每列都算奇偶位：
列校验 ↓
1 0 1 1 | 1
1 1 1 0 | 1
0 1 1 1 | 1
─────────
0 0 1 0 | 0 ← 行校验
⭐ 二维奇偶校验可以【纠正】单个比特错误！
若第 2 行第 3 列的比特翻转：
→ 第 2 行的校验失败
→ 第 3 列的校验失败
⭐ 交点就是出错的位置 → 直接翻转它即可纠正
📌 这叫前向纠错（FEC, Forward Error Correction）：接收方不需要重传就能修复错误。
FEC 的价值：在 RTT 很大（卫星）或不可能重传（实时音视频、广播）的场景下，它是唯一的选择。现代 FEC（Reed-Solomon、LDPC、Turbo 码）能力远强于二维奇偶校验，是 4G/5G、DVB、DVD 的基础。
4.3 循环冗余校验（CRC）⭐
这是链路层实际使用的方法。
数学基础：把比特串看作模 2 多项式的系数。
比特串 101011 → 多项式 x⁵ + x³ + x + 1
约定：
D = 要发送的 d 位数据
G = 生成多项式（r+1 位，⭐ 收发双方【事先约定】）
R = r 位的 CRC 校验码
发送方的目标：选择 R 使得
⭐ <D, R>（D 后面接上 R）能被 G 【整除】（模 2 运算）
接收方的检查：把收到的 <D', R'> 除以 G。
余数 = 0 → 认为无差错
余数 ≠ 0 → ⭐ 检出差错
模 2 运算规则
⭐ 模 2 加法和减法都等同于 XOR（异或），没有进位和借位。
0 + 0 = 0 0 − 0 = 0
0 + 1 = 1 0 − 1 = 1 ⭐ 注意：没有借位
1 + 0 = 1 1 − 0 = 1
1 + 1 = 0 1 − 1 = 0
计算步骤
① 在 D 后面补 r 个 0，得到 D·2ʳ
② 用 D·2ʳ 模 2 除以 G，得到余数 R
③ 发送 <D, R>
完整手算示例 ⭐
D = 101110 （6 位数据）
G = 1001 （4 位生成多项式，所以 r = 3）
第 1 步：D 后补 3 个 0
101110000
第 2 步：模 2 除法（用"余数寄存器"逐位下移的写法，最不容易错）
被除数: 1 0 1 1 1 0 0 0 0 除数 G = 1001
取前 4 位 1011
首位为 1 → XOR 1001
────
余 0010 → 记作 010
下移第 5 位 '1' → 0101 首位为 0，不做 XOR → 余 101
下移第 6 位 '0' → 1010 首位为 1 → XOR 1001 → 余 011
下移第 7 位 '0' → 0110 首位为 0，不做 XOR → 余 110
下移第 8 位 '0' → 1100 首位为 1 → XOR 1001 → 余 101
下移第 9 位 '0' → 1010 首位为 1 → XOR 1001 → 余 011
⭐ 所有位处理完毕，余数 R = 011
💡 手算口诀：维持一个 4 位的窗口；首位是 1 就 XOR 除数，首位是 0 就直接下移；把被除数的位一个一个补进窗口右端。这样永远不会算错。
第 3 步：发送
<D, R> = 101110 011 （9 位）
接收方验证：
101110011 ÷ 1001 (模 2) → 余数应为 000 ✅
CRC 的检错能力 ⭐
一个 r 位的 CRC 能保证检出：
| 差错类型 | 能否检出 |
|---|---|
| 所有单比特错误 | ✅ |
| 所有奇数个比特错误 | ✅（若 G 含因子 x+1） |
| 所有双比特错误 | ✅（若 G 选得好） |
| ⭐ 所有长度 ≤ r 的突发错误 | ✅ 全部检出 |
| 长度 > r 的突发错误 | 漏检概率 ≈ 2⁻ʳ |
常用标准：
CRC-8 ：ATM 头部
CRC-16 ：USB、Modbus
⭐ CRC-32 ：以太网、ZIP、PNG → 漏检率 ≈ 2⁻³² ≈ 2.3×10⁻¹⁰
📌 突发错误检测能力是关键：真实链路上的差错几乎都是突发的（一次电磁干扰破坏连续几十个比特）。CRC-32 能保证检出所有长度不超过 32 位的突发错误——这覆盖了绝大多数实际情形。
五、为什么强校验在链路层、弱校验在传输层 ⭐
这是一道极好的综合题，把第 10 讲和本讲连了起来。
| 传输层校验和 | 链路层 CRC | |
|---|---|---|
| 算法 | 16 位反码和 | CRC-32 |
| 漏检率 | ≈ 2⁻¹⁶ ≈ 1.5×10⁻⁵ | ≈ 2⁻³² ≈ 2.3×10⁻¹⁰ |
| 计算方式 | ⭐ 软件，CPU 逐字节 | ⭐ 硬件，专用电路 |
| 覆盖范围 | ⭐ 端到端（含路由器内存中的损坏） | ⭐ 单跳 |
两个原因：
1️⃣ 实现成本不同
链路层在 NIC 硬件里，CRC 用移位寄存器电路实现，几乎零成本。传输层校验和要 CPU 对每个字节做加法——必须简单，否则会成为性能瓶颈。
2️⃣ 覆盖范围不同，因此二者缺一不可
⭐ CRC 强，但只覆盖【一段链路】
→ 分组在路由器【内存中】损坏时，CRC 完全无能为力
→ 而这类错误真实存在（内存位翻转、软件 bug、中间件改写）
⭐ 校验和弱，但覆盖【端到端全程】
🎯 这就是端到端原则的完整论证形式（第 4 讲）： 逐跳的检查再强，也无法替代端到端的检查。二者不是冗余，是分工。
⚠️ 一个必须记住的工程结论：
传输层校验和的漏检率是 ~10⁻⁵。
在今天的高速链路上，这意味着【每传输几十 GB 就可能有一个未被检出的错误】。
⭐ 因此对数据完整性有严格要求的应用（文件同步、数据库复制、软件分发），
必须在应用层再做一次强校验（SHA-256）。
**这又是端到端原则。**它在这门课里出现了第四次。
六、例题（Worked Example）
题目：
(a) 数据 D = 1101011011，生成多项式 G = 10011。计算 CRC 并写出要发送的比特串。
(b) 接收方收到 11010110111110，用同样的 G 验证是否有错。
(c) 若一个突发错误破坏了连续 5 个比特，本例中的 CRC 一定能检出吗？
(d) 说明为什么即使 CRC 校验通过，TCP 校验和仍然是必要的。
解答：
(a)
G = 10011（5 位）→ r = 4
D 后补 4 个 0: 1101011011 0000 （14 位）
按上面的口诀逐位计算（窗口宽 5 位）：
取前 5 位 11010 → XOR 10011 → 余 1001
下移 '1' → 10011 → XOR 10011 → 余 0000
下移 '1' → 00001 → 首位 0 → 余 0001
下移 '0' → 00010 → 首位 0 → 余 0010
下移 '1' → 00101 → 首位 0 → 余 0101
下移 '1' → 01011 → 首位 0 → 余 1011
下移 '0' → 10110 → XOR 10011 → 余 0101
下移 '0' → 01010 → 首位 0 → 余 1010
下移 '0' → 10100 → XOR 10011 → 余 0111
下移 '0' → 01110 → 首位 0 → 余 1110
⭐ 余数 R = 1110
要发送的比特串：
<D, R> = 1101011011 1110 （14 位）
(b)
接收到的 11010110111110 正是 (a) 中发送的串。用 G = 10011 去除：
⭐ 余数 = 0000 → 未检出差错
📌 注意措辞：是「未检出差错」，不是「一定没有差错」。存在极小概率（≈2⁻⁴，本例 r 只有 4 位）差错模式恰好使余数为 0。
(c) 不保证能检出。
本例中 r = 4，CRC 的保证是：所有长度 ≤ r 的突发错误一定被检出。题目给出的突发长度是 5 > 4，落在保证范围之外，漏检概率约为 2⁻⁴ = 6.25%。
⭐ 这个例子恰好说明了 r 的重要性：4 位 CRC 的保护能力很弱，6% 的漏检率在工程上完全不可接受。以太网使用 CRC-32（r = 32），能保证检出所有长度不超过 32 位的突发错误，超长突发的漏检率也只有约 2.3×10⁻¹⁰——这才是实用的强度。
(d) 因为 CRC 只覆盖一段链路。分组在路由器内部（从入端口收下、存入内存、查表、送到出端口）的整个过程中：
① 入链路的 CRC 在收帧时被验证，然后【帧头和 CRC 都被剥掉】
② 分组以 IP 数据报的形式存在于路由器内存中 —— ⭐ 此时【没有任何链路层保护】
③ 出端口重新计算 CRC，封装成新帧发出
⭐ 如果在第 ② 步发生了内存位翻转（宇宙射线、硬件故障、软件 bug、NAT 改写出错），出端口会为【已经损坏的数据】计算一个【完全正确的】新 CRC。
下游的每一跳 CRC 都会通过，错误一路畅通无阻地到达目的地。
唯一能检出这类错误的，是端到端的 TCP/UDP 校验和。
七、随堂自测
- 链路层的六种服务分别是什么？哪些是可选的？
- 什么样的链路会做链路层可靠交付？为什么光纤链路不做？
- 链路层为什么必须在硬件中实现？
- 什么是字节填充？它在本课程中还以什么形式出现过？
- 一维奇偶校验能检出什么、检不出什么？为什么它在真实链路上没用？
- 二维奇偶校验能纠错吗？原理是什么？这属于什么技术？
- 写出 CRC 的发送方目标和接收方检查方法。模 2 加法等同于什么运算？
- 一个 r 位的 CRC 能保证检出多长的突发错误？
- ⭐ 为什么链路层用 CRC-32 而传输层只用 16 位校验和？给出两个理由。
- 举一个 CRC 全部通过但数据仍然损坏的场景。
八、本讲要点回顾
- 链路层服务：成帧（必须）、链路接入、可靠交付（可选）、差错检测（必须）、纠错、流量控制。
- ⭐ 低误码链路不做链路层重传，高误码（无线）链路做——端到端原则的精确应用。
- 链路层主体在网卡硬件里，因为要在线速下完成 CRC 和 MAC 协议。
- 字节填充解决「边界符号出现在数据中」的问题——与 SMTP 点填充同构。
- 一维奇偶校验检不出偶数个错误；二维奇偶校验可纠正单比特错误（FEC）。
- CRC：找 R 使
<D,R>能被 G 模 2 整除；模 2 加减 = XOR。 - ⭐ r 位 CRC 保证检出所有长度 ≤ r 的突发错误；CRC-32 漏检率约 2⁻³²。
- ⭐ 强校验在链路层（硬件、单跳），弱校验在传输层（软件、端到端）——二者是分工不是冗余。
- 路由器内存中的损坏只能由端到端校验发现。
九、自测答案
1. 成帧（必须）、链路接入/MAC（共享介质才需要）、可靠交付（可选）、差错检测（必须）、差错纠正（可选，无线常用）、流量控制（可选）。此外还有半双工/全双工的区分。
2. 高误码率的链路会做链路层可靠交付，典型是 802.11 无线（有链路层 ACK 与重传）。光纤等低误码率链路不做，因为差错极为罕见，为它增加确认与重传机制的开销、时延和复杂度不划算——偶尔出现的差错交给 TCP 的端到端重传处理即可。在无线链路上则相反：误码频繁，若每次都让 TCP 用 RTT 级的超时（甚至误判为拥塞而降速）去恢复，性能损失巨大，因此在链路层就地快速重传更划算。
3. 因为链路层要在线速下完成 CRC 计算、载波侦听、碰撞检测和成帧——这些操作对时间极其敏感（微秒到纳秒级）。以 100 Gbps 链路为例，一个 64 字节帧只占 5.12 ns，软件无论如何都跟不上。硬件实现（NIC 中的专用电路）还让 CRC-32 这样"昂贵"的算法几乎变成零成本。
4. 字节填充：当帧的定界符（FLAG）出现在数据内容中时，发送方在它前面插入一个转义字节（ESC），接收方遇到 ESC 就把下一个字节当作普通数据而非定界符（ESC 自身出现时也要转义）。本课程中它以 **SMTP 的「点填充」**形式出现过（第 8 讲）——报文以单独一行的 . 结束，因此正文中行首的 . 要被写成 ..。同一个"边界符号 vs 数据透明"问题，在应用层和链路层有完全相同的解法。
5. 能检出任意奇数个比特错误；检不出偶数个错误（两位翻转后奇偶性不变）。它在真实链路上没用，是因为实际差错往往是突发的——一次电磁干扰会连续破坏多个比特，其中出错位数为偶数的概率约为一半，漏检率高得无法接受。
6. 能纠正单个比特错误。原理：一个比特翻转会同时导致它所在的行校验失败和列校验失败，两者的交点唯一确定了出错位置，把该位翻转回去即可。这属于前向纠错（FEC）——接收方无需重传就能修复错误，适用于 RTT 很大（卫星）或无法重传（实时音视频、单向广播）的场景。
7. 发送方目标：选择 r 位的 R，使得 <D, R>（D 后接 R）在模 2 意义下能被生成多项式 G 整除（余数为 0）。做法是把 D 左移 r 位（补 r 个 0）后模 2 除以 G，所得余数即为 R。接收方检查：把收到的整个 <D', R'> 模 2 除以 G，余数为 0 则认为无差错，非 0 则检出差错。模 2 加法和减法都等同于 XOR（异或），没有进位和借位。
8. 保证检出所有长度 ≤ r 的突发错误。对于长度大于 r 的突发错误，漏检概率约为 2⁻ʳ。以太网的 CRC-32 因而能保证检出所有 32 位以内的突发错误，漏检率约 2.3×10⁻¹⁰。
9. ① 实现成本不同：链路层的 CRC 由 NIC 中的专用移位寄存器电路完成，几乎零开销；传输层校验和由 CPU 对每个字节做加法，必须足够简单，否则会成为吞吐量瓶颈。② 覆盖范围不同：CRC 强但只覆盖一段链路，无法保护分组在路由器内存中停留时发生的损坏；校验和弱但覆盖端到端全程。因此二者不是冗余而是分工——逐跳的强校验无法替代端到端的弱校验。
10. 分组到达路由器时，入链路的 CRC 校验通过，帧头和 CRC 被剥离，IP 数据报存入路由器内存等待转发。在内存中停留期间发生了位翻转（宇宙射线导致的软错误、内存硬件故障、路由器软件 bug、NAT 改写时的错误）。出端口随后对已经损坏的数据重新计算 CRC 并封装成新帧——这个新 CRC 是完全正确的。此后每一跳的 CRC 都会通过，损坏的数据一路畅通到达目的主机。只有端到端的 TCP/UDP 校验和（以及应用层的强校验）才可能发现它。