Online Dynamic B-Matching
- 5 March 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 48 (3), 99-108
- https://doi.org/10.1145/3453953.3453976
Abstract
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≥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.Keywords
This publication has 52 references indexed in Scilit:
- Improved approximability and non-approximability results for graph diameter decreasing problemsTheoretical Computer Science, 2012
- Understanding data center traffic characteristicsACM SIGCOMM Computer Communication Review, 2010
- On-line bipartite matching made simpleACM SIGACT News, 2008
- AdWords and generalized online matchingJournal of the ACM, 2007
- Matching output queueing with a combined input/output-queued switchIEEE Journal on Selected Areas in Communications, 1999
- The iSLIP scheduling algorithm for input-queued switchesIEEE/ACM Transactions on Networking, 1999
- Competitive paging algorithmsJournal of Algorithms, 1991
- A strongly competitive randomized paging algorithmAlgorithmica, 1991
- A polynomial algorithm for b-matchings: An alternative approachInformation Processing Letters, 1987
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985