Jellyfish 拓扑
关联：总览.md — 名词定义与评估指标体系
核心论文：Singla et al., "Jellyfish: Networking Data Centers Randomly", NSDI 2012
基本结构
Jellyfish 是随机正则图拓扑：给定 $N$ 个交换机、每个 $k$ 端口、$r$ 端口连服务器，剩余 $k-r$ 个端口随机连接其他交换机，最终生成一个随机 $(k-r)$-正则图。
可视化上，Jellyfish 没有层级结构，交换机之间的连接是随机分布的，没有核心层/汇聚层/接入层的概念。每个交换机看起来"地位相同"，但连接关系因随机构造而各不相同（非 Vertex-Transitive）。
构造算法：
- 将所有交换机的 $k-r$ 个空闲网络端口放入候选池
- 随机选两个有空闲端口的交换机，建立连接
- 若产生重边或自环则跳过重选
- 最后若剩余端口无法配对，随机断开一条已有边，交叉重连（swap）
- 最终得到一个随机 $(k-r)$-正则图
关键参数
| 属性 | Jellyfish | Fat-tree |
|---|---|---|
| 直径 | $O(\log N)$ | $O(\log N)$ |
| 割集带宽 | $\sim \frac{dN}{4}b$（高概率） | $= \frac{N}{2}b$ |
| 平均路径长度 | 更短 | 较长 |
| 扩展性 | 任意增量 | 必须按层扩展 |
| 交换机数 | $N$（与 Fat-tree 相同设备数） | $\frac{5N}{k}$ |
| Vertex-Transitive | No（随机构造） | No |
核心发现（NSDI 2012 论文）：
相同设备成本下，Jellyfish 支持的服务器数比 Fat-tree 多 25%。
原因：随机正则图的谱间隙（spectral gap, $\lambda_1 - \lambda_2$）高于结构化拓扑：
- Fat-tree 的割集带宽受限于 Core 层交换机数量，有明确的层级瓶颈
- 随机正则图的边分布更均匀，任意切割都不会碰到集中瓶颈
- 数学上，随机 $d$-正则图的割集带宽以高概率趋近 $\frac{Nd}{4}b$——接近理论最优
通信性能特性
路由
Jellyfish 需要 $k$-shortest-path 路由（非传统的最短路径/前缀匹配路由），论文中使用 ECMP over $k$-shortest paths。
由于拓扑随机，不存在结构化路由方案。每个交换机需要完整路由表，规模 $O(N)$。
AllReduce
随机拓扑的割集带宽接近 $\frac{dN}{4}b$，AllReduce 大消息效率接近 Fat-tree。但路由复杂性（$k$-shortest-path）使小消息延迟不可预测。
AllToAll
随机分布的链路使 AllToAll 流量可以分散到多条路径，避免集中拥塞。理论上 AllToAll 效率高于 Torus，接近 Fat-tree。但不规则路径分布使实际性能难以保证。
适用场景
Jellyfish 理论上适合以下场景（但实际均无部署）：
- 均匀随机流量的大规模数据中心
- 增量扩展需求频繁（随机插入新交换机即可）
- 成本极度敏感、可接受运维复杂度的场景
局限性
- 布线噩梦：随机连接 -> 物理布线无规律 -> 数据中心运维极难（无法用标准化布线方案）
- 路由复杂：需要全网路由表、$k$-shortest-path 计算、故障时的路由重算
- 故障诊断困难：无层级结构 -> 定位问题的工具链缺失
- 增量扩展虽理论简单但实际需重新布线：增加节点需要随机接入，实际操作复杂
- 商用交换机/SDN 控制器对随机拓扑零支持：所有商用交换机 ASIC 针对结构化拓扑优化
在大模型集群中的实际应用
无任何商业部署。
Jellyfish 从未在生产环境使用，原因是工程可行性问题极难克服。
学术价值：Jellyfish 证明了结构化拓扑（Fat-tree）不是最优的——存在成本更低、性能更高的方案。但工程可行性的鸿沟使其无法投入生产。这一结论推动了后续学术界对"接近最优"但"结构化"拓扑（SlimFly 等）的研究。
对比 SlimFly：两者都是对 Fat-tree 的挑战，但思路不同——SlimFly 用代数构造得到确定性最优图，Jellyfish 用随机构造得到概率意义上的最优图。SlimFly 有固定的布线规则（虽然非结构化），Jellyfish 完全随机。两者均无法进入生产环境，但原因有所不同：SlimFly 是规模受限于素数约束，Jellyfish 是布线和路由完全不可操作化。
参考资料
| 资料 | 关键内容 |
|---|---|
| Singla et al., NSDI 2012 | Jellyfish 原始论文，相同成本下容纳 25% 更多服务器 |
| [谱图理论相关文献] | 随机正则图谱间隙与割集带宽的理论联系 |