网络数据包如果一次发送太多，就会造成网络拥堵；如果发送太少，就浪费了带宽，延长了通信时间。TCP 协议有一个拥堵窗口机制，负责动态调整每次发送数据包的数量。本文通俗地解释了这种算法的细节。
本文翻译自 Intro to Congestion Control
这个夏天，我一直在思考更好地解决网络拥塞问题的方法。在这篇文章中，我将会讨论为什么网络拥塞问题会出现，以及一些传统的解决办法。如果你有更深厚的兴趣，这个 Juptier notebook 包含了我用来获取相应结果的代码，以及对这些结果的分析。
1 什么是 TCP
在我们开始正文讨论之前，我来先简要介绍一些信息在网络上流通的细节。
TCP协议被用来将信息从一台电脑经过英特网传输给另一台电脑。这个协议也是这篇文章所关注的协议。把 TCP 协议同其他协议（如 UDP）区分开来的特征是，TCP 确保了 100%的传输成功率。也就是说如果你从一台电脑上发送了 100kb 的数据，那么你会在接收端准确地收到这 100kb 的数据。
TCP 的这个特性非常强大，而这一特性也是很多网络应用采用 TCP 协议的原因。现有的 Web 应用和 Email 都是构筑于 TCP 协议之上。
TCP 实现所有数据的可靠传输的核心原理是，对于从 A 端发送到 B 端的数据，B 端会发送回一个 ACK(Acknowlegement)信息给 A 端来告知自己收到了对应的信息。
另外还值得注意的是，TCP 工作在 IP 协议之上，IP 协议最多允许在一个包中包含 1500 个字节的数据，因此要发送 100kb 的数据，需要拆分成多个分段。根据 TCP 协议，每个分段都会收到对应的 ACK。
如果发送者没有收到一个数据分段的 ACK，其会重新发送这个分段。
2 什么时候会还产生拥塞
拥塞（Congestion）问题是由于网络传输延时导致的。信息传输速率会收到物理信道，如以太网线，蜂窝网络等，的制约。在因特网中，大部分独立设备都连接到这些信道上。
下图是一个典型场景：
在上面的示意图中，两个发送者要各自要传输 1GB 的数据。然而这两个发送者最终接入到了一个 1GB 的链接中。第二个链接的传输能力无法匹配上前两个链接的输入，故而不得不丢弃一部分数据包。如果发送者不主动调整自己的发送速度，那么会产生非常坏的情况。在 TCP 协议中，如果发送者发现一个数据分段没有送达，会重新发送这个数据包。那么拥塞情况会持续，两个发送者会无法完成发送过程。
为了让两个发送者能够成功传输各自的数据，他们需要共同减少发送数据的速率。如果只有一个发送者减少了发送的数据，而另一个仍然维持 1GB 的发送量，那么仍然会产生拥塞。在因特网的架构中，不会有一个中央控制系统来协调两者的发送速率。
3 迂回：什么是链接(link)
在我们深入到这个问题的解决方案前，我还想进一步讨论链接（link）的属性。关于网络链接，有下面三个重要的细节问题你需要知道：
- 延时（毫秒）：一个包从链接的一端发送到另一端需要的时间
- 带宽（mb/s）：链接每秒能够通过的比特数
- 队列：在链接正在工作时，等候发送包的队列的长度，以及在队列满时管理队列的策略
如果把链接比喻成水管，那么延时可以理解为管道的长度，带宽就是水管的周长。
关于链接还有一个重要的统计参数时带宽延时积（bandwidth-delay product, BDP）。这个参数表现了体现了停留在链接中的数据量，可以理解为管道本身的容量。当链接中传输的数据量达到了 BDP 时，就可以说链接被充分利用了。如果发送端尝试发送比 BDP 更多的数据，那么链接的队列将会填满，并最终开始丢包。
4 方法
在给出方法之前，我们要思考一个问题：发送者如何知道产生了拥塞呢？如同我们之前提到的，因特网是一个分布式的系统，故而并没有一个位于中央的协调者来在下游链接产生拥塞的时候提醒发送者要减慢发送速度。
主要有两个指标：丢包率和传输往返时间。在拥塞发生时，链接的队列逐渐填满，开始发生丢包。如果一个发送者注意到了丢包现象，这就很可能意味着发生了丢包。另一个队列满负荷的现象是数据包在队列中等待的时间增加了，这会导致传输往返时间，即发送包到收到 ACK 的时间增加。
今天的一些拥塞控制机制考虑了上面两个指标，不过在一些比较早期的设计中，只使用到了丢包率这一个指标。
还需要注意的是，发送者可能并不提前知道传输链接的特性参数。例如，如果你访问"http://www.google.com"，那么你发送的数据包可能要经过很多不同性质的链接才能到达 Google 的服务器，而你的传输速率是收到其中最慢的链接的制约的。
因此，出了规避网络拥塞的能力，拥塞控制机制还需要能够探索可用带宽的具体大小。
5 拥塞窗口（Congestion Window）
理解任何拥塞控制机制的关键在于理解拥塞窗口的概念。拥塞窗口指的是在收到一个 ACK 前发送者能发送的包的数量。如果一个发送者的拥塞窗口被设置为 2，这意味着在发送了两个包之后，它必须等到接收端回复的 ACK 之后才能继续发送。
拥塞窗口越大，发送者就能在相通的时间间隔内向接收端发送更多的数据包。为了更加直观的理解，假设网络传输的延时是 88ms，拥塞窗口设置为 10，那么在一轮往返传输（88 * 2 = 176ms）时间内可以发送 10 个数据包。而如果拥塞窗口设置为 20，则相同的时间间隔内可以发送 20 个数据包。
不过当然，提升拥塞窗口的大小，也会提高发生拥塞的概率。拥塞控制算法的目标，就是计算出合适的拥塞窗口大小。
从理论角度来看，拥塞窗口的大小应当就是链接的 BDP。
6 TCP Tahoe
TCP Tahoe 是在 80 年代设计出来的拥塞控制算法。那是拥塞问题才刚刚在因特网上出现。算法本身非常简单。增加拥塞窗口分为两个阶段：
第一阶段： Slow Start：算法的开始状态是 Slow Start。在这个阶段拥塞窗口在每收到一个 ACK 就增加 1。这种机制有效地在每轮往返传输成功后，将拥塞窗口的大小翻倍。如果拥塞窗口的大小是 4，那么在同时会有 4 个包在传输路途中。当每个包的 ACK 返回时，拥塞窗口加一，即当这四个包的 ACK 都收到后，拥塞窗口会翻倍成为 8。这个过程会一直持续到拥塞窗口达到阈值，ssthresh。
第二阶段：Congestion Avoidance：当拥塞窗口达到阈值ssthresh时，进入 Congestion Avoidance 阶段。在这一阶段，每轮往返传输后拥塞窗口加一。也就是说，在上面的例子中，当所有 4 个包的 ACK 收到后，拥塞窗口只会加 1. 在这个阶段拥塞窗口的大小会大大减小。
当 Tahoe 检测到丢包后，会把ssthresh设置为当前拥塞窗口的一半，然后将拥塞窗口设置为 1，算法重新回到 Slow Start 阶段。
6.1 丢包检测与快速重传
TCP 发送端有两种方法来检测丢包现象：
- 发送端超时。发送端会给每个发送出去的数据包设置一个超时。如果在超时时限达到时尚未收到该包的 ACK，则认为发生丢包，并重传改数据包，将拥塞窗口设置为 1.
- 接受者发送回重复的 ACK。在 TCP 中，接收端只会接收按照顺序发送的包。如果收到了不合顺序的包，接收端会返回他收到的最后一个符合顺序的包的 ACK。例如，接收端收到了 1，2，3，其后又收到了包 5，那么接收端会再次回复 3 的 ACK。在 Tahoe 中，如果发送端检测到重复的 ACK，就意味着发生了丢包。这种机制被称为快速重传(Fast Retransmit)，因为这种机制不一定要等待到传输超时。
6.2 一些思考
在开头提到的Jupitor Notebook中，我实现了 Tahoe，下图是拥塞窗口随着时间变化的曲线：
注意到上图的中变化曲线存在锯齿形的行为。开始的突增为 Slow-Start 阶段，后面的平缓部分为 Congestion Avoidance 阶段。急遽掉落到 1 则是由于丢包导致的。
6.3 为什么 Tahoe 要如此工作
Tahoe 在工作过程中不断增加拥塞门限的原因是因为网络条件会随着时间不断变化。例如如果另一个发送者开始在同一个信道上发送数据，这会导致可用带宽的降低，其他的发送者需要按照实际情况调整。相反，如果有一个发送者停止发送数据了，可用带宽会增加，这也需要其他发送者根据实际情况来调整。
这种方法其实还是存在很多问题，这也是 Tahoe 目前已经基本没人使用了。特别的，Tahoe 需要很长的时间，尤其是在高带宽网络上，才能全面有效地利用可用带宽。这是因为在拥塞窗口增长到 Slow Start 门限以后，其增长就变得非常缓慢了。
另外一个问题是，发生丢包并不一定意味着网络发生了拥塞，例如 Wifi 信道下，本身信道就是可能发送丢失的。对于丢包产生剧烈的将拥塞窗口砍到 1 并不总是合适的做法。
最后一个问题是，Tahoe 使用丢包这个因子来作为判断是否发生丢包的依据。然而由于拥塞发生了丢包，此时调整拥塞窗口已经太晚了。
7 其他的方法
80 年代以后，涌现了不少新的算法来解决上面这些问题。我会在将来的文章中详细讨论这些方法：
CUBIC：这个算法在 2005 年实现，目前是 Linux 系统的默认拥塞控制算法。如同 Tahoe，这个 CUBIC 也是用丢包作为判断拥塞是否发生的依据。不同的是，CUBIC 在高带宽网络下的性能要远高于 Tahoe。不同于 Tahoe 在每一轮往返传输后将拥塞窗口增加 1 的做法，CUBIC 如同其名，使用一个立方函数来确定窗口大小，从而实现拥塞窗口的快速增长。
BBR(Bufferbloat)：这是最近才被 Google 提出的新的算法。不同于 CUBIC 和 Tahoe，这个算法使用延时来作为判断拥塞是否发生的标识。这背后的思路是延时是拥塞在导致丢包前就能起作用的判断因子。在实际丢包发生前就开始减少发送速率能够带来更高的吞吐率。
8 公平性
在研究拥塞控制算法时，一个有意思的问题是考虑不同的算法对于同一网络链接上的各个发送者是否公平。如果一个算法在发生拥塞时，没有缩减发送规模，而是按照之前相同的速率继续发送，那么这个算法就是不公平的。在这个结果中，如果同一个链接上 有一个发送者没有采用拥塞窗口控制，而另一个发送者使用 Tahoe。从结果可以看到，在一分钟的时间内，Tahoe 发送者几乎没法发送任何数据，因为它没有机会增加它的拥塞窗口。而固定窗口的发送者全占了发送信道。
尽管固定窗口发送者是一个不好的情形，这种算法可能具有对其他的算法的不公平地位，从而占据更多带宽。由于缺乏中央控制这，可能有贪婪的发送者蓄意采用固定窗口来谋取更大的带宽。这就是需要从博弈论的角度来研究拥塞控制算法了。
9 结论
拥塞控制算法是互联网的基础，同时也是在有限信息条件下进行分布式决策的一种迷人的实践。