AIMD 加性增 乘性减算法

一、从一个常见的运维难题说起

假设你正在运营一个分布式限流系统，全公司上百个服务都要经过你分配的"带宽配额"。预算就这么多，但每个服务的真实需求你事先不清楚——有的服务平时风平浪静，促销时流量能翻 10 倍；有的服务每月稳定增长 30%。

你会怎么分配这些带宽？

• 分配固定配额：结果几乎是灾难——资源浪费和争抢同时发生。
• 让业务方报需求：这种"自报家门"在 KPI 面前几乎一定会虚报，最后仍然会把系统打爆。
• 让业务方主动试：先少申请一点，发现不够再加。这种"摸着石头过河"的思路，恰恰是 TCP 拥塞控制的核心。

30 多年前，Van Jacobson 在设计 TCP 拥塞控制时面对的是同一个问题：网络（链路）的带宽是共享资源，发送方不知道链路的当前容量，也不知道有多少其他发送方在抢资源。他必须设计一个让所有发送方在不知道对方存在的情况下，依然能公平、高效地共享链路的算法。

这个算法的名字叫 AIMD：Additive Increase Multiplicative Decrease，加性增 / 乘性减。

它不仅是 TCP 的基石，也是几乎所有"分布式自适应资源分配"问题的通用解法。今天我们就把它彻底拆开。

二、先说结论

AIMD 的核心规则只有两条，所有其他特性都由这两条推出来：

• 加性增（Additive Increase）：当网络顺畅（未检测到拥塞）时，每个发送方把自己的窗口（可以理解为"占用的带宽"）线性增加，每经过一个 RTT 增加 1 个 MSS（Maximum Segment Size）。
• 乘性减（Multiplicative Decrease）：当检测到拥塞（一般是丢包）时，每个发送方把自己的窗口比例缩减，典型做法是直接砍半。

形式化表示：

$$ w(t+1) = \begin{cases} w(t) + a, & \text{无拥塞} \ w(t) \cdot b, & \text{检测到拥塞} \end{cases} $$

其中 $a > 0$ 是加性增量，$b \in (0, 1)$ 是乘性因子。TCP 的经典取值是 $a = 1$（每 RTT 加 1 MSS），$b = 0.5$（丢包时窗口减半）。

就这两条规则，已经能保证一组并发的发送方在任意初始状态下，最终收敛到所有链路带宽的公平共享。 这是 1989 年 Chiu 和 Jain 在论文《Analysis of the increase and decrease algorithms for congestion avoidance in computer networks》中证明的。

三、为什么这套规则能工作？

要理解 AIMD 的精妙，我们不妨反过来想——如果不使用 AIMD，会出现什么问题？

3.1 四种候选策略的对比

直觉上为什么 AIMD 是对的？它的两段规则在几何上互相配合：

• 加性增：所有发送方沿着"平等的斜率"往上爬，谁也不比谁快。这避免了"赢家通吃"——如果大家都用乘法增，初期多吃一点的窗口会越来越大，最后少数发送方霸占链路。
• 乘性减：当链路撑不住、大家被迫"回血"时，回得多吃的少。窗口比例缩小的结果，是已占用带宽多的发送方绝对值上让出更多。再叠加加性增的同起跑线效果，几轮循环后带宽分配就均等了。

3.2 锯齿波形：公平与效率的"呼吸"

把多个发送方放在同一个瓶颈链路上观察，AIMD 会形成著名的锯齿波形（sawtooth）：

窗口
 (W)
  ^
  |    /\        /\
  |   /  \      /  \
  |  /    \    /    \
  | /      \  /      \
  |/        \/        \
  +-----------------------> 时间
              丢包

每个发送方都在做同样的事：缓慢上升 → 撞到瓶颈 → 减半 → 再上升。但因为减半是按比例的，所以：

• 占用带宽多的发送方减半后让出绝对值更大；
• 占用带宽少的发送方减半后让出得少；
• 重新线性增长时大家的增长量相同。

多轮之后，所有发送方的窗口值会越来越接近，最终都收敛到链路的"公平份额"：$W_{fair} = C / n$（$C$ 是链路带宽，$n$ 是发送方数量）。

3.3 Chiu-Jain 的不可能性结论

更严谨地说，Chiu 和 Jain 1989 年的论文给出了分布式拥塞控制要满足的四个性质：

1. 效率（Efficiency）：最终系统工作在瓶颈链路的最大容量附近；
2. 公平（Fairness）：所有发送方获得相同的带宽份额；
3. 分布式（Distributed）：每个发送方只根据本地信息决策；
4. 收敛（Convergence）：从任意初始状态出发，系统最终稳定。

