文章

Google BBR拥塞控制算法原理

发表于
作者 Optimus-Xs
40 分钟阅读
Google BBR拥塞控制算法原理

BBR 基本介绍和发展背景

BBR 简介

Google 的 TCP BBR（Bottleneck Bandwidth and Round-trip propagation time）是一种基于模型的拥塞控制算法

它不依赖丢包信号，而是通过主动探测网络的最大瓶颈带宽 BtlBw（bottleneck bandwidth）和最小往返时延（RTT），建立一个显式的网络模型，并据此动态调整发送速率来最大化吞吐量和最小化延迟。BBR算法包含STARTUP、DRAIN、PROBE_BW和PROBE_RTT四个状态，在这些状态之间切换来持续地探索和维持最佳的发送速率

省流 (TLDR):

BBR 拥塞控制算法是由谷歌在2016年为了解决网络中的缓冲区膨胀（Bufferbloat）问题而发明的。

传统的拥塞控制算法（如CUBIC）主要依赖于丢包作为网络拥塞的信号。然而，在现代网络中，路由器往往拥有很大的缓冲区，这导致即使网络已经非常拥塞，数据包也不会立即被丢弃，而是被缓存起来，造成了严重的延迟。BBR旨在解决这个问题，它通过主动测量网络的最大瓶颈带宽（bottleneck bandwidth）和最小往返时延（RTT）来确定最佳的发送速率，从而在网络队列开始堆积时就进行控制，而不是等到发生丢包。

此外，BBR在长肥网络（long fat network，LFN: 高带宽、高延迟、有丢包的网络）中表现出色。在这些网络条件下，传统的拥塞控制算法会因丢包而大幅降低吞吐量，而BBR则能更有效地利用网络带宽，显著提升传输性能。这对于跨太平洋的大文件传输、视频流媒体（如YouTube）等应用尤其重要。

BBR算法思路类似于一款小游戏 Flappy Bird：

Flappy Bird

我们需要不断调整bird的飞行高度，但是过高过低震荡太多就很容易挂掉，所以如果能够平滑一些或许会飞得更远哦！

BBR 出现前的背景

在BBR 之前，主流的 TCP 拥塞控制算法都是基于丢包（loss-based）设计的， 这一假设最早可追溯到上世纪八九十年代，那时的链路带宽和内存容量分别以 Mbps 和 KB 计，链路质量（以今天的标准来说）也很差。

起初 aimd 挺好，为了更好，bic/cubic 相继出炉，此过程正与 linux 蓬勃发展同步，大概从 1990 年初一直持续到 2005 年前后，linux kernel 内置所谓 “拥塞状态机” 逻辑，以至于完全不同于传统 aimd 的 delay-based cc 比如 vegas 竟无处安放。

拥塞状态机其实就是 loss-based 的抽象，将 “拥塞避免”，“快速重传” 等这些状态与 tcp 语义的传输和重传强制捆绑，以至于只要出现丢包进入快速重传，必须无条件执行固定逻辑，比如降窗(比如 prr)。这种框架下，如果想在丢包时不降窗就无从谈起，显然 vegas 不适合这框架。但由于这种方式工作的足够好，vegas 几乎被遗忘。

三十年多后，这两个物理容量都已经增长了至少六个数量级，链路质量也不可同日而语。特别地，在现代基础设施中， 丢包和延迟不一定表示网络发生了拥塞，因此原来的假设已经不再成立。 Google 的网络团队从这一根本问题出发，（在前人工作的基础上） 设计并实现了一个基于拥塞本身而非基于丢包或延迟的拥塞控制新算法，缩写为 BBR。

简单来说，BBR 通过应答包（ACK）中的 RTT 信息和已发送字节数来计算 真实传输速率（delivery rate），然后根据后者来调节客户端接下来的 发送速率（sending rate），通过保持合理的 inflight 数据量来使 传输带宽最大、传输延迟最低。另外，它完全运行在发送端，无需协议、 接收端或网络的改动，因此落地相对容易。

