Information Science and Engineering

BBR congestion prevention and control algorithm based on RTT updating mechanism

  • Hua YANG ,
  • Jianhui LIANG ,
  • Jiehong WU
Expand
  • College of Computer Science,Shenyang Aerospace University,Shenyang 110136,China

Received date: 2024-01-03

  Online published: 2024-03-29

Abstract

The classic BBR congestion control algorithm lacks timely adjustment of sending behavior and packet quantity during link congestion, which can easily exacerbate the degree of congestion and result in significant delays. Through analysis, the main root cause of this issue is the hysteresis in BBR congestion detection. To address this problem, the BBR congestion prediction and avoidance (BBR-CPA) algorithm was proposed. This algorithm started from the round-trip time update mechanism of BBR, dynamically detected the bottleneck path, and predicted the congestion state of the link based on RTT data, thus reduced the packet quantity in advance to alleviate potential congestion in the link. During operation, it records the bottleneck path’s bandwidth data and performed mean processing on bandwidth estimation, accelerated the convergence of the link to the optimal state. Experimental results show that compared to the classic BBR algorithm and the latest BBR-S and BBR-ACD algorithms, BBR-CPA achieve an average delay reduction of 56%, 44%, and 8%.It effectively eliminates link congestion and reduces the resulting delays.

Cite this article

Hua YANG , Jianhui LIANG , Jiehong WU . BBR congestion prevention and control algorithm based on RTT updating mechanism[J]. Journal of Shenyang Aerospace University, 2024 , 41(1) : 27 -35 . DOI: 10.3969/j.issn.2095-1248.2024.01.004

作为TCP传输协议的重要部分,拥塞控制可以有效缓解网络拥塞。Jacobson1在1988年提出了拥塞控制算法,该算法根据数据包丢失情况来调整TCP拥塞窗口大小。随着互联网带宽的不断增长及网络基础设施的不断发展,传统的基于丢包的拥塞控制算法如CUBIC2、Reno3等,因其高丢包率和缓冲区膨胀问题4,已无法满足多数高质量网络应用的需求。2016年Cardwell等5提出了具有高吞吐量和强抗丢包特性的瓶颈链路带宽和往返传播时延算法。与基于丢包的拥塞控制算法不同,BBR通过估计最大瓶颈链路带宽( B t l B w)和最小往返传播时延( R T p r o p  )来控制其发送行为,使拥塞窗口大小尽可能接近Kleinrock6所提出的最优工作点,提高其传输过程中的吞吐量,减小时延。
尽管BBR在当今的网络环境中广泛应用7,但它在某些场景中暴露了拥塞后时延较大8-9、传输公平性不好等问题10。Mahmud等11提出了BBR-ACD算法,该算法减少了RTT波动对BBR拥塞状态判断的干扰,降低了传输过程中的时延。Chiariotti等12提出了使用自适应托比特卡尔曼滤波器取代了BBR的带宽时延估计机制,尽可能地减少因网络波动造成的错误估计,降低时延。Li等13提出BBR-APG算法,根据缓冲区情况和拥塞状况自适应调整增益函数,提高收敛速度,减少重传次数并降低时延。Vargas等14在实时流媒体环境中对BBR进行实验,并针对带宽高估的问题,提出了BBR-S算法,对带宽估值进行优化,减少了拥塞的发生。Lynn等15根据BBR的运行机制提出TCP-Davis算法,综合利用了BBR算法和基于丢包的反馈机制。上述研究分别从减少RTT波动、自适应调整增益函数、加快连接速度、优化带宽更新机制等方面对时延问题进行改进,但大都忽略了拥塞检测的滞后性问题,导致改进效果有限。分析发现拥塞检测的滞后性是造成链路拥塞后产生较大时延的关键因素。
本文提出BBR拥塞预测探测及避免算法,从BBR的传输时延更新机制入手进行改进。
(1)动态检测瓶颈链路,根据RTT的变化实现对链路拥塞状态的预判,并及时调整发包数量,提前消除链路中可能存在的拥塞。
(2)运行过程中记录瓶颈路径带宽数据并对带宽估值进行均值处理,加快链路向最优状态收敛。
本文通过对BBR的收敛过程进行分析,利用RTT更新机制对链路拥塞状态进行预测,从而提前排空链路中的拥塞,减少时延。

