愿历尽千帆 归来仍少年

网络 | 拥塞控制算法之BBR

字数统计: 5,611阅读时长: 23 min
2022/03/01

TCP BBR(Bottleneck Bandwidth and Round-trip propagation time)是由Google 设计,于2016年发布的拥塞算法。
以往的大部分拥塞控制算法都是基于丢包来作为降低传输速率的信号,而BBR 则基于模型主动探测。
目前已经在Google 内部大范围使用并随着linux 4.9 版本正式发布。

Bufferbloat

在讨论BBR 之前不得不先说下Bufferbloat,在BBR 出来之前的拥塞控制算法无一例外都和网络缓存耦合在了一起,所以都会存在发生Bufferbloat 的情况。

关于bufferbloat的定义

Bufferbloat is a cause of high latency and jitter in packet-switched networks caused by excess buffering of packets. Bufferbloat can also cause packet delay variation (also known as jitter), as well as reduce the overall network throughput. When a router or switch is configured to use excessively large buffers, even very high-speed networks can become practically unusable for many interactive applications like voice over IP (VoIP), audio streaming, online gaming, and even ordinary web browsing.
Some communications equipment manufacturers designed unnecessarily large buffers into some of their network products. In such equipment, bufferbloat occurs when a network link becomes congested, causing packets to become queued for long periods in these oversized buffers. In a first-in first-out queuing system, overly large buffers result in longer queues and higher latency, and do not improve network throughput. It can also be induced by specific slow-speed connections hindering the ontime delivery of other packets.

大多数的拥塞控制算法都是基于丢包来测算带宽,有丢包发生便会降低传输速率。
中间网络设备引入大的缓冲区虽然可以降低丢包的发生,但是会导致TCP 对网络阻塞敏感度的降低,直到缓冲区满了并开始出现丢包,TCP 才开始降窗。

另外,由于缓冲区的增大,会导致延迟增加。试着想象一下如果这个缓冲区是一个非常大的的数据池,那么延迟将会上升到一个非常糟糕的地步。

你可能会觉得Bufferbloat 的产生似乎是一个错误。

那么它的产生历史缘由是什么呢?

在以前的互联网上,交换机可能总是拥有比服务器更快的网卡,所以这些位于互联网中间层的服务器也可能比客户端更快,并且并不能对客户端发送信息包的速率有多大影响。
很显然今天已经不是这样的了!众所周知,今天的计算机相比于 5 年前的计算机在速度上并没有多大的提升(我们遇到了某些有关光速的问题)。所以我想路由器上的大型交换机并不会在速度上大幅领先于数据中心里服务器上的网卡。

(摘自Van Jacobson的netdev演讲)

如何理解这段话呢?
早期终端设备和网络核心交换设备性能上存在明显的悬殊,像思科这类厂商,他们的中间路由设备的处理能力是能够甩开一众终端设备的。
在这个时期,中间设备的缓存就显得不那么重要了,可能只需很少的缓存就够用了,对于终端设备而言,只需要考虑发送的尽可能的快就行!
随着时代的发展,终端处理器以及网卡性能的不断提升,不断缩小了和中间转发设备性能上的差距。

这个时候问题就出现了:
中间转发设备似乎不太来得及处理数据包了!

这就需要想办法尽快解决没有来得及处理的数据包,提升处理器性能或增加处理器都是办法,但这些方法都没有直接搞一个大缓存来的简单又有性价比。
这样一来,引入Buffer 其实违背了中间转发设备本身的角色定位,它的角色应该只是转发,而不应该成为一个缓存设备。

对于Bufferbloat,你可以鄙视它,甚至厌恶它,但它却是时代变迁下的产物。

BBR 原理

BBR 的诞生解决了Bufferbloat 问题,关于它的诞生缘由,BBR 论文[3]是这样描述的:

These problems result from a design choice made when TCP congestion control was created in the 1980s—interpreting packet loss as “congestion.”13 This equivalence was true at the time but was because of technology limitations, not first principles. As NICs (network interface controllers) evolved from Mbps to Gbps and memory chips from KB to GB, the relationship between packet loss and congestion became more tenuous.
Today TCP’s loss-based congestion control—even with the current best of breed, CUBIC11—is the primary cause of these problems. When bottleneck buffers are large, loss-based congestion control keeps them full, causing bufferbloat. When bottleneck buffers are small, loss-based congestion control misinterprets loss as a signal of congestion, leading to low throughput. Fixing these problems requires an alternative to loss-based congestion control. Finding this alternative requires an understanding of where and how network congestion originates.

(摘自BBR论文<BBR: Congestion-Based Congestion Control>)

简单的理解就是基于丢包的拥塞控制算法,在缓冲区缓存比较大的时候,会使得缓冲区被填满最终造成bufferbloat。而当缓冲区缓存较小时,基于丢包的拥塞算法可能会误判为此时网络拥塞,并降低吞吐量,所以要想解决这种问题,就需要找到一种不是基于丢包的拥塞控制算法。
于是,BBR 诞生了。

在讲解BBR之前,先了解几个参数名词,这几个名词会贯穿本文

  1. RTprop(Round-trippropagation time):最小时延,一个来回所以其实是两倍时延
  2. BtlBw(bottleneck bandwidth):瓶颈带宽
  3. BDP = BtlBw * RTprop:整条链路所能存储的数据值(不含路由缓存)
  4. BtlBufSize :链路上所有的中间路由缓存之和
    BBR论文中对两者关系用了一个比喻来说明
    If the network path were a physical pipe, RTprop would be its length and BtlBw its minimum diameter.
    其实根据这个定义,我们很容易想到:
    如果当前的实际发送速率乘以延迟得到的值越接近 BDP 说明算法的效率越高。

下图是这几个参数之间的关系

(这张图原图摘自BBR论文,笔者加了一些自己的理解在上面)

个人理解

  1. 数据刚开始传输时,这个时候显然数据量未填充满也就是未达到BDP,此时传输速率持续上升,RTT处于最优状态也就是最小时延,这是一个传输通畅的阶段。
  2. 当数据填充超过BDP时,数据会使用到路由的缓存区,这个时候RTT会开始上升,但是发送速率还维持不变,这个阶段处于一个缓冲阶段,一旦越过BDP分界线就说明拥塞开始出现了。
  3. 当数据填充超过(BDP+BtlBufSize)大小后,此时没有地方能够存储下没有来得及发送的数据,丢包开始产生!关于图中笔者标记出来的丢包临界点,基于丢包的拥塞算法几乎都是以此为收敛点,尽可能的填充满网络和缓存,认为此举是可以提高网络利用率和减少丢包,一旦出现丢包,就开始降低数据的发送量并再次向这个错误的收敛靠近。
    BBR的目标收敛点都是围绕着图中理想收敛点位置,而基于丢包的cubic/Reno等算法都是围绕着如何收敛到丢包临界点上,因为它们总是将缓存考虑在内,这其实是一个错误的做法。BBR

关于图中的斜率,个人理解如下:
假设某一时刻实际发送数据大小为S,实际带宽为R,R必定是 <= BtlBw,实际时延设为T>=RTprop
这一时刻的数据量 S=T*R, 所以这里T/S = 1/R >= 1/BtlBw,所以实际情况下斜率往往是比上半图中的更陡峭,同理下半图的斜率 R/S = 1/T <= 1/RTprop,所以实际情况下下半图的斜率往往会更平缓些,图中的阴影部分是不可达的。

关于发送速率的计算方式,BBR论文中是这样解释的

Unlike RTT, nothing in the TCP spec requires implementations to track bottleneck bandwidth, but a good estimate results from tracking delivery rate. When the ack for some packet arrives back at the sender, it conveys that packet’s RTT and announces the delivery of data inflight when that packet departed. Average delivery rate between send and ack is the ratio of data delivered to time elapsed: deliveryRate = Δdelivered/Δt. This rate must be ≤ the bottleneck rate (the arrival amount is known exactly so all the uncertainty is in the Δt, which must be ≥ the true arrival interval; thus, the ratio must be ≤ the true delivery rate, which is, in turn, upper-bounded by the bottleneck capacity).