Google 的全球广域网（B4）在 2016 年就已经将全部 TCP 流量从 CUBIC 切换到 BBR， 吞吐提升了 2~25 倍；在做了一些配置调优之后，甚至进一步提升到了 133 倍

Loss-Based 的缺陷

TCP 的设计缺陷 —— 20 世纪 80 年代设计 TCP 拥塞控制（congestion control） 时，认为丢包是发生了“拥塞”。 在当时的技术条件下我们可以这样认为，但它并非第一原则 （technology limitations, not first principles）。随着网卡从 Mbps 到 Gbps、 内存从 KB 到 GB，丢包和拥塞之间的关系也变得愈发微弱。

今天，TCP 那些基于丢包的拥塞控制（loss-based congestion control） —— 即使是目前其中最好的 CUBIC —— 是导致这些问题的主要原因。

链路瓶颈处的 buffer 很大时，这类算法会持续占满整个缓冲区，导致 bufferbloat； 链路瓶颈处的 buffer 很小时，这类算法又会误将丢包当作拥塞的信号，导致吞吐很低。 解决这些问题需要一种全新的方式，而这首先需要对以下两点有深入理解:

  • 拥塞会发生哪里（where）

    拥塞主要发生在网络设备的大缓冲区（large buffers）中，也称为“缓冲区膨胀”（Bufferbloat）问题。这些缓冲区存在于路由器、交换机等网络设备上，它们被设计用来临时存储数据包以应对网络流量波动。

  • 拥塞是如何发生的（how）

    现代网络的基础设施带宽越来越高，而传统的拥塞控制算法（如CUBIC）仍然主要依赖于丢包作为拥塞信号。当网络流量超过链路容量时，数据包不会立即被丢弃，而是首先在这些大缓冲区中排队。这导致:

    • 延迟增加: 数据包在缓冲区中排队会显著增加往返传输时间（RTT）。
    • 拥塞隐藏: 由于大缓冲区吸收了多余的流量，在很长一段时间内都不会发生丢包。这意味着传统的拥塞控制算法无法感知到网络已经拥塞，并继续以高发送速率传输数据，进一步加剧了缓冲区的拥塞和延迟。

拥塞不再仅仅表现为丢包，而更多地表现为延迟的持续增加，这种延迟是由于数据包在网络设备的大缓冲区中排队造成的。BBR算法正是为了解决这一问题，通过测量实际的瓶颈带宽和往返延迟来主动控制发送速率，从而避免缓冲区膨胀，实现更高的吞吐量和更低的延迟。

Loss-Based 拥塞控制算法在现代的生产网络环境下的缺陷

  • 丢包即拥塞: 现实中网络环境很复杂会存在错误丢包，很多算法无法很好区分拥塞丢包和错误丢包，因此在存在一定错误丢包的前提下在某些网络场景中并不能充分利用带宽。
  • 无法应对“缓冲区膨胀”问题: 现代网络设备（如路由器）拥有越来越大的缓冲区。基于丢包的算法只有在缓冲区被填满，导致数据包开始丢失时才会意识到拥塞。在此之前，数据包会在缓冲区中大量排队，导致往返传输时间（RTT）持续增加，从而引入高延迟，即所谓的“缓冲区膨胀”（Bufferbloat）问题。
  • 无法实现最佳性能: 最佳的拥塞控制工作点是在不产生持久队列和丢包的情况下，最大化吞吐量并最小化延迟。而基于丢包的算法为了维持高吞吐量，必须将缓冲区填满，并依赖于丢包来感知拥塞，这与最佳工作点背道而驰。
  • 在有轻微丢包的网络中表现不佳: 对于某些网络（如无线网络）来说，丢包可能由信号不稳定等非拥塞原因引起。基于丢包的算法会错误地将这些丢包理解为拥塞，从而降低发送速率，导致吞吐量下降。
  • 网络负载高但无丢包事件: 假设网络中的负载已经很高了，只要没有丢包事件出现，算法就不会主动减窗降低发送速率，这种情况下虽然充分利用了网络带宽，同时由于一直没有丢包事件出现发送方仍然在加窗，表现出了较强的网络带宽侵略性，加重了网络负载压力。
  • 高负载丢包: 高负载无丢包情况下算法一直加窗，这样可以预测丢包事件可能很快就出现了，一旦丢包出现窗口将呈现乘性减少，由高位发送速率迅速降低会造成整个网络的瞬时抖动性，总体呈现较大的锯齿状波动。

