跳转至

Managing Congestion Control Heterogeneity on the Internet with Approximate Performance Isolation

通过近似性能隔离管理互联网中的拥塞控制异构性

(1) 论文概览与核心问题

  • 背景:

    • 当前的互联网运行着多种具有不同性能目标的拥塞控制算法 (CCAs)
    • 例如:
      • CUBIC 旨在填满缓冲区以最大化吞吐量
      • BBR 和 Vegas 则对延迟敏感，力求保持较低的排队延迟

  • 核心冲突:

    • 当这些具有不同“吞吐量-延迟”偏好的算法在同一个传统的网络瓶颈（如 FIFO 队列）中竞争时，往往会导致极大的不公平甚至相互损害
    • 例如: CUBIC 会填满缓冲区导致 Vegas 饿死，或者让 BBR 承受极高的延迟

  • 现有方案的局限性:

    • 公平队列 (Fair Queuing, FQ) 为每个流分配一个独立的队列，能够完美实现性能隔离
      • 但在互联网规模下: 因需要维护庞大的队列数量而缺乏可行性（不具备可扩展性）
    • 而现有的主动队列管理 (AQM), 如 CoDel, 或其他近似 FQ 方案（如 AHAB、SFQ、Cebinae）往往只关注带宽公平性，无法真正隔离不同算法的延迟惩罚

(2) 核心理念: 近似性能隔离

Approximate Performance Isolation

  • 理论洞察:

    • 具有相似"吞吐量-延迟"偏好的算法, 在共享同一个队列时, 能够友好共存并达成它们各自期望的性能目标

  • 解决方案:

    • 无需为每个流分配独立队列，只需将具有相似性能偏好的流分入同一个队列中
    • 用极少量的队列, 就能实现接近完美 FQ 的隔离效果

(3) Santa 系统设计

为了将这一理论付诸实践，作者设计了一个名为 Santa 的实用且可扩展的多队列主动队列管理 (AQM) 系统。其核心机制包含：

  • 老鼠流处理 (Ignoring Mice Flows)：

    • 网络中约 90% 的流是短命的“老鼠流”
    • Santa 将每个流的前 10 个数据包识别为老鼠流，并直接将其送入一个最高优先级的“老鼠队列”，以确保极短的流完成时间 (FCT)

  • 初始队列分配 (Initial Queue Assignment)：

    • 当流的大小超过 10 个数据包后，它会被按权重随机分配到 K 个 Santa 队列中的一个
    • 分配概率与该队列中已有的流的数量成正比
    • 这有助于提高初始分配的准确性和稳定性

  • 动态洗牌与重排 (Flow Shuffling)：Santa 无法直接知道一个流的算法类型，但可以通过观测其 "相对攻击性 (Relative Aggression)" 来推断

    • 系统以固定的时间周期（轮次/Round）对比同一个队列中各个流的缓冲区占用情况
    • 如果一个流比同队列的平均水平激进得多（占用显著更多的带宽/缓冲区，被称为 "naughty"），它会被升级转移到更高序号的队列（与更激进的流竞争）
    • 如果一个流由于抢不到带宽而表现得十分被动（被称为 "nice"），它会被降级转移到较低序号的队列（享受更低的排队延迟）

  • 带宽分配 (Bandwidth Allocation)：

    • Santa 根据每个队列中包含的流的数量，按比例动态分配网络带宽

(4) 原型实现与评估结果

  • 硬件部署：

    • Santa 原型被成功部署在了可编程交换机（Intel Tofino，使用 P4 语言编写数据平面）上，证明了其在硬件上的实际可行性
    • 为了在大规模流量下节省内存，系统使用了 Count-Min Sketch (CMS) 这种概率数据结构来追踪流状态

  • 隔离效果评估：

    • 在 9 个并发长流（CUBIC、BBR、Vegas 各 3 个）的测试中，传统的 FIFO 和现有的 AQM 均未能让各类流达到理想状态，而使用 4 个队列的 Santa 成功实现了与完美 FQ 几乎一致的隔离性能

  • 扩展性与连续性：

    • 实验表明，Santa 提供了一种介于单一 FIFO（1个队列）和完美 FQ 之间的连续权衡空间
    • 随着 Santa 队列数量的增加（例如从 3 个增加到 6 个），隔离效果越来越接近完美的 FQ 表现

