D-mod-k

Fat-Tree 上如何用模运算实现确定性无阻塞路由

核心要点：

• D-mod-k 用目的节点 ID 的模运算选上行端口，决策只依赖目的、不依赖源
• 对 Shift 置换流量数学证明零碰撞（Zahavi CCIT #776, 2010）
• 代价：上行链路在非 Shift 模式下可能不均衡
• OpenSM ftree 路由引擎是其工程实现，NVIDIA ar_ftree 进一步混合自适应路由

D-mod-k 用目的节点编号的模运算确定性选择 Fat-Tree 上行端口，在特定流量模式下数学保证无阻塞。与 ECMP 哈希选路（见 3.2 ECMP）的伪随机性相对，D-mod-k 的负载分布是可代数计算的精确量。

Fat-Tree 中任意源-目的对的最短路径分两阶段：上行到源/目的的最近公共祖先（NCA），下行到目的节点。下行路径由 NCA 位置唯一确定，路由的关键自由度在上行端口选择。

D-mod-k 的路由公式是什么？

核心公式

D-mod-k 由 Eitan Zahavi（Technion / Mellanox）在 2010 年形式化提出[1]。核心思想：在 Fat-Tree 的每一层，用目的节点编号 $d$ 的不同位段做模运算，选择上行端口。

对于标准 $k$-ary $n$-tree（每个交换机有 $k$ 个上行端口 + $k$ 个下行端口），在第 $l$ 层（$l = 0$ 为叶交换机层）选择上行端口：

$$\begin{equation} P_U^{(l)}(d) = \left\lfloor \frac{d}{k^l} \right\rfloor \bmod k \label{eq:route-dmodk-port} \end{equation}$$

其中：

• $d$：目的节点的全局编号
• $k$：交换机每侧的端口数（上行或下行）
• $l$：当前交换机所在层级（叶交换机为 0）

对于更一般的 PGFT（Parallel Ports Generalized Fat-Tree），每层有不同的上行连接数 $w_l$ 和并行链路数 $p_l$：在第 $l$ 层（$l = 1, \ldots, h-1$）向目的 $j$ 选择的上行端口编号为（Zahavi CCIT #776 公式 (3)）：

$$\begin{equation} q_l(j) = \left\lfloor \frac{j}{\prod_{k=1}^{l} w_k} \right\rfloor \bmod (w_{l+1} \cdot p_{l+1}) \label{eq:route-dmodk-pgft} \end{equation}$$

其中：

• $w_k$：第 $k$ 层节点向上连接的不同上层节点数
• $p_k$：第 $k-1$ 层与第 $k$ 层节点之间的并行链路数
• $h$：树的总层数

标准 $k$-ary $n$-tree 是 PGFT 的特例（$w_k = k$，$p_k = 1$，所有层一致），代入 $\eqref{eq:route-dmodk-pgft}$ 即退化为 $\eqref{eq:route-dmodk-port}$。

关键性质：端口选择只依赖目的 $j$，不依赖源。同一层的所有交换机对同一个目的选择相同编号的上行端口（Zahavi CCIT #776 §IV.B）。

两阶段路由流程

源节点 s 发送报文到目的节点 d
  |
  v
[上行阶段] 逐层向上, 每层按 D-mod-k 公式选上行端口
  |  层 0: port = floor(d / 1) mod k     -- 用 d 的最低 k 进制位
  |  层 1: port = floor(d / k) mod k     -- 用 d 的次低 k 进制位
  |  ...
  |  直到到达 NCA (最近公共祖先)
  |
  v
[下行阶段] 从 NCA 向下, 路径由拓扑结构唯一确定 (无选择自由度)
  |
  v
到达目的节点 d

数值示例

以 4-ary 2-tree（$k=4$, $n=2$，共 16 个终端节点）为例：

目的 $d$	层 0 端口 $d \bmod 4$	层 1 端口 $\lfloor d/4 \rfloor \bmod 4$
0	0	0
1	1	0
2	2	0
3	3	0
4	0	1
5	1	1
6	2	1
7	3	1
15	3	3

@tbl-route-dmodk-example 4-ary 2-tree 中 D-mod-k 端口选择示例

层 0 的 4 个连续目的（如 0-3）恰好映射到 4 个不同的端口编号，这是零碰撞的直接原因。下一节将证明这一性质在每一层都成立。

为什么 D-mod-k 在 Shift 置换下严格零碰撞？

核心问题：ECMP 用哈希只能给概率保证，D-mod-k 凭什么用一个简单的模运算就拿到确定性的无阻塞结论？

