TCP拥塞控制策略

大家好，又见面了，我是你们的朋友全栈君。

一、Reno

1、算法执行示意

                                    图1 算法执行图

2、算法原理

Reno是一种基于丢包的拥塞控制算法，将丢包视为出现拥塞，采取缓慢探测的方式，逐渐增大拥塞窗口，当出现丢包时，将拥塞窗口减小。该算法拥塞控制的过程分为四个阶段：慢开始、拥塞避免、快重传和快恢复，分别对应四种算法。 

（1）慢开始算法

当主机总数据时，由于并不清楚网络的负荷情况，所以如果立即把大量数据字节注入到网络，那么就有可能引起网络发生拥塞。因此，慢开始即由小到大逐渐增大发送窗口，也就是说，由小到大逐渐增大拥塞窗口数值。

（2）拥塞避免算法

让拥塞窗口cwnd缓慢地增大，即每经过一个往返时间RTT就把发送方的拥塞窗口cwnd加1，而不是向慢开始阶段那样加倍增长。因此在拥塞避免阶段就有“加法增大”AI的特点，即拥塞窗口cwnd按线性规律缓慢增长。

 （3）快重传算法

发送方一旦收到3个连续的重复确认报文，就对相应的报文立即进行重传。

（4）快恢复算法

发送方调整门限值ssthresh=cwnd/2，同时设置拥塞窗口cwnd=ssthresh，并开始执行拥塞避免算法。

3、优缺点分析

优点：

①在早期低带宽、低时延的网络中能够很好的发挥作用。

②能够在较大的网络范围内理想地维持公平性原则。 

缺点：

在高带宽延时（High Bandwidth-Delay Product，BDP）网络中，RTT很大，导致拥塞窗口增长很慢，传输速度需要经过很长时间才能达到最大带宽，导致带宽利用率将低。

4、适用场景

适用于低延时、低带宽的网络。

二、BBR

1、算法组成

（1）即时速率的计算

计算一个即时的带宽bw，该带宽是bbr一切计算的基准，bbr将会根据当前的即时带宽以及其所处的pipe状态来计算pacing rate以及cwnd。

（2）RTT的跟踪

在bbr运行过程中，系统会跟踪当前为止最小RTT。

（3）bbr pipe状态机的维持

bbr算法根据互联网的拥塞行为有针对性地定义了4中状态，即STARTUP，DRAIN，PROBE_BW，PROBE_RTT。根据计算得到的即时带宽bw以及持续观察得到的往返时间rtt，在这4个状态之间自由切换，因此不再跟踪系统的TCP拥塞状态机，而旨在用统一的方式来应对pacing rate和cwnd的计算。

（4）结果输出-pacing rate和cwnd

bbr在计算cwnd的同时，还计算了一个与之适配的pacing rate，该pacing rate规定cwnd指示的一窗数据的数据包之间，以多大的时间间隔发送出去。

（5）其它外部机制的利用-fq，rack等

bbr之所以可以高效地运行且如此简单，是因为很多机制并不是它本身实现的，而是利用了外部的已有机制

2、算法原理

BBR也称为基于拥塞的拥塞控制算法，判断网络拥塞的依据是网络上的数据包总量大于瓶颈链路带宽和时延的乘积。因此，BBR算法是周期性地探测网络的容量，交替测量一段时间内的带宽极大值和时延极小值，将其乘积作为作为拥塞窗口大小（交替测量的原因是极大带宽和极小时延不可能同时得到，带宽极大时网络被填满造成排队，时延必然极大；时延极小时需要数据包不被排队直接转发，带宽必然极小），使得拥塞窗口始的值始终与网络的容量保持一致。

3、优缺点分析

优点：

①由于BBR的拥塞窗口是精确测量出来的，不会无限的增加拥塞窗口，也就不会将网络设备的缓冲区填满，避免了出现Bufferbloat问题，使得时延大大降低。

②由于BBR算法不将丢包作为拥塞信号，所以在丢包率较高的网络中，BBR依然有极高的吞吐量。

