路由算法总览
在多路径互联网络中，同一对源-目标节点之间往往存在多条可用路径。路由算法决定报文应走哪条路径——这个选择直接影响链路利用率、拥塞分布和通信延迟。对于 AI 训练集群，AllReduce / AllToAll 等集合通信的流量模式高度规律，路由策略选择不当会导致链路热点、带宽浪费，进而成为训练吞吐的瓶颈。
名词定义
| 名词 | 定义 |
|---|---|
| 路由算法（Routing Algorithm） | 在多路径网络中决定报文走哪条路径的策略，直接影响链路利用率、拥塞分布和通信延迟 |
| 流（Flow） | 具有相同五元组（源 IP、目标 IP、源端口、目标端口、协议）的一组报文序列 |
| Flowlet | 同一条流中两个突发之间的静默间隔超过阈值时，被视为独立的转发单元，用于 flowlet 级负载均衡 |
| ECMP（Equal-Cost Multi-Path） | 对具有相同代价的多条路径按流的五元组哈希分配流量，每条流绑定一条固定路径 |
| DOR（Dimension-Order Routing） | 按固定维度顺序（X → Y → Z）转发报文的静态路由策略，天然无死锁，专为 Torus/Mesh 设计 |
| 自适应路由（Adaptive Routing） | 交换机在转发时观察出口队列深度，实时选择最空闲路径的动态路由策略 |
| UGAL（Universal Globally Adaptive Load-balancing） | 在 Dragonfly 拓扑上对比最短路与 Valiant 路的代价，动态切换以均衡全局链路负载的路由算法 |
| Valiant 路由 | 先将报文随机中转到一个中间节点再转发到目标，以随机化流量分布换取全局均衡，代价是路径拉长 |
| Packet Spraying | 每个报文独立随机选路（不绑定流），接收端重排序，带宽利用率最高但引入乱序开销 |
| 死锁（Deadlock） | 多组报文互相等待对方释放缓冲区而永久阻塞的状态；DOR 通过维度有序转发避免死锁 |
分类与核心概念
路由算法按决策时如何利用网络状态分为三类：
静态路由：转发决策在报文到达前已确定，不依赖运行时网络状态。
- ECMP：按 5 元组哈希选路，流级别绑定，无状态，实现最简单
- DOR：按固定维度顺序（X → Y → Z）转发，天然无死锁，专为 Torus/Mesh 设计
自适应路由：交换机在转发时观察出口队列深度，实时选择最空闲路径。
- 自适应路由（AR）：逐报文或逐 flowlet 感知本地拥塞并切换路径
- UGAL：在 Dragonfly 全局链路上对比最短路与 Valiant 路的代价，动态切换
随机化路由：不依赖拥塞反馈，通过报文级随机散列天然打散流量。
- Packet Spraying：每个报文独立随机选路，接收端重排序，带宽利用率最高
横向对比
| 算法 | 决策粒度 | 状态需求 | 适配拓扑 | 拥塞应对 | 实现复杂度 |
|---|---|---|---|---|---|
| ECMP | 流（flow） | 无状态 | Fat-tree、Clos | 无感知，依赖流量均匀分布 | 低（通用 ASIC） |
| DOR | 报文 | 无状态 | Torus、Mesh | 无感知，路径唯一 | 低（维度感知转发） |
| 自适应路由（AR） | 报文 / flowlet | 本地队列深度 | Fat-tree、InfiniBand | 实时规避拥塞出口 | 中（专用 AR ASIC） |
| UGAL | 报文 | 本地 + 全局链路队列 | Dragonfly | 切换 Valiant 路绕开热点全局链路 | 中高（需读取全局链路状态） |
| Packet Spraying | 报文 | 无状态 | Fat-tree | 统计均摊，无主动感知 | 中（NIC 重排序缓冲） |
文档导航
| 文档 | 内容 |
|---|---|
| 01-ecmp.md | ECMP 哈希选路原理、流量碰撞问题及 E-ECMP / WCMP 改进变体 |
| 02-自适应路由.md | 逐报文与逐 flowlet 自适应路由、队列感知决策流程及乱序处理 |
| 03-dor.md | DOR 维度顺序路由、死锁避免原理及在 Torus/Mesh 上的实现 |
| 04-ugal.md | UGAL 最短路与 Valiant 路动态切换策略及 Dragonfly 全局链路负载均衡 |
| 05-packet-spraying.md | Packet Spraying 报文级散列、Ultra Ethernet EV 字段机制及重排序代价 |
| 06-选型指南.md | 各策略性能矩阵与按拓扑类型的选型建议 |