2016年12月1日
第14卷，第5期

BBR：基于拥塞的拥塞控制

测量瓶颈带宽和往返传播时间

Neal Cardwell, Yuchung Cheng, C. Stephen Gunn, Soheil Hassas Yeganeh, Van Jacobson

大家普遍认为，当今的互联网数据传输效率不如预期。世界上大多数蜂窝网络用户都经历着秒级甚至分钟级的延迟；机场和会议场所的公共 Wi-Fi 情况通常更糟。物理学和气候研究人员需要与全球合作者交换拍字节级的数据，但他们发现精心设计的多 Gbps 基础设施在洲际距离上的传输速率通常只有几 Mbps。⁶

这些问题源于 20 世纪 80 年代创建 TCP 拥塞控制时做出的设计选择——将数据包丢失解释为“拥塞”。¹³ 这种等价在当时是成立的，但那是由于技术限制，而不是第一性原理。随着网卡（网络接口控制器）从 Mbps 发展到 Gbps，内存芯片从 KB 发展到 GB，数据包丢失和拥塞之间的关系变得越来越薄弱。

如今，基于丢包的 TCP 拥塞控制——即使是目前最先进的 CUBIC¹¹——也是这些问题的主要原因。当瓶颈缓冲区很大时，基于丢包的拥塞控制会使其保持充满状态，从而导致缓冲区膨胀。当瓶颈缓冲区很小时，基于丢包的拥塞控制会将丢包误解为拥塞信号，从而导致吞吐量降低。解决这些问题需要一种替代基于丢包的拥塞控制的方法。找到这种替代方案需要了解网络拥塞的起源和方式。

拥塞与瓶颈

在任何时候，一个（全双工）TCP 连接在每个方向上都恰好有一个最慢的链路或瓶颈。瓶颈之所以重要，是因为

• 它决定了连接的最大数据传输速率。这是不可压缩流的一般属性（例如，想象一条六车道高速公路在高峰时段发生事故，导致一小段路变成单车道。事故上游的交通速度不会超过该车道的交通速度）。

• 持久队列在此处形成。只有当链路的离开速率超过其到达速率时，队列才会缩小。对于以最大传输速率运行的连接，瓶颈上游的所有链路都具有更快的离开速率，因此它们的队列会迁移到瓶颈。

无论连接穿越多少链路或它们的个别速度如何，从 TCP 的角度来看，任意复杂的路径都表现为具有相同 RTT（往返时间）和瓶颈速率的单个链路。两个物理约束，RTprop（往返传播时间）和 BtlBw（瓶颈带宽），限制了传输性能。（如果网络路径是一根物理管道，RTprop 将是其长度，而 BtlBw 将是其最小直径。）

图 1 显示了 RTT 和传输速率随在途数据量（已发送但尚未确认的数据）的变化。蓝线显示 RTprop 约束，绿线显示 BtlBw 约束，红线显示瓶颈缓冲区。阴影区域中的操作是不可能的，因为它至少违反了一个约束。约束之间的转换导致三个不同的区域（应用受限、带宽受限和缓冲区受限），它们具有性质上不同的行为。

BBR: Congestion-Based Congestion Control

当在途数据不足以填满管道时，RTprop 决定行为；否则，BtlBw 占主导地位。约束线在 inflight = BtlBw × RTprop 处相交，即管道的 BDP（带宽-延迟乘积）。由于管道在超过此点的位置已满，inflight - BDP 的超额部分会在瓶颈处创建一个队列，这导致 RTT 对在途数据的线性依赖性，如上图所示。当超额部分超过缓冲区容量时，数据包会被丢弃。拥塞只是持续在 BDP 线右侧运行，而拥塞控制是一些方案，用于限制连接平均运行在右侧多远。

基于丢包的拥塞控制在带宽受限区域的右边缘运行，以高延迟和频繁丢包为代价，提供完整的瓶颈带宽。当内存昂贵时，缓冲区大小仅略大于 BDP，这最大限度地减少了基于丢包的拥塞控制的额外延迟。随后的内存价格下降导致缓冲区比 ISP 链路 BDP 大几个数量级，由此产生的缓冲区膨胀导致 RTT 达到秒而不是毫秒。⁹

带宽受限区域的左边缘比右边缘是更好的运行点。1979 年，Leonard Kleinrock¹⁶ 表明，此运行点是最佳的，既最大化了传输带宽，又最小化了延迟和丢包，无论对于单个连接还是对于整个网络⁸ 都是如此。不幸的是，大约在同一时间，Jeffrey M. Jaffe¹⁴ 证明，不可能创建一个分布式算法来收敛到此运行点。此结果改变了研究方向，从寻找一种实现 Kleinrock 最佳运行点的分布式算法，转向研究拥塞控制的不同方法。

我们在 Google 的团队每天花费数小时检查来自世界各地的 TCP 数据包头捕获，理解行为异常和病态。我们通常的第一步是找到基本路径特征，RTprop 和 BtlBw。可以从跟踪中推断出这些特征表明，Jaffe 的结果可能不像曾经看起来那样具有限制性。他的结果基于基本测量歧义（例如，测量的 RTT 增加是由路径长度变化、瓶颈带宽减少还是来自另一个连接的流量的排队延迟增加引起的）。虽然不可能消除任何单个测量的歧义，但连接随时间推移的行为讲述了一个更清晰的故事，暗示了旨在解决歧义的测量策略的可能性。

