网络协议 [2] - TCP 拥塞控制

1 背景

TCP 协议是一种可靠的网络传输协议，它通过超时重传来保证数据传输的可靠性。发送方检测到丢包后会进行重传，从而保证接收方能够收到完整的数据。这看起来很理想，但真实的环境往往比较复杂。一般来说，发生丢包意味着网络负载过重，若此时继续进行重传尝试，无疑会进一步加重网络的负担，引起更频繁的丢包。而这反过来又加剧了超时重传，形成恶性循环，最终导致网络瘫痪、吞吐量急剧下降。针对这种情况，TCP 引入了拥塞控制机制，它的目标是为了根据网络环境动态调整发送方的传输速率，从而最大化利用网络带宽，同时保证大家都能公平地分一杯羹。

2 基本思想

为了控制传输速率，TCP 采用了滑动窗口协议。发送方实际窗口大小 W 的计算公式如下：

W=min(awnd,\ cwnd) \notag

其中，awnd 为接收方通告窗口大小，cwnd 为拥塞窗口大小。实际窗口 W 取两者的最小值，这样可以同时兼顾接收方的处理速率和网络的传输速率。

接收方通告窗口 awnd 的值可以通过返回的 ACK 获得，而拥塞窗口 cwnd 的值则需要动态估计。拥塞控制算法的主要目标就是采用各种方法来估计 cwnd 的值。本文将详细讨论基于丢包和基于时延的两类拥塞控制算法，并比较它们的优劣。

一个优秀的拥塞控制算法需要同时满足以下关键要素：

TCP 友好性（TCP friendliness）：当与使用不同拥塞控制算法的其他 TCP 连接共享网络带宽时，不应过度占用网络资源，应让其他连接也能获得公平份额。
RTT 公平性（RTT fairness）：当与具有不同往返时延的其他 TCP 连接共享网络带宽时，不应过度占用网络资源，应让其他连接也能获得公平份额。
高带宽利用率（High bandwidth utilization）：在保证以上两点的基础上，尽可能充分利用网络带宽，提高吞吐量。

3 基于丢包的算法

3.1 Tahoe

Tahoe 算法主要由三个机制组成：慢启动、拥塞避免和快速重传。当连接初次建立时，会执行慢启动过程。在此阶段，拥塞窗口（cwnd）随着每次往返时延（RTT）呈指数增长，直到超过慢启动阈值（ssthresh）。此后，进入拥塞避免阶段，发送窗口随着每次 RTT 线性增长，逐步逼近网络的拥塞阈值。若在此阶段发生丢包（超时或快速重传），则立即将发送窗口置为 1，并重新进入慢启动阶段。整个传输过程中，慢启动和拥塞避免两个过程不断交替，动态控制着发送窗口的大小。下图展示了发送窗口大小随时间的变化过程。

3.1.1 慢启动

整个慢启动（Slow Start）过程可以概括为以下几点：

初始化 cwnd 为 1，表示可以传 1 个 MSS（Maximum Segment Size，最大报文段大小）大小的数据。
每收到一个 ACK，设置 cwnd = cwnd + 1，呈线性增长。
每经过一个往返时延（RTT），设置 cwnd = cwnd^2，呈指数增长。
设置一个慢启动阈值（ssthresh），当 cwnd >= ssthresh 时，进入拥塞避免阶段。

3.1.2 拥塞避免

拥塞避免阶段如下：

每收到一个 ACK，设置 cwnd = cwnd + 1/cwnd。
每经过一个 RTT，设置 cwnd = cwnd + 1，呈线性增长。
若发生超时丢包，设置 ssthresh = cwnd/2，cwnd = 1，并进入慢启动阶段。

3.1.3 状态机

3.1.4 存在的问题

全局同步问题：在某些情况下，许多 TCP 连接可能会同时发生丢包，导致所有连接几乎同时进入慢启动阶段。这种现象被称为全局同步问题。它使得网络带宽的利用率产生明显的周期性波动。
对单次丢包的反应过于剧烈：在 TCP Tahoe 中，单次丢包就能将拥塞窗口减半，这种反应可能过于剧烈。在某些网络环境中，丢包可能并非总是由网络拥塞引起，因此这种剧烈的反应可能会导致不必要的性能下降。
对多次丢包的处理不佳：TCP Tahoe 在一个 RTT 内只能检测到一次丢包。如果一个 RTT 内发生多次丢包，TCP Tahoe 可能需要多个 RTT 才能检测到所有丢包。这可能导致拥塞窗口的调整过慢，进一步降低网络性能。

3.2 Reno

