自适应路由

交换机如何实时感知拥塞并动态切换路径

核心要点：

• AR 在每次转发时读队列深度，选当前最不拥塞的出口
• 两种粒度：逐报文（均衡最好但乱序）vs 逐 flowlet（均衡 + 有序）
• Flowlet gap $\ge d_{\max} - d_{\min}$ 是无乱序的充分条件
• 反馈延迟过大或灵敏度过高会让 AR 振荡，反不如 ECMP

自适应路由（Adaptive Routing, AR）是运行时感知网络状态的动态路由策略：交换机在转发时实时观察各出口的队列深度或信用可用量，动态选择当前最不拥塞的出口。与 ECMP 的静态哈希绑定不同，AR 在拥塞发生时立即将流量迁移到空闲路径。

AR 与 ECMP 的根本区别是什么？

核心问题：同样是在多路径中选一条，ECMP 哈希一次定终身、AR 每包重评估——这一差异在拥塞响应上意味着什么？

ECMP 在报文到达时根据 5 元组哈希一次性决定路径，此后该流的所有报文始终走同一条路径，即使该路径已拥塞。AR 则在每个转发时刻重新评估所有候选出口的拥塞状态，选择当前最优出口。

两种方式的本质差异在于决策所用信息见 ：

维度	ECMP	自适应路由
决策输入	报文头字段（静态）	出口队列深度（动态）
决策时机	流的首包到达时	每个报文/flowlet 到达时
路径变更	不变（除非拓扑变化）	随拥塞状态实时变化

@tbl-route-ar-vs-ecmp AR 与 ECMP 的核心区别

两种感知粒度

逐报文（per-packet）AR：每个报文独立选择最优出口。负载均衡效果最好，但同一流的报文可能走不同路径，产生乱序。

逐 flowlet（per-flowlet）AR：检测同一流中两段突发之间的静默间隔，超过阈值（flowlet gap）时重新选路，否则沿用旧路径。在均衡性和有序性之间取得平衡。

逐报文 AR 如何工作？

选路公式

报文到达交换机后，交换机查询转发表获得到目的地的所有候选出口端口集合 $P = \{p_1, p_2, \ldots, p_N\}$，读取各端口的当前队列深度 $q(p_i)$，选择队列最短的端口：

$$\begin{equation} p^* = \arg\min_{p_i \in P} q(p_i) \label{eq:route-ar-per-packet} \end{equation}$$

当多个端口队列深度相等时，使用次级规则打破平局（如静态哈希或端口编号取模），避免所有流同时涌向同一端口。

决策流程

报文到达交换机入口
  |
  v
按目的 IP 查 FIB，获取候选出口端口集合 P = {p1, p2, ..., pN}
  |
  v
读取各端口当前队列深度 q(p1), q(p2), ..., q(pN)
  |
  v
p* = argmin q(pi)
  |
  +-- 若有多个最小值 --> 次级规则打破平局（hash % 候选数）
  |
  v
从端口 p* 转发报文

数值示例

场景：8-Spine Fat-tree，ToR 交换机有 8 个上行端口通往 Spine 层。AllReduce 流量导致 Spine-3 拥塞。

端口队列深度：
  Spine-0: 12 KB    Spine-4: 8 KB
  Spine-1: 15 KB    Spine-5: 3 KB
  Spine-2: 6 KB     Spine-6: 45 KB  <-- 拥塞
  Spine-3: 52 KB    Spine-7: 2 KB   <-- 最空闲

AR 选择: p* = Spine-7 (q = 2 KB)
ECMP 选择: hash(5-tuple) % 8 = 3 -> Spine-3 (q = 52 KB，拥塞)

AR 避开了拥塞的 Spine-3，而 ECMP 无法感知拥塞，继续向已过载的路径发送流量。

逐 flowlet AR 如何在均衡与有序之间取舍？

