ECMP
哈希选路为何在 AI 负载下出现极化
核心要点：
- ECMP 用 5 元组哈希在等价路径间选路，无状态、ASIC 友好
- AI 训练的低熵大流碰撞概率远高于通用流量（生日悖论）
- 哈希极化让多层 Fat-tree 路径多样性退化到单层
- E-ECMP 引入 QP Number 字段、WCMP 按容量加权是主流缓解方案
ECMP（Equal-Cost Multi-Path）是数据中心网络最基础的多路径路由策略：通过哈希将流量分配到多条等价路径，是 Fat-tree / Clos 拓扑的标准路由方案。
等价路径如何被发现？
ECMP 的前提是网络中存在多条代价相同的路径，由 IGP（Interior Gateway Protocol）在控制平面自动发现。
IGP 计算等价最短路径
数据中心内部通常运行 OSPF 或 IS-IS 协议。每台交换机通过 Link-State Advertisement 获得全网拓扑，运行 Dijkstra（SPF）算法计算到每个目的前缀的最短路径。当 SPF 发现到同一目的地存在多条总代价相同的路径时，将它们全部安装到转发表中，形成 ECMP 组（Next-Hop Group）。
以 3 层 Fat-tree 为例：从任意 ToR 到另一 Pod 的 ToR，经过不同 Spine 交换机的路径代价完全相等——每条路径都是 ToR -> Agg -> Spine -> Agg -> ToR（4 跳），因此 Spine 数量等于 ECMP 组的路径数量。
ECMP 组
ECMP 组是转发表中的一个数据结构，包含到同一目的前缀的所有等价下一跳。交换机 ASIC 的转发流水线分两步：
- 前缀匹配：根据目的 IP 查 FIB，命中某个 ECMP 组
- 组内选路：对报文的 5 元组计算哈希，在组内的 $N$ 个下一跳中选择一个
ECMP 组的大小受平台限制，通常为 32-128 个下一跳。在标准 Fat-tree 中，Spine 数量不超过此上限，因此所有等价路径均可覆盖。
ECMP 如何选路？
核心问题：报文到达交换机后，ECMP 用什么输入、按什么算法在多条等价路径中选一条？
哈希函数与输入字段
ECMP 以报文的 5 元组（源 IP、目标 IP、源端口、目标端口、协议号）为输入，通过哈希函数计算路径选择索引[1]：
$$\begin{equation} \text{path\_index} = \text{hash}(\text{src\_ip}, \text{dst\_ip}, \text{src\_port}, \text{dst\_port}, \text{proto}) \bmod N_{\text{paths}} \label{eq:route-ecmp-hash} \end{equation}$$为什么是 5 元组：3 元组（源 IP + 目标 IP + 协议）的熵太低——同一对主机间的所有 TCP 连接共享相同的 3 元组，全部映射到同一条路径。加入端口字段后，每条 TCP 连接拥有独立的源端口，提供约 $2^{16}$ 的额外熵，实现连接级别的负载均衡。
业界主流哈希算法（交换机 ASIC 内的 ECMP 哈希）：
| 算法 | 使用厂商 | 特点 |
|---|---|---|
| CRC-16 / CRC-32 + XOR 折叠 | Broadcom（Trident/Tomahawk 系列） | 硬件实现简单，种子可配置 |
| XOR / CRC 变体 | NVIDIA/Mellanox（Spectrum 系列） | 可编程哈希字段（含 UDF），种子可配置 |
| CRC + 可配置种子 | Cisco（Nexus/ASR） | 每层交换机使用不同种子，抗极化 |
@tbl-route-ecmp-01 哈希函数与输入字段：算法、使用厂商、特点
哈希算法本身不影响均衡性（均为近似均匀分布），关键差异在于是否支持每层不同种子以对抗哈希极化（见下文分析）。
注意区分：Toeplitz 哈希主要用于 NIC 端的 RSS（Receive Side Scaling）——将进入 NIC 的报文分发到不同 CPU 核——与交换机内的 ECMP 是两个独立的哈希过程。两者输入字段重叠（均含 5 元组），但实现位置和目的不同。
路径选择流程
报文到达交换机入口
|
v
按目的 IP 查 FIB，命中 ECMP 组（N 个等价下一跳）
|
v
提取 5 元组 (src_ip, dst_ip, src_port, dst_port, proto)
|
v
计算 hash(5-tuple)
|
v
path_index = hash % N
|
v
选择第 path_index 个下一跳，转发报文
整个过程是无状态的——交换机不维护任何流表，仅根据当前报文头字段实时计算。这使 ECMP 对 ASIC 的存储和计算开销接近零。
同一条流的所有报文（5 元组不变）始终产生相同的哈希值，因此走同一条路径，不会产生报文乱序。
数值示例
场景：8-Spine Fat-tree，GPU 节点 A（IP 10.0.1.5）向 GPU 节点 B（IP 10.0.2.8）发起 AllReduce 通信。
5 元组 = (10.0.1.5, 10.0.2.8, 49152, 4791, UDP)
hash = CRC32(5-tuple) = 0x7A3C_E1F2
index = 0x7A3C_E1F2 % 8 = 2
-> 选择 Spine-2 转发
该 AllReduce 流的所有后续报文都经过 Spine-2，路径完全确定。
为什么 AI 工作负载下 ECMP 容易碰撞？
核心问题：同样是 ECMP，为什么 AI 训练的实测带宽利用率只有 60-70%，而 Web 流量场景接近线速？
ECMP 的核心弱点是哈希碰撞——多条流被映射到同一条路径，导致该链路过载而其他链路空闲。
碰撞概率：生日悖论
将 $F$ 条流通过哈希映射到 $N$ 条等价路径，至少两条流碰撞到同一路径的概率等价于生日问题：
$$\begin{equation} P(\text{collision}) = 1 - \prod_{i=0}^{F-1} \frac{N - i}{N} = 1 - \frac{N!}{N^F \cdot (N-F)!} \label{eq:route-ecmp-collision} \end{equation}$$数值示例（8-Spine Fat-tree，$N = 8$ 条等价路径，由 $\eqref{eq:route-ecmp-collision}$ 精确计算）：
| 并发流数 $F$ | 碰撞概率 |
|---|---|
| 2 | 12.5% |
| 4 | 59.0% |
| 6 | 92.3% |
| 8 | 99.8% |
@tbl-route-ecmp-02 碰撞概率：生日悖论：并发流数 F、碰撞概率
关键洞察：仅 4 条并发流就有近 60% 的概率产生碰撞。在 AI 训练场景中，双向 Ring AllReduce 的每个 GPU 同时向顺时针和逆时针两个方向发送数据，8 GPU 的双向 Ring 产生 16 条并发流，远超 8 条路径——碰撞几乎必然发生。
为什么 AI 工作负载碰撞尤其严重
传统数据中心流量（Web 服务、微服务调用）具备高熵特征：数千条短流并发，统计上近似均匀分散。而 AI 训练的集合通信具有低熵 + 大流特征：
- 流数少：双向 Ring AllReduce 在 $N$ 个节点上产生 $2N$ 条并发流（每节点同时向两个方向发送），虽然多于路径数但仍远少于 Web 场景的数千条流
- 流量大：每条流传输数十 MB 的梯度数据，持续数百毫秒到数秒
- 同步性：所有流在同一时刻启动（BSP 同步屏障后），碰撞的影响无法被时间维度摊平
结果：碰撞的流共享一条链路的带宽，AllReduce 延迟被最慢的那条流决定（木桶效应），集群训练吞吐直接下降。
多层哈希极化
在多层 Fat-tree 中，若每层交换机使用相同的哈希函数和种子，则：
- 第 1 层（ToR）：流 F 哈希到上行端口 X
- 第 2 层（Spine）：同一流 F 用同样的哈希再次选路，结果与第 1 层相关
所有层的决策高度相关，端到端路径的多样性大幅下降——同种子叠加后，理论上的 $N$-层 fan-out 树（$N^k$ 条不同路径）会因哈希值在层间被复用而显著退化。具体退化程度依赖 fan-out 结构和哈希函数性质，业界缺少通用闭式公式，需要在目标拓扑上通过抽样测量得出。
解决方案：每层使用不同的哈希种子（Cisco ip load-sharing per-packet seed），或将入口端口编号纳入哈希输入，打破层间相关性。
路径多样性的两个极端
把多层 Fat-tree 抽象为 fan-out 树：第 $i$ 层每个交换机有 $N_i$ 条上行端口，则一个流从入口到出口的"理想"路径多样性是各层 fan-out 的乘积：
$$\begin{equation} D_{\text{ideal}} = \prod_{i=1}^{k} N_i \label{eq:route-ecmp-diversity-ideal} \end{equation}$$但实际有效多样性 $D_{\text{effective}}$ 受哈希函数性质和种子配置约束，可在两个极端之间变化：
情形 A：完全独立的层间哈希（理想情况——每层独立种子或不同输入字段）
各层选路统计独立，路径多样性达到上界：
$$\begin{equation} D_{\text{effective}}^{(A)} = D_{\text{ideal}} \label{eq:route-ecmp-effective-bw-balanced} \end{equation}$$情形 B：完全相同的哈希函数 + 种子 + 输入字段
第 1 层把流分到 $N_1$ 个桶后，第 2 层再次哈希时输入字段完全没变（5 元组不变）——同一哈希函数在同输入下产出同输出。第 2 层的"选择"是第 1 层选择的确定性函数，多样性退化为单层多样性：
$$\begin{equation} D_{\text{effective}}^{(B)} \approx N_{\min} = \min_i N_i \label{eq:route-ecmp-effective-bw-skewed} \end{equation}$$——其它层的 fan-out 完全冗余，端到端只剩一层有效多样性。
实际部署介于二者之间，具体接近哪一端取决于：
- 每层是否使用不同种子
- 哈希输入是否包含入口端口编号、TTL 等"随跳变化"的字段
- 哈希函数的雪崩效应（小输入扰动引发大输出变化的程度）
业界没有公开的通用闭式公式描述"$D_{\text{effective}}$ 如何随种子配置和输入选取衰减"——具体退化程度需要在目标拓扑上通过抽样测量得出。
对 AI 工作负载的实测影响
虽然 $D_{\text{effective}}$ 没有通用公式，但其对 AI 训练吞吐的影响有实测数据：
碰撞概率 $\eqref{eq:route-ecmp-collision}$ 中的"路径数" $N$ 实际应取 $D_{\text{effective}}$ 而非 $D_{\text{ideal}}$。当 $D_{\text{effective}}$ 显著小于 $D_{\text{ideal}}$ 时，并发流碰撞概率快速逼近 100%。Meta SIGCOMM 2024 在 24K GPU 集群上的实测显示：
- 标准 ECMP 5-元组哈希下有效带宽利用率仅 60-70%
- E-ECMP 引入 QP Number 字段后提升到 80-90%[2]
E-ECMP 收益的物理解释是打破 5 元组同输入约束：每个 QP 拥有独立 QP Number，等价于把"输入熵"从 $\sim 2^{60}$（5 元组）扩展到 $\sim 2^{60} \times Q$（Q 个 QP），从根本上恢复了哈希多样性。
哈希极化的检测与诊断
生产环境检测哈希极化的常用方法：
- 流量分布抽样：在 Spine 交换机统计各端口流量，理论均匀时方差应远小于均值。若方差/均值 > 1，提示极化
- 路径多样性主动探测：在 host 端用不同 5 元组 / flow label 主动测量到目的的路径分布
- 链路利用率热图：长期 telemetry 显示热点链路集中度
修复优先级：
- 在所有层（ToR / Agg / Spine）配置不同的哈希种子
- 把入口端口编号纳入哈希输入（多数现代 ASIC 默认支持）
- 启用 E-ECMP（若是 RoCEv2 集群）或 DQPLB（若已部署 NCCLX）
业界如何缓解 ECMP 哈希极化？
核心问题：不换路由协议、不引入自适应路由的前提下，怎么让 ECMP 在 AI 负载下接近理论吞吐？
E-ECMP（Meta SIGCOMM 2024）
针对 AI 工作负载的哈希极化问题，Meta 在 24K GPU RoCEv2 集群中部署了 E-ECMP（Enhanced ECMP），从两个维度扩展哈希熵：
ASIC 侧：QP 字段注入
RoCEv2 报文的 BTH（Base Transport Header）中包含目的 QP Number 字段。标准 ECMP 不解析 BTH，仅用外层 UDP 5 元组。E-ECMP 利用交换机 ASIC 的 UDF（User Defined Field） 能力——一种可编程的报文解析器，允许运维人员指定任意报文头偏移量作为额外哈希输入——将 QP Number 纳入哈希计算：
$$\begin{equation} \text{path\_index} = \text{hash}(\text{5-tuple}, \text{QP\_number}) \bmod N_{\text{paths}} \label{eq:route-eecmp-hash} \end{equation}$$由于每个 QP 拥有唯一编号，即使 5 元组相同的多个 QP 也会散列到不同路径。
软件侧：QP Scaling
NCCL（及 Meta 的 NCCLX）在每对通信节点间建立多个 QP（通常 4-16 个），将一条逻辑 AllReduce 流拆分为多条子流。每条子流对应不同的 QP，拥有不同的源端口号，自然散列到不同物理路径。
效果：AllReduce 吞吐提升约 40%，有效带宽利用率从 60-70% 提升到 80-90%[2]。
WCMP（Google Jupiter）
WCMP（Weighted Cost Multi-Path）是 ECMP 的加权版本，由 Google 在 Jupiter 网络中大规模部署[3]，解决拓扑不对称和链路故障场景下的流量失衡[4]。
加权哈希机制
标准 ECMP 对 $N$ 条路径等权分配（每条 $1/N$）。WCMP 按链路实际可用容量分配哈希桶：
$$\begin{equation} w_i = \frac{C_i}{\sum_{j=1}^{N} C_j} \cdot B_{\text{total}} \label{eq:route-wcmp-weight} \end{equation}$$其中 $w_i$ 为第 $i$ 条路径分配的哈希桶数量，$C_i$ 为该路径的可用容量，$B_{\text{total}}$ 为哈希桶总数。报文的 hash % B_total 落入哪个桶，就走对应的路径。
SDN 控制器动态调权
Google 的 SDN 控制器（Jupiter Fabric Manager）持续收集链路状态：
- 检测链路故障或容量降级
- 重新计算每条路径的权重向量
- 将更新的桶映射下发到受影响的交换机
数值示例：Fat-tree 中 4 条等价路径（各 400G），其中一条降级为 100G：
- 标准 ECMP：4 条路径各分 25% 流量，但降级链路只有 1/4 容量，实际过载 4 倍
- WCMP：总容量 = $400 \times 3 + 100 = 1300\text{G}$，降级路径分配 $100/1300 = 7.7\%$ 的桶，其余三条各 $400/1300 = 30.8\%$，流量与容量匹配
在更极端的场景下（多条链路同时故障或严重降级），ECMP 的流量分配比差距可达 25 倍[3]，WCMP 通过动态调权消除这种失衡。
Resilient ECMP（一致性哈希）
标准 ECMP 在 ECMP 组成员变更时（如某条路径故障移除），所有流的 hash % (N-1) 结果都可能改变，导致大量流迁移路径（流量震荡）。
Resilient ECMP 使用一致性哈希（Consistent Hashing）：预分配固定数量的哈希桶到各路径，路径故障时仅将该路径的桶重分配给其他路径，不影响未故障路径上的已有流。
三种变体的性能对比
核心问题：标准 ECMP / E-ECMP / WCMP 在带宽利用率、硬件要求、故障鲁棒性上各自做了什么取舍？
| 指标 | 标准 ECMP | E-ECMP | WCMP |
|---|---|---|---|
| 有效带宽利用率 | 60-70%（AI 负载） | 80-90% | 85-95% |
| 实现复杂度 | 最低 | 低（需 ASIC UDF） | 中（需 SDN 控制器） |
| 硬件要求 | 通用 ASIC | 支持 UDF 的 ASIC | 通用 ASIC |
| 应对拓扑不对称 | 差 | 差 | 好 |
| 故障时流量震荡 | 高（全局重哈希） | 高 | 低（可结合 Resilient ECMP） |
@tbl-route-ecmp-03 性能特性：指标、标准 ECMP、E-ECMP 等
何时该用 ECMP，何时不该？
适用场景：
- Fat-tree / Clos 拓扑，路径等价性强
- 通用互联网流量（流数量多、单流带宽小、熵高）
- 需要低成本、高兼容性的部署环境
局限：
- 哈希极化：AI 训练场景中流数少、流量大、同步性强，碰撞概率高（见 $\eqref{eq:route-ecmp-collision}$ 分析）
- 无法响应实时拥塞：路径选定后不随网络状态变化，某条链路过载后无法自动迁移流量
- 非 Fat-tree 拓扑收益有限：Torus、Dragonfly 等拓扑的等价路径数量少，ECMP 分散效果差
选型建议：
- Fat-tree + AI 工作负载：优先使用 E-ECMP + QP Scaling
- 拓扑不对称或存在链路故障：使用 WCMP
- 需要实时拥塞响应：考虑自适应路由（AR）
Takeaway
| 知识点 | 核心结论 |
|---|---|
| ECMP 选路机制 | 5 元组哈希 % 路径数，无状态、流级绑定、ASIC 友好 |
| AI 负载碰撞 | 双向 Ring AllReduce 同步发起，4 条流即 60% 碰撞概率（生日悖论） |
| 哈希极化 | 多层同种子哈希让多层 Fat-tree 的有效路径多样性退化到 $\min_i N_i$ |
| E-ECMP | 把 RoCEv2 QP Number 纳入哈希，吞吐 +40%（Meta SIGCOMM 2024） |
| WCMP | 按链路容量加权分桶，应对拓扑不对称和链路降级（Google Jupiter） |
| Resilient ECMP | 一致性哈希避免 ECMP 组变更时的全局流量震荡 |
参考资料
- Hopps, Analysis of an Equal-Cost Multi-Path Algorithm, RFC 2992, 2000. https://www.rfc-editor.org/rfc/rfc2992
- Gangidi et al., RDMA over Ethernet for Distributed AI Training at Meta Scale, SIGCOMM 2024. https://dl.acm.org/doi/10.1145/3651890.3672233
- Poutievski et al., Jupiter Evolving: Transforming Google's Datacenter Network via Optical Circuit Switches and Software-Defined Networking, SIGCOMM 2022. https://dl.acm.org/doi/10.1145/3544216.3544265
- Zhou et al., WCMP: Weighted Cost Multipathing for Improved Fairness in Data Centers, EuroSys 2014 / Google Research. https://research.google/pubs/pub49093/