将这些测量与使用最新控制系统进展¹² 的稳健伺服回路相结合，可能会产生一种分布式拥塞控制协议，该协议对实际拥塞（而不是数据包丢失或瞬态队列延迟）做出反应，并以高概率收敛到 Kleinrock 的最佳运行点。因此，我们开始了为期三年的探索，以创建一个基于测量表征路径的两个参数的拥塞控制：瓶颈带宽和往返传播时间，即 BBR。

表征瓶颈

当（速率平衡）瓶颈数据包到达速率等于 BtlBw 且（满管道）在途数据总量等于 BDP（= BtlBw × RTprop）时，连接以最高吞吐量和最低延迟运行。

第一个条件保证瓶颈可以 100% 利用率运行。第二个条件保证有足够的数据来防止瓶颈饥饿，但不会过度填充管道。仅速率平衡条件不能确保没有队列，只能确保队列大小不会改变（例如，如果连接开始时将其 10 个数据包的初始窗口发送到 5 个数据包的 BDP 中，然后以完全瓶颈速率运行，则 10 个初始数据包中的 5 个填满管道，因此超额部分在瓶颈处形成一个无法消散的常设队列）。同样，满管道条件也不能保证没有队列（例如，以 BDP/2 突发发送 BDP 的连接获得完整的瓶颈利用率，但平均队列为 BDP/4）。最小化瓶颈和沿路径所有位置队列的唯一方法是同时满足这两个条件。

BtlBw 和 RTprop 在连接的生命周期内会发生变化，因此必须持续估算它们。TCP 当前跟踪 RTT（从发送数据包到收到确认的时间间隔），因为这是丢包检测所必需的。在任何时间 t，

其中 𝛈 ≥ 0 表示路径上队列、接收器的延迟确认策略、确认聚合等引入的“噪声”。RTprop 是连接路径的物理属性，仅在路径更改时才更改。由于路径更改发生在 » RTprop 的时间尺度上，因此在时间 T 的无偏、有效估计器是

（即，在时间窗口 W_R 内的运行最小值（通常为数十秒到数分钟）。

与 RTT 不同，TCP 规范中没有任何内容要求实现跟踪瓶颈带宽，但通过跟踪传输速率可以得到一个好的估计。当某个数据包的确认到达发送方时，它会传达该数据包的 RTT，并宣布在该数据包离开时在途数据的传输。发送和确认之间的平均传输速率是已传输数据与经过时间的比率：deliveryRate = Δdelivered/Δt。此速率必须 ≤ 瓶颈速率（到达量是精确已知的，因此所有不确定性都在 Δt 中，它必须 ≥ 真实到达间隔；因此，该比率必须 ≤ 真实传输速率，而真实传输速率又受瓶颈容量的上限限制）。因此，传输速率的窗口最大值是 BtlBw 的有效、无偏估计器

其中时间窗口 W_B 通常为六到十个 RTT。

TCP 必须记录每个数据包的离开时间才能计算 RTT。BBR 通过记录已传输的总数据来增强该记录，因此每个确认到达都会产生 RTT 和传输速率测量值，过滤器会将这些测量值转换为 RTprop 和 BtlBw 估计值。

请注意，这些值是完全独立的：RTprop 可以更改（例如，在路由更改时）但仍然具有相同的瓶颈，或者 BtlBw 可以更改（例如，当无线链路更改速率时）而路径不更改。（这种独立性是为什么必须知道这两个约束才能使发送行为与传输路径匹配的原因。）由于 RTprop 仅在图 1 中 BDP 的左侧可见，而 BtlBw 仅在右侧可见，因此它们遵循不确定性原理：每当可以测量其中一个时，就无法测量另一个。直观地看，这是因为管道必须过度填充才能找到其容量，这会创建一个队列，从而掩盖管道的长度。例如，运行请求/响应协议的应用程序可能永远不会发送足够的数据来填满管道并观察 BtlBw。一个持续数小时的大容量数据传输可能在其整个生命周期中都处于带宽受限区域，并且仅从第一个数据包的 RTT 中获得 RTprop 的单个样本。这种内在的不确定性意味着，除了用于恢复两个路径参数的估计器之外，还必须有状态来跟踪在当前运行点可以学习到的内容，以及随着信息变得陈旧，如何到达可以重新学习它的运行点。

使数据包流与传输路径匹配

核心 BBR 算法包含两个部分

当收到确认时

每个确认都提供新的 RTT 和平均传输速率测量值，这些测量值会更新 RTprop 和 BtlBw 估计值

函数 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

if 检查解决了上一段中描述的不确定性问题：发送方可能是应用受限的，这意味着应用程序耗尽了数据来填充网络。这在请求/响应流量中非常常见。当有发送机会但没有数据要发送时，BBR 会将相应的带宽样本标记为应用受限（请参阅下面 send() 伪代码）。此处的代码决定将哪些样本包含在带宽模型中，以便它反映网络限制，而不是应用程序限制。BtlBw 是传输速率的硬性上限，因此测量的传输速率大于当前的 BtlBw 估计值必然意味着估计值太低，无论样本是否受应用限制。否则，应用受限的样本将被丢弃。（图 1 显示，在应用受限区域中，deliveryRate 低估了 BtlBw。这些检查防止用低估值填充 BtlBw 过滤器，这会导致数据发送速度过慢。）

