跳转至

ABC: A Simple Explicit Congestion Controller for Wireless Networks

(1) 研究背景与痛点

  • 无线网络拥塞控制的挑战: 无线链路的容量会随时间快速变化, 传统的端到端 (End-to-End) 拥塞控制 (如 Cubic, BBR) 和主动队列管理 (AQM, 如 CoDel) 很难同时兼顾高吞吐量和低延迟

  • 现有显式控制方案的局限:

    • 现有的显式拥塞控制 (如 XCP, RCP) 主要是为固定容量链路设计的, 在随时间变化的无线链路上控制算法表现不佳
    • 此外, 它们需要大幅修改数据包报头, 路由器和终端设备, 导致在互联网中难以部署
积累整理: E2E-CCA 与 AQM

拥塞控制本质上要回答一个问题: 发送方该以多快的速率发数据? 解决这个问题有两个不同的 "站位":

  • 端到端 (End-to-End) 拥塞控制

    • 站在发送端, 通过观察网络反馈 (丢包, 延迟等) 来调整自己的发送速率
    • CUBIC 和 BBR 都属于这一类, 它们是 TCP 拥塞控制算法, 跑在主机的传输层

  • 主动队列管理 (AQM)

    • 站在中间的路由器/交换机上, 通过主动管理队列中的数据包 (比如提前丢弃或标记) 来向端系统 "发信号", 防止队列被填满
    • CoDel 就是其中一种

两者是互补关系, 不是替代关系!

(1) 积累: CUBIC

CUBIC 是 Linux 默认的 TCP 拥塞控制算法 (从 2.6.19 内核开始), 也是目前互联网上使用最广泛的算法之一.

核心思路: CUBIC 是一种 基于丢包 (loss-based) 的算法. 它用一个 三次函数 (cubic function) 来控制拥塞窗口 (cwnd) 的增长, 这也是名字的由来.

具体来说, 它的窗口增长模型是:

\[W(t) = C \cdot (t - K)^3 + W_{\max}\]

其中 \(W_{\max}\) 是上次发生丢包时的窗口大小, \(K\) 是从当前窗口恢复到 \(W_{\max}\) 所需的时间, \(C\) 是一个常数.

直觉理解: 想象一条 S 型曲线. 离上次丢包点的窗口值还远时, 窗口增长很快 (大胆探测); 接近上次丢包点时, 增长变得非常缓慢 (小心试探); 超过上次丢包点后, 又开始加速增长 (探测新的可用带宽). 发生丢包后, 窗口乘性减小 (通常减到 0.7 倍), 然后重新开始这个过程.

关键特性:

  • 窗口增长只和 时间 有关, 和 RTT 无关, 这让它在高带宽, 高延迟 (长肥管道) 的场景下比传统算法更公平
  • 属于 loss-based, 即 必须等到丢包才知道拥塞了——这意味着它倾向于把路由器的缓冲区填满

(2) 积累: BBR

BBR 是 Google 在 2016 年提出的拥塞控制算法, 代表了一种完全不同的哲学.

核心思路: BBR 是一种 基于模型 (model-based) 的算法. 它不依赖丢包作为拥塞信号, 而是试图持续估计两个关键参数:

  • BtlBw (瓶颈带宽): 路径上最慢那一跳的带宽
  • RTprop (最小往返传播延迟): 没有排队延迟时的纯传播延迟

理想的发送速率就是: 发送窗口 = BtlBw × RTprop.

这个点被称为 Kleinrock 最优操作点 —— 此时链路被充分利用, 但缓冲区里没有多余的排队数据!

工作方式 (BBRv1 简化版): BBR 在四个状态之间循环:

  1. Startup — 类似慢启动, 指数增长, 快速探测带宽上限
  2. Drain — 把 Startup 阶段多灌进缓冲区的数据排空
  3. ProbeBW — 稳态阶段, 周期性地小幅增减发送速率来跟踪带宽变化
  4. ProbeRTT — 偶尔主动降低发送量来测量最新的最小 RTT

(3) 积累: 主动队列管理方案 (AQM)

问题背景:

传统路由器使用 tail-drop (尾丢弃) 策略: 队列满了才丢包!

