Fat-tree 拓扑
关联：总览.md — 名词定义与评估指标体系
基本结构
Fat-tree（胖树）是 AI 集群中最广泛使用的多级交换网络拓扑，基于 Clos 网络理论（Clos, 1953）。
标准 3 级 Fat-tree（$k$-port 交换机）：
终端节点 (servers/GPUs)
└─> Edge 交换机（ToR 层，每台 k/2 个下行端口连终端）
└─> Aggregation 交换机（汇聚层）
└─> Core 交换机（核心层，(k/2)^2 颗）
每个 Pod 包含 $k/2$ 个 Edge 交换机和 $k/2$ 个 Aggregation 交换机，共 $k$ 个 Pod。相邻层之间的连接遵循特定的连线规则，使得任意两个终端节点之间存在 $k/2$ 条不相交路径（通过不同 Core 交换机）。
Pod 分组结构：每个 Pod 内 Edge 交换机下行端口连接 $k/2$ 个终端，上行端口连接 $k/2$ 个 Aggregation 交换机。每个 Aggregation 交换机的上行端口连接 $(k/2)^2$ 个 Core 交换机中的 $k/2$ 个，保证从任意 Aggregation 到任意 Core 各有一条路径。
关键参数
标准 3 级 Fat-tree，$k$-port 交换机：
| 属性 | 值 |
|---|---|
| 终端节点数 | $k^3 / 4$ |
| Pod 数 | $k$ |
| 每 Pod 交换机 | $k$（$k/2$ Edge + $k/2$ Aggregation） |
| Core 交换机数 | $(k/2)^2$ |
| 交换机总数 | $\frac{5k^2}{4}$ |
| 链路数 | $3k^3/4$（服务器→Edge：$k^3/4$，Edge→Agg：$k^3/4$，Agg→Core：$k^3/4$） |
| 直径 | 6（终端 -> Edge -> Agg -> Core -> Agg -> Edge -> 终端） |
| 割集带宽 | $\frac{k^3}{8} \cdot b = \frac{N}{2} \cdot b$（全割集带宽） |
Rearrangeably Non-Blocking (RNB)：
Clos 定理：3 级 Clos 网络在中间级交换机数 $m \geq n$ 时为 RNB。即任意输入到输出的排列都可以通过重排实现，不阻塞。
具体含义：任意一对源-目的之间存在 $k/2$ 条不相交路径。对于任意排列通信，总是存在一种路由方案使所有流同时通过而不产生链路冲突。
来源：Al-Fares et al., "A Scalable, Commodity Data Center Network Architecture", SIGCOMM 2008
路由算法
ECMP（等价多路径）
对源-目的对做哈希（通常基于 5-tuple），选择等价路径之一。每对之间有 $k/2$ 条等价路径。
- 优势：无状态、分布式、无需集中控制
- 缺陷：哈希碰撞——多条流映射到同一路径，导致部分链路过载而其他空闲
ECMP 碰撞的量化：$n$ 条流随机映射到 $k/2$ 条路径，期望最大负载为 $\Theta(\frac{n}{k/2} + \frac{\log(k/2)}{\log\log(k/2)})$（balls-into-bins 问题）。AI 集群的结构化流量（AllReduce 的固定 source-dest 对）使哈希值不变，碰撞是持久的。
死锁避免
Fat-tree 的上行-下行结构天然无环（上行只往上，下行只往下），无需额外虚通道机制。这是 Fat-tree 相比 Torus 的重要工程优势。
Hedera / 自适应路由
集中式 SDN 控制器监控链路利用率，动态重路由大象流以平衡负载。
来源：Al-Fares et al., "Hedera: Dynamic Flow Scheduling", NSDI 2010
通信性能特性
AllReduce
NCCL 在 Fat-tree 上使用 Double Binary Tree 算法：
$T_{\text{Tree-AllReduce}} = 2\log_2 N \cdot \alpha + \frac{2(N-1)}{N} \cdot \frac{M}{\beta}$
延迟项 $O(\log N)$ 优于 Ring 的 $O(N)$，适合小消息。带宽项相同。
NVIDIA SHARP（网内计算）：InfiniBand Quantum 交换机在数据转发时直接执行 Reduce 操作：
| 指标 | 无 SHARP | 有 SHARP |
|---|---|---|
| AllReduce 延迟 | $2\log_2 N \cdot \alpha$ | $\log_2 N \cdot \alpha$ |
| 网络总传输量 | $2 \cdot \frac{N-1}{N} \cdot M$ | $\frac{N-1}{N} \cdot M$ |
| 实测改善 | 基准 | 延迟降低 2x，有效带宽提升 30-50% |
AllToAll
Fat-tree 的全割集带宽使 AllToAll 理论效率最高。MoE 的稀疏 AllToAll（仅 top-k expert 的 token）在 Fat-tree 上表现良好，因为 ECMP 可分散不规则流量到多条路径。
拥塞特性
- ECMP 碰撞：Rail-Optimized 通过限制流量在 rail 内消除了 DP 阶段的 ECMP 碰撞
- Incast 拥塞：AllReduce 的 Reduce 阶段多条流汇聚到同一 ToR 下行端口，需要 PFC + ECN + DCQCN 组合缓解
- 残余拥塞：主要来自 TP AllReduce（跨 rail）和 MoE AllToAll（不规则模式）
Rail-Optimized Fat-tree
NVIDIA 为 AI 集群设计的关键变体，设计原则：同一 rail 编号的 GPU（来自不同节点但 GPU 编号相同）连接到同一 ToR 交换机。
效果：
- DP AllReduce 天然在同一 rail 内完成（同编号 GPU 之间），不需跨 rail
- Spine 层只处理 TP/PP 等跨节点通信
- 可降低 Spine 层 oversubscription，节省 30-50% 网络成本
来源：NVIDIA DGX SuperPOD Reference Architecture、Mudigere et al., ISCA 2022
适用场景
Fat-tree 是通用 AI 训练集群的首选拓扑，适合以下场景：
- 全并行策略组合：TP + PP + DP + EP 混合使用，Fat-tree 在所有通信模式上均表现良好
- MoE 模型（AllToAll 密集型）：全割集带宽是 MoE AllToAll 的必要条件
- 大规模扩展：3 级 Fat-tree 支持到 $k^3/4$ 节点，5 级可支持 100K+ GPU
- 多租户集群：不同作业的流量可通过 ECMP 自然隔离
局限性
- 成本高：交换机总数 $\frac{5k^2}{4}$，链路数 $O(N \log N)$，是 Torus 的 3-5 倍
- ECMP 碰撞：结构化 AI 流量下哈希碰撞可预测，可能导致部分链路持续过载
- 非 Vertex-Transitive：不同层级的节点视角不同（Edge、Agg、Core 的角色不对称），路由配置相对复杂
- 增量扩展按层：扩展需要按 Pod 单位添加，不能任意增量
成本分析
3 级 Fat-tree 的成本结构（$k$-port 交换机，$N = k^3/4$ 终端）：
| 组件 | 数量 | 成本驱动 |
|---|---|---|
| Edge 交换机 | $k^2/4$ | ~$940-1,170$/port (IB NDR) |
| Aggregation 交换机 | $k^2/4$ | 同上 |
| Core 交换机 | $k^2/4$ | 同上 |
| 链路/线缆 | $k^3/2 + k^2/2$ | $300-600$/pair (400G AOC 50m) |
实际数据：万卡集群的网络成本（交换机 + 光模块 + 线缆）占总 TCO 的 30-40%。
Oversubscription 降本：实际部署中 Spine/Core 层常用 2:1 或 3:1 oversubscription。例如 Edge 层下行 $k/2$ 端口连终端、上行仅 $k/4$ 端口连 Aggregation，割集带宽降为理论值的 50%，但交换机数减少 50%。
在大模型集群中的实际应用
| 集群 | 规模 | 节点内拓扑 | 节点间网络 | 特点 |
|---|---|---|---|---|
| NVIDIA Eos | 10,752 H100 | NVSwitch 3.0 全互联 | IB NDR Fat-tree | SuperPOD 参考架构 |
| xAI Colossus | 100,000 H100 | NVSwitch 全互联 | IB Fat-tree | 已知最大 GPU 集群 |
| Meta RSC | 16,384 A100 | NVSwitch 全互联 | IB HDR Fat-tree | Rail-Optimized |
| CoreWeave | 1,440 B200 | NVL72 全互联 | IB XDR + SHARP | NVL72 首批部署 |
| Oracle OCI | ~16,000 H100 | NVSwitch 全互联 | IB NDR Fat-tree | 云服务商 |
来源：NVIDIA SuperPOD Blog、CoreWeave nccl-tests
参考资料
| 资料 | 关键内容 |
|---|---|
| Clos, 1953 | Clos 网络 RNB 条件 |
| Leiserson, 1985 | Fat-tree 拓扑提出 |
| Al-Fares et al., SIGCOMM 2008 | 现代 Fat-tree 数据中心实现 |
| Al-Fares et al., NSDI 2010 (Hedera) | Fat-tree 自适应流调度 |
| NVIDIA SHARP | 网内计算实测效果 |
| RFC 2992 | ECMP 标准 |