BBR: 基于拥塞的拥塞控制

关键术语

RTT:  round-trip-time
RTprop:  round-trip propagation time 
BtlBw:  bottleneck bandwidth。 路径上最小带宽。
data in flight： data sent but not yet acknowledged
BDP: bandwidth-delay product . (BDP = BtlBw * RTprop)
pacing_gain:  控制发送速度的增益系数
cwnd_gain:  窗口增益，与BDP相乘，控制inflight数量
bufferbloat: 缓冲过满
bottleneck_bandwidth = windowed_max(deliverd / elaspsed, 10 round trips)
min_rtt = windowed_min(rtt, 10 seconds)
pacing_rate = pacing_gain * bottleneck_bandwidth
cwnd =  max(cwnd_gain * bottleneck_bandwidth * min_rtt , 4)
FQ: Fair queue 公平队列．FQ可以根据bbr设置的pacing rate将一个cwnd内的数据的发送从“突发到网络”这种行为变换到“平缓发送到网路”的行为

测量瓶颈带宽和往返时延

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

据大家所说，今天的互联网并没有像它应该那样传输数据。 世界上大多数的手机用户都会遇到几秒到几分钟的延迟; 机场和会议场所的公共Wi-Fi往往更糟糕。 物理和气候研究人员需要与全球合作者交换PB级的数据，但是他们发现他们精心设计的多千兆基础设施（multi-Gbps infrastructure）通常在洲际距离上的传输速率只有几Mbps。

这些问题是由于在20世纪80年代创建TCP拥塞控制算法时所做出的设计选择造成的，即把数据包丢失解释为“拥塞”。由于技术限制，这种等同性当时是正确的，但这不是准则。 随着NIC（网络接口控制器）从Mbps发展到Gbps，内存芯片从KB发展到GB，数据包丢失和拥塞之间的关系变得更加脆弱。

今天，TCP基于丢包的拥塞控制 – 即使是目前最好的CUBIC – 是这些问题的主要原因。 当瓶颈缓冲区（bottleneck buffer）很大时，基于丢包的拥塞控制使它们保持满，导致缓冲区溢出。 当瓶颈缓冲区很小时，基于丢包的拥塞控制会将丢包视为拥塞信号，从而导致吞吐量较低。 解决这些问题需要一个算法，来替代基于丢包的拥塞控制。 寻找这个替代方案需要了解网络拥塞的起源地点和方式。

拥塞和瓶颈

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

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

•　这是持续排队的地方。 只有当连接上数据离开速率超过其到达速率时，队列才会缩小。 对于以最大传输速率运行的连接，瓶颈上游的所有链路都具有较快的离开速率，因此它们的队列迁移到瓶颈处。

无论连接经过多少个链路或各自的速度如何，从TCP的角度来看，一个任意复杂的路径都表现为具有相同RTT和瓶颈速率（bottleneck rate）的单一链路。RTprop（往返传播时间）和BtlBw（瓶颈带宽）两种属性限制着传输性能。 （如果网络路径是物理管道，则RTprop是其长度，BtlBw是其最小直径。）

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

当没有足够的数据来填充管道时，发送行为主要受RTprop约束; 否则主要受到BtlBw约束。 约束线相交于inflight = BtlBw×RTprop，也就是管道的BDP（带宽延迟乘积）。 一旦管道已经完全超过这一点，inflight数量大于BDP，将在bottleneck处产生一个队列，如上图所示，这导致RTT与inflight数据的线性相关性。 当多余的数据超过缓存容量时，数据包被丢弃。 拥塞只是持续运行在BDP线路的右侧，而拥塞控制则是，以一定的方案来限制到BDP线路右侧的距离（限制连接上inflight－BDP的数量）。

基于丢包的拥塞控制在bandwidth-limited区域的右边缘运行，以高延迟和频繁丢包为代价提供满的bottleneck bandwidth。 当内存昂贵时，缓冲区大小仅比BDP略大，这使得基于丢包的拥塞控制的延迟降至最低。 随着内存价格下降，导致缓冲区比ISP链接上的BDP大几个数量级，并且由此产生的bufferbloat，导致了几秒而不是几毫秒的RTT。

