关于程序员:TCP拥塞控制详解-4-控制算法

网络传输问题实质上是对网络资源的共享和复用问题，因而拥塞管制是网络工程畛域的外围问题之一，并且随着互联网和数据中心流量的爆炸式增长，相干算法和机制呈现了很多翻新，本系列是收费电子书《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，作为前一个预计和新样本之间的加权平均值。也就是说,

$$\mathsf{EstimatedRTT} = \alpha \times \mathsf{EstimatedRTT} + (1 – \alpha{}) \times \mathsf{SampleRTT}$$

参数 α 是为了平滑 EstimatedRTT。小的 α 值能够感触到 RTT 的渺小变动，但可能会容易受到临时稳定的影响。另一方面，大的 α 值更稳固，但可能不够快，无奈适应真正的变动。TCP 初始标准倡议在 0.8 到 0.9 之间取值，而后基于EstimatedRTT 以一种相当激进的形式计算超时:

$$\mathsf{TimeOut = 2} \times \mathsf{EstimatedRTT}$$

4.1.2 Karn/Partridge 算法

几年后，在这种简略办法中发现了一个相当显著的缺点: ACK 实际上并不响应传输，而是响应对数据的接管。换句话说，当重传了某个分片，而后收到一个 ACK，发送端在测量样本 RTT 时，无奈确定这个 ACK 应该与第一次还是第二次传输的分片匹配。

