常见 TCP 拥塞避免算法浏览（下）

本文主要是介绍常见 TCP 拥塞避免算法浏览（下），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

作者：LeanCloud 后端高级工程师

视频版本链接请点击这里

BBR

估计 BtlBw 和 RTprop

延续前面说的，要把发送速率调整到跟 BDP 差不多大是最优的。因为网络环境会持续变化，所以需要持续监控 RTprop 和 BtlBw 的值。

RTprop 是链路固有传输延迟，我们无法直接监控到它，我们只能通过监控数据包的 RTT 来间接的得到 RTprop 的趋近值。RTT 和 RTprop 关系如下：

η 是其它因素导致的 noise 延迟，包括接收端延迟 ack 等原因导致的延迟。因为 RTprop 是链路上的固有延迟，可以认为只有链路上选择的路径变化时候它才会变化，并认为它变化频率很低，变化间隔时间远大于 η。η 一定是正数，RTT 无论如何不可能低于 RTprop，所以可以在一个时间窗口 Wr 内（一般是在几十秒到几分钟之间）监控最小的 RTT 的最小值，认为就是近似为 RTprop。

BtlBw 也是靠 Ack 来监控。每收到一个 Ack 一方面是知道数据延迟 RTT 是多少，再有送达的数据量是多少。我们在一个短的时间窗口 deltaT 内通过 Ack 计算对面收到了多少数据，得到 deliveryRate = deltaT 时间内送达数据量 / deltaT，这个速率一定低于链路上瓶颈速率，bottleneck rate。因为我们计算 deliveryRate 时使用的数据送达量是精确值，是在 Ack 里数据接收方明确告诉我们的。而我们为了做带宽计算等待的 deltaT 时间一定大于实际时间，所以 deltaT 时间内送达数据量 / deltaT 计算得到的 deliveryRate 一定小于等于真实 deliveryRate，这个真实 deliveryRate 又一定小于等于链路物理 bottleneck rate。所以：

这里时间窗口 Wb 一般是 10 个 RTT。

RTprop 和 BtlBw 是两个独立的量，RTprop 变化比如选择的链路变化时，bottleneck 可能是一样的 BltBw 不变；BtlBw 变化时候选择的链路可能没有变化，比如一个无线网络改变了发送速率，链路不变但带宽变大了。

从之前看过的下面这个图能知道，RTprop 只能在 BDP 线左侧被观测到，即发送数据比较少，inflight 数据量没有到 BDP 的时候；BtlBw 只能在 BDP 线右侧能被观察到，即 inflight 数据超过 BDP，延迟开始增大时被观测到。直观一点说就是链路上队列没排队时候，你知道链路延迟是多少，但不知道队列最大消费速度是多少，当队列开始出现排队后，你在发送端计算得到接收率不变了，RTT 延迟也升高了，知道最大接收率是多少，但又不知道链路上实际延迟是多大了，因为多了数据排队的时间。

估计带宽时候还一个需要处理的，跟 RTT 不同，RTT 是只要有应用层数据发就能测得，就能更新估计值，但 BtlBw 的话必须应用层有足够数据发才能估计。所以下图可以看到有个 App Limited。BBR 会将因为 app 没足够数据发而导致测得的 BtlBw 过小的情况丢弃，只记录有足够数据发的情况下得到的 BtlBw。实际上链路中实际 BtlBw 是个 hard limit，就是无论我们怎么测都不可能超过链路上实际 BtlBw，所以只要在窗口内测得小的 BtlBw 都可以丢掉，就用测试周期内最大的 BtlBw。

来自[4]

BBR 的状态机

BBR 在控制拥塞时候会在一组状态之间进行切换，如下图：

来自[2]

先简单介绍一下下面再针对每个状态更细一些说。初始状态就是 Startup，BBR 因为不知道当前带宽到底是多少，也会有类似 Slow Start 的过程，逐步增加发送速度探测 BtlBw。等到探测到 BtlBw 后因为 Startup 阶段发了很多数据出去，inflights 很大，可能链路会有排队，所以进入 Drain 阶段去做清理，让链路上的队列清空；之后进入稳定期，会周期性的在 ProbeBW 和 ProbeRTT 两个状态之间进行切换，间歇的探测 BtlBw 和 RTprop。

BBR 稳定期工作机制

先记录稳定期再写 Startup 等。BBR 每收到一个 ACK ，就会估计 RTprop 和 BtlBW (deliveryRate)，尽力保证 inflight 数据量跟估计得到的 BDP 差不多。BBR 下 inflights 数据量由内部的 target_cwnd 控制，而 target_cwnd 是个比 BDP 稍微大一点点的量。