核心问题：逐报文 AR 必然乱序，怎么在保留拥塞响应能力的同时不破坏报文顺序？

Flowlet 定义

Flowlet 是同一条流中的一段连续突发。当同一流的两个连续报文之间的间隔超过阈值 $\tau_{\text{gap}}$ 时，后续报文被视为新 flowlet 的起点，允许重新选路。

数据结构

交换机为每条活跃流维护一个 flowlet 表，按流的哈希索引见 ：

字段	含义
flow_hash	流的 5 元组哈希（索引键）
last_port	上一个报文使用的出口端口
last_time	上一个报文的到达时间戳

@tbl-route-ar-flowlet-struct Flowlet 表数据结构

决策算法

报文到达，计算 flow_hash
  |
  v
查 flowlet 表，找到 (last_port, last_time)
  |
  v
计算间隔 delta = current_time - last_time
  |
  +-- delta > flowlet_gap?
  |     |
  |     +-- 是 --> 新 flowlet：重新选路
  |     |           p* = argmin q(pi)
  |     |           更新 last_port = p*, last_time = current_time
  |     |
  |     +-- 否 --> 同一 flowlet：沿用旧路径
  |                 p* = last_port
  |                 更新 last_time = current_time
  |
  v
从端口 p* 转发报文

Flowlet Gap 的无乱序条件

Flowlet gap 的设定直接决定是否会产生报文乱序。考虑同一流的两个连续报文 $P_1$ 和 $P_2$：

• $P_1$ 在时刻 $t$ 发出，走路径 A（延迟 $d_A$），到达时刻 $t + d_A$
• $P_2$ 在时刻 $t + g$ 发出（$g$ 为间隔），走路径 B（延迟 $d_B$），到达时刻 $t + g + d_B$

不乱序的条件是 $P_1$ 先到达：

$$\begin{equation} t + d_A \le t + g + d_B \label{eq:route-adaptive-switching-condition} \end{equation}$$

即：

$$\begin{equation} g \ge d_A - d_B \label{eq:route-ar-flowlet-gap-condition} \end{equation}$$

由于 $P_1$ 和 $P_2$ 可能走任意两条候选路径，通用的无乱序条件为：

$$\begin{equation} \tau_{\text{gap}} \ge \max_{i,j \in P}(d_i - d_j) = d_{\max} - d_{\min} \label{eq:route-ar-flowlet-gap} \end{equation}$$

其中 $d_{\max}$ 和 $d_{\min}$ 分别是所有候选路径中最大和最小的端到端延迟。

Flowlet Gap 取值分析

在对称 Fat-tree 中，所有等价路径的跳数相同（如 3 层 Fat-tree 跨 Pod 固定 4 跳），因此路径延迟差异完全由排队延迟决定见 ：

网络环境	路径延迟差 ($d_{\max} - d_{\min}$)	建议 $\tau_{\text{gap}}$
轻负载 Fat-tree	< 1 $\mu$s（排队极少）	50-100 $\mu$s
中等负载	1-10 $\mu$s	100-500 $\mu$s
重负载（AI AllReduce 突发）	10-50 $\mu$s	500 $\mu$s - 2 ms

@tbl-route-ar-flowlet-gap-values Flowlet Gap 取值分析（按网络负载）

权衡：$\tau_{\text{gap}}$ 越大，乱序风险越低，但重选路的机会越少，AR 的均衡效果越接近 ECMP。$\tau_{\text{gap}}$ 越小，均衡越灵敏，但乱序风险越高。实际部署中 InfiniBand 的 flowlet gap 通常由 Subnet Manager 配置在 50-500 $\mu$s 范围。

AR 的乱序代价如何处理？

逐报文 AR 必然产生乱序——同一流的连续报文走不同长度的路径，后发先至。逐 flowlet AR 通过 $\eqref{eq:route-ar-flowlet-gap}$ 的约束大幅降低乱序概率，但在排队延迟突变时仍可能发生。