1 BBR的传输时延分析

1.1 BBR基本原理

BBR拥塞控制算法通过估计最大瓶颈链路带宽 B t l B w和最小往返传输时延 R T p r o p,从而得出最大带宽时延积(bandwidth delay product, BDP)即
B D P = B t l B w · R T p r o p
BBR与传统的基于丢包的拥塞控制算法的根本区别是:BBR始终将BDP控制在Kleinrock最优工作点附近。如图1所示,图中D点为基于丢包的拥塞控制算法操作点,C点为Kleinrock操作点。传统拥塞控制算法(如Reno、Cubic)将BDP控制在B点附近,而BBR将BDP控制在A点附近,在实现最大吞吐量的同时,实现最低时延。
图1 Kleinrock最佳操作点
BBR算法主要由4个状态构成,分别为STARTUP(启动)、 DRAIN (排空)、 PROBE_BW (带宽探测)和PROBE_RTT (时延探测)状态。BBR的运行状态如图2所示。
在STARTUP状态阶段,BBR会以指数形式增加发送增益,探测最大可用带宽。探测到最大可用带宽后进入DRAIN状态,DRAIN状态降低发送增益,清空STARTUP状态创建的多余队列,排空网络中的拥塞。拥塞排空后会进入PROBE_BW状态,发送增益先增大后减小最后保持不变,实现带宽的探测和平稳运行。如果在固定时间内没有测得更小的RTT,就会进入PROBE_RTT状态,该阶段发送少数数据包,更新最小RTT。在PROBE_RTT状态结束后,根据网络状态判断进入PROBE_BW状态或STARTUP状态继续运行。BBR时延方面的问题出现在图2中(1)处与(2)处,拥塞检测不及时,使其无法快速进入PROBE_RTT状态,长时间在PROBE_BW状态循环,造成拥塞程度进一步加剧,产生较大时延。

1.2 BBR的传输时延分析

