This paper studies the problem of how to dynamically optimize the topology of a reconfigurable datacenter network in a demand-aware manner: by accounting for the current traffic pattern and providing direct connectivity between frequently communicating racks, the datacenter's bandwidth efficiency can be improved. The underlying algorithmic challenge can be described as an online maximum weight $b$-matching problem, a generalization of maximum weight matching where each node has at most $b \geq 1$ incident matching edges. Recently, Bienkowski et al.~presented an $O(b)$-competitive deterministic algorithm and showed that this is asymptotically optimal. This paper initiates the study of randomized algorithms, and we present a $O(\log b)$-competitive solution and show that this is asymptotically optimal. We complement our theoretical results with extensive trace-driven simulations, based on real-world datacenter workloads.
翻译:本文研究如何以需求意识的方式以动态方式优化可重新构建的数据中心网络的地形学问题:通过考虑到当前的交通模式和提供经常通信的架子之间的直接连接,数据中心的带宽效率可以提高。基本的算法挑战可以描述为在线最大重量($b$-配对)问题,即每个节点最多达到$b\ge q 1美元事件匹配边缘的最大重量匹配的概括化问题。最近,Bienkowski et al.~ 展示了一种以O(b)$为单位的竞争性确定性算法,并展示了这种算法是尽可能最佳的。本文启动了随机化算法的研究,我们提出了一个美元(log b)-美元竞争的解决方案,并展示了这种算法是亚性最佳的。我们用基于真实世界数据中心工作量的广泛的痕量模拟来补充我们的理论结果。