BBR:Congestion-Based Congestion Control解读

测量瓶颈带宽和RTprop

原文地址：链接

背景

如今有大量的网络用户忍受着几秒甚至几分钟的网络延迟。有些精心设计的性能在Gbps级别的基础设施，实际上只有几Mbps。
造成这个问题的原因是TCP拥塞控制算法的设计选择问题，在上世纪80年代，TCP拥塞控制算法开始设计时，将丢包解释为了拥塞。这个解释在当时的技术条件限制下是正确的，但是随着网卡速度从Mbps到Gbps，内存芯片从KB到GB，丢包和拥塞之间的关系已经不再是对等关系。
基于丢包的TCP拥塞控制是造成网络延迟的最大原因，甚至是最优秀的CUBIC也不能避免。这些算法总是将链路上的路由器或者交换机或者主机的转发缓冲区填满，直到开始丢包，然后降低发包速率，这里会引起两个问题，一个是rtt增大，一个是错误地降低了发包速率。解决网络延迟大的问题需要找到正确的网络拥塞的位置和原因。

拥塞和瓶颈

TCP不管是在收包方向还是发包方向，都有一个最短路径或者瓶颈带宽。为什么要找到这个瓶颈：

• 瓶颈决定了链接的最大数据上送速率。这是一个不可压缩流的重要属性，比如，一个六车道的高速公路，在某个事故路段，车道数量降低到了一个车道，那么上流（比喻为上送速率）的车辆通过速度不可能大于这个车道。
• 这是形成持久队列的条件。发包速率一直稳定在瓶颈带宽，这样可以保证链路是空闲的，因为上流的包离开速度肯定大于下流的包加入速度。
  不管一条tcp链接中间经过多少跳，在发包端看起来和直连的链路没有区别，只要rtt和瓶颈速率相等。两个物理限制，RTprop（round-trip propagation time）和BtlBw（bottleneck bandwidth）。

图1显示了RTT和上送速率与inflight数据大小的关系。

rtt与inflight

蓝线表示稳定的rtt值的极小值，数据量还很小时，数据的加入与离开没有任何的排队。
绿线表示链路上的buffer已经被填满，后续加入的数据要开始排队，排多久呢？就是斜率是怎么计算得来的。

• 空闲时，每秒最多处理BtlBw字节数据，且缓冲区没有任何填充，假设RTT为1s，那么inflight就是BtlBw个字节
• 那么多加入1个字节，这个字节将会被放入缓冲区，需要等待前面的数据全部处理完，也就是1+1/BtlBw秒，
• 斜率等于纵坐标差值除以横坐标差值，横坐标差值为1，纵坐标差值为1/BtlBw。

红线表示链路上的缓冲区已经填满，开始丢包，rtt值肯定比绿线增加快。

上送速率和inflight

蓝线表示上送速率还取决app的发包速率，因为此时还很空闲。斜率的计算:

• 每个字节数据的往返时间肯定为RTT，比如是1s
• 因为还没开始填充链路缓冲区，所以每增加1个字节，上送字节数就加1，但是时间不变，还是RTT
• 跟之前一样，斜率还是纵坐标的变化，变化为(x+1)/RTT-(x)/RTT = 1/RTT

绿线表示开始填充链路上的缓冲区，但是还没填满，速率已达到上限且稳定。
红线表示链路上的缓冲区已被填充满，开始丢包，速率不可预测，但不可能大于上限。

图1中的灰色区域是不可能出现的，rtt值不可能小于理论上限，瓶颈带宽不可能大于理论上限，不要考虑链路的变化。

所以为了链路上一直都是通畅的，不应该去使用链路上的缓冲，保持rtt一直都是最小值，但是可以以最大的速率BtlBw发包。图中标示出了BBR算法和基于丢包的拥塞控制算法的稳定点。可以想象，基于丢包的拥塞控制算法，出现丢包才认为链路拥塞，那么必然会进入红色区域，但是为了链路拥塞应该远离这个区域。
传统的BDP = BtlBw * RTprop，带宽时延积，肥长管道，最大发送窗口，等等一系列的名称。
1979年的时候， Leonard Kleinrock曾提出过这个最优点，但是很遗憾，被
Jeffrey M. Jaffe证明不可能实现一个分布式算法找到这个点。这个证明直接把研究方向从查找最优点转移到了如何避免拥塞。
google团队开始研究如何找到这个最优点。根据测量得到的RTprop和BtlBw，实现一个拥塞控制，而不再是基于传统的丢包或者时延。
这张图十分重要，后续所有的实现和估计以及时机全部来自这张图。