本文对BBR收敛过程进行分析,以两条流为例,分析其时延产生的主要原因。如图3所示,X轴、Y轴分别代表的为流B、流A所分得的瓶颈链路带宽,buff为缓冲区的大小,直线y 1为理想情况下两路流的收敛状态。瓶颈链路带宽为 B W,流A的带宽为 a,流B的带宽为 B W - a。则起始点p1的坐标为 ( a ,   B W - a )。假设流A先进行探测,其在PROBE_BW阶段的增益为 g a i n,则A探测后的坐标p2为 ( g a i n · a ,   B W - a )。流A排空拥塞后到达点p3处,其点为直线y1与带宽 = B W - a的交点,p3的坐标为
( B W · g a i n · a B W - a + g a i n · a ,   B W - a B W - a + g a i n · a B W )
接下来流B也进入探测阶段,点p4的坐标为
( B W · g a i n · a B W - a + g a i n · a ,   g a i n ( B W - a ) )
B探测后排空网络中的拥塞到达点p5,其坐标为
X = B W 2 · g a i n B W 2 + ( g a i n - 1 ) B W a + ( 1 - g a i n ) a 2 , Y = B W 2 + ( g a i n - 1 ) B W · a + ( 1 - g a i n ) a 2 - B W + a B W 2 + ( g a i n - 1 ) B W · a + ( 1 - g a i n ) a 2
可以看出,理想条件下,随着探测过程的进行,两条流逐渐向y 1靠近,两条流的运行过程逐渐达到最优状态。但是,实际情况中BBR往往会因为路由器的猝发功能16而高估带宽,导致发送过多数据包,造成拥塞;或者因为网络波动及网络故障造成错误估计,影响传输效率。经分析发现,以下两个问题是BBR产生较大时延的主要原因:
(1)BBR对拥塞状态的检测存在滞后性。BBR采用固定时间间隔内的RTT变化来对拥塞状况进行判断。该判断方式不能立即发现当前链路的拥塞状况并做出调整(降低发包数量)。因此,BBR往往在拥塞发生后的很长一段时间才做出响应,其拥塞检测机制的滞后性会产生较大时延。BBR拥塞窗口的计算如式(5)所示。
C W N D = C w n d _ g a i n · B t l B w · R T p r o p
式中: C W N D为拥塞窗口大小; C w n d _ g a i n为窗口增益; B t l B w为最大瓶颈链路带宽; R T p r o p  为最小往返时延。当BBR出现拥塞时,所测 R T p r o p较大,所以 C W N D的计算值大于实际的拥塞窗口,造成发出较多的数据包,使得链路拥塞程度进一步加剧。只有达到固定的调整间隔,BBR才会调整发送行为,降低发包数量。在此期间BBR会一直处于拥塞状态,并超发数据包。此外,BBR对网络的波动情况考虑不够完善,当网络波动较大或者遇到网络故障时,导致BBR对 B t l B w R T p r o p进行错误估计。当RTT波动较大时,尤其是在无线网络中,频繁波动的RTT会导致BBR对拥塞状态产生错误判断,影响传输效率17。当BW波动较大时,BBR会高估带宽,发送过多数据包造成拥塞,路由器的猝发功能同样会导致BBR高估带宽14。综上,上述两种问题使得BBR无法及时检测网络中的拥塞状态,造成调整发送行为的滞后,严重影响了传输效率。
(2)BBR对于拥塞的处理不当。BBR检测到拥塞发生后会进入PROBE_RTT阶段,该阶段只传输少量数据包,目的是减轻链路的拥塞程度,并测得新的最小RTT。然而,该方法无法适应不同的拥塞状态:当拥塞较为严重时,BBR在PROBE_RTT阶段无法排空拥塞,BBR会持续拥塞状态,继续传输,因其处于拥塞状态,测得的RTT较大,计算的拥塞窗口较大,发送过多的数据包使得链路的拥塞状态进一步加剧;当拥塞程度较轻时,BBR在PROBE_RTT结束之前就足以排空网络中的拥塞,却还需要等待持续时间结束,增加了等待时延。
综上所述,BBR对链路中拥塞的检测并不及时,导致对于拥塞的处理不当,进而造成后续数据包的较大时延,实验测得时延可能超过800 ms,实时性难以满足当前流媒体网络的一般要求(400 ms左右)18

2 BBR-CPA算法

综上可知,BBR算法当前的拥塞检测及处理机制存在严重的滞后性问题。本文提出的BBR-CPA算法从RTT更新机制入手,对拥塞检测机制、拥塞处理机制和带宽更新机制进行优化。该算法实时检测链路状态,通过RTT变化趋势对链路拥塞状态进行预判、并提前消除线路中可能存在的拥塞;运行过程中记录历史带宽数据,对带宽估值进行均值处理,提高收敛速度。

2.1 拥塞检测机制优化

BBR-CPA算法对拥塞检测机制进行优化,BBR-CPA通过RTT变化趋势,实现对链路拥塞状态预判。BBR-CPA算法的拥塞检测机制流程如图4所示。
图4 BBR-CPA拥塞检测
R T T为当前测得的RTT, m _ R T T为周期内测得最小RTT,如式(6)所示其比值为 α
α = R T T m _ R T T
BBR-CPA采用基于预测的检测方式取代原有的固定间隔检测方式。BBR-CPA实时监测瓶颈链路,根据RTT变化趋势对拥塞状态做出预判,从而减少发包数量,提前排空拥塞。BBR-CPA每收到一个数据包时,便对其RTT进行比较,当 R T T < m _ R T T时说明链路状况良好,不做出调整;当 R T T > m _ R T T时进行后续判断。由于网络波动会造成RTT在一定程度内的波动,为增加判断的准确性,BBR-CPA设置了辅助判断条件。 θ为RTT检测阈值; s c o u n t为拥塞检测计数器; S为拥塞状态阈值。当 α > θ时,BBR-CPA算法认为当前网络发生拥塞,但网络发生故障时RTT会大幅增加,同样满足上述条件。为区分网络故障和实际拥塞造成的RTT增加,BBR-CPA根据几个连续数据包的RTT来进行拥塞状态的判断。当连续S个数据包均满足 α > θ时,BBR-CPA算法认为当前网络确实发生了拥塞,随即进入拥塞处理阶段排空拥塞。

