拥塞算法CUBIC和BBR

发表于 分类于 阅读次数： 本文字数： 3.4k 阅读时长 ≈ 11 分钟

经典的TCP拥塞控制算法(Tahoe与Reno)

网络层TCP协议提供的主要能力之一就是拥塞控制。TCP协议的拥塞控制主要有以下两种算法组成：

  • TCP Tahoe(现在已废弃):
    • 慢开始(慢启动)
    • 拥塞避免
    • 快重传
  • TCP Reno:
    • 慢开始(慢启动)
    • 拥塞避免
    • 快重传
    • 快恢复

拥塞算法整体过程示意图

image.png

慢开始

  • cwnd指数增大：慢开始的窗口是指数增长的，慢开始中的“慢”字却是有点误导性，慢更多指的是开始的点是慢的，阈值为2，cwind=1
  • 到达阈值后进入拥塞避免阶段：到达阈值后进入拥塞避免阶段

慢启动缺点

不适用于短连接的场景：慢启动对于一些短暂的连接性能并不好，一些较旧的网页浏览器会建立大量连续的短暂链接，通过快速开启和关闭链接来请求获得文件，这使得大多数链接处于慢启动模式，导致网页响应时间差。所以现在新的网页浏览器，会通过向特殊的服务器，开启一条链接来请求获得全部的文件，而避免频繁新建大量短暂链接。不过这样对一些非请求网站所提供的服务，例如广告跟踪脚本、社交分享功能脚本、网络分析脚本等，并不适用

tips: 注意流控和拥塞控制的差别。流控强调发送和接收方之间的流量控制。过快的发送可能导致接收方来不及处理。拥塞控制对象是整个网络，通过配置、流量控制、准入控制来避免网络中存在太多数据包降低了网络的性能。

拥塞避免

  • 线增积减(AIMD): 这个概念是拥塞避免阶段针对cwnd大小行为的说明。cwnd线性增加，乘法减小。乘法减小具体和拥塞算法相关。tahoe中cwnd=1，reno中cwnd直接等于减半后的ssthresh

快速重传

  • 接收方立即确认：接收方不是等下一次发送数据捎带ack,而是立即返回确认
  • 发送方立即重传：不等超时重传计时器，收到3个重复确认后立即重传丢失的数据包
  • 重传时ssthresh减半
  • 重传后tahoe实现中cwind=1进入慢开始
  • 重传后reno实现中cwind=ssthresh直接进入拥塞避免

image.png

快恢复

  • reno实现中重传后直接进入拥塞避免称为快恢复

通过问题加深理解

有了快重传RTO还奏效吗？

答：奏效，满足RTO时间，两种拥塞算法都是将拥塞窗口降为1个MSS，然后进入慢启动阶段。这也可以理解，满足RTO说明可能真的比较网络堵塞严重，没必要再执行快恢复了。快恢复对于偶尔网络抖动导致的丢包具有比较好的容错

BIC与CUBIC

虽然tahoe和reno是很经典的并且大家都所熟悉的拥塞控制算法。但是现代Linux内核默认拥塞控制算法早已不再使用。像Linux内核2.6.18以后默认启用的都是cubic。

1
2
3
4
5
## 查看当前可用的拥塞算法
sysctl net.ipv4.tcp_available_congestion_control

## 查看当前使用哪种拥塞算法
sysctl net.ipv4.tcp_congestion_control

cubic是bic的改进版本，我们先探讨BIC
image.png

BIC

为什么reno后有BIC

BIC是binary increase congestion contrl的缩写。不同拥塞控制算法的核心差异其实都体现在拥塞避免阶段。过去reno拥塞控制算法的主要缺点是增cwnd采用的方式是累加的线性增窗（AI，additive increase)。线性增窗主要缺点是：

  • 每经过一个RTO，cwnd才加1，如果RTO很长的话，需要很久才可以恢复到比较大的cwnd值，这样性能就不好了