当发送数据时

为了使数据包到达速率与瓶颈链路的离开速率相匹配，BBR 对每个数据包进行步调调整。（BBR 必须匹配瓶颈速率，这意味着步调调整是设计的组成部分，也是运行的基础——pacing_rate 是 BBR 的主要控制参数。辅助参数 cwnd_gain 将在途数据量限制为 BDP 的一个小倍数，以处理常见的网络和接收器病态（请参阅后面关于延迟和拉伸确认的部分）。从概念上讲，TCP 发送例程看起来像以下代码。（在 Linux 中，发送使用高效的 FQ/步调队列规则⁴，这为 BBR 在多千兆位链路上提供了线速单连接性能，并以可忽略不计的 CPU 开销处理数千个较低速率的步调连接。）

函数 send(packet) bdp = BtlBwFilter.currentMax × RTpropFilter.currentMin if (inflight >= cwnd_gain × bdp) // 等待确认或重传超时 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)

稳态行为

BBR 发送的速率和数量完全取决于估计的 BtlBw 和 RTprop，因此过滤器除了估计瓶颈约束外，还控制自适应。这创建了图 2 中所示的新型控制回路，该图说明了 10-Mbps、40-ms 流的 700 毫秒的 RTT（蓝色）、在途数据量（绿色）和传输速率（红色）详细信息。传输速率数据上方的粗灰线是 BtlBw 最大滤波器的状态。三角形结构是由 BBR 循环 pacing_gain 以确定 BtlBw 是否增加而产生的。用于循环每个部分的增益与影响它的数据时间对齐显示。增益在 RTT 之前应用，即在发送数据时应用。这由左侧向上运行的事件序列描述中的水平偏移指示。

BBR 通过花费大部分时间在途一个 BDP 来最小化延迟，并以 BtlBw 估计值进行步调调整。这会将瓶颈移动到发送方，使其无法观察到 BtlBw 的增加。因此，BBR 定期花费一个 RTprop 间隔，pacing_gain > 1，这会增加发送速率和在途数据量。如果 BtlBw 没有改变，则会在瓶颈处创建一个队列，增加 RTT，从而保持 deliveryRate 恒定。（此队列通过在下一个 RTprop 中以补偿 pacing_gain < 1 发送来消除。）如果 BtlBw 增加，deliveryRate 增加，新的最大值立即增加 BtlBw 过滤器输出，从而增加基本步调速率。因此，BBR 以指数级快速收敛到新的瓶颈速率。图 3 显示了在稳态运行 20 秒后 BtlBw 突然加倍到 20 Mbps（左图），然后在 20 Mbps 稳态运行 20 秒后降至 10 Mbps（右图）对 10-Mbps、40-ms 流的影响。

（BBR 是 Max-plus 控制系统的一个简单实例，这是一种基于非标准代数的新型控制方法。¹² 这种方法允许自适应速率[由最大增益控制]独立于队列增长[由平均增益控制]。应用于此问题，它产生了一个简单的隐式控制回路，其中对物理约束变化的适应由表示这些约束的滤波器自动处理。传统的控制系统将需要多个循环，这些循环通过复杂的状态机连接以完成相同的结果。）

单个 BBR 流启动行为

现有的实现使用特定于事件的算法和许多行代码来处理启动、关闭和丢包恢复等事件。BBR 对所有事情都使用前面（在上一节“使数据包流与传输路径匹配”中）详细介绍的代码，通过遍历一组“状态”来处理事件，这些“状态”由包含一个或多个固定增益和退出标准表定义。大部分时间都花在“稳态行为”部分中描述的 ProbeBW 状态。Startup 和 Drain 状态在连接启动时使用（图 4）。为了处理跨越 12 个数量级的互联网链路带宽，Startup 通过使用 2/ln2 的增益来加倍发送速率，同时传输速率正在增加，从而实现 BtlBw 的二分查找。这在 log₂BDP RTT 中发现 BtlBw，但在此过程中创建了高达 2BDP 的超额队列。一旦 Startup 找到 BtlBw，BBR 就会转换为 Drain，它使用 Startup 增益的倒数来消除超额队列，然后在在途数据量降至 BDP 后转换为 ProbeBW。

图 4 显示了 10-Mbps、40-ms BBR 流的第一个秒。时间/序列图显示了发送方（绿色）和接收方（蓝色）随时间的进度。红线显示了在相同条件下 CUBIC 发送方。垂直灰线标记 BBR 状态转换。下图显示了两个连接的 RTT 与时间的关系。请注意，此数据的时基是确认到达（蓝色），因此，虽然它们看起来是时间偏移的，但事件显示在 BBR 了解它们并采取行动的点。

图 4 的下图对比了 BBR 和 CUBIC。它们的初始行为相似，但 BBR 完全排空了其启动队列，而 CUBIC 则不能。在没有路径模型告诉它有多少在途数据是超额的情况下，CUBIC 使在途数据量的增长不那么激进，但增长会一直持续到瓶颈缓冲区填满并丢弃数据包，或者达到接收器的在途数据量限制（TCP 的接收窗口）。

