xSky 实验室关注高性能计算,分布式系统/存储,大数据/机器学习/WebRTC

BBR拥塞控制算法

2022-01-15 13:40:26

在阅读WebRTC源码的过程中，发现已被弃用的BBR算法有不少值得深入研究的地方。

本文为译文，原文见BBR Congestion Control

1.介绍

互联网曾广泛使用基于丢包的拥塞控制算法，例如Reno（[Jac88], [Jac90], [WS95] [RFC5681]）和 CUBIC（HRX08, draft-ietf-tcpm-cubic），这类算法认为丢包和拥塞是等效的。长久以来这类算法都运作的很好，但这并不能说明他们是绝对正确的。这种良好的表现是由于网络交换机和路由器的缓冲区都十分适配当时的网络带宽。而一旦发送者的发送速率足够快，缓冲区便会被快速填满，进而引发丢包。

实际上丢包并不等效于拥塞。拥塞可以被看作是一种在网络路径中，传输中的数据量始终大于带宽-时延积的场景。随着互联网的不断发展，丢包现象在非拥塞场景下也频繁发生。而基于丢包的拥塞控制策略给网络带来了源源不断的问题：

浅缓存：在浅缓存场景下，丢包往往发生在拥塞之前。高速、长距离的现代网络，搭配上消费级的浅缓存交换机，基于丢包的拥塞控制算法可能会导致极其糟糕的吞吐量，而这种现象则归咎于这类算法对于丢包的过激反应。流量突发引起的丢包会使发送速率乘性递减（这种丢包现象在空闲网络中也会频繁发生）。这种动态特性，使得基于丢包的拥塞控制算法在实际应用中很难对网络带宽进行充分利用：维持10Gbps/100ms RTT的网络，必须要求其丢包率在0.000003%以下。而更为实际的1%的丢包率，则会导致其只能维持在3Mbps/100ms（无论是瓶颈带宽的性能如何）。
深缓存：在有着深缓存的瓶颈链路中，拥塞往往发送在丢包之前。在现今的的边缘网络中，基于丢包的拥塞控制算法对众多最后几英里的设备，进行了深缓存的反复填充，引发了不必要的数秒级的排队延时，也就是“缓冲膨胀”的问题。

BBR拥塞控制算法使用了另类的方式：不用丢包去衡量拥塞是否发生，而是直接对网络建模来避免以及应对真实的拥塞。

BBR算法已经在之前的论文中大致描述过 [CCGHJ16] [CCGHJ17]，活跃性的社区工作也在持续进行中。该文档将对现有的BBR算法进行详细解释。

该文档将以下列形式进行组织：第二节将会给出多种术语定义。第三节是对BBR算法的设计概述。第四节将对BBR算法进行细节分析，包括BBR的网络路径模型，控制参数以及状态机。

2.术语

该文档为BBR算法定义了如下状态变量和常量：

BBR.pacing_rate：当前BBR流的pacing rate，用于控制发包间距。
BBR.send_quantum：用于传输的被规划的最大数据集的大小。
cwnd：发送端的拥塞窗口，用于限制传输中的数据量。
BBR.BtlBw：估算的传输通道的瓶颈带宽，源自滑动窗口的最大投递速率样本。
BBR.BtlBwFilter：用于估算BBR.BtlBw的最大值过滤器。
BtlBwFilterLen：用于BBR.BtlBwFilter的BBR.BtlBw的最大过滤窗口的常数。BtlBwFilterLen为10个包的往返。
BBR.RTprop：估算的该路径的双向往返传播延时，源自滑动窗口的最小往返延时样本。
BBR.rtprop_stamp：当前BBR.RTProp样本获取时的时戳。
BBR.rtprop_expired：标记BBR.RTprop是否过期的布尔变量，过期原因可以是周期性刷新或转移到ProbeRTT状态。
RTpropFilterLen：用于描述RTProp最小过滤窗口的常数，RTpropFilterLen为10s。
BBR.pacing_gain：用于计算BBR.pacing_rate的BBR.BtlBw的动态增益系数。
BBR.cwnd_gain：用于计算拥塞窗口(cwnd)的BDP的动态增益系数。
BBRHighGain：发送速率的增益系数(2/ln(2) ~= 2.89)，也是Startup阶段的BBR.pacing_gain和BBR.cwnd_gain的最小增益。
BBR.filled_pipe：用于记录("装满管道")的布尔变量，即已完全利用可用带宽。
BBRMinPipeCwnd：可使用的最小cwnd值：4个包，或4倍SMSS。
BBR.round_count：以包为单位的往返计数。
BBR.round_start：表示在一个往返开始的布尔变量，即ACKs超过BBR.round_count。
BBR.next_round_delivered：packet.delivered标志着一个往返的结束。
BBRGainCycleLen：ProbeBW阶段增益周期的阶段数(8)。
ProbeRTTInterval：两个ProbeRTT阶段之间的最小时间间隔：10s。
ProbeRTTDuration：ProbeRTT阶段，保持发送中的数据为BBRMinPipeCwnd或更少包数的最小持续时长：200ms。
SMSS：发送端最大分片大小(The Sender Maximum Segment Size)。

3.设计概览

3.1 网络路径模型

BBR是基于模型的拥塞控制算法：其行为方式是对传输流通过的网络路径的确切模型的表现。BBR模型包括两个估算参数：

BBR.BtlBw：估计的传输通道的瓶颈带宽，估算自滑动窗口的最大传发送速率样本。
BBR.RTprop：估计的该路径的双向往返传播延时，估算自滑动窗口的最小往返延时样本。

3.2 目标操作点

BBR使用该模型来探求高吞吐量低延时的工作区。为了在最优点（即达到最大吞吐量并且维持最小延时 [K79] [GK81]）附近运作，该系统需要维护两个条件：

