TCP拥塞控制之基础

TCP 要点有四，一曰有连接，二曰可靠传输，三曰数据按照到达，四曰端到端流量控制。注意，TCP 被设计时只保证这四点，此时它虽然也有些问题，然而很简单，然而更大的问题很快呈现出来，使之不得不考虑和 IP 网络相关的东西，比如公平性，效率，因此增加了拥塞控制，这样 TCP 就成了现在这个样子。

为什么要进行拥塞控制

要回答这个问题，首先必须知道什么时候 TCP 会出现拥塞。TCP作为一个端到端的传输层协议，它并不关心连接双方在物理链路上会经过多少路由器交换机以及报文传输的路径和下一条，这是 IP 层该考虑的事。然而，在现实网络应用中，TCP连接的两端可能相隔千山万水，报文也需要由多个路由器交换机进行转发。交换设备的性能不是无限的!, 当多个入接口的报文都要从相同的出接口转发时，如果出接口转发速率达到极限，报文就会开始在交换设备的入接口缓存队列堆积。但这个队列长度也是有限的 ，当队列塞满后，后续输入的报文就只能被丢弃掉了。对于TCP 的发送端来说，看到的就是发送超时丢包了。

网络资源是各个连接共享的，为了大家都能完成数据传输。所以，TCP需要当它感知到传输发生拥塞时，需要 降低自己的发送速率，等待拥塞解除。

如何进行拥塞控制

拥塞窗口 cwnd

首先需要明确的是，TCP是在 发送端 进行拥塞控制的。TCP 为每条连接准备了一个记录拥塞窗口大小的变量 cwnd1，它限制了本端TCP 可以发送到网络中的最大报文数量 ²。显然，这个值越大，连接的吞吐量越高，但也更容易导致网络拥塞。所以，TCP 的拥塞控制本质上就是根据丢包情况调整cwnd，使得传输的吞吐率尽可能地大！而不同的拥塞控制算法就是调整cwnd 的方式不同！

注 ¹: 本文中的cwnd 以发送端的最大报文段长度 SMSS 为单位的
注²: 这个数量也受对端通告的窗口大小限制

Linux 用户可以使用 ss –tcp –info 查看链接的 cwnd 值

拥塞控制算法

TCP 从诞生至今，已经有了多种的拥塞控制算法，直到现在还有新的在被提出！其中 TCP Tahoe(1988) 和TCP Reno(1990)是最初的两个算法。虽然看上去年代很就远了，但 Reno算法直到现在还在广泛地使用。

• Tahoe 提出了 1）慢启动，2）拥塞避免，3）快速重传
• Reno 在 Tahoe 的基础上增加了 4）快速恢复

Tahoe算法的基本思想是

• 首选设置一个符合情理的初始窗口值
• 当没有出现丢包时，慢慢地增加窗口大小，逐渐逼近吞吐量的上界
• 当出现丢包时，快速地减小窗口大小，等待阻塞消除

Tahoe 拥塞避免 (congestion-avoidance)

当我们在理解拥塞控制算法时，可以假想发送端是一下子将整个拥塞窗口大小的报文发送出去，然后等待回应。

Tahoe采用的是加性增乘性减 (Additive Increase, Multiplicative Decrease, AIMD) 方式来完成缓慢增加和快速减小拥塞窗口：

发送端发送 整窗 的数据：

• 如果没有丢包，则 cwnd = cwnd + 1
• 如果出现丢包了，则 cwnd = cwnd / 2

为什么丢包后是除以 2 呢, 这里的 2 实际上是一个折中值！用下面的例子来解释！

物理传输路径都会有延时，这个延时也让传输链路有了传输容量 (transit capacity) 这样一个概念，同时我们把交换设备的队列缓存称为队列容量(queue capacity). 比如下面这样一个连接，传输容量是M, 队列容量是N.

当 cwnd 小于 M 时，不会使用 R 的队列，此时不会有拥塞发生；当 cwnd 继续增大时，开始使用 R 的队列，此时实际上已经有阻塞了！但是 A 感知不到，因为没有丢包！当 cwnd 继续增大到 M + N 时，如果再增大 cwnd，就会出现丢包。此时拥塞控制算法需要减小cwnd，那么减小到多少合适呢？当然是减少到不使用R 的缓存，或者说使得cwnd = M，这样可以快速解除阻塞。

这是理想的情况！实际情况是 A 并不知道 M 和N有多大 (或者说有什么关系)，它只知道当cwnd 超过 M + N 时会出丢包！于是我们折中地假定 M = N，所以当cwnd = 2N 时是丢包的临界点，为了解除阻塞，让 cwnd = cwnd / 2 = N 就可以解除阻塞³！

所以，cwnd的变化趋势就像上面这样，图中上方的红色曲线表示出现丢包。这样的 稳定状态 也称为 拥塞避免阶段(congestion-avoidance phase)

现实算法实现中 ，拥塞避免阶段的cwnd 是在收到每个 ACK 时更新的：cwnd += 1/cwnd，如果认真算，会发现这比整窗更新 cwnd += 1 要稍微少一点！

注 ³：后面会提到，Tahoe 在此时会将 cwnd 先设置为1，然后再迅速恢复到cwnd / 2

Tahoe 慢启动 (Slow Start)

