拥塞控制之BBR

之前用vultr搭建vps的时候用到过BBR加速，这篇文章深入介绍一下拥塞控制BBR的算法。

  BBR是Google在2016年提出的一种拥塞控制算法。丢包即拥塞的思想已经沿用了很多年，很多拥塞控制算法也是基于此的，比如当前Linux kernel的默认拥塞控制算法CUBIC，还有Reno都是基于这一思想进行的拥塞控制。

  如上图所示，第1条灰色竖线，是瓶颈路由器的缓冲队列刚刚开始积压时的节点。随着内存的不断降价，路由器设备的缓冲队列也会越来越大，CUBIC算法会造成更大的RTT时延！而BBR通过检测RTprop和BtlBw来实现拥塞控制。

要达到highest throughput和lowest delay，connection必须同时满足两个条件：

• 包的瓶颈到达速率等于瓶颈带宽
• 总的inflight数据等于带宽时延积

因为BtlBw和RTprop在整个过程中一直是变动的，所以需要一直不断的测量。在任何时刻t：

$$R T T_{t}=R T \text { prop }_{t}+\eta_{t}$$

这里η>=0表示‘noise’，比如接收端的延迟ack策略，ack aggregation策略等。因此RTprop是不可能准确测量的，只能估算，像大多数算法测量最小RTT做的那样：

$$\text { RTprop }^{\prime}=R T \text { prop }+\min \left(\eta_{t}\right)=\min \left(R T T_{t}\right) \quad \forall t \in\left[T-W_{R}, T\right]$$

根据从receiver返回的ack，我们可以知道当前ack确认数据包的RTT和离开sender留存在网络中的确切数据包数。因为我们可以准确知道当前的发送序号snd_nxt，以及其确认序号snd_una，如果开启了SACK也可以准确知道，只不过需要walk一遍SACK段。这样我们便可以测量平均delivery rate:deliveryRate=Δdelivered/Δt。在这个过程中delivered是可以准确知道的，而Δt则会大于真实interval，因为受网络噪声的影响，所以deliveryrate<=bottleneckrate，那么我们可以这样评估BtlBw:

$${B t l B} w^{\prime}=\max \left(\text {delivery Rate}_{t}\right) \quad \forall t \in\left[T-W_{B}, T\right]$$

  综上所述，BBR的组成：

• 即时带宽的计算：应答了多少数据，记为delivered；应答delivered这么多数据所用的时间，记为interval_us，两者相除
• pipe状态机：
  
• pacing rate和cwnd的计算：pacing rate是使用时间窗口内(默认10轮采样)最大BW。上一次采样的即时BW，用它来在可能的情况下更新时间窗口内的BW采样值集合。这次能否按照这个时间窗口内最大BW发送数据呢？这样看当前的增益系数的值，设为G，那么BWG就是pacing rate的值。我们采用BDPG’就算出了cwnd，这里的G’是cwnd的增益系数，与带宽增益系数含义一样，根据bbr的状态机来获取。
  

每一个ack都会提供一个新的RTT和delivery rate值，用来更新RTprop和BtlBw，伪代码如下：

function onAck(packet)
    rtt = now - packet.sendtime
    update_min_filter(RTpropFilter,rtt)
    delivered += packet.size
    delivered_time = now
    deliveredRate = (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

为了使packet-arrival rate和bottleneck link’s departure rate相匹配，BBR必须paces每一个数据包。pacing_rate是BBR的主要控制参数，另外一个参数是cwnd_gain，用来限定inflight为小倍数的BDP，伪代码如下：

function send(packet)
    bdp = BtlBwFilter.currentMax * RTpropFilter.currentMin
    if( infilght >= 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_limted_until > 0)
        packet.sendtime = now
        packet.delivered = delivered
        packet.delivered_time = delivered_time
        ship(packet)
        nextSendTime = now + packet.size / (pacing_gain * BtlBwFIlter.currentMax)
    timerCallbackAt(sned,nextSendTime)

pacing_gain[5/4,3/4,1,1,1,1,1,1]便是决定链路速率调整的关键周期数组。

end!

赏

谢谢大家的打赏！

支付宝