Introduction

  • 互联网 CCA 的异构性与冲突:

    • 现代互联网承载着需求各异的应用（如低延迟敏感的在线游戏与追求高带宽的文件传输），这促使开发者部署了不同优化目标的拥塞控制算法 (CCAs)
    • 例如: 当前最流行的 BBR（追求极低排队延迟）和 CUBIC（倾向于填满缓冲区以最大化吞吐量）
    • 当它们在同一个瓶颈链路（特别是深缓冲区）中竞争时，往往会产生严重的性能冲突，导致严重的不公平并相互施加高昂的延迟惩罚

  • 现有队列管理方案的局限:

    • 传统的排队规则和主动队列管理 (AQMs) 无法管理这种异构性，也无法为具有不同性能偏好的流提供隔离
    • 虽然公平队列 (Fair Queuing, FQ) 可以通过为每个流分配独立队列来实现隔离，但这在互联网庞大的规模下是不切实际的
    • 而诸如 L4S 等其他 AQM 方案则需要端主机提供显式通知并假设主机是诚实的

  • 提出“近似性能隔离”理念:

    • 为了让拥有不同“吞吐量-延迟”权衡目标的算法能友好共存，论文提出了一种可扩展的解决方案：近似性能隔离 (Approximate Performance Isolation)
    • 核心思想: 是不依赖完美的公平队列，而是将具有相似性能权衡诉求的流分派到同一个队列中

  • Santa 系统简介:

    • 作为上述理念的概念验证，作者提出了 Santa —— 一个新颖、实用且可扩展的多队列 AQM 系统
    • Santa 会在一个周期内比较流与其所在队列中其他流的带宽份额，借此推断流的偏好
      • 它会将过于激进的流（"naughty"）和过于保守的流（"nice"）在不同队列之间进行 "洗牌 (shuffle)", 从而使表现相似的流自然聚集

  • 系统的实现与意义:

    • Santa 在可编程交换机 (Intel Tofino) 上完成了原型部署，证明了其在实际应用中的可行性与可扩展性
    • 它仅需少量队列即可近似实现 FQ 的隔离效果，从而解耦不同 CCAs 之间的性能依赖，缓解不公平问题，并更好地适应互联网日益增长的算法多样性

Background and Motivation

(1) 网络的权衡空间与 CCA 的作用

  • 网络的三维约束空间:

    • 网络瓶颈可以被抽象为一个受带宽、延迟（传播延迟到最大排队延迟之间）和丢包率限制的三维权衡空间
    • alt text

  • CCA 的理想工作点:

    • CCA 的目标是在此空间中找到最符合其期望的“自然”工作点
    • 例如:
      • delay-sensitive flow 愿意牺牲部分带宽以换取低延迟（Figure 2 中的点 A）
      • thpt-hungry flow 则为了高带宽能容忍高延迟（Figure 2 中的点 B）
      • alt text

  • 独立与竞争环境的差异:

    • alt text
    • 在没有竞争时，Linux 内核中的真实 CCA（如 CUBIC、Vegas、BBR 等）能各自停留在期望的工作点（如 Figure 3a 所示）
    • 但在共享同一 bottleneck link 时:
      • 延迟敏感型算法会被严重偏离其期望目标并面临带宽饥饿
      • 像 CUBIC 这样的算法则会填满缓冲区（Figure 3b 所示）

