论文标题
在线动态B匹配与可重新配置数据中心网络的应用程序
Online Dynamic B-Matching With Applications to Reconfigurable Datacenter Networks
论文作者
论文摘要
本文启动了对最大重量$ b $匹配问题的在线算法的研究，这是每个节点最多具有$ b \ geq 1 $相邻匹配边缘的最大重量匹配的概括。问题是由新兴的光学技术引起的，这些光学技术允许通过可重新配置的匹配增强数据中心网络，从而在经常通信的机架之间提供直接连接。这些其他链接可以通过利用工作负载中的空间和时间结构来改善网络性能。我们表明，潜在的算法问题具有与在线分页（又称Caching）的有趣联系，但引入了一个新颖的挑战。我们的主要贡献是在线算法，即$ O（b）$ - 竞争激烈；我们还证明这是渐近的最佳选择。我们基于实际数据中心工作负载以及合成的流量轨迹，通过广泛的痕量驱动模拟来补充理论结果。
This paper initiates the study of online algorithms for the maximum weight $b$-matching problem, a generalization of maximum weight matching where each node has at most $b \geq 1$ adjacent matching edges. The problem is motivated by emerging optical technologies which allow to enhance datacenter networks with reconfigurable matchings, providing direct connectivity between frequently communicating racks. These additional links may improve network performance, by leveraging spatial and temporal structure in the workload. We show that the underlying algorithmic problem features an intriguing connection to online paging (a.k.a. caching), but introduces a novel challenge. Our main contribution is an online algorithm which is $O(b)$-competitive; we also prove that this is asymptotically optimal. We complement our theoretical results with extensive trace-driven simulations, based on real-world datacenter workloads as well as synthetic traffic traces.