bandwidth-limited区域的左边缘是比右边更好的操作点。 1979年，Leonard Kleinrock指出这个工作点是最佳的，最大限度地提高了带宽，同时最大限度地减少了单个连接和整个网络的延迟和丢包。 不幸的是，与此同时，Jeffrey M. Jaffe证明，创建一个分布式算法不可能收敛到这个工作点。 这个结果改变了研究的方向，从找到一个实现Kleinrock所说的最佳操作点的分布式算法到研究不同的拥塞控制方法。

我们Google的小组每天都要花费数小时检查来自世界各地的TCP数据包头捕获情况，理解异常行为。 我们通常的第一步是找到基本的路径特征，RTprop和BtlBw。从这些信息的推断表明Jaffe的结论可能不像它曾经出现过的那样受到限制。 他的结论取决于基本的测量模糊度（例如，测量的RTT增加是否由路径长度变化，瓶颈带宽减少或来自另一连接的业务量的排队延迟增加引起）。 虽然不可能消除任何单一的衡量标准，但随着时间的推移，一个连接上的行为会说明一个更清晰的事情，这表明可能采用旨在解决歧义的测量策略。

将这些测量结果与使用最新的控制系统的鲁棒伺服回路相结合可以产生分布式的拥塞控制协议，该协议对实际拥塞，而不是分组丢失或瞬时队列延迟作出反应，并且以高概率收敛于Kleinrock的最佳拥塞控制点。 因此，我们开始了为期三年的寻找，去创建基于这两个表征路径参数（瓶颈带宽和往返传播时间，或BBR）的拥塞控制。

Characterizing the Bottleneck

当瓶颈分组到达速率等于BtlBw和（满管）时，即inflight数量等于BDP（= BtlBw×RTprop）时，连接以最高的吞吐量和最低的延迟运行。

第一个条件保证了瓶颈可以在100％利用率下运行。 第二个条件保证有足够的数据来防止瓶颈不足而不是过度填充管道。 单独的速率均衡条件并不能确保没有队列，只能确保不能改变大小（例如，如果一个连接初始发送窗口设置为10,开始就发送10个包到一个具有5个数据包的BDP中，然后以正确的瓶颈速率运行 ，10个初始数据包中有5个填满了管道，所以多余的数据就形成了一个无法消散的瓶颈）。 类似地，满管状态不保证不存在队列（例如，以BDP / 2脉冲发送BDP的连接获得完全瓶颈利用，但是平均队列为BDP / 4）。 将瓶颈和整条路径上的队列最小化的唯一方法是同时满足这两个条件。

BtlBw和RTprop在连接生命周期内不断变化，因此必须不断进行估计。 TCP当前有跟踪RTT（从发送数据包到确认的时间间隔），因为它是丢包检测所必需的。 在任何时候t，

其中η≥0代表队列沿路径引入的“噪声”，接收方的延迟ack策略，ack聚合等。RTprop是连接路径的物理属性，只有在路径发生变化时才会改变。 由于路径变化发生在时间尺度»RTprop，在时间T上一个无偏有效估计是

（即，在时间窗口WR（通常为几十秒到几分钟）内的最小RTT值。

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

其中时间窗口WB通常是6到10个RTT。

TCP必须记录每个数据包的发送时间来计算RTT。 BBR扩展了记录，增加了总数据传输信息，所以每个ack到达时，产生一个RTT和一个传输速率测量，（时间窗口）过滤器将其转换为RTprop和BtlBw的估计。

注意，这些值是完全独立的：RTprop可以改变（例如，在路由改变时），但仍具有相同的BtlBw，或者在路径未改变时，BtlBw可以改变（例如，当无线链路改变速率时）。 （这种独立性是为什么这两个约束不得不知道如何匹配发送行为和传输路径的原因。）因为RTprop仅在BDP左侧可见，而BtlBw仅在图1的右侧可见，所以它们服从不确定性原则：只要一个可以测量，其它的就没法测量。直观地说，这是因为管道必须被过度填充才能找到其容量，这就产生了一个阻塞管道长度的队列。例如，运行请求/响应协议的应用程序可能永远不会发送足够的数据来填充管道并观察BtlBw。多小时的批量数据传输可能会在带宽有限的区域内度过其整个生命周期，并且只有一个来自第一个数据包的RTTRTprop样本。这种内在的不确定性意味着，除了估计者要重新获得两个路径参数之外，还必须有一些状态跟踪在当前操作点可以学到的东西，并且随着信息变得陈旧，如何到达一个能重新学到的操作点。