假设链路上 RTprop 和 deliveryRate 一直保持不变，BBR 处在稳定状态一直发送数据，它保证 inflights 的数据量不会超估计的 BDP 很多。此时链路上 Bottleneck 在发送端，由发送端控制发送速度。如果链路上带宽提高了，因为 Bottleneck 在发送端，发送端会感知不到带宽变化。所以 BBR 需要周期性的提高发送速率将 Bottleneck 从发送端移到链路上去探测链路上的带宽，这就是 ProbeBW 状态的来源。名字也可以看出它含义是探测带宽，探测的是链路上 Bottleneck 的带宽。

ProbeBW 状态下先开始增周期，即提高发送率到稳定期的 1.25 倍，直到出现丢包或 inflights 数据量达到 1.25 倍 BDP 为止。观察延迟是否升高，如果延迟升高且 deliveryRate 不变，说明链路上带宽没有变化且产生了队列堆积；接下来会进入减周期，降低发送率到稳定期的 0.75 倍，等待一个 RTprop 或 inflights 数据量低于 BDP 为止，用以让链路上在增周期出现堆积的队列清空。之后再保持 inflights 等于 BDP 稳定数个 RTprop 后再次开始增周期。

之前提到 BBR 每次收到 ACK 会尝试更新 RTprop，而 RTprop 取的是窗口期内最低的 RTprop。如果 BBR 运行了很长时间一直没有更新 RTprop，即很长一段时间都没有比当前使用的 RTprop 更低的 RTprop 时，BBR 会进入 ProbeRTT 状态，用于探测 RTprop。比如链路上带宽出现减少，链路上出现堆积，保持发送速度或继续进行 ProbeBW 的话会让链路上堆积更加严重，RTT 上升。所以 RTprop 一直不会被更新。

ProbeRTT 下 BBR 将 CWND 降到很低的值，典型的是 4 个 MSS，持续一段至少 200ms 或一个 RTprop。这么一来 Inflights 数据量会突降。再判断链路是否处在 full_pipe 状态，是的话则进入 ProbeBW，不是则进入 Startup。

full_pipe 判断主要是靠最近的增周期中，发送率提高后 deliveryRate 是否有大幅度增加，有相应幅度的增加说明链路可能还没有满载，我们加快发送速率还是能发的出去，没增加则表示链路是满载的，发送速度加快但是接收速率没跟上。有个 Linux 内的 BBR 实现，可以看：tcp_bbr.c source code linux/net/ipv4/tcp_bbr.c - Woboq Code Browser

之前提到了 RTprop 和 BtlBw 两个量是测准一个另一个就测不准，稳定期测量这两个值的任务大多数时候都由 ProbeBW 独自完成，在增周期提高发送带宽发多数据到链路探测 BtlBW，在减周期减小发送带宽减少发送速率从而减小 Inflights，看估计的 RTprop 是否降低，降低了则说明测到了最新的 RTprop。如果很长时间都没有更低的 RTprop 出现，可能链路发生了切换，这时候才需要切换到 ProbeRTT 去探测最新的 RTprop。从 ProbeRTT 的机制能看到它对性能是有影响的，所以 BBR 是尽力减少 ProbeRTT 时间占比，大部分时间都在 ProbeBW 状态。

整体过程如下图，在一个 10Mbps 带宽，延迟 40ms 的网络下取了 700ms 时长的数据。图中纵轴有 RTT，inflight，和 Bandwidth (BW)。带宽部分有两个值，红色的是发送方计算出来的 Delivery Rate，紧挨着红色线的黑线是当前估计出来的 BtlBw。可以看到 Delivery Rate 波动但估计出来的 BtlBw 变动不大，因为是每次有估计出 Delivery Rate 后将这个值放入估计 BtlBw 的滑动统计窗口内，取滑动窗口内的最大值为 BtlBw，也即那个黑色线，所以红色线变动后，黑色线不会立即变动。黑色线上面的灰色框是 cycle gain 用于控制发送速度，cycle gain * 估计的 BtlBw 就是发送方当前需要的发送速度。每个周期通过控制 cycle gain 来定期的提高发送速度，以探测当前链路上 BtlBw 是否提高。

对于黑色的圈我们从起点开始说，起点是红线，即 Delivery Rate 计算出来后，放入 max BtlBw 滑动窗口估算 BtlBw 是多少。之后 1.25 这个 cycle_gain 时用之前估算的 BtlBw 乘以 1.25 作为发送速度发消息，增周期发消息多了以后链路 Inflights 增大，RTT 增大，发出的消息看到是在 1.00 这个 cycle_gain 才被 Ack，计入 Delivery Rate，并让 max BtlBw 稍微增加了一点点，看到红线峰值比红线上面的细黑线高了一点，于是将细黑线也向上推了一点点。

