3.7 TCP Congestion Control
我们在 3.5 节 中介绍了 TCP 是如何提供可靠的数据传输的。TCP 的另一个关键功能是拥塞控制。由于 IP 层并不提供网络状况的反馈，TCP 必须使用端对端的拥塞控制方法。
TCP 的拥塞控制方法是根据网络拥塞的程度限制 Sender 发送速率。这个方法需要解决三个问题：
- Sender 如何限制发送速度
- Sender 如何感知到网络拥塞程度
- 如何根据拥塞程度确定发送速度上限
Sender 如何限制发送速度
我们在 3.5 节 引入了接收窗口(receive window, rwnd)，用于流量控制。为了限制发送速度，Sender 会额外维护一个拥塞窗口(congestion window, cwnd)。并且总是保证 inflight 的数据字节数不超过 min(rwnd, cwnd)：
LastByteSent - LastByteAcked <= min(rwnd, cwnd)
由于限制了 inflight 数据量，在 TCP 连接的每个 RTT （即收到第一个发送的字节的确认之前），我们最多只能发送 min(rwnd, cwnd) 个字节。发送速度大致等于 min(rwnd, cwnd) / RTT （单位 byte/sec）。因此通过调节 cwnd 大小可以调节发送速度。
Sender 如何感知到网络拥塞程度
网络拥塞时，路由器 buffer 可能溢出，导致丢包。这个丢包可能导致超时，也可能导致收到三次重复 ACK。总之，TCP Sender 决定重新发送这个包，并且认为网络出现了拥塞。
若丢包没有发生，Sender 将正常收到 ACK。Sender 会将此作为一切正常的信号，并根据 ACK 的速度增加拥塞窗口大小。
如何根据拥塞程度确定发送速度上限
- 丢包后 Sender 需要降低发送速度
丢包说明网络拥塞 - 收到新的 ACK 需要提高发送速度
正确 ACK 说明网络正常 - 带宽探测
Sender 会不断提高传输速度，直到出现拥塞，然后减少传输速度，过一段时间再尝试提高。
基于以上的原则，TCP 拥塞控制算法包括三个主要特点：
- 慢启动 (slow start)
- 拥塞避免 (congestion avoidance)
- 快恢复 (fast recovery)
Slow Start
当 TCP 连接开始发送数据时， cwnd 通常被初始化为 1 MSS (maximum segment size)。因此，刚开始的发送速率大概为 MSS/RTT。收到 ACK 后，Sender 增加 cwnd 至 2 倍。因此，TCP 发送速度开始很慢，但是以 指数增长。
TCP slow start
那么指数增长何时结束呢？当丢包出现时就会结束。此时我们设置 ssthresh = cwnd / 2 (slow start threshold)，然后再将 cwnd 重置为1，开始新一轮的指数增长，直到 cwnd = ssthresh。此后“慢启动”阶段结束，转入“拥塞避免”阶段。在这个阶段下，cwnd 的增长更加保守。
慢启动的一个作用就是确定 ssthresh 的初始值。
Congestion Avoidance
在拥塞避免阶段下，TCP 每一个 RTT 仅将 cwnd 增大一个 MSS。具体实现就是每当收到一个新的 ACK，就使 cwnd = cwnd + 1，即线性增长。
这个增长将持续到出现下一次重传发生。
如果这个重传是因为超时，则回到 slow start 状态，并设置：
ssthresh = cwnd / 2cwnd = 1
如果这个重传是因为 3 次重复 ACK 触发的快重传，说明连接依然可以正常传输数据，所以拥塞情况不如超时严重，处理时不需像超时的情况一样激进。我们只需要：
ssthresh = cwnd / 2cwnd = cwnd / 2 + 3
其中 3 是因为 3 次重复 ACK。然后，进入“快恢复”阶段。
Fast Recovery
快恢复状态由 3 次重复 ACK 触发，超时是不会进入快恢复状态的。
在快恢复状态时，每收到一个 ACK，cwnd = cwnd + 1。
快恢复并不是 TCP 强制要求的功能。在老版的 TCP (TCP Tahoe) 中，无论触发是超时还是重复 ACK，都会令 cwnd=1 并开始 slow start。而新版的 TCP (TCP Reno) 实现了快恢复。下面以一个例子说明这两者的区别。
假设初始 ssthresh=8，cwnd=1，当 cwnd=12 时出现了丢包，导致了 3 次重复 ACK。则两者的对比如下：
| transmission round | cwnd (Tahoe) | ssthresh (Tahoe) | cwnd (Reno) | ssthresh (Reno) | Comment |
|---|---|---|---|---|---|
| 1 | 1 | 8 | 1 | 8 | |
| 2 | 2 | 8 | 2 | 8 | |
| 3 | 4 | 8 | 4 | 8 | |
| 4 | 8 | 8 | 8 | 8 | |
| 5 | 9 | 8 | 9 | 8 | |
| 6 | 10 | 8 | 10 | 8 | |
| 7 | 11 | 8 | 11 | 8 | |
| 8 | 12 | 8 | 12 | 8 | 此上一样 |
| 9 | 1 | 6 | 9 | 6 | Tahoe 从 1 开始 |
| 10 | 2 | 6 | 10 | 6 | |
| 11 | 4 | 6 | 11 | 6 | |
| 12 | 6 | 6 | 12 | 6 | Tahoe cap 到ssthresh
|
| 13 | 7 | 6 | 13 | 6 | |
| 14 | 8 | 6 | 14 | 6 |
Evolution of TCP's congestion window
状态转换如下图：
FSM description of TCP congestion control
要点：
- 超时进入 slow start
- 三次以上重复 ACK 进入 fast recovery
问题：
- 为什么 Tahoe 的
cwnd在 12 时是 6 而不是 8？
推测计算公式是。
TCP Congestion Control: Retrospective
如果忽略第一次初始化时的慢启动，并且假设所有的丢包都是三次重复ACK。那么 TCP 拥塞控制可以分为两个部分：
-
cwnd每个 RTT 增加 1 MSS 的线性增长环节 - 一旦发现三次重复 ACK，
cwnd降低到之前的一半
这也叫做“加法增大，乘法减小” (additive-increase, multiplicative-decrease, AIMD) 算法，如下图所示。
Additive-increase, multiplicative-decrease congestion control