由上可知，Tahoe 算法在快速重传时会设置发送窗口为 1，并启动慢启动过程。我们知道，快速重传是由于收到 3 个重复 ACK 引起的。既然能收到重复 ACK，说明网络情况并没有那么糟糕，不需要像超时丢包那样反应剧烈，这样反而会使网络吞吐量更低。因此，Reno 算法在 Tahoe 算法的基础上提出了快速恢复机制。

3.2.1 快速恢复

快速恢复阶段如下：

当收到重复 ACK 时，设置 cwnd = cwnd + 1，继续处于快速恢复阶段。
当收到一个崭新 ACK 时，设置 cwnd = sshthresh，进入拥塞避免阶段。
若发生超时丢包，则设置 sshthresh = cwnd / 2，并设置 cwnd = 1，进入慢启动阶段。

3.2.2 状态机

3.2.3 存在的问题

多包同时丢失时的性能问题：当同一窗口内丢失多个数据包时，可能导致过早退出快速重传阶段，并多次降低 CWND。

如下图所示，当发送方收到 3 个重复 ACK 时，触发快速重传丢失的数据包，进入快速恢复阶段。此时，数据包 3 的 ACK 到达被视为新的 ACK，导致发送方将 CWND 减半并退出快速重传阶段，进入拥塞避免阶段。但需要注意的是，数据包 3 同样丢失了，因此发送方随后还会收到针对数据包 3 的重复 ACK。这将导致发送方再次重传数据包 3，并重新进入快速重传阶段。当多个数据包丢失时，这个过程可能会重复多次，导致整个过程中 CWND 快速下降。

3.3 NewReno

3.3.1 基本思想

NewReno 是在 Reno 协议基础上的改进，其主要优势在于能够检测和处理多个数据包的丢失，因此在处理多包丢失时比 Reno 更高效。与 Reno 类似，NewReno 在收到三个重复包后启动快速重传，但主要区别在于 NewReno 会一直保持在快速恢复状态，直到所有未被确认的数据包都被确认，从而避免了 Reno 在快速恢复阶段 cwnd 呈指数下降的潜在问题。

NewReno 的快速重传阶段与 Reno 相同，但在快速恢复阶段，NewReno 允许多次重传。每次进入快速恢复阶段时，NewReno 会记录所有最大的未确认报文段。在快速恢复阶段，每当接收到新的 ACK 时，NewReno 有两种可能的反应：

如果新的 ACK 确认了快速恢复阶段开始时所有未被确认的报文段，那么 NewReno 将退出快速恢复，设置 cwnd 为 ssthresh，然后像 Tahoe 协议一样继续拥塞避免。
如果新的 ACK 只确认了部分报文段，那么 NewReno 将推断队列中的下一个报文段已经丢失，并重传该报文段，同时将重复 ACK 的数量重置为零。

只有当所有报文段都被确认后，NewReno 才会退出快速恢复阶段。

3.3.2 存在的问题

每个 RTT 轮次只能检测到一个丢包：NewReno 收到重复 ACK 后，会立即重传丢失的数据包，并等待其确认。由于每个丢包的确认和重传都需要一个 RTT，如果在一个窗口内发生多次丢包，将导致多个 RTT 的恢复时间，在高丢包环境下严重影响性能。

3.4 SACK

3.4.1 基本思想

TCP SACK（Selective Acknowledgments，选择性确认）是对 TCP Reno 的改进，解决了 TCP Reno 和 TCP NewReno 面临的问题，即能够在每个往返时延（RTT）内识别并重传多个丢失数据包。SACK 保留了 Reno 版本的慢启动和快速重传机制。在没有检测到丢包的情况下，它也可以依靠 Tahoe 的粗粒度超时机制。

TCP SACK 协议规定，数据包的确认应该是选择性的，而非累积性的。每个确认消息（ACK）都带有一个字段，描述哪些数据段已被接收方确认。这样，发送方就能清楚地知道哪些数据段已确认，哪些还未确认。当发送方进入快速恢复模式时，它会初始化一个名为 pipe 的变量来估计网络中未完成的数据包数量，并将拥塞窗口 cwnd 设置为当前大小的一半。每次收到 ACK 时，pipe 的值减 1；每次重传一个数据段时，pipe 的值加 1。当 pipe 的值小于拥塞窗口 cwnd 的值时，发送方检查并发送未被确认的数据段。如果没有待确认的数据段，发送方则发送新的数据包。因此，可以在一个 RTT 内重传多个丢失的数据段。

3.4.2 存在的问题

兼容性问题：并非所有的 TCP 实现都支持 SACK 机制。通常，拥塞控制只需要修改发送方的代码，而 SACK 需要修改接收方的代码，这是一项庞大的工程。

3.5 HSTCP

根据数学推算，标准 TCP 的拥塞窗口 w 和丢包率 p 存在一定的约束关系，该关系的数学表达式为： $w(p) = 1.2/\sqrt{p}$ 。它的图形如下图所示。