简单理解为

  1. 应答了多少数据,记为delivered;
  2. 应答delivered这么多数据所用时间,记为interval_us。
    将上述二者相除,就能得到带宽:bw = delivered/interval_us

从前面那张图我们可以发现,如果测量BtlBw则需要填满buffer,测量RTprop 需要排空buffer也就是不能使用buffer,所以BBR的BtlBw和RTprop无法同时测量的。
那么BBR是怎么做得呢?下面会结合源码分别进行分析

Startup
1
2
3
4
5
6
/* We use a high_gain value of 2/ln(2) because it's the smallest pacing gain
* that will allow a smoothly increasing pacing rate that will double each RTT
* and send the same number of packets per RTT that an un-paced, slow-starting
* Reno or CUBIC flow would:
*/
static const int bbr_high_gain = BBR_UNIT * 2885 / 1000 + 1;

这个值主要用于计算pacing_rate,至于这个初始值为何是2/ln(2)这样一个写死的值,笔者翻阅了BBR论文并找到没有提及原因的地方,猜测可能是实测算出的最优值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* Initialize pacing rate to: high_gain * init_cwnd / RTT. */
static void bbr_init_pacing_rate_from_rtt(struct sock *sk)
{
struct tcp_sock *tp = tcp_sk(sk);
struct bbr *bbr = inet_csk_ca(sk);
u64 bw;
u32 rtt_us;

if (tp->srtt_us) { /* any RTT sample yet? */
rtt_us = max(tp->srtt_us >> 3, 1U);
bbr->has_seen_rtt = 1;
} else { /* no RTT sample yet */
rtt_us = USEC_PER_MSEC; /* use nominal default RTT */
}
bw = (u64)tp->snd_cwnd * BW_UNIT;
do_div(bw, rtt_us);
sk->sk_pacing_rate = bbr_bw_to_pacing_rate(sk, bw, bbr_high_gain);
}

在Startup阶段,pacing_rate在每次收到一个ACK后,都会提高bbr_high_gain的值。
BBR计算拥塞窗口是用“当前采集到的速率”乘以“当前采集到的最小RTT”来计算的,这就造成了“当前发送窗口”和“当前已经提高的速率”之间的不匹配,所以,计算拥塞窗口的时候,gain因子也必须是bbr_high_gain,从而可以吸收掉速率的实际提升.

ProbeRTT

到这里,我们知道要想达到理想收敛点,就需要找到最小时延和瓶颈带宽
我们先来讨论下BBR是如何找到最小RTT的
如果了解过Vegas算法原理的人,应该知道Vegas对时延的波动比较敏感,即便一次不是真的拥塞导致的RTT增加都会导致其降窗。
那么BBR是基于时延找最小RTT的吗?并不是,下面会讲述

最小RTT的有效时间是10s

1
2
3
4
/* Window length of min_rtt filter (in sec): */
static const u32 bbr_min_rtt_win_sec = 10;
/* Minimum time (in ms) spent at bbr_cwnd_min_target in BBR_PROBE_RTT mode: */
static const u32 bbr_probe_rtt_mode_ms = 200;

探测最小RTT需要最少4个数据包,这是为了兼顾延迟ACK。

1
2
3
4
5
/* Try to keep at least this many packets in flight, if things go smoothly. For
* smooth functioning, a sliding window protocol ACKing every other packet
* needs at least 4 packets in flight:
*/
static const u32 bbr_cwnd_min_target = 4;

更新最小RTT核心函数 bbr_update_min_rtt,这个函数较长,我们将其拆分开来进行讨论

1.如果本次RTT时间小于最小RTT时间值或者最小RTT时间有效时间到了,则更新最小RTT值

1
2
3
4
5
6
7
8
9
/* Track min RTT seen in the min_rtt_win_sec filter window: */
filter_expired = after(tcp_jiffies32,
bbr->min_rtt_stamp + bbr_min_rtt_win_sec * HZ);
if (rs->rtt_us >= 0 &&
(rs->rtt_us < bbr->min_rtt_us ||
(filter_expired && !rs->is_ack_delayed))) {
bbr->min_rtt_us = rs->rtt_us;
bbr->min_rtt_stamp = tcp_jiffies32;
}