Matching the Packet Flow to the Delivery Path

核心的BBR算法有两部分：
When an ack is received

每个ack提供新的RTT和平均传输速率测量，以更新RTprop和BtlBw估计：

function 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过滤器，从而导致数据发送太慢）。

When data is sent

为了使分组到达速率与瓶颈链路的离开速率相匹配，BBR控制每个数据分组的发送节奏。 （BBR必须匹配瓶颈速率，这意味着pacing是设计中不可或缺的一部分，并且是操作的基础 – pacing_rate是BBR的主要控制参数。第二重要的参数cwnd_gain，限制inflight数量为BDP的一个小的倍数，以处理常见的网络和接收端的异常处理 （见后面的延迟和延迟ACK部分）．从概念上讲，TCP发送例程如下所示（在Linux中，发送使用高效的FQ / pacing排队规则，这使得BBR 在多千兆链路上具有line rate 单连接性能 ，并且在CPU开销可以忽略不计的情况下，可以处理数以千计的较低速度节点连接。)

function send(packet) 
  bdp = BtlBwFilter.currentMax × RTpropFilter.currentMin 
  if (inflight >= cwnd_gain × bdp) 
     // wait for ack or retransmission timeout 
     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)

Steady-state behavior

BBR发送的速率和数量只是估计的BtlBw和RTprop的孤立函数，所以除了估计瓶颈约束之外，滤波器还控制自适应。 这产生了图2所示的新颖的控制回路，其显示，在10-Mbps，40-ms流的网络中，从700ms开始的RTT（蓝色），inflight数量（绿色）和传送速率（红色）细节。 传输速率上方的粗灰线是BtlBw max过滤器的状态。 三角形结构由BBR cycling pacing_gain得出，以确定BtlBw是否增加。 每个周期使用的gain显示与其影响的数据时间对齐。 当数据被发送时，增益被应用于RTT。 这由左侧的事件序列描述中的水平点动指示。 
 
BBR通过维持inflight数量大部分时间在一个BDP，最大限度地减少了时延，按照BtlBw的估算进行了调整。 这将瓶颈移到发送方，所以它无法观察到BtlBw的增加。 因此，BBR周期性地以RTprop时间间隔，设置pacing_gain > 1，这会增加发送速率和inflight数量。 如果BtlBw没有改变，则在瓶颈处创建队列，增加RTT，这将保持deliveryRate不变。 （这个队列通过在下一个RTprop周期，设置pacing_gain <1作为补偿，来被排空。）如果BtlBw已经增加，deliveryRate增加，并且新的最大值立即增加BtlBw过滤器的输出，增加pacing_rate。 因此，BBR快速收敛到新的bottleneck rate。 图3显示了在稳定运行20秒（左图）后，BtlBw的10-Mbps，40-ms流突然加倍至20 Mbps，然后以20 Mbps稳定运行20秒后降至10 Mbps（右图）。

（BBR是Max-plus控制系统的一个简单实例，这是一种基于非标准代数的新控制方法。这种方法允许自适应速率[由 max gain控制的]独立于队列增长[由 max gain控制]，应用于这个问题，它导致了一个简单的，隐式的控制循环，其中适应物理约束变化的过程由代表那些约束的过滤器自动处理，传统的控制系统需要由复杂状态机连接的多个循环来完成相同的结果。） 

Single BBR Flow Startup Behavior

