拥塞控制算法——BBR

Myth丶恋晨 2022-10-15 10:46 532阅读 0赞

# 拥塞控制算法——BBR #

--------------------

## 目录 ##

1.  BBR产生的背景
    
    1.  TCP算法存在的问题
    2.  BBR算法的特点及核心
2.  BBR算法基本原理
    
    1.  BBR结构图
    2.  即时带宽的计算
    3.  BDP
    4.  BBR状态机
3.  BBR算法的优缺点
    
    1.  抗丢包能力强
    2.  低延迟/抢占能力强
    3.  平稳发送
    4.  收敛速度慢/高于一定丢包率吞吐量下跌
    5.  深队列竞争不过Cubic
    6.  算法公平性/抗抖动能力
4.  BBR应用在实时音视频领域
    
    1.  BBR在实时音视频领域的优势
    2.  BBR在实时音视频领域存在的问题
    3.  收敛速度/抗丢包能力解决办法
    4.  ProbeRTT阶段问题解决办法
    5.  Padding/RTT不公平问题
    6.  Cubic与BBR对比
    7.  BBR与GCC对比

--------------------

### 1. BBR产生的背景 ###

1.  拥塞控制始于20世纪80年代，当时TCP是滑动窗口的算法，拥塞窗口固定，需要通过不断地响应报文推动滑动窗口前进。但在1986年TCP导致了拥塞崩溃，比如现在多端采用TCP发起报文，实际带宽达不到所能提供的最大带宽时网络出现拥堵，此时会有越来越多的TCP发起重试，进而加剧拥堵情况。
2.  2000年之后伴随着互联网大爆发，各类应用特别是音视频应用数量大幅增加，**TCP拥塞控制算法无法满足当前互联网应用对网络传输高实时性、高带宽利用率、高吞吐量的需求**，在这种背景下BBR应运而生。

#### 1. TCP算法存在的问题 ####

1.  在互联网发展的过程当中，TCP算法也做出了一定改变，先后演进了Reno、NewReno、Cubic和Vegas，这些改进算法大体可以分为**基于丢包和基于延时的拥塞控制算法**。
2.  基于丢包的拥塞控制算法以Reno、NewReno为代表，它的**主要问题有Buffer bloat和长肥管道两种**，基于丢包的协议拥塞控制机制是被动式的，其依据网络中的丢包事件来做网络拥塞判断。即使网络中的负载很高，只要没有产生拥塞丢包，协议就不会主动降低自己的发送速度。最初路由器转发出口的Buffer 是比较小的，TCP在利用时容易造成全局同步，降低带宽利用率，随后路由器厂家由于硬件成本下降不断地增加Buffer，基于丢包反馈的协议在不丢包的情况下持续占用路由器buffer，虽然提高了网络带宽的利用率，但同时也意味着发生拥塞丢包后，网络抖动性加大。另外对于带宽和RTT都很高的长肥管道问题来说，管道中随机丢包的可能性很大，TCP的默认buffer设置比较小加上随机丢包造成的cwnd经常下折，导致带宽利用率依旧很低。
3.  基于延时的拥塞控制算法以vegas为代表，但当vegas出现时，基于丢包的拥塞控制算法在市面已经占据主流，vegas抢不到带宽出现“饿死”现象，因此也没办法与之抗争。
4.  在BBR出现之前，TCP的拥塞控制一直逃脱不了这两个方向，另外优化TCP的拥塞控制难免涉及到内核的修改，这也是限制TCP继续优化的一大问题。

#### 2. BBR算法的特点及核心 ####

1.  \*\*BBR（Bottleneck Bandwidth：瓶颈带宽 and Round-trip propagation time：往返传播时间）是一种基于带宽和延迟反馈的拥塞控制算法。\*\*目前已经演化到第二版，是一个典型的封闭反馈系统，**发送多少报文和用多快的速度发送这些报文都是在每次反馈中不断调节**。在BBR提出之前，拥塞控制都是基于事件的算法，需要通过丢包或延时事件驱动；**BBR提出之后，拥塞控制是基于反馈的自主自动控制算法，对于速率的控制是由算法决定，而不由网络事件决定，算法核心是“不排队”。**

--------------------

### 2. BBR算法基本原理 ###

#### 1. BBR结构图 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]

1.  **BBR算法的核心是找到最大带宽（Max BW）和最小延时（Min RTT）这两个参数，最大带宽和最小延时的乘积可以得到BDP(Bandwidth Delay Product), 而BDP就是网络链路中可以存放数据的最大容量**。BDP驱动Probing State Machine（探测状态机）得到Rate quantum和cwnd，分别设置到发送引擎中就可以解决发送速度和数据量的问题。

#### 2. 即时带宽的计算 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]

1.  一般情况下的即时带宽计算，很多人认为将发送报文和收到报文的时间点记录下来，发包数量再除以时间就可以得到带宽，但这样的计算方式是错误的。由于delay feedback表示一组报文的响应，一组报文之后会有一个延迟的相应来通知哪些报文没有收到，以及收到的时间差是多少。delay feedback容易受到网络影响，因此报文不会均匀发送，易发生聚合和丢包现象，在计算时要考虑发送的时间差和ack的时间差，公式为：bandwidth = delivered/max（send time,ack time），这样才能抵消掉延迟聚合和丢失的情况。

