UGAL

Dragonfly 上如何在最短路与 Valiant 路之间动态切换

核心要点：

• UGAL 在 Minimal 路（低延迟）与 Valiant 路（高均衡）之间按代价动态切换
• 代价函数综合队列深度 + 跳数惩罚（$w_{\text{hop}}$），bias 偏向最短路
• UGAL-L 用本地队列、UGAL-G 用全局信息，工程上以 UGAL-L 为主
• Dragonfly 的稀缺全局链路是 UGAL 的核心优化对象

UGAL（Universal Globally-Adaptive Load-balancing）是 Dragonfly 拓扑的标准路由方案：在最短路由（Minimal Routing）和 Valiant 非最短路之间动态切换，兼顾低延迟和全局负载均衡。由 Kim 等[1]在 ISCA 2008 与 Dragonfly 拓扑一同提出。

为什么 Dragonfly 需要专门的路由策略？

核心问题：既然 Dragonfly 的组内全互联已经提供多路径，为什么还需要 UGAL 这种动态切换？瓶颈在哪？

Dragonfly 是一种分层拓扑：

• 节点被分为 $g$ 个 Group，组内路由器全互联（local link，带宽高）
• Group 之间通过稀疏的全局链路（global link）连接，每对 Group 之间通常只有 1-2 条全局链路
• 组内任意两路由器 1 跳可达（全互联）；跨组通信需要经过 local link + global link + local link

全局链路是 Dragonfly 的稀缺资源——组内链路数量为 $O(p^2)$（$p$ 为组内路由器数），而每个 Group 的全局链路数仅为 $O(g)$（连接到其他 $g-1$ 个 Group），AI 训练的全局 AllReduce 容易将其打满。

Minimal 与 Valiant 各自的取舍是什么？

最短路由（Minimal Routing）

报文直接经过连接源 Group 和目标 Group 的全局链路：

SRC --> 源 Group border router --(global link)--> 目标 Group border router --> DST

跳数分析（源和目标在不同 Group）：

$$\begin{equation} h_{\text{min}} = h_{\text{local,src}} + 1 + h_{\text{local,dst}} \label{eq:route-ugal-hops-min} \end{equation}$$

其中 $h_{\text{local,src}}$ 是源节点到源 Group 的 border router 的跳数（0 或 1），中间的 1 是全局链路，$h_{\text{local,dst}}$ 是目标 Group 的 border router 到目标节点的跳数（0 或 1）。典型值：2-3 跳。

问题：当多条流的目标 Group 相同时，它们竞争同一条全局链路，导致该链路拥塞而其他全局链路空闲。

Valiant 路由

报文先路由到一个随机选择的中间 Group $R$，再从 $R$ 路由到目标 Group：

SRC --> 源 Group border --> (global link) --> Group R --> (global link) --> 目标 Group --> DST

跳数：

$$\begin{equation} h_{\text{val}} = h_{\text{local,src}} + 1 + h_{\text{local,R}} + 1 + h_{\text{local,dst}} \label{eq:route-ugal-hops-val} \end{equation}$$

典型值：3-5 跳，比最短路多 1-2 跳。

Valiant 的负载均衡保证：中间 Group $R$ 从所有 $g$ 个 Group 中均匀随机选取。对于任意流量模式，每条全局链路承受的期望负载为总流量的 $1/g$——这是均匀分布的结果。即使在最坏情况下（所有节点同时向同一目标通信），Valiant 也能将全局链路的最大负载限制在最优值的 2 倍以内（因为每个报文使用 2 条全局链路而非 1 条）。

代价：每个报文消耗 2 条全局链路带宽（源->中间 + 中间->目标），网络整体吞吐量上限减半。在轻负载时，这种额外的带宽消耗和延迟是浪费的。

UGAL 怎么决定该走最短路还是绕路？

核心问题：拿到队列深度信息后，UGAL 需要一个能"低延迟时偏向 Minimal、拥塞时切换 Valiant"的判据。这个判据是什么？

