第四章：路由算法详解——MinHop、Up/Down、Fat-Tree 原理
各位好，我是老张。今天咱们来聊聊 InfiniBand 网络里最核心的话题之一——路由算法。说实话，我在这个领域摸爬滚打了十几年，见过太多因为路由配置不当导致全网瘫痪的案例。你想想看，一个超算集群几千个节点，如果路由算法选错了，那性能损失可不是一星半点。
我个人习惯把路由算法分成三类：最简单的 MinHop、最经典的 Up/Down、以及最流行的 Fat-Tree。咱们一个一个来拆解。
4.1 MinHop 算法：最短路，但未必最优
MinHop 算法，说白了就是「哪条路近走哪条」。它的核心逻辑是计算源端到目的端的最小跳数路径。在 InfiniBand 里，每个交换机都会维护一张路由表，记录到达每个 LID（Local Identifier）的最短路径。
核心原理：基于 Dijkstra 或 Bellman-Ford 算法，计算所有节点对之间的最短路径。每条链路权重为 1，跳数越少优先级越高。
我在项目中遇到过一个问题：一个 200 节点的集群，用了 MinHop 算法，结果某些链路的利用率飙到 95%，其他链路只有 20%。为什么会这样？因为所有流量都挤在了最短路径上，根本没考虑负载均衡。
避坑指南：我曾经在一个金融高频交易项目中，因为 MinHop 导致某条链路过热，最终引发丢包。记住：MinHop 只适合小规模网络（< 64 节点），或者对延迟极度敏感的场景。大规模集群千万别用。
MinHop 的优点是简单、延迟低。缺点也很明显：没有负载均衡能力，容易产生热点。说白了就是「一根筋」，哪条路近就死磕哪条。
4.2 Up/Down 算法：无环才是王道
Up/Down 算法，我愿称之为「最稳重的路由算法」。它的核心思想是：给每个交换机分配一个 rank（等级），流量只能从低 rank 往高 rank 走（Up），或者从高 rank 往低 rank 走（Down），但绝对不能先 Up 再 Down 再 Up——这样就形成环路了。
嗯，这里要注意：Up/Down 算法本质上是一种 无环路由 算法。它通过构建一棵生成树（Spanning Tree），确保任意两个节点之间只有一条路径，彻底杜绝了环路风险。
我的经验：在 Mellanox 交换机上配置 Up/Down 时，我建议先手动指定根交换机。默认情况下系统会自动选举，但有时候选出来的根节点位置不好，会导致路径非最优。我曾经在一个 500 节点的集群里，手动把根交换机设在网络中心，整体延迟降低了 15%。
Up/Down 的算法流程大致如下：
- 选举根交换机（通常选 rank 最高的）
- 从根开始 BFS 遍历，给每个交换机分配 rank
- 路由规则：Up 方向只能从低 rank 到高 rank，Down 方向反之
- 禁止任何「先 Up 后 Down 再 Up」的路径
它的优点是绝对无环，适合任意拓扑。缺点是路径可能不是最短的，而且负载均衡能力一般。说白了就是「安全第一，性能第二」。
4.3 Fat-Tree 算法：为高性能计算而生
Fat-Tree 算法，这是目前超算领域最主流的方案。你想想看，为什么叫「胖树」？因为越往上层，链路带宽越宽，就像一棵树，树干比树枝粗。
Fat-Tree 的核心思想是 多路径负载均衡。它利用 InfiniBand 的 LMC（LID Mask Count）机制，为每个目的端分配多个 LID，然后通过哈希算法（比如源 MAC、目的 MAC、源 QP、目的 QP）将流量分散到不同路径上。
关键参数：LMC = 2 表示每个目的端有 4 个 LID，LMC = 3 表示 8 个 LID。LMC 越大，路径越多，但路由表也越大。我一般建议 LMC 设为 2 或 3，再大就浪费了。
我在项目中遇到过最典型的场景：一个 1024 节点的 GPU 集群，跑深度学习训练。用 MinHop 时，某些链路利用率 100%，其他链路 10%。换成 Fat-Tree 后，所有链路利用率都在 70%-80% 之间，训练速度提升了 40%。
Fat-Tree 的算法流程：
- 确定拓扑结构（通常是 2 层或 3 层 Fat-Tree）
- 为每个目的端分配多个 LID（通过 LMC）
- 在每个交换机上，根据哈希算法选择下一跳
- 动态调整哈希种子，避免哈希冲突
注意：Fat-Tree 要求拓扑必须是规则的。如果你的网络是「蜘蛛网」式的乱连，Fat-Tree 算法根本跑不起来。我曾经见过一个客户，把交换机乱接一气，然后抱怨 Fat-Tree 不好用——其实是他拓扑没设计好。
4.4 三种算法对比
| 特性 | MinHop | Up/Down | Fat-Tree |
|---|---|---|---|
| 路径选择 | 最短路径 | 无环路径 | 多路径负载均衡 |
| 环路风险 | 有 | 无 | 无（拓扑规则） |
| 负载均衡 | 差 | 一般 | 优秀 |
| 适用规模 | 小（< 64 节点） | 中（< 256 节点） | 大（> 256 节点） |
| 配置复杂度 | 低 | 中 | 高 |
| 典型场景 | 低延迟交易 | 通用集群 | 超算、AI 训练 |
4.5 知识体系图
下面这张图展示了三种路由算法的核心逻辑和适用场景。我习惯用这种图来给团队做培训，一目了然。
4.6 实际配置建议
最后，我给大家一些实际配置中的建议。这些是我这些年踩坑踩出来的经验：
- 小集群（< 64 节点）：用 MinHop 就够了，简单高效。记得开启
adaptive routing来缓解热点问题。 - 中等集群（64-256 节点）：推荐 Up/Down。手动指定根交换机，放在网络拓扑的中心位置。
- 大规模集群（> 256 节点）：必须用 Fat-Tree。LMC 设为 2，哈希算法选
src-dst-qp模式。
小技巧：在 Mellanox 交换机上，可以用 ibdiagnet 工具检查路由表。我每次配置完都会跑一遍 ibdiagnet -r，看看有没有非最优路径。如果有，调整一下根交换机位置或者 LMC 值。
好了，关于三种路由算法的原理就讲到这里。记住：没有最好的算法，只有最适合你场景的算法。下次咱们聊聊具体的配置命令和调优技巧。
公众号:蓝海资料掘金营，微信deep3321