技术摘要：一种用于可扩展确定性网络的非工作守恒无状态核心公平队列调度器

问题陈述

确定性网络（DetNet）旨在为参与流提供严格的端到端（E2E）延迟和抖动保证。虽然在具有低传播延迟的小型网络中可以实现确定性性能，但将这些解决方案扩展到大型网络面临着重大挑战。现有方法面临着特定的局限性：

• 有状态公平队列（如 PGPS、WFQ）： 这些方法提供了最优的流隔离和延迟界限，但需要在每个节点维护每条流的状态信息（特别是前一个数据包的完成时间）。在处理数百万条流的核心节点中，管理此类状态的复杂度（$O(N)$）使其无法实现线速处理。
• 工作守恒无状态调度（如 C-SCORE）： 为了解决可扩展性问题，IETF DetNet 工作组和 ITU-T 正在标准化 C-SCORE。该技术通过在数据包报头中传输作为元数据的流状态（完成时间，FT）来转移流状态，从而消除了核心节点维护流状态的需求。然而，由于 C-SCORE 是工作守恒的（即当链路空闲时立即传输数据包），它无法提供确定性的抖动保证。其抖动波动范围可能与端到端延迟界限本身一样大。
• 替代机制（TSN、CJVC）： IEEE 802.1 TSN 中的时间感知整形（TAS）和循环队列转发（CQF）提供了抖动控制，但面临着可扩展性问题（NP-hard 调度、严格的同步要求或周期时间限制）。核心无状态虚拟时钟（CJVC）试图减少抖动，但需要过多的元数据和复杂的计算（例如，在传输前预测服务完成时间），这使得实时处理负担沉重。

方法论

作者提出了 N-SCORE（非工作守恒无状态核心公平队列），这是对 C-SCORE 框架的一种演进，旨在提供确定性抖动而不牺牲可扩展性。

核心算法

N-SCORE 保留了 C-SCORE 的无状态特性，将流状态作为数据包元数据进行携带，但通过引入合格时间（Eligible Time, ET）参数引入了非工作守恒机制。

1. 元数据传播：
   • 完成时间（Finish Time, FT）： 在入口节点计算并在核心节点更新，代表理想的服务完成时间。
   • 合格时间（Eligible Time, ET）： 一个新的参数，在入口节点计算并在核心节点更新。它定义了数据包被允许开始服务的最早时间。
2. 调度逻辑：
   • 数据包根据其 FT（升序）在队列中进行排序。
   • 非工作守恒约束： 只有当当前时间大于或等于其 ET 时，数据包才能被服务。即使链路处于空闲状态，在到达其 ET 之前的数据包也必须等待。
   • 这种强制执行的等待期防止了导致工作守恒系统中抖动的“突发性”链路利用。
3. 数学公式化：
   • 节点 $h$ 处的 FT 更新为 $F_h(p) = F_{h-1}(p) + d_{h-1}(p)$，与 C-SCORE 相同。
   • ET 更新为 $E_h(p) = E_{h-1}(p) + d_{h-1}(p)$，其中 $d$ 包括节点延迟因子以及传播/时钟差异。
   • 服务间隔定义为 $(E_h(p), F_h(p)]$。作者证明了同一条流的连续数据包之间的这些间隔不会重叠。

理论推导

论文为以下界限提供了严密的数学证明：

• 端到端延迟上界： 被证明与有状态公平队列（PGPS）和 C-SCORE 相同。该界限是流固有参数（突发大小、数据包长度、服务速率）和节点延迟因子的函数，且与网络利用率无关。
• 端到端延迟下界： 基于 ET 约束进行推导，建立了数据包必须经历的最小延迟。
• 抖动界限： 定义为端到端延迟上界与下界之间的差值。分析表明，由于非工作守恒行为提升了下界，N-SCORE 显著降低了抖动。
• 缓存占用： 每跳缓存需求被限制在约 $3NL$（其中 $N$ 是流数量，$L$ 是最大数据包大小）。这一适度的需求是通过非重叠服务间隔推导出来的。

核心贡献

1. 提出 N-SCORE： 一种新型调度器，能够在不要求核心节点维护每条流状态的情况下，在大规模网络中实现确定性抖动保证。
2. 最优性理论证明： 形式化证明了 N-SCORE 在提供优于有状态公平队列的抖动抑制的同时，保留了其最优的端到端延迟上界。
3. 缓存复杂度分析： 表征了节点缓存需求，确立了 $\approx 3NL$ 的上界，这减轻了与其他背景下的先进先出（PIFO）队列相比的实现复杂度。
4. 标准化背景： 该工作被指出已被采纳为 IETF DetNet 工作组的草案。

结果

作者通过使用 SimPy 框架在部分网格网络拓扑（7 跳，1 Gbps 链路）上进行广泛模拟，验证了 N-SCORE。研究对比了 N-SCORE 与 CQF、增强型 CQF（ECQF）、带有 ECQF 的 ATS 以及 CJVC 和 C-SCORE，涵盖了典型的车载网络中的三种流类型（音频、视频、控制命令）。

• 延迟性能：
  • N-SCORE 实现了与 C-SCORE 和 CJVC 相同的端到端延迟界限。
  • 除 CQF 外，所有调度器在高利用率（93.6%）下均满足了视频流 10 ms 的截止日期要求。
  • C-SCORE 实现了最低的绝对延迟（由于其工作守恒特性），但 N-SCORE 保持了相同的理论上界。
• 抖动性能：
  • 对于音频和控制命令流，N-SCORE 和 CJVC 展示了最低的抖动水平，明显优于基于 CQF 的调度器。
  • 对于视频流，所有调度器（包括 N-SCORE、CJVC、CQF 和 ECQF）都表现出约 8 ms 的相似抖动水平。这归因于为满足截止日期要求而对视频流应用的整形延迟，该延迟主导了此类特定流类型的抖动特征。
  • 由于 C-SCORE 的工作守恒性质，其在音频和控制命令流方面的抖动高于 N-SCORE 和 CJVC，证实了链路效率与抖动控制之间的权衡。
• 缓存占用：
  • 在 93.6% 利用率下的模拟确认，所有节点观察到的最大缓存占用量始终低于论文中推导的理论上界。

意义

该论文将 N-SCORE 定位为可扩展确定性网络的一项关键进展。其主要意义在于解决了长期存在的可扩展性与确定性抖动之间的权衡问题。

• 通过消除核心节点维护流状态的需求，N-SCORE 使得在有状态方法在计算上不可行的规模化网络中部署公平队列原则成为可能。
• 通过引入基于合格时间的非工作守恒机制，它克服了 C-SCORE 的根本局限（缺乏抖动保证），同时避免了 CJVC 高昂的元数据或计算开销。
• 作者得出结论，N-SCORE 提供了一条实现“两全其美”的切实路径：既拥有有状态公平队列的最优延迟界限，又具备非工作守恒系统的抖动抑制能力，同时保持了适合硬件实现的缓存足迹。

论文指出，虽然 N-SCORE 显著改善了抖动，但来自单个流的大规模突发仍可能因端到端延迟在突发内第一个和最后一个数据包之间的差异而导致抖动。作者建议未来的工作可能涉及将突发视为单一实体（类似于“流簇/flowlets”）以进一步减轻这种影响。