这会导致两个问题:

  1. bufferbloat (缓冲区膨胀), 即数据包在大缓冲区中排队很久, 延迟飙升但没有丢包信号
  2. 全局同步, 多条 TCP 流同时丢包, 同时降速, 同时恢复, 导致带宽利用率呈锯齿波动

AQM 的思路:

路由器不等队列满, 而是 提前, 主动地 丢弃或标记 (ECN) 数据包, 让端系统尽早感知到拥塞, 从而避免队列过长

几个典型的 AQM 算法:

  1. RED (Random Early Detection)

    • 最早的 AQM
    • 根据平均队列长度, 以一定概率随机丢包. 队列越长, 丢包概率越高. 但它的参数很难调, 实际部署效果不稳定

  2. CoDel (Controlled Delay)

    • 它不看队列长度, 而是看 数据包在队列中的逗留时间 (sojourn time)
    • 如果一个数据包的排队延迟持续超过阈值 (默认 5ms) 达到一段时间 (默认 100ms), 就开始丢包, 且丢包间隔按 \(1/\sqrt{n}\) 递减 (越来越激进)
    • CoDel 的优点是几乎不需要手动调参

  3. fq_codel (Fair Queuing + CoDel)

    • 核心: 把流量按 flow 分到不同的子队列, 每个子队列独立运行 CoDel
    • 这样既控制了延迟, 又保证了流间的公平性. 这是目前 Linux 和很多家用路由器的默认队列调度算法

(2) ABC (Accel-Brake Control) 协议机制

  • 单比特反馈: ABC 路由器根据对当前链路速率的测量, 将每个数据包用 1 个比特标记为 "加速 (accelerate)" 或 "刹车 (brake)"

  • 发送端响应:

    • 收到 "加速" ACK 时, 发送端将拥塞窗口加一 (针对该 ACK 发送两个数据包)
    • 收到 "刹车" ACK 时, 拥塞窗口减一 (不发送任何数据包)
    • 这使得发送端窗口在一个 RTT 内具备巨大的动态调整范围: 可以降为 0, 也可以直接翻倍

(3) 关键创新点

  • 基于 "出队率 (Dequeue Rate)" 的反馈计算:

    • 现有的显式方案 (如 XCP) 通常比较 "入队率" 和链路容量来生成反馈
    • 而 ABC 则比较数据包从队列离开的 "出队率" 与链路容量
    • 因为 ABC 协议由 ACK 时钟驱动, 当前的出队率能够精确预测一个 RTT 后的未来入队率, 从而更好地匹配无线链路容量的剧烈波动

  • 无线链路速率估计:

    • 针对 Wi-Fi 复杂的 MAC 层聚合调度, 论文提出了一种方法: 通过分离随包数量变化的传输时间与独立的开销时间 (如信道竞争时间), 从而准确预估用户在完全积压 (backlogged) 状态下的真实链路速率

(4) 部署与共存策略

  • 无需修改包头:

    • ABC 重新利用了 IP 协议中现有的 ECN (显式拥塞通知) 比特位来传递加速/刹车信号, 无需定义新的报头

  • 与非 ABC 路由器共存:

    • 发送端维护两个拥塞窗口 (\(w_{abc}\) 和 \(w_{nonabc}\)), 当遇到传统的拥塞节点 (如出现丢包或传统的 ECN 标记) 时, ABC 会受限于较小的 \(w_{nonabc}\) 并表现出类似 Cubic 的行为, 防止引发拥塞

  • 与传统 TCP 流量的公平性:

    • 在 ABC 路由器上, 通过将 ABC 流量和非 ABC 流量分入不同队列, 并基于大小流的真实带宽需求定期进行最大最小公平分配 (Max-Min Fair Allocation) 计算权重, 从而确保公平调度

Introduction

(1) 研究背景与现有方案的局限性

  • 无线链路的挑战: 由于无线链路容量随时间快速变化, 在这些路径上进行拥塞控制非常困难.

  • 现有显式协议的缺陷:

    • 理论上, 显式控制协议 (如 XCP 和 RCP) 能够根据实时链路容量直接指示目标速率, 表现应优于端到端或 AQM 方案
    • 但它们存在两个局限:
      1. 它们专为固定容量链路设计, 在随时间变化的无线链路上算法表现次优
      2. 它们需要对数据包报头, 路由器和终端进行重大修改, 导致在互联网中难以部署