速率平衡：数据包的到达速率等于传输流的瓶颈带宽。
充盈管道：路径中处于传输状态的数据量等于BDP。
BBR使用该模型去维护网络的最佳工作区。为了达到速率平衡，BBR使用pacing让数据包以接近BBR.BtlBw的速率进行发送。为了达到充盈管道，BBR对pacing rate进行调制，来保持传输中的数据量接近估算得到的带宽延时积（BDP），或BBR.BtlBw * BBR.RTprop。

3.3 控制参数

BBR使用该模型去控制网络的发送行为，让其保持在目标工作区附近。与Reno和CUBIC不同的是（他们使用单一控制变量，如使用cwnd来限制传输中的数据量），BBR使用三个独特的控制参数：

pacing rate：BBR发送数据的速率。
send quantum：发送端为了均衡单包传输开销而规划的，可发送的单个包的最大集合大小，。
cwnd：在任意时刻，BBR允许网络中处于传输状态的数据量的最大值。

3.4 状态机设计概览

BBR使用一个清晰明了的状态机来维护三个控制参数。该状态机通过交替循环探测BBR.BtlBw和BBR.RTprop，来实现高吞吐量、低延时、近似公平的带宽共享。
BBR起始于Startup状态，该状态下会迅速提升发送速率。当预估到网络管道被填满时，则进入Drain状态，开始排放管道队列。已处于稳态的BBR流将只使用ProbeBW状态，去周期性地短暂地提升传输中的数据量，来探测更高的BBR.BtlBw样本。ProbeRTT状态下（如果需要的话），会短暂地降低传输中的数据量，去探测更低的BBR.RTprop样本。

3.4.1 状态转移图

下面的状态转移图总结了控制流程以及不同状态间的关系：

        |
        V
+--->Startup----+
|       |       |
|       V       |
|     Drain-----+
|       |       |
|       V       |
+--->ProbeBW----+
|    ^     |    |
|    |     |    |
|    +-----+    |
|               |
+----ProbeRT<---+

3.5 算法组织

BBR算法执行步骤：连接初始化，ACK，传输。如下说明：

3.5.1 初始化

BBR执行如下步骤来初始化传输连接：

BBROnConnectionInit():
    BBRInit()

3.5.2 每个ACK后的步骤

每收到一个ACK，BBR都会执行BBRUpdateOnACK( )来更新网络模型和状态机，并且调整控制参数去适应更新后的模型：

BBRUpdateOnACK():
    BBRUpdateModelAndState()
    BBRUpdateControlParameters()

  BBRUpdateModelAndState():
    BBRUpdateBtlBw()
    BBRCheckCyclePhase()
    BBRCheckFullPipe()
    BBRCheckDrain()
    BBRUpdateRTprop()
    BBRCheckProbeRTT()

  BBRUpdateControlParameters()
    BBRSetPacingRate()
    BBRSetSendQuantum()
    BBRSetCwnd()

3.5.3 传输步骤

传输时，BBR只需要检测该空闲数据流是从哪种状态下重启的。

3.6 环境和使用

BBR算法对于传输层和链路层来说是不可见的，其只会改变发送端的行为，而不会对网络进行改变。BBR的开源实现可从TCP [RFC793]和QUIC协议[draft-ietf-quic-transport-00]中获取。这些实现已被用于大规模网络流量的实际场景中。

4.算法细节

4.1维护网络路径模型

如上文所述，BBR是基于模型的拥塞控制算法：其行为方式是对传输流通过的网络路径的确切模型的表现。BBR模型包括两个估算参数：BBR.BtlBw和BBR.RTprop。

4.1.1 BBR.BtlBw

BBR.BtlBw是估计的传输流可用的瓶颈带宽大小。传输链接中的数据通常都会经历一个极慢的链路或者说是瓶颈。瓶颈发送速率决定了该链路的最大发送速率。BBR尝试让发送速率与瓶颈速率接近，以寻求“速率平衡”，也就是数据包的到达速率等于BBR.BtlBw。瓶颈速率在链接的整个生命周期中不断变化，因此BBR使用最近的发送速率样本去持续估算BBR.BtlBw。

4.1.1.1 用于估计BBR.BtlBw的发送速率样本

计算发送速率样本的过程十分精妙，该样本是独立于拥塞控制的，BBR使用的用于计算每个发送速率样本的方法在另一篇文档中详述 [draft-cheng-iccrg-delivery-rate-estimation]。

4.1.1.2 BBR.BtlBw Max过滤器

物理传输中的随机变化（如：无线链路层的噪声）以及网络路径中的排队，使得发送速率样本只能趋近于实际可用的瓶颈带宽以下。为了过滤掉这些影响，BBR使用了一个Max过滤器：BBR以长度为BtlBwFilterLen的往返为尺度，窗口化处理得到最近的最大发送速率样本，来估算BBR.BtlBw。

BBR.BtlBw Max过滤器窗口的长度BtlBwFilterLen = 10个往返。该长度由多项因素综合权衡：

BtlBwFilterLen要足够长，能够覆盖整个ProbeBW增益循环周期（详情见“ProbeBW”部分）。这保证了该窗口至少能够容纳有着super-unit的pacing_gain（大于1.0的pacing_gain）的发送速率样本。这种super-unity的发送速率样本对于计算可用带宽是十分有用的，即便发送速率受到噪声的影响而降低，如：聚合引发的延时、流量交叉引发的排队延时、链路层损耗引发的未被修正的丢包、或者非阻塞应发的缓冲区溢出（在浅缓冲中偶然发生的短暂流量突发）。
BtlBwFilterLen要足够长，去覆盖上面提及的噪声引发的网络发送速率的短期波动。特别是无线链路层（如：WIFI和蜂窝技术）的发送速率常会有较大波动，过滤器的窗口需要足够的长去保存“好的”发送速率样本，以便在这种波动环境中拥有鲁棒性。
BtlBwFilterLen要足够短，无论是由于新数据流的开启分享了瓶颈带宽，还是瓶颈链路由于物理变化降低了服务效率，都能及时响应可用带宽的减少。在这些场景中，流经瓶颈带宽的BBR流需要及时地减少估算的BBR.BtlBw，以及传输中数据的pacing rate，让发送行为匹配新的可用带宽。

