BBR算法详解
0 前言
学生时代为了完成一个Final Project,阅读了很多BBR(Bottlenect Bandwidth and Round-trip)算法相关的资料,于是决定写下这篇文章,来为自己这段时间的学习做一个梳理,大部分内容是整合(feng he)其他人的成果,再添加一点点自己的分析和理解,希望可以帮到一些和我一样从头开始学习BBR的同学。
本文内容包括BBR算法介绍,原理解析,具体实现,存在问题,BBRv2改进方案,此外,也顺便提供了一些我对于BBR做的一些性能实验,以及BBR源码解析。
文中涉及专业名词的部分,我会同时标注英文,以免翻译不当,如有疑问,请查阅原文。
面向的读者
大致掌握本科生级别计算机网络知识,最好对于TCP 拥塞控制(Congestion Control)有一些基础了解,对BBR算法感兴趣的同学。为了照顾到不同学习阶段的同学,本文在书写过程中使用了过量的信息,即某些推理、逻辑、结论可能会在文中不同阶段反复出现,是希望能够达到相互映照以帮助理解的效果。如果觉得过于冗余,还请见谅。
阅读资料的顺序
如果你有充分的时间来学习BBR相关的知识,比起直接阅读,我更推荐你先按顺序阅读一些相关的资料,能够帮助你更好的理解本文的内容。如果时间不够,可以跳过这部分,直接阅读正文内容。当然如果其中我有讲的不太清楚的地方,你也可以参照这些资料进行比对理解。
-
首先是中科大-郑烇老师 在B站发布的BBR介绍视频,一共三期,有关BBR的前因后果都讲的很清楚,让我受益匪浅:
BBR拥塞控制算法之1:通信模型哔哩哔哩bilibili
-
其次是BBR的原版论文,算是我读过最好的论文之一,深入浅出,易于理解:
BBR: Congestion-Based Congestion Control
-
原版是英文的,如果英文不够好,我找到一个不错的译文,可以对照着阅读:
[译] [论文] BBR:基于拥塞(而非丢包)的拥塞控制(ACM, 2017)
-
最后是Google自己的讲解视频,除了原始版本,BBR也有很多后续的更新,BBR团队都会在IETF会议上介绍,这里先按下不表,只附上BBR初次亮相时的介绍视频。
IETF97-ICCRG-20161115-1550
1 在BBR诞生之前
1.1 在BBR诞生前的拥塞控制算法
TCP(Transimission Control Protocol) 协议诞生于1974年,绝对算是最古老的网络协议之一,同时也是当今互联网上使用最多的网络协议。TCP带给了我们可靠的数据包传输控制(数据丢失后进行重传),但如果每一个人都为了追求更高的传输速度而疯狂发送数据,我们的互联网迟早要被数据填满,也就是拥塞(Congestion) . 因此TCP协议同样提供了拥塞控制(Congestion Control)的策略,通过改变拥塞滑动窗口(CongestionWindow,简称 cwnd
) 的大小来控制正在传输中的流量,以避免拥塞的发生,来保证网络使用的公平性。
当今互联网上主要使用的拥塞控制算法(Congestion Control Algorithms) 都是基于丢包的拥塞控制(loss-based congestion control) ,他的基本运行方式可以分为以下几个阶段:
slow start
阶段,指数级别地成倍增加发送数据的速率,试探网络的带宽上限ssthresh
之后,进入线性增长 Congestion Avoidance
的阶段,慢慢增加发送的速率loss
), 认为网络发生了拥塞,大幅度减少滑动窗口的大小slow start
的状态 基于丢包的拥塞控制算法
这套算法是20世纪80年代设计的,后来随着网络环境的变化,也逐步推出了TCP Tahoe, Vegas, Reno, Cubic(现在Linux系统的默认算法) 等改进版本的算法,在原有基础上增加了一些更细致的功能,但整体思路不变,依旧是基于丢包来进行拥塞控制。
-
通过以下命令看看你当前Linux机器的可用的算法
sysctl net.ipv4.tcp_available_congestion_control
查看正在使用的算法
sysctl net.ipv4.tcp_congestion_control
1.2 基于丢包(loss-based)的拥塞控制算法不足之处
但40多年过去了,当今的网络环境早已千差万别,原本保证网络环境通畅无阻的设计,却成为了现如今许多拥塞和网络延迟的主要原因。问题主要源于以下两个方面:
-
丢包≠拥塞(loss ≠ congestion)
过去的网络环境往往带宽较小,而且以有线线路居多,所以一旦发生丢包的行为,99%是由于拥塞导致的,所以CUBIC这样的算法才有效地支撑了互联网几十年来的发展。
但是当今的网络环境,链路带宽高达数十Gbps,是当年的六个数量级以上,在相同出错率的情况,丢包的发生情况就会变多。
另一方面像Wifi这样的无线链路逐渐普及,而Wifi由于周围物理环境的不确定等原因,天然的出错率和丢包率就要高很多(所以不要在wifi环境下打游戏)
无线网络的丢包问题
-
网络交换节点的buffer变大
随着高速buffer的价格越来越低,网络交换节点开始使用大容量的buffer来应对更大的网络需求。但是正如之前所说,基于丢包的算法在初始阶段会指数级增加发送的数据,就是想要把buffer填满,填满之后,再发送数据给交换机就会产生丢包,从而控制当前的连接速率下降。
Bufferbloat问题,大量数据被卡在buffer里,导致延迟大量增加
但是如果Buffer很大,这样的策略就会导致BufferBloat问题,大量的数据卡在交换节点的buffer中,排着队等待被发送出去,导致排队延迟(Propagation Delay) 增大,从而使得整体的网络延迟增加。关于这一点,可以结合后文2.1链路瓶颈来理解。
此外,CUBIC等算法的吞吐量(Throughput) 会随着丢包的发生反复震荡,不够稳定,同时也意味着对链路的利用率不够高,下面这张图能清晰的展现这一点
解决这些问题需要一种全新的方式来控制拥塞,这也是今天的主角,BBR ( Bottleneck Bandwidth and Round-trip propagation time,BBR) 试图做到的。事实上,它也确实做到了,将Google自家的广域网B4(连接Google各个数据中心data center的网络)中的TCP流量从CUBIC切换到BBR,吞吐量(throughput)增加了2-25倍,在做了一些配置调优后,甚至进一步提升到了133倍。(来自论文结果,后面会进一步提到)
2 BBR算法的原理介绍
要解决拥塞是如何发生的,首先要对以下两点有深入理解:
2.1 主机间的通讯模型,及概念梳理
拥塞与瓶颈
首先我们来解决第一个问题,对于一个全双工的TCP连接来说,在任意时刻,它在每个方向都有且只有一段最慢的链路( exactly one slowest link)或称瓶颈(bottleneck) 。
瓶颈链路(Bottleneck Link),管道最细处决定了最大速率,同时也是数据堆积的地方
瓶颈的概念很重要,因为:
-
瓶颈决定了连接的最大数据传输速率,就好像一根水管最细处决定了它整体的水流量。
-
瓶颈也是持久队列(persist queues)形成的地方。
对于瓶颈链路,只有当它的离开速率(departure rate)大于到达速率(arrival rate)时,这个队列才会收缩,否则就会不断堆积,而一条链路上其他的队列也会朝着瓶颈移动(因为它的传输速率最小)。
不管一条连接会经过多少条链路,以及每条链路的速度是多少,从 TCP 的角度来看, 任何一条复杂路径的行为,与 RTT(round-trip time)及瓶颈速率相同的单条链路的行为是一样的。 换句话说,以下两个物理特性决定了传输的性能:
RTprop
(round-trip propagation time):往返传输时间(假如没有排队的情况下, 简称为RTT
BtlBw
(bottleneck bandwidth):瓶颈带宽
BDP=RTT×BtlBWtext{BDP} = RTT times text{BtlBW}BDP=RTT×BtlBW
带宽延迟积(Bandwidth Delay Product) BDP
, 顾名思义就是将这两个参数相乘得到的概念,如果将网络路径视为一条管道,那么RTT就是管道的长度,Bandwidth是管道的直径,而BDP表示的则是管道的容量大小。所以对应到网络中, BDP
表示的意思就是某一时刻的网络中仍在传输中的最大数据量(buffer中留存的数据除外)。
BandWidth, Delay 与 BDP
在管道被灌满了之后, 继续发送数据就会导致数据被堆积在交换节点的buffer中,形成堆积的队列。同样以水管来类比的话,Bottleneck 就是下面那根比较细的水管,如果你的发送速率大于它(也就是上面那根比较粗的水管),数据就会累积在水管前的蓄水池中(也就是交换节点的buffer),自然而然也就产生了我们前面提到的BufferBloat问题。
2.2 Throughput, RTT 与 Inflight Data的关系
下面我们来解决第二个问题,拥塞是如何发生的?
inflight数据,是指那些已经发送出去,但是还没有得到确认的数据, 也就是前面提及的,仍在管道中的数据。某一时刻的inflight数据量(也就是正在传输中的数据)决定了当前的网络的吞吐量(Throughput) 和 RTT。(在RTT不变的假设下,inflight也可以理解为在过去一个RTT时间内发送出去的数据量)
我们可以通过下图来理解他们之间的关系:
Delivery Rate(Throughput) and Inflight Data
- 在 0 text{BDP + BufSize}Inflight>BDP + BufSize (上图最右侧红色断点处)时,就出现了我们之前提到的Bufferbloat现象,中间的节点无法再接受更多的数据,就会开始随机drop一部分新接收的数据(蓄水池已满,水从蓄水池中溢出来了),也就产生了丢包(packet loss)。 CUBIC等基于丢包的算法就在此时开始降低发送的速率。
但是上述情况的问题也是显而易见,我们再来看下图,RTT与Inflight data的关系:
Delivery rate, RTT and Inflight data
- 一开始,在 0 text{BDP + BufSize}Inflight>BDP + BufSize 时,也就出现了丢包的情况。
直观上来说, 拥塞(congestion)就是 inflight 数据量持续向右侧偏离 BDP 线的行为, 而拥塞控制(congestion control)就是各种在平均程度上控制这种偏离程度的方案或算法。
对于像CUBIC这样基于丢包的拥塞控制算法而言,他们会选择在上图的最右侧,也就是蓝色圈圈的位置开始控制整体的传输速率, 减少发送的数据量,将其向左移动。但不难看出,此时才开始控制发送速率已经太晚了,既要忍受RTT的增加,同时也会存在丢包的风险,损失一定的Throughput.
而最佳的策略就是将inflight data控制在上图红色圈圈的位置,这样我们就能够实现当前网络下最大的Bandwidth和最小的RTT。很不幸的是,在1981年,Gail & Kleinrock 就已经证明了理论上不可能设计出一个算法可以找到这个点,于是退而求其次,大家选择了基于丢包的拥塞控制算法,在当年,缓冲区域的Buffer只比BDP略大,所以导致的额外延迟很小,红点和蓝点之间距离很小,但是现在缓冲区已经比BDP大上好几个数量级了,bufferbloat导致的RTT达到了秒级,这就没有办法忽视了。
- 把以上两张图结合起来就可以理解原论文中的这张图
而BDP算法的思路简单来说就是,努力将inflight数据量控制在最优点右侧一点点,努力达到 Inflight=BDPtext{Inflight} = text{BDP}Inflight=BDP,从而获得更小的RTT和更大的吞吐量,而实现的方式就是通过Bottlenect Bandwidth 和RTT。
-
如果本段觉得无法理解,可以参考郑老师视频的这一部分(已定位时间
BBR拥塞控制算法之1:通信模型哔哩哔哩bilibili
2.3 通过当前的Bottleneck Bandwidth和RTT进行拥塞控制
当一个连接满足以下两个条件时,它将运行在最高吞吐和最低延迟状态(也就是上一节中提到的红色最优点):
速率平衡(rate balance) :瓶颈链路的数据包到达速率刚好等于瓶颈带宽 BtlBw
,
这个条件保证了链路瓶颈已达到 100% 利用率。
管道填满(full pipe) :传输中的总数据(inflight)等于 BDP(= BtlBw × RTprop
)。
这个条件保证了有恰好足够的数据,既不会产生瓶颈饥饿(bottleneck starvation), 又不会产生管道溢出(overfill the pipe)。
最高吞吐与最低延迟的状态,其中中间的橙色管道为瓶颈链路被填满,而它前面的buffer为空
需要注意,
-
仅凭 rate balance 一个条件并不能确保没有积压。
例如,某个连接在一个 BDP=5 的链路上,开始时它发送了 10 个包组成的 Initial Window,之后就一直稳定运行在瓶颈速率上。那么,在这个链路此后的行为就是:
- 稳定运行在瓶颈速率上
- 稳定有 5 个包的积压(排队)
发送速率与瓶颈带宽相同,但是积压的队列会维持不变
-
类似地,仅凭 full pipe 一个条件也无法确保没有积压。
例如,如果某个连接在12frac{1}{2}21RTT时间内发送一个 BDP 的数据, 那仍然能达到瓶颈利用率(管道刚好被填满),但却会产生平均 BDP/4 的瓶颈积压。
在链路瓶颈以及整条路径上最小化积压的唯一方式是同时满足以上两个条件:
- BBR通过控制数据发送的速率(pacing rate) 来保证速率平衡
- 同时通过控制拥塞滑动窗口(
cwnd
)的大小来控制inflight数据量等于BDP
3 BBR算法的具体实现
通过上一章的介绍,我们应该了解了BBR算法是如何控制拥塞的大致思路,而想要实现上述方案,就要根据当前网络的Bottleneck Bandwidth和RTT进行调整。所以这一章,我们将深入BBR算法的细节:
- BBR如何测量当前网络的Bottleneck Bandwidth和RTT?
- 在得知以上两个参数后,如何控制发送的速率和inflight data?
- BBR的四个不同阶段分别是什么,有什么样的作用?
- BBR的实际表现如何,在哪些方面有明显的优势?
3.1 如何测量Bottleneck Bandwidth与RTT(收到ACK时做什么
为了控制发送的速率,我们首先需要计算出当前网络的Bottleneck Bandwidth和RTT,同时由于网络环境的动态变化,这两个参数并不是固定的,而是会随着时间而变化,所以需要进行实时的采样测量。
得益于TCP协议的Send-ACK设计,其实每一次发送方发送数据,接收方接收到数据后发送一个ACK信号给发送方,而每一次这样的交互都可以视为一次独立的数据采样,具体的实现方法如下:
假设在t=0的瞬间,数据包序号 p+k
刚好准备发送出去,而与此同时,数据包序号 p
的ACK信号刚好到达,那么我们就可以在数据包 p+k
上添加上这两个记录:
send_time
这个数据包被发送出去的时间,在这里是t=0delivered_at_send
这个数据包被发送时,sender接到的最新的数据包数量,在这里就是p这两个属性会在数据包被receiver返回ACK信号时,一起发送回来。假如100ms后这个数据包的ACK信号回来了:
那么此时我们就可以计算出两个属性:
- 这个数据包的
RTT
, 只需要将当前的到达时间arrive_time
减去发送时间send_time
,就得到了数据包一次往返的总时长,这里就是 RTT=100ms−0ms=100mstext{RTT} = 100ms -0ms = 100msRTT=100ms−0ms=100ms - 过去一个RTT时间内的带宽
bw
.在这100ms的时间内,从数据包p
到数据包p+k
总共k个数据包陆续到达,所以这段时间的bw
=k/100ms
这样以来,每次有一个ACK信号到达时,我们就可以根据上述公式,更新相应的Bandwidth和RTT数据,每一个数据包都是一个采样估计,或许偶有偏差,但是大量数据的计算就可以实现对这两个物理属性的无偏估计。
理论上这个算法没有问题,但是实际上RTT和瓶颈带宽BtlBW会不断变化,究竟如何确定哪一个才是网络的真实属性呢?BBR算法里通过这种方式来去确定:
- 一段时间内测量到的最小RTT,就是这条路径在这一段时间内的往返传输延迟。在实际BBR算法中,选择10s作为这个窗口时间
- 估计出的传输速率,不会超过真实的瓶颈带宽,后者时前者的上限
deliveryRate BtlBwFilter.current_max // 如果实际传输速率已经大于当前估计的瓶颈带宽
|| !packet.app_limited) //
update_max_filter(BtlBwFilter, delivery_rate) // 则更新一段时间内的最大瓶颈带宽if (app_limited_until > 0) // 达到瓶颈带宽前,仍然可发送的字节数
app_limited_until = app_limited_until - packet.size
由于论文原代码中的一些变量名稍有歧义,我修改了部分变量名以获得流畅的阅读体验。
几点说明:
-
每个包都会更新对 RTT 的估计,但只有部分包会更新对 BtlBw 的估计;
-
应用受限的包
- 对于一个包,当应用(application)全速发送它而仍然没有占满瓶颈带宽时, BBR 会这个包标记为
app_limited
(见下面的send()
伪代码), 即packet.app_limited = true
。 - 这将决定哪些样本会用来更新对带宽的估计(如果app_limited,则不算做采样的样本)
- 对于一个包,当应用(application)全速发送它而仍然没有占满瓶颈带宽时, BBR 会这个包标记为
-
瓶颈带宽 BtlBw 是传输速率的一个硬性上限,因此
- 如果测量到当前的传输速率 > 当前对 BtlBw 估计, 必定意味着这个估计太低了,不管样本是不是 app-limited;对应到上面的代码,就是只要
delivery_rate > BtlBwFilter.current_max
,就一定更新 BtlBw 估计;否则, - 如果样本不是 app-limited(说明实际带宽已经饱和),也更新 BtlBw 估计。
- 如果测量到当前的传输速率 > 当前对 BtlBw 估计, 必定意味着这个估计太低了,不管样本是不是 app-limited;对应到上面的代码,就是只要
-
对于前面理论部分不太了解的同学,可以参照原论文”Characterizing the Bottleneck” 这一部分阅读,也可以参考郑老师视频的这一部分(已附时间定位
BBR拥塞控制算法之2:控制原理哔哩哔哩bilibili
-
pacing_gain
:BBR 的主要控制参数,控制发送的速率send_rate=pacing_gain×BtlBWtext{send_rate} = text{pacing_gain} times text{BtlBW}send_rate=pacing_gain×BtlBW
要求达到速率必须匹配到瓶颈速率,意味着 pacing 是 BBR 设计中 必不可少的部分。
-
cwnd_gain
:拥塞滑动窗口的大小cwnd
等于 BDP 乘以一个略大于 1 的系数cwnd_gain
, 用来控制当前网络中的inflight数据量。略大于1是为了容忍常见的网络和接收端异常(pathologies),这个我们后面会讲到。cwnd=cwnd_gain×BDP=cwnd_gain×BtlBW×RTTtext{cwnd} = text{cwnd_gain} times text{BDP} = text{cwnd_gain} times text{BtlBW} times{RTT}cwnd=cwnd_gain×BDP=cwnd_gain×BtlBW×RTT
3.2 控制发送的数据(如何均匀地发送数据
科普下 TCP pacing 这个下文将用到的概念:
Paper: Understanding the Performance of TCP Pacing
TCP’s congestion control mechanisms can lead to bursty traffic flows on modern high-speednetworks, with a negative impact on overall network efficiency. A pro-posed solution to this problem is to evenly space, or “pace”, data sent intothe network over an entire round-trip time, so that data is not sent in aburst. In this paper, we quantitatively evaluate this approach.
译注。
一个时间内发送同样数量的数据包,pacing rate不同,产生的效果差别很大,前者就更容易造成拥塞
为了让数据包的到达速率(packet-arrival rate)能匹配到 瓶颈链路的离开速率(departure rate), BBR 会对每个数据进行 pace (在每个 RTT 窗口内均匀发送数据)。
总的来说BBR有两个控制参数:
TCP发包时BBR的逻辑
function send(packet)
bdp = BtlBwFilter.current_max * RTpropFilter.current_min // 计算 BDP
// cwnd_gain * bdp 就是目前允许的正在传输的最大数据量
if (inflight >= cwnd_gain * bdp) // 如果正在传输中的数据量超过了允许的最大值
return // 直接返回,接下来就等下一个 ACK,或者等超时重传
// 能执行到这说明 inflight < cwnd_gain * bdp,即正在传输中的数据量 = next_send_time)
packet = nextPacketToSend()
if (!packet) // 如果没有数据要发送
app_limited_until = inflight // 更新 “在达到瓶颈容量之前,仍然可发送的数据量”
return
packet.app_limited = (app_limited_until > 0) // 如果仍然能发送若干字节才会达到瓶颈容量,说明处于 app_limited 状态
packet.sendtime = now // 记录这个包的发送时间
packet.delivered_at_send = delivered // 记录这个包发送时,已经收到的总数据量
packet.delivered_time = delivered_time // 记录这个包发送时,上一个ack接收到的时间
ship(packet)
// 下一次发送的时间间隔,等于包的大小 除以 发送速率
// 其中发送速率= 瓶颈带宽 * pacing_gain
next_send_time = now + packet.size / (pacing_gain * BtlBwFilter.current_max)
timerCallbackAt(send, next_send_time)
这段代码中没有介绍的是如何计算 inflight data
的数据量,这是我们决定要不要继续发送数据的重要因素之一, 但其实只要理解 inflight data
的含义——已经发送出去但是还没有收到ack的数据,就能推导出以下公式: inflight = send_out - delivered
, 已经发送出去的数据量减去已经接收到的数据量。
-
对于这两节觉得讲的不够清除的同学可以参考论文”MATCHING THE PACKET FLOW TO THE DELIVERY PATH“ 部分,另外郑老师的视频也可以看这部分 (已附时间定位
BBR拥塞控制算法之2:控制原理哔哩哔哩bilibili
-
对于这两部分代码不够理解的地方可以查看郑老师的视频 (已附时间定位
BBR拥塞控制算法之3:算法与应用哔哩哔哩bilibili
3.3 BBR的四个不同阶段
读完上面两节之后,我们不难理解BBR整体的控制思路,在接收时不断地采样测量当前的 BtlBW
和 RTT
, 在发送阶段,以这两个变量为基础,乘以 pacing_gain
和 cwnd_gain
来控制发送的速率和inflight数据量,从而实现拥塞控制。
我们已经知道了 BtlBw
和 RTT
是怎么来的, 但是 pacing_gain
和 cwnd_gain
又是怎么来的呢? 后两个参数是BBR控制网络速率的关键,他们是BBR算法自身设定好的,或者更具体来说,BBR算法在建立TCP连接后会进入四个不同的阶段,每个阶段都有对应的 pacing_gain
和 cwnd_gain
,来实现不同阶段的目的。
首先让我们来对这四个阶段进行一个笼统介绍:
**StartUp**
阶段,类似传统TCP阶段的slow start 阶段,会成倍的增长发送速率和cwnd,试探当前网络的性能瓶颈
当检测到RTT不断增加,而BW基本不变之后,说明我们到达了2.2中提到的最优点右侧的部分,产生了队列堆积,算法就会进入 **Drain
** 阶段,快速降低发送速率,将inflight数据量排空至BDP大小
在inflight=BDP之后, 就会进入平稳的 PROBEBW
阶段,这也是绝大部分时间所处的阶段。此时会将发送速率控制在一个稳定的范围内,偶尔会增加一下发送速率,看看网络环境是否有变化(带宽是否增加)。
为了适应网络环境可能的剧烈变化,每隔10s左右,还会进入 ProbeRTT
的阶段,将cwnd设为一个极小的值,排空当前的inflight数据量,保证这段时间内的RTT为理论最小值。
BBR不同阶段时的inflight data
StartUp 阶段
StartUp
阶段类似于CUBIC算法的slow start阶段,发生在连接刚刚建立的时候, 会指数级增长 cwnd
和 pacing rate
快速地把水管注满,探测到当前网络环境的天花板,记录下此时的 RTT
和 BW
。
在这一阶段 pacing_gain
和 cwnd_gain
的值都为 2ln2frac{2}{ln{2}}ln22 , 大约是2.885, 具体为什么是这个值呢?因为网络协议一个重要的指标是公平性,如果在start up阶段增长的速度太快,就会挤占别人的带宽资源,这样不太好,如果你增长速度太慢自身性能当然也不太行。
所以最好的方式就是和别的算法差不多,而这里所谓别的算法其实也没有别人,正是CUBIC为首的Loss-based算法。CUBIC的slow start速率是每过一个RTT,cwnd就会增长一倍,CUBIC使用它自己设置一套模型来实现这个目标,而BBR就需要在自己的模型下也模拟出这样一个每个RTT都会成倍增长的效果。将 pacing_gain
和 cwnd_gain
设置为 2ln2frac{2}{ln{2}}ln22,就可以近似模拟出这样一条曲线。 这其中有着严谨的数学证明,这里我们先不深入讨论,在4.2部分会有详细介绍。
此外,这个阶段也会记录下探测到的最小RTT和最大带宽,这在后面 ProbeBW
阶段会非常有用。
Drain 阶段
Startup
阶段难免会用力过猛,把水管注满,甚至把填充了许多buffer的空间,导致出现了堆积队列,如果BBR发现最近一段时间 RTT
开始增加,而 BW
基本没有增长,就意识到已经到达了瓶颈,可以进入 Drain
阶段了。
所以 DRAIN
阶段的目标就是把 StartUp
阶段中注入过多的inflight数据排空, 使得 inflight=BDP
, 这样延迟才会降低,同时吞吐量也足够大。
此时的 pacing_gain
会设置为 ln22frac{ln{2}}{2}2ln2, 也就是 StartUp
阶段的倒数,指数级降低当前发送速率,直到inflight 数据量等于bdp.
另外,此时的 cwnd_gain
其实仍然是 2ln2frac{2}{ln{2}}ln22 ,虽然看上去很大,但 cwnd
会维持不变,因为 cwnd=cwnd_gain * BtlBW * RTT
,后面两个变量在进入这一阶段后都不会改变,所以cwnd也不会有任何变化。
ProbeBW 阶段
在 Drain
阶段排出了过量的inflight数据,BBR就会进入一个稳定的状态,也就是 ProbeBW
的阶段,这一阶段基本不会对发送速率做出过多的改变,但是也会不断试探网络变化,有没有更高的带宽可以使用,所以简单来说要完成以下目标:
- 维持发送速率基本控制在
BtlBW
左右,充分利用瓶颈带宽。 - 维持
inflight = BDP
,保证网络的延迟稳定。 - 周期性地试探更高的带宽上限,试探本身可能会导致数据堆积,所以试探结束后会降低发送速率,把队列排空。
BBR是如何实现上述三个目标的呢?他们通过设置 周期性地改变 pacing_gain
的值来实现,以8个RTT为一个循环,探测带宽的阶段就设置为1.25, 探测结束后就设置0.75排空网络中堆积的数据,然后剩下六个RTT就会使用1.0来平稳地传输数据。
在论文原文中,作者指出BBR每次在进入
ProbeBW
循环时,会随机挑选其中一个阶段开始,但0.75除外。因为进入ProbeBW状态时,默认当前网络时没有堆积的,此时这样一个drain的阶段就没有意义。 但是在阅读BBR源码(Linux Kernel 4.15)的过程中,我发现他们其实并没有排除掉0.75,不知道后续有没有改进。 至于为什么要随机挑选初始阶段,其实是为了避免不同flow同时进入同一个阶段,使得网络同步上探带宽,产生爆发性流量。这一点在4.1中还会提到,会对收敛有所帮助。
在ProbeBW阶段,从上到下依次是RTT, inflight, BtlBW估计值,BW实际传输速率 的变化
几点说明:
虽然 pacing_gain
在这一阶段会周期性变化,但是 cwnd_gain
会一直维持在2,保持不变的原因是因为在平稳阶段要努力控制inflight数据=BDP,所以没有必要变化。
理论情况下,一个包一个ACK,BDP=14, 设置cwnd=14, 流畅传输
实际存在Ack Compression的情况会导致数据堆积,无法发送新的数据(图中序号代表因果顺序而非时间顺序
那为什么要设置 cwnd_gain=2
呢?这样一来 inflight=2*BDP
,似乎就不是最优的情况了。这样设置的原因是,理论上接收方每收到一个packet都会发送一个 ack
信号回去,但是实际网络情况中会出现ACK聚集(ACK Compression ) 的情况,发送方会攒着几个包的 ack
一起发送出去,提升网络的利用效率。但是这样就意味着inflight的数据不止在BDP这个管道内,还会在接收方的aggregation缓存中,如果设置 inflight=BDP
反而会限制网络的发送速度(数据卡在发送方那里,实际网络传输的数据量会小于BDP), 所以这里将 cwnd_gain
设置为2,保证可以发送速率不会被限制住。
-
这一段如果没有理解也没有关系,是算法的一些小细节,不影响整体思路,可以结合郑老师视频的这一部分来理解(已附定位时间
BBR拥塞控制算法之3:算法与应用哔哩哔哩bilibili
事实上这个ack聚集或延迟的问题,远没有这么简单,这也是后续BBR算法进一步优化的目标之一,我们会在第五章再回过头讨论这个问题及其解决方案。
ProbeRTT 阶段
最后就是 ProbeRTT
的阶段,正如其名,BBR会周期性地进入这个阶段来测量最小的RTT,也就是 min_rtt
的值,来适应网络环境的变化。
具体的实现方案如下,每隔10s时间,会从 Probe_BW
状态进入 Probe_RTT
状态,此时会将 cwnd
设置为4( 保证至少一条数据可以合理传输),持续时间为 max(rtt, 200ms)
。由于基本不传输新的数据,这段时间内基本会把inflight数据排空,保证管道的通畅,这样我们也就能够测到最真实的 min_rtt
值。
所以在观看BBR的传输速率曲线的时候,每隔10s就会有一个大的波谷,很容易辨认出,这就是 ProbeRTT
的阶段。
这一阶段毕竟基本不发送任何数据,所以会对链路利用率有一些损耗,总的来说每10s中会有200ms的闲置,总的损耗率在2% ,属于可以接受的范围内。当然10s的周期其实还是有些太长,所以后来BBR也提出了新的改进方案,我们会在第五章中提到。
3.4 BBR的实际表现
将上面四个阶段结合起来,我们就可以大致理解BBR算法在实际运行中的效果如何了,为了有更直接的感触,我们可以通过下图来将其与CUBIC算法做对比:
CUBIC和BBR,同时运行在一条10-Mbps/40ms的线路上前1秒钟发送速率的变化,其中绿色为BBR发送速率,红色为CUBIC发送速率,蓝色是接收方实际接收到的速率; 下图是RTT的变化
几点解释:
上半部分图展示的是 BBR 和 CUBIC 连接的发送速率 随时间的变化,蓝色代表着接收方实际接收到的速率,也就是真实的throughput,可以看到BBR在startup之后会逐渐向真实的 BtlBW
靠拢。
下半部分图中可以看出,BBR 和 CUBIC 的初始行为是类似的,但 BBR 能完全排尽它的 startup queue 而 CUBIC 不能。BBR在 Drain
阶段就排空了,但是CUBIC的RTT仍然在线性增长。
CUBIC 算法中没有 inflight 信息,因此它后面的 inflight 还会持续增长(虽然没那么激进),直到 瓶颈 buffer 满了导致丢包,或者接收方的 inflight limit (TCP’s receive window) 达到了。
这是这条线路前8秒的详情:
ProbeBw
阶段说了这么多,那么BBR在真实网络中的表现到底如何呢?
在Google B4广域网(WAN)的部署经验
Google的B4高速广域网(Wide Area Network)是为了连接Google分散在各个城市甚至各个大洲的数据中心而建立的网络,这种高延迟同时又瓶颈链路非常明显的网络非常适合使用BBR。2016年,所有B4 TCP流量都已经切换到了BBR.
BBR vs. CUBIC relative throughput improvement.
上图 可以看出,BBR 的吞吐稳定地比 CUBIC 高 2~25 倍, 而按照理论估计BBR的性能应该会更好,因此在做了一部分性能调优之后,BBR达到了比CUBIC要高133倍的提升。
在不同丢包率下的实际吞吐量
以上优异的表现就得益于BBR 没有将丢包作为拥塞指示器(not using loss as a congestion indicator),而事实上,BBR最擅长的地方就是在有一定丢包率的网络下依旧维持非常高的传输速率。
下图比较累不同丢包率下的实际吞吐量:
BBR vs. CUBIC goodput for 60-second flows on a 100-Mbps/100-ms link with 0.001 to 50 percent random loss.
最大可能的吞吐是 链路速率乘以 * (1 - lossRate)
,
- CUBIC 的吞吐在丢包率
0.1%
时下降到了原来的 1/10 倍,在丢包率 1% 时完全跌零了。 - BBR 的吞吐 在丢包率小于 5% 时能维持在最大值,在丢包率超过
15%
之后才开始急剧下降
BBR的对于延迟的降低
BBR 已经部署到了 Google.com 和 YouTube 视频服务器上。在小规模灰度测试中,一小部分用户会随机被分到 BBR 或 CUBIC。
- 以 YouTube 的所有体验质量指标来衡量,BBR 给用户带来的提升都非常明显,这可能是 由于 BBR 的行为更加一致和可预测(consistent and predictable)。
- BBR 只是略微提升了 Youtube 的连接吞吐(connection throughput),这是因为 YouTube 已经将服务器的 streaming rate 充分控制在 BtlBw 以下,以最小化缓冲区膨胀(bufferbloat)和多次缓冲(rebuffer)问题。
- 但即使是在这样的条件下,BBR 仍然将全球范围内 RTT 的中值平均降低了 53% , 而在发展中国家,这个降低的百分比更是达到了 80%
CUBIC_RTT 与CUBIC_RTT/ BBR_RTT
我们可以看到在缩短延迟上,BBR比CUBIC有着成倍的提升,CUBIC中延迟越大的网络,换成BBR的提升就越明显。
4 BBR的一些详细细节
4.1 多个BBR flow如何收敛
公平性是衡量一个TCP拥塞算法的核心指标之一,其中又分为同一个算法的公平性(intra-CCA)和不同算法间的公平性(inter-CCA),这里我们先讨论前者,即多个BBR连接同时占用一条线路时,每个连接都能分到相对公平的带宽。首先我们来看下图:
五条BBR连接共享100Mbps带宽后的吞吐量
上图是以两秒为间隔,分别建立一条BBR连接后的吞吐量变化,大概在30秒左右后收敛,能够达到平分throughput的效果。BBR之前没有任何协同机制,那他们是如何达到收敛的效果呢?其实主要有一下两个方式:
-
ProbeRTT
阶段。 flow1(第一个启动的连接)每隔10s就会drain掉当前队列中的数据,来更新min_rtt
,这一阶段同时也会将当前队列中堆积的数据排掉很多,这样以来其他flow也会检测到RTT明显发生了变化,为了更新他们的min_rtt
,大家也会同步进入ProbeRTT
的状态。所以我们能看到在30s和40s左右,所有的数据流都有一个同步的低谷,那就是大家一起进入ProbeRTT
状态。这使得它们的 RTprop estimates 在同一时间过 期,因此集中进入 ProbeRTT 状态,这会进一步使积压的数据更快消化,从而使更多 flow 看到新的 RTprop,以此类推。这种分布式协调 (distributed coordination)是公平性和稳定性(fairness and stability)的关键。排空之后再重新开始抢夺带宽,这个时候大家就是站在同一个起跑线上了,慢慢也就同步了。
-
ProbeBW
阶段。ProbeBW gain 周期性变化,使大 flow 将带宽匀给小 flow, 最终每个 flow 都得到一个公平的份额。至于这个过程是如何实现的,BBR团队在他们的Github项目给出了补充证明:(github.com/google/bbr/…)
我这里对这个证明进行简单的介绍:当两个flow都按照相同比例增加带宽时(ProbeBW的上升阶段),原本带宽更大的flow获得的实际增长比例会更小,而原本带宽较小的flow获得的实际增长更大, 久而久之,就会逐渐收敛。
假如所有人共享一条总带宽为1的链路,我们当前链路的带宽为 my_bw
, 其他所有链路的带宽为 other_bw
,两个加起来充分利用了整个链路。正如3.3中所提及的那样,不同flow之间进入 ProbeBW
的时间会错开, 所以我们先来看一看当我们的链路开始上探带宽(pacing_gain=1.25
)而其他所有链路保持不变的时候会发生事情.
growth_rate=bw_during_probing / bw_during_baselinetext{growth_rate}= text{bw_during_probing}space / space text{bw_during_baseline} growth_rate=bw_during_probing / bw_during_baseline
=(gain∗my_bw/(gain∗my_bw+other_bw))/(my_bw/(my_bw+other_bw))\ =(text{gain} * text{my_bw} / (text{gain} * text{my_bw} + text{other_bw}))/\ (text{my_bw} / (text{my_bw} + text{other_bw}))=(gain∗my_bw/(gain∗my_bw+other_bw))/(my_bw/(my_bw+other_bw))
这个公式得到在向上探测后的带宽增长比例,看起来有点复杂,其实就是向上探测后我们的带宽 my_bw*gain
在总的带宽 my_bw*gain + other_bw
中的占比,除以之前 在总的带宽中的占比。中间节点在分配带宽的时候按照发送的数据量进行分配,比如一共为2Mbps的带宽,原本大家发送1Mbps的数据量,都平分得到1Mbps。但是如果我们提升到2Mbps的速度,我们分的带宽量就是 2/3 * 2 = 4/3
的带宽量。
因为 other_bw = 1 - my_bw
,所以上述式子也可以改写为
growth_rate=(gain∗my_bw/(gain∗my_bw+1−my_bw))/(my_bw/(my_bw+1−my_bw))text{growth_rate}= (text{gain} * text{my_bw}
/ (text{gain} * text{my_bw} + 1 - text{my_bw}))/(text{my_bw} / (text{my_bw} + 1- text{my_bw}))growth_rate=(gain∗my_bw/(gain∗my_bw+1−my_bw))/(my_bw/(my_bw+1−my_bw))
=gain/(gain∗my_bw + 1 - my_bw)=text{gain} / (text{gain} * text{my_bw + 1 - text{my_bw}})=gain/(gain∗my_bw + 1 - my_bw)
既然 gain=1.25
, 那么增长比例y与原本带宽占有量x的关系就可以表示为:
y=1.25/(1+0.25x)y=1.25/(1+0.25x)y=1.25/(1+0.25x)
整个函数的曲线就会如上图所示,在一次试探后,原本带宽占比越小的flow(x≤0.5),增长的比例也就越大。这也是为什么 ProbeBW
阶段可以帮助收敛的原因。
-
这篇CSDN也帮助解释了这个收敛问题,通过图像解释地更清楚一些
漫谈TCP BBR的收敛动力学(convergence dynamics)
至于不同算法之间的公平性问题,这其实一直是BBR广为诟病的一点,所幸在BBR2.0得到了一定的改善,我们会在第五章中再提及。
4.2 STARTUP的系数为什么是2/ln2
正如前文所提到的,公平性是拥塞算法重要的指标之一,为了在 Startup
阶段可以模拟出与CUBIC相近的增长曲线, 即每一个RTT将发送速率增长一倍,BBR将这个阶段的 pacing_gain
设置为 2ln2frac{2}{ln{2}}ln22.
BBR团队同样也在自己的项目里给出了为什么选择这一数字的数学证明:
BBR Startup证明
这里同样简要地概括一下他们的证明思路。为了方便理解,我们设置 RTT=1
单位时间,同时为了拟合CUBIC的增长曲线,保证每个RTT后翻倍的增长, 我们可以这样表达 pacing_rate
的增长曲线,其中 t
是时间, k
是任意系数(不同拥塞协议有不同的设定):
PacingRate(t)=SendingRate(t)=k2ttext{PacingRate}(t) = text{SendingRate}(t) = k2^tPacingRate(t)=SendingRate(t)=k2t
根据BBR的设定,我们的PacingRate是来自于过去一段时间测量出来的带宽乘以 pacing_gain
来得到的:
PacingRate=gain∗EstimatedBandwidth(t)text{PacingRate} = gain * text{EstimatedBandwidth(t)}PacingRate=gain∗EstimatedBandwidth(t)
按照我们之前对于如何测量bandwidth的理解,其实在t时间测量到的带宽是指从t-2到t-1内发送的总数据量(假如无丢失,所有数据一个RTT准时到达),所以就可以列出这样的等式:
PacingRate(t)=∫x−2x−1PacingRate(t)dttext{PacingRate}(t)=int_{x-2}^{x-1} text{PacingRate}(t)dtPacingRate(t)=∫x−2x−1PacingRate(t)dt
代入上面PacingRate的指数表达式,可以得到 g = 4ln24ln{2}4ln2, 大约是2.77. 这可能会引发困惑,原始版本的BBR是2.89。 据BBR团队介绍说,之前推导出2.89的人离职了,没有留下数学证明或者记录,2.77是他们自己推导了一遍的版本。其实我们考虑CWND的指数增长的话,其实也可以推出2.89,大概差距在4%左右,影响不算大。BBR团队也确实做了实验,证明2.77确实是最优的可以刚好拟合出一个RTT翻一倍的增长速度,因为影响不大,所以也就将错就错使用至今了。实验相关图可以在上面的链接中找到。
-
CSDN这一篇博文分析了一些背后的数学原理,以及2.89是如何得出的,可以一看。
The math behind dynamics of TCP BBR_dog250的博客-CSDN博客
5 BBR的问题及其改进方案
5.1 BBR的几个问题
BBR 算法自2016年推出之后就受到了很大的重视,从它直接被并入Linux内核就可以看出,业界还是非常认可它的算法理念和实际表现的,以至于算法后来被分为BBR前的算法和BBR后的算法。BBR本身也是想替代CUBIC,成为下一代TCP拥塞控制的代言人,但是经过一些实验,大家发现BBR算法自身或多或少还是存在一些缺陷,只能说和CUBIC互有优劣。
不同算法竞争公平性
由于BBR在loss rate较高的情况下的出色表现,所以很容易就会让人担心BBR在和CUBIC竞争的情况下会抢占CUBIC的带宽,导致后来的建立连接的CUBIC几乎无法可用。这种担心不是没有道理的,在loss rate较高(>1%)的链路下,一个CUBIC和一个BBR竞争, BBR一般会抢占将近90%以上的带宽,导致CUBIC几乎不可用。
但是有意思的是,根据我所做的实验,在一个较好的链路当中,CUBIC会反过来压制住BBR的流量,抢占大部分带宽。因为在丢包率很低的链路中,BBR的优势并不明显,但是CUBIC会发送超量的数据给中间节点来试探带宽瓶颈,自然而然就抢占了BBR的带宽。
这个问题的解决方案还要等到BBR2.0才被推出,我们后面再讲。
ACK延迟或聚集
正如3.3 ProbeBW相关中提到的那样,TCP连接为了提升效率可能会存在ACK聚集的情况,所以默认设置 cwnd_gain=2
来缓解这种情况(这也间接导致了RTT常年维持在 min_rtt
的两倍左右)。但是到了无线WIFI网络下,情况就变得更复杂了,因为WIFI是一个半双工结构,所谓半双工就是,可以接收也可以发送,但是接收和发送不能在一端同时进行:
所以接收端在高速接收数据的同时,无法同时返回ACK信号给发送端,而是会在接收端不断累积,而这种累积可能就会导致ACK延迟超出1个RTT(设置 cwnd_gain=2
能处理的上限),从而导致网络链路没法得到充分的利用。
5.2 BBR的逐步改进
正如前文提到,BBR并非是一个论文,而是有一个专门的Google小组负责这件事情,每当有一定改进的时候,他们就会在IETF上放出来,自从在IETF97上首次公布之后,BBR参加了十二次IETF,不断地展示一部分BBR新的特性,性能表现,以及最后落实成为一个draft,描述详细的算法逻辑和实现方式, 这些draft其实是我们了解BBR的最好方式之一。我下面也会对BBR的改进进行介绍,但是由于资料来源基本就是Google自己的视频分享和PPT,我自己也是偏一知半解,所以可能没办法保证清晰性和正确性,还请见谅。
会议编号 | 改进方案 |
---|---|
IETF 97 | BBR首次被提出 |
IETF 98 | 介绍BBR的部署经验 |
IETF 99 | 提出了BBR算法草案,还有带宽预估草案 |
IETF 100 | 改进BBR在shallow buffer环境下的表现 |
IETF 101 | 改善了BBR在wifi环境下ack堆积的问题,预估aggregation大小,Drain Target |
IETF 102 | BBR v2 推出,1. ProbeBW阶段分为UP, CRUISE, DOWN,2. 提升与cubic共存的fairness,3.使用loss信号和ECN来更快结束startup阶段,4.ProbeRTT更频繁,影响更小 5. |
IETF 104 | BBR v2的效果提升 |
IETF 105 | BBR v2正式开放源代码 |
IETF 106 | 介绍了BBRv2在减少CPU占用率上的改进 |
IETF 109 | BBR.Swift 使用delay作为额外的信号 |
IETF 110 | BBR2 进展 |
IETF 112 | BBR draft 发布 |
Shallow Buffer问题
这一次IETF上Google重点介绍的是BBR在一个shallow buffer(buffer< 1 * BDP)上的改进。虽然BBR算法设计之初就是为了在较浅的buffer上也能得到良好的throughput,但是最初的设计在运行之后也不可避免的出现了一些问题:
而造成这种问题的原因是:
BBR现有的 ProbeBW
阶段使用了非常简单的方案(一个轮次八个RTT)
根据现实网络情况的权衡考量,为了动态分配带宽,会预留很多buffer,面对随机的丢包,shallow buffers需要补偿
这一段没看懂,大致是这个意思吧
Based on trade-offs among competing real-world design considerations:
- Cell systems with dynamic bw allocation need significant backlog
- Shallow buffers need compensation for stochastic loss
所以BBR为此提出的解决方案是:
-
之前为了解决限流问题,引入一个long-term bandwidth,检测长时间的bw,如果发现限流,就用long-term bw。现在这个long-term bw还会对任何fast recovery 到 probeBw阶段的带宽进行限制,使用过去2-3个RTT内的平均BW。
-
新增了两个参数
max safe volume of inflight data
,Volume of data with which to probe
根据shallow buffer 大小进行调整 -
如果丢包率> 5% , 判定当前遇到了
full pipe + buffer
, 触发事件:- 设置当前inflight大小为
max safe volume of inflight data
- 0.85倍速降低带宽
- 在重新进入probeBW之前,稍微等待(1-4s, 视RTT而定),来获得一个预估BW的函数
- 设置当前inflight大小为
实际表现如上,可以看到BBR2选择牺牲了一定的带宽,换来了较低的丢包率,同时各个flow之间也更加公平了
六个连接先后2s分别建立后,他们各自占领的带宽
BBR aggregation estimator
正如前面所提到的WIFI环境下ACK堆积的问题,原本BBR v1将 cwnd
设置为2倍的BDP,面对延迟变化在1个RTT内的网络环境还是可以应付的,但是WIFI的网络环境变化可能远超与此:在 min_rtt=20ms
的情况下,wifi的 delay_variation = 1-80ms
.
对此,BBR的解决方案是,去根据一段时间内额外收到的ACK数量(extra_acked
),来预估ACK Aggregation的大小:
翻译成数学的表达方式就是:
extra_acked= actual_acked - expected_acked
BBR源码中收到ack并不是一个一个处理的,而是一段时间(interval
)的ack会累积在一个 rate_sample
里,一起处理。 expected_acked
就是这段时间的 bw
乘以 interval
,与实际收到的ack数量的差,就是额外累积的ack大小。
这个计算出来的 extra_acked
是10个rtt内的最大值,然后 cwnd
大小就会设置为 BDP * cwnd_gain + extrac_acked
, 额外加上这部分,来保证能够流畅地传输数据。
在实验环境下,性能也获得了成倍的提升:
Drain to Target
在之前的BBRv1设计中, ProbeBW
阶段分为三种状态, pacing_gain>1
的上升状态, pacing_gain K(8)
就会提前进入 DRAIN
阶段.
ECN-basd 退出机制
ECN(Explicit Congestion Notification) 是一种显式拥塞控制机制,简单来说就是TCP header中几个标记可以被设置为ECN标记,如果路由器发现了阻塞,将会修改这个标记,从而发送方就能更快地感知到拥塞是否发生。BBRv2的设计是,如果 ecn_mark_rate> tartget_ecn_mark_rate(50%)
,就会提前进入 Drain
阶段。
ProbeBW 阶段重新设计
在BBRv2中,最大的改变之一应该就是ProbeBW阶段整体上算是重新设计了一个新的方案,思路上还和之前的设计差不多,但是对于带宽的控制更加精细了,不同状态的转换和持续时间也会动态变化,这样可以提升链路利用率,降低丢包率。
这一段还没有理解透,后面补充
ProbeRTT 更频繁,更平缓
在以前的BBR设计中,ProbeRTT阶段每隔10s运行一次,一次持续200ms,将 cwnd
缩小为4,这样会带来两个问题:
- 因为 10s一次,导致
min_rtt
收敛速度很慢(20-30s),不能应对变化迅速的网络环境 - 把inflight data缩小到4个包,过于猛烈,可能会导致更高的长尾延迟
对此的解决方案是:
-
使ProbeRTT阶段的降低更平缓,降低为
0.75 * BDP
-
更频繁地进入ProbeRTT阶段, 每隔2.5s一次
为什么选择2.5s呢?(0.2 * 0.75 + 2.5 * 1.0) / (2.5 + 0.2) = 98.1% ,总的来说对于吞吐量的损失和之前差别不大。
与其他算法的公平性
这一段还没有理解透,后面补充
BBR后续也有一些更新,比如降低对CPU的占有率,考虑引入delay作为信号的BBR.swift,后期的BBR更像是开始融合各种其他算法的机制来提升自己的性能。由于我本人的时间和能力限制,就暂时不在这里介绍了,大家可以参考IETF106, IETF 109来深入了解一下。
6 BBR性能测试实验
正如之前所提到的,这篇文章的起源是来自我的一个Final Project,这个Project的最后目标就是重现BBR论文中的一些结论。为此,我使用 mininet
搭建了一个模拟的网络环境,然后使用 iperf
建立连接,同时用 ethstats
测量运行时的带宽占有情况,最后我还用了Tensorboard来进行实验结果的可视化。
项目的源代码和我的一些试验记录已经公开在Github上:
BBRReproduce/README.md at main · sunyiwei24601/BBRReproduce
github.com/sunyiwei246…
项目的主体是用Python来写的,不过要完成其中特定的实验需要切换Linux Kernel的版本,更具体的运行要求我全都写在README里,对于大部分函数也都有相应的注释文档,你也可以自己进行改动和实验。
大部分实验结果与BBR原论文中类似,比如BBR确实能在高loss rate情况下维持高吞吐量,低延迟:
不过也发现了一些有趣的现象,比如在低loss rate和很大的buffer情况下,其实BBR完全竞争不过Cubic,因为CUBIC会超量发包来达到拥塞:
在loss_rate=0%的情况下,红色CUBIC与黄色BBR共享同一条链路带宽
此外,虽然BBR一直声称想要达到inflight=BDP,但是实际上由于cwnd设置为2*BDP,所以其实一直无法到达最小RTT,不过还是能稳定在两倍最小RTT左右:
min_rtt
在这里大概是40ms左右,但是日常 ProbeBW
阶段会维持在100ms,只有在 ProbeRTT
阶段才会下探到底部。
7 BBR 源码解读
在前面的项目里,我还顺便附带了一份BBR的源码逐行解析,基于Linux Kernel 4.15版本的BBR源码,增加很多原本没有的注释,希望可以帮助到大家。
BBRReproduce/tcp_bbr_note.c at main · sunyiwei24601/BBRReproduce
阅读源码会有一些困难,比如对C很多机制的不熟悉,Linux内核一些机制也不了解,导致你可能会卡在一些和BBR算法根本没什么关系的问题上。但是好处是,可以进一步加深对算法的了解,就我个人而言,确实是读懂了源码之后才感觉对BBR算是了如指掌了。
到了BBRv2的源码从原来的1000行增加到了2000行,我暂时还没有时间读完,希望以后有机会给大家补上。
在这里我也补充一些对于阅读BBR源码的小建议,首先是建议配合BBR draft一同观看:
BBR Congestion Control
里面对于各个参数,变量名的详细解释,对算法原理的介绍都有涉及,绝对比只看代码注释要好。这里顺便分享一下我刚开始阅读源码时遇到的几个困惑:
阅读顺序
不要从上往下读,因为C的一些原因,函数无法在未被声名前的代码行中调用,所以顺序看起来会有一些混乱。正确的阅读顺序是先看下面的main函数和bbr_update_model:
static void bbr_update_model(struct sock *sk, const struct rate_sample *rs)
{
bbr_update_bw(sk, rs); // 根据采样,更新实时的bw
bbr_update_ack_aggregation(sk, rs);
bbr_update_cycle_phase(sk, rs); // 如果PROBE_BW状态下,进入循环下一个阶段
bbr_check_full_bw_reached(sk, rs); // 判断是否跑满了bw,记录下来
bbr_check_drain(sk, rs); //判断是否进入drain阶段,drain清空了queue后,进入probe_bw阶段
bbr_update_min_rtt(sk, rs); // 根据采样,更新最小rtt,如果rtt长时间不变,进入probe_rtt阶段
bbr_update_gains(sk); // 根据所处的阶段,选择不同的gain系数
}
/* 算法主要流程 */
static void bbr_main(struct sock *sk, const struct rate_sample *rs)
{
struct bbr *bbr = inet_csk_ca(sk);
u32 bw;
// 更新brr的参数,如bw, min_rtt, 所处阶段,对应的gain系数等
bbr_update_model(sk, rs);
// 获取当前模型的bw
bw = bbr_bw(sk);
// 根据bw和gain设置pacing rate
bbr_set_pacing_rate(sk, bw, bbr->pacing_gain);
//设置滑动窗口大小
bbr_set_cwnd(sk, rs, rs->acked_sacked, bw, bbr->cwnd_gain);
}
然后根据这两个函数里各个语句的执行顺序,一个个看各个分支函数的运行逻辑和作用,会通顺和舒服很多,同时也能看到与BBR论文中相互映照的地方。
单位SCALE
为了提升运行效率,很多常数应该以小数的形式存储,在C里会使用 原数*SCALE的形式,比如1.25就会存储为 5 / 4 * 8, 到了使用的时候再除以这个SCALE,提升效率。
这个在BBR算法中也出现了很多:
/* Scale factor for rate in pkt/uSec unit to avoid truncation in bandwidth
* estimation. The rate unit ~= (1500 bytes / 1 usec / 2^24) ~= 715 bps.
* This handles bandwidths from 0.06pps (715bps) to 256Mpps (3Tbps) in a u32.
* Since the minimum window is >=4 packets, the lower bound isn't
* an issue. The upper bound isn't an issue with existing technologies.
* 时间单位一般为usec,测量包的发送速率,一般以包的数量/时间为单位,这个理就是pkt/uSec了
* 想要以pkt/uSec 为单位进行测量,但是这个单位代表的数量太大了,1pkt/uSec = 1500bytes/1usec = 12Gbps
* 所以这里需要进行缩小,缩小为12Gbps/2^24 = 715bps,这样一个单位unit表示的就是1pkt/uSec/2^24
* 换句话说,如果rate=2^24, 这说明达到了1packet/usec的发送速率
* tcp的cwnd是以packet数量为单位的,所以一般都缩小单位,乘以2^24(类似从s->ms, 乘以1000)
* 详情见:https://blog.csdn.net/quniyade0/article/details/115579087
*/
*/
#define BW_SCALE 24
#define BW_UNIT (1