ACM通信

实践

BBR:基于拥塞的拥塞控制

作者:尼尔·卡德维尔，郑宇中，c·斯蒂芬·古恩，索海尔·哈斯·耶加内，范·雅各布森
ACM通信，2017年2月，第60卷第2期，58-66页
10.1145 / 3009824
评论

大家都说，今天的互联网并没有像它应该的那样移动数据。世界上大多数手机用户都经历过几秒钟到几分钟的延迟;机场和会议场所的公共Wi-Fi通常更差。物理学和气候研究人员需要与全球合作者交换拍字节的数据，但发现他们精心设计的多gbps基础设施在洲际距离上通常只能传输几Mbps的数据。⁶

这些问题源于TCP拥塞控制在20世纪80年代创建时所做的一个设计选择，即将数据包丢失解释为“拥塞”。¹³这种对等在当时是正确的，但这是因为技术的限制，而不是基本原理。随着网卡(网络接口控制器)从Mbps发展到Gbps，内存芯片从KB发展到GB，包丢失和拥塞之间的关系变得更加脆弱。

今天TCP的基于损失的拥塞控制，即使是目前最好的品种，CUBIC¹¹是这些问题的主要原因。当瓶颈缓冲区很大时，基于损失的拥塞控制使它们保持满，导致缓冲区膨胀。当瓶颈缓冲区较小时，基于损耗的拥塞控制会将损耗误解为拥塞信号，导致吞吐量较低。解决这些问题需要一种基于损耗的拥塞控制的替代方案。要找到这种替代方案，需要了解网络拥塞是在哪里以及如何产生的。

回到顶部

阻塞和瓶颈

在任何时候，一个(全双工)TCP连接只有一个最慢的链路瓶颈在每一个方向。瓶颈之所以重要，是因为:

• 它决定了连接的最大数据传输速率。这是不可压缩流的一般性质(例如，想象一个在高峰期的六车道高速公路，事故将一小段缩短为单车道。事故上游的车辆行驶速度并不比通过该车道的车辆快)。
• 它是形成持久队列的地方。只有当一条线路的出发速率超过到达速率时，队列才会缩小。对于以最大传输速率运行的连接，瓶颈上游的所有链接都有更快的离开速率，因此它们的队列迁移到瓶颈。

不管一个连接要经过多少个链接，或者它们各自的速度是多少，从TCP的角度来看，任意复杂的路径都表现为具有相同RTT(往返时间)和瓶颈率的单个链接。两个物理约束,RTprop(往返传播时间)和BtlBw(瓶颈带宽)，绑定传输性能。(如果网络路径是一个物理管道，RTprop它的长度和BtlBw它的最小直径)。

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

当飞行中没有足够的数据填满管道时，RTprop决定行为;否则,BtlBw占主导地位。约束线相交于机上＝BtlBw×RTprop，即管道的BDP(带宽时延乘积)。因为管子满了，过了这个点inflight-BDP在瓶颈处产生一个队列，导致RTT对的线性依赖机上数据如上图所示。当超过缓冲区容量时，报文将被丢弃。交通拥堵只是BDP线右侧的持续操作，并且拥塞控制是一种限定连接平均向右移动多远的方案。

基于损耗的拥塞控制在带宽受限区域的右边缘运行，以高延迟和频繁丢包为代价提供完全的瓶颈带宽。当内存很昂贵时，缓冲区大小仅略大于BDP，这将最小化基于损耗的拥塞控制的多余延迟。随后的内存价格下降导致了比ISP链路bdp大数量级的缓冲区，并且由此产生的缓冲区膨胀产生了秒而不是毫秒的rtt。⁹

