一、拥塞是什么
拥塞：太多源以太快的速度发送太多数据，超过了网络的处理能力。
⚠️ 再次强调与流量控制的区别（第 14 讲）：
流量控制：一对一的问题 —— 发送方 vs 接收方缓冲区
拥塞控制：多对多的问题 —— 所有共享路径的连接 vs 路由器队列
关键难点：拥塞发生在网络内部，而控制必须由端系统完成（端到端原则，第 4 讲）。端系统看不到路由器队列的长度，只能靠间接信号（丢包、时延变化）推断。
二、拥塞的代价：三个场景
场景 1：两个发送方，一台路由器，无限缓冲区
主机 A ──λin──┐
├──→ [路由器，无限缓冲] ──R bps──→
主机 B ──λin──┘
- 无重传（假设不丢包，因为缓冲区无限）
- 链路容量 R
吞吐量 λout
↑
R/2├ ─ ─ ─ ─ ─ ─ ─╱──────── 时延
│ ╱ ↑
│ ╱ │ │
│ ╱ │ ╱│
│ ╱ │ ╱ │
└──────────────→ λin └────────────┴──→ λin
0 R/2 0 R/2
结论：
- 吞吐量最多到 R/2（两个流平分）
- ⭐ 当 λin → R/2 时，排队时延 → 无穷大
代价 1：当到达速率接近链路容量时，时延变得不可接受。
这正是第 3 讲那条 La/R → 1 曲线。
场景 2：有限缓冲区，发送方重传丢失的分组
现在缓冲区有限，会丢包，发送方重传。
引入区分：
λin = 应用层发送的原始数据速率
λ'in = 传输层实际发送的速率（原始 + 重传）
λout = 接收方收到的原始数据速率（"有效吞吐量" / goodput）
三种情形：
(a) 理想情况（发送方神奇地知道何时缓冲区有空）：λout = λin，无重传。
(b) 只在确知丢包时重传：
λ'in > λin （多出的是重传）
λout < λ'in （重传的分组不算新数据）
代价 2：为了补偿丢包，发送方必须重传，这些重传消耗了链路容量却不增加有效吞吐量。
(c) 过早超时，重传了并未丢失的分组：
路由器要转发【同一个分组的多个副本】
→ 有效吞吐量进一步下降
代价 3：不必要的重传让路由器做无用功，浪费了本可用于新数据的容量。
📌 这解释了第 13 讲为什么 TCP 的超时估计要保守（Est + 4·Dev）：宁可慢一点重传，也不要在拥塞时用多余的重传火上浇油。
场景 3：四个发送方，多跳路径
A ──┐ ┌── C
├─→ [R1] ──→ [R2] ──→ [R3] ───┤
B ──┘ ↑ ↑ └── D
│ │
每一跳都有其他流竞争
设 A→C 的流量要经过 R1、R2 两跳。
当所有流都加大发送速率时：
A 的分组成功通过 R1（消耗了 R1 的容量）
⭐ 却在 R2 处被丢弃
→ R1 在这个分组上花费的传输容量【完全白费】
极端情形：所有流都拼命发，最终 λout 趋近于 0。
吞吐量 λout
↑
│ ╱╲
│ ╱ ╲
│ ╱ ╲___________
└────────────────────→ λ'in
⭐ 代价 4（最严重的）：当一个分组沿路径被丢弃时，它在所有上游链路上所消耗的传输容量都被浪费了。
这就是拥塞崩溃（congestion collapse）。
三、1986 年：拥塞崩溃真的发生了
这不是理论。
1986 年 10 月，NSFNET 骨干网的一段链路（劳伦斯伯克利实验室到加州大学伯克利分校，相距 400 米）的吞吐量从 32 kbps 崩溃到 40 bps——下降了 1000 倍。
原因：当时的 TCP 没有拥塞控制。丢包 → 超时 → 重传 → 更多拥塞 → 更多丢包 → 更多重传……正反馈。
后果：Van Jacobson 在 1988 年的论文 Congestion Avoidance and Control 中提出了慢启动、拥塞避免、快速重传——这些机制至今仍是所有 TCP 实现的核心（第 16 讲）。
📌 **这是计算机网络史上最重要的事件之一。**它确立了一条原则：
在一个共享的、无准入控制的网络里，端系统必须自愿限制自己的发送速率，否则系统会集体崩溃。
⚠️ 这也是为什么「用 UDP 就能更快」是一种危险的想法（第 10 讲）。如果所有人都这么做，就是 1986 年重演。这也是 QUIC 必须自带拥塞控制、WebRTC 必须实现 GCC 的原因。
四、两种控制方式
4.1 端到端拥塞控制
网络【不提供任何显式反馈】
端系统只能从【丢包】和【时延】推断拥塞
- ⭐ 这是 TCP 采用的方式
- 优点：不需要网络支持，可增量部署，符合端到端原则
- 缺点：信号是间接的、滞后的。而且「丢包 = 拥塞」这个假设在无线链路上是错的（误码也会丢包，第 25 讲）
4.2 网络辅助拥塞控制
路由器【显式告知】端系统当前的拥塞状态
两种形式：
| 形式 | 说明 | 例子 |
|---|---|---|
| 单比特指示 | 「我拥塞了」 | ⭐ ECN（第 16 讲） |
| 显式速率 | 「你最多发 X bps」 | ATM ABR 的 ER 字段 |
- 优点：信号准确、及时，可以在丢包之前就通知
- 缺点：需要路由器支持，部署困难（沙漏模型的窄腰难以改变，第 4 讲）
📌 ECN（Explicit Congestion Notification）是今天唯一被广泛部署的网络辅助机制，它在 IP 头部用 2 个比特标记「即将拥塞」，由接收方通过 TCP 头部的 ECE 标志回传给发送方（第 16 讲详讲）。
五、公平性
如果 K 条 TCP 连接共享一条速率为 R 的瓶颈链路，每条应该得到多少？
5.1 TCP 公平性
若每条连接的平均吞吐量都是 R/K，则该拥塞控制机制是公平的。
5.2 最大最小公平（Max-Min Fairness）
更一般的定义（多瓶颈情形）：
在不减少任何一条已经更小的流的速率的前提下，无法再增加任何一条流的速率。
直观算法：「注水法」——所有流均等增长，谁先撞到自己路径上的瓶颈谁就停下，剩余容量由其余流继续均分。
5.3 现实中的三个不公平
⚠️ TCP 的公平性在实践中有严重的漏洞：
1️⃣ RTT 不公平
吞吐量 ∝ 1 / RTT
同一条瓶颈链路上，RTT 20 ms 的连接吞吐量约是 RTT 200 ms 连接的 10 倍。因为窗口每个 RTT 才增长一次，RTT 短的涨得快。
2️⃣ 并行连接
一个应用开 6 条 TCP 连接（第 6 讲的浏览器行为），就拿到 6 份带宽份额。TCP 公平的是「连接」，不是「用户」或「应用」。
📌 这是一个协议层面无法解决的问题：TCP 没有办法知道 6 条连接属于同一个用户。要解决它必须在网络里做（按用户排队）或在应用层自律。
3️⃣ UDP 完全不参与
不受控的 UDP 流会挤占所有让步的 TCP 流的带宽。
六、AIMD：这门课最优雅的结论 ⭐⭐
6.1 四种候选策略
发送方如何调整发送窗口 w？两种动作各有两种形式：
| 增（无拥塞时） | 减（拥塞时） | |
|---|---|---|
| 加性 A | w = w + a | w = w − b |
| 乘性 M | w = w × a | w = w × b |
组合出四种策略：AIAD、AIMD、MIAD、MIMD。
哪一种能同时收敛到「公平」和「高效」？
6.2 相图（Chiu & Jain, 1989）
考虑两条连接共享容量 R 的链路。横轴是连接 1 的吞吐量 x₁，纵轴是连接 2 的吞吐量 x₂。
x₂
↑
R ┤╲
│ ╲ ⭐ 目标点：两线交点
│ ╲ ╱
│ ╲ ╱ ← 公平线 (x₁ = x₂)
│ ⊙ ╳
│ ╱ ╲
│ ╱ ╲ ← 效率线 (x₁ + x₂ = R)
│ ╱ ╲
└────────────────╲──→ x₁
0 R
效率线以下：链路未充分利用（无拥塞）→ 应当【增】
效率线以上：链路过载（拥塞） → 应当【减】
公平线上：两条连接得到相同带宽
目标：让系统状态收敛到两线的交点。
6.3 AIMD 的轨迹
从任意点 (x₁, x₂) 出发：
【加性增】w += a
两条连接【各自加同样的量】
→ 在相图上沿【45° 方向】移动
⭐ 平行于公平线移动 —— 不改变差距，但改变绝对值
【乘性减】w × b（如 b=0.5）
两条连接【各自乘同样的比例】
→ 在相图上沿【指向原点的直线】移动
⭐ 差距按比例缩小 —— x₁−x₂ 也乘以了 b
轨迹：
x₂
↑ ①加性增（45°）→ 越过效率线
│ ╲ ╱ ②乘性减（朝原点）→ 差距缩小
│ ╲╱ ③加性增 → 再次越线
│ ↗ ╱╲ ④乘性减 → 差距再缩小
│ ↙╱ ╲ ...
│ ╱ ↗ ╲ ⭐ 螺旋收敛到交点
└─────────────→ x₁
⭐ 每一轮「加性增 + 乘性减」，两条流的差距 |x₁ − x₂| 都乘以 b < 1，因此指数收敛到 0。
6.4 为什么其他三种不行
| 策略 | 增（45°平行公平线） | 减 | 结果 |
|---|---|---|---|
| AIAD | ✅ 差距不变 | ❌ 减法，差距也不变 | 差距永不缩小，不收敛到公平 |
| MIMD | ❌ 乘法，差距按比例放大 | ✅ 差距按比例缩小 | 二者抵消，差距不变 |
| MIAD | ❌ 差距放大 | ❌ 差距不变 | 越来越不公平 ❌ |
| ⭐ AIMD | ✅ 差距不变 | ✅ 差距按比例缩小 | 收敛到公平且高效 ✅ |
🎯 这是整门课最漂亮的结论之一： 一个极其简单的规则（涨的时候加一点，跌的时候砍一半），被数学证明能让完全分布式的、互不通信的、自私的参与者收敛到公平分配。 没有中央协调者，没有谈判，没有信任——规则本身产生了秩序。
📌 顺带一提：AIMD 的收敛性对参与者数量、初始状态都不敏感。这种鲁棒性是它能在真实互联网上工作三十多年的根本原因。
6.5 AIMD 的锯齿
拥塞窗口
↑
│ ╱│ ╱│ ╱│ ╱│ ← 加性增：每 RTT +1 MSS
│ ╱ │╱ │╱ │╱ │
│╱ ↓ ↓ ↓ ↓ ← 乘性减：丢包时 ÷2
└──────────────────────→ 时间
⭐ **TCP 的吞吐量永远在震荡，从不稳定。**这不是缺陷——震荡正是探测可用带宽的手段。TCP 不知道链路有多宽，只能「一直涨到出问题，退回来，再涨」。
七、例题（Worked Example）
题目：两条 TCP 连接共享一条 10 Mbps 的瓶颈链路。初始时连接 1 得到 8 Mbps，连接 2 得到 2 Mbps。采用 AIMD：每轮无拥塞时各加 0.5 Mbps，拥塞时各乘 0.5。
(a) 前三轮的演化过程是什么？ (b) 差距如何变化？ (c) 若改用 AIAD（拥塞时各减 1 Mbps），差距如何变化？ (d) 从中得出什么结论？
解答：
(a) AIMD 的逐轮演化
初始 (8.0, 2.0)，和为 10.0，已达链路容量 → 判定拥塞。
乘性减 ×0.5： (4.00, 1.00) 和 = 5.0 差距 = 3.00
加性增（每轮各 +0.5，直到和达到 10）：
(4.5, 1.5) 和 6.0
(5.0, 2.0) 和 7.0
(5.5, 2.5) 和 8.0
(6.0, 3.0) 和 9.0
(6.5, 3.5) 和 10.0 → 拥塞
乘性减 ×0.5： (3.25, 1.75) 和 = 5.0 差距 = 1.50
加性增至和 = 10：(5.375, 3.875) 差距 = 1.50
乘性减 ×0.5： (2.6875, 1.9375) 和 = 4.625 差距 = 0.75
(b) 差距的变化
6.00 → 3.00 → 1.50 → 0.75 → 0.375 → ... → 0
⭐ 注意两件事：
- 加性增阶段差距完全不变（两条流各加相同的量）
- 每一次乘性减，差距恰好乘以 0.5
因此差距按 0.5ⁿ 指数收敛到 0，系统趋向 (5.0, 5.0) 附近震荡——即公平分配。
(c) 若改用 AIAD（拥塞时各减 1 Mbps）
初始： (8.0, 2.0) 差距 = 6.0
加性减 −1： (7.0, 1.0) 差距 = 6.0 ❌ 不变
加性增 +0.5×2 轮至和=10： (8.0, 2.0) 差距 = 6.0 ❌ 不变
加性减 −1： (7.0, 1.0) 差距 = 6.0
...
差距永远是 6.0。系统会在效率线附近震荡（吞吐量是高效的），但连接 1 永远拿 8 Mbps，连接 2 永远拿 2 Mbps——初始的不平等被永久固化。
(d) 结论
⭐ 乘性减是公平性的唯一来源。
加性增只负责「探测还有没有更多带宽可用」，它在相图上平行于公平线移动，对公平性是中性的；只有乘性减（沿指向原点的射线移动）才能按比例压缩两条流之间的差距。
⚠️ 这给出一个反直觉的事实：**TCP 的公平性不是靠「涨得慢」实现的，而是靠「跌得狠」实现的。**如果 TCP 在丢包时只线性地减一点点，互联网上的带宽分配将永远保持最初的不平等，先来的连接会一直占优。
📌 顺带回答一个常见疑问：为什么减半（b=0.5）而不是减到 0.9 或 0.1？b 越小收敛越快但吞吐量损失越大，b 越大越平滑但收敛越慢。0.5 是收敛速度与带宽利用率之间的经典折中；后来的 CUBIC 把它调整为 0.7（第 16 讲），正是因为在高速链路上 0.5 的损失太大了。
八、随堂自测
- 拥塞控制与流量控制的三点区别是什么？
- 说出拥塞的四种代价，并指出哪一种最严重、为什么。
- 1986 年发生了什么？它确立了什么原则？
- 端到端与网络辅助拥塞控制各自的优缺点是什么？为什么 TCP 选了前者？
- 给出 TCP 公平性和最大最小公平性的定义。
- 说出 TCP 公平性在实践中的三个漏洞。
- ⭐ 用相图论证为什么 AIMD 收敛而 AIAD 不收敛。
- 为什么说 TCP 吞吐量的锯齿震荡不是缺陷？
九、本讲要点回顾
- 拥塞的四个代价：大排队时延、重传消耗容量、不必要重传做无用功、⭐ 上游链路的投入被下游丢包浪费。
- 拥塞崩溃在 1986 年真实发生过，吞吐量下降 1000 倍。
- 两种方式：端到端（TCP，靠推断） 与 网络辅助（ECN，靠显式标记）。
- 公平性有三个现实漏洞：RTT 偏向、并行连接、UDP 不参与。
- ⭐ AIMD 收敛到公平且高效：加性增平行于公平线（差距不变），乘性减指向原点（差距按比例缩小）。
- AIAD / MIMD / MIAD 都不能同时做到公平与高效。
- TCP 的锯齿是探测带宽的手段，不是缺陷。
十、自测答案
1. ① 保护对象：流量控制保护接收方缓冲区，拥塞控制保护网络内部的路由器队列。② 信息来源：流量控制有接收方通过 rwnd 的显式告知，拥塞控制只能从丢包/时延间接推断。③ 参与范围：流量控制是两个端点之间的事，拥塞控制涉及所有共享该路径的连接，是一个多方博弈。
2. ① 到达速率接近容量时排队时延趋于无穷；② 丢包迫使重传，重传消耗容量却不产生新的有效吞吐量；③ 过早超时导致不必要的重传，路由器为同一分组的多个副本做无用功；④ ⭐ 一个分组在下游被丢弃时，它在所有上游链路上消耗的容量全部白费——这一条最严重，因为它意味着发送得越多，有效吞吐量反而越低，构成正反馈，是拥塞崩溃的直接机制。
3. 1986 年 NSFNET 上一段链路的吞吐量从 32 kbps 崩溃到 40 bps，因为当时的 TCP 没有拥塞控制，丢包触发重传、重传加剧拥塞形成正反馈。它确立的原则是：**在一个共享的、没有准入控制的网络中，端系统必须自愿限制发送速率，否则系统会集体崩溃。**Van Jacobson 由此提出慢启动与拥塞避免。
4. 端到端：无需网络支持、可增量部署、符合端到端原则；但信号间接且滞后，且「丢包即拥塞」的假设在无线链路上会误判。网络辅助：信号准确及时、可在丢包前预警；但需要修改路由器，而 IP 层是沙漏的窄腰，部署极其困难。TCP 选前者，正是因为可部署性压倒了准确性——一个需要全球路由器升级才能工作的方案，在 1988 年和今天都行不通。
5. TCP 公平性：K 条连接共享速率 R 的瓶颈链路时，每条获得 R/K。最大最小公平：一种分配是最大最小公平的，当且仅当在不减少任何一条速率不大于它的流的前提下，无法再增加任何一条流的速率（等价于「注水」过程的结果）。
6. ① RTT 偏向：吞吐量约正比于 1/RTT，短 RTT 的连接抢占更多带宽。② 并行连接：TCP 公平的单位是「连接」而非「用户」，开 N 条连接就拿 N 份份额。③ UDP 不参与：不受控的 UDP 流会挤占所有让步的 TCP 流。
7. 在 (x₁, x₂) 相图中，加性增让两条流各加相同的量 a，位移向量为 (a, a)，方向为 45°，平行于公平线，因此 |x₁−x₂| 不变。乘性减让两条流各乘相同因子 b<1，新点为 (bx₁, bx₂)，位于连接原点与原点的射线上，此时 |bx₁ − bx₂| = b|x₁−x₂|，差距按比例 b 缩小。因此 AIMD 每完成一次「增-减」循环，差距乘以 b，指数收敛到 0，同时被效率线约束在高效区域。AIAD 的减法位移为 (−c, −c)，同样平行于公平线，差距永不改变——无论迭代多少次，初始的不公平被完整保留。
8. 因为 TCP 不知道瓶颈链路的容量是多少，也无法被告知（端到端方式下没有显式反馈）。它唯一能做的是不断试探：持续增加发送速率直到出现拥塞信号，然后退回。震荡正是这个试探过程的表现形式。此外，链路的可用容量本身是变化的（其他流来去），一个「稳定不变」的速率反而意味着无法适应变化——震荡是自适应的代价，也是自适应的证据。