BtlBw计算

一个连接以最大的吞吐量和最小的时延（条件1）运行时，报文到达速率等于BtlBw，inflight（条件2） = BtlBw × RTprop。
条件1 保证了带宽利用率100%，条件2 保证了管道上一定有数据，但是又不超过管道容量。单独的条件1 不能保证链路上没有积压，比如一个连接以10pps向一个速率只有5pps的管道发包，就会造成一直有5个包的积压。类似地，条件2 也不能保证没有积压，还是刚才的例子，一个连接以BDP/2的爆发速率发送BDP字节数据，但是会得到平均BDP/4的积压。所以为了保证积压最少，需要同时满足以上两个条件。
其实对于条件2的例子举得不太好，没有描述清楚，大概意思就是说一样是100pps，一次性发送100个包和分两次50个包的效果是不一样的。例子可能是作者测试得到的。

上式是一般的RTT测量方式的展开，$\eta$η大于0表示链路上有噪声，延迟ack和ack聚合都有可能。RTprop是一条链路的物理属性，只有链路改变的时候才会改变。链路改变的时间间隔远大于RTprop，所以一个无偏的有效的RTprop估计器如下：

上式表示在一定范围的时间内计算得到的RTT最小值用来模拟RTprop，时间窗口大小一般是一个RTT，但是文章写的是数十秒到几分钟，这不现实，对发包影响太大。有关最小值或者最大值在时间窗口内的过滤可以参考我的另一篇文章Linux内核win_minmax代码解读.
不像RTT，没有TCP规范要求实现跟踪BtlBw的值，BBR采用报文上送速率来模拟BtlBw。当收到ack的时候，根据发包时间，最小确认序号的发包时间，和最大确认序号的发包时间，更新RTT和发包速率，发包速率等于被确认包数量/总时间。deliveryRate = Δdelivered/Δt。这个速率肯定小于瓶颈速率，因为Δt肯定大于实际往返总时间，也就是说，这个估计值的上限是BtlBw。

上式表示的是在一定时间范围内的上送速率最大值模拟BtlBw，时间窗口大小一般是RTT的6到10倍。
这两个值是完全独立的，这个独立性要求了需要这两个值共同来决定发包行为。通过图1，我们可以看出RTT的估计在app受限阶段估计，而BtlBw在带宽受限阶段估计，所以两者是不可以同时测量的。因为这两个值实时变化，所以在s实现上任何一个测量值都有老化时间。

适配数据包流和上送路径

这个标题有点拗口，文章写的就是BBR的实现。

收到ack的处理

具体地，更新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判断，其中包含了BtlBw是否有增大，如果有增大，则无条件更新，根据之前的证明，计算得到的BtlBw肯定小于理论BtlBw，不用考虑偏大的事情；如果没有增大，则第二个条件是能够被记录在max结构体内的肯定是非app受限的情况，因为受限的情况计算得到的BtlBw比BtlBw小很多，而如果不加这个限制进行更新的话就会导致一个很慢的发送速率。至少要比默认值大，计算得到的可能比默认值小。

数据发送时的处理

为了使数据发送速率和离开速率相匹配，BBR会调整每个数据包的发送速率。在BBR算法中，pacing是算法实现的基础，是主要的控制参数，辅助参数cwnd_gain会限制inflight在BDP的一定的倍数以内。
在linux中，pacing通过高效的FQ队列实现，后面还会再写一篇有关FQ队列的文章。
下面是发送时的伪码：

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)

这里的pacing是通过限时来控制的，而且是一个包一个包发送的，下一个包的发送超时在本次发送字节数/BtlBw。简单，但是可能会导致频繁超时。