基于丢包的算法的根本缺陷在于，它们将“丢包”作为唯一的拥塞信号，而忽略了在现代网络环境中更为重要的拥塞信号——持续增加的延迟。这使得它们无法在保障高吞吐量的同时，维持低延迟。

BBR 组成部分

即时带宽的计算

算法基于最近出站数据分组的传输时间来计算一个实时的带宽 BtlBw (bottleneck bandwith，即瓶颈带宽)，这个值是后续所有计算的基准

bbr将会根据当前的即时带宽以及其所处的pipe状态来计算pacing rate以及cwnd(见下文)，后面我们会看到，这个即时带宽计算方法的突破式改进是bbr之所以简单且高效的根源。

bbr作为一个纯粹的拥塞控制算法，完全忽略了系统层面的TCP状态，计算带宽时它仅仅需要两个值就够了：

  1. 应答了多少数据，记为data_acked；
  2. 应答data_acked这么多数据所用的时间，记为delivery_elapsed。

只关注数据的大小，不关注数据的含义，比如data_acked的采集中，bbr根本不管某一个应答是重传后的ACK确认的，正常ACK确认的，还是说SACK确认的。bbr只关心被应答了多少！

这和TCP/IP网络模型是一致的，因为在中间链路上，路由器交换机们也不会去管这些数据包是重传的还是乱序的，然而拥塞也是在这些地方发生的，既然拥塞点都不关心数据的意义，TCP为什么要关注呢？反过来，我们看一下拥塞发生的原因，即数据量超过了路由器的带宽限制，利用这一点，只需要精心地控制发送的数据量就好了，完全不用管什么乱序，重传之类的。

当然这里意思仅指在拥塞控制算法中不用管这些，但这并不意味着它们是被放弃的，传输过程的其它的机制会关注的，比如SACK机制，RACK机制，RTO机制等。

测量交付速率 (Delivery Rate)

BBR 的即时速率不是直接通过发送方计算的，而是根据接收方返回的确认（ACK）来测量的。

  • 当发送方收到一个 ACK 时，它会记录两个信息：本次 ACK 确认的已交付数据量（data_acked），以及从发送第一个数据包到收到该 ACK 之间的时间差（delivery_elapsed）。
  • 交付速率的计算公式为：$ delivery\_rate = data\_acked / delivery\_elapsed $ 。
  • 这个delivery_elapsed是经过精心设计的，它取发送该批次数据所用时间和 ACK 返回所用时间中的最大值，以避免由于数据包聚合或发送延迟造成的测量误差。

Delivery Rate（交付速率）是用来估算瓶颈带宽 BtlBw 的一个关键指标, Delivery Rate 是一个瞬时值。它代表了在特定时间窗口内，网络实际交付数据的速率。每次发送方收到 ACK 时，都会计算一个新的交付速率样本。

估算瓶颈带宽 (BtlBw)

BBR 算法中的 BtlBw（瓶颈带宽） 估计是基于对交付速率（deliveryRate）的持续测量。它的核心思想是，网络路径的真实瓶颈带宽，是在某个时间窗口内观察到的最大交付速率。

BtlBw 的具体计算公式如下

$\widehat{BtlBw} = \max(\textit{deliveryRate}_t) \quad \forall t \in [T-W_B, T]$

  1. 持续测量： BBR 不断地测量数据包的实际交付速率。每当收到一个 ACK（确认）时，它都会计算出一个新的交付速率样本。
  2. 维护窗口： 算法会维护一个时间窗口（W_B），这个窗口通常是10个 RTT。
  3. 取最大值： 在这个时间窗口内，BBR 会从所有测量的交付速率样本中选取一个最大值作为当前的 BtlBw 估计值。