现有的实现使用特定于事件的算法和大量代码来处理startup, shutdown和loss recovery。 BBR使用前面中详细描述的代码（在上一节中，匹配发送速率到传输路径），通过对包含一个或多个固定增益和退出条件的表所定义的一组“状态”进行排序来处理事件。大部分时间都在“Steady-state Behavior”一节中描述的ProbeBW状态中。Startup和Drain状态在连接开始时使用（图4）。为了探索跨越12个数量级的Internet链路带宽，Startup使用2 / ln2的增益实现了BtlBw的二进制搜索，使得发送速率增加了一倍，同时提高了传输速率。这在log2BDP个RTT中发现了BtlBw，但在此过程中创建了多达2BDP的额外队列。一旦启动发现BtlBw，BBR转换为Drain状态，它使用Startup阶段增益的倒数来排空多余的队列，然后一旦inflight数量下降到BDP，就进入ProbeBW状态。

图4显示了10-Mbps，40-ms BBR流的第一秒。 时间/序列图显示发送者（绿色）和接收者（蓝色）的进度与时间的关系。 红线显示在相同的条件下一个CUBIC发送端的状态。 垂直灰线标记BBR状态转换。 下图显示了两个连接的RTT与时间的关系。 注意，这个数据的时间参考是ack到达（蓝色），所以虽然它们似乎是时间偏移的，但在BBR了解它们并发挥作用的位置显示事件。

图4的下图对比了BBR和CUBIC。 他们最初的行为是相似的，但BBR完全排空了startup状态产生的队列，而CUBIC不能。 如果没有一个路径模型来告诉它inflight超了多少，CUBIC将使得inflight消极增长，但直到瓶颈缓冲区填满并丢包，或者达到接收端的上限（TCP的接收窗口）为止。

图5显示了图4所示连接的前8秒内的RTT行为。CUBIC（红色）填充可用缓冲区，然后每隔几秒从70％到100％循环。 启动后，BBR（绿色）基本上不运行队列。

Behavior of Multiple BBR Flows Sharing a Bottleneck

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

ProbeBW gain cycling（图2）会使得更大的流给更小的流让出带宽，从而使每个流都获得公平的份额。尽管当其他流已经（暂时）创建了一个队列，后启动的连接高估了RTprop作为开始状态时，这种不公平会持续，但是这种情况发生得相当快（只有一些ProbeBW周期）。

为了学习真实的RTProp，一个flow通过ProbeRTT状态移动到BDP的左侧：当RTProp的估计值几秒钟没有被更新（即通过测量一个较低的RTT），BBR进入ProbeRTT状态，这会将inflight减少到四个数据包，至少进行一次往返，然后返回到之前的状态。进入ProbeRTT状态的流会排掉队列中很多数据包，因此一些flows会看到一个新的RTprop（新的最小RTT）。这使得它们的RTprop估计值同时过期，所以它们一起进入ProbeRTT，这使得总队列倾角变大，导致更多的flows看到新的RTprop，等等。这种分散的协调是公平与稳定的关键。

BBR围绕一个期望的空瓶颈队列事件来同步多个flows。相比之下，基于丢包的拥塞控制,围绕周期性队列增长和溢出的不良事件来同步flows，这导致延迟和丢包放大。

Google B4 WAN Deployment Experience

Google的B4网络是一个使用commodity switches构建的高速WAN（广域网）。这些浅缓冲交换机的丢包主要来自小流量突发的同时到达。 2015年，Google开始将B4 production traffic 从CUBIC切换到BBR。 没有出现问题或回退的情况，自2016年以来，所有B4 TCP流量都使用BBR。 图7显示了切换的一个原因：BBR的吞吐量一直是CUBIC的2至25倍。 我们曾经期待更多的改进，但发现BBR连接的75％受限于内核的TCP接收缓冲区，网络操作团队为了防止CUBIC以兆兆字节的过多inflight洪泛网络（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路径，每30万包一个丢包）。图8比较了各种丢包率下的实测吞吐量。 CUBIC的丢包容忍度是算法的结构性质，而BBR的丢包容忍度是可配的参数。当BBR的丢包率接近ProbeBW峰值增益时，测量真实BtlBw的传输速率的概率急剧下降，引起最大值滤波器估值偏低。