他们的核心定理是：在只使用"增"和"减"两种操作、且不对发送方身份做假设的前提下，只有 AIMD 能同时满足这四条。

其他三种组合（AIAD、MIMD、MIAD）都有反例。这是一个不太常见但很重要的事实——它告诉我们：AIMD 不是工程师拍脑袋挑出来的，而是数学上"唯一正确"的选择。

四、AIMD 在 TCP 里的真实形态

理论很优美，但在 TCP 协议里，AIMD 是怎么落地的？

4.1 三个关键变量

在 TCP 发送方眼里，需要维护两个核心状态：

• cwnd（congestion window，拥塞窗口）：发送方认为自己可以发出去但还没收到 ACK 的最大数据量（以 MSS 为单位）；
• ssthresh（slow start threshold，慢启动阈值）：cwnd 处于"慢启动"还是"拥塞避免"的临界点。

发送方实际能发的窗口是 min(cwnd, rwnd)，其中 rwnd 是接收方通告的接收窗口。我们只关心 cwnd 这部分。

4.2 慢启动（Slow Start）

TCP 连接刚建立时，cwnd 设为 1 MSS。然后每收到一个 ACK，cwnd 就加 1 MSS。这意味着每经过一个 RTT，cwnd 翻倍——这是指数增长，不是线性增长。

为什么要从一个很小的值开始？因为发送方不知道路径容量。先快速试探到接近瓶颈，再切换到缓慢增长，是一个稳妥的策略。

4.3 拥塞避免（Congestion Avoidance）

当 cwnd 达到 ssthresh，就进入"拥塞避免"阶段。这里开始执行 AIMD：

• 加性增：每收到一个 ACK，cwnd 增加 $1/cwnd$ 个 MSS。直观地说，每个 RTT 净增加 1 MSS——这就是线性增长。
• 乘性减：检测到丢包（通常是三个重复 ACK 触发 Reno 快速重传，或者重传超时触发 Tahoe），ssthresh 更新为 cwnd / 2，cwnd 减半。

4.4 整体流程

                        检测到丢包
            ┌─────────── 减半 ──────────┐
            ▼                            │
+--- 慢启动 ---+        +--- 拥塞避免 ---+
| cwnd 翻倍/RTT |  → ssthresh  → 每 RTT 加 1 MSS
|  cwnd < ssthresh|      |
+----+----+----+        +----+----+----+
     指数增长              线性增长

关键细节：慢启动是指数增长，不是 AIMD 的加性增。经典 TCP 实际上是「指数增 + 乘性减」的混合体，AIMD 只在「拥塞避免」阶段上场。但慢启动只占整个连接生命周期的极短时间，长期看系统的收敛行为由 AIMD 主导。

4.5 几个历史变体

这是一个有意思的演进：TCP 一直在试图突破 AIMD 的天花板。但要付出代价。CUBIC 在高速网络中表现更好，但多流并发时不一定收敛到公平（这是 BBR 也面临的问题）。所以在数据中心里，**DCTCP（基于 ECN 标记而不是丢包做拥塞信号）**这种简化版 AIMD 反而更受欢迎。

五、代码实现：一个最小可用的 AIMD 仿真

光说不练假把式。我们用 Go 写一个最小可用的 AIMD 仿真，看两个发送方如何在共享瓶颈链路上收敛。

// AIMD 仿真：N 个发送方共享一个带宽为 C 的瓶颈链路
type Sender struct {
    cwnd float64 // 当前窗口（单位：MSS）
}

// OnAck 每收到一个 ACK 触发：每个 RTT 净增 1 MSS
func (s *Sender) OnAck() {
    s.cwnd += 1.0 / s.cwnd
}

// OnLoss 丢包时触发：窗口减半
func (s *Sender) OnLoss() {
    s.cwnd *= 0.5
}

func simulate(C float64, senders []*Sender, rounds int) {
    for round := 0; round < rounds; round++ {
        total := 0.0
        for _, s := range senders {
            total += s.cwnd
        }
        // 超过瓶颈带宽则视为拥塞，所有发送方同时减半
        if total > C {
            for _, s := range senders {
                s.OnLoss()
            }
        } else {
            for _, s := range senders {
                s.OnAck()
            }
        }
    }
}

跑一下：两个初始窗口分别为 1 和 8 的发送方，瓶颈带宽 10：

s1 := &Sender{cwnd: 1.0}
s2 := &Sender{cwnd: 8.0}
simulate(10, []*Sender{s1, s2}, 50)
fmt.Printf("s1: %.2f, s2: %.2f, sum: %.2f\n",
    s1.cwnd, s2.cwnd, s1.cwnd+s2.cwnd)
