【论文阅读】Slim Fly: A Cost Effective Low-Diameter Network Topology 一种经济高效的小直径网络拓扑

Slim Fly: A Cost Effective Low-Diameter Network Topology

Slim Fly：一种经济高效的小直径网络拓扑 SC’14

Maciej Besta 苏黎世联邦理工学院 maciej.besta@inf.ethz.ch
Torsten Hoefler 苏黎世联邦理工学院 htor@inf.ethz.ch

文章总结

1. 摘要

Slim Fly 一种高性能、经济高效的网络拓扑，它接近理论上的最佳网络直径。

Slim Fly网络拓扑是基于一种图论方法，这种方法试图近似解决度-直径问题（degree-diameter problem）。度-直径问题是图论中的一个经典问题，指的是在给定图的度数（每个节点连接的边的数量）和直径（两个节点之间的最大最短路径长度）约束下，寻找具有最大节点数的图。换句话说，就是在限制网络中每个节点连接的数量（度）和网络的最大通信距离（直径）的条件下，设计一个尽可能大的网络。

分析表明，Slim Fly 在延迟、带宽、弹性、成本和功耗方面比其他拓扑具有显着优势。最后，文章提出了大型计算中心的无死锁路由方案和物理布局以及详细的成本和功耗模型。 Slim Fly 能够构建经济高效、高弹性的数据中心和 HPC 网络，在不同的 HPC 工作负载（例如模板或图形计算）下提供低延迟和高带宽。

2. indroduction

大型网络的关键属性由其拓扑决定：节点和电缆的布局。

设计高效拓扑时必须考虑几个指标。首先，高带宽是必不可少的，因为许多应用程序执行全方位通信。其次，网络可占总系统成本的 33% 和总系统能耗的 50% ，因此它们应该具有成本效益和能效。第三，低端点到端点延迟对于许多应用程序很重要，例如在高频交易中。最后，拓扑应该能够适应链路故障。

而降低网络直径不仅可以减少延迟，还可以降低网络成本及其消耗的能源量，同时保持高平分带宽。减小网络的直径有两个效果。首先，由于每个数据包经过较少数量的 SerDes，因此它降低了能耗。另一个结果是数据包访问更少的接收器和路由器缓冲区，因此不太可能与流经网络的其他数据包竞争。这使文章能够减少昂贵的路由器和连接的数量，同时保持高对分带宽。

胖树拓扑是提供高二分带宽的网络示例。尽管如此，每个数据包都必须遍历许多连接，因为它首先必须沿着树向上移动到达核心路由器，然后才向下到达其目的地。Dragonfly将直径减少到3，但它们的结构也限制了带宽，并且正如文章将要展示的那样，会对容错产生负面影响。在这项工作中，文章提出了一种名为 Slim Fly 的新拓扑，它进一步减小了直径，从而降低了成本、能耗和网络延迟，同时保持了高带宽和弹性。 Slim Fly 基于给定路由器基数的最小直径图，从这个意义上说，它接近给定路由器技术的最佳直径。

Slim Fly 能够使用现成的高基数路由器（例如 64 端口 Black Widow 或 Mellanox 108 端口导向器 ）构建具有超过 100K 直径为 2 的端点的经济高效的全带宽网络。如第 II-A 节所述，可以使用直径 3 构建具有多达数千万个端点的较大网络。

文章的主要贡献：

• 文章设计并分析了一种新型的具有成本效益的低直径网络拓扑，称为“Slim Flies”。
• 文章讨论和评估不同的无死锁最小和自适应路由策略，并将它们与现有的拓扑和方法进行比较。
• 文章表明，与第一直觉相反，Slim Fly 使用更少的电缆和路由器，比类似的 Dragonflies 更能容忍链路故障。
• 文章展示了数据中心或 HPC 中心网络的物理布局以及详细的成本和能源模型。
• 文章提供了具有不同程度和网络规模的实用拓扑库，可轻松用于构建高效的 Slim Fly 网络1。该链接还包含第 III-VI 节中所有模拟的可重复性代码和扩展技术报告。

3. 主要工作

• Slim Fly topologies 构建优化

  本文使用的符号如表 I 所示:
  

  目标是设计一个最佳或接近最佳的拓扑，在给定直径 D 和基数 k 的情况下最大化端点 N 的数量，并保持完整的全局带宽。为了形式化最优性的概念，文章利用众所周知的摩尔界限概念。摩尔界限 (MB) 确定具有给定 k 和 D 的潜在图可以具有的最大顶点数。Nr为：
  $$1+d\sum _{i=0}^{k-1}(d-1{)}^i$$

  当 D = 2 时，最大 Nr ≈ k′2。因此，使用 108 端口 Mellanox Director 交换机构建的示例网络将具有近 200,000 个端点（文章在第 II-B2 节中讨论集中 p 的选择）。当 D = 3 时，Nr 限制为 ≈ k′3，这将支持多达数千万个端点。因此，文章关注直径为2和2的图来进行相关构造。