(2) ABC 协议的核心机制与创新

  • 简单的单比特反馈:

    • 论文提出了一种名为 Accel-Brake Control (ABC) 的简单且易于部署的协议
    • 无线路由器根据当前链路速率, 用 1 个比特将每个数据包标记为 "加速 (accelerate)" 或 "刹车 (brake)"

  • 高效的窗口调整:

    • 发送端在收到 "加速" 时将窗口加一 (发送两个数据包), 收到 "刹车" 时窗口减一 (不发送新数据包)
    • 这使得发送端在一个 RTT (往返时间) 内就能实现从降为 0 到窗口翻倍的巨大动态调整范围

  • 基于 "出队率" 的控制算法:

    • 不同于 XCP 等比较 "入队率 (enqueue rate)" 与链路容量的传统方案, ABC 路由器通过比较数据包的 "出队率 (dequeue rate)" 与链路容量来生成标记
    • 因为 ABC 受 ACK 时钟驱动, 当前的出队率能准确预测一个 RTT 后的入队率, 这在容量波动的无线链路上能带来显著的性能提升

(3) 可部署性与兼容性

  • 易于部署: ABC 建立在现有的 ECN (显式拥塞通知) 基础设施之上, 克服了以往显式协议的部署难题, 不需要修改报头格式
  • 后向兼容: 它具有增量部署能力, 当瓶颈是非 ABC 路由器时也能正常运行, 并且能与共享同一瓶颈链路的传统 (非 ABC) 流量良好共存

(4) 主要实验成果概括

作者在商品级 Wi-Fi 路由器上实现了 ABC, 并使用蜂窝网络数据包轨迹进行了仿真. 主要成果如下:

  • 卓越的性能:

    • 在 Wi-Fi 环境中, ABC 在延迟相近的情况下, 吞吐量比 Cubic+Codel 高出 30-40%; 同时其延迟比 BBR 低 2.2 倍
    • 在蜂窝网络路径上, ABC 的吞吐量比 Cubic+Codel 高出 50%

  • 超越传统显式方案:

    • 在模拟实验中, 尽管只依赖单比特反馈, ABC 的 95% 分位数延迟仍比多比特反馈的 XCP 低 2 倍

  • 良好的共存与公平性:

    • ABC 能够与 非 ABC 路由器共存 (遇到 非 ABC 瓶颈时会切换为 Cubic 行为)
    • 且与 非 ABC 流量竞争时非常公平 (平均吞吐量差异在 5% 以内)

Motivation

这一部分主要阐述了无线网络拥塞控制面临的根本难题, 详细分析了现有各类方案的局限性, 并借此引出了设计 ABC 协议的四大核心目标.

(1) Limitations of end-to-end congestion control

alt text

  • 传统基于丢包的方案:

    • 像 Cubic 和 NewReno 这样的传统方案 依赖数据包丢失来推断拥塞 并调整速率
    • 这往往会导致填满缓冲区, 造成巨大的排队延迟, 尤其是在为了避免丢包而设置了深缓冲区的蜂窝网络中表现尤为明显
    • 如 Fig. 1a 所示, Cubic 在模拟的 LTE 链路上虽然利用率高, 但会产生高达 1500 毫秒的极端排队延迟

  • 基于延迟和速率的新方案:

    • 近期提出的 BBR, PCC-Vivace, Copa, Sprout 和 Verus 等方案试图通过 测量 RTT 和收发速率 来更好地估计可用带宽
    • 但在高度变化的链路上, 它们的表现远非理想!
    • 如 Fig. 1b 所示, Verus 在测试中表现出巨大的速率波动, 并伴随较高的延迟

  • 根本挑战:

    • 任何端到端方案都必须完全利用链路并建立队列, 才能有效估计链路容量
    • 当队列为空时 (例如链路容量突然增加后), 它们无法获取可用容量的信息, 必须进行 "盲目" 的速率增长
    • 如果增长过慢会导致吞吐量受损, 过快则会导致超调和高昂的排队延迟

