Lec 2 端到端拥塞控制

阅读资料：

• V. Jacobson and M. Karels, Congestion Avoidance and Control, 1988

  • 奠定了现代 TCP 拥塞控制的基础
  • 引入著名的加性增乘性减（AIMD），两个机制——慢启动、拥塞避免
  • Jacobson 是网络泰斗级人物，发明tcpdump、traceroute工具

• UDP

• TCP

• 拥塞控制

这篇论文回答一个看似不可能的问题：在不改动任何路由器、只动两端软件的前提下，怎么让一个会崩溃的网络稳定下来？ 它定义了今天 TCP 拥塞控制的全部骨架。读懂它的关键不是记住四个算法的名字，而是理解它们各自在解决"控制论"上的哪一步。

1. 出发点：1986 年的拥塞崩溃

1986 年 10 月，Jacobson 观察到一个诡异现象：LBL 到 UC Berkeley 之间（物理上只隔约 400 码、中间两跳）的吞吐量，从正常的 32 Kbps 暴跌到 40 bps——掉了近 1000 倍。网络没坏，链路也通，但实际有用的传输几乎停摆。这种状态被称为拥塞崩溃（congestion collapse）。

它的成因是一个正反馈环：

链路拥塞 → 排队 → 时延变大 / 丢包
        ↑                     ↓
   注入更多副本  ←  发送方超时，重传

发送方看到迟迟没有 ACK，就重传；重传的副本进一步加重已经拥塞的链路；时延更大，于是更多连接超时、重传更多……网络里跑的几乎全是重复副本，有用吞吐趋近于零。

注意问题的约束：当时不可能要求全网路由器升级。所以 Jacobson 给自己定的目标是——纯端点方案。这正好呼应 Lec 2 的端到端原则：能在端点解决的，就不要动网络核心。

2. 总纲：分组守恒原则

整篇论文的理论支点只有一句话：

IMPORTANT

一个处于平衡态（equilibrium）的连接应当是守恒的——只有当一个"旧"分组离开网络（被确认）时，才把一个"新"分组放进去。

先说清楚"平衡态"：指连接已经把恰好"一个带宽时延积"那么多的数据填进了管道，稳定地跑着。一个守恒的连接为什么不会引发拥塞？因为网络里的在途分组总数恒定，等于管道容量——既不会越填越多导致溢出，也没有浪费。

Jacobson 指出，一个连接只会因三种方式破坏守恒、从而引发拥塞：

1. 还没进入平衡态就乱发（启动阶段的问题）→ 第 3 节用 slow start 解决；
2. 旧分组还没出去就注入了新分组（发送方对网络容量估计错误）→ 第 4 节用 congestion avoidance 解决；
3. 由于资源限制根本到不了平衡态（例如把别人挤掉的流量误判）→ 用正确的超时估计避免，见第 5 节。

换句话说，论文后面所有机制，都是在堵住"破坏守恒"的这三个漏洞。

3. 自时钟：为什么滑动窗口本身就是稳定的

要理解 slow start，必须先理解自时钟（self-clocking / ack-clocking）——这是整篇论文最漂亮的洞见。

设想数据流经一条管道，瓶颈链路的服务速率最慢。把分组想象成一段段水流，经过瓶颈时会被"拉开"成固定间距，这个间距 $P_b$ 就是瓶颈链路发送一个分组所需的时间：

发送端                    瓶颈(最慢)                接收端
 │ ▓▓▓▓ │ ───────────►  │ ▓  ▓  ▓  ▓ │ ──────►  │ ▓  ▓  ▓  ▓ │
 紧凑发出                被瓶颈拉开,间距=Pb         保持间距到达
                                                       │
        ACK 也以间距 Pb 返回  ◄───────────────────────┘

接收方每收到一个分组回一个 ACK，于是 ACK 回到发送方时的间距，也恰好是 $P_b$。发送方的规则是"收到一个 ACK 才发一个新分组"，因此它的发送节奏被 ACK 自动"卡"到了瓶颈速率上——不快不慢。

