vlambda博客
学习文章列表

现代数据中心拓扑结构，如CLOS网络（图1），绝大多数采用大路径多样性构建。一个关键问题是有效平衡可用路径之间的负载。虽然ECMP在实践中被广泛使用，但众所周知，它远远不是最优的。例如，对10个数据中心的研究表明，即使其他地方有备用容量，仍有相当一部分核心链路经常出现拥塞。

最近的许多方案都尝试解决了这一需要。与最近将功能移出网络结构的趋势相一致，许多方案努力将负载均衡委托给集中控制器，委托给网络边缘，甚至委托给终端主机。这些实体是收集有关拥塞的全局或端到端信息的方便地点。CONGA就是一个值得注意的例子，其中边缘交换机（CLOS网络中的leaf交换机）收集并分析来自远程leaf和spine的拥塞反馈，以通知转发决策。Planck、MicroTE、Mahout和Hedera则收集全局负载信息。所有这些方法都是基于非局部拥塞信息对于均衡负载是必要的这一论点。

我们探索一个不同的方向：每个交换机的本地决策能实现什么？我们称这种方法为微负载均衡，因为它在每个交换机内做出“微观”决策，无需全局信息；因为这反过来又允许在微秒（逐包）时间尺度上进行决策。

微负载均衡带来了一种优势的希望，因为基于全局流量信息的负载均衡系统的控制环路比数据中心大多数拥塞事件的持续时间要慢得多，这些拥塞事件都是短期的。例如，在一些测量中，造成大多数数据包丢失的大部分微突发持续几微秒。基于全局拥塞信息收集和反应的系统通常具有数量级较慢的控制回路。例如，尽管CONGA为leaf和spine交换机添加了硬件机制，但其控制环路通常仍需要一些RTT，届时拥塞事件可能已经结束。

我们实现的微负载均衡是DRILL（分布式随机化网络本地负载均衡/Distributed Randomized In-network Localized Load-balancing）。与ECMP一样，DRILL假定每个目的地的一组候选（最低代价/cost）下一跳已通过路由协议安装在每个交换机的转发表中，并且在数据平面中完全在本地进行操作，而交换机或任何控制器之间没有任何协调。与ECMP不同，DRILL做出的转发决策是负载感知的，并且独立于每个数据包。即使在一个交换机中，实现这一想法也可能是比较复杂的。为了适应具有多个转发引擎的交换机，DRILL使用了一种受“两种选择的幂/power of two choices”范例启发的调度算法：每个引擎比较两个随机端口的队列长度加上以前负载最少的端口，并将数据包发送到负载最低的端口。我们扩展了经典理论，以适应分布式数据源集集合（转发引擎），表明关键稳定性结果成立。我们展示了如何优化DRILL的参数，以避免在多个引擎选择相同端口时破坏同步效果。我们进一步研究了交换机内基于负载的调度算法是否会导致不稳定，从而导致低吞吐量，从而证明了所有允许的独立到达过程的稳定性和100%的吞吐量保证。

这种设计提出了一个关键挑战：我们如何处理子流（sub-flow）粒度负载均衡导致的包重新排序问题？有趣的是，我们发现，在CLOS数据中心网络中，即使出现故障，DRILL也能很好地平衡负载，以至于数据包几乎总是按顺序到达，尽管它们穿过不同的路径。无论如何，对于某些应用程序，偶尔重新排序仍然是不可取的。因此，与之前的工作类似，我们可以选择在主机GRO层部署一个缓冲区来恢复正确的顺序。

第二个挑战是处理非对称拓扑：由于重新排序和不同的丢包率，跨非对称路径拆分流可能会给TCP带来严重问题。为了处理不对称性，DRILL将网络路径划分为对称组，并在每个分区内应用微负载均衡。我们表明，即使在多个故障情况下，这也会导致允许流量的高带宽效率和短流量完成时间。

为了评估DRILL，我们仿真了详细的交换机硬件模型以及各种拓扑和工作负载，以将DRILL与ECMP、CONGA和Presto进行比较。与ECMP相比，DRILL的细粒度和负载感知使其在保持低延迟方面更加有效，特别是在高负载情况下，例如，在80%负载下，它将ECMP的平均流完成时间（FCT）减少了1.5倍。与CONGA使用“宏观”信息相比，DRILL的微观负载均衡使其能够在队列开始建立时立即对负载变化做出反应。DRILL可显著缩短尾时延，尤其是在incast情况下（与CONGA相比，FCT的99.99%分位减少2.1倍）和高负载下（与CONGA相比，FCT的99.99%分位在80%负载下减少1.4倍）。此外，DRILL提供了比CONGA更简单的交换机实现，因为它不需要检测Flowlet或发送和分析反馈。

Presto提供了一个有趣的比较。它将负载均衡移动到边缘，但不考虑拥塞：主机源以流单元的粒度在所有最短路径上路由其流量。因此，它的粒度比ECMP更细，但DRILL的粒度甚至更细，并且对负载敏感。我们发现，这些因素为DRILL带来了更高的性能，但程度取决于工作负载动态的性质。差异最大的是突发性工作负载，例如，在incast场景中尾部FCT提升了2.6倍。

最后，我们在Verilog中实现DRILL以测试其硬件可行性。我们对所需逻辑单元及其布局的分析表明，与参考交换机相比，开销最多为1%。

总之，我们的结果表明，CLOS数据中心结构中的微负载均衡是实用的，可以实现高性能，甚至优于使用全网络范围信息的方案。

CLOS拓扑结构使数据中心提供商能够使用更小、更便宜的商品交换机构建大规模网络，与传统设计相比，这些交换机具有更少的端口，连接的链路容量更小。如今，大多数数据中心和企业拓扑要么构建为一个两级折叠CLOS（two-stage folded CLOS），也称为leaf-spine拓扑（图1中显示了一个示例），或者在设计中将CLOS子图合并到各个层中。CLOS网络或其变体被广泛使用，例如在谷歌的各代数据中心中使用。作为另一个示例，VL2网络由其聚合交换机和中间交换机之间的CLOS网络组成。

CLOS网络的一个关键特征是在任何源主机和目标主机之间具有多条路径。目前，数据中心在这些路径之间平衡负载的常见做法是ECMP。当多个“最佳路径”（通常被选择以最小化每条路径的跳数）可用于向其目的地转发数据包时，每个交换机通过哈希5元组数据包报头选择一个：源和目标IP、协议号以及源和目标端口号。此路径选择机制使ECMP能够避免在TCP流中重新排序数据包，进而无需每个流的状态。上面给出的所有CLOS网络示例都部署了ECMP。