可以看到，随着丢包率 p 的不断增大，拥塞窗口 w 将急剧减小。换句话说，随着拥塞窗口 w 的增大，丢包率 p 必须足够小。这就使得标准 TCP 无法充分利用高带宽网络。假设当前带宽为 10Gbps，往返时间为 100ms，每包字节数为 1500 字节。为了充分占满带宽，拥塞窗口 w 需要达到 83,333 个报文段。此时可计算最大丢包率为：

p = 1.5 / w^2 \approx 1/5,000,000,000 \notag

这意味着每发送 5,000,000,000 个包最多只能丢 1 个包。丢包间隔时间可计算为：

S = ((1/p ÷ w) × 100) ÷ 1000 ≈ 6000s ≈ 1.7h \notag

也就是说至少要经过 1.7 小时才允许丢一个包，这显然是不可能达到的。

3.5.1 修改响应函数

HSTCP 算法通过修改响应函数 w(p) 来降低丢包率 p 对拥塞窗口 w 的影响，为此引入了以下四个参数：

low_w：表示最小窗口。只有在大于最小窗口时才使用 HSTCP 算法。
low_p：最小窗口时的丢包率。
high_w：期望达到的最大窗口，根据带宽估算。
high_p：最大窗口时可接受的丢包率，根据经验估算。

为了保证 TCP 友好性，当窗口较小时，HSTCP 仍然保持和标准 TCP 相同的增长速度。

（1）当 cwnd <= low_w 时，使用标准 TCP 响应函数 $w(p) = 1.2/\sqrt{p}$ 。

（2）当 cwnd > low_w 时，使用修改后的响应函数 $w(p) = ({\Large \frac{p}{low\_p}})^S \times low\_w$ 。

这里有一个参数 S，其值的计算公式为：

S = \frac{log(high\_w) - log(low\_w)}{log(high\_p) - log(low\_p)} \notag

修改后的响应函数 w(p) 曲线如下图所示：

由上图可以看出，当丢包率 p 增大时，拥塞窗口 w 也在增大，只是增大的速率在不断减小。这表明在高丢包率、高带宽的网络环境下，拥塞窗口依然能够达到足够的高度，从而充分利用网络资源。

3.5.2 转换为控制参数

在修改了响应函数 w(p) 后，还不能直接运用，需要将其转换为标准 TCP 形式的控制参数。标准 TCP 的窗口控制函数有如下形式：

当没有发生拥塞事件时，cwnd 按照以下公式增长： $w = w + a(w)/w$
当发生拥塞事件时，cwnd 按照以下公式减小： $w = w - b(w)*w$

在标准 TCP 中， $a(w)$ 的值为固定值 1， $b(w)$ 的值为固定值 1/2。现在需要将这两个参数变为可动态配置的，根据拥塞窗口 $w$ 的大小：

（1）当 $w \leq low_w$ 时， $a(w)$ 和 $b(w)$ 保持和标准 TCP 一致，即： $a(w) = 1, \ b(w) = {\large \frac{1}{2}}$ 。

（2）当 $low_w < w < high_w$ 时， $a(w)$ 和 $b(w)$ 按以下公式计算：

\begin{aligned} a(w) &= {\small W}^2 \times p(w) \times 2 \times {\frac{b(w)}{2-b(w)}} \\ b(w) &= (high\_decrease - 0.5) \times {\frac{log(w) - log(low\_w)}{log(high\_w) - log(low\_w)}}+ 0.5 \end{aligned} \notag

（3）当 $w \geq high_w$ 时， $a(w)$ 和 $b(w)$ 按以下公式计算：

\begin{aligned} a(w) &= {high\_w}^2 \times high\_p \times 2 \times {\frac{b(w)}{2-b(w)}} \\ b(w) &= high\_decrease \end{aligned} \notag

其中， $high\_decrease$ 是一个可配置的常量。

3.5.3 存在的问题

存在 RTT 不公平性：由于 HSTCP 算法在 RTT 较大时采用更激进的增长策略，会挤占标准 TCP 链路的带宽，使其处于低带宽状态。

3.6 BIC

二分增长拥塞（Binary Increase Congestion，BIC）控制算法的基本思想是，理想的窗口大小必定处于发生过丢包和没有发生过丢包的某个位置之间。因此，我们可以采用二分查找法快速找到目标窗口的位置，这也是 BIC 算法名字的由来。同时，BIC 也解决了 HSTCP 算法的 RTT 不公平问题。

3.6.1 二分搜索增长

