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 ∑ i = 0 k − 1 ( d − 1 ) i 1 + d \sum_{i=0}^{k-1} (d-1)^i 1+di=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
- 最小静态路由（Minimal Static Routing）
在 Slim Fly 的最小（MIN）路由中，数据包要么直接路由（如果源路由器 Rs 直接毗连到目的路由器 Rd），要么通过两跳路由（如果 Rs 和 Rd 之间的距离为2）。这种最小路由可以轻松地使用当前的静态路由技术实现，例如 InfiniBand 或 Ethernet。
- 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跳，但模拟表明，这样会增加均匀数据包延迟，由于可用路径的数量受到了限制。
- 非最小自适应路由（Non-minimal Adaptive Routing）
UGAL（Universal Globally-Adaptive Load-balanced）算法会基于跳数距离和端点之间队列的巨细，选择最小路径或由 VAL 生成的路径。对于 SF 网络，作者研究了两种 UGAL 算法的变体：
- 全局版本（UGAL-G）
UGAL-G 可以访问网络中所有路由器队列的巨细。每次注入数据包时，它生成一组随机的 VAL 路径，与最小路径举行比较，并选择总的输出路由器队列最小的路径。模拟表明，选择4条路径时可以得到最佳的均匀数据包延迟。UGAL-G 靠近于理想的 UGAL 实现，因此可以用来评估本地版本的效果。
- 本地版本（UGAL-L）
UGAL-L 只能访问每个路由器的本地输出队列。它起首生成一组 VAL 路径并计算最小路径，然后将每条路径的长度（以跳数计）乘以本地输出队列的长度，选择效果最小的路径。生成的随机路径数量会影响模拟效果，实验表明选择4条路径可以实现最低的总体延迟。
- 死锁避免
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%）的数量。
- 关键方法（减小直径）
针对图论中一个著名的概念 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 的情况下尽大概地“膨胀”端点，从而最大限度地低落每个端点的成本/功耗。
- 构建slimfly的概述
第 1 部门： 每个 Slim Fly 由两个子图组成。这两个子图中的每一个都由雷同数量的路由器组组成。在一个子图中，每个组内都有电缆，但这些组彼此之间不相连。每个组（在一个子图中）中的布线模式雷同，并且通常与另一个子图中组内的布线模式差别。
第 2 部门： 组与子图精密相连。它们形成一个完全连通的二分图（即，一个子图中的每个组都与另一个子图中的所有其他组相连）。
第 3 部门： 对于更简朴的布局（例如，在数据中心中），可以重新排列来自差别子图的组并成对归并。因此，这种 Slim Fly 由雷同的机架组成，并且每个机架具有雷同的机架内布线模式。机架形成全毗连图（即，每个机架都毗连到所有其他机架）。
- 主要发现
低直径是关键：低落直径可低落延迟以及成本和功耗。直径为 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.
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