UGAL 的核心思想：每个转发时刻同时评估最短路和 Valiant 路的代价，选择代价更低的路径。代价综合考虑拥塞程度（队列深度）和路径长度（跳数）。

代价函数

$$\begin{align} \text{cost}_{\text{min}} &= q_{\text{min}} + h_{\text{min}} \cdot w_{\text{hop}} \label{eq:route-ugal-cost-min} \\ \text{cost}_{\text{val}} &= q_{\text{val}} + h_{\text{val}} \cdot w_{\text{hop}} \label{eq:route-ugal-cost-val} \end{align}$$

其中：

• $q_{\text{min}}$：最短路出口端口的队列深度（字节）
• $q_{\text{val}}$：Valiant 路出口端口（通往随机中间 Group）的队列深度（字节）
• $h_{\text{min}}$、$h_{\text{val}}$：对应路径的剩余跳数
• $w_{\text{hop}}$：跳数权重（将跳数惩罚转换为与队列深度同量纲的代价）

切换条件

$$\begin{equation} \text{route} = \begin{cases} \text{Minimal} & \text{if } \text{cost}_{\text{min}} \le \text{cost}_{\text{val}} \times \text{bias} \\ \text{Valiant} & \text{otherwise} \end{cases} \label{eq:route-ugal-switch} \end{equation}$$

bias 参数（通常 2.0-3.0）偏向最短路：只有当最短路出口的队列深度显著高于 Valiant 路出口时，才选择绕路。

决策流程

报文到达源 Group 的路由器，目标在 Group D
  |
  v
确定最短路出口端口 p_min（通往 Group D 的全局链路）
随机选择中间 Group R，确定 Valiant 出口端口 p_val（通往 Group R 的全局链路）
  |
  v
读取队列深度 q_min = queue(p_min), q_val = queue(p_val)
  |
  v
计算代价：
  cost_min = q_min + h_min * w_hop
  cost_val = q_val + h_val * w_hop
  |
  v
cost_min <= cost_val * bias ?
  |
  +-- 是 --> 选最短路，从 p_min 转发
  |
  +-- 否 --> 选 Valiant 路，从 p_val 转发
              （报文头标记中间 Group R，中间节点按最短路转发到 Group D）

数值示例

场景：Dragonfly 拓扑，16 个 Group，组内 8 个路由器。源在 Group 0，目标在 Group 5。设 $w_{\text{hop}} = 256$ 字节，bias = 2.5。

情况 1：轻负载

p_min（通往 Group 5）: q_min = 512 B,  h_min = 3
p_val（通往随机 Group 9）: q_val = 256 B, h_val = 5

cost_min = 512 + 3 * 256 = 1280
cost_val = 256 + 5 * 256 = 1536

cost_min (1280) <= cost_val * bias (1536 * 2.5 = 3840)?  --> 是
选择：最短路（延迟低，3 跳）

情况 2：重负载（Group 5 方向拥塞）

p_min（通往 Group 5）: q_min = 8192 B,  h_min = 3  <-- 拥塞
p_val（通往随机 Group 9）: q_val = 256 B, h_val = 5

cost_min = 8192 + 3 * 256 = 8960
cost_val = 256 + 5 * 256 = 1536

cost_min (8960) <= cost_val * bias (1536 * 2.5 = 3840)?  --> 否
选择：Valiant 路（绕行 Group 9，避开拥塞）

参数调优

$w_{\text{hop}}$ 的作用：将跳数差异转换为队列深度的等价代价。$w_{\text{hop}}$ 越大，UGAL 越倾向选择跳数少的最短路（即使队列稍深）；$w_{\text{hop}}$ 越小，UGAL 越敏感于队列差异。

bias 的作用：bias > 1 偏向最短路，避免轻负载时不必要的绕路。bias = 1 时无偏好，退化为纯代价比较。实际部署中 bias = 2.0-3.0 是经验最优范围。

极端情况：

• bias -> $\infty$：退化为纯最短路由（从不绕路）
• bias = 1 且 $w_{\text{hop}}$ = 0：退化为纯队列深度比较（总是选最短队列，忽略跳数）