(2) 不同的 CCA 如何竞争

  • 性能目标的相互牵制:

    • 由于瓶颈带宽有限，竞争流会相互施加动态约束
    • alt text
    • 如果两者的期望目标相似，它们能协作达成平衡
    • 如果目标迥异，追求吞吐量的流会将平衡点拉离原位，造成不公平

  • 同类算法友好共存:

    • 具有相似期望工作点的 CCA（例如 CUBIC 竞争 CUBIC，或 Vegas 竞争 Vegas）能够公平地分享链路
    • 比如 5.a and 5.b
    • alt text

  • 异构算法相互伤害:

    • 当具有不同操作点的算法相遇时，往往极不兼容
    • alt text
    • 例如，CUBIC 会直接抢占缓冲区导致 Vegas 被饿死（Figure 5c 所示）
    • 在 CUBIC 与 BBR 竞争的场景中，甚至会出现“双输”局面:
      • CUBIC 的吞吐量被削弱，而原本对延迟敏感的 BBR 则遭受了极高的延迟惩罚（Figure 5d 所示）

(3) 提出 Performance Isolation 的依据

  • 传统 AQM 的无效性:
    • 传统的经典主动队列管理 (AQM)（如 CoDel 或 RED）无法让异构 CCA 独立运作
    • CoDel 虽然能降低排队延迟，但仍无法防止 Vegas 被饿死，且容易造成带宽利用率不足
    • RED 甚至会让 BBR 变得更具攻击性

  • 现有近似 FQ 方案的误区:

    • 完美的公平队列 (FQ) 极难在实际中扩展
    • 而现有的近似 FQ 方案（如 AFQ、AHAB、SFQ 等）模拟了 FQ 错误的特性:
      • 它们 仅关注“带宽分配的公平性” (事实上, Fair 的含义应该包括但不限于 bandwidth)
      • 在这些方案下，流虽然获得了公平的带宽，但依然会在共享队列中互相施加延迟和丢包，并未实现真正的隔离

  • 核心结论:

    • 系统真正需要的是 “性能隔离”
    • 让每个流无论面对怎样的竞争对手，都能达成自己期望的“吞吐量-延迟”权衡
    • 作者提出，不需要完美的 FQ，只要找到一种可扩展的方法实现“近似性能隔离”即可解决问题

Approximate Performance Isolation

(1) 近似性能隔离的核心理念:

  • 超越单纯带宽分配的 "真正隔离":

    • 理想的性能隔离不仅要让各个流获得固定的吞吐量份额，还要确保无论它们与哪种拥塞控制算法竞争，都能在期望的“吞吐量-延迟”边界位置上工作

  • 基于 Pareto 边界的流聚合:

    • 不同的 CCAs 天然分布在“吞吐量-延迟”的 Pareto 边界上
    • 系统无需为每个流分配独立队列，而是将处于边界相邻位置（即期望工作点相近）的流划入同一个队列
    • 以此用极少的队列数量近似实现公平队列（FQ）的隔离效果
    • Figure 6 所示，5 个不同偏好的流被合理聚合并整合到了 3 个队列中:
      • alt text

  • 隔离效果验证:

    • 如 Figure 7a 和 7b 所示:
    • alt text
    • 实验证明将 6 种不同偏好的流合理分配到 3 个 FIFO 队列中，所达到的隔离表现与使用 6 个独立队列的完美 FQ 方案高度相似

(2) 工作点推断与洗牌机制

  • 通过“攻击性”推断偏好:

    • 由于网络无法直接预知应用或流的底层偏好，系统通过测量多个流在同一队列中竞争时维持的缓冲区占用量，来推断其相对的 "攻击性 (Aggression)"

  • 过滤老鼠流 (Ignoring Mice Flows):

    • 由于互联网中约 90% 的流是短流，系统会将每个新流的前 10 个数据包直接分配到最高优先级的老鼠队列中，之后才开始对长流进行常规队列分配
    • Figure 9 所示，这覆盖了绝大部分流的长度累积分布
    • alt text

  • 跨队列的动态洗牌 (Shuffling Flows):

    • Figure 8 所示，系统在一轮（round）周期结束时评估流的带宽份额
    • alt text
    • 如果某个流获得的带宽远超队列平均值，说明它过于激进，会被晋升移入序号更高的队列（\(Q_{i+1}\)）
    • 反之，如果它被饿死，则会被降级移入序号更低的队列（\(Q_{i-1}\)）