这就是结论：一旦进入平衡态，滑动窗口协议会自我稳定，发送速率自动等于瓶颈带宽，无需任何人显式告诉它速率是多少。ACK 流就是网络给发送方的天然时钟信号。

剩下的两个真问题就清楚了：

• 怎么"启动"这个时钟？（一开始没有 ACK 可用来卡节奏）→ slow start。
• 窗口该开到多大？（开小了浪费带宽，开大了破坏守恒）→ congestion avoidance。

Figure 1: Window Flow Control 'Self-clocking'

本图表示发送方与接收方通过高带宽网络相连，但中间经过一个较慢的长距离网络。
图中纵轴表示带宽，横轴表示时间，每个阴影矩形表示一个数据包。
满足关系：Bandwidth × Time = Bits，因此每个矩形面积对应数据包大小。
发送方刚开始发送数据，并一次性（back-to-back）发送一个窗口大小的数据包，此时第一个数据包的 ACK 正在返回发送方（左下角漏斗处竖线）。
由于数据包在网络中比特数不变，当进入瓶颈链路时必须在时间上“拉伸”。
定义P_b 为瓶颈链路的最小包间隔（bottleneck spacing）。
当数据包离开瓶颈链路进入接收端网络后，包间隔保持不变，因此：P_r = P_b。
若接收端处理时间一致，则 ACK 间隔为：A_r = P_r = P_b。
若 P_b 足够容纳一个数据包，则也足够容纳 ACK，因此 ACK 间隔在返回路径保持不变：A_s = P_b。
因此，如果后续发送严格由 ACK 触发，则发送端发送间隔将精确匹配路径中最慢链路的传输时间。

4. Slow Start：如何平稳进入平衡态

启动时的困境：连接刚建立，发送方手里没有任何 ACK 来给它"打拍子"。如果它一上来就按通告窗口（receiver window）一口气把一整窗数据塞进去，就会在瓶颈处形成一个突发（burst），瞬间挤爆路由器缓冲——这恰恰是要避免的事。

Slow start 用一个新增的状态变量拥塞窗口 cwnd 来逐步把时钟"摇"起来：

初始:           cwnd = 1
每收到 1 个 ACK: cwnd += 1
实际发送窗口:    min(cwnd, 接收方通告窗口)

分析它的增长速度：一个 RTT 内，发出去 cwnd 个分组、收回 cwnd 个 ACK，每个 ACK 让 cwnd 加一，所以一个 RTT 后 cwnd 翻倍。于是

$$\text{cwnd}=1,2,4,8,\dots ,2^k(\text{第 }k\text{ 个 RTT})$$

要达到窗口 $W$ 只需 ${\log }_{2}W$ 个 RTT——非常快。

这里有个常被误解的点：名字叫 "slow" start，但增长其实是指数的。"慢"是相对于旧 TCP "开局直接灌满一整窗"而言：它在最开始的几个 RTT 里确实是从 1 起步、缓缓铺开的，目的就是温柔地把 ACK 时钟启动起来，不制造突发。等时钟一旦转起来，自时钟机制就接管稳定性了。

5. Congestion Avoidance：探测并跟踪"正确"的窗口

Slow start 解决"进入平衡态"，但平衡态对应的窗口大小——也就是瓶颈到底有多少可用带宽——是未知的，而且随别的流来去而时变。这是一个典型的控制问题：在看不到网络内部状态的情况下，发送方只能主动试探着加，遇到拥塞信号就退。

拥塞信号是什么？ 论文的一个工程假设：在一个良好设计的网络里，传输位错误率极低，所以丢包几乎总是缓冲溢出造成的，而缓冲溢出就意味着拥塞。因此——丢包 = 拥塞信号。这个假设在有线网成立，但在无线网会失效（这正是 Lec 7 ABC 要处理的）。

