BBR -- Congestion-Based Congestion Control

BBR: Congestion-Based Congestion Control

0x00 引言

这次来看一个重量级的拥塞控制的算法：Google开发的BBR算法，在Linux 4.9之后在基于Linux内核的系统上面变得可用。这个算法在一诞生的时候就收到了很大的关注，算法本身没有发表论文，而是一篇ACM杂志的文章[1，而且这篇文章感觉写得挺迷的]。BBR算法和前面看到的TIMELY算法不同，BBR是为正常情况下都存在一定的丢包可能性的网络设计的算法，最常见的就是长肥网络。而TIMELY算法面向的数据中心网络一般不具有这些特点。另外一个区别就是BBR是一个已经实用了的算法，而TIMELY应该只呆在实验室里面(⁎⁍̴̛ᴗ⁍̴̛⁎)。不明白BBR公平性如何？？

0x01 基本思路

BBR主要基于以下的现在的一些拥塞控制算法在一些网络特别是广域网上面存在的一些问题：

目前Linux默认使用Cubic算法以及经典的TCP的拥塞控制算法如New Reno都是基于丢包的，而这些基于丢包的算法的一个缺点就是当线路越“长肥“时，为了充分利用带宽对丢包率的要求就越高，但是矛盾的是越是“长肥”得网络，出现丢包的可能性就越高。这样这样的算法就存在不少的问题。
另外一个问题可以理解为基于丢包的一些算法对拥塞的发生反应太迟(联系前面的TIMELY算法，使用变化率的方式，在数据中心网络中已经有不少的Paper讨论处理了这类情况，但是广域网情况太复杂，不好直接处理)，如果这里将网络想象称为有一定容量的管子，原来的一些算法就是直接“灌”到这个管子溢出时才开始处理，但是这个时候并不是最佳的处理拥塞的时候，因为太迟了。下面的图表现了这个现象[1],

bbr-buffer

显而易见的一点就是在一个TCP流中，决定最大带宽的时线路上面最小的带宽瓶颈的地方。一个要实现最大化带宽和最小化延时的拥塞控制算法有这样两点要求：1. 发送的速率要和这个线路上面带宽瓶颈的地方的带宽一致；2. 总共的在传输过程中的数据的量要等于瓶颈带宽(BtlBw) *RTprop(round-trip propagation time)。第一个条件保证了最大化带宽的利用，第二点保证了有足够的数据利用线路但是又不至于过度占据路线上面的buffer。BBR的一个核心就是测量BtlBw和RTprop的值。BtlBw和RTprop在一个连接中时随着时间变化的，所以这两个值的测量会在连接的生命周期内一直测量。另外的一个问题这两个是不能同时测量的，因为测量其中的一个会影响到另外的一个值：为了测量BtlBw就是尽量多发送数据以探测最大的带宽，而这样的话就会影响到RTprop的值；而为了测量RTprop，输送的数据越少就越精确。所以这里这两个值的测量逻辑上是分开的，

RTprop，实际的连接的RTT来自于RTprop和其它的一些岩石，为了更精确的测量RTprop，BBR使用下面的公式 \(\\ RTT_{t} = RTprop + \eta_{t}, 这里的\eta_{t}为> 0的一个值，会随着时间变化，\\ 令 \widehat{RTprop} = RTprop + \min(\eta_{t}) = \min(RTT_{t}), \forall t \in [T-W_{B}, T]\\\) 这里的W-B为一个时间窗口，一班为数十秒or几分钟，也就是说RTprop就是测量到的RTT-t的最小值。
BtlBw与此相反BtlBw则是这个时间窗口内测量到的带宽的最大值。这里的测量的带宽使用一个段时间内发送的数据量定义， \(\\ \widehat{BtlBw} = \max(delivaryRate), \forall t \in [T-W_{B}, T]\\ delivaryRate = \frac{\triangle delivered}{\triangle t} \\\)

0x02 核心算法

BBR的核心算法由两个部分组成：

接受到ACK的时候，伪代码如下：

  def onAck(packet)
    rtt = now - packet.sendtime
    update_min_filter(RTpropFilter, rtt)
    delivered += packet.size
    delivered_time = now
    deliveryRate = (delivered - packet.delivered) / (now - packet.delivered_time) 
    if (deliveryRate > BtlBwFilter.currentMax || ! packet.app_limited)     
        update_max_filter(BtlBwFilter,deliveryRate) 
    if (app_limited_until > 0)
        app_limited_until - = packet.size

这里就是根据接受到的ACK可以获取到的值来对一些数据进行更新；

发送数据的时候，伪代码如下，

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

这里借本书就是根据前面的的的数据来决定数据包发送的情况。从这里的伪代码能得到的信息比较少。

四个状态

BBR算法的四个状态：启动(startup)、排空(drain)、带宽探测(ProbeBW)和时延探测(ProbeRTT，时间上就是为了探测RTprop)，理解这四个状态能帮助更好的理解BBR算法：

启动，这里和常见的拥塞控制的算法一样，就是从一个很小的值开始指数级别的增加。这里和一般的方法的区别在与它不是根据丢包来确定已经达到应该要进入拥塞避免的阶段了，而是根据有效带宽是否增长。在有效的带宽不在增长时，进入拥塞避免阶段。这里时间上使用的就是投递的速率，在3次测量发现投递速率不在增长的时候进入拥塞避免阶段。注意这里时3次测量，根据BBR的工作方式，这个时候已经发送了3倍BtlBw*RTprop的数据，所以要将多发送的数据排空，从而进入排空阶段，如下面的图所示；
排空，排空使用的是指数方式投递速率的方式，当发现RTT不在降低的时候，进入下一阶段；
带宽探测，BBR的大部分时间都处在被称为稳定状态。稳定的状态所做的工作一般即使带宽探测，使用的方法是以8个RTT为周期，先增大投递的速率(增加25%，这个速度比通常的算法都有激进一些)。在下一个RTT降低投递速率(使用估计的BtlBw，在此基础上降低25%)来排空操作。下面的6个RTT时间就使用估计的BtlBw来作为投递速率的依据；
时延探测，在一段时间内(默认是10s)，BBR如果发现估计的RTprop没有变化，就进入RTprop探测的阶段。使用的方法就是以很低的速率发送数据包，默认就是发送4个，使用的时间为200ms(也就是占用了2%的时间，这里在RTT很大的时候可能对发送有负面的影响)。

bbr-drain

0x03 评估

这个可以参考网上的一些使用了BBR算法之后获得的性能上面的进步的信息。在存在一定丢包率的线路上面，BBR的优势非常明显(没必要过度吹捧BBR)：

bbr-perf

参考

BBR: Congestion-Based Congestion Control, ACM Queue, september-october 2016.