下图是短RTT弱网环境下TCP吞吐量的变化
image.png

BIC采binary increase的方式主要是在拥塞避免阶段采用二分查找的搜索来增加cwnd而不是像reno一样固定增加1

BIC原理

BIC相比reno的核心差别就是拥塞避免阶段增加cwnd的方式不同。BIC可以让cwnd尽快恢复到比较大的值。为了理解BIC，以下两个定义我们先需要理解：

  • Wmax: 发现丢包时(认为网络产生拥堵)，此时我们的拥塞窗口定义成Wmax
  • Wmin: 乘法减小后的cwnd值

reno拥塞避免恢复阶段恢复cwnd的过程往往是锯齿状的。
image.png
bic拥塞避免恢复cwnd的过程也是加法增加的，只不过每次不是增加1，而是采用二分查找的探测手段决定到底需要加多少。其cwnd的恢复过程如下。cwnd能以较快的方式接近Wmax并且尽量维持多的时间。BIC相比reno主要带来以下好处：Wmax收敛快，相比reno可以更快的收敛到Wmax。

image.png
上图曲线右侧的过程是max cwnd的探测过程。BIC在cwnd超过Wmax以后，如果长时间未发生丢包，认为网络情况良好，则会慢慢增加cwnd的窗口取抢占更多带宽资源。

如何通过二分查找确定cwnd增加的值

就是不断递归 newWmin =(Wmax+Wmin)/2的过程即可：
image.png

BIC的缺点

正所谓，成也萧何败也萧何。快速收敛到Wmax在长RTT的情况下，是比较适合的，但是在短RTT的劣网环境下，激进的增窗会引发带宽的争抢，使得拥塞控制不具备公平性。公平性指的是新链路也可以像老链路一样公平的去获取带宽资源。显然BIC在短RTT劣网环境下会破坏这个公平性。

因为为了改进短RTT劣网环境下BIC公平性的问题，就引入了CUBIC

CUBIC

cubic实际上是一种改进的BIC。BIC在短RTT下增窗快，本质是因为其算法依赖RTT。CUBIC的实现方式整体和BIC一样，只不过增窗不再依赖RTT，而是根据一个公式来决定增窗的值。根据这个公式，整个增窗曲线还是会和BIC保持差不多的形态，只不过不会在短RTT场景下再有快速增窗的问题了：
image.png

CUBIC的论文可以参考：CUBIC: A New TCPFriendly HighSpeed TCP Variant
思路本质上就是先构造一个函数，使得函数曲线和BIC的曲线近似，然后就只依赖函数中的变量值来控制增窗就可以，而不是依赖RTT。

下图是论文中演示CUBIC在长RTT和短RTT网络环境中带宽情况：
image.png

BBR

基本介绍

bbr是google 2016年发布的拥塞算法,2019年更新成bbrv2，也是google内部默认使用的tcp拥塞算法，算是当前最强的拥塞算法了（截止这篇文章的时间）。google论文中提到在youtube中应用后有整体有53%的延迟降低，发展中国家的请求更是降低了80%的延迟。

之前探讨的reno、cubic本质上都是一种window based的拥塞控制算法。而BBR则是一种sending rate based算法。大概是得益于cubic的启示，google提出bbr算法显然是更加基于数学模型了，摒弃了一些在现代网络环境下并不是特别严谨的假设，例如遇到重传则认为网络拥堵需要开始减速。

