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延时策略来进行控制的，但是这类算法在发包速率上可能不够激进，竞争性能不如其他算法，因此在共享网络带宽时有失公平性，但是算法速率曲线却是很平滑。