2.最小RTT时间过期了且当前未处于PROBE_RTT模式,则切换模式到RTT,降低发送速率

1
2
3
4
5
6
if (bbr_probe_rtt_mode_ms > 0 && filter_expired &&
!bbr->idle_restart && bbr->mode != BBR_PROBE_RTT) {
bbr->mode = BBR_PROBE_RTT; /* dip, drain queue */
bbr_save_cwnd(sk); /* note cwnd so we can restore it */
bbr->probe_rtt_done_stamp = 0;
}

3.如果此时处于PROBE_RTT模式下,首先设置app_limited 是为了表面这个时间区域内BW参与最大值计算。inflight数据包小于等于bbr_cwnd_min_target即四个数据包时,同时满足一些其它条件后,开始更新本次最小RTT侦测结束时间戳,也就是当前时间加上200ms,并将本次已delivered数据赋值给下个RTT。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if (bbr->mode == BBR_PROBE_RTT) {
/* Ignore low rate samples during this mode. */
tp->app_limited =
(tp->delivered + tcp_packets_in_flight(tp)) ? : 1;
/* Maintain min packets in flight for max(200 ms, 1 round). */
if (!bbr->probe_rtt_done_stamp &&
tcp_packets_in_flight(tp) <= bbr_cwnd_min_target) {
bbr->probe_rtt_done_stamp = tcp_jiffies32 +
msecs_to_jiffies(bbr_probe_rtt_mode_ms);
bbr->probe_rtt_round_done = 0;
bbr->next_rtt_delivered = tp->delivered;
} else if (bbr->probe_rtt_done_stamp) {
if (bbr->round_start)
bbr->probe_rtt_round_done = 1;
if (bbr->probe_rtt_round_done)
bbr_check_probe_rtt_done(sk);
}
}
ProbeBW

增益系数数组

1
2
3
4
5
6
7
/* The pacing_gain values for the PROBE_BW gain cycle, to discover/share bw: */
static const int bbr_pacing_gain[] = {
BBR_UNIT * 5 / 4, /* probe for more available bw */
BBR_UNIT * 3 / 4, /* drain queue and/or yield bw to other flows */
BBR_UNIT, BBR_UNIT, BBR_UNIT, /* cruise at 1.0*bw to utilize pipe, */
BBR_UNIT, BBR_UNIT, BBR_UNIT /* without creating excess queue... */
};
  1. bbr_pacing_gain[0]
    这个阶段gain的值是1.25,也是BBR的初始值,这个阶段意味着BBR会试图增加发送量,尽可能多的占用带宽,占满新进的多余的带宽,目的是提升资源的利用率,不过这个阶段可能会出现队列的产生以及RTT变长的情况。
    bbr_pacing_gain[0]退出条件时:
    已经运行超过了一个最小RTT时间并且要么发生了丢包,要么本次ACK到来前的inflight的值已经等于窗口值了。[引用2]
  2. bbr_pacing_gain[1]
    bbr_pacing_gain[1] 这个阶段gain的值为0.75,假设此时正处于增益阶段,此时一个新的连接发起,可能会导致正处于增益阶段的连接的inflight满载,这个时候就需要切换到bbr_pacing_gain[1] 状态,在出让部分带宽后尽快进入平稳期,这个阶段体现了BBR的公平性。
    这个阶段时间较短,一旦完成出让带宽就退出,最多停留不超过一个最短RTT时间。
  3. bbr_pacing_gain[2]…. bbr_pacing_gain[7]
    这个阶段代表的是平稳期,至少停留6个RTT

进入PROBE_BW状态后会反复的在上面三个步骤之间循环:加速、减速、匀速。。。。

(图片摘自BBR论文,笔者加了些理解)