③BBR算法是反馈驱动的，有自主调节机制，不受TCP拥塞控制状态机的控制，通过测量网络容量来调整拥塞窗口，因此BBR的窗口调整是主动的，发送速率由自己掌控，这样就不会出现在瓶颈带宽附近因发送速率的激增而导致数据包排队或出现丢包的情况。

缺点：

BBR算法的不足之处在于设备队列缓存较大时，会使得BBR在多个周期内测量的极小RTT增大，进而使BBR的带宽减小。

4、适用场景

适用于高带宽、高时延、有一定丢包率的长肥网络，可以有效降低传输时延，并保证较高的吞吐量。

3、HSTCP

1、算法原理

HSTCP，即高速传输控制协议，是高速网络中基于AIMD(加法增大和乘法减小)的一种新的拥塞控制算法,能在高速度和大时延的网络中更有效地提高网络的吞吐率。通过对标准TCP拥塞避免算法的增加和减少参数进行修改，从而实现了窗口的快速增长和慢速减少，使得窗口保持在一个足够大的范围，以充分利用带宽。TCP发送端通过网络所期望的丢包率来动态调整HSTCP拥塞窗口的增量函数。

拥塞避免时的窗口增长方式：cwnd = cwnd + a(cwnd) / cwnd

丢包后窗口下降方式：cwnd = (1-b(cwnd))*cwnd

其中，cwnd表示拥塞窗口大小，a(cwnd)和b(cwnd)为两个函数，在标准TCP中，a(cwnd)=1，b(cwnd)=0.5，为了达到TCP的友好性，在窗口较低的情况下，也就是说在非BDP的网络环境下，HSTCP采用的是和标准TCP相同的a和b来保证两者之间的友好性。当窗口较大时（临界值LowWindow=38），采取新的a和b来达到高吞吐的要求。

2、算法根本思想

当拥塞窗口>阈值时，窗口增加因子a（cwnd）与减少因子b（cwnd）成为拥塞窗口调节大小cwnd的函数。

3、优缺点分析

优点：

在高速网络中能够获得更高的带宽，并且拥塞窗口值可以动态调整，实现了窗口的快速增长和慢速减少，提高了带宽的利用率。

缺点：

存在很严重的RTT不公平性。公平性指共享同一网络瓶颈的多个流之间占有的网络资源相等

4、适用场景

适用于高速度、大时延的网络。

四、Vegas

1、基本思路

RTT增加，拥塞窗口减小；RTT减少，拥塞窗口变大。

2、执行过程机制

（1）慢启动机制

由于一开始慢启动没有相关的传输数据和带宽速度等参数，需要设定慢启动门限。Vegas每经过两个RTT使cwnd拥塞窗口增加1倍。然后计算diff，当diff>a,则结束慢启动，转入拥塞避免。

在 Vegas慢启动中，每经过两个 RTT使 W增加 1倍。其中前一个 RTT内是与 TCP Reno相同的指数增长，即每收到一个 ACK包就将加 1，同时发送出两个数据包，可称为增长期；后一个 RTT内保持不变以观测 RTT的变化，可称为观测期。Vegas的慢启动过程就是由一个增长期和一个观测期周期往复，在每个观测期结束时，计算新的 RTT和diff的值，以此决定是继续下一个周期还是结束慢启动。

（2）拥塞避免机制

Vegas通过比较实际吞吐量和期望吞吐量来调节拥塞窗口的大小。

期望吞吐量：Expected=cwmd/BaseRTT

实际吞吐量：Actual=cwnd/RTT

计算差值：diff=（Expected-Actual）*BaseRTT

BaseRTT是所有观测来回响应时间的最小值，一般是建立连接后所发的第一个数据包的RTT。cwnd是目前的拥塞窗口的大小。定义阈值a、b，当diff拥塞窗口增大，+1；当diff>b，拥塞窗口缩小，-1；当a<=diff<=b,拥塞窗口不变。通常a=1，b=3，意味着该连接至少保留一个包在队列中。

（3）重传机制