(2) Limitations of active queue management (AQM) solutions

  • 只能发出 "减速" 信号:

    • AQM 方案 (如 RED, PIE 和 CoDel) 能够 在瓶颈链路缓冲区填满前通过 ECN 或丢包发出拥塞信号, 从而有效降低延迟
    • 然而, AQM 方案无法发出 "速率增加" 的信号

  • 导致链路利用率不足:

    • 当链路容量增加时, 发送端仍然必须依赖盲目的速率增加
    • 如 Fig. 1c 所示, Cubic+CoDel 组合虽然将延迟降低了 1 到 2 个数量级, 但在容量增加时会导致链路利用率严重不足

(3) Deployment challenges for explicit congestion control

  • 理论优势:

    • 像 XCP 和 RCP 这样的显式方案由路由器根据对无线链路容量的直接掌握, 为发送端提供多比特反馈
    • 它们明确告诉发送端如何增减速率, 理论上可以在一个 RTT 内快速适应链路变化

  • 实际部署困难:

    • 这些协议 需要对数据包报头、路由器和终端进行重大修改
    • 它们需要新的数据包字段来携带多比特信息
    • 但在实际互联网中, 携带 IP 选项的数据包常被广域网路由器丢弃, 而使用 TCP 选项又会面临中间设备 (middleboxes) 拦截和 IPSec 加密等问题
    • 此外, 与传统路由器和传输协议的共存也是一个严峻挑战

(4) ABC Design Goals

为了克服上述痛点, 论文提出了 ABC 协议的四个核心设计目标:

  • 针对快速变化链路的控制算法:
    • 不同于 XCP 为固定链路设计, ABC 专门针对无线链路的带宽快速波动以及 MAC 层批量传输行为设计了控制算法
  • 无需修改数据包报头:
    • ABC 重新利用了现有的 ECN 位, 通过每包 1 比特的信号序列来表达广泛的动态范围, 精确控制发送端的拥塞窗口
  • 与传统瓶颈路由器共存:
    • 如果路径上的非 ABC 路由器成为瓶颈, ABC 发送端能够忽略来自无线链路的 "加速" 反馈, 确保其发送速率不超过自身在瓶颈链路上的公平份额
  • 与传统传输协议共存:
    • ABC 路由器将 ABC 流量和非 ABC 流量分离到两个队列中, 并使用调度算法确保它们公平共享无线瓶颈链路
  • 优异的综合表现:
    • 如 Fig. 1d 所示, ABC 仅使用单比特反馈, 就能紧密跟踪瓶颈链路的变化, 在保持低排队延迟 (接近 Cubic+CoDel) 的同时, 实现了接近 100% 的高利用率

Design

  • 基于窗口与单比特反馈:

    • ABC 是一种基于窗口的拥塞控制协议
    • 路由器根据计算出的目标速率, 在每个数据包上设置 1 比特的标记 (加速或刹车), 接收端随后通过 ACK 将该标记传回给发送端

  • 发送端的极简响应:

    • 发送端收到 "加速" 标记时, 拥塞窗口加 1 (即针对该 ACK 发送 2 个包)
    • 收到 "刹车" 标记时, 窗口减 1 (不发新包)
    • 这种极简的单比特反馈经过一个 RTT 的累积, 能让窗口实现从 0 到翻倍的巨大动态调整

  • 路由器目标速率 (Target Rate) 设定:

    • 路由器结合链路容量和排队延迟来设定目标速率
    • 当延迟低时, 目标速率设定为略低于链路容量; 当延迟超过设定阈值时, 则主动降低目标速率以快速排空队列

  • 基于 "出队率" 的标记算法 (核心创新):

    • 不同于以往协议依赖 "入队率 (enqueue rate)", ABC 路由器根据当前的 "出队率 (dequeue rate)" 来计算需要标记 "加速" 的数据包比例
    • 因为在 ACK 时钟驱动下, 当前的出队率能精准预测未来的入队率
    • 如 Fig. 2 所示, 采用出队率进行计算能让 ABC 更准确地跟踪链路容量, 避免严重的排队延迟
    • alt text

  • 多瓶颈链路协同:

    • 数据包最初由发送端统一标记为 "加速", 路径上的 ABC 路由器只能将 "加速" 降级为 "刹车", 绝对不能反向操作
    • 这保证了整条链路上最小的瓶颈速率起决定性作用

  • 引入加性增保障公平性:

    • 纯粹的乘性增减规则无法保证多条流之间的公平性 (如 Fig. 3a 所示)
    • 因此, ABC 在发送端引入了每 RTT 增加 1 个数据包的加性增 (Additive Increase) 机制, 构成 MAIMD 模型, 从而完美收敛到公平分配状态 (如 Fig. 3b 所示)
    • alt text

  • 系统稳定性:

    • 只要参数配置合理 (如排空队列的时间常数不远小于 RTT), ABC 协议的控制环路在理论上被证明是全局渐进稳定的