这个时候,设想下如果上面的数组中移除掉后面的六个元素,也就是移除平稳期,会出现什么样的情况呢?
因为一旦进入平稳期由于至少停留6个RTT的限制,导致在这期间如果有富余带宽,BBR是无法抢占的,所以如果一旦移除到平稳期,带来的就是更快的发现富余带宽,代价就是比较网络比较颠簸,对于一些如下载类的业务有益,不适用于如直播类业务。

关于bbr_pacing_gain增益数组的作用,归纳下来就是:
BBR会尽可能的抢占更多带宽,一旦有了新的连接之后,如果出现本次窗口估值等于上次的inflight值,说明这个时候带宽被填满了。 此时旧连接的gain值下降进而让出部分带宽给新连接,在至少6个RTT周期内也就是平稳期,这个阶段旧连接不会抢占更多带宽,直到6个RTT后,旧连接会试图抢占更多带宽,周而复始。

bbr_update_bw 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/* Estimate the bandwidth based on how fast packets are delivered */
static void bbr_update_bw(struct sock *sk, const struct rate_sample *rs)
{
struct tcp_sock *tp = tcp_sk(sk);
struct bbr *bbr = inet_csk_ca(sk);
u64 bw;

bbr->round_start = 0;
if (rs->delivered < 0 || rs->interval_us <= 0)
return; /* Not a valid observation */

/* See if we've reached the next RTT */
if (!before(rs->prior_delivered, bbr->next_rtt_delivered)) {
bbr->next_rtt_delivered = tp->delivered;
bbr->rtt_cnt++;
bbr->round_start = 1;
bbr->packet_conservation = 0;
}

bbr_lt_bw_sampling(sk, rs);

/* Divide delivered by the interval to find a (lower bound) bottleneck
* bandwidth sample. Delivered is in packets and interval_us in uS and
* ratio will be <<1 for most connections. So delivered is first scaled.
*/
//计算当前实际带宽
bw = div64_long((u64)rs->delivered * BW_UNIT, rs->interval_us);

/* If this sample is application-limited, it is likely to have a very
* low delivered count that represents application behavior rather than
* the available network rate. Such a sample could drag down estimated
* bw, causing needless slow-down. Thus, to continue to send at the
* last measured network rate, we filter out app-limited samples unless
* they describe the path bw at least as well as our bw model.
*
* So the goal during app-limited phase is to proceed with the best
* network rate no matter how long. We automatically leave this
* phase when app writes faster than the network can deliver :)
*/
//加入新的样本
if (!rs->is_app_limited || bw >= bbr_max_bw(sk)) {
/* Incorporate new sample into our max bw filter. */
minmax_running_max(&bbr->bw, bbr_bw_rtts, bbr->rtt_cnt, bw);
}
}

这个函数主要做的事比较清晰,主要是更新RTT周期、通过已delivered数据 * BW_UNIT/采样时间得出带宽值,并将带宽和min rtt加入到新的RTT和BW样本。

通过对ProbeRTTProbeBW的分析,可以知道BBR其实大部分时候都是在ProbeBW和ProbeRTT状态之间切换,并且绝大部分时间是停留在ProbeBW上。
根据代码可以得到如下一个简要的图:

可以看出大部分时候都停留在ProbeBW上,在ProbeRTT停留的时间很短,这其实符合BBR的初衷:尽可能的多占用带宽并且尽量不占用缓存。

根据前面的代码梳理,画了一张状态机的流转图

如果我们用一个精简的图来看这个过程的话,大致如下

BBR 优缺点

从前面的讨论中,我们知道BBR的优势,也不难发现其劣势。

BBR 优势

1.在长传即大RTT场景下优势明显
有一种典型的场景便是”长肥管道”,在TCP连接中,较长的距离意味着RTT的增加,进而意味着窗口打开的更慢,对于像Cubic这类AIMD的拥塞算法而言,它们的慢启动过程会越长 ,这就是Reno家族算法的典型弊端。
另外,对于Cubic这类算法而言,更容易出现缓冲区被占满的情况,也就是我们前面提到的bufferbloat,这是为何呢?
一窗数据只有在得到ACK确认后才会清除,RTT越小意味着缓冲区能够越快腾出空间,发生bufferbloat概率也越低。反之RTT越大的话,越容易出现bufferbloat的情形
而BBR设计之初,就没有将中间缓存考虑在内,从本文前面的收敛图可以看出

  • BBR的理想带宽收敛点是在缓冲区即将被填充的时候,此时BtlBW最大,RTT最小
  • 而对于Reno家族算法而言,其收敛点是缓冲区被填满的时候,此时BtlBW最大,但RTT也最大。

