拥塞控制设计

基于主机的算法概述

大多数基于主机的算法遵循相同的总体思路，差异主要体现在三个关键的选择点上。

每个源端会反复循环执行以下逻辑：尝试以速率 R 发送一段时间。然后，判断：在这段时间内是否经历了拥塞？如果是，则降低 R；如果否，则提高 R。

其中一个缺失的环节是：初始发送速率应该设为多少？我们需要某种方法来选择初始速率 R。

三个关键选择点是：如何选择初始速率？如何检测拥塞？每次应该增加或减少多少速率？

检测拥塞

发送方如何检测网络是否拥塞？有两种常见方法。

发送方可检查数据包丢失情况。这是 TCP 常用的方法。这种方法的优点是信号明确：每个数据包要么被标记为丢失（超时或重复确认），要么未丢失。此外，TCP 为了重传数据包已经会检测丢失的数据包，因此我们无需重新实现这一功能。

但这种方法也有缺点：有时数据包丢失是由于损坏（校验和错误），而非拥塞。事实上，当链路不拥塞但数据包频繁损坏时，TCP 会产生误判并表现不佳。此外，TCP 还可能被数据包重排序所干扰：一个迟到的数据包可能会被误判为丢失。

这种方法的另一个主要缺点是，拥塞检测具有滞后性。当数据包开始被丢弃时，路由器队列已经满了，数据包也已经出现延迟。

除了检查数据包丢失，发送方还可以通过检查数据包延迟来检测拥塞。发送方可测量发送数据包到收到该数据包的确认之间的时间。如果发送方发现延迟在增加，这可能是拥塞的迹象。

历史上，精确测量延迟被认为是困难的。数据包延迟会因队列大小和其他流量而变化。多年来，基于延迟的算法并未得到广泛应用，但近年来，谷歌的 BBR 协议（2016 年）表明基于延迟的算法是可行的，一些服务（如谷歌服务）已经采用了基于延迟的算法。

确定初始速率

当连接刚开始时，我们必须确定一个初始发送速率。我们可以通过一个探测过程来获取初始速率，即尝试几种不同的速率以估计可用带宽。

我们希望这个探测过程是安全的，因此应该从较低的速率开始。我们不希望立即向网络中发送大量数据包。

同时，为了提高效率，我们希望探测过程能快速发现可用带宽。如果探测过程耗时过长，我们就浪费了本可以以最佳速率发送数据包的时间。例如，假设我们每 100ms 将速率增加 0.5 Mbps，直到检测到拥塞（丢失）。如果可用带宽是 1 Mbps，探测阶段需要 2 次迭代 = 200ms。但如果可用带宽是 1 Gbps=1000 Mbps，那么探测阶段需要 2000 次迭代 = 200 秒才能提升到合适的速率，这显然太久了。互联网的链路速度差异很大，因此这两种情况在现实中都可能出现。

为了支持慢启动但快速提升，我们每次将带宽乘以一个因子来增加（而不是 additive 增加）。这种方案称为慢启动，尽管这个名称可以说并不直观。在慢启动中，我们从一个几乎肯定远低于实际带宽的小速率开始。然后，我们以指数方式增加速率（例如，每次翻倍），直到遇到丢失。安全的速率是遇到丢失之前的那个速率（我们不希望使用出现丢失时的速率）。形式上，如果在速率 R 时发生丢失，那么安全速率是 R/2。

调整：应对拥塞

回想一下，在探测阶段之后，我们需要不断调整带宽，因为网络本身在变化，可用带宽并非恒定不变。

最后一个选择点是：检测到拥塞时应该降低多少带宽，未检测到拥塞时应该增加多少带宽。

我们的决策将决定主机适应可用带宽变化的速度，进而决定带宽的利用效率。如果我们需要很长时间来适应变化并找到合适的速率，我们会在很长一段时间内以次优带宽运行，这是低效的。适应缓慢还可能导致公平性问题。例如，如果我正在使用链路的全部带宽，而此时另一个连接被建立，我需要快速调整并降低我的带宽以共享链路。

回想一下，拥塞控制算法的主要目标是效率（充分利用所有可用带宽）和公平性（连接平等共享带宽）。我们需要选择能够实现这两个目标的增减规则。

我们可以选择哪些规则？从宏观上看，我们可以选择快速变化或缓慢变化。更具体地说，快速变化是乘法式的，例如每次迭代将速率翻倍或减半。缓慢变化是加法式的，例如每次迭代将速率加 1 或减 1。这些选择构成了四种可能的组合：

AIAD：加性增加，加性减少

AIMD：加性增加，乘性减少

MIAD：乘性增加，加性减少

MIMD：乘性增加，乘性减少

在这四种组合中，事实证明 AIMD（缓慢增加，快速减少）是实现效率和公平性的最佳选择。