控制律就是著名的 AIMD（加性增、乘性减）：

• 加性增（在没有丢包时探测更多带宽）：每收到一个 ACK，

  $$\text{cwnd}\leftarrow \text{cwnd}+\frac{1}{\text{cwnd}}$$

  一个 RTT 累计约增加 1 个 MSS。注意是线性爬升——比 slow start 温和得多，因为此时已接近容量，要小心试探。

• 乘性减（一旦丢包，果断退让）：

  $$\text{ssthresh}\leftarrow \frac{\text{cwnd}}{2},\text{cwnd}\leftarrow \frac{\text{cwnd}}{2}$$

ssthresh（慢启动阈值）记录"上次出事时的一半窗口"，用来划分两个阶段：cwnd < ssthresh 时用指数的 slow start 快速回到接近容量；cwnd ≥ ssthresh 时切换到线性的 congestion avoidance 小心探测。

---

6. 为什么偏偏是 AIMD？（相图论证——本讲的逻辑核心）

"加性增、乘性减"不是拍脑袋选的，而是能被严格论证的唯一合理线性控制律（形式化分析见 Chiu & Jain 1989，这里给出可视化的直觉）。

设两条流共享一条容量为 $C$ 的链路，状态记为 $(x_1,x_2)$，即两条流各自的发送速率。我们关心两件事：

• 效率（efficiency）：希望落在 $x_1+x_2=C$ 这条线上（既不浪费也不过载）；
• 公平（fairness）：希望落在 $x_1=x_2$ 这条线上（两条流分得一样多）。

理想的目标点是这两条线的交点。而网络给的反馈只有一个比特、且对两条流相同——"现在过载了 / 没过载"，它没法告诉某条流"你占多了"。在这种受限反馈下能否同时收敛到效率和公平？看几种线性控制律在状态平面上的轨迹：

 x2
  ▲           x1 = x2 (公平线)
  │          ╱
  │        ╱
  │      ╱ •  ← 加性增: 沿 (1,1) 方向走 45°
  │    ╱   ↗      (平行于公平线, 推向效率线)
  │  ╱   ↙        乘性减: 沿连向原点的射线缩回
  │╱___________     (移动方向更靠近公平线)
  │      ╲ x1+x2=C (效率线)
  └──────────────► x1

• 加性增：两条流各加相同的量，状态点沿 45° 方向（向量 $(1,1)$）移动。这个方向平行于公平线，所以推向效率的同时不改变两者的差距，但会越过效率线导致过载。
• 乘性减：两条流各按比例（例如减半）退让，状态点沿"连向原点的射线"缩回。沿这条射线移动会靠近公平线（因为按比例缩，差距的绝对值在变小）。

把两者交替执行，轨迹就会螺旋收敛到两条线的交点——既高效又公平。

对照其他组合就知道为什么必须是 AIMD：

• AIAD（加性增、加性减）：增和减都沿 $(1,1)$ 平移，永远停在某条平行于公平线的直线上，初始的不公平永远消不掉。
• MIMD（乘性增、乘性减）：增减都沿过原点的射线移动，比例不变，同样无法纠正不公平。

结论：只有"减"用乘性（推向公平）、"增"用加性（推向效率而不破坏已有公平），才能在单比特反馈下同时收敛。 这就是 AIMD 不可替代的根本原因。

至于减半因子 $1/2$：一旦丢包，说明已经至少打满了容量、还溢出了缓冲，保守的做法是退到容量以下；用乘性而非固定值，是因为"超出的量"大致与当前速率成比例，按比例退才稳定。

---

7. 被忽视的崩溃元凶：RTT 估计与超时

光有 AIMD 还不够。Jacobson 发现，1986 年崩溃的另一半原因藏在超时重传计时器（RTO）里——这部分常被读者跳过，但极其重要。

