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

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

为什么需要拥塞控制?

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

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

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

v2 6a3a7b0f85bf9a664e8f9a000d80a8e7 r - BBR(瓶颈带宽和往返传播时间)拥塞控制算法

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

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

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

Tahoe 算法

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

Reno 算法

  • 发生丢包时,拥塞窗口减半并直接线性增长
v2 86c12ed3ddb2391c057f7d3598372880 720w - BBR(瓶颈带宽和往返传播时间)拥塞控制算法

New Reno 算法

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

CUBIC 算法

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

局限性

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

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

别老盯着丢包!

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

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

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

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

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

vanjacobson1 - BBR(瓶颈带宽和往返传播时间)拥塞控制算法

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

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

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

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

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

适应网络的参数变化

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

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

vanjacobson2 - BBR(瓶颈带宽和往返传播时间)拥塞控制算法
vanjacobson3 - BBR(瓶颈带宽和往返传播时间)拥塞控制算法

连接的启动

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

vanjacobson4 - BBR(瓶颈带宽和往返传播时间)拥塞控制算法

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

vanjacobson5 - BBR(瓶颈带宽和往返传播时间)拥塞控制算法

公平分配瓶颈链路

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

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

vanjacobson6 - BBR(瓶颈带宽和往返传播时间)拥塞控制算法

参考资料



发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据