图 5 显示了图 4 所示连接的前八秒的 RTT 行为。CUBIC（红色）填满了可用缓冲区，然后每隔几秒钟在 70% 到 100% 之间循环。启动后，BBR（绿色）在基本没有队列的情况下运行。

多个 BBR 流共享瓶颈的行为

图 6 显示了共享 100-Mbps/10-ms 瓶颈的几个 BBR 流的个别吞吐量如何收敛到公平份额。向下三角形结构是连接 ProbeRTT 状态，其自同步加速了最终收敛。

ProbeBW 增益循环（图 2）导致较大的流将带宽让给较小的流，从而使每个流学习其公平份额。这种情况发生得相当快（几个 ProbeBW 周期），尽管当后启动者由于在其他流（暂时）创建队列时启动而高估 RTprop 时，不公平现象可能会持续存在。

为了学习真实的 RTProp，流使用 ProbeRTT 状态移动到 BDP 的左侧：当 RTProp 估计值在许多秒内未更新（即，通过测量较低的 RTT）时，BBR 进入 ProbeRTT，这会将在途数据量减少到四个数据包至少一个往返，然后返回到之前的状态。进入 ProbeRTT 的大型流会从队列中排空许多数据包，因此多个流会看到新的 RTprop（新的最小 RTT）。这使得它们的 RTprop 估计值在同一时间到期，因此它们一起进入 ProbeRTT，这使得总队列下降更大，并导致更多流看到新的 RTprop，依此类推。这种分布式协调是公平性和稳定性的关键。

BBR 将流同步到空瓶颈队列的理想事件周围。相比之下，基于丢包的拥塞控制将同步到周期性队列增长和溢出的不良事件周围，从而放大延迟和数据包丢失。

Google B4 WAN 部署经验

Google 的 B4 网络是一个使用商用交换机构建的高速 WAN（广域网）。¹⁵ 这些浅缓冲区交换机上的丢包主要来自小流量突发的巧合到达。2015 年，Google 开始将 B4 生产流量从 CUBIC 切换到 BBR。没有遇到任何问题或回归，自 2016 年以来，所有 B4 TCP 流量都使用 BBR。图 7 显示了切换的原因之一：BBR 的吞吐量始终比 CUBIC 高 2 到 25 倍。我们原本预计会有更大的改进，但发现 75% 的 BBR 连接受到内核 TCP 接收缓冲区的限制，网络运营团队故意将接收缓冲区设置得很低 (8 MB)，以防止 CUBIC 用数兆字节的超额在途数据量淹没网络（8-MB/200-ms 洲际 RTT ⇒ 335-Mbps 最大吞吐量）。在一个美国-欧洲路径上手动提高接收缓冲区导致 BBR 立即达到 2 Gbps，而 CUBIC 仍然保持在 15 Mbps——Mathis 等人¹⁷ 预测的 133 倍相对改进。

图 7 显示了 BBR 与 CUBIC 的相对吞吐量改进；插图显示了吞吐量 CDF（累积分布函数）。测量来自一个主动探测器服务，该服务打开到远程数据中心的持久 BBR 和 CUBIC 连接，然后每分钟传输 8 MB 数据。探测器通过北美、欧洲和亚洲境内和之间的许多 B4 路径进行通信。

巨大的改进是 BBR 不使用丢包作为拥塞指标的直接结果。为了实现完整带宽，现有的基于丢包的拥塞控制要求丢包率低于 BDP¹⁷ 的平方倒数（例如，对于 10-Gbps/100-ms 路径，每 3000 万个数据包丢包少于一个）。图 8 比较了在各种丢包率下测量的良好吞吐量。CUBIC 的丢包容忍度是算法的结构属性，而 BBR 的丢包容忍度是配置参数。随着 BBR 的丢包率接近 ProbeBW 峰值增益，测量真实 BtlBw 传输速率的概率急剧下降，导致最大过滤器低估。

图 8 显示了在 100-Mbps/100-ms 链路上以 0.001% 到 50% 的随机丢包率进行 60 秒流的 BBR 与 CUBIC 的良好吞吐量。CUBIC 的吞吐量在 0.1% 的丢包率下下降了 10 倍，并在 1% 以上的丢包率下完全停滞。最大可能的吞吐量是链路速率乘以已传输的分数（= 1 - lossRate）。BBR 在高达 5% 的丢包率下满足此限制，并在高达 15% 的丢包率下接近此限制。

YouTube 边缘部署经验

BBR 正在 Google.com 和 YouTube 视频服务器上部署。Google 正在进行小规模实验，其中一小部分用户被随机分配到 BBR 或 CUBIC。使用 BBR 的播放显示 YouTube 的所有体验质量指标都有显着改进，这可能是因为 BBR 的行为更加一致和可预测。BBR 仅略微提高了连接吞吐量，因为 YouTube 已经将服务器的流媒体速率调整到远低于 BtlBw，以最大限度地减少缓冲区膨胀和重新缓冲事件。即便如此，BBR 将全球范围内的中位数 RTT 平均降低了 53%，在发展中国家降低了 80% 以上。