2.2 拥塞处理机制优化

现对拥塞处理机制进行优化,采取适当的处理机制,排空链路中的拥塞。
BBR-CPA拥塞控制机制的流程如图5所示。BBR-CPA算法对拥塞处理机制进行优化,在PROBE_RTT阶段更新最小RTT的同时排空网络拥塞。BBR-CPA通过拥塞检测机制得到当前网络的拥塞状态,当BBR-CPA处于拥塞状态时,会一直处于PROBE_RTT阶段,该阶段将发送增益降低,有效排空网络拥塞。但优化后的拥塞检测机制会使得BBR-CPA频繁进入PROBE_RTT阶段。为了减少频繁进入PROBE_RTT阶段造成的时延累加,BBR-CPA不再使用固定的持续时间作为结束条件,而是检测到拥塞排空后,立即结束PROBE_RTT阶段,恢复正常传输,从而减少排队时延。
图5 拥塞处理过程

2.3 带宽更新机制优化

BBR的带宽更新机制往往会导致带宽高估和收敛较慢14,分析原因如下:BBR采用最大带宽作为估计带宽,而现实网络中的路由设备都具有一定的猝发能力,此时形成误判,即BBR误认为可以维持当前猝发速率,高估带宽导致计算的拥塞窗口偏大,进而发送过多的数据包,很可能造成网络拥塞。此外,当网络带宽波动较大时,其带宽更新机制无法及时检测到带宽下降,不能准确更新拥塞窗口大小,造成BBR向稳定运行过程的收敛速度较慢。针对上述问题,BBR-CPA在运行时实时检测瓶颈链路并记录其上带宽数据,并对带宽数据进行均值处理,尽可能减少网络波动所导致的带宽误判。

3 实验结果与分析

3.1 实验环境与评价指标

为验证BBR-CPA算法的有效性及性能,本文基于BBR拥塞控制算法在Ubuntu18.04操作系统下使用Network Simulator3(NS3)仿真工具进行仿真实验。实验拓扑为经典的哑铃拓扑,其结构如图6所示,其中S1至S5为发送端,C1至C5为接收端。参考目前普遍使用的实验环境11,实验参数如下:瓶颈链路带宽为1 Mbps,时延为10 ms,其余链路带宽为40 Mbps,时延为20 ms,运行时间为300 s。对比算法分别为经典BBR算法和最新的BBR-S14、BBR-ACD11算法。评价指标包括传输吞吐量、传输时延、RTT抖动等。RTT抖动是指在网络通信中RTT变化的不稳定性或波动性。RTT抖动可能会对实时应用和网络性能产生负面影响。在实时流媒体传输中,如果RTT抖动很大,会导致通信延迟的不稳定性,可能引起声音中断、视频卡顿等问题。

3.2 实验结果与分析