带宽受限区域的左边缘比右边缘是一个更好的操作点。1979年，Leonard Kleinrock¹⁶表明该操作点是最佳的，最大限度地提高传输带宽，同时最小化延迟和损耗，无论是对单个连接还是对整个网络⁸．不幸的是，与此同时，杰弗里·m·贾菲¹⁴证明了不可能创建一个收敛到这个操作点的分布式算法。这一结果改变了研究方向，从寻找一种实现Kleinrock最优工作点的分布式算法，到研究拥塞控制的不同方法。

我们在谷歌的团队每天花费数小时检查来自世界各地的TCP包头捕获，了解行为异常和病态。我们通常的第一步是找到基本路径特征，RTprop而且BtlBw。这些都可以从痕迹中推断出来，这表明贾菲的结果可能不像以前那样有局限性。他的结果基于基本的度量歧义(例如，度量的RTT增加是由路径长度变化、瓶颈带宽减少还是由另一个连接的流量引起的排队延迟增加引起的)。尽管不可能消除任何单个测量的歧义，但连接随时间的变化行为说明了一个更清楚的情况，这表明设计用于解决歧义的测量策略的可能性。

将这些测量与使用最新控制系统的鲁棒伺服回路相结合¹²可以产生一个分布式拥塞控制协议，它对实际的拥塞做出反应，而不是丢包或瞬时队列延迟，并以很高的概率收敛到Kleinrock的最佳工作点。因此，我们开始了为期三年的探索，基于测量表征路径的两个参数:瓶颈带宽和双向传播时间(BBR)来创建一个拥塞控制。

回到顶部

描述瓶颈

当(速率平衡)瓶颈包到达率等于时，连接以最高吞吐量和最低延迟运行BtlBw和(满管)飞行中的总数据等于BDP (=BtlBw×RTprop)．

第一个条件保证瓶颈可以以100%的利用率运行。第二种方法保证有足够的数据来防止瓶颈短缺，但不会使管道过载。只有速率平衡条件不确保没有队列，只是它不能改变大小(例如，如果一个连接通过将它的10个包初始窗口发送到一个5个包的BDP开始，然后以精确的瓶颈速率运行，10个初始包中的5个填充管道，因此多余的队列在瓶颈处形成一个不散的固定队列)。类似地，全管道条件也不能保证没有队列(例如，以BDP/2突发发送BDP的连接将获得完全的瓶颈利用率，但平均队列为BDP/4)。最小化瓶颈处和整个路径上的队列的唯一方法是同时满足这两个条件。

BtlBw而且RTprop在连接的生命周期中变化，因此必须不断地估计它们。TCP目前跟踪RTT(从发送数据包到被确认的时间间隔)，因为丢失检测需要RTT。在任何时候t，

其中0表示路径沿线队列引入的“噪声”、接收方的延迟ack策略、ack聚合等。RTprop是连接路径的物理属性，仅在路径更改时才更改。因为路径变化是在时间尺度上发生的RTprop，一个无偏的，有效的估计时T是