图 9 显示了来自一周内在五大洲测量的超过 2 亿次 YouTube 播放连接的 BBR 与 CUBIC 中位数 RTT 改进。全球 70 亿移动互联网用户中，超过一半的用户通过 8- 到 114-kbps 的 2.5G 系统连接，⁵ 这些系统由于基于丢包的拥塞控制的缓冲区填充倾向而遭受了广为人知的问题。³ 这些系统的瓶颈链路通常在 SGSN （服务 GPRS 支持节点）¹⁸ 和移动设备之间。SGSN 软件在具有充足内存的标准 PC 平台上运行，因此在互联网和移动设备之间经常有兆字节的缓冲区。图 10 比较了 BBR 和 CUBIC 的（模拟）SGSN 互联网到移动设备的延迟。水平线标记了更严重的后果之一：TCP 适应长 RTT 延迟，除非在连接启动 SYN 数据包上，该数据包具有操作系统相关的固定超时。当移动设备通过大型缓冲 SGSN 接收大容量数据（例如，来自自动应用程序更新）时，在队列清空之前（SYN ACK 接受数据包的延迟时间超过固定的 SYN 超时），设备无法连接到互联网上的任何内容。

图 10 显示了在 128-Kbps/40-ms 链路上，具有八个 BBR（绿色）或 CUBIC（红色）流的稳态中位数 RTT 随链路缓冲区大小的变化。BBR 使队列保持在接近最小值，独立于瓶颈缓冲区大小和活动流的数量。CUBIC 流始终填满缓冲区，因此延迟随缓冲区大小线性增长。

移动蜂窝自适应带宽

蜂窝系统部分基于使用针对用户的队列数据包的需求估计来调整每用户带宽。早期版本的 BBR 被调整为创建非常小的队列，导致连接卡在低速率上。将峰值 ProbeBW pacing_gain 提高以创建更大的队列导致卡住的连接更少，这表明对某些网络来说可能过于友好。使用当前的 1.25 × BtlBw 峰值增益，在任何网络上与 CUBIC 相比，都没有明显的性能下降。

延迟和拉伸确认

蜂窝、Wi-Fi 和有线宽带网络通常会延迟和聚合确认。¹ 当在途数据量限制为一个 BDP 时，这会导致降低吞吐量的停顿。将 ProbeBW 的 cwnd_gain 提高到 2 允许 BBR 以估计的传输速率平稳地继续发送，即使确认延迟长达一个 RTT。这在很大程度上避免了停顿。

令牌桶策略器

BBR 最初的 YouTube 部署揭示，世界上大多数 ISP 都使用令牌桶策略器来篡改流量。⁷ 令牌桶通常在连接启动时是满的，因此 BBR 学习底层网络的 BtlBw，但一旦令牌桶为空，所有发送速度快于（远低于 BtlBw）令牌桶填充速率的数据包都会被丢弃。BBR 最终会学习到这个新的传输速率，但 ProbeBW 增益循环会导致持续的适度丢包。为了最大限度地减少这些丢包造成的上游带宽浪费和应用程序延迟增加，我们向 BBR 添加了策略器检测和显式策略器模型。我们还在积极研究更好的方法来减轻策略器造成的损害。

与基于丢包的拥塞控制的竞争

无论是与其他 BBR 流竞争还是与基于丢包的拥塞控制竞争，BBR 都会收敛到瓶颈带宽的公平份额。即使基于丢包的拥塞控制填满了可用缓冲区，ProbeBW 仍然可以稳健地将 BtlBw 估计值移向流的公平份额，而 ProbeRTT 找到一个 RTProp 估计值，该估计值刚好足够高，可以进行针锋相对地收敛到公平份额。然而，超过几个 BDP 的未管理路由器缓冲区会导致长期存在的基于丢包的竞争者膨胀队列并抢占超过其公平份额的带宽。减轻这种情况是另一个积极研究的领域。

结论

重新思考拥塞控制带来了巨大的回报。BBR 没有使用诸如丢包或缓冲区占用率等仅与拥塞微弱相关的事件，而是从 Kleinrock 的拥塞形式模型及其相关的最佳运行点开始。通过观察到延迟和带宽的关键参数可以顺序估计，从而规避了延迟和带宽的关键参数无法同时确定的令人讨厌的“不可能”结果。然后，使用控制和估计理论的最新进展来创建一个简单的分布式控制回路，该回路接近最优，充分利用网络，同时保持小队列。Google 的 BBR 实现已在开源 Linux 内核 TCP 中提供，并在本文的附录中详细描述。

BBR 已部署在 Google 的 B4 骨干网上，与 CUBIC 相比，吞吐量提高了几个数量级。它还在 Google 和 YouTube Web 服务器上部署，大大减少了迄今为止测试过的五大洲的延迟，尤其是在发展中地区。BBR 纯粹在发送方运行，不需要更改协议、接收方或网络，使其可以逐步部署。它仅依赖于 RTT 和数据包传输确认，因此可以为大多数互联网传输协议实现。

可以通过 [email protected] 联系作者。

致谢