旧 TCP 这样估计 RTO：用指数加权移动平均（EWMA）平滑测得的 RTT 得到 SRTT，再令 $\text{RTO}=2\times \text{SRTT}$。问题在于这个固定系数 2：

当网络负载升高，RTT 的均值和方差会同时变大。负载重时，单次 RTT 经常远超均值的 2 倍。于是 RTO 太小 → 分组其实还在路上就被判超时 → 虚假重传 → 给已经拥塞的网络又添副本 → 加速崩溃。

Jacobson 的修正：不只估计均值，还要估计波动，让 RTO 随方差自适应地放宽。每收到一个 RTT 样本 $M$：

$$\begin{array}{rl}\text{Err}& =M-\text{SRTT}\\ \text{SRTT}& \leftarrow \text{SRTT}+g\cdot \text{Err},& g& =1/8\\ \text{RTTVAR}& \leftarrow \text{RTTVAR}+h\cdot (|\text{Err}|-\text{RTTVAR}),& h& =1/4\\ \text{RTO}& =\text{SRTT}+4\cdot \text{RTTVAR}\end{array}$$

几个工程上的精妙处：

• 用平均偏差（mean deviation） $|\text{Err}|$ 而不是标准差，是为了避免平方和开方——可以全用整数/定点运算在内核里高效实现。
• 系数 $g=1/8,h=1/4$ 都是 2 的幂，移位即可，无需乘法。
• $4\times \text{RTTVAR}$ 对常见分布约等于好几个标准差，足以覆盖 RTT 的长尾，从根上消除虚假超时。

---

8. 指数退避（exponential backoff）

如果重传后还是超时，怎么设下一次的 RTO？Jacobson 论证：在对网络一无所知的情况下，唯一被证明稳定的退避策略是指数退避——每次超时把 RTO 翻倍。直觉是：连续超时强烈暗示网络严重拥塞，此时必须以几何速度拉长重试间隔，给网络排空的时间，否则又会陷入正反馈。

9. 全貌：四个机制如何拼成一台状态机

把上面的部件组装起来，单条 TCP 连接的拥塞窗口随时间呈现经典的锯齿波（sawtooth）：

cwnd
 │            ╱|        ╱|        ╱|
 │          ╱  |      ╱  |      ╱  |   ← congestion avoidance: 线性加性增
 │        ╱    |    ╱    |    ╱    |
 │      ╱      ↓減半 ╱   ↓減半╱    ↓ 丢包→ ssthresh=cwnd/2
 │    ╱(slow start 指数段)
 │  ╱
 └─────────────────────────────────► 时间

控制流程：

1. 连接启动 → slow start（指数增），直到 cwnd 达到 ssthresh 或丢包；
2. cwnd ≥ ssthresh → 切到 congestion avoidance（线性加性增）探测带宽；
3. 检测到丢包（超时）→ ssthresh = cwnd/2，cwnd 重置后重新 slow start（这是最早的 Tahoe 版本）；
4. 全程由改进的 RTT/RTO 估计 与 指数退避 防止虚假重传。

（论文的这条思路稍后催生了 Reno 的快速重传 / 快速恢复：收到 3 个重复 ACK 就立即重传、并且不必把窗口砍回 1，从而避免每次丢包都退回慢启动——这是后续工作，但血脉同源。）

---

10. 一句话遗产，以及它通向哪里

这篇论文的伟大之处在于：完全不改路由器，只靠两端的几行控制逻辑，就让一个会崩溃的网络变得稳定、高效且公平——是端到端原则最有力的一次胜利。今天的 TCP（Reno、CUBIC、BBR 之前的一切）都建立在它定义的 cwnd/ssthresh/AIMD/RTO 框架上。

它的边界也正是后续讲次的起点：

• 丢包作为单比特、隐式信号，在高带宽时延积链路上反应太慢 → Lec 4 让路由器给出显式多比特反馈（XCP），或直接管理队列时延（PIE）。
• "丢包=拥塞"的假设在无线网失效 → Lec 7（ABC）。
• 它优化单条流的行为，但数据中心的 incast、超低时延场景需要新信号 → Lec 7（SWIFT）。