首先，设置最小窗口大小，它可以是任何没有发生过丢包的当前窗口大小。然后，根据经验设置一个会发生丢包的最大窗口大小。由于最小窗口不会发生丢包，而最大窗口一定会发生丢包，所以理想的窗口大小应该处于这两个值之间。这样一来，就可以采用二分查找的方式快速确定目标窗口大小。在增加窗口大小的过程中，若发生任何丢包，可将当前窗口视为新的最大值，并将丢包后减小的窗口大小视为新的最小值。然后，在这两者之间重新寻找一个平衡点。

该方法的基本原理是，因为网络在新的最大窗口附近产生丢包，但在新的最小窗口附近不产生丢包，所以目标窗口大小必定在这两者之间。我们使用二分查找来寻找目标窗口。当达到目标窗口大小时，如果未发生丢包，则当前窗口大小成为新的最小值，并计算新的目标。重复此过程，使用更新后的最大值和最小值，直到最大值和最小值之间的差值低于预设阈值，即最小增量 $S_{min}$ 。

3.6.2 加性增长

当当前窗口与目标窗口之间的距离过大时，直接将当前窗口大小增加到目标窗口可能会给网络带来太大的压力。因此，这里引入了加性增长策略。简单来说，在二分查找过程中，如果当前窗口与目标窗口的距离大于最大增量 $S_{max}$ ，那么在下一个 RTT 中，当前窗口不会直接增加到目标窗口，而是只增加 $S_{max}$ ，直到当前窗口与目标窗口的距离小于 $S_{max}$ 。只有这时，才会直接将当前窗口大小增加到目标窗口大小。这样，在窗口大幅度缩减之后，该策略先线性增加窗口，再对数增长。这种结合了二分搜索增长和加性增长的策略被称为二分增长（Binary Increase）策略。

3.6.3 超出最大值之后

随着当前窗口不断接近最大窗口，它们之间的距离也在不断缩小。由于存在最小增量 $S_{min}$ ，当前窗口必然会在某个时刻超过最大窗口。此时需要重新设置最大窗口值。由于最大值未知，这里设置一个默认最大值（一个很大的常量），并将当前窗口设置为最小值。此时当前窗口距离目标中点可能很远，若按照二分增长，会按照最大增量 $S_{max}$ 线性增长。由于此时处于上一轮的饱和点附近，网络是否好转尚且未知，所以这种增长还是偏激进。这里先采用慢启动策略。假设当前窗口为 cwnd，最大增量为 $S_{max}$ ，那么慢启动过程将在每个 RTT 轮次内以 cwnd + 1、cwnd + 2、cwnd + 4、…、cwnd + $S_{max}$ 的步长增长。使用慢启动的方法探测可用带宽，直到能够安全地以 $S_{max}$ 增加窗口。经过慢启动过程后，再切换到二分增长。

3.6.4 快速收敛

在 HSTCP 算法中，拥有较大窗口的流会占用更多带宽，而窗口较小的流只能占用少量带宽。这显然对较小窗口的流不公平。为了修正此行为，BIC 算法进行了调整。具体来说，在二分搜索增长过程中，一旦窗口减小，需要重新定义最大值和最小值。如果新的最大值小于先前的最大值，表明窗口正处于下降趋势，可能有新的连接加入了当前网络。因此，我们必须重新调整最大值，使其与新的目标窗口保持一致，即设置为 (max_win-min_win)/2，并重新定义目标窗口。然后，可以继续标准的二分增长策略。这种方法称为快速收敛。

3.6.5 伪代码

如果没有发生丢包，拥塞窗口（cwnd）将会按照三种不同的方式增长：二分搜索增长、加性增长和慢启动增长。具体增长过程如下：

if (cwnd < wmax)          // 二分搜索 OR 加性增长
  bic_inc = (wmax - cwnd) / 2;
else                      // 慢启动 OR 加性增长
  bic_inc = cwnd - wmax;
if (bic_inc > Smax)       // 加性增长
  bic_inc = Smax;
else if (bic_inc < Smin)  // 二分搜索 OR 慢启动
  bic_inc = Smin;
cwnd = cwnd + (bic_inc / cwnd);

如果发生丢包事件，将对当前窗口（cwnd）进行乘性减少。有一个减少因子 β，用于将 cwnd 减少 (100×β)%。具体减少过程如下：

if (cwnd < wmax) // 快速收敛
  wmax = cwnd * (2-β) / 2;
else 
  wmax = cwnd;
cwnd = cwnd * (1-β);

3.6.6 存在的问题

公平性问题：在 RTT 较小的情况下，BIC 算法的窗口增长速度仍然过快，会挤占标准 TCP 的带宽。

3.7 CUBIC

CUBIC 将现有的线性窗口增长修改为三次函数，该函数是时间的函数。这使得窗口增长与 RTT 无关，即无论传输快慢，当前窗口增长都基于时间，在特定时间做特定的事。这完美地解决了 RTT 不公平性，在不同 RTT 的流之间实现了更公平的带宽分配。

