{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T19:06:16Z","timestamp":1770491176908,"version":"3.49.0"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,3,5]],"date-time":"2021-03-05T00:00:00Z","timestamp":1614902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2021,3,5]]},"abstract":"<jats:p>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\u22651 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.<\/jats:p>","DOI":"10.1145\/3453953.3453976","type":"journal-article","created":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T04:12:32Z","timestamp":1615003952000},"page":"99-108","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Online Dynamic B-Matching"],"prefix":"10.1145","volume":"48","author":[{"given":"Marcin","family":"Bienkowski","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Fuchssteiner","sequence":"additional","affiliation":[{"name":"University of Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Marcinkowski","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"University of Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Competitive analysis of randomized paging algorithms. Theoretical Computer Science, 234(1--2):203--218","author":"Achlioptas D.","year":"2000","unstructured":"D. Achlioptas , M. Chrobak , and J. Noga . Competitive analysis of randomized paging algorithms. Theoretical Computer Science, 234(1--2):203--218 , 2000 . D. Achlioptas, M. Chrobak, and J. Noga. Competitive analysis of randomized paging algorithms. Theoretical Computer Science, 234(1--2):203--218, 2000."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1402958.1402967"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486031"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90178-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3393691.3394205"},{"key":"e_1_2_1_6_1","volume-title":"An online matching model for self-adjusting tor-to-tor networks. arXiv preprint arXiv:2006.11148","author":"Avin C.","year":"2020","unstructured":"C. Avin , C. Griner , I. Salem , and S. Schmid . An online matching model for self-adjusting tor-to-tor networks. arXiv preprint arXiv:2006.11148 , 2020 . 106 Performance Evaluation Review , Vol . 48, No. 3, December 2020 C. Avin, C. Griner, I. Salem, and S. Schmid. An online matching model for self-adjusting tor-to-tor networks. arXiv preprint arXiv:2006.11148, 2020. 106 Performance Evaluation Review, Vol. 48, No. 3, December 2020"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.12.008"},{"key":"e_1_2_1_8_1","first-page":"1","volume-title":"Proc. Int. Symp. on Distributed Computing (DISC)","volume":"91","author":"Avin C.","year":"2017","unstructured":"C. Avin , K. Mondal , and S. Schmid . Demand-aware network designs of bounded degree . In Proc. Int. Symp. on Distributed Computing (DISC) , volume 91 of LIPIcs, pages 5: 1 -- 5 :16, 2017 . C. Avin, K. Mondal, and S. Schmid. Demand-aware network designs of bounded degree. In Proc. Int. Symp. on Distributed Computing (DISC), volume 91 of LIPIcs, pages 5:1--5:16, 2017."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737431"},{"key":"e_1_2_1_10_1","volume-title":"Proc. Latin American Theoretical Informatics Symposium (LATIN)","author":"Avin C.","year":"2020","unstructured":"C. Avin , K. Mondal , and S. Schmid . Dynamically optimal self-adjusting single-source tree networks . In Proc. Latin American Theoretical Informatics Symposium (LATIN) , 2020 . C. Avin, K. Mondal, and S. Schmid. Dynamically optimal self-adjusting single-source tree networks. In Proc. Latin American Theoretical Informatics Symposium (LATIN), 2020."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3310165.3310170"},{"key":"e_1_2_1_12_1","volume-title":"Renets: Toward statically optimal self-adjusting networks. arXiv preprint arXiv:1904.03263","author":"Avin C.","year":"2019","unstructured":"C. Avin and S. Schmid . Renets: Toward statically optimal self-adjusting networks. arXiv preprint arXiv:1904.03263 , 2019 . C. Avin and S. Schmid. Renets: Toward statically optimal self-adjusting networks. arXiv preprint arXiv:1904.03263, 2019."},{"key":"e_1_2_1_13_1","first-page":"319","volume-title":"Proc. ACM SIGCOMM","author":"Azimi N. H.","year":"2014","unstructured":"N. H. Azimi , Z. A. Qazi , H. Gupta , V. Sekar , S. R. Das , J. P. Longtin , H. Shah , and A. Tanwer . Firefly: a reconfigurable wireless data center fabric using free-space optics . In Proc. ACM SIGCOMM , pages 319 -- 330 , 2014 . N. H. Azimi, Z. A. Qazi, H. Gupta, V. Sekar, S. R. Das, J. P. Longtin, H. Shah, and A. Tanwer. Firefly: a reconfigurable wireless data center fabric using free-space optics. In Proc. ACM SIGCOMM, pages 319--330, 2014."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387514.3406221"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1672308.1672325"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.05.014"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360443.1360462"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/290169"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75520-3_24"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.772430"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13731-0_39"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213992"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.7"},{"key":"e_1_2_1_24_1","volume-title":"Scheduling for weighted flow and completion times in reconfigurable networks. arXiv preprint arXiv:2001.07784","author":"Dinitz M.","year":"2020","unstructured":"M. Dinitz and B. Moseley . Scheduling for weighted flow and completion times in reconfigurable networks. arXiv preprint arXiv:2001.07784 , 2020 . M. Dinitz and B. Moseley. Scheduling for weighted flow and completion times in reconfigurable networks. arXiv preprint arXiv:2001.07784, 2020."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9793-0"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851223"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.23919\/IFIPNetworking.2019.8816859"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230718.3230722"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336937.3336939"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3351452.3351464"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934911"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.INS.2017.09.020"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592568.1592577"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2017.249"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8056969"},{"key":"e_1_2_1_37_1","first-page":"87","volume-title":"Proc. ACM SIGCOMM","author":"Jin X.","year":"2020","unstructured":"X. Jin , Y. Li , D. Wei , S. Li , J. Gao , L. Xu , G. Li , Performance Evaluation Review , Vol. 48, No. 3, December 2020 107 W. Xu, and J. Rexford. Optimizing bulk transfers with software-defined optical WAN . In Proc. ACM SIGCOMM , pages 87 -- 100 , 2016. X. Jin, Y. Li, D. Wei, S. Li, J. Gao, L. Xu, G. Li, Performance Evaluation Review, Vol. 48, No. 3, December 2020 107 W. Xu, and J. Rexford. Optimizing bulk transfers with software-defined optical WAN. In Proc. ACM SIGCOMM, pages 87--100, 2016."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.122111.00069"},{"key":"e_1_2_1_39_1","volume-title":"An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1--2):319--325","author":"Kalyanasundaram B.","year":"2000","unstructured":"B. Kalyanasundaram and K. R. Pruhs . An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1--2):319--325 , 2000 . B. Kalyanasundaram and K. R. Pruhs. An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1--2):319--325, 2000."},{"key":"e_1_2_1_40_1","volume-title":"HotNets","author":"Kandula S.","year":"2009","unstructured":"S. Kandula , J. Padhye , and P. Bahl . Flyways to de-congest data center networks . In HotNets , 2009 . S. Kandula, J. Padhye, and P. Bahl. Flyways to de-congest data center networks. In HotNets, 2009."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098836"},{"key":"e_1_2_1_43_1","first-page":"1","volume-title":"NSDI","author":"Liu H.","year":"2014","unstructured":"H. Liu , F. Lu , A. Forencich , R. Kapoor , M. Tewari , G. M. Voelker , G. Papen , A. C. Snoeren , and G. Porter . Circuit switching under the radar with reactor . In NSDI , pages 1 -- 15 , 2014 . H. Liu, F. Lu, A. Forencich, R. Kapoor, M. Tewari, G. M. Voelker, G. Papen, A. C. Snoeren, and G. Porter. Circuit switching under the radar with reactor. In NSDI, pages 1--15, 2014."},{"key":"e_1_2_1_44_1","first-page":"399","volume-title":"NSDI","author":"Liu V.","year":"2013","unstructured":"V. Liu , D. Halperin , A. Krishnamurthy , and T. E. Anderson . F10: A fault-tolerant engineered network . In NSDI , pages 399 -- 412 , 2013 . V. Liu, D. Halperin, A. Krishnamurthy, and T. E. Anderson. F10: A fault-tolerant engineered network. In NSDI, pages 399--412, 2013."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993716"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759073"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"N. McKeown. The islip scheduling algorithm for input-queued switches. IEEE\/ACM transactions on networking 7(2):188--201 1999.  N. McKeown. The islip scheduling algorithm for input-queued switches. IEEE\/ACM transactions on networking 7(2):188--201 1999.","DOI":"10.1109\/90.769767"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_2_1_50_1","volume-title":"Expanding across time to deliver bandwidth efficiency and low latency. arXiv preprint arXiv:1903.12307","author":"Mellette W. M.","year":"2019","unstructured":"W. M. Mellette , R. Das , Y. Guo , R. McGuinness , A. C. Snoeren , and G. Porter . Expanding across time to deliver bandwidth efficiency and low latency. arXiv preprint arXiv:1903.12307 , 2019 . W. M. Mellette, R. Das, Y. Guo, R. McGuinness, A. C. Snoeren, and G. Porter. Expanding across time to deliver bandwidth efficiency and low latency. arXiv preprint arXiv:1903.12307, 2019."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098838"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_21"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764482"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063952"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.4"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2002.1019369"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785956.2787472"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_47"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2015.2410313"},{"key":"e_1_2_1_60_1","volume-title":"Polyhedra and Efficiency. Algorithms and combinatorics","author":"Schrijver A.","year":"2003","unstructured":"A. Schrijver . Combinatorial Optimization : Polyhedra and Efficiency. Algorithms and combinatorics . Springer , 2003 . A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and combinatorics. Springer, 2003."},{"key":"e_1_2_1_61_1","first-page":"225","volume-title":"NSDI","author":"Singla A.","year":"2012","unstructured":"A. Singla , C. Hong , L. Popa , and P. B. Godfrey . Jellyfish: Networking data centers randomly . In NSDI , pages 225 -- 238 , 2012 . A. Singla, C. Hong, L. Popa, and P. B. Godfrey. Jellyfish: Networking data centers randomly. In NSDI, pages 225--238, 2012."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1364\/JOCN.379487"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896377.2901479"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3204412"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1658939.1658943"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2016.2626784"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2377677.2377761"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453953.3453976","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3453953.3453976","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:51Z","timestamp":1750193271000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453953.3453976"}},"subtitle":["With Applications to Reconfigurable Datacenter Networks"],"short-title":[],"issued":{"date-parts":[[2021,3,5]]},"references-count":68,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,3,5]]}},"alternative-id":["10.1145\/3453953.3453976"],"URL":"https:\/\/doi.org\/10.1145\/3453953.3453976","relation":{},"ISSN":["0163-5999"],"issn-type":[{"value":"0163-5999","type":"print"}],"subject":[],"published":{"date-parts":[[2021,3,5]]},"assertion":[{"value":"2021-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}