直观地说，AIMD 是合理的选择，因为发送过多比发送过少更糟糕。当我们的速率过高时，会导致拥塞，数据包会被丢弃。当我们的速率过低时，虽然没有充分利用带宽，但至少不会导致拥塞。

AIMD 会导致这样的行为：当没有拥塞时，我们缓慢增加速率，逐渐接近最大带宽。然后，一旦我们超过最大带宽并检测到拥塞，就会迅速降低速率。这样，我们大部分时间都在速率过低的状态（这是更可取的），而当速率过高时（不可取），我们会迅速降低以避免拥塞。

调整：模型

为什么 AIMD 是实现效率和公平性的最佳选择？让我们进行更详细的分析。

首先，注意到这四种选择在实现效率方面都表现不错。当我们低于最优速率（未拥塞）时增加速率，当我们高于最优速率（拥塞）时降低速率，从长远来看，我们的速率应该始终在最优速率附近波动。

然而，事实证明，在这四种选择中，AIMD 是唯一能实现公平性的选择。为了理解原因，让我们考虑一个简单的模型：两个连接通过一条容量为 C 的链路传输数据。两个连接的发送速率分别为 X1 和 X2。我们知道，如果 X1+X2 大于 C，网络就会拥塞；如果 X1+X2 小于 C，网络则未被充分利用。

为了实现效率，我们希望链路被充分利用，即 X1+X2 = C。为了实现公平性，我们希望 X1 = X2，以便两个连接平等共享容量。

为了可视化可能的情况，考虑一个二维图表，x 轴是 X1（用户 1 的速率），y 轴是 X2（用户 2 的速率）。图表上的每个点都代表一种可能的场景，即每个用户以特定速率发送数据。

假设 C=1。为了实现最大效率，我们希望 X1+X2 = 1。我们可以在图表上画出这条线。这条线上的每个点都充分利用了可用带宽。

我们知道，当 X1+X2 大于 1 时，网络拥塞。在图表上，这个不等式表示的是这条线以上的半平面。我们也知道，当 X1+X2 小于 1 时，网络未被充分利用，这对应于这条线以下的半平面。这意味着，这条线以上的所有点都代表拥塞状态，这条线以下的所有点都代表未充分利用状态。

为了实现公平性，我们希望 X1 = X2。我们也可以画出这条线。这条线上的每个点都代表一种公平状态，即两个用户使用相同的带宽。不在这条线上的任何点都是不公平的。

理想状态出现在两条线的交点，即 X1 = X2 = 0.5。这个点同时在两条线上，因此既公平又高效。

点（0.2, 0.5）是低效的，因为我们只使用了 0.7 的带宽。从图形上看，我们在效率线下方。点（0.7, 0.5）是拥塞的，因此在效率线上方。点（0.7, 0.3）是高效的（在效率线上），但不公平（不在公平线上）。

回想一下，在我们的动态调整算法中，每个发送方都独立运行相同的算法来确定自己的速率。这意味着，如果两个用户检测到网络未被充分利用，两者都会以相同的方式（根据我们选择的规则，加性或乘性）增加速率。同样，如果两个用户检测到拥塞，两者都会以相同的方式降低速率。

如果两个用户都加性地增加或降低速率，会发生什么？如果两个用户都通过加 b 来增加速率，状态（x1, x2）将变为（x1+b, x2+b）。如果两个用户都通过减 a 来降低速率，状态（x1, x2）将变为（x1-a, x2-a）。

在图表上，如果我们进行加性变化，代表我们状态的点会沿着斜率为 1 的线移动。

如果两个用户都乘性地增加或降低速率，会发生什么？乘以 c 会将（x1, x2）转换为（cx1, cx2），除以 d 会将（x1, x2）转换为（x1/d, x2/d）。

在图表上，如果我们进行乘性变化，代表我们状态的点会沿着斜率为 x2/x1 的线移动。换句话说，这条线是连接（x1, x2）和原点（0, 0）的线。

现在，我们可以将这个模型应用到四种增减选择中，看看它们是否会导致点接近或远离公平线。我们的目标是，随着我们调整速率，点会接近公平线。

调整：AIAD 动态

考虑每次增加时加 1，每次减少时减 2。假设容量 C=5。那么，从给定的起点开始，我们的点会如下移动：

X1=1，X2=3（起点，比 5 小 4，增加）

X1=2，X2=4（比 5 大 6，减少）

X1=0，X2=2（比 5 小 2，增加）

X1=1，X2=3

我们回到了起点！我们最初的分配是不公平的，经过几次迭代后，我们又回到了同样不公平的分配。

事实上，如果我们看 X1 和 X2 之间的差值（公平差值为 0），每次迭代的差值都是相同的（2）。迭代并没有使我们的分配变得更公平或更不公平。

我们可以从图形上看到这种行为。从给定的起点开始，如果我们加性地增加和减少，我们将始终沿着斜率为 1 的线移动，永远不会更接近公平线。