3.7.1 算法细节

（1）为了保证 TCP 友好性，如果当前窗口大小 cwnd 小于阈值 $W_{tcp(t)}$ ，将使用 $W_{tcp(t)}$ 的值来更新当前窗口。 $W_{tcp(t)}$ 的计算公式如下：

W_{tcp(t)} = W_{max}(1-\beta) + 3 \frac{\beta}{1+\beta} \frac{t}{RTT} \notag

由上式可知， $W_{tcp(t)}$ 实际上是时间 t 的线性函数，这意味着拥塞窗口在较短 RTT 中保持线性增长，就像标准 TCP 一样。

（2）当拥塞窗口 cwnd > $W_{tcp(t)}$ 时，使用以下三次函数来更新窗口大小。每收到一个新的 ACK，计算自上次窗口减小以来经过的时间 t，然后将 t 代入以下公式计算当前窗口值：

W(t) = C \times (t-K)^3 + W_{max} \notag

其中 C 表示缩放因子，是一个常数； $W_{max}$ 是上次窗口减小之前的窗口大小；K 表示在没有进一步丢包的情况下将 cwnd 增加到 $W_{max}$ 所需的时间。K 在每次丢包事件后更新，其计算公式为：

K = \sqrt[3]{\frac{W_{max} \cdot \beta}{C}} \notag

假设 C = 0.4，β = 0.2，将其代入公式，则 K 等于下式：

K = \sqrt[3]{\frac{W_{max}}{2}} \notag

如果 $W_{max}$ = 250，可以计算出 K = 5s。假设 RTT = 100ms，则需要 50 个 RTT 才能增长到最大窗口 $W_{max}$ 。

（3）如果发生丢包事件，将当前窗口设置为最大值 $W_{max} = cwnd$ ，然后将当前窗口减小 $cwnd = (1-\beta)cwnd$ ，然后进入快速恢复阶段。

恢复期间，K 使用以下公式更新：

K = \sqrt[3]{\frac{\beta \cdot W_{max}}{C}} \notag

$W_{max}$ 使用以下公式更新：

W_{max} = \beta \cdot W_{max} \notag

3.7.2 与缓冲区的关系

在上图中，黄色线表示拥塞窗口的大小，蓝色线表示缓冲队列中的数据包数量，图中包含两条浅绿色水平线。较低的那条代表链路管道容量，较高的那条代表链路的总容量。开始时，黄色线开始增长，但不超过下方绿线。此时缓冲队列中没有任何积压，因此蓝色线保持为零。当黄色线越过下方绿线时，表示链路管道已满，之后到达的数据包将被放入缓冲队列。此时蓝色线将开始快速增长，直到达到上方绿线，表示缓冲队列已满，此后到达的数据包将被丢弃。

一旦发生丢包事件，黄色线将开始快速下降。当它向下穿过上方绿线时，蓝色线也开始下降。下降到一定程度后，黄色线将重新开始增长。此后，黄色线将始终在下方绿线附近波动，时而低于时而高于它，蓝色线也会呈现出周期性的起伏。然而值得注意的是，蓝色线在波动过程中始终保持在零以上，这也说明 CUBIC 会始终在缓冲队列中保持一定数量的数据包。

3.7.3 存在的问题

无法快速响应网络状况变化：CUBIC 大部分时间都停留在 $W_{max}$ 附近，需要一定时间才能检测到网络带宽的变化。
链路延迟较大：丢包发生后窗口减小，但很快又会逼近 $W_{max}$ 。没有足够的时间等待链路缓冲区完全清空，缓冲区又开始重新积压，导致缓冲区处于比较满的状态，这会导致整体链路延迟增加。

4 基于时延的算法

4.1 Vegas

在上图中，状态 1 表示缓冲队列无积压，整条链路比较顺畅。状态 2 表示缓冲队列有轻微积压，此时延迟会增加，但尚未发生丢包。状态 3 表示缓冲队列已满，开始发生丢包。之前介绍的基于丢包的算法只在状态 3 才开始采取措施，但最优的运营点应该是在状态 2。Vegas 算法的目标就是在状态 2 时就采取行动，减少网络拥塞，减少丢包重传的现象。实验表明，与 Reno 相比，Vegas 的吞吐量可提高 40% 到 70%，而重传的数据量仅为 Reno 的 20% 到 50%。

4.1.1 新的重传机制

在 Reno 中，往返时间（RTT）和方差估计是使用粗粒度定时器（约 500 毫秒）计算的，这意味着 RTT 估计并不十分准确。这种粗粒度影响了计算本身的准确性，也影响了 TCP 检查是否应该对某个报文段进行超时重传的频率。Reno 不仅在粗粒度超时发生时重传，还会在收到三个重复 ACK 时重传。当 Reno 收到无法确认的新数据时，它会发送重复 ACK，因为之前的所有数据尚未全部收到。