4.1.1.3 BBR.BtlBw Max过滤器的追踪时长

BBR.BtlBw Max过滤器窗口的追踪时长使用了一个以BBR.round_count计时的虚拟时钟(非墙上时钟 wall-clock)，即以一个包的往返来计数。BBR.round_count虚拟时钟相对于墙上时钟有更好的鲁棒性。墙上时钟的时间在RTT变化或重传超时引起了延时的时候也会流逝，导致过早为“超时”估计带宽。

BBR.round_count通过记录标志包的状态，等待该标志包之后被发送的任意包的ACK来为包往返计数，如以下伪代码：

连接初始化：
BBRInitRoundCounting():
    BBR.next_round_delivered = 0
    BBR.round_start = false
    BBR.round_count = 0

传输数据包：

packet.delivered = BBR.delivered

接收到数据包的ACK：

BBRUpdateRound():
    BBR.delivered += packet.size
    if (packet.delivered >= BBR.next_round_delivered)
      BBR.next_round_delivered = BBR.delivered
      BBR.round_count++
      BBR.round_start = true
    else
      BBR.round_start = false

4.1.1.4 BBR.BtlBw和应用受限发送速率样本

传输过程可能会发生应用受限，即传输速率被应用层面而非拥塞控制算法所限制。这是请求/响应式通讯中很常见的现象。当传输通道可用，但没有数据可发送时，发送速率样本就会标记相应的带宽样本为应用受限 [draft-cheng-iccrg-delivery-rate-estimation]。BBR.BtlBw估算器会很精心挑选带宽模型中的样本，以达到准确反映网络受限的状况，而非应用受限。默认地，估算器会丢弃应用限制样本，因为定义上来说他们反映的是应用层面受限。然而，在测量的发送速率比当前BBR.BtlBw还要大时，估算器也会去使用应用受限样本，因为该现象意味着当前BBR.BtlBw是被低估的。

4.1.1.5 更新BBR.BtlBw最大值过滤器

对于每个用于声明发送包被接收到的ACK，BBR会调用 BBRUpdateBtlBw( ) 来更新BBR.BtlBw估算器，如下（这里packet.delivery_rate是指从已被ACKed的包中获取到的发送速率样本 [draft-cheng-iccrg-delivery-rate-estimation]）：

BBRUpdateBtlBw()
    BBRUpdateRound()
    if (rs.delivery_rate >= BBR.BtlBw || ! rs.is_app_limited) 
        BBR.BtlBw = update_windowed_max_filter(
                      filter=BBR.BtlBwFilter,
                      value=rs.delivery_rate,
                      time=BBR.round_count,
                      window_length=BtlBwFilterLen)

4.1.2 BBR.RTprop

BBR.RTprop是估计的传输连接发送过程中的往返传播延时。该值决定了这条连接需要保持BBR.BtlBw速率的最短时间，也是能达到充分利用（“满管道”）所需的最小传输中的数据量。往返传播延时会在一个连接的生命周期中不断变化，因此BBR会根据最近的往返延时样本持续估算RTprop。

4.1.2.1 用于估算BBR.RTprop的往返时间样本

对于连接中发送的每个数据包，BBR都会计算出一个RTT样本，即从一个包的发送到该包被ack之间的时间间隔。

大多数情况下，用于重传超时RTT的估算机制 [RFC6298] 也同样作用于BBR的RTT样本。换句话来说，BBR不使用重传包的传输时间作为RTT样本，因为其是不清晰不可靠的。BBR使用累积的、经过选择的ACK（如果该传输支持 [RFC2018] SACK选项或相似原理），或传输层时间戳（如果该传输支持 [RFC7323] TCP时间戳或者相似原理）去计算RTT样本。

对于重传超时的RTT估算，唯一不同的场景是，一个ACK是对多个数据包的集合反馈。为了保守地规划长超时来避免假性重传，这种潜在的RTT样本中的最大值被专门用于计算重传超时；如，带有最早传输时间的数据包被专门用于SRTT的计算。与之相比，BBR使用潜在的RTT样本中的最小值来实现用最小的数据量填充传输管道；如，BBR使用具有最新传输时间的数据包去计算RTT。

4.1.2.2 BBR.RTprop最小值过滤器

由于各种“噪声”，如物理传输过程的随机变化（无线链路层噪声）、网络路径的排队、接收端的ack延时策略、ack堆积等等，RTT样本往往会高于往返传播延时。为了过滤掉这些噪声带来的影响，BBR使用了Min过滤器：BBR使用过去的，时长范围在RTpropFilterLen秒内的，最近的RTT样本去估算BBR.RTprop。（许多相同的网络状况也会降低发送速率，并且增加RTT，这也是为什么BBR用于计算RTT的Min过滤器与用于计算发送速率的Max过滤器是互补的。）

RTProp Min过滤器的窗口大小为RTpropFilterLen = 10秒。该值由以下几点综合推断：

RTpropFilterLen要长于ProbeRTTInterval，以便覆盖整个ProbeRTT周期（见“ProbeRTT”部分）。这确保了窗口可以容纳低于估算BDP的传输中数据的RTT样本。这些RTT样本将有助于计算路径中的双向传播延时，即便上述“噪声”会使观测模糊。
RTpropFilterLen要足够长，以避免频繁截断传输中的和输出的数据。测量双向传播延时要求传输中的数据量小于或等于BDP，否则会造成管道未被充分利用，因此BBR使用一个足够长的过滤窗口让这种未充分利用的事件概率变得足够低。
RTpropFilterLen要足够长，让应用有一个“自然的”闲置或低带宽使用率区间，以便程序自己降低传输中数据量到BDP以下，并刷新BBR.RTprop，而不是人为地降低传输数据。该方法应用于多种热门场景，包括Web、RPC、分块音频、视频流等。
RTpropFilterLen要足够短，去及时响应双向传播延时的增长。如，以30秒或更长时间为尺度的路由切换。