#### 3. BDP ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]

1.  BDP（带宽延迟积）是BBR算法中的核心，其中最大带宽和最小延迟不能同时得到。如图所示，横轴是网络链路中的数据量，纵轴分别是RTT和带宽，在RTT不变的时候，网络没有发生拥塞，带宽一直在上升，没有达到最大，而当带宽停止上涨的时候，网络开始拥塞，RTT持续变大，直到发生丢包。图中BDP所标识的点就是理想情况下最大带宽和最小延时。很明显只有在没有发生拥塞时才能得到RTT的数值，因此很难在同一时刻找到最小的RTT和最大带宽。

#### 4. BBR状态机 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 3]

1.  既然最大带宽和最小延迟不能同时得到，必然存在探测最大带宽和最小RTT的过程。上图表示的是BBR的状态机，状态机分为Startup，Drain，ProbeBW，ProbeRTT4个阶段。Startup阶段类似于普通拥塞控制里的慢启动，以2/ln2的增益系数持续更新发包速率，带宽连续三次没有增长就可以判定达到最大带宽而进入Drain状态。
2.  进入Drain状态时队列可能存在拥堵，因此需要把 Startup状态中产生的队列排空，排空的速率是ln2/2，如果inflight < BDP 说明此时网络由BBR造成的拥塞已经全部排空，如果 inflght > BDP 说明此时网络还有拥塞，不能进入下一个状态。
3.  拥塞排空之后会进入探测带宽阶段，探测最大带宽的方法是在10个RTT中观测到的最大带宽，以此数据作为最大带宽。如果10s没有得到最小RTT，超时之后需要继续探测最小RTT。探测最小RTT需要尽量避免网络拥堵，降低拥塞窗口，发送比较少的报文。整个BBR的拥塞控制在启动之后，最终是在Drain和ProbeBW阶段之间切换。

--------------------

### 3. BBR算法的优缺点 ###

1.  BBR相对TCP的**优点包括抗丢包能力强、延迟低、抢占能力强和平稳发送**。在BBR算法之前的TCP Cubic，拥塞控制算法并没有平稳发送的说法，而只是判断发送与否的问题，BBR算法出现之后，会平稳的发送数据，不会突发流量冲击。BBR相对TCP的优点包括抗丢包能力强、延迟低、抢占能力强和平稳发送。

#### 1. 抗丢包能力强 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 4]

1.  关于BBR算法的抗丢包能力可以用上图来说明，BBR算法不会因为一次或者偶然的丢包就大幅降低吞吐量，因此具有较强的抗丢包能力。

#### 2. 低延迟/抢占能力强 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 5]

1.  对于BBR在低延迟方面的优势来说，由于目前关于拥塞控制的算法很多，BBR在运转时设备中可能会有多种拥塞控制算法同时作用的情况，BBR算法只能保证自己不排队。但在实际现行网络下，是否排队并不由BBR一个算法决定，运行过程中BBR算法不会加重网络拥塞。
2.  在带宽探测阶段，BBR算法每一轮都会尝试上探更大的带宽，由此可以很快抢占其他拥塞算法让出来的带宽，这也是BBR算法抢占能力强的原因。

#### 3. 平稳发送 ####

1.  之前提到在TCP算法中并没有平稳发送的说法，BBR算法后来引入了平稳发送的概念，不只解决了发送多少的问题，还解决了发送速率的问题，具体实现是使用cwnd控制发送数量，发送速度使用漏桶算法控制。BBR算法中的cwnd与TCP算法不同，TCP算法中的cwnd是对网络状态的模拟，分为发送窗口和接收窗口，而BBR算法只有发送窗口，且cwnd = 2\*BDP。

#### 4. 收敛速度慢/高于一定丢包率吞吐量下跌 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 6]

1.  BBR算法在具备一些优势的同时也存在一定的缺点，比如原始的BBR算法收敛性受到pacing gain周期影响，带宽突降的时候，BBR需要多个轮次才会降到实际带宽。这其中的原因是BBR每轮只能降速一次，而pacing gain的6个RTT的保持周期大大加长了这个时间。由于pacing gain上探周期的1.25无法抵消掉25%以上的丢包，这会造成带宽反馈持续下降，BBR吞吐量就会断崖式下跌。

#### 5. 深队列竞争不过Cubic ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 7]

1.  BBR算法设计之初cwnd = 2\*BDP，在此之前BBR算法要比Cubic强很多，但在实际的网络环境中，如果出现buffer很大的情况，BBR是比Cubic竞争性差的，因此在应用BBR算法时必须了解当前的网络状况。

#### 6. 算法公平性/抗抖动能力 ####

![在这里插入图片描述][20210524203120492.png]

1.  在算法公平性方面，BBR在与Reno竞争时可以占用90%以上的带宽，但在与多个BBR流竞争时，RTT高的流占用带宽更高，其中也暴露的漏洞是如果想占用更高带宽，可以人为调高RTT的值，这些并不是BBR算法的设计初衷。在抗抖动能力方面，RTT的抖动使BBR无法得到准确的BDP，探测带宽很有可能低于可用带宽。