机制背后的隐式假设

  • 混淆公平性与期望工作点：

    • 该洗牌机制隐含了一个假设，即: 在共享队列中竞争公平的流拥有相似的性能偏好
    • 在浅缓冲区场景下，CUBIC 和 BBR 可能会表现得看似公平，但其实它们的期望操作点截然不同，这需要通过调整路由器缓冲区大小等策略来缓解

  • 攻击性的传递性假设：

    • 系统默认流的相对攻击性具有数学上的传递性
    • 虽然现实中不同算法混战时这一规则偶尔会失效，但基于相对表现的持续洗牌机制，依然能够确保将表现相似的流最终收敛归拢到同一个队列中

Santa's Design

(1) 整体架构与基本原理

  • 队列结构:

    • Santa 维护 1 个具有绝对高优先级的 "老鼠流队列 (mice queue)" 和 \(K\) 个平级的 "Santa 队列"
    • 这 \(K\) 个队列按从 \(Q_1\) 到 \(Q_K\) 排序
      • 最低序号的 \(Q_1\) 容纳最不具攻击性且对延迟敏感的流
      • 最高序号的 \(Q_K\) 则容纳最激进（渴望吞吐量）的流

  • 动态评估机制:

    • Figure 8 所示，系统会定期评估每个流的平均缓冲区占用情况，并与同队列其他流进行比较，借此做出流的 晋升/降级 (洗牌) 决策
    • alt text
    • Santa 的设计包含三个关键环节：初始分配、流洗牌和带宽分配

(2) 初始队列分配

  • 老鼠流优先处理:

    • 鉴于互联网中约 90% 的流是短流:
      • 系统将每个新流的前 10 个数据包划分为"老鼠流"，并送入绝对优先的老鼠队列，避免它们受到长流的影响
    • alt text

  • 长流的加权随机分配:

    • 对于超过 10 个数据包的长流（非老鼠流），如果所有 \(K\) 个队列都不为空，系统会按“加权随机概率”将其分配到某个队列中
    • 分配到某一队列的概率，与该队列中已有的流的数量成正比 (原因: "稀释")

  • 分配策略的双重优势:

    • 最大化准确率:
      • 在不预先知道新流特征的情况下，按照当前稳定的流分布比例去“盲猜”分配，能在概率上最大化初始分配的准确性
    • 提升稳定性:
      • 将不可预知的（甚至极具破坏性的）新流丢进一个已经有大量流的“大池子”，能有效稀释新流对现有网络环境的冲击

(3) 流洗牌与重排

  • 衡量攻击性的核心逻辑:

    • Santa 在每个固定轮次（如 10 秒）内监控一个流的平均缓冲区占用量 (\(B_i\))
    • 将其与该队列中所有流的平均占用水平 (\(\overline{B}\)) 进行对比

  • 晋升与降级规则:

    • 如果 \(B_i > r\overline{B}\)（即: 当前流霸占了过多缓冲区，非常激进）
      • 将其移动到更高一级的队列 (\(Q_{i+1}\)) 中，去和更强悍的流竞争
    • 如果 \(B_i < \overline{B}/r\)（即: 当前流处于劣势，无法抢到资源）
      • 将其移动到更低一级的队列 (\(Q_{i-1}\)) 中，让它享受更温和的竞争与更低的延迟

  • 洗牌阈值 (Shuffling thresholds):

    • 系统引入了阈值倍数 \(r\)（原型设计中 \(r=2\)），这意味着 Santa 允许同一个队列内部存在最大 \(r^2\) 倍的带宽不公平
    • \(r\) 的大小是一个可调参数:
      • 设置过小: 导致流频繁在队列间 反复横跳(不稳定)
      • 设置过大: 意味着 要容忍更高的内部不公平性

(4) 带宽分配

  • 按比例分配带宽:
    • 在每个评估轮次结束时，Santa 会根据 每个队列中当前容纳的流的数量, 成比例为这 \(K\) 个队列分配链路带宽
  • 分配的静态与动态性:
    • 分配完成后，带宽比例在下一个轮次期间保持固定
    • 这种设计既能保证宏观上的公平，又能在一定范围内支持开发者对高吞吐量流分配更多权重的灵活调整