作者感谢 Len Kleinrock 指出拥塞控制的正确方法。我们感谢 Larry Brakmo 在 Vegas² 和 New Vegas 拥塞控制方面的开创性工作，这些工作预示了 BBR 的许多要素，以及在 BBR 早期开发期间的建议和指导。我们还要感谢 Eric Dumazet、Nandita Dukkipati、Jana Iyengar、Ian Swett、M. Fitz Nowlan、David Wetherall、Leonidas Kontothanassis、Amin Vahdat 以及 Google BwE 和 YouTube 基础设施团队的宝贵帮助和支持。

附录 - 详细描述

用于顺序探测的状态机

pacing_gain 控制数据包相对于 BtlBw 的发送速度，是 BBR 学习能力的关键。pacing_gain > 1 会增加在途数据量并减少数据包到达间隔时间，从而将连接向图 1 的右侧移动。pacing_gain < 1 具有相反的效果，将连接向左移动。

BBR 使用此 pacing_gain 来实现一个简单的顺序探测状态机，该状态机在测试更高的带宽，然后测试更低的往返时间之间交替。（没有必要探测更低的带宽，因为 BtlBw 最大滤波器会自动处理：新的测量值反映了下降，因此一旦最后一个旧测量值超时，BtlBw 就会自行纠正。RTprop 最小滤波器也会自动处理路径长度的增加。）

如果瓶颈带宽增加，BBR 必须发送得更快才能发现这一点。同样，如果实际的往返传播延迟发生变化，这将改变 BDP，因此 BBR 必须发送得更慢才能使在途数据量低于 BDP，以便测量新的 RTprop。因此，发现这些变化的唯一方法是进行实验，发送得更快以检查 BtlBw 是否增加，或发送得更慢以检查 RTprop 是否减少。这些实验的频率、幅度、持续时间和结构因已知的信息（启动或稳态）和发送应用程序行为（间歇性或连续性）而异。

稳态行为

BBR 流大部分时间处于 ProbeBW 状态，使用一种称为增益循环的方法来探测带宽，这有助于 BBR 流实现高吞吐量、低排队延迟，并收敛到带宽的公平份额。通过增益循环，BBR 循环使用 pacing_gain 的一系列值。它使用一个八阶段循环，pacing_gain 值如下：5/4、3/4、1、1、1、1、1、1。每个阶段通常持续估计的 RTprop 时间。这种设计允许增益循环首先使用高于 1.0 的 pacing_gain 来探测更多带宽，然后使用一个与 1.0 相等距离之下的 pacing_gain 来耗尽任何由此产生的队列，然后使用 1.0 的 pacing_gain 在短队列中巡航。所有阶段的平均增益为 1.0，因为 ProbeBW 的目标是使其平均 pacing 速率等于可用带宽，从而保持高利用率，同时保持一个小的、良好限制的队列。请注意，虽然增益循环会改变 pacing_gain 值，但 cwnd_gain 始终保持为 2，因为延迟和拉伸的 ACK 可能随时发生（请参阅关于延迟和拉伸 ACK 的部分）。

此外，为了提高混合和公平性，并减少多个 BBR 流共享瓶颈时的队列，BBR 通过在进入 ProbeBW 时随机选择一个初始阶段（除了 3/4 阶段之外的所有阶段）来随机化 ProbeBW 增益循环的阶段。为什么不从 3/4 开始循环？3/4 pacing_gain 的主要优点是耗尽当管道已经满时，运行 5/4 pacing_gain 可能创建的任何队列。当退出 Drain 或 ProbeRTT 并进入 ProbeBW 时，没有队列需要耗尽，因此 3/4 增益不提供该优势。在这些情况下使用 3/4 只有一个成本：该轮的链路利用率为 3/4 而不是 1。由于从 3/4 开始会有成本但没有好处，并且由于进入 ProbeBW 发生在任何足够长的连接的开始，以便有 Drain 阶段，因此 BBR 使用了这个小的优化。

BBR 流协同工作，使用称为 ProbeRTT 的状态定期耗尽瓶颈队列。在 ProbeRTT 自身以外的任何状态下，如果 RTProp 估计值超过 10 秒未更新（即，通过获得更低的 RTT 测量值），则 BBR 进入 ProbeRTT 并将 cwnd 减少到一个非常小的值（四个数据包）。在保持飞行中的最小数据包数量至少 200 毫秒和一个往返时间后，BBR 离开 ProbeRTT 并转换到 Startup 或 ProbeBW，具体取决于它是否估计管道已经填满。

BBR 的设计目标是将其绝大部分时间（约 98%）花费在 ProbeBW 中，其余时间花费在 ProbeRTT 中，这是基于一系列权衡。ProbeRTT 持续足够长的时间（至少 200 毫秒），以允许具有不同 RTT 的流具有重叠的 ProbeRTT 状态，同时仍然足够短，以将 ProbeRTT 的 cwnd 限制对性能的损失大致限制在 2%（200 毫秒/10 秒）。RTprop 滤波器窗口（10 秒）足够短，以便在流量水平或路由发生变化时能够快速收敛，但又足够长，以便交互式应用程序（例如，网页、远程过程调用、视频块）通常在窗口内具有自然的静默或低速率时段，在这些时段内，流的速率足够低或持续时间足够长，以耗尽其在瓶颈中的队列。然后，RTprop 滤波器会伺机拾取这些 RTprop 测量值，并且 RTProp 会刷新，而无需 ProbeRTT。这样，只有当多个批量流在整个 RTProp 窗口中繁忙发送时，流通常才需要支付 2% 的损失。