• Diameter-2 Networks

  著名的Hoffman-Singleton图是一个直径为2的图，具有50个度数为7的顶点和175条边。然而，目前还没有一种通用的方案能够构造出最优或接近最优的图，对于大多数 D 和 k′，还不知道是否存在最优图，或者这些图能否接近Moore Bound（穆尔界限）。

  为了开发直径为2的网络，作者使用了McKay、Miller和Širáň提出的一类图（称为MMS图）。这些图通过图覆盖技术构造而成。文章提出了一个简化的构造方案，并使用该方案设计了Slim Fly拓扑（SF MMS）。

• Diameter-3 Networks

  由于篇幅限制，文中省略了 BDF 和 DEL 图的具体构造方案的细节，这些细节可以在文献和技术报告中找到。尽管 BDF 和 DEL 图接近穆尔界限，但本研究主要关注 MMS图，因为它们的可扩展性适合大多数拥有超过10万个端点的大规模网络。对于直径为3的网络结构，虽然它们的成本和性能优势不如直径为2的网络明显，但在接近最优结构的情况下，仍能展现出类似的结果。

• slimfly 结构分析
  1. SF 提供所有比较拓扑中最小的直径 Diameter = 2
  2. 对于所有考虑的拓扑，平均距离逐渐接近网络直径，并且对于所有分析的网络规模，SF 的平均距离最低。
  3. SF 提供比 DF、FBF-3 更高的带宽。

• ROUTING

1. 最小静态路由（Minimal Static Routing）
   在 Slim Fly 的最小（MIN）路由中，数据包要么直接路由（如果源路由器 Rs 直接连接到目的路由器 Rd），要么通过两跳路由（如果 Rs 和 Rd 之间的距离为2）。这种最小路由可以轻松地使用当前的静态路由技术实现，例如 InfiniBand 或 Ethernet。

2. Valiant 随机路由（Valiant Random Routing）
   Valiant Random Routing (VAL) 算法可用于 Slim Fly 来应对对抗性流量场景，在这些场景下最小路由效率低下。该协议首先随机选择一个与 Rs 和 Rd 不同的路由器 Rr。然后数据包沿两条最小路径进行路由：从 Rs 到 Rr，再从 Rr 到 Rd。VAL 生成的路径可能包含2、3或4跳，具体取决于 Rs、Rr 和 Rd 是否直接连接。尽管可以施加约束，使得随机路径最多包含3跳，但模拟表明，这样会增加平均数据包延迟，因为可用路径的数量受到了限制。

3. 非最小自适应路由（Non-minimal Adaptive Routing）
   UGAL（Universal Globally-Adaptive Load-balanced）算法会基于跳数距离和端点之间队列的大小，选择最小路径或由 VAL 生成的路径。对于 SF 网络，作者研究了两种 UGAL 算法的变体：

4. 全局版本（UGAL-G）
   UGAL-G 可以访问网络中所有路由器队列的大小。每次注入数据包时，它生成一组随机的 VAL 路径，与最小路径进行比较，并选择总的输出路由器队列最小的路径。模拟表明，选择4条路径时可以获得最佳的平均数据包延迟。UGAL-G 接近于理想的 UGAL 实现，因此可以用来评估本地版本的效果。

5. 本地版本（UGAL-L）
   UGAL-L 只能访问每个路由器的本地输出队列。它首先生成一组 VAL 路径并计算最小路径，然后将每条路径的长度（以跳数计）乘以本地输出队列的长度，选择结果最小的路径。生成的随机路径数量会影响模拟结果，实验表明选择4条路径可以实现最低的总体延迟。

6. 死锁避免
   1. 作者采用了类似于 Gopal 提出的策略，使用两个虚拟信道（VC0 和 VC1）来实现最小路由。
   2. 对于自适应路由，使用四个 VC（因为距离为 4 的最大匝数）。在这里，简单地概括了上面的方案，对于 Ra 到 Rb 之间的 n 跳路径，在跳 k 上使用 VC k (0 ≤ k < n)。 为了避免最小路由中的死锁，还可以使用一种基于自动 VC 分配的通用死锁避免技术来打破通道依赖图中的循环。