研究类别 核心方法 / 代表性工作 主要机制与特点 局限性与不足
端主机拥塞控制优化
(End-host CCA optimizations)		 针对发送端的特定优化 [7, 36, 42, 45] 致力于在传输层通过调整发送速率来改善带宽共享的公平性。 作用范围有限；当遇到带宽分配不公时，端主机唯一的策略是激进地增加发送速率，这往往会导致严重的网络拥塞，而非实现真正的公平。
网络辅助与信令方法
(Network-assisted approaches)		 ECN信号: DCTCP [5], DCQCN [64], L4S [26]
带内遥测(INT): HPCC [32], PowerTCP [3]
优先级标记: DiffServ [8]		 利用网络内信号（如 ECN 或 INT）来调节过度激进的流；或者由端点给出标记来为流分配不同的优先级。 高度依赖端主机的配合，而互联网用户实际上可能并不总是遵守网络建议的操作或信号。
公平队列及其近似方案
(Fair Queuing & Approximations)		 公平队列: FQ [18]
基于优先级: PIFO [49], SPPIFO [4]
单队列+准入控制: AIFO [61]
网卡卸载: PIEO [48]
多队列+特定数据结构: AFQ [46], PCQ [47], HCSFQ [62]		 FQ 通过为每个流分配单独的队列来实现完美的流级隔离；近似方案则试图利用有限的队列，通过排名调度、准入控制或特定数据结构来模拟 FQ 的效果。 交换机的硬件队列数量有限，完美的 FQ 无法在现实中扩展; 现有的近似方案对所有流采取统一的处理方式，无法区分不同的 CCA 及其目标. 且它们错误地将目标定为了“带宽公平性”而非“性能隔离”。
主动队列管理 (AQMs)
(Active Queue Management)		 传统AQM: RED [20], ARED [19], CoDel [43], PIE [44]
可编程AQM: Nimble [50], Flowtamer [37], Cebinae [60], P4air [51]		 传统AQM主要针对基于丢包的 CCA 进行早期拥塞信令或防止缓冲区膨胀；
可编程方案则支持固定速率限制、通过改变 TCP 接收窗口抑制激进流，或通过向大流“征税”来近似实现大规模公平队列。		 Flowtamer 存在可扩展性问题且不支持 QUIC 流量；P4air 虽试图隔离不同 CCA，但需要维护庞大的每流状态，甚至通过主动丢包来测量响应，且在流改变分组时需要重循环数据包，从而影响实际带宽。
超越带宽公平性的新视角
(Beyond bandwidth fairness)		 质疑TCP友好性 [11]
基于商业协议分配 [10]
关注流完成时间(FCT) [63]
网络效用最大化(NUM) [29]		 指出不应仅仅将带宽平均分配，例如不平衡的带宽分配并不一定会降低用户的实际体验（用户更关心 FCT）；提出在 NUM 范式下看待拥塞控制设计空间。 在现实世界中应用 NUM 范式面临根本性挑战，因为 CCA 的效用函数（通常取决于延迟和吞吐量等参数）往往是未知的。

Conclusion

Our current implementation of Santa is a proof-of-concept that shows it is possible to achieve approximate performance isolation using a handful of queues and a simple shuffling strategy. Santa explores a new design space for AQMs that can allow different CCAs to co-exist and achieve good performance tradeoffs. Santa is open-source and available on GitHub at https://github.com/NUS-SNL/santa-nsdi-ae.

  • 概念验证与核心机制:

    • 目前的 Santa 主要是作为一个概念验证原型
    • 它证明了: 仅需极少量的队列配合简单的洗牌策略，就可以成功实现近似的性能隔离(FQ)

  • 拓展设计空间:

    • Santa 为主动队列管理 (AQM) 探索出了一个全新的设计空间
    • 使得各种不同的 CCAs 能够在一个网络中友好共存，并实现良好的性能权衡

  • 开源状态: