6.1810 / 6.1810 · 第 15 课 · nz
网络编程
本节课探讨内核网络软件栈的结构与过载行为。以 Mogul & Ramakrishnan (1996) 的经典论文为核心，分析"接收活锁"（Receive Livelock）问题及其解决方案——轮询（Polling）机制。
为什么关注网络软件处理？
- 软件栈（包括 Linux）广泛用于包处理
- 低端路由器、防火墙、VPN
- 服务：DNS、Web
- 性能、设计、过载行为是热门话题
网络协议分层
以太网帧格式
| 字段 | 大小 | 说明 |
|---|
| Preamble | 8 字节 | 同步（如 10101010...10101011） |
| Destination MAC | 6 字节 | 目的以太网地址（48 位） |
| Source MAC | 6 字节 | 源以太网地址 |
| EtherType | 2 字节 | 上层协议类型 |
| Payload | 46-1500 字节 | 数据 |
| CRC-32 | 4 字节 | 校验 |
以太网地址
- 每个以太网 NIC 有唯一地址，由制造商分配
- <24 位厂商标识, 24 位序列号>
- 原始以太网是广播电缆；今天是交换机电缆到每个主机
IP 头
- 32 位 IP 地址足以路由到任何 Internet 计算机
- 高位包含"网络号"，帮助路由器理解如何转发
- 协议号告诉目的主机将包交给哪个上层协议（UDP 或 TCP）
UDP 头
- 包含源和目的端口号
- 应用使用 socket API 告诉内核接收特定端口的所有包
- 端口 53 保留给 DNS 服务器
嵌套模式
高层数据包嵌在低层数据包内：eth | ip | udp | DNS。一层的有效载荷头是下一层的头。所以你会看到一系列头的序列。
内核网络软件栈结构
数据流
接收路径：
NIC 硬件 → NIC DMA RX Ring → RX 中断处理程序 → IP 输入队列
→ 网络线程（IP 处理/转发/ socket 队列）→ 应用
发送路径：
应用 → IP 输出队列 → TX 中断处理程序 → NIC TX DMA Ring → NIC 硬件
net lab 是此结构的子集
每层做什么？
- 接收方向：解析、验证、剥离头部；损坏或队列过长则丢弃
- 发送方向：前置头部
为什么有这么多包队列？
- 吸收临时输入突发，避免软件繁忙时强制丢弃
- 计算时保持输出 NIC 忙碌
- 允许独立控制流（NIC vs 网络线程 vs 应用）
其他可能的安排
- 用户态网络栈
- 用户直接访问 NIC（如 Intel DPDK）
- 轮询（如本论文）
今日论文：消除接收活锁
背景：软件路由器非常常见（如 Linux 防火墙、线缆调制解调器、WiFi AP）。最大网络速度常超过路由器速度，因此可能发生过载。
Figure 6-1：原始系统（无修复）
路由器结构：[NIC, RX intr, input q, IP, output q, TX intr, NIC]
- 黑点向上：输入速率增加，每个包的处理时间约 200μs（峰值 @ 5000）
- 黑点向下：输入速率下降，系统恢复
问题所在
接收活锁（Receive Livelock）
- NIC 中断优先级高于所有其他处理
- 随着输入速率增长，中断最终占用 100% CPU
- 没有 CPU 时间用于 IP 处理
- IP 输入队列增长到最大长度
- NIC 中断读每个包，发现队列已满，丢弃包
高层视角：软件浪费时间为最终丢弃的包做部分处理。
理想情况应该是什么样？
如果路由器设计尽可能好，图形应该显示：在过载时，吞吐量保持稳定（不下降），丢弃的包是那些无法处理的。
论文解决方案
核心思想
- 无 IP 输入队列
- NIC 接收中断仅唤醒网络线程，然后禁用该 NIC 的中断
- 网络线程做所有处理，重新检查 NIC 是否有更多输入
- 仅当没有输入等待时才重新使能中断
轮询网络线程
while (1)
if (NIC 有包等待)
从 NIC 读一个包
完整处理该包
else
使能中断
sleep
为什么不完全轮询？
如果包到达慢，轮询浪费 CPU。中断在低负载时更高效。
Figure 6-3：修复后的系统
- 空方框持平：吞吐量在过载时保持稳定
- 不像 Figure 6-1 那样下降
- 多余包在 NIC 处尽早丢弃
"Polling (no quota)"为什么表现差？
输入处理饿死了 tx-complete 处理（发送完成中断处理）。
"no quota"为什么快速下降而非逐渐下降？
活锁因丢弃前做更多处理而加剧——每个多余的 rx 包消耗许多 tx 包的 CPU 时间。
Figure 6-4：用户级程序场景
- "Polling, no feedback"：screend 前有过载队列，net thread 占用 100%，screend 为 0%
- "Polling w/ feedback"：当到 screend 的队列接近满时 net thread 睡眠，队列接近空时唤醒
大局观：轮询循环是施加调度控制的地方
通过配额（quota）和反馈（feedback），可以控制资源分配，避免活锁和饥饿。
通用原则
- 不要开始新工作，如果那可能阻止现有工作的完成
- 需要丢弃时，尽早丢弃
- 设计使效率随负载增加而增加，而非减少——如论文从中断切换到轮询
其他方法
| 方法 | 说明 |
|---|
| 中断合并 | 积累多个事件后一次性中断 |
| 多核 + 多 NIC 队列 | 分散处理负载 |
| 用户态 NIC 访问（DPDK） | 绕过内核栈 |
类似现象在其他系统领域
- 网络中的超时 + 重传，随连接数增长
- 自旋锁，随核心数增长
一般教训
复杂（多阶段）系统需要仔细调度资源才能在过载中存活。
Linux NAPI
Linux 的 NAPI（New API）方案受此论文启发，结合中断和轮询：
- 包到达时中断
- 中断处理程序禁用该 NIC 中断，调度轮询
- 轮询处理积累的包
- 没有更多包时重新使能中断
测验
Q1："接收活锁"（Receive Livelock）是什么？
Q2：论文的核心解决方案是什么？
Q3：为什么需要配额（quota）和反馈（feedback）？
Q4：为什么不完全使用轮询（始终轮询）？
Q5：论文对现代系统的主要影响是什么？
要点总结
协议分层
eth → IP → UDP/TCP → 应用。每层解析/剥离或添加头部。
内核网络栈
NIC DMA、中断处理程序、IP 处理线程、socket 队列组成流水线。
接收活锁
高中断率使 CPU 陷入中断处理，无时间做实际工作，吞吐量崩塌。
轮询 + 反馈
在中断和轮询间切换，通过配额和反馈控制资源分配。
延伸阅读