理解 BBR 拥塞控制算法--理论篇

Published at 2021-05-30 | Last Update 2021-05-30

简介

BBR (Bottleneck Bandwidth and Round-trip propagation time)是 Google 在 2016 年发布的一套拥塞控制算法。它尤其适合在存在一定丢包率的弱网环境下使用，在这类环境下，BBR 的性能远超 CUBIC 等传统的拥塞控制算法。

以下是 Google 公开的的一些资料

本文将帮助你理解 BBR。

使用 BBR

没有比展示效果更适合作为开篇的了。

这里使用 iperf 来测试两个主机之间的 TCP 传输性能。tc 工具可以模拟传输时延和丢包率。

tc qdisc add dev eth0 root netem loss 1% latency 25ms

下面这是一些测试结果

可以看到，在存在丢包的场景下，BBR 的性能远远强于 CUBIC.

网络拥塞与控制

网络中的数通设备(交换机路由器)在入方向通常都会有缓存入报文的队列，其目的是为了应付短时间内涌入的大量报文。但如果入方向的报文持续超负荷，缓存队列也一定会被填满，此后的报文就只能被无情丢弃，之后发送端便能感知到报文丢了。

可以把网络链路想象为一根水管，路径上的数通设备会自带一个蓄水池，一般不会使用。而当水流变大时，蓄水池开始蓄水，如果超过蓄水极限，则水流会溢出(报文丢包)。

当发送端感知到丢包时，传统的 TCP 拥塞控制算法会减小发送端的拥塞窗口 Cwnd，限制报文的发送。这类拥塞控制算法也被称为基于丢包(Loss-based)的拥塞控制算法。

这显然不是最好的时机! 因为使用缓存队列并不能提升整个链路的带宽，反而还会增大报文的 RTT (每个报文的排队时间变长了)。缓存队列只是应急区域，平时是不应该被使用的。

BBR 的设计思路

控制时机提前，不再等到丢包时再进行暴力限制，而是控制稳定的发包速度，尽量榨干带宽，却又不让报文在中间设备的缓存队列上累积。

为了得到稳定的发包速度，BBR 使用 TCP Pacing 进行发包控制，因此 BBR 的实现也需要底层支持 TCP Pacing; 为了榨干带宽，BBR 会周期性地去探测是否链路条件变好了，如果是，则加大发送速率; 为了不让报文在中间设备的缓存队列上累积，BBR 会周期性地探测链路的最小 RTT，并使用该最小 RTT 计算发包速率。

BBR 理论基础

下图是来自 BBR paper 里的一张经典设计图

这张图分为上下两部分：上半部分的 Y 轴是 RTT，下半部分的 Y 轴则表示 delivery rate (也就是 estimated bandwidth)。特别注意的是 X 轴不是时间，而是 amount inflight，也就是在途报文的数量。

整个图从左到右可分为 3 个区域：1. app limited, 2. bandwidth limited, 3. buffer limited

1. app limited

这个区域中，这条流上流量较小，没有充分利用信道，不存在阻塞的情况，delivery rate 线性增加，因此 RTT 保持不变，为链路的固有往返时延(RTprop)。

1. bandwidth limited

这个区域表示 inflight 报文数量超过了 BDP，超过的部分是被中间设备缓存，最终表现出来就是 delivery rate 不变(只跟 bandwidth 有关)，而 RTT 由于中间设备缓存 queue 的存在而线性增加。

1. buffer limited

inflight 报文数量继续增加，超过 BDP 的部分最终也超过了中间设备的缓存极限，出现丢包。

BBR 追求的目标是保持 inflight 报文数量就为 BDP，这样既充分利用了 bandwidth，每个报文又能享受到 RTprop。

尽管 bandwith 和 RTT 都是可测量的，但很遗憾的是它们不能被同时探测！

BBR 采用的方案是分时探测，即在不同的状态下探测 bandwidth 和 RTT。

BBR 状态机

采用 BBR 进行拥塞控制的流在任一时刻都是处于以下四个状态之一：Startup、Drain、Probe Bandwidth 和 Probe RTT。其中 Probe Bandwidth 属于稳态，其他三个状态都是暂态。

下面四个状态的转移图：

              |
              V
     +---> STARTUP  ----+
     |        |         |
     |        V         |
     |      DRAIN   ----+
     |        |         |
     |        V         |
     +---> PROBE_BW ----+
     |      ^    |      |
     |      |    |      |
     |      +----+      |
     |                  |
     +---- PROBE_RTT <--+

Startup & Drain

Startup 是 BBR 控制的流启动时的状态，为了能尽快找到链路的瓶颈带宽 BtlBw，处于 Startup 状态的流每一个 RTT 会将报文发送速率会提高一倍。指数增长的发送速率使得 inflight 报文快速增加，也使得 delivery rate 快速增加，从而 BBR 计算的 bandwith 也快速增加。

随着 inflight 越过 BDP 这条线，delivery rate 不再变化，此时 BBR 测量到的 bandwidth 也会达到峰值。当 BBR 看到测量到的 bandwidth 连续 3 个 RTT 不再显著增长时(增长幅度小于 25%)，变会退出 Startup 状态，进入 Drain 状态。

Drain 状态的目标是让 inflight 报文数量回到 BDP 的水平，其存在的意义是为了抵消掉在 Startup 状态后期向网络灌入的超量报文。

随后，该流会进入 Probe Bandwidth 状态

Probe Bandwidth 状态

Probe Bandwidth 是四个状态中唯一的稳态，也是持续时间最长的状态 (大概 98% 的时间)。

在此状态下，BBR 会不断的去探测(或者说是压榨)带宽。

BBR 定义了一个增益循环(gain cycling)的概念，将增益系数作用到 pacing rate 上，以此控制报文发送速度。

具体的定义是，一个 cycle 包含 8 个 phase，每个 phase 的持续时间为 1 个 min RTT。8 个 phase 的 gain 分别为：1.25、0.75、1、1、1、1、1、1。当处于 gain 为 1.25 的 phase 时，意味着 pacing rate 是当前计算的合理值的 1.25 倍，此时 BBR 发送速率也会变成正常情况下的 1.25 倍(踩油门)。而当处于 gain 为 0.75 的 phase 时，相应的发送速率是正常情况的 0.75 倍(踩刹车)。而 gain 为 1 时，发送速率就是正常值(巡航).