KSP
非结构化拓扑如何用离线预计算实现多路径路由
核心要点：
- 预计算每对源-目的的前 $K$ 条最短路径（Yen 算法），离线建表 + 在线哈希选路
- 唯一适用于 Jellyfish / Xpander 等无层级、无维度结构的拓扑
- 每跳表 vs 源路由两种部署模型，TCAM 容量决定可扩展上限
- 路径长度不等，简单 ECMP 哈希会造成长路径过载，需要按长度加权
KSP（K-Shortest Paths）路由是为非结构化拓扑（Jellyfish / Xpander 等随机/Expander 图）设计的多路径路由方案。ECMP 依赖 Fat-tree 层级结构自动发现等价路径，KSP 不假设任何结构，仅通过拓扑邻接图预计算前 $K$ 条最短路径。
为什么传统路由算法无法用于 Jellyfish / Xpander?
ECMP 和 DOR 等传统路由算法依赖拓扑的结构化特征见 ：
| 路由算法 | 依赖的结构特征 | 无法适用的拓扑 |
|---|---|---|
| ECMP | Fat-tree 的层级对称性：多条路径天然等价 | Jellyfish、Xpander（无层级，路径长度不等） |
| DOR | Torus/Mesh 的维度结构：按维度顺序转发 | 非维度拓扑 |
| UGAL | Dragonfly 的组结构：最短路 vs Valiant 路判断 | 无组概念的拓扑 |
@tbl-route-ksp-01 为什么需要 KSP：路由算法、依赖的结构特征、无法适用的拓扑
在 Jellyfish 和 Xpander[1] 等非结构化拓扑中：
- 路径长度不等——源到目的地可能有 1 跳、2 跳、3 跳的路径混合存在
- 没有"等价路径"的层级保证——不同路径经过的链路、中间节点完全不同
- 没有维度或组概念——无法用 DOR 或 UGAL 的结构化规则决策
KSP 不依赖任何拓扑结构，只需要拓扑的邻接图即可工作——这是它能适配任意拓扑的原因。
KSP 如何预计算 $K$ 条最短路径？
路径预计算
KSP 路由分为离线预计算和在线转发两个阶段：
离线阶段：对每对源-目的地 $(s, t)$，使用 K-Shortest Paths 算法找到前 $K$ 条最短路径（按跳数或权重排序），生成转发表。
在线阶段：报文到达交换机后，查转发表获得到目的地的 $K$ 条候选路径，按 ECMP 哈希（或其他策略）选择其中一条。
Yen 算法
最经典的 KSP 算法是 Yen 算法（Yen, 1971）[2]，找从 $s$ 到 $t$ 的前 $K$ 条最短路径（允许不同长度）：
- 用 Dijkstra 算法找到最短路径 $P_1$
- 对于 $i = 2, 3, \ldots, K$：
- 遍历上一条路径 $P_{i-1}$ 的每个中间节点 $v_j$（称为 spur node）
- 临时移除从 $v_j$ 出发与已发现路径重叠的边（防止生成重复路径），运行 Dijkstra 找从 $v_j$ 到 $t$ 的最短偏离路径（spur path）
- 将 $P_{i-1}$ 中从 $s$ 到 $v_j$ 的前缀（root path）与偏离路径拼接，得到候选路径
- 从所有候选中选最短的作为 $P_i$
- 输出 $P_1, P_2, \ldots, P_K$
复杂度：
$$\begin{equation} T_{\text{Yen}} = O(KN(M + N\log N)) \label{eq:route-ksp-yen-complexity} \end{equation}$$其中 $N$ 为节点数，$M$ 为边数。外层循环 $K$ 次，每次遍历前一路径的 $O(N)$ 个节点，每个节点运行一次 Dijkstra $O(M + N\log N)$。
全网预计算（所有 $N^2$ 对源-目的地）的总复杂度为 $O(KN^3(M + N\log N))$。
数值示例
场景：6 节点网络，找从节点 A 到节点 F 的前 $K=3$ 条最短路径。
拓扑图：
A --- B --- D --- F
| | /
C ------- E ---
邻接关系：A-B, A-C, B-D, C-E, D-E, D-F, E-F
第 1 步：Dijkstra 找最短路径 $P_1$：
- $P_1$: A -> B -> D -> F（3 跳）
第 2 步：找 $P_2$：
- Spur node = A：移除 A->B 边，Dijkstra 找到 A -> C -> E -> F（3 跳）
- Spur node = B：移除 B->D 边，无其他路径到 F
- 候选最短：A -> C -> E -> F（3 跳）
- $P_2$: A -> C -> E -> F（3 跳）
第 3 步：找 $P_3$：
- 在剩余候选中选最短
- $P_3$: A -> C -> E -> D -> F（4 跳）
结果：$P_1$ （3 跳），$P_2$ （3 跳），$P_3$ （4 跳）——路径长度不等，这是 KSP 与 ECMP 的关键区别。
ECMP over KSP
Jellyfish 论文[3]提出将 ECMP 与 KSP 结合使用：
离线预计算阶段：
对每对 (s, t)，运行 Yen 算法得到 K 条路径
|
v
将 K 条路径安装到转发表（每条路径 = 一组逐跳转发规则）
|
v
在线转发阶段：
报文到达入口交换机
|
v
按 ECMP 哈希将流分配到 K 条路径之一
|
v
后续跳按预安装的转发规则逐跳转发
（中间交换机不做路径选择决策）
这种方式保持了 ECMP 的无状态转发优势（中间交换机不需要做路径选择决策），同时利用 KSP 提供的多条非等价路径。
KSP 的转发表规模能撑到多大？
KSP 的工程开销取决于部署模型，两种模型的转发表规模差异巨大：
模型 A：每跳转发表（OpenFlow / 传统 IP 路由）
每台交换机为每个目的地存储 $K$ 条路径中本跳的转发规则：
$$\begin{equation} \text{entries\_per\_switch} = K \cdot N_{\text{destinations}} \label{eq:route-ksp-table-size} \end{equation}$$其中 $K$ 为每对节点预计算的路径数，$N_{\text{destinations}}$ 为目的地数量（通常等于交换机数 $N$）。
模型 B：源路由 / Segment Routing
完整路径编码在报文头（如 SR-MPLS label stack 或 SRv6 SID list）中，只有入口交换机需要存储 $K \cdot N$ 条完整路径，中间交换机按 label/SID 简单转发，转发表规模与拓扑大小线性相关（$O(N)$），与 $K$ 无关。
两种模型对比：
| 部署模型 | 入口交换机条目 | 中间交换机条目 | 报文头开销 | 商用支持 |
|---|---|---|---|---|
| 每跳转发表 | $K \cdot N$ | $K \cdot N$ | 无 | 需 TCAM 支持多路径 |
| 源路由 | $K \cdot N$（仅入口） | $O(N)$ | label/SID list | 需 SR/SRv6 ASIC |
@tbl-route-ksp-deployment 两种 KSP 部署模型对比
数值示例（模型 A）：$N = 1{,}000$ 台交换机，$K = 16$，每台交换机条目 = $16 \times 1{,}000 = 16{,}000$。现代交换机 ASIC 的 TCAM 容量通常在 32K-128K 条目范围，$N = 1{,}000$ 可容纳；$N > 10{,}000$ 时 160K+ 条目可能超出 TCAM 容量。模型 B 在大规模场景下显著优于模型 A，但需要 SR/SRv6 硬件支持。
| ECMP (Fat-tree) | KSP (Jellyfish/Xpander) | |
|---|---|---|
| 路由发现 | 拓扑结构自动保证等价路径 | 需要显式预计算（$\eqref{eq:route-ksp-yen-complexity}$） |
| 转发表规模 | $O(\text{prefix})$（前缀匹配） | $O(K \cdot N)$（$\eqref{eq:route-ksp-table-size}$） |
| 路由更新（故障后） | 本地收敛（SPF 重算受影响子树） | 可能需要全网重算 |
| 硬件支持 | 所有商用 ASIC 原生支持 | 需要 TCAM 容量支持多路径条目 |
@tbl-route-ksp-02 路由表规模与可扩展性：ECMP (Fat-tree)、KSP (Jellyfish/Xpander)
$K$ 值怎么选，不等长路径如何均衡？
$K$ 值的选择是性能与开销的权衡：
- $K$ 太小（如 $K=1$）：退化为最短路径路由，无负载均衡能力
- $K$ 太大（如 $K=128$）：路由表膨胀，且长路径消耗更多网络带宽
- 经验值：Jellyfish 论文[3]使用 $K = 8$-$64$，在吞吐和路由表规模之间取得平衡
非等长路径的负载均衡问题
与 ECMP 的等价路径不同，KSP 的 $K$ 条路径可能长度不同。假设 $K=3$ 条路径长度分别为 2、3、4 跳：
- 简单 ECMP 哈希将 1/3 流量分配到每条路径
- 2 跳路径消耗 2 条链路资源，4 跳路径消耗 4 条——后者的链路占用是前者的 2 倍
- 结果：长路径上的链路负载更高，网络整体利用率不均衡
改进方案：按路径长度的倒数加权分配流量（短路径分配更多流），类似 WCMP 的思想。但这增加了转发逻辑的复杂度。
KSP 在 Jellyfish 上比 Fat-tree ECMP 强在哪？
Jellyfish 论文[3]的评估结果（ECMP over 8-shortest-paths）见 ：
| 指标 | KSP on Jellyfish | ECMP on Fat-tree（对照） |
|---|---|---|
| 均匀随机流量吞吐 | 更高（同等交换机端口配置和成本下，均匀随机流量可接入约 25% 更多服务器） | 基线 |
| 平均路径长度 | 较短（随机图直径小，小规模时优势明显） | 固定（层级结构决定跳数） |
| 尾延迟可预测性 | 较差（路径长度不等） | 较好（路径等价） |
| 对抗性流量 | 取决于 $K$ 和拓扑随机种子 | 全割集带宽保证 |
@tbl-route-ksp-03 性能特性：指标、KSP on Jellyfish、ECMP on Fat-tree（对照）
KSP 在均匀随机流量下性能优于 ECMP on Fat-tree，这源于 Jellyfish 拓扑本身的低直径和高 bisection bandwidth。但在对抗性流量模式和尾延迟可预测性方面，缺乏 Fat-tree 的结构化保证。
何时该用 KSP，何时不该？
适用场景：
- 非结构化拓扑（Jellyfish、Xpander）——唯一可用的多路径路由方案
- 需要在任意拓扑上实现多路径负载均衡
- 网络规模适中（$N < 10{,}000$），TCAM 容量足够
局限：
- 预计算开销大：全网路由表需离线计算，拓扑变更（故障、扩展）后需重算
- TCAM 消耗高：每目的地 $K$ 条路径，大规模网络中转发表可能超出 ASIC 容量（$\eqref{eq:route-ksp-table-size}$）
- 商用 ASIC 支持有限：主流交换机 ASIC（Broadcom Trident/Tomahawk 系列）的 TCAM 和转发流水线针对前缀匹配优化，多路径条目支持有限
- 路径长度不等导致负载不均：简单 ECMP 哈希在不等长路径上效果不如等价路径
Takeaway
| 知识点 | 核心结论 |
|---|---|
| KSP 角色 | 不依赖结构的多路径方案，Jellyfish / Xpander 上唯一可用 |
| Yen 算法 | $O(KN(M+N\log N))$，全网 $O(KN^3(M+N\log N))$ |
| 部署模型 | 每跳表（TCAM 重）vs 源路由（仅入口存表，需 SR/SRv6 硬件） |
| $K$ 值经验 | Jellyfish 论文 $K=8\sim64$，吞吐 vs 表大小折中 |
| 不等长路径问题 | 简单 ECMP 哈希让长路径过载，需按 $1/\text{len}$ 加权 |
| 规模上限 | $N<10{,}000$；超过后 $K\cdot N$ 超 TCAM 容量 |
| Jellyfish 优势 | 同等成本下均匀随机流量可接入 ~25% 更多服务器 |
参考资料
- Valadarsky et al., Xpander: Towards Optimal-Performance Datacenters, CoNEXT 2016. https://doi.org/10.1145/2999572.2999580
- Yen, Finding the K Shortest Loopless Paths in a Network, Management Science, 1971. https://doi.org/10.1287/mnsc.17.11.712
- Singla et al., Jellyfish: Networking Data Centers Randomly, NSDI 2012. https://www.usenix.org/system/files/conference/nsdi12/nsdi12-final148.pdf