实验中存在5条数据流,由于每条数据流的变化趋势类似,这里选取流1为例进行分析。图7为不同拥塞控制算法下的信道利用率,可以看出BBR实现了较高的信道利用率,其信道利用率为96.7%。BBR-S记录了历史带宽数据,并使用带宽数据的中位数作为估计带宽,有效地克服了带宽高估问题,但导致信道利用率的下降,信道利用率最低,仅为96.4%。BBR-ACD减少了RTT波动对拥塞状态的错误判断,但其算法导致了利用率降低,为96.5%。BBR-CPA算法优化了拥塞处理过程,增加了拥塞排空时期的发包数量,有效地克服了传统改进算法导致的信道利用率下降问题,将信道利用率提升至97%。
图7 信道利用率图
图8给出不同拥塞控制算法下的时延对比情况。BBR在传输时产生了较大的时延,多达981 ms;BBR-S通过解决带宽高估问题,将时延降低至737 ms;BBR-ACD通过减少网络波动对带宽估值和RTT估值的影响,有效降低了时延,时延降低为408 ms;BBR-CPA算法通过克服拥塞检测的滞后性,大幅降低了传输时延,时延降低至376 ms。此外,BBR-CPA有效降低了时延抖动,由图8可知,除BBR-CPA之外,各算法均存在较为明显的时延抖动。BBR算法时延抖动为12.5 ms,BBR-S时延抖动为10.5 ms,BBR-ACD时延为8.6 ms,BRB-CPA时延抖动仅为7.4 ms。BBR-CPA不仅降低了传输时延,还降低了时延抖动,有效提高了传输质量。
图8 流1在不同拥塞控制算法下的时延对比图
图9给出流1在不同拥塞控制算法下的吞吐量对比情况,流2~流5基本与之类似,这里不再进行分析说明。从图9可以看出,BBR-CPA变化趋势与BBR几乎一致;BBR-ACD吞吐量波动较大,传输稳定性不足;BBR-S的稳定性最好,但在降低时延方面表现不佳。在收敛速度方面,BBR是一种基于模型的拥塞控制算法,它并没有将丢包作为当前链路拥塞的判断条件。由于其对带宽竞争的敏感性,导致链路拥塞后不限制发送速率,不断进行重传数据包,导致缓冲区一直被填满,直到不断进入拥塞排空阶段,缓慢排空数据,到40 s时BBR才开始收敛,各条流逐步趋向于稳定,不再出现较大的带宽波动。BBR-S采用带宽数据的中位数作为估计带宽,将收敛速度降低至32 s,此外其对带宽的处理方式有效地减少了5条流的波动,使得多条数据流吞吐量数据相近。BBR-ACD算法大幅降低了收敛速度,18 s时就已收敛,但其破坏了各条数据流的稳定性,导致多条数据流存在较为明显的波动。经分析,BBR-ACD导致多条数据流不断进行较为激烈的带宽竞争行为,导致吞吐量波动较大。BBR-CPA算法吞吐量波动情况与原算法一致。在收敛速度方面,BBR-CPA算法采用历史带宽数据均值作为估计带宽,大幅提升收敛速度,18 s时就实现了收敛。
图9 流1在不同拥塞控制算法下的吞吐量对比图
图10为BBR-CPA与对比算法的吞吐量数据和时延数据对比。从图10可以看出,各算法的吞吐量均值无明显差异。无论是各个流的时延还是平均时延,BBR-CPA都明显低于其他对比算法。BBR平均时延为864 ms,BBR-S为670 ms,BBR-ACD为408 ms,而BBR-CPA为375 ms。与BBR、BBR-S和BBR-ACD相比,其时延分别降低了56%、44%、8%。
图10 不同拥塞控制算法下的吞吐量、时延对比图
综上所述,在信道利用率和吞吐量方面,各算法表现类似,BBR-CPA略优于对比算法。在时延和时延抖动方面,BBR-CPA相比于其
他算法实现了大幅降低。BBR-CPA在降低传输时延和时延抖动的同时,提升了链路的收敛速度。总的来说,BBR-CPA在保证传输效率情况下,降低了传输时延和时延抖动,提高了传输质量,满足用户对高质量实时音视频服务的需求,带给用户更好的使用体验。

4 结论

