2019, Vol. 51
2. 中国科学院大学, 北京 100049
2. University of Chinese Academy of Sciences, Beijing 100049, China
目前广泛使用的拥塞控制算法如New-Reno[1]、CUBIC[2]都属于基于丢包的算法，即将丢包作为网络链路发生拥塞的信号.在互联网的初期，路由器和交换机上只有很浅的队列，并且网络环境比较简单，带宽较低，这个策略可以很好地实现网络上的拥塞控制.但是随着互联网的发展，如今的网络的情况已经大有不同：
首先，摩尔定律使得存储器的价格越来越便宜，网络设备上的缓存队列越来越深.一个TCP连接在建立后会逐渐增大拥塞窗口，先填充链路，再填充路由器等网络中间设备的缓存队列，当链路上的深队列被填满后网络设备会把多余的数据包丢弃，此时才会发生丢包.实际上在队列被填满之前，网络上已经发生了拥塞.因此，基于丢包的算法不但容易造成丢包而且会带来较大的时延[3].
其次，近些年来Wi-Fi、4G LTE等无线网络已经得到了广泛应用，无线网的信号不稳定，经常会出现噪声丢包；广域网也有较高的丢包率.而基于丢包的算法不能区分噪声丢包和拥塞丢包，只要有丢包事件发生就会减小拥塞窗口.以CUBIC为例，当丢包率为0.01%时，性能已经下降了一半，当丢包率超过1%时，已经几乎不能工作了.
因此，由于噪声丢包和深队列等原因的存在，丢包与拥塞已经不再具有紧密的联系.
最近，谷歌提出的BBR算法[4-5]为拥塞控制提供了一种全新的思路，它致力于解决两个问题：降低网络链路上的队列深度，从而降低传输时延；实现在具有一定丢包率的网络链路上充分利用带宽.
BBR会探测网络链路的最大带宽Bmax和最小往返时延Tmin，根据这两个值计算拥塞窗口和数据发送速率，以最大化吞吐率并最小化时延.BBR只运行于发送端，不需要对协议、接收端、网络做任何改变，因此可以方便地运行于大多数传输协议中.谷歌已经将它部署在内部的B4广域网和YouTube服务器上，运行结果表明，与CUBIC相比，BBR能够显著提高吞吐率并降低时延.文献[6-7]测试了BBR在移动网络中的性能，结果表明BBR的性能要优于CUBIC.
但是在一些无线网络环境下，当网络的时延抖动剧烈时，BBR的性能会急剧下降.本文发现这是因为BBR关于RTT的一个重要假设在网络时延剧烈抖动时不成立，并提出了相应的优化措施.本文还针对BBR对网络带宽的降低不够敏感的问题进行了优化.在实际网络中的测试结果表明，改进的BBR算法在时延剧烈抖动时仍可以保持高吞吐率，并在带宽降低时具有更快的收敛速率.
1 BBR拥塞控制算法 1.1 BBR的设计思想吞吐率和RTT可以反映出一条网络链路的性能.图 1显示了一条链路的RTT和吞吐率随inflight增加的变化趋势[4]，inflight为链路上正在传输的数据，即所有已发送但还未确认的数据包.
|
图 1 RTT、吞吐率与inflight的关系 Fig. 1 Relation of RTT and throughput with inflight |
图中区域被两条虚线分为三部分.左侧部分，网络链路上的数据较少，RTT一直维持在最小值，吞吐率随链路中数据量的增大而提高；中间部分，网络链路已经被填满，吞吐率达到最高值，不能继续增长，多发送的数据会被填充到网络中间设备的缓存队列中，因此RTT会逐渐增大；右侧部分，缓存队列也被填满，此后多发送的数据包会被路由器丢弃，发生丢包.
基于丢包的拥塞控制算法工作于右侧的虚线与两条曲线的交点处，此处可以充分利用带宽，但以较高的时延和频繁丢包作为代价.文献[8]证明了左侧虚线的交点是拥塞控制的最优操作点，此处inflight的值为吞吐率与RTT的乘积(bandwidth-delay product，BDP)，可以同时保证最大的传输速率与最小的时延.但不幸的是，Jaffe[9]证明不可能使用一个分布式算法来收敛到这个最优点.
BBR巧妙地解决了这一问题，如图 2，BBR设计了一个状态机，使用状态机的两个状态交替测量最大带宽Bmax和最小往返时延Tmin.相应地，BDP为
|
图 2 BBR的状态机模型 Fig. 2 BBR state machine |
| $ {B_{{\rm{BDP}}}} = {B_{\max }} \cdot {T_{\min }}. $ | (1) |
从而使算法收敛到最优点附近.
BBR主要维护两个控制参数：传输速率pacing_rate和拥塞窗口cwnd.传输速率等于当前带宽乘以增益系数pacing_gain，是最主要的参数，控制数据的发送速率，防止发送窗口中的数据一次性发出而阻塞链路.拥塞窗口等于BDP乘以增益系数cwnd_gain，控制当前链路上正在传输的数据总量.
1.2 算法流程BBR的主体由一个状态机构成，如图 2所示，共有4个状态：STARTUP、DRAIN、PROBE_BW、PROBE_RTT其中BBR生命周期的绝大部分时间都处于PROBE_BW阶段, BBR使用一个增益数组[1.25, 0.75, 1, 1, 1, 1, 1, 1]周期性地改变pacing_gain, 以探测网络链路的可用带宽.
2 BBR存在的问题 2.1 时延剧烈抖动时传输速率低在无线网络中BBR的传输速率有时会突然降低.通过实验发现，当网络的时延抖动较为剧烈时，即使网络的丢包率为0且未发生拥塞，BBR的传输速率会还是很低.如图 4中BBR的传输曲线所示，实验中链路带宽为3 Mbps，但实际的传输速率仅仅有0.5 Mbps.
|
图 4 传输速率随时间的变化 Fig. 4 Delivery rate over time |
因此这一问题主要是由时延的剧烈抖动所引起的.可知，BBR的拥塞窗口的大小为
| $ {\rm{cwnd}} = {\rm{cwn}}{{\rm{d}}_ - }{\rm{gain}} \cdot {B_{{\rm{max}}}} \cdot {T_{{\rm{min}}}}. $ | (2) |
即拥塞窗口取决于探测到的最大带宽和最小往返时延，而探测到的RTT满足
| $ {R_{{\rm{RTT}}}} = {T_{{\rm{prop}}}} + \mu . $ | (3) |
式中，Tprop是链路固有的往返时延，μ是抖动量，受链路上队列深度等因素的影响.
BBR使用Tmin来估算拥塞窗口基于一个假设：RTT的抖动程度μ远小于链路的固有往返时延Tprop，因此一段时间内探测到的最小RTT最接近真实的RTT，即
| $ {T_{\min }} \approx {T_{{\rm{prop}}}}. $ | (4) |
有线网络的网络环境比较稳定，这一假设基本成立，但是它不适用于4G、Wi-Fi等无线网络.
以视频服务的场景为例.用户使用手机在Wi-Fi或4G网络中观看视频，当视频内容提供商部署了边缘CDN服务器时，用户与服务器之间的最小时延很小，为几毫秒到十几毫秒；而Wi-Fi网络是很不稳定的，其时延会在4 ms~80 ms之间波动[10].因此，当用户在Wi-Fi网络中访问边缘CDN服务器时，链路的“固有RTT”与RTT的抖动量处于同一数量级.此时式(4)不成立，探测到的Tmin要远小于链路的真实时延.
Tmin过小会带来一系列影响，如图 3所示.Tmin变小使得拥塞窗口变小，若拥塞窗口过小，BBR的实际发送速率受到拥塞窗口的限制而无法达到pacing_rate，则PROBE_BW状态的pacing_gain数组不起作用，无法通过增大发送速率来探测更高的可用带宽.因此Bmax不变甚至减小，反过来又导致拥塞窗口变小.这样形成了一个恶性循环，使得BBR最终只能以很低的速率传输数据，无法有效利用网络带宽.
|
图 3 Tmin太小带来的影响 Fig. 3 The impact of too small Tmin |
随着移动互联网和5G[11]的快速发展，据思科估计，到2022年，Wi-Fi和移动网络将占IP流量的71%[12].因此，解决这一问题具有非常重要的现实意义.
2.2 对带宽下降不敏感PROBE_BW状态的pacing_gain数组为[1.25, 0.75, 1, 1, 1, 1, 1, 1].在一个周期中，先使用1.25倍的增益来探测可用的带宽，再将增益降为0.75以排空链路上累积的队列，最后是连续6轮的增益为1的平稳阶段.这个平稳阶段是为了保证公平性，在此期间BBR不能抢占带宽，使得共享资源的其它连接有充足的时间收敛到公平的状态.
但这是以牺牲了灵活性作为代价的.BBR使用“乘性增”的方式探测带宽，对带宽增长的反应很灵敏；但是当网络带宽降低时，它不会主动降低拥塞窗口或pacing_gain，故需要多个周期才能收敛[5].若平稳阶段的时间过长会带来较长的收敛时间，在此期间的发送速率高于链路实际带宽，非常容易造成丢包或者拥塞.在视频直播等业务中，这会造成视频卡顿，给用户带来非常差的观看体验.
3 BBR性能改进针对时延剧烈抖动时传输速率低的问题.由分析可知，当时延波动比较剧烈时，探测到的Tmin远小于链路的真实时延，此时应该使用RTT的均值Tsmo作为真实RTT的估计值，即
| $ {T_{{\rm{smo}}}} \approx {T_{{\rm{prop}}}}. $ | (5) |
由于标准差反映了数据的离散程度，可以统计探测到的RTT的标准差Tdev，用它来判断时延的波动程度.
BBR中没有记录历史RTT的滑动窗口，如式(8)所示，可以使用指数加权移动平均值记录RTT的均值Tsmo.类似地，使用式(9)可以得到标准差Tdev.α, β为新数据所占的权重.
当时延抖动比较剧烈时式(4)不成立，应改写为Tprop-Tmin>γ·Tprop，结合式(5)可以得到
| $ {T_{{\rm{smo}}}} - {T_{{\rm{min}}}} > \gamma \cdot {T_{{\rm{smo}}}}. $ | (6) |
由于Tmin≈Tsmo-Tdev，将其代入式(6)可以得到
| $ {T_{{\rm{dev}}}} > \gamma \cdot {T_{{\rm{smo}}}}. $ | (7) |
则当RTT波动剧烈时，式(7)成立，此时使用Tsmo计算BDP；否则，依然使用Tmin，如式(10)所示.γ决定了使用Tsmo替代Tmin的阈值.若γ值过小，BBR在网络条件较好时也会激进地发送数据，容易引起网络拥塞；若γ值过大，则当无线网络的时延波动较为剧烈时BBR仍会使用Tmin，导致传输速率下降.文献[13]测量了从天津到北京、香港、美国的有线网络的RTT，其统计结果显示有线网络中RTT标准差与均值的比值不超过0.3，故本文的实验取γ=0.3.
针对BBR对带宽下降不敏感的问题.在网络不稳定时，可以降低平稳阶段的时间长度，使BBR及时地探测到链路带宽的改变.由于RTT能够忠实地反映网络的波动状态，依然可以使用Tsmo和Tdev判断网络的状态，如式(11)，当Tdev>γ·Tsmo时认为网络是不稳定的，将pacing_gain数组中增益为1的数量减为3个；否则，保持原数组不变.
| $ {T_{{\rm{smo}}}} = (1 - \alpha ) \cdot {T_{{\rm{smo}}}} + \alpha \cdot RTT, $ | (8) |
| $ {T_{{\rm{dev}}}} = (1 - \beta ) \cdot {T_{{\rm{dev}}}} + \beta \cdot abs\left( {{T_{{\rm{smo}}}} - RTT} \right), $ | (9) |
| $ {B_{{\rm{BDP}}}} = \left\{ {\begin{array}{*{20}{l}} {{T_{{\rm{smo}}}} \cdot {B_{{\rm{max}}}}, {T_{{\rm{dev}}}} > \gamma \cdot {T_{{\rm{smo}}}};}\\ {{T_{{\rm{min}}}} \cdot {B_{{\rm{max}}}}, {T_{{\rm{dev}}}} \le \gamma \cdot {T_{{\rm{smo}}}}.} \end{array}} \right. $ | (10) |
pacing_gain数组为
| $ \left\{ {\begin{array}{*{20}{l}} {[1.25, 0.75, 1, 1, 1], {T_{{\rm{der}}}} > \gamma \cdot {T_{{\rm{smo}}}};}\\ {[1.25, 0.75, 1, 1, 1, 1, 1, 1], {T_{{\rm{dev}}}} \le \gamma \cdot {T_{{\rm{smo}}}}.} \end{array}} \right. $ | (11) |
为了验证改进后的BBR算法的性能，本文在实际网络中进行实验.使用QUIC协议在两台Ubuntu16.04主机之间传输文件，QUIC中使用BBR或改进的BBR作为拥塞控制算法，对比两者性能.链路上使用网损仪限制带宽和时延.
算法的具体参数设置如下：α=0.125, β=0.25, γ=0.3.其中α, β的值参考了QUIC源码[14](QUIC中统计了Tsmo和Tdev的值).
4.1 时延剧烈抖动的网络中的传输速率对比图 4显示了BBR与改进BBR的传输速率随时间的变化.实验中设置链路带宽为3 Mbps，设置了呈正态分布变化的往返时延，其均值为60 ms，标准差为40 ms.
BBR在STARTUP阶段，由于增益系数较大，且还未采样到特别小的RTT，传输速率可以短暂地增长到一个较大的值.但随着采样到的RTT值不断减小，拥塞窗口不断减小，导致传输速率逐渐降低.此后在PROBE_BW状态中，虽然pacing_gain会周期性地增大为1.25，但此时拥塞窗口非常小，传输速率受到拥塞窗口的限制，无法探测到更高的带宽，传输速率逐渐降低.
虚线为改进后的算法，由于使用Tsmo取代Tmin计算BDP，拥塞窗口的大小近似于链路的真实容量，因此传输速率主要受pacing_rate控制，出现了PROBE_BW状态的周期性波动，并且基本维持在3Mbps附近，可以充分利用链路的带宽.
图 5为改变网络时延的抖动程度，BBR和改进BBR的平均传输速率的变化曲线.实验中设置链路带宽为3 Mbps，时延的均值为60 ms，将时延的标准差从0~60 ms.
|
图 5 不同时延抖动程度下的平均传输速率 Fig. 5 Average delivery rate under different jitter degrees |
当时延的标准差为20 ms时，BBR的性能已经开始下降，增大到30 ms以上时，BBR的传输速率迅速降低到0.5 Mbps.此后时延抖动程度继续增大，传输速率却一直维持在0.5 Mbps附近.这是因为实验中将时延的最小值设为定值1 ms，所以BBR探测到的Tmin是恒定的，计算得到的拥塞窗口的大小不会改变，因此平均传输速率也基本保持不变.这表明：在RTT抖动剧烈时，是Tmin限制了BBR的性能.而优化后的BBR的平均传输速率稳定在2.55 M附近，基本不受RTT波动的影响，能够充分利用网络带宽.
4.2 带宽改变时的收敛速度对比图 6显示带宽改变时BBR和优化后的BBR的传输速率随时间的变化曲线.实验中设置链路带宽为5~10 Mbps，周期20 s的方波，时延为60 ms.
|
图 6 带宽改变时传输速率随时间的变化 Fig. 6 Delivery rate over time when bandwidth changes |
a) 中网络带宽在13 s附近升高到10 M，在23 s附近降为5 M；b)中网络带宽在8 s附近升高，在18 s附近降低.可以看到当带宽升高时，两者都能很快地收敛.但当带宽降低时，优化后的BBR的收敛时间只有BBR的一半，收敛速度显著提高.
5 结论当无线网络的时延剧烈抖动时，即使网络丢包率很低且未发生拥塞，BBR算法的传输速率还是很低.针对这一缺陷，本文提出了改进BBR算法：通过计算RTT的标准差，当标准差较大时认为网络的时延抖动剧烈，使用RTT的均值代替最小RTT来计算拥塞窗口.BBR还存在对网络带宽降低不敏感的问题，本文根据网络状态灵活调节PROBE_BW状态的pacing_gain数组中平稳阶段的时间长度，使得算法在网络不稳定时能够更快地收敛.
实验网络测试表明，优化后的BBR不受时延抖动影响，可以保持高吞吐率；而且在带宽降低时，算法的收敛速度显著提高.
| [1] |
FLOYD S, HENDERSON T, GURTOV A. The NewReno modification to TCP's fast recovery algorithm[R]. No. RFC 3782, 2004
|
| [2] |
HA S, RHEE I, XU L. CUBIC: A new TCP-friendly high-speed TCP variant[J]. ACM SIGOPS Operating Systems Review, 2008, 42(5): 64. DOI:10.1145/1400097.1400105 |
| [3] |
GETTYS J, NICHOLS K. Bufferbloat: Dark buffers in the internet[J]. Communications of the ACM, 2012, 55(1): 57. DOI:10.1145/2063166.2071893 |
| [4] |
CARDWELL N, CHENG Y, GUNN C S, et al. BBR: Congestion-based congestion control[J]. ACM Queue, 2016, 14(5): 50. DOI:10.1145/3012426.3022184 |
| [5] |
CARDWELL N, CHENG Y, GUNN C S, et al. BBR: Congestion-based congestion control[J]. Communications of the ACM, 2017, 60(2): 58. DOI:10.1145/3009824 |
| [6] |
LI F, CHUNG J W, JIANG X, et al. TCP CUBIC versus BBR on the highway[C]//International Conference on Passive and Active Network Measurement. Springer, Cham, 2018: 269
|
| [7] |
ATXUTEGI E, LIBERAL F, HAILE H K, et al. On the use of TCP BBR in cellular networks[J]. IEEE Communications Magazine, 2018, 56(3): 172. DOI:10.1109/MCOM.2018.1700725 |
| [8] |
KLEINROCK L. Power and deterministic rules of thumb for probabilistic problems in computer communications[C]//Proceedings of the International Conference on Communications, 1979, 43: 1
|
| [9] |
JAFFE J. Flow control power is nondecentralizable[J]. IEEE Transactions on Communications, 1981, 29(9): 1301. DOI:10.1109/TCOM.1981.1095152 |
| [10] |
CARDWELL N, CHENG Y, STEPHEN C, et al. BBR congestion control work at Google[DB/OL]. (2018-3)[2019-1-3]. https://datatracker.ietf.org/meeting/101/materials/slides-101-iccrg-an-update-on-bbr-work-at-google-00
|
| [11] |
张宇, 解伟. 5G移动与广播电视融合网络[J].网络新媒体技术, 2018, 7(5): 6. DOI:CNKI:SUN:WJSY.O.2018-05-002 ZHANG Yu, XIE Wei. 5G mobile and broadcast TV convergence network[J]. Journal of Network New Media, 2018, 7(5): 6. DOI:CNKI:SUN:WJSY.O.2018-05-002 |
| [12] |
CISCO. Cisco visual networking index: Forecast and trends, 2017-2022[DB/OL]. (2018-12-26)[2019-1-3].https://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/white-paper-c11-741490.html
|
| [13] |
赵伟丰.基于RTT的端到端网络拥塞控制研究[D].天津大学 ZHAO W F. Study on RTT-based end-to-end network congestion control[D]. Tianjin: Tianjin University, 2014 http://cdmd.cnki.com.cn/Article/CDMD-10056-1015019963.htm |
| [14] |
Google. Chromium[2019-1-3]. https://cs.chromium.org/chromium/src/third_party/webrtc/modules/congestion_controller/bbr/rtt_stats.cc?g=0
|