SlimFly
基于 MMS 图构造的直径 2 拓扑，在等端口下接近 Moore 界节点数上限
核心要点：
- Besta & Hoefler SC 2014 提出，目标是直径 2 + 接近 Moore 界节点数
- 基于 MMS 图 (McKay-Miller-Siran 1998)，参数 $q$ 须素数且 $q \equiv 1 \pmod 4$
- 交换机数 $N_s = 2q^2$，每交换机度 $\frac{3q-1}{2}$
- 达到 Moore 界 ~89% 效率 （规则随机图通常 <70%）
- 直径恒为 2，比 Fat-tree (4-6) / 3D Torus ($O(N^{1/3})$) 低
- 等端口下比 Fat-tree 少 25-40% 交换机和线缆
- $q = 5$ 时与 1960 Hoffman-Singleton 图完全同构
- 无大规模商业部署 （ASIC / 布线 / 路由表三大障碍）
核心论文：[Besta & Hoefler, Slim Fly: A Cost Effective Low-Diameter Network Topology, SC 2014][1]
设计动机：为什么直径 2？
网络设计有三个相互制约的目标：
- 低直径：任意两节点最大跳数尽小 （低延迟）
- 高节点数：容纳尽可能多节点 （大规模）
- 低度数：每交换机端口数尽少 （低成本）
三者不可兼得 — 这就是 Moore 界：给定度数 $d$ 和直径 $k$，节点数上限为：
$$\begin{equation} N_{\text{Moore}}(d, k) = 1 + d \sum_{i=0}^{k-1} (d-1)^i \label{eq:topo-slimfly-moore-bound} \end{equation}$$| 直径 $k$ | Moore 界 | 含义 |
|---|---|---|
| 1 | $d + 1$ | 完全图 |
| 2 | $d^2 + 1$ | 1 跳达 $d$，2 跳达 $d(d-1)$ |
| 3 | $d^3 - d^2 + d + 1$ | 以此类推 |
@tbl-topo-sf-moore Moore 界
为什么 Moore 界几乎不可达：达到 Moore 界的图叫 Moore 图，仅在少数平凡情况下存在：
| 情况 | 度数 $d$ | 直径 $k$ | 图 | 节点数 |
|---|---|---|---|---|
| 完全图 | 任意 | 1 | $K_{d+1}$ | $d+1$ |
| 奇环 | 2 | 任意 | $C_{2k+1}$ | $2k+1$ |
| Petersen 图 | 3 | 2 | — | 10 |
| Hoffman-Singleton 图 | 7 | 2 | 1960 年构造[2] | 50 |
| 可能的第三个 | 57 | 2 | 是否存在未知 （开放问题） | 3,250 |
@tbl-topo-sf-moore-graphs Moore 图列表
对实际交换机度数 (32/48/64) 而言 $d^2+1$ 永远达不到。SlimFly 要解决的问题：直径 2 约束下，如何构造节点数最接近 $d^2 + 1$ 的图？
为什么选直径 2：
- 直径 1 = 完全图，几十节点后不可行
- 直径 2 是第一个"可扩展"的直径，$N \approx d^2$
- 直径 3+ 虽更多节点，但延迟增加，且 Fat-tree （直径 4-6） 已有成熟生态
直径 2 = 任意两交换机最多经过 1 台中间交换机。与 Fat-tree 4-6 跳、3D Torus $O(N^{1/3})$ 跳相比，是可扩展拓扑中最低延迟。
MMS 图基本参数是什么？
McKay-Miller-Siran 1998 构造的接近 Moore 界的正则图族[3]。
参数约束：$q$ 是素数且 $q \equiv 1 \pmod 4$。满足：5, 13, 17, 29, 37, 41, 53, 61, ...
基本参数 (@tbl-topo-sf-mms):
| 参数 | 值 | 含义 |
|---|---|---|
| 交换机总数 | $N_s = 2q^2$ | 两子图各 $q^2$ 台 |
| 每交换机度 | $d = \frac{3q-1}{2}$ | 网络端口 （连其他交换机） |
| 直径 | 2 | 任意两台最多 2 跳 |
| 每交换机终端 | $T = R - d$ | 连计算节点 ($R$ = 总端口) |
@tbl-topo-sf-mms MMS 图基本参数
与 Moore 界接近程度：
$$\begin{equation} \frac{N_s}{N_{\text{Moore}}} = \frac{2q^2}{(3q/2)^2 + 1} \approx \frac{8}{9} \approx 0.89 \label{eq:topo-slimfly-density-ratio} \end{equation}$$MMS 达到 Moore 界 ~89%，常规随机图通常 <70%。
构造方法是怎么用代数实现的？
基于有限域 $\text{GF}(q)$ 的二次剩余集合。以 $q = 5$ （50 台交换机，度 7） 为例。
前置：有限域与二次剩余
$\text{GF}(q)$ 是模 $q$ 整数集合，加乘都取模 $q$。$\text{GF}(5)$ 示例：$3 + 4 = 7 \equiv 2$，$2 \times 3 = 6 \equiv 1$，$-1 \equiv 4$。
二次剩余 (Quadratic Residue) 是有限域中可表示为非零元素平方的元素。$\text{GF}(5)$ 中：
| $x$ | $x^2 \pmod 5$ |
|---|---|
| 1 | 1 |
| 2 | 4 |
| 3 | $9 \equiv 4$ |
| 4 | $16 \equiv 1$ |
@tbl-topo-sf-qr GF(5) 二次剩余计算
- QR （二次剩余） = $\{1, 4\}$
- QNR （二次非剩余） = $\{2, 3\}$
$q \equiv 1 \pmod 4$ 的条件保证 $-1$ 是 QR ($-1 \equiv 4 \in QR$)，确保连接对称性 （A 连 B → B 也连 A）。
节点编址
两个子图 $G_0$ 和 $G_1$，各含 $q^2 = 25$ 节点。每节点用三元组 $(g, m, c)$:
- $g \in \{0, 1\}$：子图编号
- $m \in \{0, ..., 4\}$：第一维坐标
- $c \in \{0, ..., 4\}$：第二维坐标
共 50 节点。每子图可想象为 $5 \times 5$ 网格。
子图内连接
$(g, m_1, c_1)$ 和 $(g, m_2, c_2)$ 相连条件：$m_1 \neq m_2$ 且 $\frac{c_1 - c_2}{m_1 - m_2} \in QR$。
直觉：把节点 $(m, c)$ 看作有限域平面上的直线 $y = mx + c$。两节点的"斜率差/截距差"必须是二次剩余才相连。
$(0, 0, 0)$ 的组内邻居示例 (@tbl-topo-sf-intra):
| 邻居 $(0, m_2, c_2)$ | $c_2 / m_2 \pmod 5$ | ∈ QR? |
|---|---|---|
| $(0, 1, 1)$ | $1/1 = 1$ | ✓ |
| $(0, 1, 4)$ | $4/1 = 4$ | ✓ |
| $(0, 2, 2)$ | $2/2 = 1$ | ✓ |
| $(0, 2, 3)$ | $3/2 = 9 \equiv 4$ | ✓ |
| $(0, 3, 3)$ | $3/3 = 1$ | ✓ |
| $(0, 3, 2)$ | $2/3 = 4$ | ✓ |
| $(0, 4, 4)$ | $4/4 = 1$ | ✓ |
| $(0, 4, 1)$ | $1/4 = 4$ | ✓ |
@tbl-topo-sf-intra $(0, 0, 0)$ 的组内候选邻居
注：$\text{GF}(5)$ 中 $2^{-1} = 3, 3^{-1} = 2, 4^{-1} = 4$。
$(0, 0, 0)$ 有 8 个候选，经生成集筛选后实际度为 $\frac{q-1}{2} = 2$。
子图间连接
$(0, m_0, c_0)$ 与 $(1, m_1, c_1)$ 相连当且仅当 $c_0 + c_1 \equiv m_0 \cdot m_1 \pmod q$。
$(0, 0, 0)$ 跨组邻居：条件简化为 $c_1 = 0$。连接到 $(1, 0, 0), (1, 1, 0), (1, 2, 0), (1, 3, 0), (1, 4, 0)$ 共 5 个。
$(0, 2, 3)$ 跨组邻居：条件 $3 + c_1 \equiv 2 m_1 \pmod 5$，即 $c_1 \equiv 2m_1 - 3$ (@tbl-topo-sf-inter):
| $m_1$ | $c_1 = 2m_1 - 3 \pmod 5$ | 邻居 |
|---|---|---|
| 0 | $-3 \equiv 2$ | $(1, 0, 2)$ |
| 1 | $-1 \equiv 4$ | $(1, 1, 4)$ |
| 2 | $1$ | $(1, 2, 1)$ |
| 3 | $3$ | $(1, 3, 3)$ |
| 4 | $5 \equiv 0$ | $(1, 4, 0)$ |
@tbl-topo-sf-inter $(0, 2, 3)$ 的跨组邻居
每节点恰好 $q$ 个跨组邻居。
最终度数
总度数 = 组内 + 跨组 = $\frac{q-1}{2} + q = \frac{3q - 1}{2}$。$q = 5$ 时 $d = 2 + 5 = 7$。
与规则拓扑的根本差异
| 拓扑 | 连接规则 | 物理直觉 |
|---|---|---|
| Ring | 左右邻居 | 一维排列 |
| 2D Torus | 上下左右邻居 | 二维网格 |
| Fat-tree | 上层/下层 | 层级树 |
| SlimFly | 代数公式 | 无几何直觉 |
@tbl-topo-sf-vs-regular SlimFly vs 规则拓扑
SlimFly 没有"左邻右舍""上层下层"的空间含义 — 代数最优性和物理直觉性不可兼得。
为什么直径 2 能保证？
MMS 图的代数结构保证：对任意两个不直接相连的节点 $A$ 和 $B$，至少存在一个节点 $C$ 同时是 $A$ 和 $B$ 的邻居。
$q \equiv 1 \pmod 4$ 的条件保证这个交集性质。所以：
- 直接相连：1 跳
- 不直接相连：经一个公共邻居，2 跳
- 不存在 3 跳以上
$q = 5$ 结果总结
| 参数 | 值 |
|---|---|
| 交换机总数 | 50 |
| 度数 | 7 |
| 组内连接 | 每节点 2 条 |
| 跨组连接 | 每节点 5 条 |
| 直径 | 2 |
| Moore 界 | $7^2 + 1 = 50$ |
| 效率 | 100% |
@tbl-topo-sf-q5 $q = 5$ 结果
$q = 5$ 是特殊情况，恰好达 Moore 界，与 1960 Hoffman-Singleton 图完全同构 — MMS 的代数构造在 $q = 5$ 时重新生成了这个经典 Moore 图。更大 $q$ 下效率降至约 89%，但仍是已知最接近的构造。
可选规模有什么限制？
$q$ 的约束让交换机数离散，但终端数仍灵活:
- 固定：交换机数量 $N_s = 2q^2$ 及连接关系 (由 $q$ 唯一确定)
- 灵活：每交换机挂多少终端 ($T = R - d$ 可逐交换机不同)
48-port 交换机下各 $q$ 的终端容量 (@tbl-topo-sf-scale):
| $q$ | 交换机数 $N_s$ | 网络度 $d$ | 终端端口 $T = 48 - d$ | 终端范围 |
|---|---|---|---|---|
| 5 | 50 | 7 | 41 | 1 ~ 2,050 |
| 13 | 338 | 19 | 29 | 1 ~ 9,802 |
| 17 | 578 | 25 | 23 | 1 ~ 13,294 |
| 29 | 1,682 | 43 | 5 | 1 ~ 8,410 |
| 37 | 2,738 | 55 | — | 不可行 ($d > 48$) |
@tbl-topo-sf-scale 不同 $q$ 的规模
关键观察：
- 终端数灵活，交换机数离散 （50 → 338 → 578 → 1,682 大跳跃）
- 大 $q$ 时网络度数吃掉大部分端口，剩余终端端口少
- 不满配的代价：交换机骨架"一口价"，不能按需裁剪，与 Fat-tree 不同
关键参数和与其他拓扑对比
核心问题：SlimFly 的交换机数、度数、直径、割集等关键参数值是多少？与 Fat-tree/Dragonfly/HyperX 对比有什么优势？
| 属性 | 值 |
|---|---|
| 交换机总数 | $N_s = 2q^2$ |
| 终端总数 | $N = N_s \cdot T$ |
| 交换机度 （网络） | $d = \frac{3q-1}{2}$ |
| 交换机 radix | $R = T + d$ |
| 直径 | 2 （恒定） |
| 割集带宽 | $\sim \frac{N}{2} b$ （接近全割集） |
| 链路总数 | $\frac{N_s \cdot d}{2}$ |
| Vertex-Transitive | Yes |
@tbl-topo-sf-params SlimFly 关键参数
$\sim 1000$ 交换机规模对比 (SlimFly 取 $q = 17$，$N_s = 578$，@tbl-topo-sf-vs):
| 属性 | SlimFly | Fat-tree （3 级） | Dragonfly | HyperX |
|---|---|---|---|---|
| 直径 | 2 | 4-6 | 3 | $L$ (2-3) |
| 割集 | $\sim 0.89 \cdot \frac{N}{2}b$ | $= \frac{N}{2}b$ | $\sim 0.5 \cdot \frac{N}{2}b$ | 可配置 |
| 交换机数 （等规模） | $N_s$ | $\sim 2.5 N_s$ | $\sim 1.2 N_s$ | $\sim 1.5 N_s$ |
| 可选规模 | 离散 （稀疏） | 任意 | 较灵活 | 灵活 |
| 布线 | 非结构化 | 层级结构化 | 组结构化 | 维度结构化 |
| Vertex-Transitive | Yes | No | No | Yes |
@tbl-topo-sf-vs SlimFly vs 其他拓扑
关键数据：相同端口数下，SlimFly 比 Fat-tree 少 25-40% 交换机和线缆；均匀随机流量吞吐与 Fat-tree 相当或略优[1]。
拓扑特性
核心问题：SlimFly 的直径 2、接近全割集、Vertex-Transitive、非层级这四大特性各自带来什么工程影响？
恒定直径 2：任意两交换机最多经过 1 台中间交换机，最坏延迟 = 2 跳，与规模无关。
接近全割集：MMS 图构造保证高度连接均匀性，~89% 效率，对抗性流量某些切分方向略弱于 Fat-tree 精确全割集。
Vertex-Transitive：从任何节点看网络结构完全相同，均匀流量下所有链路负载相等，不存在热点。
非层级：与 Fat-tree (Core→Agg→Edge)、Dragonfly (Group→Router) 不同，代数规则决定连接无层级划分。后果：
- 路由必须查表：无法用目的地前缀匹配，每交换机需预计算到所有其他交换机的转发表 ($O(N)$ 规模)
- 布线无物理规律：无法按 rack/pod 组织线缆，每交换机到 $d$ 个邻居的线缆长度方向各异
适用场景与局限
核心问题：SlimFly 适合和不适合哪些并行策略和部署场景？
适用：
- 延迟是首要目标 （直径 2 最优）
- 规模恰好匹配离散点
- 流量模式接近均匀
- 成本约束严格 （比 Fat-tree 少 25-40%）
局限：
- 规模受限于特定素数 （338 → 578 → 1682 间隔大）
- 布线非结构化，运维困难
- 对抗性流量弱于 Fat-tree
- 路由表需预计算 ($O(N)$，不如前缀匹配可扩展)
- 增量扩展不可行 ($q$ 变化需重构拓扑)
实际部署：为什么没有？
无大规模商业部署。工程化障碍：
- 交换机 ASIC 不支持：商用 ASIC (Broadcom/Mellanox) 针对 Fat-tree/Clos 层级优化，不支持 SlimFly 预计算路由表
- 非结构化布线无法管理：数据中心标准线缆管理 （线槽、标签、对称走线） 依赖物理规律，SlimFly 在物理空间无规律
- 商业生态缺失：SDN 控制器 / 监控 / 故障诊断工具均不支持非层级拓扑
- AI 集群流量不匹配：MoE AllToAll 是不均匀流量，SlimFly 缺乏完善分析数据
学术意义：证明在直径和成本方面存在比 Fat-tree 更优的拓扑，建立"接近 Moore 界"作为网络拓扑优化的理论标杆。
演进：ETH Zurich 同一研究组 （Hoefler 团队） 在 SlimFly 基础上提出 PolarFly (SC 2022)[4]，放宽素数约束 (任意素数幂 vs $q \equiv 1 \pmod 4$)，可选规模点约 SlimFly 3 倍，性能相当。两者面临相同工程化障碍。
Takeaway
| 知识点 | 核心结论 |
|---|---|
| 设计目标 | 直径 2 + 接近 Moore 界节点数 |
| Moore 界 | $d^2 + 1$ 是直径 2 的理论上限 |
| MMS 图 | 89% Moore 界效率，远高于随机图 70% |
| 构造 | 基于 $\text{GF}(q)$ 二次剩余的代数公式，$q$ 素数且 $\equiv 1 \pmod 4$ |
| 规模 | $N_s = 2q^2$，离散点 50 → 338 → 578 → 1682 |
| 度数 | $d = \frac{3q-1}{2}$ |
| 与 Fat-tree | 少 25-40% 交换机和线缆，直径低 2-4 |
| $q = 5$ | 与 1960 Hoffman-Singleton 图同构 |
| 部署现状 | 无大规模商用，ASIC / 布线 / 路由 / 流量四大障碍 |
参考资料
- Besta M. and Hoefler T., Slim Fly: A Cost Effective Low-Diameter Network Topology, SC 2014. https://doi.org/10.1109/SC.2014.34
- Hoffman A. J. and Singleton R. R., On Moore Graphs with Diameters 2 and 3, IBM J. Research and Development 1960. https://doi.org/10.1147/rd.45.0497
- McKay B., Miller M., Siran J., A Note on Large Graphs of Diameter Two and Given Maximum Degree, J. Combinatorial Theory Series B 1998. https://doi.org/10.1006/jctb.1998.1828
- Lakhotia K. et al., PolarFly: A Cost-Effective and Flexible Low-Diameter Topology, SC 2022. https://doi.org/10.1109/SC41404.2022.00017