图8显示了100-Mbps / 100-ms链路上60秒flow的BBR与CUBIC吞吐量的比较，随机丢包率为0.001％到50％。 在丢包率为0.1％的情况下，CUBIC的吞吐量下降了10倍； 在丢包率为1％的情况下完全失速。 最大可能吞吐量是链路速率乘以分数（= 1 - lossRate）。 BBR在丢包率为5％到15%的情况下符合这个限制。

YouTube Edge Deployment Experience

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

图9显示了在一个星期内在五大洲测量的超过2亿个YouTube回放连接的BBR与CUBIC中值RTT的改进。全球70亿移动互联网用户中，超过一半的用户通过8Gbps到114Kbps的2.5G系统进行连接，这些系统由于基于丢包的拥塞控制的填充缓存倾向而遭受了严重的文件记录问题.这些系统的瓶颈环节是通常在SGSN（服务GPRS支持节点）和移动设备之间。 SGSN软件运行在具有足够内存的标准PC平台上，因此Internet和移动设备之间经常有兆字节的缓冲区。图10比较了（模拟的）BBR和CUBIC的SGSN互联网到移动设备的延迟。水平线标志着一个更严重的后果：TCP适应长时间RTT延迟，除了连接启动SYN数据包，其具有取决于操作系统的固定超时。当移动设备通过大缓冲的SGSN接收批量数据（例如，app自动更新）时，设备不能连接到互联网上的任何东西，直到队列清空（SYN ACK接受分组延迟超过固定SYN超时）。

 

图10显示了具有八个BBR（绿色）或CUBIC（红色）flows的128-Kbps / 40-ms链路上的链路缓冲区大小的稳态中值RTT变化。 BBR将队列保持在最小值附近，与瓶颈缓冲区大小和活动flows数量无关。 CUBIC的flows总是填充缓冲区，所以延迟随缓冲区大小线性增长。

Mobile Cellular Adaptive Bandwidth

蜂窝系统部分地基于（使用指定给用户的分组队列的）需求估计来适配每个用户带宽。 BBR的早期版本被调整为创建非常小的队列，导致连接陷入低速。 提高峰值ProbeBW pacing_gain创建更大的队列导致更少的卡住连接，表明可能对某些网络来说太棒了。 在当前的1.25×BtlBw峰值增益下，与任何网络上的CUBIC相比，没有明显的降级。

Delayed and Stretched ACKs

蜂窝，Wi-Fi和有线宽带网络通常会延迟和合并ACK.当inflight限制为一个BDP时，这会导致吞吐量减少。 将ProbeBW的cwnd_gain提高到两个允许的BBR，以估计的传送速率平滑地继续发送，即使ACK最多延迟一个RTT。 这在很大程度上避免了突降（stalls）。

Token-Bucket Policers

BBR最初的YouTube部署显示，世界上大多数的ISP用token-bucket policers来管理流量.bucket在连接启动时通常是满的，所以BBR学习底层网络的BtlBw，但是一旦bucket清空，所有发送比bucket填充速率更快（远小于BtlBw）的数据包将被丢弃。 BBR最终得知这个新的传输速率，但是ProbeBW增长周期导致持续的适度丢包。 为了最大限度地减少上行带宽浪费和应用等待时间的增加，我们在BBR中加入了policer detection和明确的policer model。 我们也在积极研究更好的方法来缓解 policer damage。

Competition with Loss-Based Congestion Control

无论是与其他BBR流还是基于丢包的拥塞控制流竞争，BBR都会收敛于瓶颈带宽的公平份额。 即使基于丢包的拥塞控制填充了可用的缓冲区，ProbeBW依然可靠地将BtlBw估计值移向流量的公平份额，ProbeRTT发现RTProp估计值足够高，从而可以达到公平份额。 不受管理的路由器缓冲区超过了几个BDP，但是，会导致长期以来基于丢包的竞争者膨胀队列，并获得超过其合理份额。 减轻这是另一个积极的研究领域。

Conclusion