图中 RTT，Inflights，cycle_gain，Delivery Rate 大致都是对齐的，可以看到增周期时候 Delivery Rate ，Inflights 和 RTT 增加，减周期是减少。

来自[4]

下图是带宽从 10Mbps，40ms 延迟提到到 20Mbps 又降回 10Mbps 的过程。带宽提高后看到在 ProbeBW 的增周期， BBR 发现提高发送速度后 RTT 没有变化，且计算出来的 deliveryRate 有升高，更新 BtlBw 到新值，稳定期发送速度比原来高了 25%。在接下来三个周期内，每一次发送速率提高 25% 后延迟都没有变化，且 deliveryRate 得到提高，最终在第四个探测周期重新出现蓝色小三角，即链路上队列有排队后说明链路进入 full_pipe 状态开始稳定发送速率。

下半部分是带宽从 20Mbps 降低到 10Mbps，BBR 内因为维护了 BtlBW max filter 即从一个窗口期内采样得到的 BtlBw 值中取最大值作为当前链路的 BtlBw。所以即使带宽出现突降，因为 20Mbps 的 BtlBw 还在 max filter 内缓存着，这段时间 BBR 依然认为 BtlBw 是 20Mbps，会按照原来的发送速度继续发数据。于是带宽突降后延迟和 inflight 数据量大幅度增加。 但 inflights 数据量最大不能超过 BBR 内的 target_cwnd，其值等于 cwnd_gain * 估计的 BDP，BBR 会始终控制发送速率保持 inflights 在 target_cwnd 内，cwnd_gain 比 1 大，但不会大很多，所以带宽突然变小后 inflights 不会无限增加，并且会维持一个固定值，在图中表现为 40s ~ 42s 之间的一条水平线。这个期间即使处在 ProbeBW 阶段也无法执行增周期按 1.25 倍速率发数据，因为 target_cwnd 是满的，必须遵从它的限制，它限制了发送端不能让 inflights 数据量比它大。Inflights 和 RTT 能是一条水平线说明链路上 Buffer 比较大，能承载 target_cwnd 下的数据量且不出现丢包。

补充一下 BBR 里有两个听起来很像的东西，pacing_gain 和 cwnd_gain。pacing_gain 用来在 ProbeBW 内周期性的控制发送速率，发送速率等于估计的 BtlBw * pacing_gain。而 cwnd_gain 用于控制 target_cwnd，限制 inflights 数据量。

在 42s 开始，之前 20Mbps 的 BtlBw 估计值过期了，从 BtlBw max filter 的采样窗口中滑出，根据过去一段时间 Ack 计算出来的到达重新估算 BtlBw，根据这个重新估算的 BtlBw 调整发送速度，所以发送速率大幅度下滑。因为当前的 Inflights 数量远大于当前的 target_cwnd 也即cwnd_gain * 新估计的 BtlBw，所以发送方会完全不发数据等待 Inflights 下降，在图上表现出 Inflights 突然掉下来。当 Inflights 小于当前 target_cwnd 后，ProbeBW 的周期特性又开始显现，一个一个的小三角开始出来了。最终发送速率重新回到稳态。

看到这里时候我开始一直有个疑问，在 42s 到 44s 期间，队列内一直有堆积，一个周期发送速度是 1.25，一个周期发送速度是 0.75，岂不是刚好把发多少数据消费掉，但队列内堆积的 inflights 不是依然保持没有被消费掉吗？不该是下降趋势。

后来知道，ProbeBW 期间一个周期大致上是一个 RTT 时间，但发送速度 1.25 的周期和发送速度 0.75 的周期并不是严格等长的。1.25 周期时长是 inflights 数量到达 1.25 倍估计的 BDP 或有数据丢包。0.75 周期长度是一个完整的估计的 RTprop，或者 inflights 低于估计的 BDP。发送者能感知到 inflights 低于 BDP 的时候实际 inflights 一定低很多了，所以 BBR 的 inflights 曲线都是像心跳一样，上面一个三角下面一个三角，而不是只有上面的三角。在 19 ~ 20s 的时候，上三角比下三角大。20 ~ 21s 因为带宽变大了，但发送带宽只是缓慢增加上去，所以下三角比上三角大很多，等到稳态以后又变成上三角大于下三角。42s 以后因为每个减周期都要等到 Inflights 低于估计的 BDP，所以绿线一路向下。