这种“取最大值”的策略是 BBR 算法的一个关键创新。它能确保算法：

  • 快速适应更高的带宽： 如果网络路径的瓶颈带宽突然增加（例如，从 Wi-Fi 切换到有线网络），BBR 能够迅速捕捉到更高的交付速率样本，并更新其 BtlBw 估计，从而立即利用新的带宽。
  • 忽略瞬时波动： 它不会因为瞬时拥塞或抖动导致的交付速率下降而轻易降低其带宽估计。

简单来说，BBR 认为网络路径的“管道”有多粗，是由它在一段时间内能达到的最大传输速度决定的

Delivery Rate计算案例

接下来我们看一下这个data_acked以及delivery_elapsed的采集是如何实现的

Delivery Rate Demo

上图中，我故意用了一个极端点的例子，在该例子中，我几乎都是使用的SACK，当X被SACK时，我们可以根据图示很容易算出从Delivered为7时的数据包被确认到X被确认为止，一共有 12-7=5个数据包被确认，即这段时间网络上清空了5个数据包！我们便很容易算出带宽值了。我的这个图示在解释带宽计算方法之外，还有一个目的，即说明bbr在计算带宽时是不关注数据包是否按序确认的，它只关注数量，即数据包被网络清空的数量。实实在在的计算，不猜Lost，不猜乱序，这些东西，再怎么猜也猜不准！

RTT的跟踪

bbr之所以可以获取非常高的带宽利用率，是因为它可以非常安全且豪放地探测到带宽的最大值以及rtt的最小值，这样计算出来的BDP就是目前为止TCP管道的最大容量。bbr的目标就是达到这个最大的容量！这个目标最终驱动了cwnd的计算。

BBR 算法跟踪 RTT 的方式与传统拥塞控制算法有所不同，它主要关注的是最小往返传播时间（RTprop），而不是简单的平均 RTT

BBR 算法通过以下方式来跟踪 RTT：

1.持续测量 RTT 样本： BBR 会持续地测量每个数据包发送到其确认（ACK）返回的往返时间，并将这些 RTT 值作为样本记录下来。

2.使用最小 RTT 过滤器： BBR 算法的核心思想之一是，真正的往返传播时间（RTprop）是网络路径上物理距离决定的最小延迟。任何由于缓冲区排队造成的延迟增加都会导致 RTT 变大。因此，BBR 会使用一个最小值过滤器来持续地跟踪最近一个时间窗口（通常是10秒）内测量到的最小 RTT 样本。这个最小值就是 BBR 对 RTprop 的估计。

3.进入 ProbeRTT 状态： 为了确保能探测到真正的最小 RTT，BBR 引入了一个特殊的ProbeRTT状态。

  • 当 BBR 发现其最小 RTT 估计值在一段时间内（比如10秒）没有被更新时，它会进入这个状态。
  • 在 ProbeRTT 状态下，BBR 会主动降低其发送速率，将正在传输的数据量（inflight data）减少到一个很小的量（例如4个数据包），以清空网络路径上的任何缓冲区排队。
  • 当缓冲区被清空后，BBR 就能测量到更接近真实 RTprop 的 RTT 值。然后它会更新其 RTprop 估计值，并退出 ProbeRTT 状态，重新进入带宽探测阶段。

具体的RTprop计算公式如下

$\widehat{RTprop} = RTprop + \min(\eta_t) = \min(RTT_t) \quad \forall t \in [T-W_R, T]$

BBR状态机的维持

BBR算法和CUBIC算法类似，也同样有几个过程: StartUp、Drain、Probe_BW、Probe_RTT，来看下这几个状态的迁移情况:

bbr 状态机

但是相比之前的所有拥塞控制算法，其革命性的改进在于bbr拥塞算法不再跟踪系统的TCP拥塞状态机，而旨在用统一的方式来应对pacing rate和cwnd的计算，不管当前TCP是处在Open状态还是处在Disorder状态，抑或已经在Recovery状态，换句话说，bbr算法感觉不到丢包，它能看到的就是BtlBw和RTT！

bbr的状态机转换的转换条件如下图

bbr 状态机切换条件