下文证明严格按 Zahavi CCIT #776 §V 的引理-定理结构组织，使用 PGFT 通用形式 $\eqref{eq:route-dmodk-pgft}$。

符号约定（沿用 PGFT 标准）：

• $m_l$：第 $l$ 层交换机的下行端口数（每个第 $l$ 层节点有 $m_l$ 个子节点）
• $w_l$：第 $l$ 层交换机的上行链路数（连到上一层 parent group 的链路数）
• $p_l$：第 $l$ 层 parent group 的大小（每个 group 包含 $p_l$ 个第 $l$ 层节点）
• $K$：交换机端口总数

RLFT 是 PGFT 加上"等分带宽 $m_l p_l = w_{l+1} p_{l+1}$"和"端口数恒定 $K = m_l p_l = w_{l+1} p_{l+1}$"两个工程约束的子类。在 RLFT 下，$w_1 = m_1$（叶交换机的下行端点数等于其上行链路数）。

Shift 置换流量模式

Shift 置换定义为：节点 $i$ 发送给节点 $(i + s) \bmod N$，$s \in \{1, \ldots, N-1\}$。该置换的源-目的对集合为 $\{(n_i, n_{(i+s) \bmod N})\}$。Ring AllReduce 每步通信、Halo Exchange、$\text{AllToAll}$ 的 Bruck 算法各阶段都是 Shift 的实例。

上行无阻塞（Theorem 1）

Lemma 1（经过节点的目的序列）：经过节点 $(l, b_1, \ldots, b_h)$ 上行端口的目的索引集合是等差数列

$$\begin{equation} J_{(l, b_1, \ldots, b_h)} = \left\{ \sum_{t=1}^{l} b_t \prod_{k=1}^{t-1} w_k + i \prod_{k=1}^{l} w_k \;\middle|\; 0 \le i < N \Big/ \prod_{k=1}^{l} w_k \right\} \label{eq:route-dmodk-lemma1} \end{equation}$$

证明思路（按层数 $l$ 归纳）：

• 基础 $l=0$：$\eqref{eq:route-dmodk-lemma1}$ 在 $l=0$ 退化为公差 1、长度 $N$ 的等差数列，即叶交换机视角下所有 $N$ 个目的的编号（其中 $m_1$ 个目的对应本叶下挂端点不上行，其余目的按下文归纳步上行分流）。RLFT 下 $w_1 = m_1$，使叶下挂端点编号本身也构成 $m_1$ 个连续整数，可作为后续递推的初始结构
• 归纳步：根据 PGFT 连接规则，从第 $l$ 层节点到第 $l+1$ 层父节点的端口编号 $q = \lfloor j / \prod_{k=1}^{l} w_k \rfloor \bmod w_{l+1}$。所有 $b_{l+1} = q$ 的子节点把同一公差为 $\prod_{k=1}^{l} w_k$ 的等差子序列汇聚到父节点，父节点的目的序列公差变为 $\prod_{k=1}^{l+1} w_k$

Lemma 2（长度等于上行端口数的连续子序列无碰撞）：令 $C_0 = \sum_{t=1}^{l} b_t \prod_{k=1}^{t-1} w_k$，则 $\eqref{eq:route-dmodk-lemma1}$ 中的目的索引可写为 $j = C_0 + i \cdot \prod_{k=1}^{l} w_k$。将此代入 PGFT 公式 $\eqref{eq:route-dmodk-pgft}$ 第 $l$ 层选端口：

$$\begin{equation} q_l(j) = \left\lfloor \frac{C_0 + i \cdot \prod_{k=1}^{l} w_k}{\prod_{k=1}^{l} w_k} \right\rfloor \bmod (w_{l+1} p_{l+1}) = \left( \left\lfloor \frac{C_0}{\prod_{k=1}^{l} w_k} \right\rfloor + i \right) \bmod (w_{l+1} p_{l+1}) \label{eq:route-dmod-k-quotient-recursive} \end{equation}$$

记 $C = \lfloor C_0 / \prod_{k=1}^{l} w_k \rfloor$，得

$$\begin{equation} q_l(j) = (C + i) \bmod (w_{l+1} p_{l+1}) \label{eq:route-dmod-k-quotient-direct} \end{equation}$$

其中 $C$ 是与 $i$ 无关的常数。$w_{l+1} p_{l+1}$ 个连续整数对 $w_{l+1} p_{l+1}$ 取模恰好遍历 $\{0, 1, \ldots, w_{l+1} p_{l+1} - 1\}$ 各一次——每个上行端口恰好分配到一个目的。在 RLFT 下 $w_{l+1} p_{l+1} = K$，即"连续 $K$ 个目的覆盖所有上行端口"。

