网络传输问题本质上是对网络资源的共享和复用问题，因此拥塞控制是网络工程领域的核心问题之一，并且随着互联网和数据中心流量的爆炸式增长，相关算法和机制出现了很多创新，本系列是免费电子书《TCP Congestion Control: A Systems Approach》的中文版，完整介绍了拥塞控制的概念、原理、算法和实现方式。原文: TCP Congestion Control: A Systems Approach
第 4 章 控制算法(Control-Based Algorithms)
本章将介绍目前占主导地位的网络拥塞控制算法。Van Jacobson 和 Mike Karels 在 1988 年提出了这种方法，并进行了持续多年的改进。目前广泛使用的是被称为 CUBIC 的变体，稍后将详细介绍。
控制算法的总体思路相当简单，简单来说就是基于当前估计的可用带宽传输一组数据包，然后 TCP 发送方对两组网络信号作出反应。首先是 ACK，收到 ACK 表明一个包已经离开网络，可以安全的传输一个新包，而不会增加拥塞程度。通过 ACK 控制数据包的传输节奏，被称为自时钟(self-clocking) 。其次，超时意味着数据包丢失，从而意味着发生了网络拥塞，因此需要降低 TCP 的发送速率。因为通过丢包作为信号，意味着拥塞已经发生，而我们是在事后才做出反应，所以将这种方法称为基于控制(control-based) 的方法。
作为实际使用的拥塞控制方法，还有需要解决许多微妙的问题，本章将介绍处理这些问题的技术，因此也可以作为识别和解决一系列问题的经验的案例研究。在接下来的章节中，我们将在介绍每种技术时追溯其历史背景。
4.1 超时计算
超时和重传是 TCP 实现可靠字节流的核心方法，但超时在拥塞控制中也扮演着关键角色，因为可以表示丢包，而丢包又表明拥塞的可能性。换句话说，TCP 超时机制是其整体拥塞控制方法的构建块。
请注意，发生超时时，可能是因为丢了一个包，或者丢了相应的 ACK，或者什么都没丢，但是 ACK 到达时间比预期要长。因此，重要的一点是要知道 ACK 到达需要多长时间，否则就有可能在没有发生拥塞的时候做出发生拥塞一样的响应。
TCP 有一种根据测量的 RTT 进行计算的自适应方法来设置超时。虽然听起来很简单，但完整实现比想象的要复杂得多，并且多年来经过了多次改进，本节将回顾这一经验。
4.1.1 初始算法
我们从 TCP 规范中描述的简单算法开始，其思想是保存 RTT 的平均值，然后用 RTT 的函数计算超时。具体来说，TCP 每发送一个分片，就会记录时间，当该分片的 ACK 到达时，再次读取时间，然后将这两次时间的差值作为SampleRTT，然后计算EstimatedRTT，作为前一个估计和新样本之间的加权平均值。也就是说,
EstimatedRTT=α×EstimatedRTT+(1−α)×SampleRTT
参数α是为了平滑EstimatedRTT。小的α值可以感受到 RTT 的微小变化，但可能会容易受到暂时波动的影响。另一方面，大的α值更稳定，但可能不够快，无法适应真正的变化。TCP 初始规范建议在 0.8 到 0.9 之间取值，然后基于EstimatedRTT以一种相当保守的方式计算超时:
TimeOut=2×EstimatedRTT
4.1.2 Karn/Partridge 算法
几年后，在这种简单方法中发现了一个相当明显的缺陷: ACK 实际上并不响应传输，而是响应对数据的接收。换句话说，当重传了某个分片，然后收到一个 ACK，发送端在测量样本 RTT 时，无法确定这个 ACK 应该与第一次还是第二次传输的分片匹配。
为了计算出准确的SampleRTT，必须知道 ACK 与哪次传输相关联。如图 21 所示，如果假设 ACK 匹配初始传输，但实际上应该匹配第二次传输，那么SampleRTT就太大了(a)；如果假设 ACK 匹配第二次传输，但实际上是匹配第一次传输，那么SampleRTT就太小了(b)。
图 21. 将 ACK 与(a)原始传输和(b)重传联系起来。
解决方案以其发明者的名字命名，被称为 Karn/Partridge 算法，乍一看出奇的简单。在这种算法中，每当 TCP 重传一个分片，就停止采集 RTT 样本，即只对只发送过一次的分片测量SampleRTT。但该算法还包括对 TCP 超时机制的第二个更改。每次 TCP 重传时，将下一个超时设置为上一次超时的两倍，而不是基于上一次EstimatedRTT，即 Karn 和 Partridge 提出超时计算采用指数后退方法。使用指数后退的动机是，超时会导致重传，而重传分片不再有助于更新 RTT 估算。因此，在宣布丢包时要更加谨慎，而不是进入一个可能的快速超时然后重传的周期。在后面的章节中，我们将再次在一个更复杂的机制中看到指数后退的概念。
4.1.3 Jacobson/Karels 算法
Karn/Partridge 算法是对 RTT 估算的一种改进，但并没有解决拥塞问题。Jacobson 和 Karels 在 1988 年提出的拥塞控制机制(以及其他几个组件)定义了一种决定何时超时以及重传的新方法。
原始算法的主要问题是没有考虑样本 RTT 的方差。直观的说，如果样本之间的变化很小，那么EstimatedRTT更值得信任，没有理由将这个估计值乘以 2 来计算超时。另一方面，样本的方差较大就表明超时值不应该与EstimatedRTT耦合得太紧密。
在新方法中，发送方像以前一样测量新的SampleRTT，然后将新采样加入超时计算中，如下所示:
Difference=SampleRTT−EstimatedRTT
EstimatedRTT=EstimatedRTT+(δ×Difference)
Deviation=Deviation+δ(∣Difference∣−Deviation)
δ在 0 到 1 之间取值，即，计算 RTT 及其变化的移动加权平均值，然后以EstimatedRTT和Deviation的函数计算超时，如下所示:
TimeOut=μ×EstimatedRTT+ϕ×Deviation
根据经验值，μ一般设为 1，ϕ 一般设为 4。因此，当方差很小时，TimeOut接近EstimatedRTT，较大的方差会导致Deviation主导计算。
4.1.4 实现
关于 TCP 中超时的实现，有两点需要注意。首先，不使用浮点运算就可以实现EstimatedRTT和Deviation的计算。相反，整个计算被扩展为 2n，δ被设为 1/2n，从而允许我们进行整数运算，通过移位实现乘除法，获得更高的性能。计算结果由下面的代码片段给出，其中 n=3(即δ=1/8)。注意，EstimatedRTT和Deviation以扩展形式存储，而代码开头的SampleRTT值以及末尾的TimeOut值都是真正的、未扩展的值。如果发现代码难以理解，可能需要尝试将一些实数代入其中，并验证给出的结果是否与上面的方程相同。
{ SampleRTT -= (EstimatedRTT >> 3); EstimatedRTT += SampleRTT; if (SampleRTT < 0) SampleRTT = -SampleRTT; SampleRTT -= (Deviation >> 3); Deviation += SampleRTT; TimeOut = (EstimatedRTT >> 3) + (Deviation >> 1); }
其次，该算法精度和读取当前时间的算法一样。在典型 Unix 实现中，时钟精度高达 500 毫秒，比 100 到 200 毫秒的平均跨国 RTT 要大得多。更糟的是，TCP 的 Unix 实现只在这个 500 毫秒的时钟间隙检查是否发生超时，并且只对每个 RTT 进行一次往返时间采样。这两个因素的结合可能意味着在传输分片 1 秒后才会发生超时。下一节将介绍使 RTT 计算更加精确的 TCP 扩展。
关于 TCP 超时实现的更多细节，我们向读者推荐权威的 RFC:
延伸阅读:
RFC 6298: Computing TCP’s Retransmission Timer. June 2011.
4.1.5 TCP 时间戳扩展
到目前为止所介绍的对 TCP 的更改只是对发送方计算超时的方式进行了调整，协议本身并没有更改。不过，也有一些对 TCP 报头的扩展，可以帮助改进管理超时和重传的能力。我们在这里讨论的扩展与 RTT 估算有关，在 2.3 节中介绍过另一个为AdvertisedWindow建立比例因子的扩展，接下来还将介绍第三种扩展，用于发送可选 ACK 或 SACK。
TCP 时间戳扩展有助于改进 TCP 超时机制。与粗粒度事件测量 RTT 不同，TCP 可以在即将发送一个分片时读取实际的系统时钟，并将这个时间(可以将其看作一个 32 位时间戳)放入分片头部。然后，接收方将这个时间戳在其确认中回传给发送方，发送方用当前时间减去这个时间戳来测量 RTT。本质上，时间戳选项为 TCP 提供了一个方便的地方来存储一个分片何时被传输的记录。注意，连接中的端点不需要同步时钟，因为时间戳是在连接的同一端写入和读取的。这改进了 RTT 的测量，从而降低了由于较差的 RTT 估算而导致不正确超时的风险。
时间戳扩展还有第二个用途，即提供了一种创建 64 位序列号字段的方法，解决了 2.3 节中介绍的 32 位序列号的缺点。具体来说，TCP 根据 64 位逻辑标识符(SequenceNum字段为低 32 位，时间戳为高 32 位)来决定是否接受或拒绝一个分片。由于时间戳总是增加的，因此可以用来区分相同序列号的两个不同版本。请注意，在此设置中使用时间戳只是为了防止重复，不作为序列号的一部分用于排序或确认数据。
4.2 线性增加/指数减少(Additive Increase/Multiplicative Decrease)
更好超时计算方法是必要的构建模块，但不是拥塞控制的核心。拥塞控制最主要的挑战是计算出发送者可以安全的传输多少流量。为此，TCP 为每个连接维护一个新的状态变量，称之为CongestionWindow(但在文献中通常被称为cwnd，这是基于代码中使用的变量名)，发送端通过它来限制在给定时间内允许传输的数据量。
拥塞窗口是拥塞控制机制的流控通告窗口。TCP 发送端未确认的最大字节数是拥塞窗口和通告窗口的最小值。因此，使用第 2 章定义的变量，TCP 的有效窗口修改如下:
MaxWindow=MIN(CongestionWindow,AdvertisedWindow)
EffectiveWindow=MaxWindow−(LastByteSent−LastByteAcked)
也就是说，在计算EffectiveWindow时，MaxWindow取代了AdvertisedWindow。因此，TCP 发送端的发送速度不允许超过最慢的组件(网络或目标主机)所能适应的速度。
当然，问题是 TCP 如何为CongestionWindow学习一个合适的值。不像AdvertisedWindow是由连接的接收端发送的，没有人给 TCP 发送端发送一个合适的CongestionWindow。答案是 TCP 发送端根据感知到的网络中存在的拥塞级别来设置CongestionWindow，这意味着到当拥塞水平上升时减小拥塞窗口，当拥塞水平下降时增加拥塞窗口。综合起来，基于其所采用的方法，该机制通常被称为线性增加/指数减少(AIMD, additive increase/multiplicative decrease) 。
那么关键问题就变成了: 发送端如何确定网络是拥塞的，以及应该怎样减小拥塞窗口？根据观察，报文无法递送以及超时的主要原因是由于拥塞而丢包，数据包在传输过程中由于错误而被丢弃的情况非常罕见，因此 TCP 将超时解释为拥塞的标志，并降低传输速率。具体来说，每次发生超时时，发送端将CongestionWindow设置为以前值的一半。对于每个超时，将拥塞窗口减半对应于 AIMD 的"指数减少"部分。
虽然CongestionWindow以字节为单位，但如果我们从整个包的角度来考虑，它是最容易理解指数减少的。例如，假设CongestionWindow当前设置为 16 个包，如果检测到丢包，CongestionWindow被设置为 8。(通常，当超时发生时，会检测到丢包，但正如下面所看到的，TCP 有另一种机制来检测丢包。) 额外的丢包导致拥塞窗口减少到 4 个，然后是 2 个，最后是 1 个包。CongestionWindow不允许小于一个包的大小，在第 2 章我们知道这是MSS。
图 22. 在增加过程中传输的数据包线性增加，每 RTT 增加一个数据包。
只减少窗口大小的拥塞控制策略显然过于保守，我们还需要能够增加拥塞窗口，以利用网络中新近可用的容量。这是 AIMD 的"线性增加"部分。其工作原理如下，每次发送端成功发送一个CongestionWindow值的包时，也就是说，在上一个往返时间(RTT)发送出去的每个包都被 ACK 了，就会给CongestionWindow增加相当于一个包的值，这种线性增长如图 22 所示。
实践中，TCP 不会等到收到整个窗口的 ACK 值才给拥塞窗口增加一个包，而是每收到一个 ACK 就增加一点拥塞窗口。具体来说，每次 ACK 到达时，拥塞窗口按如下方式递增:
Increment=MSS×(MSS/CongestionWindow)
CongestionWindow=CongestionWindow+Increment
也就是说，不是在每个 RTT 中给CongestionWindow增加整个MSS字节，而是在每次接收到 ACK 时增加MSS的一小部分。假设每个 ACK 都响应收到了MSS字节，那么这个部分就是MSS/CongestionWindow。
图 23. 典型的 TCP 锯齿模式。
这种不断增加和减少拥塞窗口的模式在连接的整个生命周期中持续存在。事实上，如果我们将CongestionWindow的当前值作为时间的函数绘制出来，会得到一个如图 23 所示的锯齿状图形。关于 AIMD 需要理解的重要概念是，发送端愿意以比增加拥塞窗口更快的速度减少拥塞窗口。我们可以想象另一种增加/减少策略，在 ACK 到达时窗口增加 1 个包，超时发生时减少 1 个包，但这被证明太激进了。快速响应拥塞对稳定性非常重要。
对于 TCP 为什么对减少窗口很积极而对增加窗口很保守，直观解释是，窗口太大会造成很多后果。因为当窗口太大时，丢失的包将被重传，从而使拥塞更加严重，尽快摆脱这种状态非常重要。可以将 AIMD 看作是缓慢增加数据，以探测拥塞开始的级别，然后当通过超时检测到该级别时，从拥塞崩溃的边缘快速后退。
最后，由于超时是引发指数减少的拥塞的标志，TCP 需要它所能承受的最精确的超时机制。我们已经在第 4.1 节中介绍了 TCP 的超时机制，但是请回忆一下，超时被设置为平均 RTT 和平均偏差的函数。