(也就是说，一个运行的最小值随时间窗口变化W_R(通常是几十秒到几分钟)。

与RTT不同的是，TCP规范中没有任何要求实现跟踪瓶颈带宽的内容，但是通过跟踪交付速率可以得到很好的估计。当某个数据包的ack返回发送方时，它将传递该数据包的RTT并宣布数据的交付机上当包裹离开的时候。send和ack之间的平均传递速率是传递的数据与时间流逝的比率:deliveryRate＝交付/t。这个速率必须是瓶颈速率(到达量是准确知道的，所以所有的不确定性都在t，它必须是真实的到达间隔;因此，该比率必须是真正的交付率，而该交付率又是瓶颈容量的上界)。因此，有窗最大值的交付率是一个有效的，无偏的估计BtlBw:

时间窗口在哪里W_B通常是6到10次rtt。

---

我们在谷歌的团队每天花费数小时检查来自世界各地的TCP包头捕获，了解行为异常和病态。我们通常的第一步是找到基本路径特征，RTprop和BtlBw。

---

TCP必须记录每个报文的出发时间来计算RTT。BBR将该记录与传递的总数据相加，因此每个ack到达都会产生RTT和传递速率测量值，然后由过滤器转换为该值RTprop而且BtlBw估计。

注意，这些值是完全独立的:RTprop可以更改(例如，在路由更改上)但仍然有相同的瓶颈，或者BtlBw可以在不改变路径的情况下改变(例如，当无线链路改变速率时)。(这种独立性就是为什么必须知道这两个约束才能将发送行为与传递路径相匹配。)自RTprop只在BDP左侧可见BtlBw只有到右边才行图1在美国，它们遵循一个测不准原理:只要一个可以测量，另一个就不能。直观地说，这是因为管道必须被过度填充才能找到它的容量，这会创建一个队列，从而掩盖了管道的长度。例如，运行请求/响应协议的应用程序可能永远不会发送足够的数据来填充管道并进行观察BtlBw．一个数小时的批量数据传输可能在带宽有限的区域中度过整个生命周期，并且只有一个样本RTprop从第一个包的RTT。这种内在的不确定性意味着，除了恢复两个路径参数的估计量外，还必须有跟踪在当前操作点可以学到什么以及(当信息变得陈旧时)如何到达可以重新学习的操作点的状态。

回到顶部

匹配报文流和发送路径

BBR的核心算法有两个部分:

当收到ack时。每个ack提供新的RTT和传递速率测量，更新RTprop而且BtlBw估计，如图2．

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

当数据发送时。为了使数据包到达速率与瓶颈链路的离开速率相匹配，BBR对每个数据包进行配速。BBR必须与瓶颈相匹配率这意味着起搏在设计中是不可或缺的，而起搏速率是BBR的主要控制参数。第二个参数cwnd__gain, bounds机上到BDP的一个小倍数来处理常见的网络和接收器病变(如我们将讨论的)。从概念上讲，TCP发送例程类似于图3．(在Linux中，发送使用高效的FQ/节奏排队规则，⁴它在千兆连接上提供BBR线速率单连接性能，并处理数千个较低速率速率的连接，CPU开销可以忽略不计。)

稳态行为。BBR发送的速率和数量仅仅是估计的函数BtlBw而且RTprop，因此过滤器除了估计瓶颈约束外，还控制自适应。这就创建了如下所示的控制循环图4，表示RTT(蓝色)，机上(绿色)和传输速率(红色)细节来自700ms的10Mbps, 40ms的流。交付率数据上面的粗灰色线是状态BtlBw马克斯过滤器。三角形结构由BBR循环pacing_gain来确定BtlBw增加了。在周期的每个部分使用的增益显示与它影响的数据时间对齐。当数据被发送时，增益被应用RTT。这可以通过事件序列描述中左侧的水平慢跑来表示。

BBR最大限度地减少了延误，它的大部分时间都在一个BDP的飞行中，速度在BtlBw估计。这将把瓶颈移到发送方，因此发送方不能进行观察BtlBw增加。因此，BBR定期花费一个RTproppacing_gain > 1的间隔，该间隔将增加发送速率和机上。如果BtlBw没有改变，那么在瓶颈处创建一个队列，增加RTT，保持deliveryRate常数。(通过向下一个队列发送补偿pacing_gain < 1来删除此队列RTprop)。如果BtlBw增加了,deliveryRate增加和新的最大立即增加BtlBw过滤输出，增加基地起搏速率。因此，BBR以指数级的速度收敛到新的瓶颈速率。图5显示了对10Mbps, 40ms流量的影响BtlBw稳定运行20秒后突然翻倍到20Mbps(上图)，然后在20Mbps稳定运行20秒后下降到10Mbps(下图)。

(BBR是Max-plus控制系统的一个简单实例，这是一种基于非标准代数的控制新方法。¹²这种方法允许自适应率[由马克斯增益]独立于队列增长[由平均获得)。应用到这个问题中，它会产生一个简单的、隐式的控制循环，其中对物理约束变化的适应由代表这些约束的过滤器自动处理。传统的控制系统需要通过复杂的状态机连接多个循环才能达到同样的效果。)

回到顶部

单个BBR流启动行为

现有的实现使用特定于事件的算法和许多行代码处理启动、关闭和丢失恢复等事件。BBR使用前面详细描述的代码，通过一组“状态”(由包含一个或多个固定收益和退出标准的表定义)进行排序来处理事件。大部分时间都花在稳态行为一节中描述的探针bw状态上。Startup和Drain状态用于连接启动(图6)．为了处理跨越12个数量级的Internet链路带宽，Startup实现了一个二进制搜索BtlBw通过使用2/ln2的增益使发送速率增加一倍，而传输速率增加。这个发现BtlBw在日志₂和平民主党rtt但是创建到2 bdp进程中队列过多。一旦启动时发现了BtlBw， BBR转换到Drain，它使用Startup的增益的倒数来去除多余的队列，然后再转换到ProbeBW机上降至BDP。

图6显示10Mbps, 40ms BBR流的第一秒。时间/序列图显示发送方(绿色)和接收方(蓝色)进度与时间的关系。红线显示相同条件下的CUBIC发送方。垂直的灰色线表示BBR状态转换。下图显示了两个连接的RTT随时间的变化。请注意，此数据的时间参考是ack到达(蓝色)，因此，虽然它们看起来是时移的，但事件显示在BBR了解到它们并采取行动的点。

下面的图是图6BBR和CUBIC的对比。它们最初的行为是相似的，但BBR完全耗尽了启动队列，而CUBIC不能。没有路径模型来告诉它有多少机上是过剩，立方使机上增长不那么积极，但增长会继续，直到瓶颈缓冲区填满并丢弃一个包或接收方的包机上limit (TCP的接收窗口)已达到。

图7中所示连接的前8秒内的RTT行为图6．CUBIC(红色)填充可用缓冲区，然后每隔几秒从70%满循环到100%满。启动后，BBR(绿色)运行时基本上没有队列。

回到顶部

共享一个瓶颈的多个BBR流的行为

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

探头增益循环(图4)导致较大的流将带宽分配给较小的流，从而使每个流都能获得公平的份额。这发生得相当快(几个ProbeBW周期)，但当后发者高估时，不公平可能持续存在RTprop当其他流(临时)创建队列时启动。

学习真理RTProp时，流使用ProbeRTT状态移动到BDP的左侧:当RTProp估计没有更新(即通过测量较低的RTT)很多秒，BBR进入ProbeRTT，这降低了机上到四个包进行至少一次往返，然后返回到前一个状态。进入ProbeRTT的大型流从队列中抽走许多包，因此有几个流看到一个新的RTprop(新最低RTT)。这使得他们的RTprop估计同时过期，因此它们一起进入ProbeRTT，这使得总队列倾斜更大，并导致更多流看到新的RTprop，等等。这种分布式协调是公平和稳定的关键。

BBR在空瓶颈队列的期望事件周围同步流。相比之下，基于损耗的拥塞控制是围绕不希望发生的周期性队列增长和溢出事件进行同步的，这会放大延迟和丢包。

回到顶部

谷歌B4广域网部署经验

谷歌的B4网络是使用商用交换机构建的高速广域网。¹⁵这些浅缓冲开关上的损失主要是由于小流量突发的同时到达造成的。2015年，谷歌开始将B4生产流量从CUBIC切换到BBR。没有出现任何问题或倒退，自2016年以来，所有B4 TCP流量都使用BBR。图9显示了转换的一个原因:BBR的吞吐量始终是CUBIC的2到25倍。我们期望有更多的改进，但发现75%的BBR连接受到内核的TCP接收缓冲区的限制，网络运营团队故意将该缓冲区设置得很低(8MB)，以防止CUBIC用兆字节的溢出溢出网络机上(8MB/200ms洲际RTT 335Mbps最大吞吐量)。在一条美欧路径上手动提高接收缓冲区，BBR立即达到2Gbps，而CUBIC保持在15mbps——Mathis等人预测的133×相对改善。¹⁷

图9BBR与CUBIC的相对吞吐量有所改善;插图显示吞吐量cdf(累积分布函数)。测量来自一个活跃的探针服务，它打开到远程数据中心的持久BBR和CUBIC连接，然后每分钟传输8MB的数据。探测器通过北美、欧洲和亚洲内部和之间的许多B4路径进行通信。

这种巨大的改善是BBR的直接结果不使用损耗作为拥塞指示器。为了实现全带宽，现有的基于损耗的拥塞控制要求丢失率小于BDP的平方反比¹⁷(例如，对于10Gbps/100ms的路径，每3000万个包中< 1个丢失)。图10比较不同损失率下测量的存货量。CUBIC的容错是算法的一个结构属性，而BBR的容错是一个配置参数。当BBR的损失率接近ProbeBW的峰值增益时，测量的概率为真实的交付率BtlBw急剧下降，导致最大滤镜低估。

图10显示了在100Mbps/100ms链路上60秒流量下BBR与CUBIC的良放，随机损失为0.001至50%。CUBIC的吞吐量在0.1%的损失下下降10倍，并完全停滞在1%以上。最大可能的吞吐量是链路速率乘以交付的分数(=1lossRate)．BBR达到了5%的损失上限，接近15%。

回到顶部

YouTube Edge部署体验

BBR正在部署中Google.com以及YouTube视频服务器。谷歌正在进行小规模实验，其中一小部分用户被随机分配为BBR或CUBIC。使用BBR的回放显示了YouTube的所有体验质量指标的显著改善，可能是因为BBR的行为更加一致和可预测。BBR只能轻微提高连接吞吐量，因为YouTube已经将服务器的流媒体速率调整到远低于此速率的水平BtlBw尽量减少缓冲区膨胀和重新缓冲事件。即便如此，BBR在全球平均降低了53%的RTT中值，在发展中国家降低了80%以上。图11显示了在五大洲超过2亿的YouTube播放连接中，BBR和CUBIC在一周内的平均RTT改善。

全球70亿移动互联网用户中，超过一半通过8kbps到114kbps的2.5G系统连接，⁵由于基于损失的拥塞控制的缓冲区填充倾向，它们遭受了充分证明的问题。^3.这些系统的瓶颈链接通常在SGSN(服务GPRS支持节点)之间¹⁸和移动设备。SGSN软件运行在具有充足内存的标准PC平台上，因此在互联网和移动设备之间通常有兆字节的缓冲区。图12比较(仿真)SGSN的互联网到移动延迟BBR和CUBIC。水平线标志着一个更严重的后果:TCP适应较长的RTT延迟，除了连接发起SYN包，它有一个依赖于操作系统的固定超时。当移动设备通过一个大缓冲SGSN接收大量数据(例如，来自自动应用程序更新)时，设备无法连接到Internet上的任何东西，直到队列清空(SYN ACK接收包的延迟时间超过固定的SYN超时时间)。

图12显示了在128Kbps/40ms链路上有8个BBR(绿色)或CUBIC(红色)流的链路缓冲区大小随稳态RTT中值的变化。BBR将队列保持在其最小值附近，与瓶颈缓冲区大小和活动流的数量无关。立方流总是填满缓冲区，因此延迟与缓冲区大小成线性增长。

回到顶部

移动蜂窝自适应带宽

蜂窝系统在一定程度上根据使用发送给订阅者的包队列的需求估计来调整每个订阅者的带宽。BBR的早期版本被调优为创建非常小的队列，导致连接在低速率时卡住。提高峰值ProbeBW pacing_gain以创建更大的队列，结果导致更少的阻塞连接，这表明可能对某些网络太好了。与当前1．25×BtlBw峰值增益，与任何网络上的CUBIC相比，没有明显的退化。

延迟和拉伸。蜂窝网络、Wi-Fi和有线宽带网络经常延迟和聚合ack。¹当机上限制为一个BDP，这导致吞吐量降低的档位。将ProbeBW的cwnd_gain提高到2可以使BBR继续以估计的交付速率平稳发送，即使ack被延迟了最多一个RTT。这在很大程度上避免了摊位。

令牌桶policers。BBR最初在YouTube上的部署表明，世界上大多数isp都使用令牌桶政策器来干扰流量。⁷在连接启动时，桶通常是满的，因此BBR学习底层网络的BtlBw，但一旦桶空了，所有的包发送比(远低于BtlBw)桶填充率下降。BBR最终学会了这个新的传输速率，但ProbeBW增益周期导致持续的中等损失。为了尽量减少上游带宽浪费和应用程序延迟的增加，我们在BBR中添加了策略检测和显式策略模型。我们也在积极研究更好的方法来减轻政策的损害。

与基于损失的拥塞控制竞争。无论是与其他BBR流竞争还是与基于损失的拥塞控制竞争，BBR都会收敛到瓶颈带宽的公平份额。即使基于损失的拥塞控制填充了可用的缓冲区，ProbeBW仍然健壮地移动BtlBw估计了流动的公平份额，ProbeRTT找到了一个RTProp估计刚好高到以牙还牙的收敛到公平的份额。然而，未管理的路由器缓冲区超过几个bdp，会导致长期存在的基于损耗的竞争对手使队列膨胀，并夺取超过其公平份额的份额。缓解这种情况是另一个积极研究的领域。

回到顶部

结论

重新思考拥塞控制将带来巨大收益。BBR不是使用损失或缓冲区占用等事件，这些事件与拥塞只有弱相关性，而是从Kleinrock的拥塞形式化模型及其相关的最佳工作点开始。延迟和带宽的关键参数不能同时确定，这是一个令人讨厌的“不可能”结果，通过观察它们可以依次估计，就避开了这一结果。然后利用控制和估计理论的最新进展来创建一个接近最优的简单分布式控制环，充分利用网络，同时保持一个小的队列。谷歌的BBR实现可在开源Linux内核TCP中获得。

BBR部署在谷歌的B4主干上，与CUBIC相比吞吐量提高了数量级。它还被部署在谷歌和YouTube的Web服务器上，大大减少了迄今为止测试的所有五大洲的延迟，其中最显著的是在发展中地区。BBR完全运行在发送端，不需要对协议、接收端或网络进行更改，因此可以增量部署。它只依赖于RTT和包传递确认，因此可以为大多数Internet传输协议实现。

回到顶部

致谢

感谢Len Kleinrock指出了控制拥堵的正确方法，感谢Larry Brakmo在拉斯维加斯的开创性工作²以及预示着BBR许多元素的新拉斯维加斯拥堵控制，以及BBR早期开发期间的建议和指导。我们还要感谢Eric Dumazet、Nandita Dukkipati、Jana Iyengar、Ian Swett、M. Fitz Nowlan、David Wetherall、Leonidas Kontothanassis、Amin Vahdat以及谷歌BwE和YouTube基础设施团队。

相关文章
在queue.acm.org

发送端缓冲区和多媒体适应案例
艾曼·埃尔巴德和查尔斯·巴克·克拉西奇
http://queue.acm.org/detail.cfm?id=2381998

你对网络性能一无所知
凯文·福尔和史蒂夫·麦卡恩
http://queue.acm.org/detail.cfm?id=1066069

数据中心网络导览
丹尼斯·阿布斯和鲍勃·费尔德曼
http://quue.acm.org/detail.cfm?id=2208919

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2017 ACM, Inc.

---

没有发现记录