数据中心拓扑性能的吞吐量研究

3490数据中心拓扑性能的吞吐量视角0Pooria Namyar 南加州大学 Sucha SupittayapornpongVidyasirimedhi科学与技术学院0Mingyang Zhang 南加州大学0Minlan Yu 哈佛大学 Ramesh Govindan 南加州大学0摘要0尽管之前的研究探索了许多提出的数据中心设计，但只有两种设计，基于Clos和基于扩展器，通常被认为是实际可行的，因为它们可以使用商品交换芯片进行扩展。之前的研究使用了两种不同的度量标准，即分割带宽和吞吐量，来评估这些拓扑在大规模上的性能。从理论上或实践上，我们对这些度量标准之间的关系知之甚少。利用这些拓扑的特性，我们证明了它们的吞吐量的上界，然后证明这个上界比所有先前提出的吞吐量估计器更好地估计了最坏情况下的吞吐量，并且比它们中的大多数都具有更好的扩展性。利用这个上界，我们证明对于基于扩展器的拓扑，与Clos不同，在网络的某个规模之后，没有任何拓扑可以实现全吞吐量，即使它具有全分割带宽；事实上，即使是相对较小的基于扩展器的拓扑也无法实现全吞吐量。最后，我们通过展示使用吞吐量来评估数据中心性能而不是分割带宽可以改变之前关于数据中心成本、可管理性和可靠性的结论。0CCS概念0• 网络 →数据中心网络；网络性能建模；网络可管理性；拓扑分析与生成；•一般和参考 → 指标；0关键词0数据中心，吞吐量，Clos拓扑，网络管理0ACM参考格式：Pooria Namyar，Sucha Supittayapornpong，MingyangZhang，Minlan Yu和RameshGovindan。2021。数据中心拓扑性能的吞吐量视角。在ACM SIGCOMM2021会议（SIGCOMM'21），2021年8月23日至28日，虚拟活动，美国。ACM，纽约，美国，21页。https://doi.org/10.1145/3452296.34729130未经费用许可，允许个人或课堂使用本作品的全部或部分内容的数字或印刷副本，前提是不得为了盈利或商业优势而制作或分发副本，并且副本必须带有本通知和第一页的完整引用。必须尊重ACM以外其他人拥有的本作品组成部分的版权。允许带有信用的摘要。要进行其他复制、重新发布、发布到服务器或重新分发到列表，需要事先获得特定的许可和/或费用。请向permissions@acm.org请求权限。SIGCOMM'21，2021年8月23日至28日，虚拟活动，美国© 2021年计算机协会。ACM ISBN978-1-4503-8383-7/21/08。https://doi.org/10.1145/3452296.347291301 引言0云计算成功的一个主要因素是数据中心，它是一个仓库式的计算和存储聚合，使用商品服务器。数据中心内运行的分布式应用程序（如搜索、可靠存储和社交网络）的性能很大程度上取决于数据中心网络的设计。该网络由一个拓扑结构组成，其中交换机互连服务器。如今，数据中心通常有数万个交换机连接数十万个服务器。本文的重点是设计和评估这种大规模数据中心的拓扑结构。0数据中心拓扑设计。近年来出现了两种不同的拓扑设计类别。基于Clos[8]的设计包括Fat-tree[1]、VL2[15]、Jupiter[42]和FacebookFabric[3]，以及故障容忍的变种，如F10[36]。这些分层设计是双规则的，一个交换机要么连接到�个服务器，要么根本不连接（图1）。最近的替代设计旨在降低安装成本和/或管理成本，而不像基于Clos的拓扑那样。这些设计使用扩展图来互连交换机，包括Jellyfish[44]、Xpander[47]和FatClique[52]。这些拓扑是单规则的：每个交换机都连接到�个服务器（图1）。在这两类设计中，每个服务器只连接到一个交换机。10拓扑容量的度量。数据中心网络的容量限制了其托管的应用程序的性能。直观地说，具有足够容量的拓扑可以允许每个服务器以满线速发送流量，简化了云应用程序的设计：运营商可以在网络中的任何位置放置应用实例而不影响性能，这种放置灵活性使应用程序更具成本效益，更能抵御相关故障（例如整个机架或电源域的故障）[15, 21,35, 42]。大多数之前的工作[1, 3, 15, 42,52]使用网络的双切带宽作为其容量的度量，双切带宽是指在将拓扑图分成两半的所有切割中，跨越最坏情况切割的链路的最小总容量。如果一个拓扑的双切带宽至少等于总服务器数量的一半，则该拓扑具有完全的双切带宽，对于基于Clos的设计，这样的拓扑允许任意应用实例的放置。其他工作[24, 26, 27, 50,51]探索了另一种网络容量的度量，吞吐量，定义如下。在流量矩阵�下的吞吐量是最高的缩放因子�(�)，使得拓扑能够支持流量矩阵� ∙ �(�)，01其他拓扑设计，如DragonFly [30]和SlimFly[6]，无法扩展到现代数据中心的规模，因此我们在本文中不考虑它们；请参见§7。3500SIGCOMM '21，2021年8月23日至28日，虚拟活动，美国Namyar等。0图1：双正则和双正则拓扑。0而不违反任何链路的容量约束。拓扑的吞吐量��是所有流量矩阵中的最坏情况吞吐量。如果��至少为1，则拓扑可以支持任何流量需求（在这种情况下，我们称该拓扑具有完全吞吐量）。由于它可以支持任何流量需求，具有完全吞吐量的拓扑根据定义也允许任意应用实例的放置。0之前的工作如何使用这些指标。这些指标可以帮助评估拓扑设计，进行成本比较，或评估网络扩展的复杂性。正如表1所示，大量的工作已经使用双切带宽对大规模的双正则和双正则拓扑进行了这些评估。（一些之前的工作[27, 43, 44,47]使用吞吐量对一些规模较小的拓扑进行了这些评估，这些拓扑只有几千个服务器。）0目标指标拓扑类别之前的工作0评估设计BBW双正则[1, 15, 42]0双正则[44, 47, 52]0评估成本BBW双正则[15, 42, 44, 52]0双正则[44, 52]0评估扩展复杂性BBW双正则[10, 42, 52, 53]0双正则[44, 52]0表1：之前的工作已经使用双切带宽进行大规模评估。0在这个讨论的基础上，很自然地会问：双正则和双正则拓扑的这些指标有什么区别？表1中列出的论文是否应该使用吞吐量？如果使用吞吐量，这些评估会发生什么变化？据我们所知，文献尚未探讨这两个指标之间的精确差异，但已经探讨了相关但略有不同的问题。双切带宽是一种基于图切割的度量，[27]研究了切割度量和吞吐量之间的关系，但研究规模远小于我们在本文中考虑的规模。此外，[34]表明，对于给定流量矩阵，任何拓扑的最稀疏切割与其吞吐量之间的差距在�(����)范围内。最后，Yuan等人[50]表明，双切带宽无法预测拓扑的平均吞吐量。0为了实现任意实例的放置，还需要一种可扩展、实用的路由方案，可以利用拓扑的可用容量。对于基于Clos的网络，可以使用基于ECMP的路由方案实现。对于大规模的双正则拓扑，我们认为这个问题是开放的。由于我们专注于拓扑属性，所以在本文中我们不涉及这个问题。0在本文中，我们首次探讨了这些度量之间的关系，做出了以下贡献。0贡献：单规则拓扑的全吞吐量与全双分带宽之间的差异。我们证明（§4），对于任何单规则拓扑，存在一个大小（以服务器数量表示），超过该大小，即使具有全双分带宽，拓扑也无法实现全吞吐量。即使是具有10-15K服务器的小型单规则拓扑也是如此（§4.2）。相比之下，双规则Clos拓扑不受此限制，具有全双分带宽的拓扑始终具有全吞吐量（图2）。这意味着拓扑设计者无法通过使用全双分带宽的单规则拓扑来确保应用程序放置的独立性（更准确地说，支持任意的流量需求）（表1）。换句话说，对于单规则拓扑，全双分带宽是必要但不充分的，而全吞吐量则是必要且充分的。0图2：全吞吐量与全双分带宽。0贡献：一种以吞吐量为中心的视角。表1显示之前的工作使用双分带宽来评估单规则和双规则拓扑；我们表明使用吞吐量可能导致不同的结论，影响成本和管理复杂性（§5.1）。这也是更合适的度量标准：正如之前的贡献所证明的那样，吞吐量更好地捕捉了单规则和双规则拓扑的容量，而双分带宽则不行。0�之前的研究认为，一个具有全双分带宽的Jellyfish、Xpander或FatClique使用的交换机比一个具有全双分带宽的Clos少50%[8]。我们表明，一个具有全吞吐量的Jellyfish [44]、Xpander[47]或FatClique[52]只比一个具有全吞吐量的Clos少25%的交换机。这一发现很重要，因为较小的成本差异可能使单规则拓扑相对于Clos不那么有吸引力（尽管Clos的封装和路由简单性可能超过其更高的成本）。�之前的研究认为，Jellyfish或FatClique可以通过使用比双分带宽更简单的随机重连策略[52]进行扩展，而不会有太大的带宽损失，同时保持每个交换机的服务器数量不变。这假设带宽损失是使用双分带宽来估计的。我们表明，即使只扩展一个具有全吞吐量的Jellyfish或FatClique一小部分，同时保持每个交换机的服务器数量不变，也可能导致一个没有全吞吐量的拓扑。因此，希望在扩展后保持单规则拓扑的全吞吐量的设计者可能需要重新连接服务器，这需要比Clos更复杂的扩展策略。3510数据中心拓扑性能的吞吐量视角 SIGCOMM '21，2021年8月23日至28日，虚拟活动，美国0�数据中心设计者通过设计过订阅的拓扑来在拓扑容量和成本之间进行权衡。FatTree[1]论文将拓扑的过订阅比率定义为端到端之间最坏情况下可实现的吞吐量与总双分带宽之间的比率。我们的结果表明，对于单规则拓扑，过订阅比率的更直接定义是吞吐量本身（吞吐量小于1表示过订阅的拓扑）。我们发现，对于这些拓扑，基于双分带宽的过订阅比率高估了吞吐量高达50%。因此，使用该定义的设计者将构建一个实际容量低于目标容量的网络。0贡献：一种高效计算、紧密的吞吐量上限。之前的研究需要一种方法来计算大型单规则和双规则拓扑的吞吐量。为此，我们做出以下贡献。0� 我们证明了单规则和双规则拓扑的吞吐量的上界（§2）。�我们通过实验证明（§3），与现有的估计网络容量或吞吐量的方法相比，这个上界更紧密，并且具有更好的扩展性：[ 43]中的吞吐量上界，[ 23 ,  24 ,  51]中的吞吐量估计启发式算法，双分带宽和最稀疏割 [27]。�这个可扩展的吞吐量上界可以用于更好地评估比以前更大规模的数据中心拓扑的性能，从而使设计者对特定的拓扑更有信心（§5.2）。一个具体的例子是弹性。之前的研究表明，Jellyfish [ 44 ]和Xpander [47]在随机链路故障下对多达1K个服务器的性能下降得很好；我们展示了对于一个规模为131K的Jellyfish或Xpander，性能下降不如预期的那么好（故障后的吞吐量可能比优雅降级时低20%）。0伦理。这项工作没有引发任何伦理问题。02 吞吐量的上界0在本节中，我们证明了适用于单规则和双规则拓扑的吞吐量的上界。02.1 计算吞吐量上界的复杂度0排列矩阵是每行和每列都恰好有一个非零元素的矩阵。排列矩阵可以表示服务器级别的流量（其中每个元素表示两个服务器之间的流量），也可以表示交换机级别的流量。在服务器级别的排列矩阵中，所有非零元素都被归一化为1，而在交换机级别的矩阵中，它们表示连接到交换机的服务器数量（ �）。在本节中，我们将展示这组交换机级别的排列流量矩阵，记为 ˆT ，足以描述单规则和双规则拓扑的吞吐量。0符号说明。交换机级别的流量矩阵  �  的元素  � ��  描述了从交换机  �到交换机  �  的流量需求。设  K  为所有具有服务器的交换机的集合，�为  K中每个交换机连接的服务器数量。为了确定拓扑的吞吐量，我们0符号说明0� 服务器的总数量0� 交换机之间的总链路数量0� 交换机的基数0� 每个交换机的服务器数量0S 具有和没有服务器的交换机集合0K 交换机集合，其中包含  � 个服务器（ K � S ）0� �� 从  �  到  �  的流量需求，其中  �, �  ∈ K0�  =  [ � ��  ] |K | × |K |  流量矩阵，其中包含需求  � ��0T 饱和软管模型集合0ˆ T 排列交通集0�  ( � ) 流量矩阵  �  下的吞吐量0� � 拓扑吞吐量（ � � =  min �  ∈T  �  ( � ) ）0� �� 从交换机  �  到  �  的最短路径长度0表2：符号说明0使用软管模型 [ 11 ] 3，其中每个交换机的发送和接收流量都不超过其最大速率  �（为简单起见，每个链路的容量为单位）。软管模型的流量集合是符合软管模型的流量矩阵的集合：� �  ∈  R |K |×|K | + :  ∈K � �� ≤  � � �  ∈K � � ∈K � �� ≤  � � �  ∈ K0空格0其中  R +是非负实数集合。该流量集合包括常用的流量矩阵，如全互连和随机排列，并且不仅适用于单规则拓扑，也适用于双规则拓扑。双规则拓扑包含两种类型的交换机：没有连接服务器的交换机和每个交换机具有  �个服务器的交换机。没有连接服务器的交换机无法产生或接收任何流量，因此只需要通过连接服务器的交换机（ K）来描述流量矩阵即可。我们的软管模型定义与[ 27]一致，后者基于服务器级别的流量矩阵进行定义。我们的定义使用交换机级别的流量矩阵，利用了单规则和双规则拓扑每个交换机具有 �  个服务器且每个服务器连接到一个交换机的事实。0关于计算拓扑吞吐量。由于水管模型流量集合包含无限数量的流量矩阵，计算拓扑的吞吐量（所有流量矩阵中的最小吞吐量）是不可行的。为了提高可计算性，考虑以下一组流量矩阵，我们称之为饱和水管模型集合T，其中每个交换机以恰好其最大速率�发送和接收流量：0T = {� ∈ R|�|×|�|+: � ∈ �, � �� = � �� ∈ �, � = � �� ∈ �}0。0该集合支配了水管模型流量集合，因为我们总是可以通过增加非负值来将任何水管模型流量矩阵扩展为饱和水管模型流量矩阵。因此，水管模型集合中所有流量矩阵的最小吞吐量不能小于T中所有流量矩阵的最小吞吐量。然而，T中仍然有无限多个元素。下面的定理表明，对于单规则和双规则的拓扑结构，我们可以计算出这些拓扑结构的吞吐量的一个上界。0在水管模型中，端点主机的流量速率受端口速度的限制，这意味着该模型只允许拓扑的可接受流量模式。我们使用的水管模型与之前的工作[11, 27]保持一致。3520SIGCOMM '21，2021年8月23日至28日，美国虚拟会议 Namyar等。0对于拓扑结构，只需考虑一个更小的流量集合即可计算吞吐量。0定理2.1.单规则或双规则拓扑的吞吐量是排列流量集合ˆT中所有流量矩阵的最小吞吐量。0证明概述。§A包含了详细的证明，分为两个步骤。首先，它展示了ˆT表示了T中流量矩阵形成的凸多面体的极值。其次，依赖于集合T的凸性，它展示了所有流量矩阵中的最小吞吐量必须对应于一个排列流量。□0之前的工作[45]在稍微不同的背景下使用了类似的凸性论证，[46]在更有限的背景下证明了类似的定理（对于无知路由）。其他之前的工作（[29]，猜想2.4）将定理2.1作为一个猜想。ˆT的大小虽然是有限的，但随着矩阵维度的增长呈组合增长，因此无法遍历所有元素以计算吞吐量。然而，在ˆT中的任何流量矩阵中，每个交换机�以满速率发送流量到恰好一个其他交换机�。我们利用这一点，结合单规则和双规则拓扑的结构，推导出这些拓扑结构吞吐量的高效计算上界（§2.2）。02.2 吞吐量上界0现在我们使用定理2.1推导出单规则或双规则拓扑吞吐量的上界的闭合表达式。吞吐量既是拓扑结构的函数，也是用于路由流量需求的路由算法的函数；推导出的上界与路由算法无关。0单规则拓扑吞吐量的上界。以下定理为单规则拓扑的吞吐量建立了一个可计算的闭合表达式。它假设，不失一般性，一个单规则拓扑有�个交换机和单位链路容量。0定理2.2. 任意路由下，单规则拓扑的最大可达吞吐量受到以下限制：0�* ≤ min � ˆT0� ∈ �2 � �� I[� �� > 0] (1)0其中�是拓扑中交换机之间的链路数，���是从交换机�到交换机�的最短路径长度，I[∙]是一个指示函数。0证明概述。§B包含了详细的证明，该证明依赖于基于路径的多商品流问题的最优解（§H，在广域网流量工程中常用[33]）。对于给定的流量矩阵�，基于路径的多商品流最大化吞吐量�(�)。现在，考虑任意一个交换机�。它的总入口流量由两个部分组成：流向其服务器的流量，取决于�(�)，以及其中转流量。我们通过交换机的聚合链路容量上界来限制入口流量，并通过路径长度和流量分割比来下界入口流量。解这些不等式，并应用定理2.1，得到方程1。□0高效计算吞吐量上界。方程1的右手边选择了一个最大化总路径长度的排列流量矩阵。找到这个矩阵等价于在[27]中找到近似最坏情况的流量矩阵。在那项工作中，作者提出了一个直观的吞吐量上界形式，并建议使用一种直观的启发式方法构造一个“困难”的服务器级流量矩阵（近似最坏情况）。在本文中，我们正式证明了吞吐量上界，并使用稍微不同的方法（下面讨论）构造一个交换机级流量矩阵，以实现方程1右手边的最小值。为了找到最小吞吐量，我们从给定的拓扑 �构造一个完全二分图 � （由两个不相交的节点集 � 和 � 组成）。 � 和 �分别表示在 �中与直接连接的服务器相连的所有可能的源交换机和目标交换机。边( �, � ) 的权重，其中 � ∈ � 且 � ∈ � ，是从交换机 � 到交换机 �的最短路径长度。决定方程1中吞吐量上界的排列流量矩阵对应于 �中的加权最大匹配。我们称之为最大排列矩阵。0对双正则拓扑的扩展。定理2.2也适用于双正则拓扑。直观上，没有服务器的额外交换机增加了中转流量的容量，这反映在方程1的分子中。我们在§C中正式证明了这一点。该定理还适用于每个交换机 �具有不同基数 � �的单正则和双正则拓扑；为简洁起见，我们省略了对此扩展的描述。定理2.2意味着拓扑的吞吐量与总链路容量成正比，与最大排列矩阵的最大总路径长度成反比。之前的工作[43]计算了单正则拓扑在所有均匀流量矩阵（全互联和排列矩阵）上的平均吞吐量的上界。相比之下，我们对最坏情况下的吞吐量进行了界定，我们的界定与[43]的界定相比更接近单正则拓扑在所有尺度上的最坏情况行为（§3.2）。我们的界定也更加通用：它也适用于双正则拓扑，并且适用于所有流量矩阵（作为定理2.1的结果）。0关于服务器级和交换机级流量矩阵。我们利用单正则和双正则拓扑中的规律性，推理出交换机级排列流量矩阵，而不是服务器级排列流量矩阵。这有助于我们高效地计算大型拓扑的上界（§3）。相对于使用服务器级排列矩阵，这种效率对吞吐量估计没有影响，如我们现在所示。如果我们使用了服务器级TM，吞吐量上界将是相同的。当将交换机级最大排列矩阵 ˆ � 转换为服务器级 ˆ � �时，它是相应服务器级加权最大匹配问题的解。我们可以通过反证法证明这一点。对于任何服务器 � ，� ( � ) 是连接到 � 的交换机，并假设 ˆ �� 可以通过对 ( �, � )进行一组操作（例如插入或删除流量）来改进（排列矩阵的总路径长度可以增加，参见方程1的分母）。我们可以证明，通过对 ( � ( � ) ,� ( �)) 进行类似的一组操作，ˆ �也可以以相同的量进行改进。这是因为从服务器到其直接连接的0.00.250.50H=6H=7H=8(a) Jellyfish (K=100)0.00.250.50H=6H=7H=8(b) Xpander (K=100)0.00.250.50H [5.5, 6.5)H [6.5, 7.5)H [7.5, 9]2k4k8k6k4k2k40k50k025507500spnsp2k4k8k16k24k32k40k50k80k00k20k40k180k220k240k280k300k000000000500spl+2spl+1spl3530数据中心拓扑性能的吞吐量中心视角 SIGCOMM '21，2021年8月23日至28日，虚拟活动，美国00 5k 10k 15k 20k 25k #服务器（N）0差距00 5k 10k 15k 20k 25k #服务器（N）0差距00 5k 10k 15k 20k 25k #服务器（N）0差距0(c) FatClique（K=200）0图3：吞吐量上界与K短路径多商品流。对于所有选择的单规则拓扑和交换机每个服务器（�），随着服务器数量（�）的增加，差距趋近于零。0交换机不限制吞吐量，因此所有的���都不包括它。因此，添加/删除（�(，�(�)）会增加/减少总路径长度，与添加/删除（�，�）的增加/减少量相同。这是一个矛盾，因为我们假设ˆ�是最大置换矩阵。然而，拓扑在交换机级别的最大置换矩阵下的实际吞吐量始终小于或等于服务器级别的吞吐量。如果将服务器级别的最大置换矩阵转换为交换机级别时不是置换矩阵，那么类似于定理2.1的证明线可以表明相应的交换机级别流量矩阵是一些交换机级别置换流量矩阵的凸组合。因此，至少有一个交换机级别的置换矩阵的吞吐量低于该TM。因此，考虑交换机级别的矩阵不仅改善了吞吐量上界的可扩展性，还更好地捕捉了拓扑的最小吞吐量。03 评估吞吐量上界0在本节中，我们展示了吞吐量上界（简称tub）(a)准确估计了最坏情况下的吞吐量，(b)所有先前提出的吞吐量估计器[23, 24, 43,51]对于单规则拓扑的估计都较差，并且大多数情况下扩展性较差。403.1 吞吐量差距0在本节中，我们计算了吞吐量上界（简称tub）与吞吐量之间的吞吐量差距0我们的代码可在https://github.com/USC-NSL/TUB找到0#服务器（N）0吞吐量比例（%）0(a) 吞吐量分布0#服务器（N）0#成对路径0(b) 路径分布0图4：水母（H=8）。 (a)在最短路径提供不足够多样性的拓扑大小上出现吞吐量差距。 (b)最大置换矩阵中成对最短路径的数量周期性增加和减少。(sp=最短路径，nsp=非最短路径，spl=最短路径长度)0通过路由“最坏情况”流量矩阵来实现，并展示了这种差距很小。0方法论。之前的工作[27]表明，最大置换矩阵可以实现最坏情况下的吞吐量。我们已经独立验证了这一点。对于小拓扑，我们详尽比较了KSP-MCF下每个TM的吞吐量，并发现最大置换矩阵实现了最低吞吐量。对于大拓扑，我们将最大置换矩阵的吞吐量与20个随机置换进行了比较，并观察到最大置换矩阵的吞吐量始终较低，并且随着规模增加，两者之间的差距也增大。为了证明吞吐量差距较小，我们需要选择一种路由方案。我们发现解决基于路径的多商品流问题[KSP-MCF，见§H]足以计算吞吐量差距。我们通过扫描�的值，直到增加�不再增加吞吐量，来计算吞吐量差距；在大多数情况下，�=100足以匹配tub。顺便说一句，我们并不是要暗示KSP-MCF对于大型网络是实用的；特别是对于单规则拓扑，找到一个能够实现高吞吐量的可扩展路由方案是一个留给未来工作的开放问题。0其他细节。在本文的所有结果中，我们使用METIS[28]来（过度）估计双切带宽，使用Gurobi[18]来解线性规划的最大流量，使用networkx[19]的�-最短路径[49]实现和igraph[9]的最大二分匹配[32,40]实现。FatClique与我们对单规则拓扑的定义略有不同：在FatClique拓扑中，�在交换机之间可能相差1。我们已经调整了tub和最大排列算法来处理这个差异（§I）。0对于单规则拓扑。图3显示了三个单规则拓扑的tub吞吐量差距，对于不同的 � 值。0Jellyfish。图3(a)显示了� = 100的Jellyfish的吞吐量差距，其中� =8（其他�值的情况类似）。在3K-15K的小规模范围内，差距是非零的。然而，对于更大的实例，差距接近于零。在3K-15K的范围内，tub比较宽松，因为（a）定理2.2的证明使用了吞吐量在最高时的观察。05 §J显示了不同 � 值的结果Small to medium scale. Figure 5(a) shows the throughput gap(determined using the methodology described in §3.1) for topologieswith up to 25K servers. tub has the smallest throughput gap acrossall alternatives. In the range 15K – 25K, tub’s throughput gap iszero, that of others is higher than 0.2, and sometimes as high as 0.4.To illustrate why it is important to have a small throughput gap,consider a scenario in which a network operator wishes to design afull throughput topology; if she uses a loose throughput estimator,the resulting topology may not actually have full throughput.Moreover, tub is among the most efficient of the alternatives(Figure 5(b)).It is both more accurate, and faster than Jain’s method (JM)and Hoefler’s method (HM). These have large throughput gaps atlarger topology sizes (Figure 5(a)). JM and HM exploit edges of eachavailable path, but their estimates are loose because they assume allthe sub-flows going through each edge get a fair share of the edge’scapacity. This assumption may not maximize the throughput of atraffic matrix; to do this, flows that currently have lower throughputshould get more share of the available capacity. JM and HM area few orders of magnitude slower than tub (Figure 5(b)) becausethey exploit more of the topological structure.Bisection bandwidth and [43] scale better than tub, but theirestimates have large error. Bisection bandwidth is a loose cut-basedestimate of throughput as shown by [27] at small scales, and provenby us in §4. Figure 5(a) empirically verifies this at much largerscales than [27]. Computing exact bisection bandwidth for generalnetworks is intractable [4], so we use a fast heuristic [28] thatapproximates the bisection bandwidth. Furthermore, the boundin [43] relies on average distance among all the pairs of switches,based on the fact that every switch splits its traffic equally and sendsto all the other switches in the average case. Our bound, however,considers structural properties (e.g., distance between individualpairs) to maximize the congestion by routing the traffic betweenpairs with the largest distance. Therefore, the gap for tub is smallerthan that for [43], but tub is slower since it considers more detailsabout the topology.3540SIGCOMM '21，2021年8月23日至28日，虚拟活动，美国Namyar等人。0每个源-目的地对之间的所有路径都是最短路径，而且（b）在这个大小范围内的拓扑具有较少的最短路径，所以KSP-MCF会将流量路由到非最短路径上。（图4(a)绘制了不同拓扑大小下流量在最短路径和非最短路径上的比例分布）。有趣的是，拥有100K-180K服务器的拓扑具有较小比例的最短路径（图4(b)），所以我们预计在这个范围内tub会比较宽松（我们无法确认这一点，因为KSP-MCF无法扩展到这些大小），但是在超过这个范围后，我们预计吞吐量差距会很小，因为最短路径的比例增加。然而，在§E中，我们展示了最大可能的吞吐量差距渐近地趋近于零。未来的工作可以探索利用非最短路径的多样性来获得更好的吞吐量界限。0Xpander和FatClique。图3显示了Xpander和FatClique的吞吐量差距，对于不同的�值。与� =8的Jellyfish类似，这些拓扑在5K-15K的小规模范围内差距显著，而在更大的实例中差距接近于零。0双规则拓扑。对于基于Clos的双规则拓扑，ECMP能够实现（接近）全吞吐量（除了流量大小的差异[15]）。我们发现tub的估计在不同的Clos拓扑中也是1，表明它们之间的差距也是零（表A.1）。03.2与其他吞吐量度量的比较0先前的工作提出了其他估计吞吐量的方法。对于单规则拓扑，我们预计tub比这些其他方法更快、更准确，因为它利用了单规则拓扑的特性。在本节中，我们验证了这个直觉。0高效计算tub。在这之前，我们简要讨论一些计算tub速度的经验结果。这个计算的瓶颈是完全二分图中的加权最大匹配。几个网络分析工具，如networkx[19]和igraph[9]，都有高效的加权最大匹配实现。此外，我们的计算具有良好的可扩展性，因为我们将服务器级的流量抽象为交换机级的流量矩阵，从而构建的二分图中的节点数量大大减少。在一台具有64GB内存的机器上，我们能够在20分钟内找到具有�=8的180K服务器拓扑的吞吐量上界。作为校准，使用KSP-MCF计算排列流量矩阵的吞吐量在50K服务器以上无法扩展，使用完整的MCF在8K服务器以上无法扩展。0比较替代方法。之前的工作[27]已经将吞吐量（即MCF的解）与基于切割的度量进行了比较，例如最稀疏切割（在[26]中使用基于特征向量的优化）和双分带宽，以及[43]计算了均匀流量矩阵下统一规则拓扑结构的平均吞吐量的上界。除了这些，我们还将我们的方法与为一般图开发的其他两种吞吐量估计器进行比较。Hoefler的方法[51]将流量分成源和目的地之间的每条路径上的子流量，并将链路的容量平均分配给所有通过它的流量。Jain的方法[24]逐步路由每条路径上的流量；在每一步中，它将链路上的剩余容量分配给所有在此步骤中添加到链路上的新流量，并迭代直到没有路径剩余。0结果。图5比较了tub与这些替代方法，对于每个交换机有8个服务器的Jellyfish拓扑结构。其他拓扑结构的结果类似（为了简洁起见省略）。0大规模。图5(c)显示了双分带宽和通过tub和[43]估计的吞吐量，对于多达300K个服务器的拓扑结构。在这些规模下，我们无法计算KSP-MCF来估计吞吐量，因此我们绘制了绝对吞吐量值。与tub相比，[43]的吞吐量估计在整个范围内始终明显更高。后者的计算复杂度与[43]相当，除了200K-280K范围内，tub表现出非单调行为。tub试图选择两个距离较远的不相交的交换机对来构建最大的排列矩阵，但在这个大小范围的拓扑结构中，这样的对越来越少，因此需要更长的时间。0.00.25.50.751.0002550751000.6.8.0.21.450k100k 150k 200k 250k 300k#Servers (N)02500500075001000012500Time (seconds)𝜃∗ ≤ 𝑁 (𝑅 − 𝐻)𝐻2𝐷(2)𝐷 = 𝑑( 𝑁𝐻 − 1) −𝑅 − 𝐻𝑅 − 𝐻 − 2�(𝑅 − 𝐻 − 1)𝑑 − 1𝑅 − 𝐻 − 2− 𝑑�first bounds the number of switches whose distance is at least 𝑚from a given switch (Lemma 8.1 in §D). Then, we construct (Algo-rithm 1 in the Appendix) the maximal permutation traffic matrix inwhich each switch exchanges traffic with other switches that arefurthest from it (Lemma 8.2 in §D). This construction maximizes𝐿𝑢𝑣, and from this construction and using Lemma 8.1, we can boundthe number of communicating switch pairs whose distances are atleast 𝑚 hops of each other. The bound applies to the denominatorof the RHS of Theorem 2.2, resulting in a throughput upper boundindependent of the traffic matrix (Lemma 8.3 in §D).□(3)3550数据中心拓扑性能的吞吐量视角 SIGCOMM ’21，2021年8月23日至28日，虚拟活动，美国0TUB BBW SC [42] HM(100) JM(100)05k 10k 15k 20k 25k #服务器（N）0吞吐量差距0（a）准确性05k 10k 15k 20k 25k #服务器（N）0时间（秒）0（b）效率050k 100k 150k 200k 250k 300k #服务器（N）0吞吐量0（c）准确性，大规模0（d）效率，大规模0图5：与其他所有指标相比，tub更准确，并且几乎与[43]中的双切割带宽和吞吐量边界一样快。（BBW是双切割带宽，SC是最稀疏切割，HM(.)是Hoefler的方法，JM(.)是Jain的方法，其中（.）是路径数）0算法用于搜索这些不相交的对。我们预计通过并行化加权最大匹配实现可以显著减少搜索时间；我们将这留给未来的工作。0总结。tub的吞吐量差距