Vegas采用更精确的RTT估计值在以下两种情形下决定是否重发：

①当接受到重复ACK时，Vegas检查目前时间和记录的时间标签之差是否比超时值大，如果是，则立刻重发数据包，不必等第三个重复ACK。当接受重传数据包应答后，Vegas以3/4而不是1/2因子降低拥塞窗口。

②当接受到非重复的ACK时，如果它是重发之后的第一或是第二个确认，Vegas将再次检测数据发送时间间隔是否查过超时值。如果是，则重发。

3、优缺点分析

优点：

TCP Vegas在拥塞避免阶段采用的是主动的、基于回路响应延时RTT估计的方法，根据△的值，线性增加或者减少(调整速度为1)拥塞窗口，在实际丢包以前减小发送拥塞窗口。

缺点：

①他会被欺骗，也就是说本身这个正向的延迟就是比它期待的高，比如在tcp中，有可能正向反向做的不是相同的路径，那么当反向有拥塞的时候，就有问题了。也就是数据包ack返回给发送端的就是延迟的。此时就会导致Vegas降低拥塞窗口。

②TCP Vegas只是单纯的指数增长拥塞窗口，没有考虑到网络的动态变化，尤其在慢启动中后期，这会导致加倍数据包短时间内充斥网络，数据包的突发可能会造成短暂的长排队时间(即RTT陡然增加)， TCP Vega会过早地结束慢启动阶段，整体性能严重下降，TCP Vegas存在慢启动阶段过早结束。

③因为TCP Vegas是预测性的调整拥塞窗口，拥塞避免机制过于保守，拥塞避免阶段的窗口调整周期过长。

4、适用场景

适用于网络中只存在Vegas一种拥塞控制算法，竞争公平的情况。

五、Westwood

1.TCPW拥塞控制算法分析

TCPW算法是专门针对无线网络提出的一种拥塞控制算法，是在TCP Reno版本上改进而得，在一定程度上提高了网络出现丢包时TCP的传输性能。TCPW也是由“慢启动”、“拥塞避免”、“快速重传”和“快速恢复”四个部分组成。

TCPW算法主要通过实时测量来估算网络中的带宽值，并利用带宽估计值来调整CWND和SSTHRESH值以达到拥塞控制的目的。基本流程是，通过持续不断地监测TCP目的端返回的ACK速率，从而计算出单位时间内TCP发送端发送的分组数目和数据包大小，计算出网络中的带宽估计值。当出现拥塞收到3个重复ACK或RTO超时时，SSTHRESH和CWND的赋值如下：

              (1)

其中cuurent_bwe是带宽估计值，size 是数据包的大小，min_rtt_estimate是测量中的最小RTT。在收到3个重复ACK时，CWND值设置为SSTHRESH的当前值，而超时的情况下，CWND值设置为1。

2、TCPW算法缺点分析

（1）TCPW算法无法区分丢包类型

当网络中出现丢包时，TCPW算法都会按照拥塞丢包来处理，而不区分是无线丢包还是拥塞丢包。

（2）TCPW算法在处理丢包时具有盲目性且单一

主要体现在CWND和SSTHRESH值的调整上，在出现丢包时，不管丢包原因也不分拥塞程度，单纯减小窗口值，降低数据的发送速率，这种处理会使得网络带宽利用率大幅度下降。

（3）Westwood算法控制的是在从快速恢复阶段退出时的拥塞窗口的值

原理上讲，这时的窗口值应该是一个不包括队列缓存在内的BDP，即最大带宽与最小RTT的乘积。但是这种算法的在解求最大带宽问题上存在缺陷。标准的Westwood算法做的非常粗糙，它将一个TCP连接的生命周期分解为一段一段的采样周期，每一个采样周期内采集被ACK的字节数，然后除以采样周期的间隔，结果做低通滤波(其实就是移动指数平均)，即为带宽。然而，4.9版本之前的内核对于Linux的TCP实现，在开放给拥塞控制回调的接口中，只能通过当前的snd_una与上次记录的snd_una之间的差值来估算被ACK的字节数，说“估算”这个词的意思是，在拥塞控制回调中，关于SACK的信息会丢失。

