传统TCP拥塞控制算法都是基于丢包的算法,例如收包加法增,丢包乘法减,然而基于丢包的算法无法达到理论的时延、带宽最优解。
谷歌在2016年提出了基于拥塞的BBR拥塞控制算法。BBR的思路在于利用估算的带宽和延迟直接推测拥塞程度从而计算滑动窗口。本文将从源码和论文两方面讲述BBR的原理与实现。
我们要先了解滑动窗口的理论基础,排队论中的Little's Law
当排队系统达到稳定后,
,这里的
代表排队者到达速率对应带宽,
代表排队者逗留时间对应时延,
表示队列容量对应所有流动的数据即inflight。
事实上,把packet看成一个个排队的消息。根据包守恒原则,稳定情况应该是每发出一个包就收到一个ACK,总是保持发送窗口那么多包在网络中流动。
TCP中一个重要的概念名为RTT,意思是往返时延,相当于发送信息与收到信息的ACK间隔的时间, 是重传timeout的依据。
传统算法迭代RTT,只考虑期望值,Timeout的设置不甚合理。
Jacobson/Karels的改进算法则同时考虑期望值和标准差,如果是正态分布的情况下偏离四倍的标准差极为罕见,可认为发生丢包。
,所以RTT与inflight的大小成正比,下限为RTprop
则说明传输速率与inflight的大小成正比,上限为BtlBw
显然,理论最优解就是
,称为BDP(Bandwidth Delay Product)
然而,基于丢包的拥塞控制将会使得系统稳定在右界,只保证最大带宽而无法保证时延。
RTprop 与 BtlBw是动态变化的,需要计算。
RTprop
,RTprop由物理设备决定,而
表示噪音,包含交换机队列时延、ACK处理时延等等。根据此式可以利用一段时间内最小的RTT估算RTprop。
时间长度通常十秒
或者
过期时,刷新时间戳和
static void bbr_update_min_rtt(struct sock *sk, const struct rate_sample *rs)
{
struct tcp_sock *tp = tcp_sk(sk);
struct bbr *bbr = inet_csk_ca(sk);
bool filter_expired;
/* 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;
}
}
如果过期则进入PROBE_RTT开始采样计算最新的RTT,采样时需要将滑动窗口设定为4,故先保存cwnd。
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;
}
如果处于PROBE_RTT状态并且监测到inflight<=4,则可以开始采样,设置RTT状态的结束时间为当前时间戳+200ms。设置app_limited避免这段时间内的BW参与最大值计算。
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);
}
}
/* Restart after idle ends only once we process a new S/ACK for data */
if (rs->delivered > 0)
bbr->idle_restart = 0;
检查RTT状态是否结束,如果结束则恢复到最好的cwnd,然后返回之前的状态。
static void bbr_check_probe_rtt_done(struct sock *sk)
{
struct tcp_sock *tp = tcp_sk(sk);
struct bbr *bbr = inet_csk_ca(sk);
if (!(bbr->probe_rtt_done_stamp &&
after(tcp_jiffies32, bbr->probe_rtt_done_stamp)))
return;
bbr->min_rtt_stamp = tcp_jiffies32; /* wait a while until PROBE_RTT */
tp->snd_cwnd = max(tp->snd_cwnd, bbr->prior_cwnd);
bbr_reset_mode(sk);
}
BtlBw
同时,传输速率不可能超过最大带宽,因此
时间长度通常6-10个RTT
带宽相当于采样区间的传输总数/区间总时间。RTT状态下不参与BW最大值计算。
/* 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 */
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);
bw = div64_long((u64)rs->delivered * BW_UNIT, rs->interval_us);
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);
}
}
适配令牌桶算法
当获取带宽时,可能是短期采样,也有可能是长期采样。
LT表示长期,意思是以长期的样本计算带宽。原因在于,如果使用令牌桶算法进行QOS限流的话,两个短期采样中的带宽是一致的,并且会有大量丢包。
当监测到使用令牌桶算法时,直接使用长期采样,避免频繁采样。
/* Return the windowed max recent bandwidth sample, in pkts/uS << BW_SCALE. */
static u32 bbr_max_bw(const struct sock *sk)
{
struct bbr *bbr = inet_csk_ca(sk);
return minmax_get(&bbr->bw);
}
/* Return the estimated bandwidth of the path, in pkts/uS << BW_SCALE. */
static u32 bbr_bw(const struct sock *sk)
{
struct bbr *bbr = inet_csk_ca(sk);
return bbr->lt_use_bw ? bbr->lt_bw : bbr_max_bw(sk);
}
/* Token-bucket traffic policers are common (see "An Internet-Wide Analysis of
* Traffic Policing", SIGCOMM 2016). BBR detects token-bucket policers and
* explicitly models their policed rate, to reduce unnecessary losses. We
* estimate that we're policed if we see 2 consecutive sampling intervals with
* consistent throughput and high packet loss. If we think we're being policed,
* set lt_bw to the "long-term" average delivery rate from those 2 intervals.
*/
计算BDP
窗口小于BDP时才能测出RTprop,窗口大于BDP时才能测出BtlBw,不可能同时测量准,因此Google的解决办法是在不同时间段分别测量RTprop和BtlBw,最后乘积得出BDP。
下面这段代码还做了向上取整,目的是避免负反馈循环。大概指的是在BDP附近来回摇摆没法收敛?
static u32 bbr_bdp(struct sock *sk, u32 bw, int gain)
{
struct bbr *bbr = inet_csk_ca(sk);
u32 bdp;
u64 w;
if (unlikely(bbr->min_rtt_us == ~0U)) /* no valid RTT samples yet? */
return TCP_INIT_CWND; /* be safe: cap at default initial cwnd*/
w = (u64)bw * bbr->min_rtt_us;
/* Apply a gain to the given value, remove the BW_SCALE shift, and
* round the value up to avoid a negative feedback loop.
*/
bdp = (((w * gain) >> BBR_SCALE) + BW_UNIT - 1) / BW_UNIT;
return bdp;
}
作为拥塞控制算法,显然不需要一开始就进入拥塞控制状态。
BBR状态机共有STARTUP、DRAIN、PROPERTT、PROPEBW四个状态,各自拥有自己的pacing_gain(决定实际发包速率)和cwnd_gain(决定窗口)。
下面这段伪代码的妙处在于正反馈
pacing_rate = pacing_gain * bottleneck_bandwidth
cwnd = max(cwnd_gain * bottleneck_bandwidth * min_rtt, 4)
42-44秒就是经典的正反馈过程
这里的状态机比较复杂,腾讯专栏那篇文章里都写错了。我是按照源码注释里的状态机来写的。问题在于PROBE_RTT可以由所有状态进入(因为入口在bbr_update_model中,不管什么状态都会调用),需要通过full_bw_reached判断之前是不是已经最大带宽。如果达到了的话,就一直处在BW和RTT的状态切换之中。
在稳定状态下,八个RTT先以5/4带宽速率探索最大带宽,然后以3/4带宽速率处理一阶段堆积的packet,最后以1倍带宽速率巡航。
上文提到了令牌桶的情况下需要进行长期采样
由Meter进行令牌桶算法后Marker进行颜色标记,根据标记执行对应的Action,例如
双桶单速率三色
承诺速率,每秒向桶中加入对应速率的令牌。令牌溢出后放入E桶。
承诺尺寸CBS和突发尺寸EBS,对应令牌数,代表容许的最大尺寸。
在包没有颜色的情况下:
在包有颜色的情况下:
双桶双速率三色
承诺速率和峰值速率,每秒向桶中加入对应速率的令牌。
承诺尺寸CBS和峰值尺寸PBS,对应令牌数,代表容许的最大尺寸。
在包没有颜色的情况下:
在包有颜色的情况下:
WRED加权随机先期检测
Ref: BBR: Congestion-Based Congestion Control,某奇怪的slide
虽然说是状态交替地执行,事实上每次都会采集bw和rtt。
static void bbr_update_model(struct sock *sk, const struct rate_sample *rs)
{
bbr_update_bw(sk, rs);
bbr_update_ack_aggregation(sk, rs);
bbr_update_cycle_phase(sk, rs);
bbr_check_full_bw_reached(sk, rs);
bbr_check_drain(sk, rs);
bbr_update_min_rtt(sk, rs);
bbr_update_gains(sk);
}