BBR拥塞控制
谷歌在2016年提出了基于拥塞的BBR(Bottleneck Bandwidth and Round-trip propagation time的缩写)拥塞控制算法,随后各路大佬对该算法进行了深度的分析,本文从原理、性能测试、源码实现、应用场景4个角度,全面分析BBR拥塞控制算法。
简介
拥塞控制的目标是最大化利用网络上链路的带宽(当然,还有其他的目的如平竞争、降低网络延时)。那怎么判断网络链路到达瓶颈了呢?在BBR之前,主流的拥塞控制算法(如reno, fast tcp, cubic等拥塞控制算法)使用丢包这个指标来评估。在硬件技术受限的年代,网络设备的缓存通常只有几KB,当发生拥塞时,网络设备无法缓存大量数据包,只能丢弃,此时可以了解为拥塞即丢包。
但随着硬件技术的发展,特别是缓存技术的发展,网络设备的缓存从KB升级到GB,拥塞时,网络数据包首先进入缓存队列等待,长时间的拥塞才会导致缓存溢出、丢包,可见,出现丢包与拥塞的映射时延变成,基于丢包的拥塞控制算法将导致缓存队列大量占用,数据包往返时延增加。
另外,网络中,除了拥塞导致的丢包外,设备损害、环境干扰等其他因素也可能导致丢包,基于丢包的拥塞控制算法在这种环境中可能导致误判,最终导致网络带宽利用率低。
BBR 致力于解决上述两个问题:
减少网络设备的缓存队列的占用率,降低数据包往返时延;
在有一定丢包率的网络链路中,充分利用网络带宽。
BBR 原理
那BBR是通过什么办法解决上述两个问题的呢?
降低时延方案:网络时延包括传播时延、缓存时延、处理时延等,BBR的目标是降低数据包在网络中缓存队列的排队时延,即降低缓存队列的占用率。BBR只发送通过瓶颈带宽(BtlBW)x传播时延(RTprop)获得整个网络链路本身(缓存队列为空时)容纳数据包数量到网络中,而不是整个网络(包含缓存队列)能够容纳数据包的数量到网络中,进而降低缓存队列占用率,减轻缓存膨胀(如下图所示)效应,进而降低时延;
一定丢包率网络中,充分利用带宽方案:不再使用丢包估计带宽,而是直接使用一定时间内回复的ACK计算瓶颈带宽,即rate=ack_num/t。
缓存膨胀(BufferBloat)是指:当网络拥塞发生时,网络设备缓存了过多的数据包,以试图阻止数据包丢失,但最终导致数据包时延增加、吞吐量减少的现象。
如下图所示,展示了数据包往返时延(Round-Trip Time, 即RTT)、数据包投递速率(delivery rate,链路真实吞吐量)与网络链路中数据包数量(amount infight)之间的关系。
RTT:包括传播时延(RTprop, 受传播距离、传播速率等影响)、排队时延(W)、转发时延等。当发送到网络中的数据包较少时,缓存队列无积压,
RTT ~= RTprop
,随着网络链路中数据包的增加,缓存队列(队列深度记作L)不断积压,则RTT = RTprop + W
,其中排队时延W = L/BtlBW
,BtlBW为瓶颈带宽(Bottleneck Bandwidth),即网络链路中最小的带宽。当缓存队列满时,此时RTT达到最大值RTT= RTprop + Max_L/BtlBW
;Delivery Rate: 一次发送到网络中的数据包越多,投递速率(Delivery Rate)(瓶颈吞吐量)越大,直到达到网络的最大容量(网络的最大处理能力,BtlBW),再增加投递数据包数量将不再增大投递速率,反而,由于网络处理不过来这么多数据包,将积压在缓存队列中,增加排队时延。
上图来自 Google 的BBR论文
可见,问题的关键是必须算出可以发送多少数据包到网络链路中,显然,这个值的理论最优解为RTprop*BtlBW
,即为带宽时延乘积(BDP, Bandwidth Delay Product)。通常,基于丢包的拥塞控制策略将使得BDP偏于上图的右边界。BBR的目的是让BDP尽量靠近上图中的第一条灰线处。
事实上, RTprop 与 BtlBw 是动态变化的,需要周期性计算。并且RTprop 与 BtlBw 就像粒子的位置与动量,无法同时测准。
BBR使用包含4个阶段的状态机,交替测量 RTprop 与 BtlBw,用一段时间窗口中带宽的极大值和时延的最小值作为 BtlBw 与 RTprop的估计值。
BBR状态机
BBR状态机制中包含4个状态,分别为:STARTUP、DRAIN、PROBE_BW、PROBE_RTT
,每当接收到ACK时,就调用 BBR 算法计算 BtlBw 与 RTprop :
-BtlBw = windowed_max(delivered / elapsed, 10 round trips)
: 10 个往返下(ACK)最大接收吞吐量;
RTprop = windowed_min(rtt, 10 seconds)
: 10s 内,最小 rtt。
图片来自腾讯技术文章“万字详文:TCP 拥塞控制详解”
STARTUP:初始状态,该状态下类似于传统拥塞控制的慢启动阶段。该状态下pacing_gain和cwnd_gain为 2/ln(2)+1。因为这是最小能平衡达到 Reno 或者 CUBIC 算法启动速度的值。
DRAIN :该状态为排除状态。在 STARTUP 状态下三轮没有涨幅超过 25%时会进入该状态。该状态下 BtlBw 会根据 bbr_drain_gain 逐渐降低,直到 inflight 数据包数量降到 BDP 为止。
PROBE_BW :该状态下会照常计算当前的 bw,即瞬时带宽。然而在计算 pacing rate 以及 cwnd 时,并不会像在 STARTUP 状态时那样用一个很大的增益系数去扩张 pacing rate 和 cwnd,而是顺序的在
[5/4,3/4,1,1,1,1,1,1]
中选一个,感官上 bw 就在其停止增长的地方上下徘徊了。PROBE_RTT :当 PROBE_BW 检测到连续 10s 没有更新 min rtt 时就会进入该状态。该状态的目标是保持 BBR 的公平性并定期排空瓶颈队列,以收敛到真实的 min_rtt。进入该模式时,BBR 会将 cwnd 的上限设置为 4 个数据包。在 flight pkg <= 4 后开始进行 rtt 探测,探测时间为 200ms,探测结束后 BBR 便会记录 min rtt,并离开 PROBE_RTT 进入相应的模式:1)若 吞吐量没有到达 BDP 带宽,则进入STARTUP 阶段;2)吞吐量大于 BDP 带宽,则进入 PROBE_BW 阶段。
测量 RTprop
数据包在网络中的传输时延 RTprop 链路的物理特性,只有路径发生变化时才会改变,但受各种因素的影响,如缓存队列、延时ACK确认机制等,其永远测不准。BBR算法在上图中的第一条灰线前的状态下测量RTprop,这个状态下没有数据包缓存,计算的数据包RTT即为RTprop。当然,实际中,很难达到上述状态,通常取一个时间窗口中所有RTT的最小值作为RTprop,公式如下:
其中,WR为时间窗口大小,一般设置为几十秒至几分钟。
测量 BtlBw
BBR将所有状态测量的最大接收吞吐量做为瓶颈带宽(BtlBw ),测量公式如下:
在稳态情况下(PROBE_BW),BBR会周期性增加发送吞吐量,试探链路的瓶颈带宽,若大于TODO
为获得网络中缓存队列的低占用率、高带宽利用率,通常,实际的数据包发送速率略小于(~1%)瓶颈带宽BtlBw。
源码分析
性能测试
单流下的表现
单流情况下,BBR表现如下图所示。假定刚开始时,网络链路的RTT为40ms,瓶颈带宽为10 Mbit/s。
图片来自:Towards a Deeper Understanding of BBR IFIP-Networking-2018-TCP-BBR
在此测试实验的前18秒,吞吐量每隔10s降低一次,这是因为BBR算法每隔10秒进入一次ProbRTT状态,在这个状态下,为获得较低的RTT时延,以估计出RTprop。
瓶颈带宽增加的响应
18秒时,瓶颈带宽增大2倍,变为20Mbit/s,此时若BBR处在带宽探测期,每个周期增加1/4吞吐量,3个周期后吞吐量增加1.25*1.25*1.25 = 1.95
倍。其中,每个周期是8个RTT,每周期按照 [5/4, 3/4, 1, 1, 1, 1, 1, 1] 倍的瓶颈带宽依次发送数据包, 一个RTT是40ms,一个带宽探测期是320ms。
可见,当瓶颈带宽增加时,只需要不到1秒钟BBR即可将发送吞吐量增加1倍。另外,缓存队列基本没有增加,所以RTT基保持稳定。
上图来自 Google 的BBR论文
瓶颈带宽降低的响应
BBR收到数据包ACK后,根据接收到的ACK的数量与投递时间计算发送方与接收方之间网络链路瓶颈带宽,然后作为下次发送的速率。当瓶颈带宽降低时,BBR收到的ACK就会减少,计算的瓶颈带宽就会立即减少。可见,当链路的瓶颈带宽降低时,BBR算法只需一个RTT就可以快速感应到。
多流下的表现
应用场景
BBR算法应该在Google自家World Area Network中早已投入使用。Google后来提出基于SDN的B4网络(paper叫做B4,很有名的一篇paper),其拥塞控制算法也是使用的BBR。
参考
附录
队列与时延关系
一个数据包在网络设备的转发时间为排队时间加上处理时延,其中排队时延latency计算方法如下:
拥塞控制简史
大约在1988年之前TCP/IP是没有拥塞控制的,入选计算机名人堂Internet Hall of Fame的Van Jacobson大神提出并设计实施了TCP/IP拥塞控制,解决了当时最大的问题。随后几十年间,拥塞控制算法不断优化、迭代,发展出了不同的版本。例如,基于丢包策略的传统拥塞控制算法,几个迭代版本如下图所示:
与此同时还有一类算法是基于RTT延时策略来进行控制的,但是这类算法在发包速率上可能不够激进,竞争性能不如其他算法,因此在共享网络带宽时有失公平性,但是算法速率曲线却是很平滑。
评论