概念

TCP拥塞控制概念是为每个源确定网络中有多少可用能力，从而知道它可以安全完成传送的分组数。

一开始确定可获得的能力并不简单 因为其他连接时断时连，可获得的带宽不断在变。 TCP为每个连接维护一个状态变量，称为拥塞窗口（Congestion Window），与流量控制的通知窗口相对应，TCP要求，取这两者最小值。问题是如何得到一个适合的拥塞窗口值，通知窗口是连接的接受方送出的，这就要求发送方摸索，丢包就是出现拥塞的信号，发送如何调整，这就是拥塞算法应该做的事情。

NOTE

在无线网络中，丢包非常常见，认为丢包就是拥塞是非常错误的。

当源操作接近网络可达能力时，使用上加性增是正确的；但是如果在启动时候，还加性增就太慢了，因此，我们会用慢启动，指数性增加；为啥指数性增加还叫慢启动，放在情境下就明白了：当接受端告知可用窗口值65535，即使有大量带宽可用，但是也不会直接加以利用，而是指数增长的发包观察网络拥塞情况。

快速重传

当目前为止描述的机制只是将拥塞控制加到TCP的一部分，人们很快发现，TCP超时的粗粒度的实现方导致在等待一个计时器超时时，有很长时间连接无效。因此快速重传（fast retransmit）的新机制被加入其中，只是启发式机制，有时触发对丢失分组的重传比常规超时机制更快，但并不能代替，只是增强机制。

快速重传的思想简单明了，按原本意思，接收方拿到分组后会ACK，当分组没有按正常顺序达到时，接收方还是会把上次发过的确认消息再发一次，此时称为重复确认（duplicate ACK）。当发送方发送一个重复ACK时，它就知道接收方必定收到一个未按正常顺序到达的分组，表明它前面的分 能丢失。实际应用中， 发送方看到3次重复ACK，就重传分组。 劣势： 在连接刚开始或网络状况极差时，窗口很小，没有后续数据包去“暴露”这次丢包，就只能靠超时。解释一下： 假设 cwnd 很大，发送方一口气发送了包 [1, 2, 3, 4, 5, 6]，假设包2、3、4都丢了，只有包1、5、6到达

• 包1到达，接收方回复 ACK 2。
• 包5到达（失序），接收方回复 ACK 2（第1个重复ACK）
• 包6到达（失序），接收方回复 ACK 2（第2个重复ACK）
• 此时，发送方收到了3个ACK 2，触发了快速重传机制。但它只会重传它认为丢失的【第一个】包，即包2。
• 但包3和包4还是丢的！这个ACK 3对于发送方来说是一个新的ACK，它会清空重复ACK计数

快速恢复

最后，我们再做一个改进。 当快速重传机制发出拥塞信号时，不把拥塞窗口退回1个分组并启动慢启动，而是将其减半。

CUBIC

CUBIC是标准TCP算法的一个变体，也是Linux默认分发的拥塞控制算法。目标是支持大延迟 x 带宽积的网络， 有时也称为”長胖“（long-fat newtork）网络。这类网络在使用原始 TCP 算法时，会因为需要过多的往返时延（RTT）才能达到端到端路径的可用容量而表现不佳。CUBIC 通过更激进地增加拥塞窗口来解决这一问题，但关键是要在提升速度的同时，不对其他流量产生不良影响。

CUBIC 方法的一个重要方面是：在固定时间间隔内调整拥塞窗口，这个时间间隔基于自上一次拥塞事件（例如重复 ACK 到达）以来经过的时间，而不仅仅是 ACK 到达时调整（后者依赖 RTT）。这种方式使得 CUBIC 在与短 RTT 流竞争时表现得更加公平，因为短 RTT 流的 ACK 到达频率更高。