本文从拥塞检测的滞后性这一角度进行研究,分析了BBR算法在网络链路中产生时延的主要原因,提出BBR-CPA算法。BBR-CPA算法基于RTT更新机制,通过对拥塞检测机制、拥塞处理机制、带宽更新机制进行优化,有效降低了传输中的时延。BBR-CPA算法通过实时检测瓶颈链路,根据RTT变化对链路拥塞状态做出预判,提前减少发包数量,消除链路中可能存在的拥塞;运行过程中记录瓶颈链路数据,并对带宽估值进行均值处理。仿真实验表明,BBR-CPA算法克服了拥塞检测的滞后性问题,在稳定传输的同时,大幅降低了传输时延,减少了时延抖动,提高了传输质量,满足用户对高质量实时流媒体资源的需求。
1
Jacobson V.Congestion avoidance and control[J]. ACM SIGCOMM Computer Communication Review198818(4):314-329.

2
Floyd S Henderson T Gurtov A.The NewReno modification to TCP’s fast recovery algorithm[J]. RFC200437(82):1-19.

3
Ha S Rhee I Xu L.CUBIC:a new TCP-friendly high-speed TCP variant[J]. ACM SIGOPS operating systems review200842(5): 64-74.

4
Gettys K Nichols J. Bufferbloat: dark buffers in the internet[J]. Queue20119(11):40-54.

5
Cardwell N Cheng Y Gunn C S, et al.BBR: congestion-based congestion control[J]. Communications of the ACM201760(2): 58-66.

6
Kleinrock L.Power and deterministic rules of thumb for probabilistic problems in computer communications[C]. Proceedings of the International Conference on Communications,Boston:IEEE,1979:1-43.

7
Soumyadeep D Fraida F.Replication: when to use and when not to use BBR[C]//Proceedings of the 2023 ACM on Internet Measurement Conference.New York:IEEE,2023:30-35.

8
Mishra Y Wee H T Leong B.Are we heading towards a BBR-dominant internet?[C]//Proceedings of the 22nd ACM Internet Measurement Conference New York:IEEE,2022:538-550.

9
Scherrer S Legner M Perrig A,et al.Model-based insights on the performance,fairness,and stability of BBR[C]//Proceedings of the 22nd ACM Internet Measurement Conference.New York:IEEE,2022:519-537.

10
Vargas S Gunapati G Gandhi A,et al.Are mobiles ready for BBR[C]//Proceedings of the 22nd ACM Internet Measurement Conference.New York:IEEE,2022: 551-559.

11
Mahmud I Kim G H Lubna T,et al. BBR-ACD: BBR with advanced congestion detection[J]. Electronics20209(1):136-154.

12
Chiariotti F Zanella A Kucera S, et al. BBR-S: a low-latency BBR modification for fast-varying connections[J].IEEE Access202132(5):76364-76378.

13
Li Q Zheng Q Yang F,et al.Improved convergence and low retransmission of BBR congestion control algorithm based on adaptive pacing gain[C]//2022 5th International Conference on Hot Information-Centric Networking (HotICN), Guangzhou:IEEE,2022:105-110.

14
Vargas S Drucker R Renganathan A,et al. BBR Bufferbloat in DASH Video[C]//Proceedings of the Web Conference 2021.New York:IEEE,2021:329-341.

15
Lynn T Ghosal D .TCP Davis:a low latency first congestion control algorithm[C]//2022 IEEE International Conference on Networking,Architecture and Storage .Philadelphia:IEEE,2022:1-7.

16
Mahmud I Papadimitriou G Cong W,et al.Elephants sharing the highway: studying TCP fairness in large transfers over high throughput links[C]//Proceedings of the SC’23 Workshops of The International Conference on High Performance Computing, Network, Storage, and Analysis New York: IEEE, 2023: 806-818.

17
董瀚泽,郭志川.BBR 拥塞控制算法在无线网络中的性能改进[J]. 哈尔滨工业大学学报201951(11): 63-67.

18
Ziegler C Neudel R Pham S,et al .Improving media streaming services for train passengers with 5G[C]//Proceedings of the 2020 ACM International Conference on Interactive Media Experiences.Barcelona:IEEE,2020:189-194.

Outlines

/