通过上述的状态机以及上一节的带宽计算方式，我们知道了bbr的工作方式：不断地基于当前带宽以及当前的增益系数计算pacing rate以及cwnd，以此2个结果作为拥塞控制算法的输出，在TCP连接的持续过程中，每收到一个ACK，都会计算即时的带宽，然后将结果反馈给bbr的pipe状态机，不断地调节增益系数，这就是bbr的全部

我们发现它是一个典型的封闭反馈系统，与TCP当前处于什么拥塞状态完全无关

这非常不同于之前的 Loss-Based 拥塞控制算法，在之前的算法中，我们发现拥塞算法内部是受外部的拥塞状态影响的，比如说在Recovery状态下，甚至都不会进入拥塞控制算法，在bbr进入内核之前，Linux使用PRR算法控制了Recovery状态的窗口调整，即便说这个时候网络已经恢复，TCP也无法发现，因为TCP的Recovery状态还未恢复到Open

STARTUP（启动）:

BBR的慢启动阶段类似于CUBIC的慢启动，同样是进行探测式加速区别在于BBR的慢启动使用 $ 2/ln2 $ 加速，过程中即使发生丢包也不会引起速率的降低，而是依据返回的确认数据包来判断带宽增长，直到带宽不再增长时就停止慢启动而进入下一个阶段，需要注意的是在寻找最大带宽的过程中产生了多余的 2BDP 的数据量

DRAIN（排空）:

排空阶段是为了把慢启动结束时多余的2BDP的数据量清空，此阶段发送速率开始下降，也就是单位时间发送的数据包数量在下降，直到 未确认的数据包数量 < BDP 时认为已经排空，也可以认为是RTT不再下降为止，排空阶段结束。

PROBE_BW（带宽探测）:

在网络出现拥塞后，该状态会保持一个比最大可用带宽稍低的速率，并通过周期性地降低发送速率来探测是否存在未被利用的带宽

此阶段发送方进入稳定状态进行数据的发送，由于网络带宽的变化要比RTT更为频繁，因此ProbeBW阶段也是BBR的主要阶段，在探测期中增加发包速率如果数据包ACK并没有受影响那么就继续增加，探测到带宽降低时也进行发包速率下降

PROBE_RTT（时延探测）:

前面三个过程在运行时都可能进入ProbeRTT阶段，当某个设定时间内都没有更新最小延时状态下开始降低数据包发送量，试图探测到更小的MinRTT，探测完成之后再根据最新数据来确定进入慢启动还是ProbeBW阶段

状态机切换过程案例

BBR 四个过程的示意图

曲线说明: 这两个坐标给出了10Mbps和40msRTT的网络环境下CUBIC和BBR的一个对比过程，在上面的图中蓝色表示接收者，红色表示CUBIC，绿色表示BBR，在下面的图中给出了对应上图过程中的RTT波动情况，红色代表CUBIC，绿色代表BBR。

不同状态的增益系数 G

上文已经呈现了关于STARTUP，DRAIN，PROBE_BW，PROBE_RTT的状态图以及些许细节，当时我指出这个状态图的目标是为了完成bbr的目标，即填满整个网络！在这个状态图看来，所有已知的东西就是当前的即时带宽，所有可以计算的东西就是增益系数，然后根据这两个元素就可以轻易计算出pacing rate和cwnd，是不是很简单呢？整体看来就是就是这么简单，但是从细节上看，不同的pipe状态中的增益系数的计算却是值得推敲的，以下是bbr处在各个状态时的增益系数

  • STARTUP: 2~3
  • DRAIN: pacing rate的增益系数为1000/2885，cwnd的增益系数为1000/2005+1。
  • PROBE_BW: 5/4，1，3/4，bbr在PROBE_BW期间会随机在这些增益系数之间选择当前的增益系数。
  • PROBE_RTT: 1。但是在探测RTT期间，为了防止丢包，cwnd会强制cut到最小值，即4个MSS。

我们可以看到，bbr并没有明确的所谓“降窗时刻”，一切都是按照状态机来的，期间丝毫不会理会TCP是否处在Open，Recovery等状态。在此前的拥塞控制算法中