为了计算出精确的 SampleRTT，必须晓得 ACK 与哪次传输相关联。如图 21 所示，如果假如 ACK 匹配初始传输，但实际上应该匹配第二次传输，那么SampleRTT 就太大了 (a)；如果假如 ACK 匹配第二次传输，但实际上是匹配第一次传输，那么SampleRTT 就太小了(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，而后将新采样退出超时计算中，如下所示:

$$\mathsf{Difference = SampleRTT – EstimatedRTT}$$
$$\mathsf{EstimatedRTT = EstimatedRTT} + (\delta \times \mathsf{Difference)}$$
$$\mathsf{Deviation = Deviation} + \delta \mathsf{(| Difference | – Deviation)}$$

δ 在 0 到 1 之间取值，即，计算 RTT 及其变动的挪动加权平均值，而后以 EstimatedRTT 和Deviation的函数计算超时，如下所示:

$$\mathsf{TimeOut} = \mu \times \mathsf{EstimatedRTT} + \phi \times \mathsf{Deviation}$$

依据经验值，μ 个别设为 1，$\phi$ 个别设为 4。因而，当方差很小时，TimeOut靠近 EstimatedRTT，较大的方差会导致Deviation 主导计算。

4.1.4 实现

对于 TCP 中超时的实现，有两点须要留神。首先，不应用浮点运算就能够实现 EstimatedRTT 和Deviation的计算。相同，整个计算被扩大为 $\mathsf2^n$，δ 被设为 $\mathsf1/2^n$，从而容许咱们进行整数运算，通过移位实现乘除法，取得更高的性能。计算结果由上面的代码片段给出，其中 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 的无效窗口批改如下:

$$\mathsf{MaxWindow = MIN(CongestionWindow, AdvertisedWindow)}$$
$$\mathsf{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。

只缩小窗口大小的拥塞控制策略显然过于激进，咱们还须要可能减少拥塞窗口，以利用网络中早先可用的容量。这是 AIMD 的 ” 线性减少 ” 局部。其工作原理如下，每次发送端胜利发送一个 CongestionWindow 值的包时，也就是说，在上一个往返工夫 (RTT) 发送进来的每个包都被 ACK 了，就会给 CongestionWindow 减少相当于一个包的值，这种线性增长如图 22 所示。

实际中，TCP 不会等到收到整个窗口的 ACK 值才给拥塞窗口减少一个包，而是每收到一个 ACK 就减少一点拥塞窗口。具体来说，每次 ACK 达到时，拥塞窗口按如下形式递增:

$$\mathsf{Increment = MSS} \times \mathsf{(MSS\ /\ CongestionWindow)}$$
$$\mathsf{CongestionWindow = CongestionWindow\ +\ Increment}$$

也就是说，不是在每个 RTT 中给 CongestionWindow 减少整个 MSS 字节，而是在每次接管到 ACK 时减少 MSS 的一小部分。假如每个 ACK 都响应收到了 MSS 字节，那么这个局部就是MSS/CongestionWindow。

这种一直减少和缩小拥塞窗口的模式在连贯的整个生命周期中继续存在。事实上，如果咱们将 CongestionWindow 的以后值作为工夫的函数绘制进去，会失去一个如图 23 所示的锯齿状图形。对于 AIMD 须要了解的重要概念是，发送端违心以比减少拥塞窗口更快的速度缩小拥塞窗口。咱们能够设想另一种减少 / 缩小策略，在 ACK 达到时窗口减少 1 个包，超时产生时缩小 1 个包，但这被证实太激进了。疾速响应拥塞对稳定性十分重要。

对于 TCP 为什么对缩小窗口很踊跃而对减少窗口很激进，直观解释是，窗口太大会造成很多结果。因为当窗口太大时，失落的包将被重传，从而使拥塞更加重大，尽快解脱这种状态十分重要。能够将 AIMD 看作是迟缓减少数据，以探测拥塞开始的级别，而后当通过超时检测到该级别时，从拥塞解体的边缘疾速后退。

最初，因为超时是引发指数缩小的拥塞的标记，TCP 须要它所能接受的最准确的超时机制。咱们曾经在第 4.1 节中介绍了 TCP 的超时机制，然而请回顾一下，超时被设置为均匀 RTT 和平均偏差的函数。

4.3 慢启动(Slow Start)

当发送端应用了靠近网络的可用容量时，刚刚介绍的减少机制是一种正当的办法，但如果从头开始时，须要破费太长的工夫。因而，TCP 提供了第二种机制，被反直觉的称为 慢启动(slow start)，用于从冷启动疾速减少拥塞窗口。慢启动能够成倍增加拥塞窗口，而不是线性减少。

具体来说，发送端首先将 CongestionWindow 设置为一个包。当这个包的 ACK 达到时，TCP 将 CongestionWindow 加 1，而后发送两个包。在收到相应的两个 ACK 后，TCP 将 CongestionWindow 加 2，而后发送 4 个数据包。最终的后果是，TCP 在每次 RTT 传输中无效减少了一倍的数据包数量。图 24 显示了慢启动期间传输的数据包数量的增长，能够将其与图 22 所示的线性增长进行比拟。

为什么指数机制会被称为 ” 慢 ” 的确令人费解，但从其历史背景来看，这是有情理的。不要将慢启动与前一节的线性机制进行比拟，而是与 TCP 的原始行为进行比拟。考虑一下，当建设连贯时，发送端首先 (即以后没有信息包在传输时) 开始发送数据包，会产生什么状况。如果发送端发送的包数量和窗口容许的数量一样多(也正是 TCP 在开发慢启动之前所做的)，那么即便网络中有相当大的可用带宽，路由器也可能无奈耗费这些突发的包，因为这齐全取决于路由器上有多少缓冲空间可用。因而，慢启动被设计为距离发送数据包，这样就不会产生突发流量。换句话说，只管它的指数增长比线性增长要快，但慢启动比一次性发送整个通告窗口的数据要 ” 慢 ” 得多。

实际上，慢启动有两种不同的状况。第一种状况是在连贯刚开始建设的时候，此时发送端不晓得在给定工夫里能传输多少包。(请记住，明天 TCP 链接运行在从 1 Mbps 到 40 Gbps 的各种网络状况下，所以发送端没有方法晓得网络容量。)在这种状况下，慢启动每过一个 RTT 就加倍 CongestionWindow，直到产生了丢包，而后因为超时导致指数缩小并将CongestionWindow 除以 2。

第二种状况更奥妙一些，当连贯在期待超时生效，就会产生这种状况。回忆一下 TCP 的滑动窗口算法是如何工作的，当一个包失落时，发送端最终会达到一个状态，在这个状态上它曾经发送了通告窗口容许的尽可能多的数据，因而在期待一个不会达到的 ACK 时阻塞。最终会产生超时，但此时没有包在传输，这意味着发送端将不会收到 ACK 来触发新包的传输。相同，发送端将接管一个累积的 ACK，从而从新关上整个通告窗口，然而，如上所述，发送端将应用慢启动来重新启动数据流，而不是一次将整个窗口的数据全副发送到网络上。

尽管发送端再次应用慢启动，但当初晓得的信息比连贯开始时更多。具体来说，发送端具备以后 (且有用) 的CongestionWindow值，作为丢包的后果，这个值是上次丢包之前存在的 CongestionWindow 值除以 2，咱们能够把它看作指标拥塞窗口。慢启动疾速减少发送速率达到这个值，而后减少的窗口将超过这个值。留神，咱们须要小小的记录一下，因为咱们想要记住由指数缩小导致的指标拥塞窗口，以及慢启动应用的理论拥塞窗口。为了解决这个问题，TCP 引入了一个长期变量来存储指标窗口，通常称为 CongestionThreshold，被设置为与CongestionWindow 的值相等，这个值是由指数缩小产生的。而后，变量 CongestionWindow 被重置为一个包，并且随着每一个 ACK 的接管而减少一个包，直到达到CongestionThreshold，而后每过一个 RTT 再减少一个包。

换句话说，以下代码段定义了 TCP 如何减少拥塞窗口:

{
    u_int    cw = state->CongestionWindow;
    u_int    incr = state->maxseg;

    if (cw > state->CongestionThreshold) 
        incr = incr * incr / cw;
    state->CongestionWindow = MIN(cw + incr, TCP_MAXWIN);
}

其中 state 示意特定 TCP 连贯的状态，并定义了容许减少的拥塞窗口的下限。

图 25 显示了 TCP 的 CongestionWindow 是如何随着工夫的推移而减少和缩小的，并用来阐明慢启动和线性减少 / 指数缩小的相互作用。这个图是从理论的 TCP 连贯中获取的，并显示了随着时间推移的 CongestionWindow 的以后值(带色彩的线)。

对于这个图示，有几个中央须要留神。首先是连贯开始时，拥塞窗口疾速减少。这对应于最后的慢启动阶段。慢启动阶段持续，直到在大概 0.4 秒时丢了几个包，此时 CongestionWindow 在大概 34 KB 时变平。(上面将探讨为什么这么多数据包在慢启动过程中失落。) 拥塞窗口变平的起因是因为失落了几个包，没有 ACK 达到。事实上，在此期间没有发送任何新数据包，这一点从顶部短少散列标记就能够看出。超时最终大概在 2 秒产生，此时拥塞窗口被除以 2(即从大概 34 KB 削减到大概 17 KB)，并且将 CongestionThreshold 设置为这个值，慢启动导致 CongestionWindow 被重置为一个包，并从那里开始减速。

图中没有足够的细节来查看当两个数据包在 2 秒后失落时到底会产生什么，所以咱们间接跳到产生在 2 秒到 4 秒之间的拥塞窗口的线性减少。大概 4 秒时，同样是因为丢包，拥塞窗口变平。在 5.5 秒的时候:

1. 产生了超时，导致拥塞窗口被除以 2，从大概 22 KB 降落到 11 KB，而 CongestionThreshold 被设置为这个值。
2. CongestionWindow被重置为一个包，发送方进入慢启动。
3. 慢启动导致 CongestionWindow 指数增长，直到达到CongestionThreshold。
4. 而后 CongestionWindow 线性增长。

当大概 8 秒时再次发生超时，反复雷同的模式。

当初咱们回到这个问题: 为什么在最后的慢启动期间会失落这么多包。此时，TCP 试图理解网络上有多少带宽可用，这是一项艰巨的工作。如果发送端在这个阶段不被动，例如，如果只是线性减少拥塞窗口，那么须要很长时间能力发现有多少带宽可用。这可能会对此连贯的吞吐量产生重大影响。另一方面，如果发送端在这个阶段比拟激进，那么就须要冒着被网络抛弃半个窗口的数据包的危险。

为了理解指数增长过程中会产生什么，思考这样一种状况: 发送端仅仅可能胜利通过网络发送 16 个包，导致网络的拥塞窗口翻倍至 32。然而，假如网络恰好有足够的容量反对来自这个发送端的 16 个数据包。可能的后果是，在新的拥塞窗口下发送的 32 个数据包中，有 16 个将被网络抛弃，实际上这是最坏的后果，因为一些数据包会被缓冲到某个路由器中。随着网络带宽时延积的减少，问题将变得越来越重大。例如，1.8 MB 的带宽时延积意味着每个连贯在开始时都有可能失落高达 1.8 MB 的数据。当然，须要假设发送端和接收端都实现了 ” 大窗口(big windows)” 扩大。

也有人摸索慢启动的代替计划，即发送端试图通过更简单的办法预计可用带宽。其中一个例子叫做 快启动(quick-start)。其根本思维是，TCP 发送端通过将申请的速率作为 IP 选项放入 SYN 包中，从而要求比慢启动所容许的更大的初始发送速率。沿路路由器能够查看该选项，评估该流进口链路以后的拥塞程度，并决定该速率是否能够承受，或者是否能够承受较低的速率，或者是否应该应用规范慢启动。当 SYN 达到接收端时，要么蕴含门路上所有路由器都能够承受的速率，要么蕴含门路上一个或多个路由器不能反对快启动申请的批示。在前一种状况下，TCP 发送方应用该速率开始传输，在后一种状况下，回到规范慢启动状态。如果容许 TCP 以更高速率开始发送，会话能够更快达到填满流水线的状态，而不必破费许多往返工夫来实现此操作。

显然，对 TCP 进行这种加强的挑战之一是，与规范 TCP 相比，须要来自路由器的更多单干。如果门路中的某个路由器不反对快启动，则整个零碎将复原到规范慢启动。因而，在这类加强进入互联网之前可能还须要很长一段时间，目前更可能用于受控的网络环境(例如，钻研网络)。

4.4 疾速重传和疾速复原

目前为止所介绍的机制是将拥塞管制增加到 TCP 的最后提议的一部分，因为相应实现被蕴含在 1988 年的 4.3 BSD Unix 的 Tahoe 发行版中，因而被统称为 TCP Tahoe。一旦被宽泛部署，教训表明 Tahoe 的一些问题随后被 1990 年初的TCP Reno (4.3BSD-Reno 版本的一部分) 解决。本节将介绍相干教训以及 Reno 解决问题的办法。

简言之，TCP 超时的粗粒度实现导致长时间的连贯在期待计时器过期时生效。一种称为 疾速重传(fast retransmit) 的启发式办法有时会比惯例超时机制更早触发失落数据包的重传。疾速重传机制不替换惯例超时，只是减少了另一种能够更及时检测丢包的办法。

其思维是，每当一个数据包达到接收端，接收端回应一个 ACK，即便这个序列号曾经被确认。因而，当一个乱序包达到，TCP 还不能确认包中蕴含的数据(因为之前的数据还没有达到)，TCP 会从新发送和上次雷同的 ACK。

雷同 ACK 的第二次传输称为 反复 ACK(duplicate ACK)。当发送端看到一个反复 ACK 时，就晓得另一方肯定收到了一个程序谬误的包，这表明前一个包可能曾经失落了。不过也有可能之前的包只是被提早了而不是失落了，所以发送端会期待，直到看到肯定数量的反复 ACK(实际上是 3 个)，而后从新发送失落的包。这里内置的假如 (在实践中失去了很好的验证) 是，乱序数据包比失落的数据包要少得多。

图 26 阐明了反复 ACK 如何触发疾速重传。本例中，目的地接管到包 1 和包 2，但包 3 在网络中失落。因而，当数据包 4 达到时，目的地将对数据包 2 发送一个反复 ACK，当数据包 5 达到时再次发送，以此类推。(为了简化示例，咱们从包 1、2、3 等的角度思考，而不是思考每个字节的序列号。) 当发送方看到数据包 2 的第三个反复 ACK(因为接管方收到了数据包 6 而发送的 ACK)时，会从新发送数据包 3。请留神，当包 3 的重传正本达到目的地时，接管方随后将包含包 6 在内的所有内容的累积 ACK 发送回发送端。

CongestionWindow；实心标记 = 超时；散列标记 = 每个数据包传输的工夫；竖线 = 最终重传的数据包第一次传输的工夫。” title=” 图 27. 疾速重传 TCP 图示。黑白线 =CongestionWindow；实心标记 = 超时；散列标记 = 每个数据包传输的工夫；竖线 = 最终重传的数据包第一次传输的工夫。”>

图 27 展现了具备疾速重传机制的 TCP 版本的行为。将此图示与图 25 进行比拟是很有意思的事件，拥塞窗口放弃扁平且打消了无奈发送数据包的工夫。通常，这种技术可能打消典型 TCP 连贯上大概一半的粗粒度超时，从而使吞吐量比应用其余办法能够实现的性能进步约 20%。但请留神，疾速重传策略并不能打消所有粗粒度超时，这是因为对于小窗口来说，在传输过程中没有足够多的包来导致发送足够多的反复 ACK。如果有足够多的丢包(例如，在初始慢启动阶段产生的状况)，滑动窗口算法最终会阻塞发送方，直到呈现超时。在实践中，TCP 的疾速重传机制能够在每个窗口中检测到最多三个丢包。

还能够做进一步改良。当疾速重传机制收回了拥塞信号，能够基于还在流水线中的 ACK 来触发包的发送，而不是将拥塞窗口设为一个包并开始慢启动。这一被称为 疾速复原(fast recovery) 的机制无效打消了疾速重传机制检测到丢包并开始慢启动的阶段。例如，疾速复原防止了图 27 中 3.8 到 4 秒之间的慢启动周期，而是简略的将拥塞窗口缩小一半(从 22 KB 到 11 KB)，并从新开始减少拥塞窗口。换句话说，慢启动只在连贯开始时和产生粗粒度超时时应用，其余任何时候，拥塞窗口都遵循纯正的线性减少 / 指数缩小模式。

4.5 增量改良

如果对 TCP 拥塞管制的钻研只教会了咱们一件事，那就是意识到这个问题有如许简单，以及须要正确处理多少细节。只有通过一系列通过教训测验的后果，即渐进的改良能力实现。上面给出了这一教训的两个额定例子。

4.5.1 TCP SACK

原始 TCP 标准应用累积确认，意味着接管方在任何丢包之前只确认收到的最初一个包。能够认为接管方领有接管包的汇合，其中任何失落的包都由接管字节流中的空洞示意。依据原始标准，即便失落了几个包，也只能通知发送方第一个洞开始。直观的说，这种细节的不足可能会限度发送方对丢包作出无效响应的能力。解决这个问题的办法被称为 选择性确认(selective acknowledgments) 或SACK。SACK 是 TCP 的一个可选扩大，最后是在 Jacobson 和 Karels 的晚期工作实现后不久提出的，但因为很难证实有用，因而花了几年工夫才被承受。

在没有 SACK 的状况下，当分片被无序接管时，发送方只有两种正当的策略。对于反复 ACK 或超时，乐观策略不仅会重传显著失落的分片 (接管方失落的第一个包)，还会重传随后传输的任何分片。实际上，乐观策略假如了最坏的状况: 所有这些局部都隐没了。乐观策略的毛病是可能不必要的重传第一次胜利接管到的分片。另一种策略是对失落信号(超时或反复 ACK) 做出响应，办法是只重传触发该信号的分片。乐观办法假如了最乐观的状况: 只有一个局部失落了。乐观策略的毛病是，当一系列间断分片失落时，复原十分迟缓，在拥挤状况下就可能产生这种状况。之所以慢，是因为在发送方收到重传前一段的 ACK 之后，才会发现每一个分片的失落。这意味着它每个分片都须要耗费一个 RTT，直到重传失落序列中的所有分片。应用 SACK 选项，发送方能够应用一种更好的策略: 只重传那些填补已选择性确认的分片之间空白的分片。

连贯开始时，发送方首先协商 SACK，通知接管方它能够解决 SACK 选项。当应用 SACK 选项时，接管方持续失常确认分片，Acknowledge字段的含意不会扭转, 然而也会对任何无序接管的块应用额定的确认扩大报头。这容许发送方辨认在接管方存在的空洞，并只重传失落的分片，而不是之后的所有分片。

SACK 被证实能够进步 TCP Reno 的性能，尤其是在一个 RTT 中抛弃多个包的状况下(因为当只抛弃一个包时，累积 ACK 和 SACK 是一样的)。随着工夫的推移，随着带宽时延积的减少，这种状况变得更可能产生，给定 RTT 可能抛弃更多的数据包。因而，在 1996 年被提议成为 IETF 规范的 SACK 是对 TCP 的及时补充。

4.5.2 NewReno

从麻省理工学院的 Janey Hoe 在 20 世纪 90 年代中期的一些钻研开始，这种被称为 NewReno 的加强技术通过在某些包失落的状况下对重传哪些包做出更智能的决定，逐步提高了 TCP 的性能。

延长浏览:\
J. Hoe. Improving the start-up behavior of a congestion control scheme for TCP. SIGCOMM‘96. August 1996.

NewReno 背地的要害见解是，即便没有 SACK，反复 ACK 也能够向发送方传递抛弃了多少包以及抛弃了哪些包的信息，因而发送方能够在何时重传包方面做出更理智的抉择。此外，在单个窗口呈现屡次丢包的状况下，NewReno 能够防止以前版本中呈现的对拥塞窗口屡次减半。

NewReno 有很多细节，但简略来说，如果丢了一个包，发送方须要反复 3 次 ACK，才会从新发送失落的包。当接收端收到重传时，因为当初曾经填满了接收缓冲区中的空洞，因而将 ACK 所有缓冲区中的包。相同，如果失落了多个包，则在收到重传包之后的第一个 ACK 将只能局部笼罩未响应的包。由此，发送方能够推断有更多的包失落，并立刻开始尝试通过发送下一个尚未失去确认的包来填补空白。这能够缩小的超时，缩小阻塞工夫并且缓解对拥塞窗口的缩小。

值得注意的是，NewReno 在 1999 年至 2012 年公布了三次 RFC，每一次都修复了之前算法中的一些问题。这是一个对于了解拥塞管制的细节是如许简单的案例钻研(特地是对于 TCP 重传机制的奥妙之处)，也减少了部署新算法的挑战。

4.6 TCP CUBIC

当初应该很分明，试图找到向网络发送流量的适当速率是拥塞管制的外围，而在任何一个方向上都有可能出错。比方发送流量过少，网络利用率不高，会导致应用程序性能降落。而发送过多流量会导致网络拥塞，最坏的状况下会导致拥塞解体。在这两种故障模式之间，发送过多流量通常会导致更重大的问题，并且因为重传失落的数据包，拥塞会迅速减轻。Tahoe、Reno 和 NewReno 采纳的 AIMD 办法反映了这一点: 迟缓减少窗口(线性减少)，迅速缩小窗口(指数缩小)，以便在拥塞解体变得过于重大之前从解体的边缘退回。然而在高带宽提早环境中，探测拥塞时过于激进的代价是相当高的，因为在 ” 流水线满 ” 之前可能须要许多 RTT。因而，这导致了对如何探测适当的窗口大小的一些反思。

一种被称为Binary Increase Congestion Control (BIC) 的新办法提出，窗口应该在某些时候疾速关上，而在其余时候慢一些的想法。BIC 并没有像 TCP Reno 那样忽然的从指数窗口增长切换到线性窗口增长，而是对 ” 正确 ” 的窗口大小进行二分查找。在丢包之后，拥塞窗口以指数参数 β 截断。每次在新的窗口大小上胜利发送报文，窗口就会减少到其以后值和造成拥塞的旧值的中点。通过这种形式，以先快后慢的速度逐步靠近旧值。(极其状况下，窗口将永远不会复原到原来的值，相似于芝诺的悖论，但当达到某个阈值时，会被设置为原来的值)。

在这一点上，如果没有拥塞，能够得出结论，网络条件曾经扭转，能够探测新的拥塞窗口大小。BIC 先慢一点，而后快一点。能够在图 28 中看到 BIC 减少窗口的大抵形态，渐近靠近 $W_{max}$(最初一次丢包之前的旧拥塞窗口)，而后超过它。

三次函数，如图 28 所示，有三个阶段: 迟缓增长，平台阶段，快速增长。在最初一次拥塞事件之前实现的最大拥塞窗口大小是初始指标(示意为 $\mathsf{W}_{max}$)。能够看到窗口一开始快速增长，但随着越来越凑近 $\mathsf{W}_{max}$，增长越来越平缓，最初阶段开始摸索新的可实现的 $\mathsf{W}_{max}$ 指标。

具体来说，CUBIC 用自上次拥塞事件产生以来工夫 (t) 的函数计算拥塞窗口(CongestionWindow)

$$\mathsf{CongestionWindow(t)} = \mathsf{C} \times \mathsf{(t-K)}^{3} + \mathsf{W}_{max}$$

其中，

$$\mathsf{K} = \sqrt[3]{\mathsf{W}_{max} \times (1 – \beta{})/\mathsf{C}}$$

C 是一个比例常数，β 是指数递加因子。CUBIC 将后者设为 0.7，而不是规范 TCP 应用的 0.5。回头看看图 28，CUBIC 通常被形容为在凹函数和凸函数之间转换(而规范 TCP 的线性函数仅是凸函数)。

乏味的是，与 TCP 晚期变体相比，CUBIC 要么更激进，要么更不激进，这取决于具体条件。短 RTT TCP Reno 流往往能无效获取瓶颈带宽，因而 CUBIC 蕴含了一个 ”TCP 敌对 ” 模式，其指标是像 TCP Reno 一样激进。但在其余状况下，尤其是高带宽提早网络，CUBIC 可能取得更大的瓶颈带宽份额，因为 CUBIC 能够更快减少窗口大小。这让咱们想到 3.3 节的探讨，即对现有算法的 ” 偏心 ” 是否是正确的设计指标。最初，对 CUBIC 进行了宽泛的剖析，在许多条件下均体现出良好的性能，且不会造成不适当的挫伤，因而失去了广泛应用。

延长浏览:\
S. Ha, I. Rhee, and L. Xu. CUBIC: a New TCP-friendly High-speed TCP Variant. ACM SIGOPS Operating Systems Review, July 2008.

你好，我是俞凡，在 Motorola 做过研发，当初在 Mavenir 做技术工作，对通信、网络、后端架构、云原生、DevOps、CICD、区块链、AI 等技术始终保持着浓重的趣味，平时喜爱浏览、思考，置信继续学习、一生成长，欢送一起交流学习。\
微信公众号：DeepNoMind

本文由 mdnice 多平台公布