重新思考拥塞控制支付巨大的红利。 BBR不是使用与拥塞相关性较弱的事件，如丢包或缓冲区占用率，而是从Kleinrock的正式堵塞模型及其相关的最佳控制点开始。令人讨厌的“不可能性”导致延迟和带宽的关键参数不能被同时确定，因此通过观察它们可以被连续地估计来回避。然后使用控制和估计理论的最新进展来创建一个简单的分布式控制环，它接近最佳控制点，充分利用网络，同时维持一个小队列。 Google的BBR实现可以在开源的Linux内核TCP中找到，在本文的附录中有详细的介绍。

BBR部署在Google的B4主干上，与CUBIC相比，吞吐量提高了数个数量级。它也被部署在谷歌和YouTube网络服务器上，大大降低了迄今测试的五大洲的时延，在发展中地区最为显着。 BBR纯粹在发送方运行，不需要对协议，接收方或网络进行更改，从而使其可以逐步部署。它仅取决于RTT和分组传送确认，因此可以用于大多数Internet传输协议。

The authors can be contacted at bbr-dev@googlegroups.com. 

Acknowledgments

The authors are grateful to Len Kleinrock for pointing out the right way to do congestion control. We are indebted to Larry Brakmo for pioneering work on Vegas2 and New Vegas congestion control that presaged many elements of BBR, and for advice and guidance during BBR's early development. We would also like to thank Eric Dumazet, Nandita Dukkipati, Jana Iyengar, Ian Swett, M. Fitz Nowlan, David Wetherall, Leonidas Kontothanassis, Amin Vahdat, and the Google BwE and YouTube infrastructure teams for their invaluable help and support.

Appendix - Detailed Description

A State Machine for Sequential Probing

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

BBR使用这个pacing_gain来实现一个简单的顺序探测状态机，在更高带宽的测试之间交替，然后测试更低的往返时延。 （不必探测更小的带宽，因为BtlBw max滤波器会自动处理较少的带宽：新的测量结果反映了下降，一旦最后一次旧的测量结果超出滤波器，BtlBw就会自行修正。类似的，RTprop min滤波器也自动处理路径长度的增加。）

如果瓶颈带宽增加，BBR必须发送更快来识别。同样，如果实际的往返传播延迟改变，这改变了BDP，并且因此BBR必须较慢地发送到BDP以下以便测量新的RTprop。因此，发现这些变化的唯一方法是run experiments，发送更快来检查BtlBw增加或发送更慢来检查RTprop减少。这些实验的频率，大小，持续时间和结构取决于已知（startup或ssteady-state）和发送应用行为（间歇或连续）。

Steady-State Behavior

BBR流量大部分时间处于ProbeBW状态，使用称为增益循环的方法探测带宽，这有助于BBR流量达到高吞吐量，低排队延迟以及收敛到公平的带宽。随着增益循环，BBR循环通过pacing_gain的一系列值。它使用具有以下pacing_gain值的八个阶段的周期：5 / 4,3 / 4,1,1,1,1,1,1。每个阶段通常持续估计RTprop。这个设计允许增益周期首先探测更多的带宽，其中pacing_gain大于1.0，然后用pacing_gain小于1.0排出任何得到的队列，然后使用1.0的pacing_gain巡航短队列。所有阶段的平均增益为1.0，因为ProbeBW的目标是使其平均pacing rate等于可用带宽，从而保持较高的利用率，同时维持一个小而有序的队列。请注意，虽然增益循环会改变pacing_gain值，但cwnd_gain保持恒定为2，因为延迟和拉伸的ack可以在任何时候触发（参见Delayed and Stretched Acks部分）。

此外，为了改善混合和公平性，并且在多个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估计值尚未更新（即通过获取较低的RTT测量值）超过10秒，则BBR进入ProbeRTT并将cwnd减小到非常小的值（四个分组）。在保持这个最小inflight数量至少200 ms和一个往返后，BBR将离开ProbeRTT并转换到Startup或ProbeBW，这取决于它是否估计管道已经被填满。