4.1.2.3 更新BBR.RTprop Min过滤器

每传输一个包，BBR（或相关传输协议）都会储存该包传输时的墙上时钟（Now( )返回当前的墙上时钟）：

packet.send_time = Now()

对于每个已发送包的ACK，BBR（或相关传输协议）会如下计算RTT样本：

packet.rtt = Now() - packet.send_time

BBR的实现可能使用了常规窗口化的Min过滤器去追踪BBR.RTprop。然而，使用相同状态去追踪BBR.RTprop和ProbeRTT能够明显地节省空间。因此本文使用组合方法，该方法会让每个ACK都提供一个RTT样本。BBR将如下更新BBR.RTprop估算器：

BBRUpdateRTprop()
    BBR.rtprop_expired =
      Now() > BBR.rtprop_stamp + RTpropFilterLen
    if (packet.rtt >= 0 and
       (packet.rtt <= BBR.RTprop or BBR.rtprop_expired))
      BBR.RTprop = packet.rtt
      BBR.rtprop_stamp = Now()

BBR.rtprop_expired是用于记录BBR.RTprop是否由于周期性刷新或转移到ProbeRTT阶段而引发过期的布尔变量。

4.2 BBR控制参数

BBR使用三个独特且相关联的控制参数：pacing rate、send quantum和congestion window (cwnd)。

4.2.1 Pacing Rate

为了让发送速率与瓶颈带宽的到达速率相匹配，BBR让数据包有节奏地发送。Pacing强制规定了最大发送速率。其是BBR控制发送行为的首要机制；BBR的实现必须包含Pacing的实现。
发送端通过维护发包的间距来实现Pacing。下一个包的发送时间由最近的包大小与当前pacing rate计算得出。可表示为以下形式：

next_send_time = Now() + packet.size / pacing_rate

为了适应瓶颈带宽，BBR通过一个动态增益或者说是放大系数“pacing_gain”来将pacing rate设置为BBR.BtlBw的倍数。
当一个BBR流开启时，其并未估算BBR.BtlBw。这种情况下，BBR使用了基于发送端实现的初始化拥塞窗口（“InitialCwnd”），第一个非零RTT样本之后的初始化SRTT（smoothed round-trip time），和初始化pacing_gain：

BBRInitPacingRate():
    nominal_bandwidth = InitialCwnd / (SRTT ? SRTT : 1ms)
    BBR.pacing_rate =  BBR.pacing_gain * nominal_bandwidth

在初始化之后，每收到1个ACK，只要其估算当前已填满管道（BBR.filled_pipe为真；见“Startup”部分），BBR都会以BBR.BtlBw为倍数去更新pacing rate，或者直接增加pacing rate。以这种方式限制pacing rate的更新是为了帮助连接更鲁棒地探测带宽，直到达到可用带宽的上限（“满管道”）。特别的是，这种方式能够防止因只观测到应用受限样本而导致的pacing rate下降。BBR在通过BBRSetPacingRate( )来更新pacing rate：

BBRSetPacingRateWithGain(pacing_gain):
    rate = pacing_gain * BBR.BtlBw
    if (BBR.filled_pipe || rate > BBR.pacing_rate)
      BBR.pacing_rate = rate

  BBRSetPacingRate():
    BBRSetPacingRateWithGain(BBR.pacing_gain)

4.2.2 发送量

高性能的发送端往往会聚合多个包并一次性发送来均衡发送过程中的单包传输开支（使用TSO, GSO, 或者其他卸载机制 DC13）。BBR拥塞控制算法使用了明确的、动态的控制决策来计算BBR.send_quantum，即这些传输集合的最大大小。该决策基于：较小的BBR.send_quantum适用于低数据速率场景，因为其具有较短数据包突发、较短排队、较低排队延时、以及较低丢包率的特性；较大的BBR.send_quantum在高数据速率场景适用，该场景发送及接收端可以从网络堆栈中一次性运输更大量的数据，而只需较低的CPU开支。
每一次ACK，BBR运行BBRSetSendQuantum( )来更新BBR.send_quantum：

BBRSetSendQuantum():
    if (BBR.pacing_rate < 1.2 Mbps)
      BBR.send_quantum = 1 * MSS
    else if (BBR.pacing_rate < 24 Mbps)
      BBR.send_quantum  = 2 * MSS
    else
      BBR.send_quantum  = min(BBR.pacing_rate * 1ms, 64KBytes)

考虑到发送端接收端的CPU开支，以及网络路径的缓存区等,BBR的实现可能会使用其他方式来选择BBR.send_quantum。然而，为了网络和用户的利益，BBR的实现理应使用尽可能小的发送量。

4.2.3 拥塞窗口

拥塞窗口控制了网络中任意时刻允许传输的最大数据量。BBR用网络路径模型不断调整cwnd，用状态机决定决定如何探测该路径。

默认地，BBR扩张其窗口以达到目标窗口BBR.target_cwnd大小。该目标窗口可经过比例变化来适应模型中估算的BDP。但BBR的cwnd选择是多种因素的均衡，以便动态适应多变的情况。在丢包恢复时，BBR将基于最近的发送样本来更谨慎地调整发送行为。如果BBR需要重新探测当前路径的BBR.RTprop，其便可直接裁剪cwnd。以下部分将解释各种情况对cwnd的影响。

4.2.3.1 初始cwnd