Vegas 通过以下方式扩展了 Reno 的重传机制。

首先，每次发送数据包时，Vegas 会读取并记录系统时钟。
当收到 ACK 时，Vegas 再次读取时钟，并使用该时间以及相关报文段的记录时间戳进行 RTT 计算。
然后，Vegas 使用这一更准确的 RTT 估计，在以下两种情况下决定是否进行重传。

Vegas 重传的两种情况：

当收到重复 ACK 时，Vegas 检查当前时间与相关记录报文段的时间戳之间的差值是否大于超时值。如果是，Vegas 立即重传该报文段，无需等待三个重复 ACK。在许多情况下，丢包要么非常严重，要么窗口太小使得发送方永远不会收到三个重复 ACK，因此 Reno 必须依赖上述粗粒度超时。
当收到非重复 ACK 时，如果是重传后的第一个或第二个 ACK，Vegas 再次检查自该报文段发送以来的时间间隔是否大于超时值。如果是，Vegas 重传该报文段。这将在无需等待重复 ACK 的情况下捕获可能在重传之前丢失的任何其他报文段。

换句话说，Vegas 将收到特定 ACK 视为检查是否应该发生超时的触发条件。如果这些机制无法识别丢失的报文段，它仍然包含 Reno 的粗粒度超时代码。

4.1.2 拥塞避免机制

Reno 是一种被动的拥塞控制算法，它依赖于丢包事件作为网络拥塞的信号。这种设计使其无法在网络拥塞的早期阶段（即丢包发生之前）采取预防措施。因此，为了找到连接的可用带宽，Reno 必须通过引起丢包来进行测量和调整。

Vegas 算法通过测量吞吐量来调整窗口大小。它采用的简单思想是：传输中的字节数与预期吞吐量成正比。因此，随着窗口大小的增加，传输中的字节数也会增加，带宽吞吐量也应相应提高。

步骤 1：首先，初始化连接的基本往返时间（BaseRTT）。在实际应用中，一般设置为所有测得的往返时间中的最小值。

步骤 2：计算预期吞吐量：Expected = WindowSize / BaseRTT。其中 WindowSize 是拥塞窗口的当前大小。

步骤 3：计算实际吞吐量：Actual = transmittedBytes / transmittedRTT。此计算每往返时间执行一次。

步骤 4：计算预期吞吐量与实际吞吐量之间的差值：Diff = Expected - Actual。根据此差值相应地调整窗口大小。这里定义了两个阈值：α < β。窗口调整策略如下：

当 Diff < α 时，在下一个往返时间内线性增加拥塞窗口。
当 Diff > β 时，在下一个往返时间内线性减小拥塞窗口。
当 α < Diff < β 时，保持拥塞窗口不变。

请注意，当实际吞吐量大于预期吞吐量时，需要将 BaseRTT 更改为最近采样的 RTT。

4.1.3 改进的慢启动机制

Vegas 预期随着网络带宽的增加，慢启动期间的预期损失也会相应增加。为了在慢启动期间检测并避免拥塞，Vegas 只允许每隔一个往返时间进行指数增长。在此期间，拥塞窗口保持不变，以便有效比较预期速率和实际速率。当实际速率低于预期速率一定量（称为 y 阈值）时，Vegas 会从慢启动模式切换到线性增加/减少模式。

4.1.4 存在的问题

无法充分利用网络带宽：Vegas 算法的拥塞窗口 cwnd 同样是线性增长的，因此与标准 TCP 一样，无法充分利用较大的网络带宽。
无法与基于丢包的算法共存：一旦 Vegas 检测到 RTT 增加，就会减慢发送速率。此时尚未发生丢包事件，因此基于丢包的算法不会降低发送速率。因此，当与基于丢包的算法共享网络带宽时，Vegas 很可能被挤占。

4.2 BBR

在传统的基于丢包的算法中，默认丢包对应着网络拥塞。然而，随着高速网络的发展，这种对应关系可能并不可靠。如前文所述，随着拥塞窗口的增大，丢包率必然上升。因此，我们不能仅依赖丢包作为判断网络拥塞的唯一依据。为了更好地利用网络带宽，我们首先需要了解真正的网络瓶颈在哪里。下图展示了 BBR 算法对不同阶段网络带宽限制的解释。

在上图中，上半部分展示了 RTT 随 inflight 数据包数量的变化，下半部分展示了吞吐量随 inflight 数据包数量的变化。蓝色线表示 RTprop 的变化，绿色线表示 BtlBw 的变化，红色线表示整个链路的缓冲区瓶颈。整个图从左到右可以分为三个区域，分别是：应用受限（app limited）、带宽受限（bandwidth limited）和缓冲区受限（buffer limited）。