不过需要注意的是，我们的点会围绕效率线振荡，这是符合预期的。四种选择都会有这种行为。

我们也可以从代数上看到这种行为。假设 X1 和 X2 相差 5（不公平分配）。如果我们给 X1 和 X2 加上相同的数，得到的 X1’ 和 X2’ 仍然相差 5（同样不公平）。如果我们从两者中减去相同的数，情况也是如此。

总之，这种方法无法缩小公平差距。如果初始分配是不公平的，它将一直保持不公平。

你可能会问：如果我们给 X1 多加一些（例如 + 2），给 X2 少加一些（例如 + 1）会怎样？请记住，我们的分布式方法意味着每个主机都在运行相同的算法。实际上，主机也无法知道相对于其他主机应该增加多少。

调整：MIMD 动态

考虑通过翻倍来增加速率，通过除以 4 来减少速率。同样，容量 C=5。从给定的起点开始，前几次迭代如下：

X1=0.5，X2=1（比 5 小 1.5，增加）

X1=1，X2=2（比 5 小 3，增加）

X1=2，X2=4（比 5 大 6，减少）

X1=0.5，X2=1

我们再次回到了起点，公平性没有任何改善！

我们可以从图表上看到这种行为。当我们乘性地增加或减少速率时，我们沿着连接该点和原点的线移动，永远不会更接近公平线。

从代数上看，考虑 X2 与 X1 的比率，即 X2/X1（公平比率为 1）。在上面的例子中，比率始终是 2，即 X2 的带宽始终是 X1 的两倍。即使我们将 X1 和 X2 都乘以或除以一个常数因子，这个比率也保持不变。我们的调整无法使我们更接近 1 这个公平比率。

调整：MIAD 动态

这个稍微复杂一些。考虑通过翻倍来增加速率，通过减 1 来减少速率。当 C=5 时，前几次迭代如下：

X1=1，X2=3（比 5 小 4，增加）

X1=2，X2=6（比 5 大 8，减少）

X1=1，X2=5（比 5 大 6，减少）

X1=0，X2=4（比 5 小 4，增加）

X1=0，X2=8

此时，X1 的带宽为零。每次我们通过翻倍来增加速率时，X1 的带宽仍然为零。我们实际上创造了最不公平的情况：X2 拥有所有带宽，而 X1 一无所有。

更一般地说，如果初始分配是不公平的，MIAD 会使分配更加不公平，最终会达到一个人拥有所有带宽而另一个人一无所有的状态。

从代数上可以看出，考虑 X1 和 X2 之间的差距。当我们通过翻倍来增加速率时，差距也会翻倍，从（X2 - X1）变为（2X2 - 2X1）=2（X2 - X1）。但是，当我们从 X1 和 X2 中都减去 1 时，差距保持不变。差距要么增大，要么保持不变，经过足够多次的增减迭代后，差距会达到最大的不公平状态（一个人永远拥有零带宽）。

调整：AIMD 动态

最后，考虑通过加 1 来增加速率，通过减半来减少速率。当 C=5 时，前几次迭代如下：

X1=1，X2=2（比 5 小 3，增加）

X1=2，X2=3（5 不大于 5，增加）

X1=3，X2=4（比 5 大 7，减少）

X1=1.5，X2=2（比 5 小 3.5，增加）

X1=2.5，X2=3（比 5 大 5.5，减少）

X1=1.25，X2=1.5（比 5 小 2.75，增加）

X1=2.25，X2=2.5（比 5 小 4.75，增加）

X1=3.25，X2=3.5（比 5 大 6.75，减少）

X1=1.625，X2=1.75（比 5 小，增加）

X2=2.625，X2=2.75

我们可以看到 X1 和 X2 越来越接近，实际上，它们正在接近公平分配 X1=X2=2.5。

从代数上看，我们可以发现 X1 和 X2 之间的差距在减小。具体来说，当我们给两个数都加上一个常数时，差距保持不变。但是，当我们将两个数都减半时，差距也会减半，从（X1 - X2）变为（X1/2 - X2/2）=（X1 - X2）/2。随着我们交替进行增加和减少，差距会不断减半并趋近于 0。

我们也可以从图形上看到这一点。当我们乘性地减少时，我们沿着通过原点的线移动。这条线朝向公平线倾斜，沿着这条线向下移动意味着我们在接近公平线。和之前一样，加性增加不会使我们更接近公平线，因为我们沿着斜率为 1 的线（与公平线平行）移动。但关键的认识是，增加也不会使我们离得更远。我们的两种操作要么使我们更接近，要么既不接近也不远离。经过多次迭代后，我们的点会慢慢靠近公平线。

总之：AIAD 和 MIMD 会保持不公平性，不会向公平性改进。MIAD 会加剧不公平性，而 AIMD 会趋向于公平性。