第二个重要方面是：使用三次函数（cubic function）来调整拥塞窗口。基本思想可以通过观察三次函数的一般形状来理解，其具有三个阶段：增长减慢、平缓平台、增长加快。图 6.14 给出了一个通用示例，并标注了额外信息：上一次拥塞事件发生前达到的最大拥塞窗口大小 $W_{\text{max}}$作为目标。

核心思路是：

1. 初期快速增长，
2. 接近 $W_{\text{max}}$时减缓增长，接近平台阶段时增长几乎为零，以保持谨慎，
3. 远离 $W_{\text{max}}$时再加快增长速度，此阶段本质上是在探测一个新的可达最大窗口 $W_{\text{max}}$​

具体来说，CUBIC 将拥塞窗口 CWND 计算为自上一次拥塞事件以来经过时间 t 的函数：

$CWND(t)=C\times (t-K)3+Wmax$

其中

$K=\sqrt[3]{\frac{W_{\text{max}}\times (1-\beta )}{C}}$​

这里 C 是一个缩放常数，$\beta$ 是乘法减小因子。CUBIC 将 $\beta$ 设置为 0.7，而标准 TCP 使用的是 0.5。可以看到 CUBIC 通常被描述为曲线从 凹形（concave）向凸形（convex） 转变，而标准 TCP 的加法增长函数仅为凸形

论文阅读： 拥塞避免与控制, 1988

摘要

1986年，互联网出现了严重的拥塞，一个例子是吞吐量从32Kbps到40bps。但作者发现问题不在TCP协议本身，而是TCP的实现方式，在拥塞时会导致完全错误的行为。提出一个核心思想——分组守恒（Packet Conservation）——对于一个稳定运行的TCP连接，只有当旧数据包离开网络后，新的数据包才能进入网络。 作者只有三种方式会破坏分组守恒：（接下来的章节中，作者将依次讨论这三种情况）

• 发送方一开始发得太快。网络还没建立稳定流动， 数据已经堆积。 解决方法：慢启动（Slow Start），不要一开始就大量发送，而是要逐步探测网络容量
• 旧包未离开，新包又进入。发送方发送速度超过网络处理能力， 会导致缓冲区溢出、丢包以及重传风暴。 解决方法： 动态拥塞窗口控制，根据网络反馈动态调节发送速率
• 路径资源不足。 网络本身容量不够。 解决方法： （无） 无论算法多好，也无法达到稳态。

为此，作者将7个算法添加到了 4BSD TCP中了：

1. RTT 方差估计
2. 指数退避（exponential retransmit timer backoff）
3. 慢启动
4. 更积极的接收端 ACK 策略
5. 拥塞情况下的动态窗口调整
6. Karn 的受限重传退避算法（clamped retransmit backoff）
7. 快速重传（fast retransmit）

慢启动

系统刚启动时最容易破坏这种分组守恒，原因是连接刚开始发送，或者丢包后重新恢复发送，此时发送方并不知道网络真正容量。 发送方利用 ACK 控制发送节奏，即收到 ACK 才发送新包，这是TCP协议的自时钟特性（Self-clocking），见图1。 而ACK的返回速度不会快于网络真正传输速度，因此，ACK到达节奏天然反映网络当前承载能力。 于是， 发送方只要收到ACK再发包，发送速率就会自动匹配，并且这个节拍由瓶颈链路决定。

自适应时钟的优点是自动适应带宽变化、时延变化，且动态范围很大。虽然稳定，但是很难启动，因为要发送新包就要ACK，要得到ACK就要发送数据，陷入“鸡生蛋”问题。作者提出 慢启动算法。 只需要维护一个新的状态变量，拥塞窗口（Congestion Window）。机制是连接启动或者丢包恢复后， cwnd = 1即只允许发送一个包，收到一个新的ACK后 cwnd += 1，发送窗口取min(rwnd, cwnd)，即取拥塞窗口和接收方通告窗口的最小值。