应用受限：此时没有足够的数据包填满数据管道，因此吞吐量受应用本身限制。此时 RTprop 的值是固定的，BtlBw 呈线性增长。
带宽受限：此时虽然管道容量被数据包填满，但缓冲队列尚未被填满。因此，吞吐量受管道带宽限制。此时 BtlBw 的值是固定的，RTprop 呈线性增长。
缓冲区受限：此时数据包已经填满了缓冲队列，从此处开始将开始发生丢包。因此，吞吐量受缓冲区大小限制。

传统的基于丢包的算法在缓冲区受限阶段进行优化，而 BBR 算法认为最优的优化点应该在带宽受限阶段。

4.3.1 探测指标

（1）RTprop（往返传播时间，round-trip propagation time）

RTprop 是指当前链路的最小往返时间。它是当前链路的物理属性，只有当连接路径发生变化时才会改变。它与 RTT（Round Trip Time，往返时间）不同，二者之间的关系可用以下等式表示：

RTT_t = RTprop_t + \eta_t \notag

在上述等式中， $\eta_t$ 始终大于 0。它表示路径上产生的噪声，例如接收方的延迟 ACK 策略、ACK 聚合等，都会导致往返时间延长。我们可以测量 RTT，但如何计算噪声呢？我们可以计算一个窗口内的最小 RTT，并将其作为 RTprop 的估计值。

\widehat{RTprop} = RTprop_t + min(\eta_t) = min(RTT_t) \notag

（2）BtlBw（瓶颈带宽，bottleneck bandwidth）

BtlBw 表示当前链路的瓶颈带宽，也可以说是管道容量。任何超过此值后发送的数据包将被放入缓冲队列，这将增加链路的往返时间。BtlBw 的估计值可以通过以下等式计算：

\widehat{BtlBw} = max(deliveryRate_t) \notag

上述 deliveryRate 可以通过传输的数据量除以 RTT 获得。

4.3.2 状态机

使用 BBR 进行拥塞控制的流在任何给定时刻处于以下四种状态之一：启动（Startup）、排空（Drain）、带宽探测（ProbeBW）和 RTT 探测（ProbeRTT）。其中，ProbeBW 是稳态，其他三种状态是瞬态。以下是四种状态的转换图：

（1）启动（Startup）

启动是 BBR 算法的初始阶段。为了快速确定链路的瓶颈带宽（BtlBw），BBR 算法以指数方式增加发送速率。在此过程中，inflight 数据包数量迅速增加，而往返时延（RTT）保持不变，因此 deliveryRate 也快速增加。当 deliveryRate 在某个时刻不再继续增长时，BBR 测量的瓶颈带宽 BtlBw 也达到了峰值。此时，BBR 退出启动状态，进入排空状态。

（2）排空（Drain）

排空阶段的目标是快速排空启动阶段在缓冲队列中积压的数据包。此时，发送速率设置为启动阶段的倒数，指数级降低当前发送速率。当 BBR 观察到 inflight 数据包数量与 BDP 估计值大致相同时，将退出排空状态，进入 ProbeBW 状态。之后，它将在 ProbeBW 和 ProbeRTT 状态之间周期性切换，间歇性地探测 BtlBw 和 RTprop。

（3）带宽探测（ProbeBW）

在 ProbeBW 状态中，周期一般分为八个阶段，例如 [1.25, 0.75, 1, 1, 1, 1, 1, 1]。首先执行增加期，将发送速率提升到稳态的 1.25 倍，直到发生丢包或 inflights 数据量达到 BDP 的 1.25 倍。观察时延是否增加，如果时延增加而 deliveryRate 不变，说明链路带宽没有变化，而是有队列积压。随后进入减少期，将发送速率降低到稳态的 0.75 倍，等待一个 RTprop 或直到 inflights 数据量小于 BDP，使得链路上在增加期产生的队列积压可以被清除。随后保持 inflights 等于 BDP 稳定若干个 RTprop，然后再次开始增加期。

（4）RTT 探测（ProbeRTT）

在 ProbeRTT 状态以外的状态中，如果 RTprop 的估计值超过 10 秒没有更新，就会进入 ProbeRTT 状态。在此状态下，当前窗口 cwnd 会被降低到一个非常小的值，以排空队列中积压的数据包，这可以降低时延，便于 RTprop 的测量。保持此状态一段时间后，根据是否估计链路已填满，将转换到启动或 ProbeBW 状态。

4.3.3 工作过程

