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