3、TCP-NW算法

针对TCPW算法的不足，我们提出了一种改进算法TCP-NW，TCP-NW算法的步骤如下：

（1）计算网络带宽估计值

通过TCPW协议中的带宽估计算法实时计算网络中的带宽估计值current_bwe，引入一个变量bwe_max，用于保存此过程中的current_bwe的最大值。

（2）计算网络带宽利用率

根据(1）中计算出的current_bwe和bwe_max的值，计算出网络中的带宽利用率。计算公式如式所示：

               (2)

　　其中，current_bwe为当前带宽估计值，bwe_max为当前带宽估计值中的最大值，α∈（0，1]。

　　由于网络中带宽利用率较低时，网络拥塞的可能性较小，如果网络中此时出现了数据丢包，则认定为出现了无线丢包。此算法中α∈（0，1/4]时，认定为无线丢包。

（3）分别对不同情况下的丢包作出相应处理

　　当在无线网络出现数据丢包时，根据计算出的网络带宽利用率来调整CWND和SSTHRESH值的大小。由于在网络环境下丢包的原因主要有三个重复的ACK和超时，因此两种情况下的调整如下：

　　收到三个重复ACK当出现无线丢包时（此时网络并没有发生拥塞），如果按照式（1）计算，SSTHRESH值会过度减小，CWND进而减小，从而降低了数据发送速率，浪费网络带宽，改进后的重新计算公式如式（3）所示：

           (3)

　　其中，α为当前网络的带宽利用率，计算公式如式（2）。

式（3）虽然避免了在带宽利用率较低时将SSTHRESH值过度减小的问题，但是在带宽利用率较高时，依然存在此问题。为了解决此问题，将α值进行细化，重新计算公式如式（4）所示：

    (4)

六、CUBIC

1、tcp cubic数学模型

（1）CUBIC在设计上简化了BIC-TCP的窗口调整算法，在BIC-TCP的窗口调整中会出现一个凹和凸(这里的凹和凸指的是数学意义上的凹和凸，凹函数/凸函数)的增长曲线，CUBIC使用了一个三次函数(即一个立方函数)，在三次函数曲线中同样存在一个凹和凸的部分，该曲线形状和BIC-TCP的曲线图十分相似，于是该部分取代BIC-TCP的增长曲线。另外，CUBIC中最关键的点在于它的窗口增长函数仅仅取决于连续的两次拥塞事件的时间间隔值，从而窗口增长完全独立于网络的时延RTT，之前讲述过的HSTCP存在严重的RTT不公平性，而CUBIC的RTT独立性质使得CUBIC能够在多条共享瓶颈链路的TCP连接之间保持良好的RRTT公平性。

（2）当某次拥塞事件发生时，Wmax设置为此时发生拥塞时的窗口值，然后把窗口进行乘法减小，乘法减小因子设为β，当从快速恢复阶段退出然后进入到拥塞避免阶段，此时CUBIC的窗口增长开始按照“凹”式增长曲线进行增长，该过程一直持续直到窗口再次增长到Wmax，紧接着，该函数转入“凸”式增长阶段。该方式的增长可以使得窗口一直维持在Wmax附近，从而可以达到网络带宽的高利用率和协议本身的稳定性。

                                     图 2  窗口增长图像

其中窗口的增长函数如下：

W(t) = C * (t-K)3 + Wmax,其中C和β为常量。

t为当前时间距上一次窗口减小的时间差，而K就代表该函数从W增长到Wmax的时间周期。

（3）当收到ACK后，CUBIC计算利用该算法计算下一个RTT内的窗口增长速度，即计算W(t+RTT)，该值将作为cwnd的目标值，根据cwnd的大小，CUBIC将进入三种不同模式，如果cwnd会小于在标准TCP下经过上次拥塞之后的时刻t窗口将会达到的值(该值是通过标准TCP的窗口增长函数计算出来的)，那么CUBIC就处于标准TCP模式，如果小于Wmax，那么位于凹阶段的，如果大于Wmax，那么处于凸阶段。