InfiniBand vs RoCEv2 的处理方式

维度	InfiniBand AR	RoCEv2/以太网 AR
重排序处理	HCA（ConnectX NIC）硬件透明重排序，对应用完全不可见	NIC 或软件层处理，需额外配置
流控机制	原生 credit-based（天然无损）	PFC + ECN（需配置，PFC 暂停的端口队列深度可能误导 AR）
AR 配置	Subnet Manager 统一下发 flowlet gap 等参数	SDN 控制器或手动配置
SHARP 协同	支持——SHARP 在同一交换机上做网内规约，AR 均衡剩余流量	不支持（SHARP 仅限 InfiniBand）
代表芯片	NVIDIA Quantum/Quantum-2	NVIDIA Spectrum-4、Broadcom Tomahawk 4+

@tbl-route-ar-ib-vs-roce InfiniBand AR 与 RoCEv2 AR 的处理方式对比

InfiniBand AR 的工程成熟度显著高于以太网 AR：HCA 的硬件重排序缓冲对上层 RDMA 语义完全透明，应用无需任何修改。RoCEv2 环境中，AR 产生的乱序需要 NIC 支持（如 ConnectX-7 的 RoCEv2 重排序模式）或软件栈适配。

PFC 对 AR 的干扰

在 RoCEv2 环境中，PFC 暂停的端口队列深度可能看起来很低（因为上游已停止发送），但该端口实际上被阻塞。AR 如果仅凭队列深度选路，可能将流量导向被 PFC 暂停的端口。解决方案是将 PFC 暂停状态纳入 AR 的决策输入，或使用信用可用量（credit availability）替代队列深度作为拥塞指标。

业界 AR 实现有哪些代表方案？

CONGA（SIGCOMM 2014）

CONGA[1] 在交换机侧实现 flowlet 级负载均衡，核心特点是带内拥塞反馈：

• Spine 交换机在数据报文中附加拥塞度量（队列利用率）
• 目的 Leaf 收集路径拥塞信息，通过反向流量回传给源 Leaf
• 源 Leaf 根据各路径的拥塞度量，在 flowlet 边界选择最不拥塞的路径

CONGA 使用相对小的固定 flowlet gap（论文中约 500 μs），只要该 gap 大于路径排队延迟差，即可保证基本有序——这是 $\eqref{eq:route-ar-flowlet-gap}$ 的工程实例。CONGA 的核心代价是需要定制 ASIC 支持带内拥塞反馈头。

LetFlow（NSDI 2017）

LetFlow[2] 是极简主义方案——交换机侧实现，但不需要拥塞反馈：

• 在 flowlet 边界随机选择一条候选路径（randomized load balancing）
• 不使用任何拥塞反馈信号，也不需要主机侧改动
• 利用 flowlet 的天然突发特性：随机散列在统计上近似均匀分布，且实现极简

LetFlow 在交换机本地完成 flowlet 检测与选路，使用相对小的 flowlet gap（论文中 ~500 μs 量级），性能接近 CONGA 但实现复杂度远低（无需带内拥塞反馈头）。

方案对比

方案	决策位置	拥塞信号	交换机修改	Flowlet Gap
Per-packet AR	交换机	本地队列深度	需要 AR ASIC	N/A（逐包）
Per-flowlet AR (IB)	交换机	本地队列深度	需要 IB ASIC	50-500 $\mu$s
CONGA	Leaf 交换机	带内反馈（RTT + 队列利用率）	需要定制 ASIC	固定 ~500 $\mu$s
LetFlow	交换机（本地）	无（随机路径选择）	仅需识别 flowlet	固定 ~500 $\mu$s

@tbl-route-ar-scheme-compare AR 方案对比（Per-packet/Per-flowlet/CONGA/LetFlow）

AR 为什么容易振荡，如何避免？