Tahoe需要为选定一个 cwnd 初始值，但是发送端并不知道多大的 cwnd 才合适。所以只能从 1 开始 ⁴，如果这个时候就开始加性增，那就太慢了，比如假设一个连接会发送5050 个MSS大小的报文，按照加性增加，需要 100 个RTT才能传输完成 (1+2+3+…+100=5050)。因此，Tahoe 和Reno使用一种称为慢启动的算法迅速提高 cwnd。也就是只要没有丢包，每发送一个整窗的数据，cwnd = 2 X cwnd。换句话说，在 慢启动阶段 (slow-start phase)，当发送端每收到一个ACK 时，就让cwnd = cwnd + 1

注 ⁴RFC 2581 已经允许cwnd 的初始值最大为 2, RFC 3390 已经允许cwnd 的初始值最大为 4, RFC 6928 已经允许cwnd 的初始值最大为10

那么，慢启动阶段何时停止？或者说什么时候进入前面的拥塞避免阶段 ? Tahoe算法定义了一个 慢启动阈值 (slow-start threshold) 变量，在 cwnd < ssthresh 时，TCP处于慢启动阶段，在 cwnd > ssthresh 后，TCP处于拥塞避免阶段。

ssthreshold的初始值一个非常大的值。连接建立后 cwnd 以指数增加，直到出现丢包后，慢启动阈值将被设置为 cwnd / 2。同时 cwnd 被设置为1, 重新开始慢启动过程。这个过程如下图所示, 可以看到，慢启动可是一点也不慢。

Tahoe 快速重传 (Fast Retransmit)

现实的网络网络环境拓扑可能十分复杂，即使是同一个 TCP 连接的报文，也有可能由于诸如等价路由等因素被路由器转发到不同的路径，于是，在接收端就可能出现报文的乱序到达，甚至丢包！举个例子，发送端发送了数据 DATA[1]、DATA[2]、……、DATA[8]，但由于某些因素，DATA[2] 在传输过程中被丢了，接收端只收到另外 7 个报文，它会连续回复多次 ACK[1](请求发送端发送 DATA[2])。这个时候，发送端还需要等待 DATA[2] 的回复超时 (2 个RTT) 吗？

快速重传的策略是，不等了！挡发送端收到第 3 个重复的 ACK[1] 时(也就是第 4 个ACK[1])，它要马上重传DATA[2], 然后进入慢启动阶段，设置ssthresh = cwnd / 2 , cwnd = 1.

如上图所示，其中 cwnd 的初始值为 8，当发送端收到第3 个重复的 ACK[1] 时，迅速进入慢启动阶段，之后当再收到 ACK[1] 时，由于 cwnd = 1 只有1，因此并不会发送新的报文

Reno 快速恢复(Fast Recovery)

在快速重传中，当出现报文乱序丢包后，拥塞窗口 cwnd 变为 1，由于该限制，在丢失的数据包被应答之前，没有办法发送新的数据包。这样大大降低了网络的吞吐量。针对这个问题，TCP Reno 在TCP Tahoe的基础上增加了快速恢复(Fast Recovery)。

快速恢复的策略是当收到第 3 个重复的 ACK 后，快速重传丢失的包，然后

• 设置 sshthresh = cwnd / 2
• 设置 cwnd = cwnd /2

还是以上面的例子为例

与快速重传中不同的是，发送端在收到第 3 个重复的 ACK 后，cwnd变为 5，EFS 设置为7

这里 EFS 表示发送端认为的正在向对端发送的包 (Estimated FlightSize)，或者说正在链路上(in flight) 的包。一般情况下，EFS是与 cwnd 相等的。但在快速恢复的时候，就不同了。假设拥塞避免阶段时 cwnd = EFS = N，在启动快速恢复时，收到了3 个重复的 ACK，注意，这3 个ACK是不会占用网络资源的 (因为它们已经被对端收到了)，所以EFS = N - 3, 而既然是出发了快速恢复，那么一定是有一个包没有到达，所以EFS = N - 4，然后，本端会快速重传一个报文，EFS = N - 3，这就是上面EFS 设置为 7 的来源。

其他部分没什么好说的，发送端会在 EFS < cwnd 时发送信的数据，而同时，这又会使得EFS = cwnd

TCP New Reno

根据 Reno 的描述，TCP发送端会在收到 3 个重复的 ACK 时进行快速重传和快速恢复，但还有有一个问题，重复的 ACK 背后可能不仅仅是一个包丢了！如果是多个包丢了，即使发送端快速重传了丢失的第一个包，进入快速恢复，那么后面也会收到接收端发出的多个请求其他丢失的包的重复 ACK！这个时候？发送端需要再累计到3 个重复的 ACK 才能重传！

问题出在哪里？发送端不能重收到的重复 ACK 中获得更多的丢包信息！它只知道第一个被丢弃的报文，后面还有多少被丢弃了？完全不知道！也许使用 SACK(参考 RFC6675) 这就不是问题，但这需要两端都支持 SACK。对于不支持SACK 的场景，TCP需要更灵活！

RFC6582 中描述的 New Reno 算法，在 Reno 中的基础上，引入了一个新的变量 recover, 当进入快速恢复状态时(收到3 个重复的 ACK[a])，将recover 设置为已经发送的最后的报文的序号。如果之后收到的新的 ACK[b] 序号 b 不超过 recover，就说明这还是一个丢包引起的ACK！这种ACK 在标准中也称之为 部分应答(partial acknowledgments), 这时发送端就不等了，立即重传丢失的报文。

还有后文！

Ref List

Intronetworks
CoolShell
dog250