2、tcp cubic内核源代码调用逻辑

（1）连接每收到一个ack，则调用tcp_ack

（2）tcp_ack会调用bictcp_acked，用来更新cnt和delayed_ack（用来消除delay包的影响）

（3）tcp_ack会调用bictcp_cong_avoid，这是分两种情况：

①snd_cwnd小于慢启动阈值，处于慢启动阶段，则调用tcp_slow_start

②snd_cwnd大于慢启动阈值，处于拥塞避免阶段，则调用bictcp_update来更新bictcp，再调用tcp_cong_avoid_ai

（4）tcp_ack中如果检测到丢包，进入拥塞处理阶段， 则bictcp_recalc_ssthresh来更新慢启动阈值。

（5）tcp_ack中完成丢包重传后，退出拥塞处理阶段，则调用bictcp_undo_cwnd来更新snd_cwnd快速重传：tcp_ack中的丢包检测，即检测到连续3个重复ACK。快速恢复：bictcp_undo_cwnd，直接把snd_cwnd更新为max(snd_cwnd，last_max_cwnd)，和掉包前相差不大。

3、tcp cubic算法的优缺点分析

CUBIC算法能在高速网络环境中有效的提升网络速度,在拥塞丢包严重,网络流量很低时快速恢复网络速度;但同时因为拥塞窗口波动太大,高速TCP流的吞吐量变化太大,带宽的利用率很不稳定。

结束语

本文首先介绍了TCP的拥塞控制的产生原因，就产生的原因分析、比较了TCP拥塞控制的六种算法，同时指出了这六种算法的优缺点，其中Reno算法是较为常用以及为人们熟知的一种经典算法，包括了慢启动、拥塞控制、快恢复和快重传四个阶段，其能够在较大的网络范围内理想地维持公平性原则，但只适用于低延时、低带宽的网络。其他拥塞控制算法例如CUBIC算法，在高速的网络环境中能够有效的提升网络速度,在拥塞丢包严重、网络流量很低时能够快速恢复网络速度，但同时因为拥塞窗口波动太大，导致其带宽不稳定。因此，各种TCP拥塞控制策略都有其优点和缺点，所以我们应该根据不同的网络环境选择相对应的最优TCP控制策略。

参　考　文　献

[1] 《计算机研究与发展》编辑部，“各类参考文献的著录格式及示例”，http://www.cajcd.edc.cn/pub/wml.txt/980810-2.html,2004-09-08/2005-07-24.

[2] 黄智诚、谢静贤、黄恺昕，中文WORD 2000使用指南，北京: 中国石化出版社，2000.

[3] 陈宜东，TCP协议中的拥塞控制[D].哈尔滨：哈尔滨理工大学，2003.

[4] Comer D.Internetworking with TCP IP (Volume I)Principles, protocols, and architecture[M].PrenticeHall,Inc.,aSimon&Schuster Company . September 1998.

[5] Stevens W.TCP Slow Start, Congestion Avoidance, Fast Retransmit , and Fast Recovery Algorithms[ R] .RFC2001 , January 1997. [ 3] M.Allman , V.Paxson , W.Stevens.TCP Congestion Control[ R] . RFC2581 .April 1999.

[6] 王强、普杰信、刘伟，TCP拥塞控制慢启动研究[D].河南：河南科技大学，2007.

[7] 钱同惠、徐跃东、关治洪，基于TCP协议的网络拥塞控制改进算法的研究[D].武汉：江汉大学，2004.

[8] 陈文娟.TCP/IP计算机网络拥塞控制问题浅析[J].甘肃科技,2018,34(07):12-15.

[9] 叶成荫,曹宇,刘琳琳.TCP网络自适应有限时间拥塞控制[J].电机与控制学报,2018,22(12):107-113.

[10] 曹涛涛. 拥塞控制算法的性能评估及公平性分析[D].南京大学,2017.