Lemma 3（环绕情况）：Shift 置换 $s$ 可能让经过某节点的目的序列从最大索引 $N-1$ 环绕回 0。需证：环绕处的端口分配仍与 Lemma 2 一致。

由 Lemma 1，经过 $l$ 层节点上行的目的序列总长为 $|J| = N / \prod_{k=1}^{l} w_k$。在 RLFT 下 $N = \prod_{k=1}^{h} m_k \cdot p_h$，且 $w_k p_k = m_{k-1} p_{k-1}$（带宽守恒）。展开：

$$\begin{equation} |J| = \frac{\prod_{k=1}^{h} m_k \cdot p_h}{\prod_{k=1}^{l} w_k} = \prod_{k=l+1}^{h} m_k \cdot p_h \cdot \prod_{k=1}^{l} \frac{m_k}{w_k} \label{eq:route-dmod-k-flow-count} \end{equation}$$

由 $w_k p_k = m_{k-1} p_{k-1}$ 与 RLFT 下 $m_l p_l = w_{l+1} p_{l+1}$，每项 $m_k / w_k$ 均为正整数比例。整理可见 $|J|$ 是 $w_{l+1} p_{l+1}$ 的整数倍。所以将目的序列按"每段 $w_{l+1} p_{l+1}$"分块，最后一段在环绕处也是完整段——Lemma 2 对每个完整段独立成立，环绕处不出现"半段碰撞"。

Lemma 4（每个交换机的目的数 $\le K$）：第 $l$ 层交换机服务 $\prod_{k=1}^{l} m_k$ 个叶端点；在一次 Shift 阶段，这些叶发送的目的索引按 $\prod_{k=1}^{l} w_k$ 为公差稀疏化，单个 Shift 阶段经过该交换机的目的数表达式见 Zahavi CCIT #776 §V Lemma 4，RLFT 约束 $K = m_l p_l = w_{l+1} p_{l+1}$ 下化简结果为 $K$，即恰好等于交换机的上行端口数。

注：此处直接引用 Zahavi #776 §V 的 Lemma 4 化简结果。完整代数推导（约 5-6 步带宽守恒递推）请参见原论文 §V。

Theorem 1（上行无阻塞）：由 Lemma 2 知，任意连续 $w_{l+1} p_{l+1}$ 个目的索引恰好遍历所有上行端口编号各一次；由 Lemma 3 知，Shift 引起的目的序列环绕不破坏这一覆盖性；由 Lemma 4 知，单 Shift 阶段经过每个交换机的目的数恰好等于上行端口数 $K$。三者合起来给出：RLFT 上任意 Shift 置换下，每个上行端口最多承载一个目的的流量。

下行无阻塞（Theorem 2）

Lemma 5（流量汇聚单一顶层交换机）：对任意目的 $j$，所有源节点的流量在上行阶段汇聚到唯一的顶层交换机。

证明按层数归纳：

• 基础：从叶交换机 $(0, s_1, \ldots, s_h)$ 选上行端口 $q = j \bmod (w_1 p_1)$，根据 PGFT 连接规则，连到第 1 层节点 $(1, b_1, \ldots, b_h)$，其中 $b_1 = \lfloor q / p_1 \rfloor$。由于 $q$ 仅依赖 $j$，$b_1$ 也仅依赖 $j$，与源 $s$ 无关
• 归纳步：假设第 $l$ 层交换机的前 $l$ 位元组仅由 $j$ 决定。第 $l$ 层向第 $l+1$ 层选上行端口 $q_l(j)$（公式 $\eqref{eq:route-dmodk-pgft}$ 只依赖 $j$），PGFT 连接规则给出 $b_{l+1} = \lfloor q_l(j) / p_{l+1} \rfloor$，因此第 $l+1$ 层交换机的前 $l+1$ 位元组也仅由 $j$ 决定

归纳到顶层（$l = h$）即得：所有源到 $j$ 的流量经过同一顶层交换机。

Lemma 6（顶层交换机服务的目的数 $\le$ 端口数）：直接应用 Lemma 1 的目的集合大小公式于顶层节点。

Theorem 2（下行无阻塞）：由 Lemma 5，所有到目的 $j$ 的流量汇聚到唯一顶层交换机；由 Lemma 6，顶层交换机服务的目的数不超过其下行端口数，保证下行不出现"目的数 > 端口数"的过载；从顶层交换机到 $j$ 的下行路径在 PGFT 中沿最短路径唯一确定——每个交换机的每个下行端口对应一个明确的子树，到 $j$ 的流量只走向包含 $j$ 的那一个子树。综合三点：每个下行端口最多承载一个目的的流量。