BBR将会使用测量值去构建网络模型，并且基于该模型去调整控制策略。此时，初始cwnd的挑选是处于BBR算法之外的，因为在初始阶段无测量值供BBR使用。因此，BBR使用发送端实现的初始化拥塞窗口。

4.2.3.2 目标cwnd

BBR.target_cwnd是BBR允许的传输数据量的上限。当所有其他条件都满足时，该限制将生效：数据流未处于丢包恢复，不需要探测BBR.RTprop，对模型参数有足够的累计的信心，即在接收到足够多的ACK后去不断扩张当前的cwnd，直到达到BBR.target_cwnd。

对于每个ACK，BBR计算BBR.target_cwnd的过程如下：

BBRInflight(gain):
    if (BBR.RTprop == Inf)
      return InitialCwnd /* no valid RTT samples yet */
    quanta = 3*BBR.send_quantum
    estimated_bdp = BBR.BtlBw * BBR.RTprop
    return gain * estimated_bdp + quanta

  BBRUpdateTargetCwnd():
    BBR.target_cwnd = BBRInflight(BBR.cwnd_gain)

“estimated_bdp”项允许数据流以BBR.BtlBw的速率维持BBR.RTprop的时长，让足够多的数据包去充分使用估算的BDP。使用cwnd_gain放大BDP，并用状态机筛选使其始终大于1.0，限制传输中的数据量为小尺度放大的BDP，以便应对网络和接收端常见的状况，例如延迟的，间隔拉长的，或聚合化的ACK [A15]。"quanta"项允许发送端和接收端传输足量的数据以便达到网络的充分使用，即便是在使用卸载机制的高吞吐环境下。

4.2.3.3 流水线的最小cwnd

正常情况下（除了进入丢包恢复之后的瞬间），BBR为BBRMinPipeCwnd设置了最小值（4个包，如4*MSSS）。这个底线保证了即便在很低的BDP下（如TCP的接收端可能只会选择性的每经过MSS的数据发送一次ACK），也能有足够多的传输中的包来维持整个流水线继续运行。特别的是，BBR尝试让至少有两个包处于传输中的状态，并且至少有两个ACK包处于接收端到发送端的传输路径中。

4.2.3.4 丢包恢复时调制cwnd

BBR认为丢包是模型未能反馈出的最近网络状态发生过变化的警示，因此要谨慎对待。

重传超时时，即发送端认为传输过程中的包都丢失了，BBR谨慎地减小cwnd到一个包大小(1 MSS)，并且只发送一个包。然后使用"核心cwnd调整机制"中提到的常规方法来逐渐增大cwnd。

当BBR发送端检测到丢包但仍有包处于传输状态时，在丢包恢复的第一轮，BBR临时减小cwnd来让发送速率匹配此时ACK的到达速率。在第二轮以及随后的过程中，BBR将保证发送速率不超过两倍的ACK到达速率。

当BBR退出丢包恢复模式后，cwnd将被重置为进入丢包恢复之前的最后一次已知的最优值。该操作在恢复完丢包数据或因丢包事件是假的而取消恢复时都被应用。

有多种方法可实现丢包恢复阶段cwnd的更新。其中一个如下：

重传超时时：

BBR.prior_cwnd = BBRSaveCwnd()
  cwnd = 1

进入快恢复时，设置cwnd为处于传输中的包的数量（对于快重传允许至少有一个包）：

BBR.prior_cwnd = BBRSaveCwnd()
  cwnd = packets_in_flight + max(packets_delivered, 1)
  BBR.packet_conservation = true

在快恢复阶段每收到一个ACK，运行以下BBRModulateCwndForRecovery( )步骤，来确保恢复的第一轮的包守恒，并且在之后的轮次中发送速率不超过两倍的当前发送速率（已知"packets_delivered"的包是最新标志的ACKed或者SACKed，"packets_lost"的包是最新标志的丢失）：

BBRModulateCwndForRecovery():
    if (packets_lost > 0)
      cwnd = max(cwnd - packets_lost, 1)
    if (BBR.packet_conservation)
      cwnd = max(cwnd, packets_in_flight + packets_delivered)

经过一个往返的快速恢复：

BBR.packet_conservation = false

当离开丢包恢复（重传超时恢复或快速恢复），无论是修复完成还是取消恢复，BBR都会将cwnd恢复到进入丢包恢复之前已知的最优值：

BBR.packet_conservation = false
  BBRRestoreCwnd()

BBRSaveCwnd( )和BBRRestoreCwnd( )帮助储存和恢复最后一个最优cwnd（最新的一个未被丢包恢复或ProbeRTT增幅的cwnd），定义如下：

BBRSaveCwnd():
    if (not InLossRecovery() and BBR.state != ProbeRTT)
      return cwnd
    else
      return max(BBR.prior_cwnd, cwnd)

  BBRRestoreCwnd():
    cwnd = max(cwnd, BBR.prior_cwnd)

4.2.3.5 ProbeRTT时调制cwnd

如果BBR决定要进入ProbeRTT状态（见“ProbeRTT”部分），则其需要快速减少传输中的数据量，并且排放瓶颈中的队列，从而能够测量BBR.RTprop。为了实现该模式，BBR将cwnd限制为BBRMinPipeCwnd，即流水线中允许的最小值（见"流水线的最小cwnd"）：

BBRModulateCwndForProbeRTT():
    if (BBR.state == ProbeRTT)
      cwnd = min(cwnd, BBRMinPipeCwnd)

4.2.3.6 核心cwnd调整机制

流量在网络传输时可能会发生戏剧性的突发变化。为了平稳鲁棒地适应这些变化，减少这种情况下的丢包，BBR使用了谨慎的策略。当cwnd超过模型计算的BBR.target_cwnd时，BBR立即减小cwnd到目标值。当cwnd在BBR.target_cwnd以下时，BBR逐渐谨慎地提升cwnd，并且不超过ACK到达的速率。