相关工作方案 核心机制与特点 主要局限性 / 缺点 与 ABC 的对比 / ABC 的优势
CQIC & piStream [cite_start]
  • 利用接收端的物理层信息来推断底层的链路容量 [cite: 873].
 [cite_start]
  • 由于基站资源分配过程对接收端不透明, 导致估计不准确 [cite: 874, 876][cite_start].
  • CQIC 仅考虑历史资源使用情况, 而非可用的物理资源 [cite: 875][cite_start].
  • piStream 依赖秒级视频片段下载, 无法应对逐包拥塞控制所需的短时间尺度链路速率变化 [cite: 875].
 [cite_start]
  • ABC 通过直接在基站准确估计链路容量, 从而规避了这些问题 [cite: 877].
VCP [cite_start]
  • 路由器将拥塞状态分类为低, 中, 高, 并通知发送端执行乘性增, 加性增或乘性减 [cite: 878].
 [cite_start]
  • 发送端每 RTT 仅响应一次, 这种粗粒度更新限制了其在时变无线路径上的有效性 [cite: 879, 880][cite_start].
  • 例如, 窗口翻倍可能需要长达 12 个 RTT [cite: 881][cite_start].
  • 与 ECN 不兼容, 导致部署困难 [cite: 882].
 [cite_start]
  • 不同于 VCP, ABC 发送端会对每一个 ACK 做出单独的响应 [cite: 879].
BMCC & MTG [cite_start]
  • BMCC 使用 ADPM 在 ECN 位上将链路负载信息发送至接收端, 并依赖 TCP 选项将反馈中继回发送端 [cite: 883][cite_start].
  • MTG 提议修改蜂窝基站, 使用新的 TCP 选项显式传达链路速率 [cite: 884].
 [cite_start]
  • 这两种方法都无法与 IPSec 加密协同工作 [cite: 885][cite_start].
  • 修改数据包会引发数据包被中间设备 (middleboxes) 静默丢弃的风险 [cite: 885][cite_start].
  • MTG 无法保证单个用户的多条流之间的公平性 [cite: 886][cite_start].
  • BMCC 在与非 BMCC 流共存时同样面临公平性问题 [cite: 886].
 [cite_start]
  • 与 MTG 等方案不同, ABC 能够确保流之间的公平性 [cite: 886].
XCP-b [cite_start]
  • 一种专为容量未知的无线链路设计的 XCP 变体 [cite: 887][cite_start].
  • 路由器利用队列大小来决定反馈信息 [cite: 888][cite_start].
  • 当队列积压时, 通过队列大小的变化计算剩余容量, 并应用 XCP 控制规则 [cite: 889].
 [cite_start]
  • 当队列降至零时, XCP-b 无法估计剩余容量, 只能退化为盲目的固定加性增 [cite: 890][cite_start].
  • 这种盲目增加会导致链路利用率不足以及延迟增加 [cite: 891].
  • (参考下方综合对比)
综合对比
(XCP, RCP, VCP, BMCC, XCP-b)		 [cite_start]
  • 试图将当前的入队率 (current enqueue rate) 与链路容量相匹配 [cite: 892].
 [cite_start]
  • 没有一种方案能够将未来的入队率与链路容量相匹配 [cite: 892].
 [cite_start]
  • ABC 由于能够匹配未来的入队率与容量, 因此在随时间变化的链路上表现优于所有这些先前提出的方案 [cite: 892].