// 几十轮后两个发送方的窗口都会稳定在 5 附近（即 10/2 = 公平份额）

可以试着改改参数观察：

• 如果把 OnLoss 改成 cwnd -= 1（AIAD），曲线会永远在过载和欠载之间震荡；
• 如果把 OnAck 改成 cwnd *= 1.1（MIMD），这两个发送方会以指数级差距拉开；
• 这两种都不是我们想要的。

如果你想玩得更深，可以加一个可视化：把每轮的窗口值画出来，能直观看到锯齿波形。

六、AIMD 之外：为什么它是分布式资源分配的"通用解"

AIMD 不只是 TCP 的私货。在很多**「多方共享有限资源，事先不知道对方存在」**的场景里，工程师都会自发地采用 AIMD 模式。

6.1 自适应限流里的 AIMD

回到开头的场景。Sentinel、Dubbo 的自适应限流，本质都是 AIMD 的变体：

顺风时：并发上限 + α（加性增）
过载时：并发上限 × 0.5（乘性减）

Sentinel 的"冷启动"（Warm-Up）还引入了滑动窗口估算 QPS，动态调整 α，本质是把"加性增"换成与当前负载相关的自适应增速。

6.2 视频流媒体的带宽探测

YouTube、Netflix 的 ABR（Adaptive Bitrate）播放器，在播放过程中不断探测可用带宽——

• 下载顺利 → 试探更高画质（加性增）；
• 缓冲即将耗尽 → 降回低画质（乘性减）。

视频领域的顺口溜叫 “buffer-based” 或 “rate-based” ABR，但它们的反馈回路本质都是 AIMD。

6.3 分布式系统的负载均衡

早期的 gRPC 客户端负载均衡、Twitter 的 ADQ（Adaptive Distributed Quota），都让每个客户端自探测后端的承载能力，本质也是 AIMD。

特别有意思的是 BGP 路由震荡抑制：路由器从丢包中学到"某条路径有问题"，把它的优先级乘性降低；路径恢复后慢慢加回来——和 AIMD 的精神完全一致。

6.4 加密货币的难度调整

比特币的难度调整看起来像 AIMD 的"反"——挖矿算力上升时，难度加性增（每 2016 个区块调整一次），但当算力下降时，难度乘性减（条件更宽松）。它选的就是 AIAD 吗？稍微有点特殊：比特币希望"维持稳定的出块时间"，并不追求多个矿工之间的公平，所以选择不完全照搬 AIMD。

这一节想说明：AIMD 的「加性增 乘性减」模式，是一种分布式资源分配的通识，跨越了 TCP、限流、流媒体、路由协议、区块链等多个领域。

七、AIMD 的局限与演进

AIMD 不是银弹。它有几个公认的缺陷：

1. 锯齿波形本身就是浪费

AIMD 永远在"撑满链路 → 丢包 → 减半"的循环里打转。理想情况下，链路利用率只有 75%（平均在 50% 和 100% 之间）。在数据中心这种寸土寸金的环境里，这个浪费不可接受。

2. 延迟高，反馈慢

AIMD 依赖"丢包"作为拥塞信号。但在高速网络中，丢包往往发生在缓冲区已经溢出之后——此时排队延迟早已爆炸。BBR、HPCC 这种"基于模型"的拥塞控制，就是想跳出"丢包即拥塞"的假设。

3. 公平但低效

AIMD 给所有发送方相同份额，但不同流的 RTT 差异巨大时，短 RTT 流会快速循环"增-减"，而长 RTT 流慢得多——结果就是带宽分配倾向于 RTT 较小的流（这被称为 ACK clock bias）。

4. 难以适配新兴场景

QUIC 把拥塞控制从内核搬到用户态，机器学习的 LC-RL、DRL-CC 试图用神经网络替代硬编码规则——但实证上这些"AI 拥塞控制"在公网表现并不稳定，AIMD 配合 CUBIC 仍然是 TCP 的事实标准。

八、小结

AIMD 是分布式系统设计里的"老古董"，但也是最经得起时间检验的算法之一。它的力量在于用最简单的两条规则（线性增、比例减），在完全无中心协调的情况下做到全局资源的最优分配。

它的核心要义可以浓缩成三句话：

• 加性增保证公平：所有玩家沿着同一个斜率往上爬，初始差距不会持续放大；
• 乘性减保证效率：过度使用时按比例回血，链路容量被快速释放；
• 组合保证收敛：Chiu-Jain 定理证明，这是唯一能同时满足效率 + 公平 + 分布式 + 收敛的组合。

下次你设计任何"多方共享有限资源"的系统时，不妨先问一句：这个场景，能用 AIMD 吗？