具体来说，每收到一个ACK，BBR都会执行BBRSetCwnd( )去更新cwnd，如下：

BBRSetCwnd():
    BBRUpdateTargetCwnd()
    BBRModulateCwndForRecovery()
    if (not BBR.packet_conservation) {
      if (BBR.filled_pipe)
        cwnd = min(cwnd + packets_delivered, BBR.target_cwnd)
      else if (cwnd < BBR.target_cwnd || BBR.delivered < InitialCwnd)
        cwnd = cwnd + packets_delivered
      cwnd = max(cwnd, BBRMinPipeCwnd)
    }
    BBRModulateCwndForProbeRTT()

这里有几个注意事项，如果BBR已经测量到足够多的样本确保其已经填充满管道（见“Startup”部分解释的BBR.filled_pipe），则根据已发的包的数量增大cwnd，同时限制cwnd不超过BBR.target_cwnd。相反，如果cwnd在目标值以下，或者发送端标记了太少的发送数据（小于InitialCwnd）以至于无法估算BBR.BtlBw和BBR.target_cwnd是有效的，则可以无限制地增大cwnd。最后，BBR使用BBRMinPipeCwnd为底线以便整个流水线能在小BDP的情况下正常运作（见"流水线的最小cwnd"）。

4.3 状态机

BBR实现了一个用网络模型来进行决策的，使用控制参数来表示决策的，简单的状态机。在启动时，BBR探测参数去构建网络模型；为了适应随后的网络变化，BBR必须持续探测参数来更新模型。同样的，如果实际往返传播延时变化，这也同时改变了BDP，BBR必须减缓发送速率，让传输中的数据量小于新的BDP，以便能够测量新的BBR.RTprop。因此，BBR的状态机需要周期性地、顺序化地进行实验，更快地发送去检测BBR.BtlBw的增长，或更慢地发送去检测BBR.RTprop的减小。实验中的频率、大小、持续时长、结构的不同取决于什么是已知的（启动或者稳态），以及应用的发送行为(间歇性或持续性)。

该状态机有几个目标：

有效使用可用带宽来达到高吞吐量。
保持队列是有界的并且足够小来实现低延时。
周期性成倍地加速发送来快速探测新的带宽上限。
必要时，减缓发送速率，排放瓶颈队列，来估计网络的双向传播延时。
将样本输入BBR.BtlBw和BBR.RTprop的估算器中，更新网络模型。

BBR的状态机使用两个控制机制。第一个也是最重要的一个，根据BBR.BtlBw使用pacing_gain（见“Pacing Rate”部分）来控制包的发送速率，其是BBR的关键能力。pacing_gain > 1，减小包间时间间隔，增大传输中的数据量。pacing_gain < 1 拥有相反效果，增大包间时间间隔，减小传输中的数据量。第二，BBR使用cwnd来快速减少传输中的数据量到指定的值。

下面几节将解释状态机的几个状态。

4.3.1 初始化步骤

连接初始化时，BBR执行如下步骤：

BBRInit():
    init_windowed_max_filter(filter=BBR.BtlBwFilter, value=0, time=0)
    BBR.rtprop = SRTT ? SRTT : Inf
    BBR.rtprop_stamp = Now()
    BBR.probe_rtt_done_stamp = 0
    BBR.probe_rtt_round_done = false
    BBR.packet_conservation = false
    BBR.prior_cwnd = 0
    BBR.idle_restart = false
    BBRInitRoundCounting()
    BBRInitFullPipe()
    BBRInitPacingRate()
    BBREnterStartup()

4.3.2 Startup

4.3.2.1. Startup动态

当BBR流启动时，其将执行第一次(最快速的)连续性探测/排放过程。网络带宽范围在几bps到100Gbps之间，跨越了至少11个数量级。为了在如此大的范围内快速获取BBR.BtlBw，BBR在Startup状态中将发送速率指数级增加，每轮都会加倍发送速率。在O(log_2(BDP))个往返内便可获取到BBR.BtlBw。

为了以平滑的方式实现快速探测，在进入Startup状态时，BBR设置BBR.pacing_gain和BBR.cwnd_gain为BBRHighGain = 2/ln(2) ~= 2.89，即允许发送速率每轮翻倍的最小增益值。当初始化一个连接时，或在之后任意时刻进入Startup模式时，BBR都会执行BBREnterStartup( )：

BBREnterStartup():
    BBR.state = Startup
    BBR.pacing_gain = BBRHighGain
    BBR.cwnd_gain = BBRHighGain

当BBR快速增加发送速率时，其获取到了更高的发送速率样本，BBR.BtlBw增大，pacing rate和cwnd都需要成比例地平滑增加。管道一旦装满，队列已经形成，cwnd_gain限制队列为(cwnd_gain - 1) * BDP，随之便立即进入Drain状态，来快速排放队列。

4.3.2.2 当Startup阶段填满管道时的估算

在Startup阶段，BBR通过观测估算的BBR.BtlBw是否进入稳态来判定管道是否被填满。这个“满管道”估算器的输出是BBR.filled_pipe（一个记录BBR是否曾充分使用过可用带宽的布尔变量）。如果BBR发现在几（三）轮投递率倍增的尝试中，只得到了很少量的增加(少于25%)，则认为已经达到了BBR.BtlBw，设置BBR.filled_pipe为true，退出Startup，进入Drain。

连接初始化时，满管道估算器运行如下：

BBRInitFullPipe():
    BBR.filled_pipe = false
    BBR.full_bw = 0
    BBR.full_bw_count = 0

每个往返收到新的ACK时，如果发送速率样本未处于应用受限，BBR会在必要时运行“满管道”估算器：

