LESS: A Matrix Split and Balance Algorithm for Parallel Circuit (Optical) or Hybrid Data Center Switching and More
LESS: A Matrix Split and Balance Algorithm for Parallel Circuit (Optical) or Hybrid Data Center Switching and More
复制标题
LESS：用于并行电路（光纤）或混合数据中心交换等的矩阵拆分和平衡算法
DOI：
10.1145/3344341.3368807
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Singh, Mohit
中科院分区：
文献类型：
--
作者：
Liu, Liang;Xu, Jun;Singh, Mohit
如何使用高速电路交换机(通常是光交换机)来最有效地提高数据中心网络的交换容量的研究问题已经得到了广泛的研究。在这项工作中，我们专注于一个不同但相关的研究问题，当使用多个(比方说)并行电路交换机时：如何最好地将交换工作负载分割为子工作负载，并将它们作为各自的工作负载分配给交换机，从而使并行交换系统的总工期最小？不幸的是，计算这样的最优分裂是NP困难的，因为当必须改变开关配置时，电路/光开关引起不平凡的重新配置延迟。在这项工作中，我们描述了这个问题的一个较弱的形式：在每行或列和(分别对应于发送或接收机架上的工作量)的约束下，如何最小化中的非零条目总数(从而使总体重构成本保持在较低水平)？虽然这个较弱的问题仍然是NP难的，但我们能够设计出更少的近似算法，它在实践中具有仅有的低逼近比和低的计算复杂性，其中非零条目的数目为。我们的仿真研究表明，在现实的数据中心流量工作负载和参数设置下，较少的结果会产生优异的总体完成时间性能。
The research problem of how to use a high-speed circuit switch, typically an optical switch, to most effectively boost the switching capacity of a datacenter network, has been extensively studied. In this work, we focus on a different but related research problem that arises when multiple (say) parallel circuit switches are used: How to best split a switching workloadinto sub-workloads, and give them to theswitches as their respective workloads, so that the overall makespan of the parallel switching system is minimized? Computing such an optimal split is unfortunately NP-hard, since the circuit/optical switch incurs a nontrivial reconfiguration delay when the switch configuration has to change. In this work, we formulate a weaker form of this problem: How to minimize the total number of nonzero entries in(so that the overall reconfiguration cost can be kept low), under the constraint that every row or column sum of(which corresponds to the workload imposed on a sending or receiving rack respectively) is evenly split? Although this weaker problem is still NP-hard, we are able to design LESS, an approximation algorithm that has a low approximation ratio of onlyin practice and a low computational complexity of only, whereis the number of nonzero entries in. Our simulation studies show that LESS results in excellent overall makespan performances under realistic datacenter traffic workloads and parameter settings.
NXG05-6：可扩展混合电子/光分组交换机中的最小延迟调度
DOI：
--
发表时间：
2006
期刊：
IEEE Globecom 2006
影响因子：
--
作者：
Bin Wu;K. Yeung
通讯作者：
K. Yeung
数据中心的光交换（特邀论文）
DOI：
--
发表时间：
2018
期刊：
International Conference on High Performance Switching and Routing
影响因子：
--
作者：
W. M. Mellette;A. Snoeren;G. Porter
通讯作者：
G. Porter