对于蓝色的线我们知道链路上延迟是固有时间，所以它最低点是一条直线，增周期时延迟只会有上三角，没下三角。

注意下图没有 ProbeRTT 出现。我理解是因为 RTprop 还未超时就被更小的值更新了。

来自[4]

BBR 的 startup

链路上带宽跨度很大，从几个 bps 到上百 Gbps，所以 BBR 一开始也会以指数形式增大 BtlBw，每一个 RTT 下发送速度都增大 2/ln(2) 约 2.89 倍，从而在 O(log(BDP)) 个 RTT 内找到链路的 BtlBw，log 的底是 2。BBR 在发现提高发送速度但 deliveryRate 提高很小的时候标记 full_pipe，开始进入 Drain 阶段，将排队的数据包都消费完。BBR 能保证排队的数据最多为实际 BDP 的 1.89 倍。BBR 下并没有 ssthresh，即 CUBIC 那样增加到某个配置值后开始进入线性增加 CWND 阶段。

Drain 阶段就是把发送速率调整为 Startup 阶段的倒数。比如 Startup 阶段发送速度是 2.89，那 Drain 阶段发送速度是 1/ 2.89。BBR 会计算 inflights 数据包量，当与估计的 BDP 差不多的时候，BBR 进入 ProbeBW 状态，后续就在 ProbeBW 和 ProbeRTT 之间切换。

下图是在 10Mbps，40ms 延迟网络下的 Startup 阶段的图，绿色是发送方发送数据量，蓝色是接收方收到的数据量。红色是 CUBIC 在同样环境的发送数据量，作为对比。下图绿色线的斜率就是发送速度，同一时间点绿色线上的点和蓝色线上的点的差值就是那个时刻 inflights 数据量。

看到 BBR 在 0.25s 之前是曲线，10Mbps 40ms 延迟的网络下 BBR 允许的 BDP 为 0.04Mb，0.25 时间点上绿色和蓝色线差值大约 0.1Mb，大致是 0.04Mb 的 2.89 倍。即 BBR 在一开始指数的快速提升发送速度，但快到了 0.25s 的时候，RTT 开始升高，inflights 提高后 deliveryRate 并没有相应提高，BBR 开始维持在一个速度等待几个 RTT 周期以确认链路确实承载不了当前的发送速度，所以 0.25s ~ drain 之前绿线斜率不变。到 Drain 后 RTT 迅速下降，Acked 数据量图的斜率也降低很多。在找到 RTprop 之后进入 ProbeBW 状态。

红线的话就是看到 CUBIC 更早的切换到线性增长，但之后会逐步增加发送包数量直到丢包。但下图上半部分看红线看不太出来发送率在增加，只是能隐约的感觉到 0.25 时间点时红线和蓝线的间隔似乎小于 0.75 时间点时他俩的间隔。

来自[4]

下面是 BBR 和 Cubic 在延迟时间上的对比。BBR 开始延迟大但随即恢复。CUBIC 一直增长下去直到丢包，再减小再增长。

来自[4]

当多个 BBR 流在同一个链路时如下图。基本上就是靠 BtlBw max filter 内 BtlBw 超时过期以及 ProbeRTT 逐步让每个 BBR 流都找到自己合适的份额。在一开始只有红色的线，之后绿的来了，红色线继续按原来速度发数据链路一定会拥塞，并且因为有两个流了红线的 deliveryRate 一定会下降，BtlBw 超时后红线降低发送速率。大致上就是这么相互作用，每来一个流需要调整一下直到稳定。

来自[4]

BBR 跟 CUBIC 等基于丢包的算法共存时会有问题吗？

列一下 Reno，CUBIC，BBR 三个在时间和发送速率上的图做对比。

来自[1]

之前提到 TCP Vegas，Vegas 会被基于丢包的算法挤掉份额，不能跟这些算法共存，所以无法流行起来。对于 BBR 的话，它抢占份额的方式主要靠 ProbeBW 期间按 1.25 倍估计值发送数据，会给链路带去压力，为自己抢占生存空间；再有就是 Startup 阶段，BBR 相对 CUBIC 来说会为链路带去更多数据去抢占份额，这个只在初始阶段有用，但如果 BBR 上的数据如果能持续发送，初始期占的份额可能就能一直保持下去。

BBR 如何处理丢包

在网上搜很多文章都说 BBR 根本不管丢包，完全基于自己的周期即 ProbeBW 内的周期去计算发送率，CWND 来发数据包，所以 BBR 根本无视丢包。但实际上 BBR 作者写的 BBR 介绍里明确说了 BBR 是会管丢包情况的，在这 BBR: Congestion-Based Congestion Control - ACM Queue。以及这里：Modulating cwnd in Loss Recovery

