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.
翻译:本文开始研究最大重量($b$)匹配问题的在线算法, 在每个节点最多拥有$b \geq 1美元相邻匹配边缘的地方, 将最大重量匹配的普及化。 问题的起因是新兴的光学技术, 能够通过重新配置匹配加强数据中心网络, 提供经常沟通的架子之间的直接连接。 这些额外的链接可以提高网络的性能, 在工作量中利用空间和时间结构。 我们显示, 根本的算法问题具有与在线调试( a.k.a.caching) 连接的吸引力, 但却带来了新的挑战。 我们的主要贡献是在线算法, 它具有O(b)$- 竞争性; 我们还证明, 这是一种微量的最佳方法。 我们用基于真实世界数据中心工作量和合成交通轨迹的广泛的微动模拟来补充我们的理论结果。