然而，ECMP经常被报告在发生流哈希冲突时表现不佳并导致拥塞。例如，数据中心测量研究表明，尽管其他地方有足够的备用容量来承载负载，但仍有相当一部分核心链路经常出现拥塞。许多方案试图通过平衡更细粒度的流量单元来提高ECMP的性能。与最近将功能移出网络结构的趋势相一致，这些建议努力将这项任务委托给集中控制器，网络边缘，甚至是终端主机。例如，在Presto中，终端主机将流拆分为流单元、大小为64KB的TSO（TCP段卸载）段；网络以负载无关的方式平衡流单元，而不是流（the network balances flowcells, instead of flows, in a load-oblivious manner）。Presto的前提是ECMP的每流粗粒度与数据中心中存在的大流混合在一起是ECMP的主要缺陷，而在在具有小流的任何CLOS网络中，ECMP接近最优。在CONGA中，作为另一个示例，每个边缘交换机基于跨网络负载信息平衡flowlets。它的中心论点是，不仅要平衡细粒度的负载，而且全局负载信息对于优化负载均衡和应对拥塞至关重要。Presto和CONGA平衡粒度比数据包粗，以减少重新排序。

虽然改进了ECMP，但这些方案无法有效抑制短期拥塞事件，这些事件往往只持续亚毫秒的间隔，有时称为微突发，因为即使是最快的也有10毫秒到几秒延迟的控制环。然而，根据测量，数据中心的大部分数据包丢失都是由微突发造成的。在今天的数据中心中，尽管据报道平均链路利用率较低（在不同阶段为1%到20-30%），但高突发性使得缓冲区超限周期非常短，因此高丢包率成为常态而非例外。例如，Facebook数据中心以10微秒的粒度对连接web服务器和缓存节点的交换机的缓冲区利用率统计数据表明，最大和平均队列占用率之间存在几个数量级的持续差异。此外，据报告，这些Facebook web服务器机架中的最大缓冲区占用率在24小时测量周期的大约四分之三接近配置极限，即使同一机架的平均链路利用率仅为1%。这些短暂的高缓冲区占用率与高丢包率相关。当利用率接近25%时，固有的流量突发性也会导致谷歌数据中心的高拥塞丢包率，因此利用率通常保持在该水平以下。鉴于微突发的普遍性及其对性能的不利影响，在低流量完成时间和高吞吐量方面，我们的第一个目标是提供高性能，特别是在微突发出现时。

尽管ECMP在处理拥塞方面不太理想，但其极度的简单性和可扩展性有效地将其转变为数据中心事实上的负载均衡实践。值得注意的是，它对于每个交换机来说都是本地的，因为对于转发数据包，每个交换机在可用路径中自主选择，而不考虑其他交换机的负载和选择，这使得它可以轻松地与大多数路由协议一起部署。一旦收集到全局拓扑信息，每个交换机就会做出本地转发决策。因此，通过分布式算法（如CONGA）或以集中方式（如Planck）收集全局负载信息的复杂机制减轻了网络的负担。理想情况下，我们希望分享ECMP的可伸缩性和简单性。因此，在设计DRILL时，我们的第二个目标是使每个交换机的负载均衡决策都是本地的。

3.1 设计概述

对称CLOS网络的理想流体模型方法。为了提供我们可以建立的直觉，我们从一个简化模型开始，其中数据流traffic是流动的流体。为了在短时间内建模，我们假设主机以固定速率注入流体，网络的目标是平衡通过平行路径的流体量。此外，现在假设一个对称的leaf-spine数据中心。

在这个模型中，考虑一个我们称为相等分裂流体（ESF，Equal Split Fluid）的方案：在每个具有n个最小成本路径到目的地的交换机中，交换机沿着每个路径将精确的1/n的流体流量发送到该目的地。ESF在不考虑流量需求的情况下产生精确的最佳负载均衡。想知道为什么，考虑路径上的第一个leaf：它的所有流量都可以以相同的成本发送到n个spine中的任何一个，因此每个“向上”端口接收进入该leaf的每个流的1/n。因此，到任何spine的传入流量（来自所有叶）包括每个端到端流量的1/n。由于spine的传入流量是相同的，因此它们到任何特定leaf的传出“向下”流量也是相同的。当然，最终并非所有端口都有相同的负载；主机和leaf的发送和接收流量会有所不同。但是，如果我们考虑任何两个主机，它们之间的所有最短路径在沿路径的相应跳数处将具有相同的流量（以及单个流的混合！）；我们称之为对称路径。这种直觉延伸到更一般的CLOS网络，本质上是Valiant负载均衡（VLB）背后的流体模型直觉。

虽然ESF是最优的，但它只是一个理论上的流体模型，理想情况下，交换结构需要在真实的离散世界中进行近似。我们可以将几种现有的负载均衡方案解释为试图近似ESF。ECMP与ESF的相似之处在于，在较长的时间范围内，平均而言，它将在所有成本相同的传出端口上平均分配流量。但在重要的小时间尺度下，它是一个很差的近似值，因为它做出决策（a）在整个流的非常粗粒度的块中，以及（b）在不考虑负载的情况下伪随机一致，导致偶尔出现负载冲突。Presto将离散化单元缩小为64 KB的flowcell，并使用终端主机源路由均匀地分布这些flowcell，部分缓解了问题（a）。我们可以想象更进一步，我们称之为每包随机（Per-packet Random），它通过一个均匀的随机中间（spine）交换机发送每个包。有的方案避免了这种设计，以减少终端主机CPU开销和数据包重新排序。但不管怎样，每包随机性将有助于解决问题（a），而不是（b），我们将从经验上看到这两个问题都很重要。

DRILL是ESF的近似最佳值。前面的讨论有助于我们以一种提供前进方向的方式来界定问题：我们能更接近ESF吗？如果可以，ESF方法可以实现我们的目标，即使在微秒级的时间尺度上，也可以使用交换机局部算法实现高性能。但接近理论理想是挺难的。为了实现这一点，DRILL首先选择最小的离散化实用单元，即单个数据包。这也是一个决策单元，交换机可以简单地无状态处理（并通过让交换机做出决策，避免了端主机上每个数据包转发决策的开销问题）。第二，DRILL不均匀随机地（uniform-randomly）转发流量。相反，DRILL利用交换机本地负载信息，在做出每个数据包的转发决策时对一些或所有传出队列进行采样，并将数据包放在这些队列中最短的队列中。直观地说，这最大限度地减少了理想的基于流体的ESF和实际数据包转发之间的“错误”。特别是，我们在后面的章节中证明了DRILK是稳定的，能够为所有允许的独立到达过程提供100%的吞吐量。