总之就是说 BBR 处理丢包的时候需要区分 RTO 和 Fast Retransmission 两个场景，RTO 下与 CUBIC 差不多；只有 Fast Retransmission 下，发送速率还能保持在较高位置，但也是受影响的。

下面是 CUBIC （红色）和 BRR （绿色）在面对丢包的时候吞吐量表现。CUBIC 在丢包 1% 的时候基本就无法工作了，BRR 能扛到 20% 的丢包率。黑线是理想状况下的吞吐量，因为有丢包存在，所以吞吐量随着丢包率升高而递减。

来自[4]

对于右侧绿线是个断崖式有这么一些原因：

• 丢包率高了以后一个是会引起 Fast Retransmission，会对吞吐量有影响，另一个是可能出现 RTO，出现 RTO 后 CWND 立即降到 1 跟 CUBIC 表现就一致了，吞吐量会大幅度下滑；
• 丢包率高了之后会严重影响实际 Delivery Rate 的计算，让计算得到的值比实际值小，进而让 BBR 错误估计当前 BtlBw，减小发送速率。因为丢包率固定不变，减小发送速率后 Delivery Rate 可能会进一步减小，最终降为 0；

对于为什么是丢包率接近 ProbeBW 增周期增益 (1.25) 时会出现吞吐量大幅度下滑我理解是这样的：

在估计 BtlBw 是是取过去一段时间内的最大值，比如丢包率是 10%，如果没有增周期发送者通过 Delivery Rate 计算得到的带宽比实际 BtlBw 会低 10%，之后会调整发送速度变成 90% BtlBw，因为依然有 10% 的丢包率，在 90% BtlBw 从估计带宽用的滑动窗口过期移除后，发送速率会降为 90% * 90% BtlBw = 81% BtlBw，最终这么一步步下降到 0，这是没有增周期的场景。

但是因为有增周期的存在，假设当前估算的带宽为 BtlBw，普通周期发送速率就是 BtlBw，增周期是 1.25 BtlBw，减周期是 0.75 BtlBw。当丢包率是 10%，普通周期时计算出来的 Delivery Rate 是 90% BtlBw，增周期计算出来的是 1.25 * 90% * BtlBw = 1.125 BtlBw ，但实际上 BtlBw 是链路带宽不可能超越 BtlBw，所以增周期 Delivery Rate 还是 BtlBw，减周期是 0.75 * 90% * BtlBw = 0.675 BtlBw，这么一来根据过去一段时间 Delivery Rate 最大值估算带宽时得到的带宽还是 BtlBw，所以 10% 丢包率的时候吞吐量受丢包的影响不大。

当丢包率增长到 20% 的时候，根据上面的算法，增周期计算出来的 Delivery Rate 就马马虎虎刚好是 1 倍 BtlBw 了，因为 1.25 * 80% * BtlBw = 1 BtlBw。只要有风吹草动让计算的 Delivery Rate 低于最初的 BtlBw，那一步步的计算的 Delivery Rate 就会和实际带宽偏离越来越大，最终降到 0。也就是说增周期的增益和丢包率的乘积能大于 1，就能保持发送速度，小于 1 则会断崖式下滑，大于 1 是不可能的。

所以 BBR 对 CUBIC 在丢包方面的优势是说，CUBIC 是算法结构上导致丢包一定会让性能大幅度下滑。而 BBR 是在一定程度上能通过配置去容忍丢包。比如增周期增益提升到 1.5，抗丢包能力一定会大幅度提升，但性能受重传数据影响会越来越大。

参考：

1. blog.apnic.net/2017/05/09/…
2. BBR Congestion Control
3. Cubic
4. cacm.acm.org/magazines/2…
5. queue.acm.org/detail.cfm?…
6. www.net.in.tum.de/fileadmin/b…
7. AusNOG 2019: TCP and BBR
8. A bit about TCP BBR - http://blog.cerowrt.org/
9. tcp_bbr.c source code linux/net/ipv4/tcp_bbr.c - Woboq Code Browser
10. RFC 6937 - Proportional Rate Reduction for TCP

其他分享内容：

• 常见 TCP 拥塞避免算法浏览（上）

• 深入学习理解 IO 多路复用

• CPU Cache 基础解析

• 内存屏障及其在-JVM 内的应用（上）

• 内存屏障及其在-JVM 内的应用（下）

更多内容欢迎关注 LeanCloud 官方微信号：「LeanCloud 通讯」

这篇关于常见 TCP 拥塞避免算法浏览（下）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！