结论

综合 Theorem 1 + Theorem 2：对 RLFT 上的任意 Shift 置换，D-mod-k 路由保证每条上行和下行链路最多承载一个源-目的对的流量。这是 D-mod-k 在 Shift 模式下相对 ECMP 的核心优势——确定性的零碰撞，不依赖概率假设。

零极化的代数本质

D-mod-k 的均匀性来自 Lemma 2 中"连续 $w_{l+1} p_{l+1}$ 个整数对 $w_{l+1} p_{l+1}$ 取模恰好遍历所有余数"这一代数结论。

与 ECMP 的对比：ECMP 依赖哈希函数的伪随机均匀性，需用 birthday paradox 估计碰撞概率（见 $\href{/interconnect/路由算法/ecmp}{\text{(3.2)}}$）；D-mod-k 在 Shift 模式下不存在碰撞概率，每条链路负载是精确可计算的代数量。

D-mod-k 与 ECMP 在哪些维度根本不同？

维度	D-mod-k	ECMP
决策依据	$d \bmod k$（确定性）	5 元组哈希（伪随机）
路由粒度	基于目的（所有到同一目的的流走同一路径）	基于流（同目的不同连接可走不同路径）
Shift 置换下的负载	数学证明无阻塞	取决于哈希碰撞概率（见 $\href{/interconnect/路由算法/ecmp}{\text{(3.2)}}$）
多层极化	不同层使用 $d$ 的不同位段，天然避免	各层独立哈希，相同种子时严重极化
非 Shift 流量	上行可能不均衡（多个源到同一目的竞争同一端口）	哈希分散，但碰撞仍可能
状态需求	无状态（纯算术）	无状态（纯哈希）
拓扑要求	仅 Fat-Tree / PGFT	任意多路径拓扑

@tbl-route-dmodk-vs-ecmp D-mod-k 与 ECMP 对比

在 Shift 之外的随机置换流量下，D-mod-k 与 ECMP 的吞吐率均低于理论上限，但 D-mod-k 的目的级确定性分配仍优于哈希的概率分配。Chrysos 等[2]通过仿真比较了两者在不同流量模式下的相对差距，但具体数值依赖拓扑参数（端口数、层数）和流量类型——读者引用前应回原文核对实验条件。

何时该用 D-mod-k，何时不该？

适用场景

• InfiniBand Fat-Tree 集群：OpenSM 的 ftree 路由引擎实现了 D-mod-k 原理（Zahavi 同时是 D-mod-k 论文作者和 ftree 引擎开发者）[3][4]。OpenSM 文档本身未使用"D-mod-k"名词，但 ftree 引擎优化 shift 通信模式的行为与 D-mod-k 一致
• Shift/AllReduce 为主的 HPC 工作负载：Ring AllReduce 通信模式是 Shift 置换的实例，D-mod-k 在此场景达到理论最优
• 需要可预测、可分析的流量分布：确定性路由的负载分布可以精确计算，不依赖概率分析

局限

上行链路不均衡

D-mod-k 只保证下行链路均匀。上行端口选择只依赖目的 $j$，所以同一层的所有交换机对相同目的选择相同编号的上行端口；多个源同时向同一目的发送时，流量在每一层汇聚后共享同一条下行路径，目的所在的下行端口和叶交换机入端口成为瓶颈[5]。

Slimmed Fat-Tree 上负载失衡

当 Fat-Tree 做了超售（oversubscription），即上行带宽 < 下行带宽时（即 RLFT 的等分带宽约束 $m_l p_l = w_{l+1} p_{l+1}$ 被破坏），Lemma 3 的整除性不再成立，D-mod-k 的均匀性失效。Yuan 等[6]分析了 slimmed Fat-Tree 下 D-mod-k 的负载失衡，并提出 Round-Robin Routing (RRR) 作为改进。

故障/降级拓扑下表现差

D-mod-k 的公式依赖完整的 Fat-Tree 结构。节点或链路故障后，拓扑不再对称，模运算的均匀分配性质被破坏。Dmodc[7]专门针对这一问题提出改进。

仅适用于 Fat-Tree 拓扑族

D-mod-k 依赖 Fat-Tree 的层级结构和等分带宽性质，无法用于 Torus、Dragonfly、HyperX 等非 Fat-Tree 拓扑。

D-mod-k 有哪些工程演进？

S-mod-k（源模 k 路由）