BBRCheckFullPipe():
    if BBR.filled_pipe or
       not BBR.round_start or rs.is_app_limited
      return  // no need to check for a full pipe now
    if (BBR.BtlBw >= BBR.full_bw * 1.25)  // BBR.BtlBw still growing?
      BBR.full_bw = BBR.BtlBw    // record new baseline level
      BBR.full_bw_count = 0
      return
    BBR.full_bw_count++ // another round w/o much growth
    if (BBR.full_bw_count >= 3)
      BBR.filled_pipe = true

BBR会等待三轮以获取实质性的证据，来证明发送端达到的稳态不是由于接收窗口临时造成的。有三轮的时间去让接收端的接收窗口调节增加，使BBR的发送端能够探测到BBR.BtlBw可以更大：第一轮，接收窗口自动调谐算法扩张接收窗口；第二轮，发送端填充更大的接收窗口；第三轮，发送端获取到更高的发送速率样本。三轮限制已在YouTube的实验性数据中被验证。

4.3.3 Drain

在Startup阶段，当“满管道”估算器估算出管道已被填满时，BBR将切换到Drain状态。在Drain阶段，BBR会降低pacing_gain到1.0以下，来快速排出Startup阶段产生的队列。特别的是，BBR使用Startup阶段的pacing_gain的倒数为新的pacing_gain，进行持续一轮的排放：

BBREnterDrain():
    BBR.state = Drain
    BBR.pacing_gain = 1/BBRHighGain  // pace slowly
    BBR.cwnd_gain = bbr_high_gain    // maintain cwnd

在Drain阶段，当传输中的数据量与估计的BDP相匹配时，也就是BBR估计该队列已经被完全排空但管道仍然是满的，则BBR会退出Drain状态，进入ProbeBW阶段。对于每个ACK，BBR执行以下操作：

BBRCheckDrain():
    if (BBR.state == Startup and BBR.filled_pipe)
      BBREnterDrain()
    if (BBR.state == Drain and packets_in_flight <= BBRInflight(1.0))
      BBREnterProbeBW()  // we estimate queue is drained

4.3.4 ProbeBW

4.3.4.1 增益循环

在BBR的生命周期中，ProbeBW阶段占据了绝大部分时间。ProbeBW使用循环增益的方式来探测带宽，这种方式能够帮助BBR实现高吞吐、低队列延时、公平的带宽分享。增益循环使得BBR有了一个序列化的pacing_gain：5/4，3/4，1，1，1，1，1，1。每个阶段通常会会持续约为BBR.RTprop的时长。

在增益循环的第0个阶段，BBR使用5/4作为pacing_gain来探测更高带宽，该操作可逐渐增加传输中的数据量。该阶段会持续至少一个BBR.RTprop的时长，或直到传输中的数据量达到5/4 * estimated_BDP（当BBR.RTprop较低时，可能耗费的时间大于BBR.RTprop），或发生了丢包（可能该网络并不能容纳5/4 * estimated_BDP的数据量）。

第1阶段使用3/4作为pacing_gain来排放瓶颈中的队列，挑选该值的理由是1-3/4等于5/4-1。该阶段会持续BBR.RTprop的时长，或直到传输中的数据量下降到estimated_BDP以下（队列可能因应用受限而被提前排空）。

最后，第2到7阶段使用值为1.0的paicng_gain来达到短队列、全利用的巡航模式。每个阶段持续BBR.RTprop的时长。

所有阶段的增益平均值为1.0，因为ProbeBW的目的是使平均pacing rate等于估算的可用带宽BBR.BtlBw。因此需要维持高利用率的、小的、被限制的很好的队列。

值得注意的是，在ProbeBW阶段，当增益循环改变pacing_gain的值时，cwnd_gain将维持在常数2，因为延迟的、拉长间隔的、聚合化的ACK会在此时出现（见“目标cwnd”部分）。

4.3.4.2 增益循环随机化

在有多个BBR流同处于一个瓶颈带宽中时，为了混合多路流、增强公平性，BBR在进入ProbeBW阶段时，会随机化挑选一个阶段作为初始阶段（除了3/4这个阶段）。

为什么不从3/4开始？值为3/4的pacing_gain主要用于排放在5/4阶段满管道时产生的队列。在退出Drain或ProbeRTT并进入ProbeBW阶段时，实际上并没有队列需要排放，所以3/4的增益并不能发挥出应有的作用。如果一定要使用3/4，则需要相应的代价：在该轮次中带宽的利用率变成3/4而不是1。使用3/4作为起始值不会带来好处，反而带来坏处。对于任意链接来说，从ProbeBW阶段到进入Drain阶段之间会有很长的时间，因此，BBR使用了优化后的方法（不使用3/4）。

4.3.4.3 增益循环算法

ProbeBW阶段，增益循环算法如下：

BBREnterProbeBW():
    BBR.state = ProbeBW
    BBR.pacing_gain = 1
    BBR.cwnd_gain = 2
    BBR.cycle_index = BBRGainCycleLen - 1 - random_int_in_range(0..6)
    BBRAdvanceCyclePhase()

每次收到ACK，BBR将执行BBRCheckCyclePhase( )，来检测是否应该进入下一阶段：

BBRCheckCyclePhase():
    if (BBR.sate == ProbeBW and BBRIsNextCyclePhase())
      BBRAdvanceCyclePhase() 

  BBRAdvanceCyclePhase():
    BBR.cycle_stamp = Now()
    BBR.cycle_index = (BBR.cycle_index + 1) % BBRGainCycleLen
    pacing_gain_cycle = [5/4, 3/4, 1, 1, 1, 1, 1, 1]
    BBR.pacing_gain = pacing_gain_cycle[BBR.cycle_index]

  BBRIsNextCyclePhase():
    is_full_length = (Now() - BBR.cycle_stamp) > BBR.RTprop
    if (BBR.pacing_gain == 1)
      return is_full_length
    if (BBR.pacing_gain > 1)
      return is_full_length and
                (packets_lost > 0 or
                 prior_inflight >= BBRInflight(BBR.pacing_gain))
    else  //  (BBR.pacing_gain < 1)
      return is_full_length or
                 prior_inflight <= BBRInflight(1)