AR 的核心机制是"读队列深度 → 决策 → 切换路径"，本质上是一个带反馈延迟的闭环控制系统。当反馈延迟与决策灵敏度不匹配时，AR 会振荡——同一条流在多条路径之间来回切换，反而不如静态 ECMP。这是 AR 工程部署中最常见的失效模式，但通用的稳定性闭式判据在业界并无标准化形式，下面给出定性机制和工程经验。

振荡的形成机制

考虑两条等价路径 $P_A$ 和 $P_B$，AR 周期性重新评估，反馈延迟 $\tau_{\text{fb}}$ 表示"队列深度从拥塞实际发生到 AR 决策器观测到"之间的时延：

t=0:  P_A 已积压，AR 读到 q(P_A) >> q(P_B)，切换到 P_B
t=τ:  报文开始走 P_B，P_A 上的队列因停止注入开始消散
t=T_dec: AR 再次评估，但观测到的 q(P_A) 仍是历史值（消散未反映）
        AR 仍以为 P_A 拥塞，继续走 P_B
        此时 P_B 已被新流量灌满
t=2T_dec: AR 观测到 q(P_B) >> q(P_A)，又切回 P_A——但 P_A 已消散完毕
         AR 看到的始终是过时数据

结果：流量在 $P_A$、$P_B$ 之间反复跳跃，两条路径都不被充分利用，且乱序严重。这与控制理论中"反馈延迟超过被控对象时间常数时系统失稳"是同一类现象（但不能直接套用线性系统 Nyquist 判据——AR 是非线性离散决策）。

稳定性的定性原则

避免振荡的核心是让"AR 看到的状态"与"网络真实状态"保持一致。三个相互独立的旋钮：

旋钮	影响	调整方向
决策周期 $T_{\text{dec}}$	两次决策之间的时间间隔	$T_{\text{dec}}$ 显著大于 $\tau_{\text{fb}}$，让反馈跟上
决策灵敏度	多大队列差异触发切换	灵敏度低（差异大才切）→ 不被噪声推动
切换粒度	per-packet / per-flowlet / per-flow	粒度大 → 切换频次低 → 振荡幅度小

@tbl-route-ar-stability-knobs AR 稳定性调节旋钮

经验法则（无闭式公式，依经验估算）：

• 决策周期至少 2-3 倍于反馈延迟
• 切换粒度从 per-packet 升级到 per-flowlet 通常足以消除振荡
• 在反馈延迟显著大（跨域 SDN 反馈、带内反馈跨多跳）时，应增大灵敏度阈值或退化为静态路由

工程实践：用 Bias 降低灵敏度

UGAL 等算法引入的 bias 参数（见 06-ugal.md §切换条件）正是"决策灵敏度"旋钮的具体实现：

$$\begin{equation} \text{cost}_{\text{min}} \le \text{cost}_{\text{val}} \times \text{bias} \label{eq:route-adaptive-ugal-bias-rule} \end{equation}$$

bias > 1 让 AR 偏向"维持当前路径"，只有在拥塞显著且持续时才切换。bias 越大，振荡风险越低，但响应速度也越慢——这是稳定性 vs 响应速度的经典权衡。具体的 bias 取值需要在目标网络上调参验证，UGAL 原始论文给出的 bias 通常在 2.0-3.0 区间。

与拥塞控制的耦合振荡

更复杂的情形是 AR 与上层拥塞控制（DCTCP / Swift / Bolt）的耦合振荡：

• 拥塞控制根据 ECN 信号降速
• AR 看到队列消散，切回原路径
• 拥塞控制看到 RTT 改善，升速
• 队列再次积压，循环

这种二阶振荡比纯 AR 振荡更难调试。生产部署中通常通过让 AR 决策周期显著大于拥塞控制的响应时间（数 RTT 量级）来解耦——具体倍数取决于拥塞控制算法的响应曲线。

AR 在带宽利用率上比 ECMP 提升多少？