• 结论
  互连网络构成整个数据中心和 HPC 中心建设和维护成本的重要组成部分。因此，降低互连的成本和能耗对于网络社区来说是一项日益重要的任务。 提出了一种称为 Slim Fly 网络的新型拓扑，用于实施大型数据中心和 HPC 网络架构。为此，利用了一个概念，即降低网络直径可以减少穿过网络的数据包使用的昂贵网络资源（电缆、路由器）的数量，同时保持高带宽。将其定义为优化问题，并朝着摩尔界限进行优化。然后，提出了几种设计最佳网络的技术。采用了一系列 MMS 图，它在 D = 2 时接近摩尔界限，并基于它们设计了 Slim Fly。

Slim Fly 架构遵循高基数路由器和经济高效光纤的技术趋势。在当前技术限制下，比 Dragonfly 实现了 25% 的成本和功耗优势。预计光纤的进一步商品化将带来更具成本效益的连接，而硅工艺技术的进一步改进将带来更高基数的路由器。两者都将使 Slim Fly 未来的相对优势变得更大。

提出的路由策略在位排列和最坏情况流量模式下运行良好，并渐近地实现随机流量的高带宽。得益于类似于 Dragonfly 的模块化结构，Slim Fly 比随机网络等其他拓扑更容易部署。 理论分析表明，Slim Fly 比 Dragonfly 对链路故障的恢复能力更强，并且接近随机拓扑等高恢复能力的结构。这种反直觉的结果（因为拓扑使用更少的链接并实现更小的直径）可以通过具有扩展图属性的图结构来解释。 最后，引入的使用摩尔界限优化网络的方法可以扩展到更高直径的网络，在提供稍高的延迟的同时，可以建立允许数百万个端点的可扩展结构。通用方法基于数​​学优化方面的工程问题，可以有效解决网络中的其他挑战。

主要思想

“一切都与直径有关！”：优化拓扑以实现低直径，不仅可以减少延迟（由于路径较短），还可以减少成本和功耗，因为数据包将穿越，因此需要更少的路由器和电缆。

全带宽胖树与 Slim Fly 之间的比较：两种拓扑都提供高带宽，而 SF 减少了路由器（>50%）和电缆（>30%）的数量。

1. 关键方法（减小直径）
   针对图论中一个著名的概念 Moore Bound 优化了 Slim Fly 的结构。Moore Bound (MB) 确定了具有给定顶点度和直径的潜在图可以具有的最大顶点数。我们在构建方案中使用 MB 概念，并将其定义为具有给定直径 D 的网络可以包含的基数为 k 的路由器数量的上限。为了连接路由器，首先固定 D 和 k，然后使用/构建接近 MB 的这些 D 和 k 的图。文章专注于 D=2（但也简要分析了 D=3），并选择 k 以匹配可用路由器的基数。通过这种方式最大化了给定 D 和 k 的连接端点数量。这可以最大限度地降低每个端点的成本：直观地说，使用接近 MB 的图可以使 Slim Fly 网络在给定 D 和 k 的情况下尽可能地“膨胀”端点，从而最大限度地降低每个端点的成本/功耗。

2. 构建slimfly的概述
   第 1 部分： 每个 Slim Fly 由两个子图组成。这两个子图中的每一个都由相同数量的路由器组组成。在一个子图中，每个组内都有电缆，但这些组彼此之间不相连。每个组（在一个子图中）中的布线模式相同，并且通常与另一个子图中组内的布线模式不同。
   

第 2 部分： 组与子图紧密相连。它们形成一个完全连通的二分图（即，一个子图中的每个组都与另一个子图中的所有其他组相连）。

第 3 部分： 对于更简单的布局（例如，在数据中心中），可以重新排列来自不同子图的组并成对合并。因此，这种 Slim Fly 由相同的机架组成，并且每个机架具有相同的机架内布线模式。机架形成全连接图（即，每个机架都连接到所有其他机架）。

3. 主要发现
   低直径是关键：降低直径可降低延迟以及成本和功耗。直径为 2 的 Slim Fly 保留了高带宽，并且在成本、功耗和延迟方面均优于所有比较目标（低基数传统网络和最先进的高基数设计）。
   摩尔图确保所需的网络属性：除上述属性外，接近摩尔边界的图可确保高带宽和弹性。它们还具有允许数据中心或超级计算机机架布局的连接结构。
   值得一提，slimfly 的优异弹性性能非常有趣！

references

[1] https://spcl.inf.ethz.ch/Research/Scalable_Networking/SlimFly/
[2] Besta, Maciej, and Torsten Hoefler. “Slim fly: A cost effective low-diameter network topology.” SC’14: proceedings of the international conference for high performance computing, networking, storage and analysis. IEEE, 2014.