这里“prior_inflight”是指接收到ACK前处于传输中的数据量。

4.3.4.4 从空闲状态重新启动

从空闲状态重新启动时，为了尽快回到速率平衡及满管道的状态，BBR将维持cwnd为当前值，并且以BBR.BtlBw的速率发送数据。尤其是处于ProbeBW状态并且应用受限时，当前无数据包处于传输过程中，BBR将会设置BBR.pacing_rate为BBR.BtlBw来发送一个或多个包。BBR算法在发送数据前将执行以下步骤：

BBRHandleRestartFromIdle():
    if (packets_in_flight == 0 and C.app_limited)
      BBR.idle_start = true
      if (BBR.state == ProbeBW)
        BBRSetPacingRateWithGain(1)

[RFC5681]的“Restarting Idle Connections”小节中建议，要从初始窗口进行慢启动来重启。该方法是假设拥塞控制算法未对瓶颈带宽进行估计，并且没有Pacing功能，所以只能依赖以ACK作为时钟驱动的慢启动方法。“slow start after idle”的方法使得达到满带宽有着很长的延时(log_2(BDP)*RTT)，大量部署关闭了该机制，并且使用“BDP-scale line-rate burst”方法来进行替换。这两种方式BBR都不使用，而是采用了以BBR.BtlBw为速率的重启，最终达到了显著效果。在达到速率平衡和满管道时，只过去了一个BBR.RTprop的时长。

4.3.5 ProbeRTT

为了探测BBR.RTprop，BBR会周期性地进入ProbeRTT状态，排放瓶颈队列。当处于非ProbeRTT状态时，如果RTProp在ProbeRTTInterval = 10秒的时间内未被更新，BBR便会进入ProbeRTT阶段，并且减小cwnd到BBRMinPipeCwnd（4个包）。在维持BBRMinPipeCwnd或少量传输中的包至少ProbeRTTDuration(200ms)和一个往返后，BBR将退出ProbeRTT阶段，转移到Startup或ProbeBW阶段，这取决于管道是否以及被填满。

权衡之下，BBR设计了其生命周期中大部分时间（约98%）会处于ProbeBW状态，其他时间处于ProbeRTT状态。ProbeRTT要持续足够长的时间（至少ProbeRTTDuration = 200ms）让拥有不同RTT的数据流在ProbRTT阶段产生重叠；也要持续足够短的时间，让因限制ProbeRTT的cwnd吞吐量而产生的代价约束在2%（200ms/10s）。

正如“BBR.RTprop Min过滤器”中提到的，BBR的BBR.RTprop过滤窗口RTpropFilterLen与两个ProbeRTT状态间的时间间隔ProbeRTTInterval，是相配合工作的。BBR的实现必须令RTpropFilterLen大于或等于ProbeRTTInterval。为了与其他的BBR流协调工作，RTpropFilterLen必须是标准ProbeRTTInterval长度，即10s。这里推荐RTpropFilterLen和ProbeRTTInterval都使用10s。10s的RTpropFilterLen对于流量平稳或路由改变时的快速收敛是足够短的，对于应用交互(网页、RPC、视频块)来说是足够长的，该场景下常有数据空窗期或低速率期，此时流量足够小或时间足够长来排放瓶颈中的队列。然后BBR.RTprop过滤器适时地挑选测量到的BBR.RTprop，且RTProp的刷新无需进入ProbeRTT。这种方式下，如果有多路数据流在整个ProbeRTTInterval窗口中频繁发送数据，数据流只需承担2%吞吐量的代价。

每收到1个ACK，BBR会执行BBRCheckProbeRTT( )来实现ProbeRTT中的操作：

BBRCheckProbeRTT():
    if (BBR.state != ProbeRTT and
        BBR.rtprop_expired and
        not BBR.idle_restart)
      BBREnterProbeRTT()
      BBRSaveCwnd()
      BBR.probe_rtt_done_stamp = 0
    if (BBR.state == ProbeRTT)
      BBRHandleProbeRTT()
    BBR.idle_restart = false

  BBREnterProbeRTT():
    BBR.state = ProbeRTT
    BBR.pacing_gain = 1
    BBR.cwnd_gain = 1

  BBRHandleProbeRTT():
    /* Ignore low rate samples during ProbeRTT: */
    C.app_limited =
      (BW.delivered + packets_in_flight) ? : 1
    if (BBR.probe_rtt_done_stamp == 0 and
        packets_in_flight <= BBRMinPipeCwnd)
      BBR.probe_rtt_done_stamp =
        Now() + ProbeRTTDuration
      BBR.probe_rtt_round_done = false
      BBR.next_round_delivered = BBR.delivered
    else if (BBR.probe_rtt_done_stamp != 0)
      if (BBR.round_start)
        BBR.probe_rtt_round_done = true
      if (BBR.probe_rtt_round_done and
          Now() > BBR.probe_rtt_done_stamp)
        BBR.rtprop_stamp = Now()
        BBRRestoreCwnd()
        BBRExitProbeRTT()

  BBRExitProbeRTT():
    if (BBR.filled_pipe)
      BBREnterProbeBW()
    else
      BBREnterStartup()

当从空闲阶段重启时（BBR.idle_restart为true），发现BBR.RTprop已经过期了，BBR便不再进入ProbeRTT；该空闲期被认为是协调排放队列的充分地尝试。

临界点是，在BBR提升BBR.RTprop之前（会交替升高cwnd），其必须进入ProbeRTT状态来合作协调排放瓶颈中的队列，并且测量BBR.RTprop。这使得多路BBR流在实际场景中能够很好地锚定BBR.RTprop的估计值，避免反馈循环使得队列和RTT样本不断增大。

By:xSky | 网络与安全 |