与 D-mod-k 对称，S-mod-k 用源节点编号做模运算选择上行端口。Chrysos 等[8]证明对于置换流量模式，S-mod-k 和 D-mod-k 的竞争分布完全等价。S-mod-k 曾用于 CM-5 等早期并行计算机。

r-NCA（随机化 NCA 选择）

Chrysos 等[8]提出 r-NCA-u / r-NCA-d，用随机映射替代简单的模运算，打破特定流量模式与模运算的病态对齐。D-mod-k 和 S-mod-k 是 r-NCA 的特例。

Dmodc（降级 Fat-Tree 适配，2023）

Gliksberg 等[7]提出 Dmodc，保持 D-mod-k 的闭合算术公式，但将固定的 $k$ 替换为基于代价的动态分隔数，适应降级/故障拓扑。已部署在 Atos BXI 8490 节点生产网络上，在数千个同时故障的条件下仍保持高质量路由。

ftree + Adaptive Routing（现代混合方案）

NVIDIA Quantum InfiniBand 支持 ar_ftree 模式[4]：下行使用 ftree（D-mod-k 原理）保证均匀，上行使用自适应路由（AR）根据队列深度动态选路。这种混合方案弥补了 D-mod-k 上行不均衡的局限，是当前 AI/HPC 集群的主流部署方式。

D-mod-k 对性能建模有什么价值？

D-mod-k 对性能建模的价值在于可精确计算的负载分布：

• ECMP：需要概率分析（哈希碰撞概率、birthday paradox），负载分布是统计量
• D-mod-k：给定拓扑和流量矩阵，每条链路的负载可以精确求解——直接由 $\eqref{eq:route-dmodk-port}$ 计算得到

在 Fat-Tree 上做 Shift 置换的通信建模时，D-mod-k 可以直接给出"每条链路恰好承载一个流"的结论，无需蒙特卡洛模拟或概率估计。

开放问题

核心问题：D-mod-k 尚未解决的关键开放问题有哪些？

• D-mod-k 在 MoE AllToAll 流量模式下的负载分布。AllToAll 不是 Shift 置换，Zahavi 的无阻塞证明不适用——需要定量分析实际不均衡程度
• ftree + AR 混合模式的有效带宽建模：下行 D-mod-k 确定性 + 上行 AR 动态选路，两者耦合下的吞吐如何估算

Takeaway

知识点	核心结论
D-mod-k 公式	第 $l$ 层选端口 $\lfloor d/k^l \rfloor \bmod k$，只依赖目的不依赖源
无阻塞保证	Shift 置换 + RLFT 下数学证明零碰撞（每条链路最多一个源-目的对）
vs ECMP	确定性 vs 伪随机；目的级 vs 流级；零极化 vs 多层极化
主要局限	上行可能不均衡；slimmed Fat-Tree / 故障拓扑下均匀性失效；仅 Fat-Tree
工程实现	OpenSM ftree 引擎；现代部署用 ar_ftree（下行 D-mod-k + 上行 AR）
建模价值	负载分布是精确代数量，不需概率分析

参考资料

1. Zahavi, D-Mod-K Routing Providing Non-Blocking Traffic for Shift Permutations on Real Life Fat Trees, CCIT Report #776, Technion, 2010. https://ece.technion.ac.il/wp-content/uploads/2021/01/publication_776.pdf
2. Chrysos et al., High Performance Multipath Routing for Datacenters, HPSR 2014. https://research.ibm.com/publications/high-performance-multipath-routing-for-datacenters
3. Zahavi et al., Optimized InfiniBand Fat-tree Routing for Shift All-To-All Communication Patterns, CPE 2010. https://onlinelibrary.wiley.com/doi/10.1002/cpe.1527
4. OpenSM ftree routing engine source, linux-rdma/opensm. https://github.com/linux-rdma/opensm/blob/master/opensm/osm_ucast_ftree.c
5. DRB: Dynamic Randomized load-Balancing, arXiv:1708.09135, 2017. https://arxiv.org/abs/1708.09135
6. Yuan, Mahapatra, Lang, Pakin, Static load-balanced routing for slimmed fat-trees, JPDC 2014. https://www.sciencedirect.com/science/article/abs/pii/S0743731514000215
7. Gliksberg et al., Dmodc: An Oblivious Routing Algorithm for Degraded Fat-Trees, IEEE MICRO 2023. https://arxiv.org/abs/2211.13101
8. Chrysos et al., Oblivious Routing Schemes in Extended Generalized Fat Tree Networks, CLUSTER 2009. https://ieeexplore.ieee.org/document/5289145/

延伸阅读

• OpenSM routing documentation. https://github.com/linux-rdma/opensm/blob/master/doc/current-routing.txt