BBR（瓶颈带宽和往返传播时间）拥塞控制算法

为什么需要拥塞控制？

在网络上传输数据就像在水管中传输水流。假如我们要通过一根参数未知的水管输水，输得多了水管会爆裂，输得少了效率会降低，如何传输就是一个关键的问题。

• 最开始的时候，我们不知道这根水管能承受多大的速率，我们可以监控水管的状况，并且逐渐开大阀门，直到发现状况异常；
• 如果输水过程中，水管被砸了一下而变窄了（或者突然改道变宽了），以前的速率可能过大（或过小），为了适应新的参数，我们可能需要调整速率，比如把阀门关上重新逐渐开大。

也许上面的策略不是最好的策略，我们还可以制定更好的策略让调整的时间变短，从而使输水的效率增加。这种调整的策略就是拥塞控制算法。

根据上述场景，我们可以确定理想的拥塞控制算法满足的要求：

• 能在尽量短时间内获得当前链路的传输能力；
• 能及时适应链路的波动，确定较合适的传输速率。

以前我们是怎么进行拥塞控制的？

Tahoe 算法

• 拥塞窗口：最大允许没有收到 ACK 确认的包的数量
• 慢启动：每收到一个 ACK，拥塞窗口指数增长，直到丢包或达到慢启动阈值
• 发生丢包时，重传丢包并重新慢启动，达到慢启动阈值后线性增长

Reno 算法

• 发生丢包时，拥塞窗口减半并直接线性增长

New Reno 算法

• 仅对重传部分的效率有优化

CUBIC 算法

• 窗口大小是上次拥塞事件以来的时间的三次函数
• 利用三次函数的凹部分和凸部分实现快速启动、平缓增长
• 不依赖 ACK 包，与延迟无关
• 适应于长胖网络：高带宽、高延迟

局限性

容易发现，上述几种算法都基于对丢包的判断和处理来进行拥塞控制。但是现在，丢包和拥塞的关系不那么紧密了，这些算法对于高延迟、高带宽、有一定丢包率的网络并不能达到最大传输效率。

怎么解决基于丢包的拥塞控制算法的问题？

别老盯着丢包！

既然丢包不是一种合适的判断方法，那么我们干脆不以丢包作为拥塞控制的依据，而是另寻其他信息。

Google 的研究人员对世界各地的大量 TCP 头部进行研究，确定了一种新的判断依据：瓶颈带宽（Bottleneck Bandwidth）和往返传播时间（Round-trip Propagation Time）。

• 瓶颈链路：在网络中，一个连接的一段最慢的链路
• 瓶颈带宽：瓶颈链路的带宽
• 往返传播时间

考虑正常行驶的高速公路上突然发生了交通事故，这会导致局部通行速率降低，使得该处有车辆形成队列，从而使整条道路的通信速率降低。瓶颈带宽就是事故处的通行速率，而往返传播时间可以代表道路的长度。

瓶颈带宽、往返传播时间和流行为的关系

丢包往往发生在图中缓存限制的区域，因此传统的 TCP 拥塞控制算法事实上只能将传输情况控制在该区域的边界附近。在此处，网络的延迟较大，缓存队列较慢，并不是最优方案。

通过 BBR 算法，我们可以以瓶颈带宽、往返传播时间来控制传输，使得网络中不存在缓存队列。这相当于控制向水管注水的速率，使水管中最细的一段恰好填满且没有水堆积在近端。

计算出瓶颈带宽、往返传播时间

往返传播时间是链路的物理特性，可以视作不会改变，因此可以统计一段时间内的延迟最小值作为往返传播时间。

我们无法直接对瓶颈带宽进行计算，但可以用间接的方法。可以统计一个包从发出到收到 ACK 的时间间隔，在统计这段时间内的未确认包数，就可以计算出瓶颈带宽。

适应网络的参数变化

由于网络可能不断产生变化，瓶颈带宽、往返传播时间也应该进行实时的估计与调整。但当网络带宽增大时，上述过程并不会主动探测到带宽的增大。

BBR 使用 pacing 作为试探瓶颈带宽的方式，每次将窗口设置为比当前瓶颈带宽稍大的值，重新统计速率，即可判断当前状况处于临界点的哪一边。如果处于临界点右侧，则之后使用比瓶颈带宽稍小的值来消除网络中的队列。

连接的启动

BBR 在连接启动时，使用指数上升的规律增大发送速率，直到探测出瓶颈带宽。一旦找到瓶颈带宽，BBR 使用增大倍数的倒数消耗队列，之后保持上述稳定状态。

BBR 可以主动消耗网络中的队列，而传统的拥塞控制算法无法消耗网络中的队列，这是 BBR 的优势。

公平分配瓶颈链路

在新的连接建立之前，可能已有一些连接占满了瓶颈链路，BBR 需要平均分配链路，使得新建立的连接也可以分配到传输资源。

当一段时间内往返传播时间没有改变时，BBR 主动将窗口减小，使得网络中队列被消耗，其他连接得到了更小的往返传播时间，使得其他连接也主动减小窗口，之后同时开始回到原状态，从而实现资源的重新公平分配。

参考资料

• 力扣（LeetCode）．面试头条你需要懂的 TCP 拥塞控制原理．知乎 https://zhuanlan.zhihu.com/p/76023663
• TCP拥塞控制．维基百科 https://zh.wikipedia.org/wiki/TCP%E6%8B%A5%E5%A1%9E%E6%8E%A7%E5%88%B6
• yue2388253．BBR论文中文翻译．CSDN https://blog.csdn.net/yue2388253/article/details/88925203
• CUBIC TCP．维基百科 https://zh.wikipedia.org/wiki/CUBIC_TCP
• TCP BBR congestion control comes to GCP – your Internet just got faster．Google Cloud Blog https://cloud.google.com/blog/products/gcp/tcp-bbr-congestion-control-comes-to-gcp-your-internet-just-got-faster
• Neal Cardwell, …．BBR: Congestion-Based Congestion Control．Communications of the ACM https://cacm.acm.org/magazines/2017/2/212428-bbr-congestion-based-congestion-control/fulltext https://queue.acm.org/detail.cfm?id=3022184