除了Vegas等基于延时的算法会在计算得到的target cwnd小于当前cwnd时视为拥塞而在算法中降窗外，其它的所有基于丢包的算法中均是检测到丢包(RTO或者reordering个重复ACK)时降窗的

可悲的是，这个降窗过程并不受拥塞算法的控制，拥塞算法只能消极地给出一个ssthresh值，即降窗的目标，这显然是令人无助的！

输出 Pacing Rate 和 Cwnd

bbr的输出并不仅仅是一个cwnd，更重要的是pacing rate。在传统意义上，cwnd是TCP拥塞控制算法的唯一输出，但是它仅仅规定了当前的TCP最多可以发送多少数据，它并没有规定怎么把这么多数据发出去

在Linux的实现中，如果发出去这么多数据呢？简单而粗暴，突发！忽略接收端通告窗口的前提下，Linux会把cwnd一窗数据全部突发出去，而这往往会造成路由器的排队，在深队列的情况下，会测量出rtt剧烈地抖动。

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

pacing rate计算

使用时间窗口内(默认10轮采样)最大BtlBw。上一次采样的即时BtlBw，用它来在可能的情况下更新时间窗口内的BtlBw采样值集合。这次能否按照这个时间窗口内最大BtlBw发送数据呢？这样看当前的增益系数的值，设为G，那么

$ pacing\_rate = BtlBw*G $

pacing rate 的值就是 BtlBw 和 增益系数 G 的乘积

BBR 使用 pacing rate 来平滑地发送数据包。它不依赖于传统的 ACK 时钟，而是使用一个时钟来控制数据包的发送间隔，确保数据流不会以突发的形式涌入网络。这种平滑发送的方式是 BBR 避免“缓冲区膨胀”和保持低延迟的关键

cwnd 计算

至于说cwnd的计算可能要稍微复杂一点，但是也是可以理解的，我们知道，cwnd其实描述了一条网络管道(rwnd描述了接收端缓冲区)，因此cwnd其实就是这个管道的容量，也就是BDP(带宽延时积, Bandwidth-Delay Product)！

BDP是Bandwidth-Delay Product的缩写，可以翻译为带宽延时积

我们知道带宽的单位是bps(bit per second)，延时的单位是s，这样BDP的量纲单位就是bit，从而我们知道BDP就是衡量一段时间内链路的数据量的指标。这个可以形象理解为水管灌水问题，带宽就是水管的水流速度立方米/s，延时就是灌水时间单位s，二者乘积我们就可以知道当前水管内存储的水量了

在BBR算法中BDP的计算公式是

$ BDP = BtlBw × RTprop $

我们采用 $ BDP × G $ 就算出了cwnd，这里的G是cwnd的增益系数，与带宽增益系数含义一样，根据bbr的状态机来获取

BBR 将 cwnd 作为安全网或数据量限制。即使 pacing rate 允许发送更多数据，实际在途的数据量也不能超过 cwnd, 这主要有两个目的:

  • 防止过量发送： 在 BBR 探测更高带宽时（pacing_gain > 1），cwnd 限制可以防止发送过量数据，避免引起不必要的丢包。
  • 作为安全保障： 尤其是在网络路径条件恶劣或存在丢包时，cwnd 能够提供一个更保守的限制，防止网络崩溃。

在 BBR 中，pacing rate 是主要的、基于速率的控制机制，它决定了数据包的发送频率。而 cwnd 则是辅助的、基于数据量的限制机制，它确保在途数据总量不会超过一个合理的上限。

BBR的优势

  • 高吞吐量和低延迟: 相较于基于丢包的算法，BBR能够更有效地利用网络资源，从而提供更高的吞吐量和更低的延迟。
  • 不受丢包影响: BBR不依赖丢包信号，因此它能够更好地处理如Wi-Fi或现代网络接口中的高千兆速度所带来的大量丢包，而这些丢包可能并非由拥塞引起。

  • 广泛应用: 该算法已经应用在YouTube等服务中，并被集成到了Linux内核的4.9版本中，还支持QUIC协议。

    Linux 中的BBR实现:

参考

Bottom Layer Knowledge
Algorithm Network
本文由作者按照 CC BY 4.0 进行授权