以往大部分拥塞算法是基于丢包来作为降低传输速率的信号，都属于基于丢包反馈的被动式机制(Loss-Based)。主要缺点是：

  • 丢包即拥塞的假设不一定完全正确：现实中网络环境很复杂会存在错误丢包，很多算法无法很好区分拥塞丢包和错误丢包，因此在存在一定错误丢包的前提下在某些网络场景中并不能充分利用带宽。
  • bufferbloat问题：路由器、交换机等设备缓冲区在Loss-Based策略中也计算了，然而现在网络设备都有比较大的网络设备缓冲区，TCP发送端真正感知到拥塞和时机产生的时间会产生比较大的误差。网络已经拥塞，但是发送端在发现之前还在增大窗口，这就使得网络更加拥堵不堪了，在弱网、高延迟的环境中，这个问题会更加严重。
  • 网络负载高、无丢包时Loss-Based策略仍然增窗：增加了网络带宽的竞争
  • 高负载丢包、网络抖动：reno、cubic这种windows based的都有这个问题，就是带宽侵略性，不断增加窗口，最终必然导致乘法减小，网络抖动。
  • 低负载高延迟丢包时带宽利用率低：有些丢包时因为弱网环境下延迟导致，而不是带宽争抢导致的拥塞导致，此时根据loss-based策略，带宽利用率比较低

BBR基于模型主动探测。该算法使用网络最近出站数据分组当时的最大带宽和往返时间来创建网络的显式模型。数据包传输的每个累积或选择性确认用于生成记录在数据包传输过程和确认返回期间的时间内所传送数据量的采样率。

可以用BBR来替代其他流行的拥塞算法例如CUBIC。BBR之后移植入Linux内核4.9版本，并且对于QUIC可用。

基本原理

如果下面理解还看不懂，建议看下参考资料原始论文。

前置概念BDP

BDP是Bandwidth-Delay Product的缩写，可以翻译为带宽延时积，我们知道带宽的单位是bps(bit per second)，延时的单位是s，这样BDP的量纲单位就是bit，从而我们知道BDP就是衡量一段时间内链路的数据量的指标。这个可以形象理解为水管灌水问题，带宽就是水管的水流速度立方米/s，延时就是灌水时间单位s，二者乘积我们就可以知道当前水管内存储的水量了，这是BBR算法的一个关键指标，来看一张陶辉大神文章中的图以及一些网络场景中的BDP计算：
image.png

拥塞控制的本质

拥塞的本质是偏离BDP的过程。未到达BDP时，说明网络这根水管没满，随着数据的发送量增加RTT也不基本不会变化，发送速率随着发送数据增加还会持续增加。超过第一个BDP时，这时候已经达到BDP的限制，也就是说发送速率受到带宽限制了(bandwith limited)，RTT还会增加时因为有网络设备buffer。

拥塞控制的本质是控制偏离BDP的过程。过去一些理论论文证明最优的控制点(optimum operation point)是bandwith limited开始的时候。但是我们现在的拥塞控制算法实现都是考虑了设备buffer，有bufferbloat问题，因此就不是最优的了。
image.png
理解了拥塞控制的本质后，看BBR算法的流程也就会更加理解一些了

BBR拥塞控制流程

基本流程分为4个阶段：
image.png

  • STARTUP: 这个阶段启动是为了在指定数量个RTT窗口内探测出BDP。不过用于探测算法本身的限制，这个过程中会导致缓冲中额外积压2个BDP
  • DRAIN：把多余的2个BDP缓存排出，使得inflight的数据量在1个PDB，然后就可以进入最优的介入时间了
  • PROBE_BW: 控制BDP偏离，必然要探测带宽和RTT。由于网络带宽的变化要比RTT更为频繁，因此ProbeBW阶段也是BBR的主要阶段，在探测期中增加发包速率如果数据包ACK并没有受影响那么就继续增加，探测到带宽降低时也进行发包速率下降。
  • PROBE_RTT：前面三个过程在运行时都可能进入ProbeRTT阶段，当某个设定时间内都没有更新最小延时状态下开始降低数据包发送量，试图探测到更小的MinRTT，探测完成之后再根据最新数据来确定进入慢启动还是ProbeBW阶段。

只要能实时获取到计算的BDP，就可以调节发送速率来避免拥塞。看了流程应该可以理解和过去windows based的拥塞算法的差别。

参考资料