稳态表现

发包速率和能发多少数据，单纯是由估计得到的RTprop和BtlBw决定的，所以这两个值的估计器还需要自动调整配合瓶颈限制。所以，BBR有一种自适应的控制环，如图2。
从图中可以看到pacing的大小是变化的，中间有一个rtt时间内是BtlBw的1.25倍，如果在这个速率下发包估计得到的BtlBw的确变大了，则更新BtlBw，否则不变。下一个rtt的增益系数为0.75，正是为了上一个rtt导致的积压准备的，总体来看，平均速率还是BtlBw。
BBR能够最小化时延是因为大部分时间inflight的数据量最多一个BDP，速率控制在BtlBw内。
图3展示了BBR算法如果检测到带宽变化，并自动增加或者降低发送速度和发送数据量的。

BBR是Max-plus控制系统的简单实例，这是一种基于非标准代数的新控制方法。图2中的增益系数控制环，可以让系统自动地适应带宽的变化。

一个BBR流的启动流程

与传统的慢启动和拥塞控制算法不同，BBR仅仅基于上一节中所描述的BtlBw和RTprop估计值，通过一系列预定义的状态和其对应的增益系数及退出条件，来响应传统的事件，比如快速恢复，慢启动等等。
BBR的启动流程（STARTUP状态）通过二分查找的方式，当估计BtlBw变大时，将估计BtlBw*2/ln2作为BtlBw。这个方式需要耗时log2BDP RTT的时间，并且在链路上堆积了两倍的BDP数据。所以需要一个DRAIN状态，来排空这个积压，当inflight数据量到达一个BDP的时候进入稳态PROBEBW。

图4展示了BBR算法的整个生命流程，启动绿线是发送者，蓝线是发送者接收到ack，红线是CUBIC算法的表现，可以看到在慢启动流程两者接近，但是进入稳态之后，BBR算法的延迟显然低于CUBIC算法。
可以想象，CUBIC进入稳态之后，在感知到丢包时又会退出稳态，降低自己的发包速率，但是BBR算法不会。下图展示了在进入稳态后两个算法的RTT对比，

多路BBR流共享一个带宽时的表现

实际结果如下图，

可以看到，一开始各个流的吞吐是不一致的，但是在一段时间之后各个流表现几乎一致。其中向下的一个三角是所有的流同时在测量自己的RTT。
前面图2中的增益环，会让各个流学习到自己该分得的公平份额。但是对于后续新加入的流会高估自己的RTT值，因为他加入是缓冲区已经满了。
之前有说过，RTprop和BtlBw都有老化时间，那么当RTprop老化之后，会自动进入PROBERTT状态，该状态下会将inflight数据量减少至4个包，至少维持一个RTT，然后再回到PROBEBW；当大流量的流一旦进入ProbeRTT状态，放空自己的队列，其他流马上会看到一个新的RTT值，促使自己也进入PROBERTT状态，所以可以看到图中的倒三角。
退出PROBERTT之后，也会重新估计PROBEBW，所有流的pacing都是一样的，所以最终所有流会公平地分享一个带宽。
BBR算法同步所有的流在空闲期，但是传统的算法同步所有流在拥塞时。

后面是一大堆google的测试环境数据

这个不展开。总的来讲，BBR提高了性能2-75倍，放开缓冲区可以上百倍。

加一个BBR状态机

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

总结

BBR算法，将TCP或者其他任何想要控制流量的用户态协议，保证其运行在最优点，而不是完全占用链路缓存的点，个人觉得这就是BBR的重点，预防拥塞而不是探测发送拥塞的点，探测拥塞必须先到达拥塞。
BBR整体对外体现为两点，一个是pacing_rate，一个是拥塞窗口cwnd，不出意外可以很好地在最优点工作。但是，在链路缓存很深的情况下，并且同时存在大量CUBIC算法流的情况下，BBR会被饿死，因为链路上的缓存会被CUBIC填满，导致BBR预估到RTT很大。

后续

后面会再写一篇FQ队列和linux代码实现，状态机也没有好好分析。

-------------
探花原创