指标	Per-packet AR	Per-flowlet AR	ECMP（对照）
有效带宽利用率	88-95%	85-92%	60-70%（AI 负载）
延迟稳定性	中（乱序恢复增加尾延迟）	好（实时避拥塞 + 基本有序）	高（但拥塞路径延迟高）
乱序风险	高	低（$\tau_{\text{gap}} \ge d_{\max} - d_{\min}$ 时无乱序）	无
硬件复杂度	高（AR ASIC + 重排序缓冲）	中高（AR ASIC + flowlet 表）	低（通用 ASIC）

@tbl-route-ar-perf AR 性能特性（vs ECMP）

关键洞察：AR per-flowlet 相比 ECMP 的带宽利用率提升约 15-30 个百分点（从 60-70% 到 85-92%）[3]，代价是需要专用 ASIC 和 flowlet 表的存储开销。在 AI 训练的 AllReduce 突发场景中，AR 的实时拥塞感知能力尤为关键——周期性同步突发（Collective Burst）恰好是 AR 能够实时疏散的流量模式。

何时该用 AR，何时不该？

适用场景：

• InfiniBand 集群（硬件 AR 成熟，HCA 内置重排序，对应用透明）
• 使用 NVIDIA Spectrum-4 或 Broadcom Tomahawk 4+ 的 RoCEv2 集群
• 流量模式不规律、需要实时响应拥塞的大规模 AI 集群
• Dragonfly 拓扑中全局链路的拥塞管理（需与 UGAL 配合，参见 LIA[4]）

局限：

• 需要特定硬件——无法在通用以太网交换机上部署
• Per-packet AR 的报文乱序对 RDMA 语义有影响，需要重排序缓冲
• RoCEv2 环境中 PFC 暂停状态可能干扰 AR 的队列深度判断
• Flowlet 表规模受限于 ASIC 的 SRAM 容量，大规模网络中可能出现哈希冲突

选型建议：

• InfiniBand Fat-tree + AI 训练：per-flowlet AR 是默认最优选择
• RoCEv2 Fat-tree：优先考虑 E-ECMP + QP Scaling（无 AR 硬件时），有 AR ASIC 时使用 per-flowlet AR
• 需要极致带宽利用率且有 UEC NIC：考虑 Packet Spraying（见 3.7 Packet Spraying）

Takeaway

知识点	核心结论
AR 决策机制	每次转发读队列深度 $q(p_i)$，选 $\arg\min q$
Per-packet vs per-flowlet	前者均衡最好但乱序；后者用 $\tau_{\text{gap}} \ge d_{\max} - d_{\min}$ 保有序
乱序处理	InfiniBand HCA 硬件透明重排序；RoCEv2 需 NIC 或软件层适配
代表方案	CONGA（带内反馈）/ LetFlow（本地随机）/ IB per-flowlet AR
振荡机制	反馈延迟超过 AR 决策周期 → 历史数据驱动决策 → 路径反复跳跃
稳定性旋钮	决策周期、灵敏度（bias）、切换粒度
实测收益	per-flowlet AR 相比 ECMP 带宽利用率 +15-30 pp（60-70% → 85-92%）

参考资料

1. Alizadeh et al., CONGA: Distributed Congestion-Aware Load Balancing for Datacenters, SIGCOMM 2014. https://dl.acm.org/doi/10.1145/2619239.2626316
2. Vanini et al., Let It Flow: Resilient Asymmetric Load Balancing with Flowlet Switching, NSDI 2017. https://www.usenix.org/conference/nsdi17/technical-sessions/presentation/vanini
3. Gangidi et al., RDMA over Ethernet for Distributed AI Training at Meta Scale, SIGCOMM 2024. https://dl.acm.org/doi/10.1145/3651890.3672233
4. LIA: Latency-Improved Adaptive Routing for Dragonfly, ACM TACO 2025. https://dl.acm.org/doi/10.1145/3711914