归纳下来:
对于长肥管道这种场景,Cubic这类传统算法表现会异常脆弱,一旦有丢包立马械 投降,执行MD 过程,这个过程是一个快速降窗的过程,前功尽弃。
而BBR的优势在于不会导致bufferbloat,且对丢包不敏感使得其不会出现激进降窗的行为。

2.抢占带宽能力强
BBR其实大部分时候都是在ProbeBW和ProbeRTT状态之间切换,并且绝大部分时间是停留在ProbeBW上。ProbeBW阶段会不断的试探剩余可用带宽,短时间内占据更多的带宽。

3.平稳发送
由于其平稳期至少待够6个RTT周期才行,这使得该阶段的发送速率比较平稳,比较适合音视频领域比如视频直播这种对稳定性要求较高的场景。

BBR 不足之处

1.对带宽变化不敏感
从前面原理分析环节,我们知道BBR减损期会让出部分带宽,一旦这个时候被其它流占据了话,BBR要等到度过本地”漫长”的平稳期,等到下个增益周期才能发现。
也就是说BBR在ProbeBW状态下,只有在ProbeMore周期才能感受到带宽的变化,后面的ProbeDrain以及平稳期对于带宽的变化都无法感知,如果这个阶段实际带宽降低,BBR需要多个RTT周期才能收敛到实际的带宽位置。

2.ProbeRTT阶段导致发送速率下降太多
这个阶段由于只发四个包,导致发送速率迅速下降,虽然时间很短,但是如果应用在一些对实时性要求很高的音视频场景下,就会出现卡顿现象。
解决方案有多种,根据实际业务需要可以减少ProbeRTT时间甚至直接拿掉ProbeRTT阶段。

3.抗RTT抖动能力差
一个典型的场景便是BBR在WIFI弱网下表现不佳,这里的弱网不是指的是网络质量差,速度慢。
而是指的是WIFI场景下的稳定性相比于有线网络而言,逊色太多。由于无线网络是共享介质的,几乎无法在信号不冲突的前提下同时发送和接收。
所以在WIFI场景下,接入的终端设备一多,RTT抖动会越明显,这种情况下BBR测算出的BDP很可能就不准确了,可能会低于实际带宽数据。

综合来看:
个人理解目前为止并没有一种拥塞算法能够适应各种网络环境,是否选择BBR需要根据自己的业务场景需要。BBR存在不少优势的同时,也存在不少劣势。
应用BBR之后如存在问题,只要不是先天不足,都可以根据业务需要对BBR进行修改。
比如对于下载业务应用BBR的话是否可以将平稳期移除,这样虽然带来了网络颠簸,但是对于用户而言带来的变化时下载更快了。
再比如对于稳定性要求高的音视频业务,是否可以缩短ProbeRTT时间甚至直接拿掉ProbeRTT阶段,这样的话就不会存在ProbeRTT阶段发包速率掉下来导致的卡顿。

小结

至此,对于BBR的一个小结到此结束,由于理解水平有限,可能有不足或理解错误的地方,希望以后回顾时能够再完善下。

参考文章

  1. BBR论文 https://www.cis.upenn.edu/~cis553/files/BBR.pdf
  2. [引用1] Startup阶段拥塞窗口计算的滞后性
  3. [引用2] 从TCP拥塞本质看BBR算法及其收敛性
CATALOG
  1. 1. Bufferbloat
  2. 2. BBR 原理
    1. 2.1. Startup
    2. 2.2. ProbeRTT
    3. 2.3. ProbeBW
  3. 3. BBR 优缺点
    1. 3.1. BBR 优势
    2. 3.2. BBR 不足之处
  4. 4. 小结
  5. 5. 参考文章