启动行为

当 BBR 流启动时，它会执行其第一次（也是最快速的）顺序探测/耗尽过程。网络链路带宽跨越 10¹² 的范围——从几比特到 100 千兆比特每秒。为了了解 BtlBw，考虑到需要探索的巨大范围，BBR 对速率空间进行二分搜索。这可以非常快速地找到 BtlBw（log₂BDP 个往返时间），但代价是在搜索的最后一步创建 2BDP 队列。BBR 的 Startup 状态执行此搜索，然后 Drain 状态耗尽由此产生的队列。

首先，Startup 以指数方式增长发送速率，每轮加倍。为了以尽可能平滑的方式实现这种快速探测，在 Startup 状态下，pacing_gain 和 cwnd_gain 被设置为 2/ln2，这是允许发送速率每轮加倍的最小值。一旦管道已满，cwnd_gain 将队列限制为 (cwnd_gain - 1) × BDP。

在 Startup 期间，BBR 通过查找 BtlBw 估计值的平台期来估计管道是否已满。如果它注意到在若干轮（三轮）中，尝试使交付速率加倍实际上导致很少的增加（小于 25%），则它估计它已达到 BtlBw 并退出 Startup 并进入 Drain。BBR 等待三轮，以便有确凿的证据表明发送方没有检测到由接收窗口暂时施加的交付速率平台期。允许三轮为接收方的接收窗口自动调整打开接收窗口，以及 BBR 发送方意识到 BtlBw 应该更高提供时间：在第一轮中，接收窗口自动调整算法增长接收窗口；在第二轮中，发送方填充更高的接收窗口；在第三轮中，发送方获得更高的交付速率样本。这个三轮阈值已通过 YouTube 实验数据验证。

在 Drain 状态下，BBR 旨在通过切换到与 Startup 期间使用的值相反的 pacing_gain 来快速耗尽 Startup 中创建的任何队列，这会在一轮中耗尽队列。当飞行中的数据包数量与估计的 BDP 匹配时，这意味着 BBR 估计队列已完全耗尽但管道仍然已满，则 BBR 离开 Drain 并进入 ProbeBW。

请注意，BBR 的 Startup 和 CUBIC 的慢启动都以指数方式探索瓶颈容量，每轮将其发送速率加倍；然而，它们在主要方面有所不同。首先，BBR 在发现可用带宽方面更稳健，因为它不会在数据包丢失或（如 CUBIC 的 Hystart¹⁰ 中那样）延迟增加时退出搜索。其次，BBR 平滑地加速其发送速率，而在每一轮中，CUBIC（即使使用 pacing）也会发送突发的数据包，然后强加一段静默间隙。图 4 展示了 BBR 和 CUBIC 的飞行中数据包数量和在每次确认中观察到的 RTT。

对瞬态的反应

网络路径和在其上传输的流量可能会发生突然的剧烈变化。为了平滑而稳健地适应这些变化，并减少这种情况下的数据包丢失，BBR 使用了许多策略来实现核心模型。首先，BBR 将 cwnd_gain×BDP 视为当前 cwnd 从下方谨慎接近的目标，在任何时候 cwnd 的增加量不超过确认的数据量。其次，在发生重传超时时，这意味着发送方认为所有飞行中的数据包都丢失了，BBR 会保守地将 cwnd 减少到一个数据包并发送一个数据包（就像基于丢失的拥塞控制算法（如 CUBIC）一样）。最后，当发送方检测到数据包丢失但仍有数据包在飞行中时，在丢失修复过程的第一轮中，BBR 会暂时降低发送速率以匹配当前的交付速率；在丢失修复过程的第二轮及以后的轮次中，它确保发送速率永远不会超过当前交付速率的两倍。当 BBR 遇到策略器或在 BDP 规模的缓冲区上与其他流竞争时，这会显着减少瞬态丢失。

参考文献

1. Abrahamsson, M. 2015. TCP ACK suppression. IETF AQM mailing list; https://www.ietf.org/mail-archive/web/aqm/current/msg01480.html.

2. Brakmo, L. S., Peterson, L.L. 1995. TCP Vegas: end-to-end congestion avoidance on a global Internet. IEEE Journal on Selected Areas in Communications 13(8): 1465-1480.

3. Chakravorty, R., Cartwright, J., Pratt, I. 2002. Practical experience with TCP over GPRS. In IEEE GLOBECOM.

4. Corbet, J. 2013. TSO sizing and the FQ scheduler. LWN.net; https://lwn.net/Articles/564978/.

5. Ericsson. 2015 Ericsson Mobility Report (June); https://www.ericsson.com/res/docs/2015/ericsson-mobility-report-june-2015.pdf.

6. ESnet. Application tuning to optimize international astronomy workflow from NERSC to LFI-DPC at INAF-OATs; http://fasterdata.es.net/data-transfer-tools/case-studies/nersc-astronomy/.