--------------------

### 4. BBR应用在实时音视频领域 ###

#### 1. BBR在实时音视频领域的优势 ####

![在这里插入图片描述][20210524205022744.png]

1.  如果将BBR算法应用在实时音视频领域，需要满足带宽（特别是低带宽场景）探测准确，适合实时音视频传输的低延时需求，能够满足音视频传输码率平稳的需求以及快速响应带宽变化这四个要求。

#### 2. BBR在实时音视频领域存在的问题 ####

![在这里插入图片描述][20210524205106288.png]

1.  满足以上四个实时音视频需求的同时，BBR算法在应用时也存在着收敛速度慢、抗丢包能力无法达到预期的问题，另外实时音视频领域需要提供稳定的视频流，但BBR的ProbeRTT阶段只发4个包，发送速率下降太多会引发延迟加大和卡顿问题，最后BBR探测带宽需要Paddin有可能造成带宽浪费。

#### 3. 收敛速度/抗丢包能力解决办法 ####

![在这里插入图片描述][20210524205206916.png]

1.  针对BBR应用在实时音视频领域遇到的问题，目前已经有不少解决方案。对于收敛速度慢的问题来说，BBR V2提出在Probe Down一次排空到位（inflight < BDP），另外还可以随机化6个1x平稳发送周期，缩短排空所需要的时间。对于抗丢包能力不足的问题来说，目前BBR算法的抗丢包能力是足够的，但在一些极端网络条件下可以把丢包率补偿到pacing rate，有效提升抗丢包能力。

#### 4. ProbeRTT阶段问题解决办法 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 8]

1.  ProbeRTT并不适用实时音视频领域，因此可以选择直接去除，或者像BBR V2把probe RTT缩短到2.5s一次，使用0.5xBDP发送。

#### 5. Padding/RTT不公平问题 ####

![在这里插入图片描述][20210524205320632.png]

1.  为了保持带宽竞争性和平稳发送，BBR中的padding不可或缺，想要迅速感知带宽变化也必须有padding的存在。关于RTT不公平问题之前有提到RTT大占据的带宽多，但在排空阶段一次排空就可以缓解这个问题。

#### 6. Cubic与BBR对比 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 9]

1.  由上图整体可以看出BBR带宽利用率要高于Cubic。

#### 7. BBR与GCC对比 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 10]

1.  目前GCC控制算法在实时音视频领域占据主流，但WebRTC的GCC算法仍然有一些局限性，比如将带宽限制在300k，一段时间后取消限制的场景来对比，由图像对比可以得到，BBR比GCC的带宽估计更加准确（GCC:250k,BBR:300k），而在带宽限制取消后，GCC需要20s以上才能恢复到最大带宽，BBR仅需要2s就可以恢复。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 11]

1.  如果将带宽限制在2.5Mbps，加入200ms delay，200ms jitter，此场景中GCC和BBR的表现如图所示，GCC带宽探测只有300k，而BBR带宽维持在2.5M附近波动，在如此恶劣的网络环境中BBR的表现已经是相当优秀了。
2.  总结来看，BBR算法有很多优点的同时也有很多缺点，目前没有一个算法能够适用所有的网络状态，针对不同的网络状态选择不同的拥塞算法似乎是一个可行的办法，但基于当前拥塞算法，融合其他算法的优点也是可以实现的，在此希望能够涌现出更多有兴趣的人为实时音视频领域的拥塞算法出力。

转载：https://zhuanlan.zhihu.com/p/87375044

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: /images/20221014/324a759b5d204440b71cb949f0a1e573.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: /images/20221014/c462a71aa9d149358f3a52b32e81ddb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]: /images/20221014/27731f1c69b045bba2c84b348b23eacd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 3]: /images/20221014/fa2472f62689446fa400fd437f59b9f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 4]: /images/20221014/539273dcc6944f5281e993ddc95c9051.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 5]: /images/20221014/c68ce3dcb79e4fab8184550890682ad4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 6]: /images/20221014/f22aa59a1d3c479eaaaa1e6ab1ab77a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 7]: /images/20221014/011ebef959d7442f93e0dc4da2df72ee.png
[20210524203120492.png]: /images/20221014/25dffb1028544640aa1f47333f137217.png
[20210524205022744.png]: /images/20221014/8efe7122702848269e537f8bcb90c3c8.png
[20210524205106288.png]: /images/20221014/9af760d61e284292b1f66c4d00139d79.png
[20210524205206916.png]: /images/20221014/58489d29befe459fb7888a34bfed5d61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 8]: /images/20221014/13bfe75d2ea0465b81a2660a9f364836.png
[20210524205320632.png]: /images/20221014/26bd7f36fa4c4d5981d60b01250fc159.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 9]: /images/20221014/c4433ff5d897492db725781c108fd43c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 10]: /images/20221014/f542d6b7430c499196f0f3f316442794.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 11]: /images/20221014/b2a09e124f6243b7b18e6863099e20ee.png