跳到主要内容

UGAL 全局自适应负载均衡路由

UGAL（Universal Globally-Adaptive Load-balancing）是专为 Dragonfly 拓扑设计的路由策略，在最短路由（Minimal Routing）和 Valiant 非最短路路由之间动态切换，兼顾低延迟和全局负载均衡。

基本原理​

Dragonfly 拓扑背景​

Dragonfly 是一种分层拓扑：

  • 节点被分为多个 Group，组内路由器全互联（local link，带宽高）
  • Group 之间通过稀疏的全局链路（global link）连接
  • 组内任意两节点 1 跳可达；跨组通信需要经过 local link + global link + local link，共 3 跳（最短路）

全局链路是 Dragonfly 的稀缺资源，AI 训练的全局 AllReduce 容易将其打满。

两种路由模式​

最短路由（Minimal Routing）：

  • 直接经过目标 Group 的全局链路，2-3 跳到达
  • 延迟低，但当目标 Group 的全局链路已拥塞时性能退化

Valiant 路由：

  • 先将报文路由到一个随机中间 Group，再从中间 Group 路由到目标 Group
  • 共 4-5 跳，引入额外延迟，但将全局链路负载均匀分散到所有 Group 间链路
  • Valiant 路由的理论保证：即使所有节点同时通信，每条全局链路的负载不超过最大值的 $1/2$

UGAL 动态切换​

UGAL 在每个转发时刻比较两种路由的代价，选择更优的路径：

$\text{cost}_{\text{min}} = q_{\text{min}} + h_{\text{min}} \cdot w_{\text{hop}}$

$\text{cost}_{\text{val}} = q_{\text{val}} + h_{\text{val}} \cdot w_{\text{hop}}$

其中 $q$ 为目标出口队列深度，$h$ 为路径跳数，$w_{\text{hop}}$ 为跳数权重。

切换条件：

$\text{选 Minimal} \quad \text{if} \quad \text{cost}_{\text{min}} \le \text{cost}_{\text{val}} \times \text{bias}$

算法细节​

两阶段路由过程​

最短路（直达 Group 2）：

SRC (Group 0) --(local link)--> Group 0 border router
                                    |
                              (global link)
                                    |
                              Group 2 border router --(local link)--> DST

Valiant 路（经随机中间 Group 1）：

SRC (Group 0) --> Group 0 border router
                      |
                  (global link)
                      |
                  Group 1 border router --> Group 1 内部路由
                                              |
                                         (global link)
                                              |
                                         Group 2 border router --> DST

Bias 参数​

bias 参数（通常 2.0-3.0）偏向最短路：只有当最短路出口的队列深度显著高于 Valiant 路出口时，才选择绕路。这避免了轻负载时不必要的绕路引入额外延迟。

变体算法​

受限代理路由（Restrictive Proxy Routing）：

限制 Valiant 中间节点的选择范围（非任意随机，而是在特定候选集中选择）。反直觉的是，限制随机性反而提升了均衡性，因为避免了某些中间 Group 被过度选择（ScienceDirect 2025）。

Q-adaptive：

基于多智能体强化学习（MARL）的 Dragonfly 路由，每个交换机作为独立智能体，通过 Q-learning 学习最优路由策略。报告比 ECMP 提升 15-25% 吞吐量（arxiv 2403.16301），目前仍处于学术阶段。

性能特性​

场景延迟带宽利用率
轻负载（最短路主导）低（2-3 跳）中
重负载（Valiant 主导）中（4-5 跳）高（接近理论最优）
均匀 AllToAll中高（全局链路均匀分担）
全局 AllReduce（AI 训练）高风险（全局链路可能成瓶颈）需配合分层通信策略

局限：大规模 LLM 的全局 AllReduce 会压垮稀疏全局链路。Dragonfly 更适合全局 AllToAll（MoE Expert Routing）而非全局 AllReduce，后者应通过分层通信将流量尽量限制在组内。

与直接路由的权衡​

维度最短路ValiantUGAL
延迟最低（无拥塞时）较高（+1-2 跳）动态平衡
负载均衡差（热门链路拥塞）理论最优接近最优
全局状态需求无无（随机中间节点）需要本地队列深度
全局链路利用率集中分散自适应

UGAL 是 Minimal 的低延迟和 Valiant 的高均衡性之间的工程折中：在网络空闲时走最短路（低延迟），在拥塞时自动切换 Valiant 绕路（高吞吐）。

适用场景与局限​

适用场景：

  • Dragonfly 拓扑（HPE Slingshot、部分 HPC 超算）
  • 流量模式多变、局部 AllReduce + 全局 AllToAll 混合的 AI 工作负载
  • 需要在 Dragonfly 的低硬件成本和相对高性能之间取得平衡的场景

局限：

  • 仅适用于 Dragonfly 拓扑，无法直接用于 Fat-tree 或 Torus
  • 全局状态感知（队列深度）仍是局部信息，全局最优需要 TE-CCL 等集中式方案
  • 大规模 LLM 全局 AllReduce 场景下仍存在全局链路瓶颈，需配合分层通信策略

参考资料​