UGAL 有哪些工程变体？

UGAL-L vs UGAL-G

原始 UGAL 论文[1]定义了两种信息范围：

• UGAL-L（Local）：仅使用本路由器出口端口的队列深度。信息获取零开销，但视野有限——无法感知下游拥塞
• UGAL-G（Global）：使用路径上所有链路的队列深度之和。需要全局信息收集机制，但决策更准确

实际部署中以 UGAL-L 为主（硬件可直接读取本地队列寄存器），UGAL-G 需要额外的状态同步开销。

受限代理路由（Restrictive Proxy Routing）

限制 Valiant 中间 Group 的选择范围（非从所有 $g$ 个 Group 中随机选，而是从特定候选集中选择）。反直觉的是，限制随机性反而提升了均衡性——避免了某些中间 Group 因拓扑不对称而被过度选择[2]。

Q-adaptive

基于多智能体强化学习（MARL）的 Dragonfly 路由，每个交换机作为独立智能体，通过 Q-learning 学习最优路由策略。报告比传统自适应路由提升最多 10.5% 系统吞吐量[3]，目前仍处于学术阶段。

UGAL 在不同负载下的表现？

场景	延迟	带宽利用率	主导路由模式
轻负载	低（1-3 跳）	中	Minimal
重负载	中（3-5 跳）	高（接近理论最优）	Valiant
均匀 AllToAll	中	高（全局链路均匀分担）	混合
全局 AllReduce（AI 训练）	高风险	需配合分层通信策略	Minimal 易拥塞

@tbl-route-ugal-01 性能特性：场景、延迟、带宽利用率 等

与纯 Minimal / 纯 Valiant 相比 UGAL 取舍在哪？

维度	Minimal	Valiant	UGAL
延迟	最低（无拥塞时）	较高（+1-2 跳）	动态平衡
负载均衡	差（热门链路拥塞）	理论最优	接近最优
全局链路带宽消耗	1x	2x（每包用 2 条全局链路）	1x-2x（动态）
全局状态需求	无	无（随机中间节点）	需要本地队列深度

@tbl-route-ugal-02 与 Minimal / Valiant 的权衡：维度、Minimal、Valiant 等

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

何时该用 UGAL，何时不该？

适用场景：

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

局限：

• 仅适用于 Dragonfly 拓扑，无法直接用于 Fat-tree 或 Torus
• UGAL-L 的局部信息可能导致次优决策（无法感知下游拥塞）
• Valiant 路消耗 2x 全局链路带宽，重负载时网络整体吞吐上限下降
• 大规模 LLM 全局 AllReduce 场景下仍存在全局链路瓶颈，需配合分层通信策略

Takeaway

知识点	核心结论
Dragonfly 瓶颈	全局链路稀缺（$O(g)$/Group），单一目标 Group 易拥塞
Minimal 路	2-3 跳直达，延迟低但热点集中
Valiant 路	随机中间 Group 中转，每包用 2 条全局链路换均衡
UGAL 决策	$\text{cost} = q + h \cdot w_{\text{hop}}$，bias > 1 偏最短路
UGAL-L vs UGAL-G	本地队列 vs 全局信息，工程主流 UGAL-L（零同步开销）
经验参数	bias = 2.0-3.0，$w_{\text{hop}}$ 决定跳数 / 队列的等价换算
适用拓扑	仅 Dragonfly；HPE Slingshot 等 HPC 超算的默认方案

参考资料

1. Kim et al., Technology-Driven, Highly-Scalable Dragonfly Topology, ISCA 2008. https://doi.org/10.1145/1394608.1382129
2. Improving Dragonfly via Restrictive Proxy Routing, Computer Networks, 2025. https://www.sciencedirect.com/science/article/pii/S1389128625003019
3. Q-adaptive: MARL-Based Routing on Dragonfly, arXiv:2403.16301. https://arxiv.org/abs/2403.16301

延伸阅读

• LIA: Latency-Improved Adaptive Routing for Dragonfly, ACM TACO 2025. https://dl.acm.org/doi/10.1145/3711914