BBR被设计为将大部分时间（大约98％）花费在ProbeBW中，其余部分花在ProbeRTT上，基于一系列权衡。 ProbeRTT持续时间足够长（至少200毫秒），以允许具有不同RTT的流具有重叠的ProbeRTT状态，同时还足够短以将ProbeRTT的cwnd减小的性能损失限制为大约2％（200ms / 10秒）。 RTprop过滤器窗口（10秒）足够短，以便在流量级别或路由改变时允许快速收敛，但时间足够长以使得交互式应用程序（例如，网页，远程过程调用，视频块）在窗口内通常具有自然的静音或低速率时段，其中流速足够低或足够长以排出其瓶颈中的队列。然后RTprop过滤器概率性地拾取这些RTprop测量，并且RTProp刷新而不需要ProbeRTT。这样，如果在整个RTProp窗口中有多个批量流量正忙于发送，流量通常只需要支付2％的处罚。

Startup Behavior

当BBR flow启动时，它执行第一个（也是最快速的）sequential probe/drain过程。网络链路带宽的范围是1012 － 从每秒几位到100Gbps。为了学习BtlBw，考虑到这个巨大的范围，BBR做了一个二进制搜索速率空间。这很快找到BtlBw（log2BDP往返），但是在搜索的最后一步创建一个2BDP队列。 BBR的“Startup ”状态执行此搜索，然后是“Drain”状态排空队列。

首先，Startup的发送速度呈指数级增长，每轮增加一倍。为了以最平稳的方式实现这种快速探测，在启动时，将pacing_gain和cwnd_gain设置为2 / ln2，这是允许发送速率每轮增加一倍的最小值。一旦管道满，cwnd_gain将队列限制为（cwnd_gain - 1）×BDP。

在Startup期间，BBR通过在BtlBw估计值中寻找一个平台来估计管道是否满了。如果注意到有几次（三次）试图将delivery rate加倍，结果实际上导致很小的增加（小于25％），那么它估计已经达到BtlBw并且退出Startup并且进入Drain。 BBR等待三轮，以便有确凿证据表明发送端没有检测到接收窗口暂时强加的传送速率plateau。允许三轮，为接收端的接收窗口自动调整提供时间来打开接收窗口，并且为BBR发送端提供时间意识到BtlBw应该更高：在第一轮中，接收窗口自动调整算法生长接收窗口;在第二轮发送端填充较高的接收窗口;在第三轮中发件端获得更高的delivery-rate样本。这个三轮门槛通过YouTube实验数据验证。

在Drain状态中，BBR的目标是通过切换pacing_gain为Stratup过状态下的倒数，来快速排除在Startup时创建的任何队列。当inflight数量与估计的BDP相匹配时，BBR估计队列已经完全耗尽但管道仍然充满，然后BBR离开Drain进入ProbeBW。

注意，BBR的Startup和CUBIC的慢启动都是以指数方式探测bottleneck capacity，每轮发送速率翻倍;然而，它们主要行为有所不同。首先，BBR在发现可用带宽方面更加健壮，因为在数据包丢失时不会退出搜索，或者（如在CUBIC的Hystart中）延迟增加。其次，BBR平滑地加速了它的发送速度，而在每一轮中，CUBIC（即使有pacing）发送一个包突发，然后imposes a gap of silence。图4演示了inflight数量和在BBR和CUBIC的每次确认中观察到的RTT关系。

Reacting to Transients

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

References

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 ACM 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); http://queue.acm.org/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. ACM 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. ACM 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. ACM 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. ACM 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.

Related Articles

Sender-side Buffers and the Case for Multimedia Adaptation 
Aiman Erbad and Charles "Buck" Krasic 
http://queue.acm.org/detail.cfm?id=2381998

You Don't Know Jack about Network Performance 
Kevin Fall and Steve McCanne 
http://queue.acm.org/detail.cfm?id=1066069

A Guided Tour through Data-center Networking 
Dennis Abts and Bob Felderman 
http://queue.acm.org/detail.cfm?id=2208919

The authors are members of Google's make-tcp-fast project, whose goal is to evolve Internet transport via fundamental research and open source software. Project contributions include TFO (TCP Fast Open), TLP (Tail Loss Probe), RACK loss recovery, fq/pacing, and a large fraction of the git commits to the Linux kernel TCP code for the past five years.

Copyright © 2016 Hhld by owner/author. Publication rights licensed to ACM.