总之，这些机制比过去的设计更接近ESF。然而，我们接下来将讨论两个关键挑战。

数据包重新排序。DRILL基于可能快速变化的本地负载信息的细粒度每包负载均衡引起了对可能危及TCP吞吐量的重新排序的关注。我们在第3.2节和第3.3节中显示，在该算法下，负载非常均衡，即使在高负载情况下，重新排序的概率在大多数情况下也非常小，远低于损害TCP吞吐量的程度，事实上，远低于最近通过修改通用接收卸载（GRO, Generic Receive Offload）处理程序在终端主机上处理重新排序的建议所能解决的程度。虽然DRILL可以使用这些技术来避免重新排序，但在许多环境中，即使没有这些技术，它也能提供巨大的好处。

拓扑不对称性。在不对称网络中，世界不再那么简单。像在ESF中一样，在所有路径之间公平地分割流量并不能最佳地平衡负载。如果TCP流在可用容量不等的路径上被分割，它们将由于较慢路径上的损失而退出，留下一些无法使用的容量(此外，如果我们在一组具有不同负载和不同排队延迟的路径中逐个分组地分割流，我们可以预期高度的分组重新排序。

为了处理非对称CLOS网络，DRILL的控制算法将每个交换机处的路径集分解为最少数量的组，这样每个组内的路径都是对称的。在数据平面中，它将流哈希到一个组（如ECMP），然后在每个组内的路径上执行每个包负载感知的微负载均衡（如上文针对对称情况所述）。因此，随着网络变得更加不对称，DRILL变得更加类似于ECMP。请注意，该方法不适用于处理完全任意的网络或随机图等替代拓扑。DRILL的主要目标环境是对称leaf-spine或CLOS数据中心，这些数据中心可能会因偶尔的故障而变得不对称。我们的方法本质上提供了从DRILL到ECMP的优雅回退。

总结。从严格的不考虑负载的方案（ECMP，Presto）到全局负载感知方案（CONGA，Planck），DRILL占据了中间位置：它保留了第一类方案的大部分简单性和可扩展性，但利用少量额外的本地负载信息和可忽略的状态量（独立于流的数量），以在任一类中实现比现有技术更好的性能。在本节的其余部分，我们将更详细地介绍DRILL的设计，从对称情况开始，然后处理重新排序和不对称性。

3.2 对称CLOS中DRILL

在对称CLOS中DRILL开始于使用标准控制平面（在我们的原型中带有ECMP扩展的OSPF）来构建全局拓扑图，选择路由，并在转发表中安装一个等价转发组。DRILL的新机制在数据平面中，我们在这里重点介绍。

在对称CLOS中，我们的任务是尽可能接近ESF。在介绍算法之前，我们将从较高的层次概述可能影响负载均衡的交换硬件。

3.2.1 交换硬件。交换机具有转发引擎，可为数据包做出转发决策。虽然部署在数据中心的许多简单交换机都有一个集中式引擎，但高性能交换机总是有多个转发引擎。高性能交换机在每个接口卡上可能有多个引擎。这些引擎进行并行和独立的转发决策。Cisco 6700系列、Cisco 6800系列、Cisco 7500系列、Cisco Catalyst 6500主干交换机系列和Juniper MX系列是支持多个转发引擎的交换机的一些示例。例如，在Cisco交换机中，为线路卡安装了多个分布式转发卡（DFC，Distributed Forwarding Card）。然后在每个启用DFC的线路卡上复制转发逻辑，每个卡在本地独立于其他卡做出转发决策。一些交换机可以持续访问队列深度，通常作为微突发监控的一种手段。此功能允许网络提供商基于每个端口监控流量，以在微秒的时间窗口内检测意外数据突发。虽然这些信息很容易用于数据包转发，但并不总是精确的：队列长度不包括刚进入队列的数据包，直到它们完全排队。我们的仿真器仿真了这种行为。在某些交换机中，队列信息可能更加不精确或延迟；我们将对此类交换机的研究留给未来的工作。

3.2.2 DRILL(d、m)调度策略。在这里，我们介绍了在对称CLOS中调度每个交换机中的数据包的DRILL算法。我们假设每个目的地的一组候选下一跳已经使用众所周知的机制（例如ECMP使用的最短路径）安装在交换机的每个引擎的转发表中。DRILL本质上是一种交换机本地调度算法，其灵感来源于关于两种选择的幂的开创性工作，即每当数据包的目的地有多个下一跳可用时，用来决定数据包应采用哪一跳。

DRILL(d，m)算法在每个交换机处的操作如下。在每个数据包到达时，数据包的转发引擎从N个可能的输出端口中随机选择d个，在这些d个样本和来自先前时隙的m个最小加载样本之间找到当前最小队列占用率的端口，并将其数据包路由到该端口。最后，引擎使用样本中负载最少的输出队列的标识更新其m个记忆单元。

该算法的时间复杂度为O(d+m)。我们对各种大小的CLOS网络、具有不同数量引擎的交换机和不同负载的实验表明，（a）具有少量选择和少量记忆对我们算法的效率至关重要，例如，DRILL(2,1)显著优于每个数据包的Random和RR，和（b）将d增加到2以上，将m增加到1以上对DRILL性能的影响较小，并且在某些情况下，由于同步效应，可能会降低性能。我们依次解释每一点。

3.2.3 选择和记忆陷阱。为了告知我们对d和m的选择，我们评估了DRILL(d，m)的性能，并使用以下方法将其与ECMP、每包随机和RR进行比较：我们在包级仿真器中构建不同大小的CLOS数据中心（详情见第4节），从[Inside the Social Network's (Datacenter) Network]这篇文章中得出流大小和到达间隔时间，并缩放到达间隔时间以仿真不同程度的网络负载。考虑到数据中心延迟的主要来源是排队延迟，在本节中，我们的目标是最小化队列长度(后面章节将测量更高级别的指标，如流完成时间和吞吐量。）理想的负载均衡器应在每个leaf交换机的上行链路队列以及连接到同一leaf交换机的spine层下行链路队列之间平衡负载。因此，作为性能指标，在100秒实验期间，每10us，我们测量每个leaf交换机上行链路队列长度的标准偏差（STDV）和连接到每个leaf交换机的所有spine交换机下行链路队列长度的标准偏差（STDV）。从理论上讲，ESF将保持这个指标始终为零，我们努力接近于零。

少量的选择和记忆极大地提高了性能。我们的实验表明，在不同规模的网络中，使用不同数量的引擎部署交换机，在高负载和低负载下，添加少量的选择和记忆，例如，DRILL(2,1)而不是逐包随机或RR，可以显著提高负载均衡性能，尤其是在高负载下。例如，在每个连接到48台主机的48个spine和48个leaf的网络中，在80%负载下，与每包随机数相比，DRILL(2,1)将队列长度的平均STDV减少了65%以上，而与每个交换机中的引擎数量无关（图2（a））。每包随机，反过来，由于其更细粒度的每包操作，在ECMP上提高了约94%。对于具有大量引擎的交换机，DRILL对RR的改进更为明显，但即使在单引擎交换机负载下，DRILL也能实现更为平衡的队列，因为基于队列大小的负载感应允许它平衡数据包大小的差异。当网络负载较少，交换机拥有更多引擎时，改进就不那么显著了。例如，在30%的负载下，如果网络由48个引擎交换机组成，则DRILL(2,1)的性能比每个数据包Random和RR高出约20%，而单引擎交换机则高出75%（图2（b））。

太多的记忆和太多的选择可能会降低性能。虽然少量选择和记忆单元可以显著提高性能，但过多选择和记忆单元会降低带有大量引擎（在我们的实验中超过6个引擎）的交换机在高负载下的性能。图3显示了在80%负载下具有48个引擎交换机的网络示例。一个额外选项，即DRILL(1,2)与DRILL(1,1)相比，平均队列长度STDV减少了11%，而有20个选项，即DRILL(1,20)，则将该指标增加了8%。原因是随机样本或记忆单元的数量越大，使得大量引擎越有可能同时选择同一组输出端口，这反过来会导致这些端口上的数据包突发。我们称这种现象为同步效应。由此产生的负载不平衡可能会导致更多的排队延迟，例如，虽然DRILL(1,2)下队列长度的99.9990%低于1（即，队列几乎总是空的），DRILL(1,20)下队列长度的99%略大于1，即DRILL(1,20)下99%队列长度由于同步效应，数据包会经历一些排队延迟。对于其他情况（轻负载或引擎数较少），设置d≫2和m≫1导致负载更加平衡，但考虑到队列在DRILL(2,1)下已经几乎完全平衡，因此对队列长度的影响微乎其微。例如，当一个引擎在80%负载下切换时，与DRILL(2,1)相比，DRILL(12,1)中的平均队列长度STDV较低，但对于这两个引擎，99.9999%的队列长度都低于1，即，数据包很少经历任何排队延迟。

3.2.4 DRILL保证稳定性。如果没有队列的预期长度在没有边界的情况下增长，则系统是稳定的。我们考虑了一个M×N组合输入输出排队交换机的FIFO队列，其中到达是独立的，并且数据包可以被转发到任何N个输出端口。我们假设流量是可容许/通过的，即   ，其中   是到输入端口i的到达率，   是输出队列j的服务率。我们不限制到达率或服务率的异质性。这些速率可以不同，并且可以随时间动态变化。特别是，我们将重点放在更有趣、更具挑战性的案例上，因为数据中心常见的故障和恢复等各种原因，服务率可能会随时间而变化。我们首先证明了没有记忆的纯随机算法，例如DRILL(d，0)是不稳定的，然后证明了DRILL(d，m)在   时的稳定性。

纯随机抽样是不稳定的。首先，我们考虑DRILL(d，0)，即每个转发引擎从可能的N队列中选择d个随机出口的算法，找到它们之间占用最小的队列，并将其分组路由到它。定理1证明了这种算法是不稳定的。

定理1. 对于容许（可通过）的独立到达过程，DRILL(d，0)不能保证对任意   数量的样本的稳定性。

证明。对于具有F个转发引擎的交换机，设   为到引擎i的到达率，   为输出队列j的服务率。   。现在考虑输出队列I。对于任何转发引擎，它选择I作为样本的概率为d/N。I将收到最大到达率，如果任何引擎的样本选择也使用了它。所以它的最大到达率是   。因此，剩余N-1个输出队列的最小到达率为   。显然，如果   大于这些N-1队列的服务速率之和，则系统是不稳定的。

请注意，该论点不成立：（a）当到达或服务费率有一些限制时，例如，当服务速率相等时，或（b）当d=N时。然而，这些特殊情况没有什么意义，因为前者选择了一些可接受的流量模式，而后者使随机化的好处无效，并可能导致同步效应。我们的实验表明，该DRILL在   时表现良好。

随机抽样加记忆是稳定的。我们在上面展示了随机策略在不使用记忆单元的情况下不能保证稳定性。与[A Practical Scheduling Algorithm to Achieve 100% Throughput in Input-Queued Switches]类似，并使用Kumar和Meyn的结果，我们证明了DRILL的调度算法对于所有均匀和非均匀独立到达过程都是稳定的，最大吞吐量可达100%。注意：该结果显示了任何数据包调度算法都可以实现的最大吞吐量，但吞吐量仍可能受到路由次优性的限制。

定理2. 对于所有允许的独立到达，DRILL(1,1)是稳定的，并达到100%的吞吐量。

为了证明算法是稳定的，我们证明了对于由DRILL(1,1)调度的M×N交换机，在Lyapunov函数中存在负的期望单步漂移。有关证明的详细信息，请参见本文的技术报告版本(http://ghorban2.web.engr.illinois.edu/papers/drill)。

3.3 数据包重新排序

DRILL根据本地和潜在易失性交换机负载信息，独立于相同流的其他数据包，为每个数据包做出转发决策。有人可能认为这会导致过度的数据包重新排序，从而触发重复确认机制（TCP检测数据包丢失的主要手段之一），从而降低TCP性能。如RFC 2581中所述，当某个数据段到达时出现故障，接收方立即向发送方发送“重复确认”。发送方使用TCP重传阈值（三个重复ACK的到达）作为数据包丢失和拥塞的指示。它的反应是重新传输感知丢失的数据包并降低其传输速率。重新排序还可能增加CPU开销，因为诸如合并传入数据包突发的GRO之类的优化依赖于顺序传递。出于对这些问题的警惕，大多数负载均衡方案，从ECMP到CONGA到Presto，都通过平衡较粗的流量单元来避免重新排序。

然而，事实证明，DRILL导致最小的重新排序。这可能有点令人惊讶，但如果沿多条路径的延迟相差超过流中数据包之间的时间，则使用多条路径只会导致重新排序。众所周知，排队延迟是数据中心网络延迟的主要来源，DRILL的良好平衡负载和极低的队列长度差异（图2）意味着数据包经历几乎相同的排队延迟，而与它们所走的路径无关。因此，即使流的数据包以非常精细的粒度采用不同的路径，它们也不应该频繁地重新排序。我们使用Linux 2.6中的实际TCP实现进行的实验证实了这一假设，并表明TCP性能没有受到显著影响（第4节）。但是，对于某些遗留或专用应用程序，可能需要消除所有重新排序。这可以通过使用最新技术通过添加终端主机薄层来构建重新排序的弹性网络堆栈来实现。在第4节中，我们评估了带薄层和不带薄层的两种DRILL。

3.4 处理不对称问题

到目前为止，DRILL的设计假设了一个对称网络。最初对称的网络可能会遇到导致不对称的故障，例如，如果从leaf到spine的链接出现故障。出现这种情况时，会出现两个关键问题。

首先，在可用路径之间分割单个流的负载均衡器可能会浪费带宽，因为它们与TCP的控制循环交互。这是因为流可用的非对称路径可能具有不同的容量（取决于使用这些路径的其他流的负载）。每个路径上的流量速率由TCP控制，以避免拥塞。因此，在非对称路径之间平均分配流量负载可以有效地将每条路径上的流量限制为最拥挤路径的流量。这意味着，即使流对带宽有需求，容量更大的路径仍将未得到充分利用。

作为一个简单的例子，考虑图4（a），其中leaf交换机L0和L3下的主机具有无限的TCP流量需求，以便发送给L1下的主机。假设L0-S0链路出现故障，并且所有链路的容量均为40Gbps。在ESF等本地计划下，这种链路故障可能会对通过其他链路的流量造成附带损害。这是因为从L0和L3发送到S1和S2的流共享瓶颈链路S1→L1和S2→L1。假设这些流的数量相等，并且它们都处于稳定状态，TCP不允许来自L3的流通过这两条路径中的任何一条路径的速率（P1:L3→S1→L1和P2:L3→S2→L1），增加超过20Gbps以避免S1→L1和S2→L1上的拥塞。现在，如果负载均衡器尝试将负载保持在路径P0:L3→S0→L1上等于路径P1和P2上的速率，它使P0上的速率也保持为20Gbps，尽管P0可以以40Gbps的速率服务业务。换句话说，50%的P0容量将闲置。如果没有处理不对称性的机制，DRILL也会有同样的缺陷——通过平衡队列，L3有效地将P0的利用率限制在其容量的一半。请注意，其他一些本地负载均衡器也存在此问题。例如，Presto的故障切换机制修剪受故障影响的生成树，并在剩余路径上使用静态加权调度算法，类似于WCMP。在本例中，由于P0、P1和P2各自具有40Gbps的静态容量，因此它们的相关权重将相等，并且Presto将继续均匀地分布L3→L1的荷载穿过它们。

请注意，以不考虑负载的方式更改权重并不能解决此问题，因为最佳权重取决于来自其他来源的负载—一个潜在的快速变化参数。例如，在上面的示例中，对于给定场景，最佳权重为   和   ，但是如果L0停止向L1发送业务，则这些权重使得P1和P2未充分利用。

除了在非对称情况下的这种带宽效率低下之外，在非对称路径上分割流的方案（如Presto和DRILL）可能会导致过度的数据包重新排序。在上面的示例中，由于S1比S0更拥挤，因此穿过P1的分组比穿过P0的分组经历更高的排队延迟，并且因此可能相对于沿着P0发送的分组而无序到达。

我们观察到，这两个问题并不是本地负载均衡器的根本缺陷，而是源于在不对称路径上施加速率依赖性，例如，在上例中将速率   保持为等于状态。直观地说，为了解决这些问题，DRILL需要打破这些依赖关系。为了实现这一点，DRILL引入了控制平面和数据平面更改。在展示如何处理异构链路之前，我们首先介绍了DRILL的控制和数据平面算法，用于处理每个阶段中具有同质链路的多级拓扑中的不对称性。

3.4.1 控制平面操作。DRILL的控制平面标识对称路径组，并将这些组交给数据平面，以便在每个组内实现微负载均衡。这可以利用OSPF的链路状态数据库在每个交换机上本地执行，也可以在SDN网络中集中执行。在这两种情况下，算法都按如下进行。

精确定义对称性：DRILL不需要整个拓扑在各个方面都是对称的。功能上影响DRILL的是它在备选路径之间的选择：在下游/downstream，路径在排队方面应该相似，而不管当前的流量模式如何。但沿路径排队取决于来自与之冲突的其他源-目的地对的流量。在图4（a）中，例如，路径L3S1L1可以具有比L3S0L1更高的排队，因为只有路径L3S1L1与L0→L1的流量共享链路。

考虑到这一点，我们定义了两个链接   ,    为对称的，记为   ，如果它们被同一组源-目的地对遍历，则根据路由协议选择路径。现在考虑两个路径P和Q，其组成的链接分别为P1，…,pn和q1，..,qm。我们把P和Q定义为对称的、写的   、 如果它们具有相同的跳数（即，n=m），并且相应的链路是对称的（即，   ,    ）。

为了理解这个定义，考虑两个例子。首先，很容易看出，在基于CLOS的常规数据中心中，即从源到目标的所有最短路径都是对称的；现在假设从主机h到其机架顶部交换机的链路出现故障。然后对称性仍然是满足的，因为从h流入和流出的流从所有链接中被平等地移除。实际上，路由协议的机制将清除转发表中的失败条目，并继续使用前面介绍的机制在其余路径之间分配流量。因此，并非所有故障都会导致不对称。接下来，考虑图4中的较早示例。P1和P2是对称的，但是P0和P1是不对称的，因为   ，因为只有后者承载L0→L1的流量。

[本文的技术报告版（参加前文）]中的定理3表明，对于允许的独立流量，仅在对称路径之间执行微负载均衡足以保证CLOS网络中DRILL的稳定性和100%的吞吐量。因此，我们有了一种自然的方法，可以将不规则CLOS网络分解为对称组件，并在本地平衡负载。接下来，我们计算这些组件。

步骤1：构建一个箭图：我们构造一个带标记的多有向图（一个有标记边的有向图，其中边允许具有相同的端点和标签），我们称之为箭图。对于网络中的每个交换机，我们在箭图中创建一个节点。然后，我们计算网络中所有leaf交换机对之间的最短路径。对于从交换机a到交换机b的每一条链路，它位于从leaf的src到dst的最短路径p上，我们在箭图中添加一条从a到b的有向边，标记为（src，dst）。计算链接的所有标签可以在多项式时间内完成——对于   个leaf和V个顶点，它需要   ，因为对于每个   对leaf交换机，可以使用Dijkstra算法在   中检查链接是否出现在它们之间的最短路径上。图4（b）通过显示由图4（a）的网络产生的部分箭图来证明这一点；具有相同标签的链接将以相同的颜色显示。

步骤2：将网络分解为对称组件：在构建箭图后，每个源交换机将其指向目的地dst的最短路径集分解为组件：仅包含彼此对称的路径的最大子集。为了更快地检查路径对称性，DRILL使用了一个哈希函数，该函数将箭图中顶点a到b的边集映射到一个我们称之为(a, b)分数（score of (a, b)）的数值。路径p的分数，p.score，就是它所有链接的分数列表。在前面的示例中，假设hash(L3, S1)=1和hash(S1，L1)=2，则P1.score是<1,2>。如果两条路径的分数相等，则这两条路径是对称的。除了计算路径p的分数外，DRILL还计算其容量p.cap，这是p的最慢链路的容量。p.score和p.cap计算的复杂性是   ，其中d是p的长度。在这些计算之后，DRILL在未分配的路径集上迭代，该路径集尚未分配给任何组件（它最初包括通向dst的所有最短路径）。在每次迭代中，它会将未指定（unassigned）中的所有对称路径指定给组件，并将其从未指定（unassigned）中移除。在上面的示例中，L3→L1的路径集合被分解为两个组件：{P0}和{P1，P2}。

DRILL还为每个组件分配一个权重，该权重与其路径的总容量成比例。在上面的例子中，   。因此：{P0}.w=1和{P1，P2}.w=2。该权重分配类似于一些文献中的路径权重分配，可以在交换机中实现。

分解集合的复杂性为   ，其中   和   分别是该集合中的路径数和最大路径长度。请注意，集合的分解不会影响其他集合的分解，这使得计算在必要时易于并行化。

多级拓扑中的一个示例：图5显示了部署在Facebook中的基于CLOS的网络的示意图示例，其中pod由多个服务器机架和结构交换机组成。折叠的CLOS连接每个pod中的TOR和结构交换机。pod通过spine平面相互连接。每个pod的每个结构交换机连接到其本地平面内的每个spine交换机，即每个pod的第一个结构交换机连接到第一个spine平面的所有交换机。如果链路(R0, F0)出现故障，则R5→R1路径穿过第一个spine平面:    和   ，以及穿过第二个平面:    和   , 这些路径是不对称的，因为Q2和Q3中的一些链路与Q0和Q1不同，也可以将流量从Pod 2传输到R0，并且在箭图中具有额外的边缘；相比之下F3→R1路径都是对称的。

3.4.2 数据平面操作。在检测到对称组件后，每个交换机遵循两个步骤来转发每个数据包：流分类：通过像ECMP一样哈希每个数据包的5元组头，DRILL根据前一步骤中设置的权重将其分配给组件。组件内微负载均衡：DRILL使用DRILL(d，m)跨对称路径平衡负载。

3.4.3 处理异构设备。除故障外，异构链路（具有不同容量的同一级链路）和不平衡条带/strip（从leaf到spine的链路数量不等）使拓扑不对称。例如，在图4（a）中，如果L0连接到S0，L1通过一条40Gbps链路或四条10Gbps链路连接到S0，而所有其他对leaf交换机和spine交换机通过一条10Gbps链路连接，则一些路径包括来自L0→L1的路径是不对称的，跨这些路径拆分流可能会导致重新排序和带宽效率低下。

通常，对于异构设备，在交换机a向b排队不仅取决于通过(a, b)的流，还取决于流向a发送流量的速率和a向b发送流量的速率。为了获得这两个附加标准，我们定义了容量因子(capacity factor)    。对于穿过(a, b)的从src到dst的路径p，   定义为该路径的输入速率除以其输出速率：capacity(src,a)/capacity(a,b)，其中capacity(a,b)和capacity(src,a)分别是从a到b的链路容量和路径p从src到a的容量，即该路径上从src到a的瓶颈链路的容量。它对src→src如果只使用路径p，流量在a向b转发过程建立队列的过程进行建模。对于源顶点，我们考虑容量因子为   , 例如，如果a=src，那么   。然后，箭图中的边标签还包括其容量因子：在构建箭图时，对于src和dst之间路径p上的每个(a, b)链路，我们将从a到b的有向边添加到标签为(src，dst，cf(a，b，p))的箭图中。控制和数据平面算法的其他步骤和以前完全一样。我们的稳定性和100%吞吐量结果涵盖了这种情况。作为示例，在图4（a）中，如果L0-S0、L0-S1和L1-S0链路是40Gbps，而其他链路是10Gbps，则在L0→L1路径中H0=L0S0L1，H1=L0S1L1，H2=L0S2L1，我们有   但   。

我们在详细的仿真中评估DRILL。我们发现，在80%的负载下，DRILL的平均FCT分别比Presto、CONGA和ECMP低1.3倍、1.4倍和1.6倍。我们的细粒度和负载感知都是影响性能的重要因素，第二个因素在高突发流量模式（如incast）和链路故障中变得更加重要。DRILL在处理incast时特别有效，因为它是对自动负载突发做出反应的最灵活的负载均衡器；与CONGA和Presto相比，FCT的第99.99百分位分别降低了2.1倍和2.6倍。我们还展示了DRILL具有最小的数据包重排序，并探讨了故障、合成流量模式、向外扩展和向上扩展的影响。最后，我们在Verilog中实现了DRILL来评估可部署性。这些评估的细节如下。

性能评价方法。为了大规模测试DRILL的性能，我们测量了DRILL下的流量完成时间（FCT）和吞吐量，并通过仿真将其与CONGA、Presto和ECMP进行了比较。我们使用OMNET++仿真器和INET框架，以及标准以太网交换机和主机的网络堆栈。我们通过网络仿真Cradle库从Linux 2.6移植真实世界的TCP实现。对于DRILL，除非另有说明，否则我们在DRILL(2,1)下使用单引擎交换机。我们使用2级和3级CLOS网络，在一组真实和合成的工作负载以及一个incast应用程序下，具有各种大小、无故障和多链路故障。

在对称CLOS中，DRILR减少平均和尾部延迟。我们使用来自真实数据中心流量的跟踪驱动(trace-driven)工作负载来确定流量大小、流量到达间隔时间和流量模式，并使用带有4个spine和16个leaf交换机的CLOS，每个交换机连接到20台主机。连接Spine和Leaf的链路为40Gbps，主机和Leaf之间的链路为10Gbps。为了仿真不同程度的负载，我们对流量间隔时间进行了缩放。在此设置下（图6），我们发现负载均衡粒度是负载均衡器有效性的关键因素。与Presto相比，DRILK的FCT较低，而Presto的FCT又低于CONGA。（稍后，我们将看到，即使在对称情况下，负载感知也很重要。）在重负载下，差异更大，例如，在80%负载下，DRILL将Presto和CONGA的平均延迟分别减少1.3倍和1.4倍（图6）。我们还测试了一个strawman“每流DRILL”，它为流的第一个数据包做出负载感知决策，然后锁定流；这略微改善了Presto和CONGA的尾部延迟，同时比两者都粗粒度些。

为了了解这种改进来自何处，我们测量了每跳的排队时间（图6（c））：leaf向上到spine（1跳/Hop 1），spine向下到leaf（2跳/Hop 2），以及leaf到主机（3跳/Hop 3）。负载为10%时，排队主要发生在最后一跳，例如，在ECMP下，最后一跳排队时间占数据包端到端排队时间的97.6%。在第3跳，没有路径选择，也没有任何负载均衡方案提供明显的好处——DRILL、CONGA和Presto在ECMP上的平均FCT改进小于9%——但在任何情况下，总排队时间几乎都是不可见的非常微小。在50%和80%的负载下，我们可以看到在第2跳的排队可以忽略不计，而在第3跳的方案之间几乎没有差异。在这种情况下，负载均衡器的优势主要来自较短的上游队列（即第1跳）：在ECMP下，平均上游队列延迟占负载为80%的数据包总排队延迟的54%。DRILL、Presto和CONGA分别将第1跳排队时间缩短了2.3倍、1.7倍和1.6倍。

如今，随着利用率接近25%，数据中心的高拥塞丢包率。因此，平均负载保持在25%左右，以控制延迟。我们注意到，与ECMP相比，DRILL允许提供商使用额外10% (10% more)的带宽容量，同时在25%负载下保持99.99%分位的FCT低于ECMP。也就是说，与ECMP相比，DRILL在相同尾部FCT性能的情况下可承受高1.4倍的载荷，比CONGA高1.3倍，比Presto高1.2倍。

DRILL优雅地向外和向上扩展。我们研究了使用“横向扩展”方法的影响，即，我们使用大量性能较差的交换机，而不是数量较少但功能更强的交换机，来构建具有相同总体核心容量的网络。图7显示了具有16个spine和16个leaf的网络的结果，每个spine和leaf连接到20个主机，其中所有链路均为10Gbps。请注意，此网络在使用链路较慢的交换机时，提供了与先前实验相同的核心容量。我们应用相同的负载，观察到所有方案（包括DRILL）的性能都会下降。这是因为链接越慢，队列消耗越慢；因此，次优（suboptimal）负载均衡决策的负面影响更大。然而，在这种情况下，与其他方案相比，DRILL的收益更为显著。也就是说，DRILL可更优雅地向外扩展。在重负载下差异更大，例如，在80%负载下，ECMP、CONGA和DRILL的平均延迟分别减少2.1倍、1.6倍和1.4倍。图8显示了30%和80%负载时FCT的CDF。

在不同大小和超额订阅率的网络中，我们没有看到显著的性能差异，但是在相同的负载和链路速度下。图9（a）和图9（b）分别显示了两个网络的FCT的CDF两个示例，其中，每个网络有20个spine，16个leaf连接20台主机（即1:1的订阅比率），以及12个spine，16个leaf连接20台主机（即5:3的订阅比率），其中所有链路均为10Gbps，并且在这两种情况下，负载均为80%。

我们还测试了DRILL在具有两个以上阶段（如VL2和fat tree）的CLOS拓扑中平衡负载的能力。图10显示了一个VL2网络的实验结果，该网络有16个ToR交换机，每个交换机通过1Gbps链路连接到20台主机，8个聚合交换机和4个中间交换机。核心链路为10Gbps5。我们将20%和70%的负载放在网络上。图10显示，在这样的网络中，DRILL可以有效地缩短FCT。

我们还测试了每个交换机中转发引擎数量方面的规模效应，发现其对DRILL(2,1) FCT的影响可以忽略不计，例如，我们发现在80%负载下，1和48个引擎交换机之间的平均FCT差异小于1%。

DRILL具有最少的数据包重新排序。前面的数据显示，尽管有重新排序，FCT仍然很低，但接下来我们将深入挖掘原因。图11（a）显示了在80%负载下，使用与本节第一个实验相同的设置，根据TCP重复ACK的数量测量的重新排序量。与DRILL和Presto不同，ECMP和CONGA不会导致重新排序。作为strawman较初级的比较，我们还显示了在无负载感知的情况下，每个数据包随机（沿着独立的随机最短路径转发每个数据包）和每个数据包循环（RR）（沿着最短路径转发每个数据包循环）的重排序量，以及在其薄层（shim layer）之前测量的Presto。我们注意到两个重要结论。首先，每数据包Random、RR和DRILL具有相同的负载均衡粒度，但DRILL显著降低了数据包的重新排序。这说明了本地负载感知如何在路径间保持队列的高度平衡。

其次，即使在重载情况下，DRILL的重新排序程度也很少达到TCP重传阈值。例如，在80%负载下，只有0.4%的流具有任何重复的ack。这比没有使用薄层前的每数据包随机、RR和Presto分别低8倍、7.3倍和3.3倍。另外，在DRILL下，只有0.02%的流的重传阈值超过了典型的TCP重传阈值。请注意，与每数据包随机和RR相比，Presto会导致对更少的流进行重新排序，但会增加触发过多（例如>3）重复ACK的流的数量。这是因为Presto的粗力度flowcell转发屏蔽了大多数流的重新排序，使大多数流适合单个flowcell。然而，在flowcell被重新排序的情况下，与每包方案相比，其较大的包数导致更多的重复ACK生成。在低负载下，很少有流接收到任何重复的ack，例如，在20%负载下，不到0.8%的流在任何这些方案下接收到任何重复的ack。这种最小程度的重新排序说明了为什么使用和不使用薄层的DRILL具有非常相似的性能。

重新排序也会增加接收端主机CPU开销。操作系统通常会执行优化，如通用接收卸载（GRO），以合并传入数据包的突发，从而减少每个数据包的处理开销。GRO通过合并流的数据包来执行每流数据包批处理，只要数据包按顺序到达且批大小低于阈值（64KB）。如果批大小超过该阈值，或者如果接收到无序数据包，GRO将发送到更高的层。因此，过度的重新排序会增加批处理的数量，从而增加CPU开销。然而，由于DRILL很少导致重新排序，即使在负载下，它对GRO的性能影响微乎其微。例如，在80%负载下，DRILL增加的批次数不到0.5%。

DRILL优雅地处理失败。尽管大规模数据中心显示出高可靠性，大多数链路的可靠性高于4个9，但在每个时间点至少有一个故障的概率仍然很高。因此，优雅地处理故障对于任何负载均衡器来说都是必不可少的。我们在3种故障场景下测试了DRILL的性能：（a）一个单leaf-spine链接故障，因为单leaf-spine链接故障是数据中心最常见的故障案例，（b）10个随机选择的leaf-spine链接故障, 这是一个罕见但仍有可能的案例。即使在大型数据中心中，大的组相关链路故障也很少见，只有10%的故障组（停机时间同时发生或相近的故障）包含四个以上的故障。我们将系统加载到可用核心容量的90%。我们观察到，DRILL和Presto在处理单个故障时最有效，而DRILL和CONGA在处理多个故障时最有效（图11（b、c）和图12）。这是因为CONGA将负载转移到具有更大容量的拓扑部分，而DRILL打破了非对称路径之间的速率依赖关系，有效地允许流获取可用带宽，提高其速率，并更快地完成。请注意，在所有这些情况下，DRILL的性能在有薄层和无薄层的情况下几乎相同，因为其重新排序的程度非常低，很少达到TCP的重新传输阈值。

由于DRILL依赖于OSPF来了解拓扑变化，因此它受到该协议对拓扑变化的反应和传播延迟的限制。在我们的实验中，这种延迟的影响可以忽略不计。在70%负载和5个链路故障的实验中，理想DRILL（一种理想化的DRILL变体，可即时学习故障并对故障作出反应）的中值FCT为3.49 ms，比DRILL提高不到0.6%。

DRILL在具有异构设备的非对称拓扑中非常有效。如第3.4节所述，DRILL可在不对称拓扑中运行，例如，具有异构链路和不平衡条带的拓扑。图13显示了一个带有16个leaf的拓扑的实验结果，   ，每个通过10Gbps链路连接到48个主机，16个spine，   . 每个leaf L_i通过两条10Gbps链路连接到spine    和   ，并通过一条10Gbps链路连接到其他spine。除了CONGA和Presto之外，我们还将DRILL与WCMP进行了比较，后者旨在提高ECMP在不对称CLO中的性能。我们观察到，DRILL和CONGA在这种拓扑中更有效，并且比Presto和WCMP实现更低的FCT。

DRILL减少了incast场景中的尾部延迟。数据中心中一种常见且令人烦恼的流量模式是incast，它导致过度拥塞和数据包丢失。除了谷歌最近的一项研究报告了incast在不同层引起的数据包丢失外，incast的大部分工作都是研究集群内的问题（通过一个交换机或树形拓扑连接的主机），自然只关注最后一跳缓冲区的溢出（连接到接收端）. 我们的实验表明，在多根拓扑中，incast流量模式也会触发其他层的缓冲区溢出。此外，我们的结果强调了一个事实，即这个问题与负载均衡交织在一起，可以通过能够对微突发做出反应的敏捷负载均衡器来缓解微突发。图14（a，b）给出了一个网络示例，该网络类似于本节中的第一个实验，分别在20%和35%的典型负载下运行incast应用程序，其中10%的主机向10%的其他主机（均随机选择）发送10KB流的同步请求。如前所述，使用提取的背景流量和到达间隔时间。DRILL显著降低了尾部延迟，例如，在20%的负载下，它的FCT比CONGA和Presto分别低2.1倍和2.6倍。这是因为这种高度突发的流量模式在第一跳时会导致微突发，DRILL可以迅速转移负载并缓解热点上的拥塞。通过更好地平衡spine上的负载，还可以降低spine上形成热点的风险。图14（c）显示了排队和分组丢失发生的位置。DRILL几乎消除了第一跳排队和丢包，并显著减少了第二跳中的这些指标。

合成工作负载。除了跟踪驱动的工作负载外，与之前的工作类似，我们还使用了一组合成工作负载，已知这些工作负载要么经常出现在数据中心中，要么对负载均衡设计具有挑战性：Stride(x)，其中服务器[i]将流发送到服务器[(i+x) mod number of server]，Random，其中每台服务器与一个随机目的地进行通信，该目的地与自身不在同一个leaf下。我们使用Stride(8)和Shuffle，其中每个服务器以随机顺序向所有其他服务器发送流。我们使用1GB的“大象”流，此外，我们每100毫秒发送50 KB的“老鼠流”。我们使用具有4个leaf和4个spine交换机的CLOS，每个leaf连接到8个主机，其中所有链路的容量均为1Gbps。表1报告了老鼠流FCT的平均值和99.99%分位值以及大象流的平均流量，均通过ECMP标准化。对于随机和Stride工作负载，DRILL显著减少老鼠流的时延，尤其是尾部时延，并实现更高的大象流的吞吐量。由于Shuffle工作负载在最后一跳时主要处于瓶颈状态，因此没有一个经过测试的方案能够显著改善ECMP。

硬件和可部署性注意事项。我们用不到400行代码在Verilog中实现了DRILL。我们使用Xilinx Vivado Design Suite 2014.4和面积估算方法估算DRILL的面积开销。DRILL预计需要0.04mm^2的芯片面积。我们估计该值小于典型交换机芯片面积的1%。这证明了在硬件中实现DRILL的可行性和易用性。DRILL涉及两个附加组件。在拓扑不对称的情况下，交换机需要计算每个对称组件的流量权重；这可以在交换机本地的控制软件中完成（如果通过路由算法可以获得拓扑信息），也可以通过中央控制器完成。或者，DRILL可以使用薄层，部署在虚拟机监控程序中。正如我们所展示的，这并不总是必要的，并且其他文献已经证明了它的可行性。

与基于宏观流量的常用负载均衡方法相反，我们探索了微观负载均衡：使网络结构能够基于每个交换机的本地流量信息在微妙的时间尺度上做出决策，解决了这种方法的挑战，包括硬件可行性、包重排序和不对称性。我们的实验表明，在CLOS网络中，我们的简单且可证明稳定的切换调度算法DRILL的性能优于最先进的负载均衡器，特别是在高负载和incast情况下。DRILL通过将网络分解为对称部分来适应不对称性。未来工作的途径包括研究其他拓扑中的微负载均衡，以及具有多个转发引擎的交换机中延迟队列信息的影响。

参考文献：Ghorbani, Soudeh, et al. “DRILL: Micro Load Balancing for Low-Latency Data Center Networks.” Sigcomm2017.