拥塞控制算法, CUBIC, BBR

BBR

BBR对TCP性能的提升是巨大的，它能更有效的使用当下网络环境，Youtube 应用后在吞吐量上有平均4%提升 (对于日本这样的网络环境有14%以上的提升）：

报文的往返时延 RTT 降低了33%，这样如视频这样的大文件传输更快，用户体验更好：

不像 CUBIC 这种基于丢包做拥塞控制，常导致瓶颈路由器大量报文丢失，所以重新缓存的平均间隔时间也有了11%提升：

在 Linux4.19 内核中已经将拥塞控制算法从 CUBIC (该算法从2.6.19内核就引入Linux了）改为 BBR，而即将面世的基于 UDP 的 HTTP3 也使用此算法。许多做应用开发的同学可能并不清楚什么是拥塞控制，BBR 算法到底在做什么，我在《Web协议详解与抓包实战》这门课程中用了6节课在讲相关内容，这里我尝试下用一篇图片比文字还多的文章把这个事说清楚。

TCP 协议是面向字符流的协议，它允许应用层基于 read/write 方法来发送、读取任意长的字符流：

但 TCP 之下的 IP 层是基于块状的 Packet 报文来分片发送的，因此，TCP 协议需要将应用交付给它的字符流拆分成多个 Packet (在TCP传输层被称为 Segment）发送， 由于网速有变化且接收主机的处理性能有限，TCP 还要决定何时发送这些 Segment。TCP 滑动窗口解决了 Client、Server 这两台主机的问题，但没有去管连接中大量路由器、交换机转发 IP 报文的问题，因此当瓶颈路由器的输入流大于其输出流时，便会发生拥塞

这虽然是IP网络层的事，但如果 TCP 基于分层原则不去管，互联网上大量主机的 TCP 程序便会造成网络恶性拥堵。上图中瓶颈路由器已经造成了网速下降，但如果发送方不管不顾，那么瓶颈路由器的缓冲队列填满后便会发生大量丢包，且此时 RTT (报文往返时间）由于存在长队列而极高。

如上图，最好的状态是没有队列，此时 RTT 最低，而 State2 中RTT升高，但没有丢包，到State 3队列满时开始发生丢包。

TCP的拥塞控制便用于解决这个问题。在 BB R出现前，拥塞控制分为四个部分：慢启动、拥塞避免、快速重传、快速恢复：

慢启动在 BBR 中仍然保留，它的意义是在不知道连接的瓶颈带宽时，以起始较低的发送速率，以每 RTT 两倍的速度快速增加发送速率，直到到达一个阈值，对应上图中 0-4 秒。到该阈值后，进入线性提高发送速率的阶段，该阶段叫做拥塞避免，直到发生丢包，对应上图中 8-11 秒。丢包后，发速速率大幅下降，针对丢包使用快速重传算法重送发送，同时也使用快速恢复算法把发送速率尽量平滑的升上来。

如果瓶颈路由器的缓存特别大，那么这种以丢包作为探测依据的拥塞算法将会导致严重问题：TCP 链路上长时间RTT变大，但吞吐量维持不变。

事实上，我们的传输速度在3个阶段被不同的因素限制：1、应用程序限制阶段，此时RTT不变，随着应用程序开始发送大文件，速率直线上升；2、BDP 限制阶段，此时RTT开始不断上升，但吞吐量不变，因为此时瓶颈路由器已经达到上限，缓冲队列正在不断增加；3、瓶颈路由器缓冲队列限制阶段，此时开始大量丢包。如下所示：

如 CUBIC 这样基于丢包的拥塞控制算法在第2条灰色竖线发生作用，这已经太晚了，更好的作用点是 BDP上限开始发挥作用时，也就是第1条灰色竖线。

什么叫做 BDP 呢？它叫做带宽时延积，例如一条链路的带宽是 100Mbps，而RTT是40ms，那么

BDP=100Mbps*0.04s=4Mb=0.5MB 即平均每秒飞行中的报文应当是 0.5MB。因此Linux的接收窗口缓存常参考此设置：

第1条灰色竖线，是瓶颈路由器的缓冲队列刚刚开始积压时的节点。随着内存的不断降价，路由器设备的缓冲队列也会越来越大，CUBIC算法会造成更大的RTT时延！

而 BBR 通过检测 RTpro 和 BtlBw 来实现拥塞控制。什么是 RTprop 呢？这是链路的物理时延，因为 RTT 里含有报文在路由器队列里的排队时间、ACK 的延迟确认时间等。什么叫延迟确认呢？TCP 每个报文必须被确认，确认动作是通过接收端发送ACK报文实现的，但由于TCP和IP头部有40个字节，如果不携带数据只为发送ACK网络效率过低，所以会让独立的ACK报文等一等，看看有没有数据发的时候顺便带给对方，或者等等看多个ACK一起发。所以，可以用下列公式表示RTT与RTprop的差别：

RTT我们可以测量得出，RTprop呢，我们只需要找到瓶颈路由器队列为空时多次RTT测量的最小值即可：

而BtlBw全称是bottleneck bandwith，即瓶颈带宽，我们可以通过测量已发送但未ACK确认的飞行中字节除以飞行时间deliveryRate来测量：

早在1979年Leonard Kleinrock就提出了第1条竖线是最好的拥塞控制点，但被Jeffrey M. Jaffe证明不可能实现，因为没有办法判断RTT变化到底是不是因为链路变化了，从而不同的设备瓶颈导致的，还是瓶颈路由器上的其他TCP连接的流量发生了大的变化。但我们有了RTprop和BtlBw后，当RTprop升高时我们便得到了BtlBw，这便找到第1条灰色竖线最好的拥塞控制点，也有了后续发送速率的依据。

基于BBR算法，由于瓶颈路由器的队列为空，最直接的影响就是RTT大幅下降，可以看到下图中CUBIC红色线条的RTT比BBR要高很多：

而因为没有丢包，BBR传输速率也会有大幅提升，下图中插入的图为CDF累积概率分布函数，从CDF中可以很清晰的看到CUBIC下大部分连接的吞吐量都更低：

如果链路发生了切换，新的瓶颈带宽升大或者变小怎么办呢？BBR会尝试周期性的探测新的瓶颈带宽，这个周期值为1.25、0.75、1、1、1、1，如下所示：

1.25会使得BBR尝试发送更多的飞行中报文，而如果产生了队列积压，0.75则会释放队列。下图中是先以10Mbps的链路传输TCP，在第20秒网络切换到了更快的40Mbps链路，由于1.25的存在BBR很快发现了更大的带宽，而第40秒又切换回了10Mbps链路，2秒内由于RTT的快速增加BBR调低了发送速率，可以看到由于有了pacing_gain周期变换BBR工作得很好。

pacing_gain周期还有个优点，就是可以使多条初始速度不同的TCP链路快速的平均分享带宽，如下图所示，后启动的连接由于过高估计BDP产生队列积压，早先连接的BBR便会在数个周期内快速降低发送速率，最终由于不产生队列积压下RTT是一致的，故平衡时5条链路均分了带宽：

我们再来看看慢启动阶段，下图网络是10Mbps、40ms，因此未确认的飞行字节数应为10Mbps*0.04s=0.05MB。红色线条是CUBIC算法下已发送字节数，而蓝色是ACK已确认字节数，绿色则是BBR算法下的已发送字节数。显然，最初CUBIC与BBR算法相同，在0.25秒时飞行字节数显然远超过了0.05MB字节数，大约在 0.1MB字节数也就是2倍BDP：

大约在0.3秒时，CUBIC开始线性增加拥塞窗口，而到了0.5秒后BBR开始降低发送速率，即排空瓶颈路由器的拥塞队列，到0.75秒时飞行字节数调整到了BDP大小，这是最合适的发送速率。

当繁忙的网络出现大幅丢包时，BBR的表现也远好于CUBIC算法。下图中，丢包率从0.001%到50%时，可以看到绿色的BBR远好于红色的CUBIC。大约当丢包率到0.1%时，CUBIC由于不停的触发拥塞算法，所以吞吐量极速降到10Mbps只有原先的1/10，而BBR直到5%丢包率才出现明显的吞吐量下降。

CUBIC 造成瓶颈路由器的缓冲队列越来越满，RTT时延就会越来越大，而操作系统对三次握手的建立是有最大时间限制的，这导致建 CUBIC下的网络极端拥塞时，新连接很难建立成功，如下图中RTT中位数达到 100秒时 Windows便很难建立成功新连接，而200秒时Linux/Android也无法建立成功。

BBR 算法的伪代码如下，这里包括两个流程，收到ACK确认以及发送报文：

function onAck(packet) rtt = now - packet.sendtime update_min_filter(RTpropFilter, rtt) delivered += packet.size delivered_time = now deliveryRate = (delivered - packet.delivered) / (delivered_time - packet.delivered_time) if (deliveryRate > BtlBwFilter.currentMax || ! packet.app_limited) update_max_filter(BtlBwFilter, deliveryRate) if (app_limited_until > 0) app_limited_until = app_limited_until - packet.size 这里的app_limited_until是在允许发送时观察是否有发送任务决定的。发送报文时伪码为：

function send(packet) bdp = BtlBwFilter.currentMax × RTpropFilter.currentMin if (inflight >= cwnd_gain × bdp) // wait for ack or retransmission timeout return if (now >= nextSendTime) packet = nextPacketToSend() if (! packet) app_limited_until = inflight return packet.app_limited = (app_limited_until > 0) packet.sendtime = now packet.delivered = delivered packet.delivered_time = delivered_time ship(packet) nextSendTime = now + packet.size / (pacing_gain × BtlBwFilter.currentMax) timerCallbackAt(send, nextSendTime) pacing_gain便是决定链路速率调整的关键周期数组。

BBR算法对网络世界的拥塞控制有重大意义，尤其未来可以想见路由器的队列一定会越来越大。HTTP3放弃了TCP协议，这意味着它需要在应用层 (各框架中间件）中基于BBR算法实现拥塞控制，所以，BBR算法其实离我们很近。理解BBR，我们便能更好的应对网络拥塞导致的性能问题，也会对未来的拥塞控制算法发展脉络更清晰。 ———————————————— 版权声明：本文为CSDN博主「陶辉」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/russell_tao/article/details/98723451

CUBIC

CUBIC是当前Linux系统上默认的拥塞控制算法。它的拥塞控制窗口增长函数是一个三次函数，这样设计的目的是为了在当前的快速和长距离网络环境中有更好的扩展性。CUBIC的拥塞窗口增长独立于RTT，因此能更好的保证流与流之间的公平性。

问题是什么 &emspp; 当今的因特网朝着速度更快，距离更长的趋势发展，致使针对传统网络设计的TCP算法性能受到了挑战。上面的网络特性用一个专业名词描述叫做高BDP (bandwidth and delay product），它代表了带宽被完全利用时网络中能容纳的数据包总量。   传统的TCP算法，例如TCP-Reno，TCP-NewReno，TCP-SACK等之所以在新环境下不能充分利用网络带宽，主要是因为在进入拥塞避免阶段后，它们的拥塞窗口每经过一个RTT才加1，拥塞窗口的增长速度太慢，当碰上高带宽环境时，可能需要经历很多个RTT，拥塞窗口才能接近于一个BDP。如果数据流很短，可能拥塞窗口还没增长到一个BDP，数据流就已经结束了，这种情况的带宽利用率就会非常低。

已存在的方法   为了解决上面提到的TCP低利用率问题，有很新的TCP变体被提出来，例如FAST，HSTCP，STCP，HTCP，SQRT，West-wood和BIC-TCP。这些算法都号称能在很短的时间内提高网络传输速率。在Linux内核2.6.8版本里，BIC-TCP被选为默认算法，其他算法也实施在Linux内核里作为可选项。BIC-TCP相比其他算法的优点是其稳定性。下面就花点篇幅介绍下BIC-TCP算法。

BIC-TCP   BIC-TCP采用二分搜索的方式来决定拥塞窗口的增长尺度，首先它会记录拥塞窗口的一个最大值点，这个最大值就是TCP最近一次出现丢包时拥塞窗口的值；还会记录一个最小值点，即在一个RTT周期内没有出现丢包事件时窗口的大小。二分搜索就是取最小值和最大值的中间点，当拥塞窗口增长到这个中间值且没有出现丢包的话，就说明网络还可以容纳更多的数据包。那么将这个中值设为新的最小值，在新的最小值和最大值间搜索中间值。当当前拥塞窗口的值还远没有达到通道的容量时，其增长速度很快；相反，当拥塞窗口的值接近于通道的容量时，其拥塞窗口增长函数是一个简化的对数凹函数。这个凹函数使拥塞窗口在饱和点或平衡点比凸函数或线性函数保持更长的时间，在饱和点处，凹函数和线性函数它们具有最大的窗口增量，因此在丢包发生时会出现大量的数据包被丢失。

  BIC-TCP的主要特征是在前面说过的其独特的窗口增长函数，图1给出了BIC-TCP的窗口增长函数。当出现丢包事件时，BIC-TCP通过乘以因子$\beta$来缩小窗口，缩小之前的窗口大小被设置为最大$W_max$，并且缩小之后的窗口大小被设置为最小值$W_min$。 然后，BIC-TCP使用这两个参数执行二分搜索，拥塞窗口的下一个取值会是$W_max$和$W_min$之间的“中点”$W_mid$。   为了防止拥塞窗口从$W_min$增长到$W_mid$的步长$step$太大，BIC-TCP还设置了一个常数$S_max$，当$step$>$S_max$时，BIC-TCP会取下一个增长点为$W_min$+$S_max$而不是$W_mid$，如果没有出现丢包的话，再更新$W_min$，直到$step$<$S_max$为止。与此同时BIC-TCP还设置一个另一个控制参数$S_min$，当窗口增量小于$S_min$时，BIC-TCP会将当前拥塞窗口值设为最大值。   如果窗口增长超过最大值，则说明当前窗口最大值还不是一个饱和点，网络还可以容纳更多的数据包，窗口还有增长的空间，一个新的窗口最大值需要被探索。于是BIC-TCP会进入一个新的阶段，叫做最大值探索阶段。最大探测使用一个与在加法增长和二分搜索阶段 (这是对数;其倒数将是指数）完全对称的窗口增长函数。图1中给出了在最大探索阶段期间的窗口增长函数。在最大探测期间，窗口最初缓慢地增长以发现附近新的最大值，经过一段时间的缓慢增长，如果没有找到新的最大值 (即，没出现包丢失），则它猜测新的最大值离得很远，所以它给窗口大小增加一个大的固定增量，使用加法增加切换到更快的增加速度。BIC-TCP的良好性能来自$W_max$附近的缓慢增加和在加法增加和最大探测期间的线性增加。

什么是CUBIC   CUBIC是BIC-TCP的下一代版本。 它通过用三次函数 (包含凹和凸部分）代替BIC-TCP的凹凸窗口生长部分，大大简化了BIC-TCP的窗口调整算法。实际上，任何奇数阶多项式函数都具有这种形状。三次函数的选择是偶然的，并且不方便。CUBIC的关键特征是其窗口增长仅取决于两个连续拥塞事件之间的时间。一个拥塞事件是指出现TCP快速恢复的时间。因此，窗口增长与RTT无关。 这个特性允许CUBIC流在同一个瓶颈中竞争，有相同的窗口大小，而不依赖于它们的RTT，从而获得良好的RTT公平性。而且，当RTT较短时，由于窗口增长率是固定的，其增长速度可能比TCP标准慢。 由于TCP标准 (例如，TCP-SACK）在短RTT下工作良好，因此该特征增强了协议的TCP友好性。

CUBIC的窗口增长函数   BIC-TCP在高速网络中实现了良好的可扩展性，在自身的竞争流之间是公平的，并且具有低窗口振荡的稳定性。但BIC-TCP的窗口增长函数对于TCP来说还是过于激进，特别是在短RTT或低速网络中。于是有了CUBIC，CUBIC保留了BIC-TCP的稳定性和可扩展性的优点，同时简化了窗口控制和加强了TCP友好性。

  CUBIC的窗口增长函数是一个三次函数，非常类似于BIC-TCP的窗口增长函数，CUBIC的函数图像如图2所示。CUBIC的详细运行过程如下，当出现丢包事件时，CUBIC同BIC-TCP一样，会记录这时的拥塞窗口大小作为$W_max$，接着通过因子$\beta$执行拥塞窗口的乘法减小，这里$\beta$是一个窗口降低常数，并进行正常的TCP快速恢复和重传。从快速恢复阶段进入拥塞避免后，使用三次函数的凹轮廓增加窗口。三次函数被设置在$W_max$处达到稳定点，然后使用三次函数的凸轮廓开始探索新的最大窗口，如果新的最大窗口存在的话。   CUBIC的窗口增长函数公式如下所示： $$W(t)=C(t-K)^3+W_max \quad (1)$$ 这里，C是一个CUBIC的参数，t是从窗口上次降低开始到现在的时间，是一个弹性值，而K是上述函数在没有进一步丢包的情况下将$W$增加到$W_max$经历的时间，其计算公式如下： $$K=\sqrt[3]{\frac{W_max*\beta}{C}} \quad (2)$$ 在拥塞避免阶段每收到一个ACK，CUBIC都会使用方程 (1）计算在下个RTT的窗口增长速率。CUBIC使用$W(t+RTT)$作为拥塞窗口的候选值，假设当前拥塞窗口大小为$cwnd$。根据$cwnd$的值，CUBIC有三种运行模式。首先，如果cwnd小于 (标准）TCP在上次丢包事件之后t时刻到达的窗口大小，那么CUBIC处于TCP模式 (我们将在下面描述如何根据时间确定标准TCP的窗口大小）。否则，如果$cwnd$小于$W_max$，那么CUBIC在三次函数的凹轮廓区域，如果$cwnd$大于$W_max$，那么，CUBIC处于三次函数的凸轮廓区域。

TCP友好型区域   这小节主要说了怎么判断在发生丢包事件后，标准TCP在$t$时刻的窗口大小。

凹区域   当在拥塞避免阶段收到一个ACK，如果协议不处于TCP模式，且$cwnd$小于$W_max$，那么，协议就处于凹区域，在这个区域，$cwnd$的增量为 $$\frac{W(t+RTT)-cwnd}{cwnd}$$

凸区域   如果协议不处于TCP模式，且$cwnd$大于饱和点$W_max$，那么协议处于凸区域，$cwnd$的增量为 $$\frac{W(t+RTT)-cwnd}{cwnd}$$ 其实凸区域的增长函数和凹区域的增长函数一样，只不过凸区域越过了饱和点，而其区域没有越过饱和点。

乘法降低   当出现数据包丢失时，CUBIC会通过乘以因子$\beta$来降低拥塞窗口，这里取$\beta=0.2$，设置$\beta$小于0.5的副作用是收敛较慢。虽然更适应性的设置会导致更快的收敛，但是会使协议的分析变得更加困难，并影响协议的稳定性。

快速收敛   为了提高CUBIC的收敛速度，在协议中加入了启发式。当新的流量加入网络时，网络中的现有流量需要放弃其带宽份额，以使新流量有一定的增长空间。下面详细描述一下快速收敛的过程。在发生丢包前，CUBIC会记录一个最大窗口值$W_max$，当发生丢包后，在降低窗口前，CUBIC又会记录当前的窗口值作为新的$W_max$，为了不至于混淆，可以将之前记录的$W_max$标记位$W_lastmax$。当发生丢包时，CUBIC会比较$W_lastmax$的$W_max$大小，如果$W_max$小于$W_lastmax$，这表明由于可用带宽的变化，该流所经历的饱和点正在降低。这种情况下，CUBIC的做法是通过进一步的减小$W_max$来释放更多的可用带宽。

https://allen-kevin.github.io/2017/12/21/TCP%E6%8B%A5%E5%A1%9E%E6%8E%A7%E5%88%B6%E4%B9%8BCUBIC/