下图为带宽为 10Mbps、时延为 40ms 的网络的数据。蓝色线代表 RTT，绿色线代表 inflight 数据包数量，红色线代表 deliveryRate。红色线上方的黑色线是当前估计的 BtlBw。黑色线上方的 cycle gain 用于控制发送速度，发送方当前的发送速率为 cycle gain * BtlBw。BBR 会周期性地将 cycle gain 设置为大于 1，这会使 inflight 数据包数量增加。如果链路上的 BtlBw 没有变化，增加的 inflight 数据包将积压在缓冲队列中，导致 RTT 上升。此过程将持续一个 RTprop。随后，cycle gain 的值会被设置为小于 1，这会使 inflight 数据包数量减少。先前积压在缓冲队列中的数据包将被快速清除，RTT 也会下降。此过程也将持续一个 RTprop。随后 cycle gain 将恢复到 1 并保持稳定若干个 RTprop。整个过程周期性执行，使得曲线呈现脉冲状的波动。

下图上部分展示了带宽从 10Mbps 增加到 20Mbps 的过程，下部分展示了带宽从 20Mbps 减少到 10Mbps 的过程。在大约 20 秒处，链路上的带宽突然增加，此时 RTT 有一个小幅下降，随后 inflight 数据包数量骤降。此时 BBR 检测到带宽增加了，因此相应增加发送速率。在接下来的三个周期中，inflight 数据包数量持续上升，而 RTT 保持不变，直到出现第一个小峰值。此时 BBR 算法检测到管道已达到饱和，因此停止进一步提高发送速率。

在大约 40 秒处，链路上的带宽突然下降。由于 BBR 维护着一个滑动窗口用于存储检测到的 BtlBw，并选择窗口中的最大值作为当前链路的 BtlBw，即使带宽突然下降，BBR 仍使用之前检测到的 BtlBw 值，因此不会立即降低发送速率。此时 inflight 数据包量迅速增加并开始在缓冲队列中积压，导致 RTT 大幅上升。然而，BBR 会限制 inflight 数据包量不超过 cwnd_gain×BDP，因此带宽下降后 inflight 数据包不会无限增长，而是保持在一个固定值，在图中表现为 40 秒 ~ 42 秒之间的一条水平线。从 42 秒开始，之前的 BtlBw 最大值滑出了采样窗口。BBR 根据过去一段时间重新计算 BtlBw 的值，并使用这个重新计算的 BtlBw 来调整发送速率。因此此时发送速率会急剧下降，inflight 数据包数量和 RTT 也随之逐渐下降，最终达到稳定状态。

4.3.4 存在的问题

公平性问题：当 BBR 算法与传统的基于丢包的算法共存时，BBR 流量可能占用大部分带宽，导致其他流量的带宽分配不公平。
对 RTT 的依赖性：BBR 算法依赖往返时间（RTT）来估计带宽。然而，在某些网络环境中，RTT 可能会大幅波动，这可能会影响 BBR 的性能。
长尾效应：当网络流量减少时，BBR 的带宽估计可能滞后于实际情况，可能继续以过高的速率发送数据，从而引起网络拥塞。这种情况只有在 BBR 的带宽估计下降到适当水平时才会改善。

5 参考资料

[1] “A Comparative Analysis of TCP Tahoe, Reno, New-Reno, SACK and Vegas.”

[2] S. Floyd, M. Handley, and J. Padhye, “A comparison of equation-based and AIMD congestion control,” 2000.

[3] “BBR: Congestion-Based Congestion Control - ACM Queue.” Accessed: Dec. 31, 2023. [Online]. Available: https://queue.acm.org/detail.cfm?id=3022184

[4] L. Xu, K. Harfoush, and I. Rhee, “Binary Increase Congestion Control for Fast, Long Distance Networks”.

[5] V. Jacobson, “Congestion Avoidance and Control”.

[6] L. Xu, S. Ha, I. Rhee, V. Goel, and L. Eggert, “CUBIC for Fast and Long-Distance Networks,” Internet Engineering Task Force, Request for Comments RFC 9438, Aug. 2023. doi: 10.17487/RFC9438.

[7] S. Ha, I. Rhee, and L. Xu, “CUBIC: a new TCP-friendly high-speed TCP variant,” SIGOPS Oper. Syst. Rev., vol. 42, no. 5, pp. 64–74, Jul. 2008, doi: 10.1145/1400097.1400105.

[8] S. Floyd, “HighSpeed TCP for Large Congestion Windows,” Internet Engineering Task Force, Request for Comments RFC 3649, Dec. 2003. doi: 10.17487/RFC3649.

[9] V. R. P. DRAFT, “Modifying TCP’s Congestion Control for High Speeds,” 2002.

[10] A. Gurtov, T. Henderson, and S. Floyd, “The NewReno Modification to TCP’s Fast Recovery Algorithm,” Internet Engineering Task Force, Request for Comments RFC 3782, Apr. 2004. doi: 10.17487/RFC3782.