总览
本章节范围：AI 训练 / 推理集群中"报文走哪条路"的路由策略——从交换机 ASIC 的静态哈希到主机驱动的 repath、从在线自适应到离线 MILP 求解 目标读者：数据中心网络架构师、AI 训练系统工程师、想理解 NCCL / NCCLX / UEC 路由层选型的研究者
范围与边界 (Scope)
- 包含：
- 单路径与多路径路由策略（ECMP / D-mod-k / DOR / KSP）
- 自适应路由（AR / UGAL / DQPLB）
- 报文级负载均衡（Packet Spraying）
- 主机驱动 repath（PLB / PRR）与源路由（SRv6）
- 离线流量工程（TE-CCL）与可靠多路径传输（MRC）
- 按拓扑类型的选型矩阵
- 不包含：
- 拓扑结构本身的设计 → 见
02-网络拓扑/ - 集合通信算法（Ring / Tree / Halving-Doubling）→ 见
04-集合通信/ - 拥塞控制协议（DCQCN / Timely / Swift）→ 见
01-硬件互联/RDMA 章节
- 拓扑结构本身的设计 → 见
名词定义
| 名词 | 定义 |
|---|---|
| 路由算法（Routing Algorithm） | 在多路径网络中决定报文走哪条路径的策略 |
| 流（Flow） | 具有相同五元组（源 IP、目标 IP、源端口、目标端口、协议）的报文序列 |
| Flowlet | 同一流中静默间隔超过阈值时拆分出的独立转发单元 |
| ECMP（Equal-Cost Multi-Path） | 按流的五元组哈希在等价路径间分配流量 |
| D-mod-k（Destination-Mod-K） | 在 Fat-Tree 中以目的节点 ID 对 k 取模选择上行端口的确定性路由 |
| DOR（Dimension-Order Routing） | 按固定维度顺序（X → Y → Z）转发报文的静态路由 |
| 自适应路由（Adaptive Routing, AR） | 交换机感知本地队列深度实时选路的动态策略 |
| UGAL（Universal Globally Adaptive Load-balancing） | Dragonfly 上对比最短路与 Valiant 路代价的全局自适应路由 |
| Valiant 路由 | 先随机中转到中间节点再转发到目标，以路径拉长换取流量打散 |
| Packet Spraying | 每报文独立随机选路 + 接收端重排序 |
| KSP（K-Shortest Paths） | 预计算每对节点前 K 条最短路径并按哈希选择 |
| DQPLB（Dynamic QP Load Balancing） | 通信库按 CQE 反馈在多 QP 间动态分配 segment |
| TE-CCL | 将集合通信建模为 MCF + MILP 离线求解最优 chunk 路径与时序 |
| PLB / PRR | host transport 按 ECN / RTO 信号改 IPv6 Flow Label 触发 ECMP 重哈希 |
| SRv6（Segment Routing over IPv6） | 入口节点把完整路径打包成 SID list 写入 IPv6 SRH |
| MRC（Multipath Reliable Connection） | 多条并行路径上做可靠传输的 transport 层方案 |
| 死锁（Deadlock） | 多组报文互相等待对方释放缓冲区而永久阻塞的状态 |
@tbl-route-overview-terms 路由算法章节名词表
本章节所有文档默认这些名词已定义，各概念型文档只额外定义"本文新引入的名词"。
按决策位置分类
不同路由算法把"选哪条路"的决策放在不同位置——从交换机硬件到主机软件再到离线求解器。决策位置直接决定部署门槛和对硬件的依赖。
| 决策位置 | 代表方案 | 拥塞感知 | 部署门槛 |
|---|---|---|---|
| 交换机 ASIC（静态） | ECMP / E-ECMP / WCMP / D-mod-k / DOR / KSP | 无 | 低 |
| 交换机 ASIC（自适应） | AR per-flowlet / UGAL | 有（本地队列） | 中（AR ASIC） |
| 端点 NIC | Packet Spraying（UEC EV） | 无（统计均匀） | 中（UEC NIC） |
| 通信库（host） | DQPLB | 有（CQE 反馈） | 低（仅软件） |
| transport（host） | PLB / PRR | 有（ECN / RTO） | 低（Linux 6.0+） |
| 入口控制面 | SRv6 | 无（静态编程） | 中（SRv6 ASIC + IPv6） |
| 离线控制面 | TE-CCL | 无（计划已避开拥塞） | 高（MILP 求解器） |
@tbl-route-overview-position 按决策位置分类
按决策时机分类
静态路由：转发决策在报文到达前已确定，不依赖运行时网络状态。
- ECMP：按 5 元组哈希选路，流级别绑定，无状态
- D-mod-k：按目的 ID 模运算选路，对 Shift 置换零碰撞，专为 Fat-Tree 设计
- DOR：按固定维度顺序转发，天然无死锁，专为 Torus / Mesh 设计
- KSP：预计算前 $K$ 条最短路径，按哈希选路，适用于非结构化拓扑
- SRv6：入口节点编程完整路径到 SID list
- TE-CCL：离线 MILP 求解最优 chunk 路径与时序
自适应路由：观察网络状态实时选择路径。
- AR：交换机感知本地队列深度，逐报文或逐 flowlet 切换
- UGAL：Dragonfly 全局链路对比最短路与 Valiant 路的代价
- DQPLB：通信库按 CQE 反馈分配 segment 到不同 QP
- PLB / PRR：host 按 ECN / RTO 信号触发 IPv6 flow label 重哈希
随机化路由：不依赖反馈，通过报文级随机散列天然打散流量。
- Packet Spraying：逐报文独立随机选路，接收端重排序
子文档索引 (Index)
| 文档 | 一句话内容 |
|---|---|
| 3.2 ECMP | ECMP 哈希选路原理、流量碰撞与 E-ECMP / WCMP 变体 |
| 3.3 D-mod-k | D-mod-k 确定性路由、Shift 置换无阻塞证明、变体演进 |
| 3.4 自适应路由 | 逐报文 / 逐 flowlet AR、队列感知决策、乱序处理 |
| 3.5 DOR | DOR 维度顺序路由、死锁避免原理、Torus / Mesh 实现 |
| 3.6 UGAL | UGAL 最短路与 Valiant 路动态切换、Dragonfly 全局均衡 |
| 3.7 Packet Spraying | Packet Spraying 报文级散列、Ultra Ethernet EV 字段、重排序代价 |
| 3.8 KSP | K-Shortest Paths 预计算多路径、非结构化拓扑的路由方案 |
| 3.9 DQPLB | DQPLB 多平面 QP 动态负载均衡（Meta NCCLX，Llama 4 实战） |
| 3.10 TE-CCL | TE-CCL 集合通信流量工程（MILP 离线最优调度，SIGCOMM 2024） |
| 3.11 PLB / PRR | PLB / PRR 主机驱动 Repath（拥塞 + 故障双触发） |
| 3.12 SRv6 | SRv6 源路由（Microsoft Fairwater AI 集群部署） |
| 3.13 MRC | MRC Multipath Reliable Connection（OpenAI / OCP，per-packet spraying + SRv6 uSID） |
| 3.14 路由策略选型指南 | 各策略性能矩阵与按拓扑类型的选型建议 |
@tbl-route-overview-nav 子文档索引