7. Flach, T., Papageorge, P., Terzis, A., Pedrosa, L., Cheng, Y., Karim, T., Katz-Bassett, E., Govindan, R. 2016. An Internet-wide analysis of traffic policing. In SIGCOMM: 468-482.

8. Gail, R., Kleinrock, L. 1981. An invariant property of computer network power. In Conference Record, International Conference on Communications: 63.1.1-63.1.5.

9. Gettys, J., Nichols, K. 2011. Bufferbloat: dark buffers in the Internet. acmqueue 9(11); https://queue.org.cn/detail.cfm?id=2071893.

10. Ha, S., Rhee, I. 2011. Taming the elephants: new TCP slow start. Computer Networks 55(9): 2092-2110.

11. Ha, S., Rhee, I., Xu, L. 2008. CUBIC: a new TCP-friendly high-speed TCP variant. SIGOPS Operating Systems Review 42(5): 64-74.

12. Heidergott, B., Olsder, G. J., Van Der Woude, J. 2014. Max Plus at Work: Modeling and Analysis of Synchronized Systems: a Course on Max-Plus Algebra and its Applications. Princeton University Press.

13. Jacobson, V. 1988. Congestion avoidance and control. SIGCOMM Computer Communication Review 18(4): 314-329.

14. Jaffe, J. 1981. Flow control power is nondecentralizable. IEEE Transactions on Communications 29(9): 1301-1306.

15. Jain, S., Kumar, A., Mandal, S., Ong, J., Poutievski, L., Singh, A., Venkata, S., Wanderer, J., Zhou, J., Zhu, M., et al. 2013. B4: experience with a globally-deployed software defined WAN. SIGCOMM Computer Communication Review 43(4): 3-14.

16. Kleinrock, L. 1979. Power and deterministic rules of thumb for probabilistic problems in computer communications. In Conference Record, International Conference on Communications: 43.1.1-43.1.10.

17. Mathis, M., Semke, J., Mahdavi, J., Ott, T. 1997. The macroscopic behavior of the TCP congestion avoidance algorithm. SIGCOMM Computer Communication Review 27(3): 67-82.

18. Wikipedia. GPRS core network serving GPRS support node; https://en.wikipedia.org/wiki/GPRS_core_network#Serving_GPRS_support_node_.28SGSN.29.

发送方缓冲区和多媒体自适应的案例
Aiman Erbad 和 Charles "Buck" Krasic
https://queue.org.cn/detail.cfm?id=2381998

关于网络性能，你一窍不通
Kevin Fall 和 Steve McCanne
https://queue.org.cn/detail.cfm?id=1066069

数据中心网络漫游指南
Dennis Abts 和 Bob Felderman
https://queue.org.cn/detail.cfm?id=2208919

作者是 Google 的 make-tcp-fast 项目的成员，该项目的目标是通过基础研究和开源软件来发展互联网传输。项目贡献包括 TFO (TCP Fast Open)、TLP (Tail Loss Probe)、RACK 丢包恢复、fq/pacing 以及过去五年对 Linux 内核 TCP 代码的大部分 git 提交。

最初发表于 Queue 杂志第 14 卷，第 5 期—
在数字图书馆中评论本文

更多相关文章

David Collier-Brown - 关于带宽，你一窍不通
当您的员工或客户说他们的互联网性能很差时，带宽可能不是问题。一旦他们拥有 50 到 100 Mbps 范围内的带宽，问题就是延迟，即 ISP 的路由器处理他们的流量需要多长时间。如果您是一家 ISP 并且您的所有客户都讨厌您，请振作起来。现在这是一个可以解决的问题，这要归功于一群敬业的人，他们找到了这个问题，解决了它，然后在家庭路由器中验证了他们的解决方案。

Geoffrey H. Cooper - 使用 FDO 和不受信任的安装程序模型的设备入职
设备的自动入职是处理正在安装的越来越多的“边缘”和 IoT 设备的重要技术。设备的入职与大多数设备管理功能不同，因为设备的信任从工厂和供应链转移到目标应用程序。为了通过自动入职来加速该过程，必须在设备中形式化供应链中的信任关系，以允许自动化过渡。

Brian Eaton, Jeff Stewart, Jon Tedesco, N. Cihan Tas - 通过关键路径追踪的分布式延迟分析
低延迟是许多 Google 应用程序（如搜索）的重要功能，延迟分析工具在保持大规模低延迟方面发挥着关键作用。对于包含功能和数据不断发展的服务的复杂分布式系统，将总体延迟保持在最低水平是一项具有挑战性的任务。在大型、真实的分布式系统中，现有的工具（如 RPC 遥测、CPU 性能分析和分布式跟踪）对于理解整个系统的子组件很有价值，但不足以在实践中执行端到端延迟分析。

David Crawshaw - 一切 VPN 焕然一新
VPN（虚拟专用网络）已有 24 年历史。这个概念是为与我们今天所知的互联网截然不同的互联网而创建的。随着互联网的增长和变化，VPN 用户和应用程序也随之发展。VPN 在 2000 年代的互联网中经历了尴尬的青春期，与其他广泛流行的抽象概念交互不佳。在过去的十年中，互联网再次发生了变化，这个新的互联网为 VPN 提供了新的用途。一种全新的协议 WireGuard 的开发提供了一种技术，可以在其上构建这些新的 VPN。