{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:19:31Z","timestamp":1761621571180,"version":"3.41.0"},"reference-count":41,"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>Emerging reconfigurable data centers introduce the unprecedented flexibility in how the physical layer can be programmed to adapt to current traffic demands. These reconfigurable topologies are commonly hybrid, consisting of static and reconfigurable links, enabled by e.g. an Optical Circuit Switch (OCS) connected to top-of-rack switches in Clos networks. Even though prior work has showcased the practical benefits of hybrid networks, several crucial performance aspects are not well understood.<\/jats:p>\n          <jats:p>In this paper, we study the algorithmic problem of how to jointly optimize topology and routing in reconfigurable data centers with a known traffic matrix, in order to optimize a most fundamental metric, maximum link load. We chart the corresponding algorithmic landscape by investigating both un-\/splittable flows and (non-)segregated routing policies. We moreover prove that the problem is not submodular for all these routing policies, even in multi-layer trees, where a topological complexity classification of the problem reveals that already trees of depth two are intractable.<\/jats:p>\n          <jats:p>However, networks that can be abstracted by a single packet switch (e.g., nonblocking Fat-Tree topologies) can be optimized efficiently, and we present optimal polynomialtime algorithms accordingly. We complement our theoretical results with trace-driven simulation studies, where our algorithms can significantly improve the network load in comparison to the state of the art.<\/jats:p>","DOI":"10.1145\/3453953.3453962","type":"journal-article","created":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T04:12:32Z","timestamp":1615003952000},"page":"39-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Load-Optimization in Reconfigurable Networks"],"prefix":"10.1145","volume":"48","author":[{"given":"Wenkai","family":"Dai","sequence":"first","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus-Tycho","family":"Foerster","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Fuchssteiner","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,5]]},"reference":[{"volume-title":"portal.nersc.gov\/project\/CAL\/doe-miniapps.htm","year":"2016","key":"e_1_2_1_1_1","unstructured":"Characterization of the doe mini-apps. portal.nersc.gov\/project\/CAL\/doe-miniapps.htm , 2016 . Characterization of the doe mini-apps. portal.nersc.gov\/project\/CAL\/doe-miniapps.htm, 2016."},{"key":"e_1_2_1_2_1","volume-title":"Network flows - theory, algorithms and applications","author":"Ahuja R. K.","year":"1993","unstructured":"R. K. Ahuja Network flows - theory, algorithms and applications . Prentice Hall , 1993 . R. K. Ahuja et al. Network flows - theory, algorithms and applications. Prentice Hall, 1993."},{"key":"e_1_2_1_3_1","volume-title":"SIGCOMM","author":"M.","year":"2008","unstructured":"M. Al-Fares et al. A scalable, commodity data center network architecture . In SIGCOMM , 2008 . M. Al-Fares et al. A scalable, commodity data center network architecture. In SIGCOMM, 2008."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486001.2486031"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3393691.3394205"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3310165.3310170"},{"key":"e_1_2_1_7_1","volume-title":"Renets: Statically-optimal demand-aware networks","author":"Avin C.","year":"2021","unstructured":"C. Avin and S. Schmid . Renets: Statically-optimal demand-aware networks . In APOCS. SIAM , 2021 . C. Avin and S. Schmid. Renets: Statically-optimal demand-aware networks. In APOCS. SIAM, 2021."},{"key":"e_1_2_1_8_1","volume-title":"SIGCOMM","author":"Azimi N. H.","year":"2014","unstructured":"N. H. Azimi : a reconfigurable wireless data center fabric using free-space optics . In SIGCOMM , 2014 . N. H. Azimi et al. Firefly: a reconfigurable wireless data center fabric using free-space optics. In SIGCOMM, 2014."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879175"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1953.tb01433.x"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM41043.2020.9155537"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2013.6567015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851223"},{"issue":"138","key":"e_1_2_1_14_1","first-page":"147","article-title":"Efficient non-segregated routing for reconfigurable demand-aware networks","volume":"164","author":"Fenz T.","year":"2020","unstructured":"T. Fenz Efficient non-segregated routing for reconfigurable demand-aware networks . Computer Communications , 164 : 138 -- 147 , 2020 . T. Fenz et al. Efficient non-segregated routing for reconfigurable demand-aware networks. Computer Communications, 164:138 -- 147, 2020.","journal-title":"Computer Communications"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230718.3230722"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336937.3336939"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3351452.3351464"},{"key":"e_1_2_1_18_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman , 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934911"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1364\/JOCN.11.000478"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2018436.2018442"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934904"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644893.1644918"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.6312192"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2716281.2836126"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2020.2986904"},{"key":"e_1_2_1_28_1","volume-title":"NSDI","author":"Mellette W. M.","year":"2020","unstructured":"W. M. Mellette Expanding across time to deliver bandwidth efficiency and low latency . In NSDI , 2020 . W. M. Mellette et al. Expanding across time to deliver bandwidth efficiency and low latency. In NSDI, 2020."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2017.2782753"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043164.2018467"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785956.2787472"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535372.2535397"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2975159"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230570"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/500776"},{"key":"e_1_2_1_36_1","volume-title":"Costly circuits, submodular schedules and approximate carath\u00b4eodory theorems. Queueing Syst., 88(3--4):311--347","author":"Venkatakrishnan S. B.","year":"2018","unstructured":"S. B. Venkatakrishnan Costly circuits, submodular schedules and approximate carath\u00b4eodory theorems. Queueing Syst., 88(3--4):311--347 , 2018 . S. B. Venkatakrishnan et al. Costly circuits, submodular schedules and approximate carath\u00b4eodory theorems. Queueing Syst., 88(3--4):311--347, 2018."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851222"},{"key":"e_1_2_1_38_1","volume-title":"Design, implementation and evaluation of congestion control for multipath TCP","author":"Wischik D.","year":"2011","unstructured":"D. Wischik Design, implementation and evaluation of congestion control for multipath TCP . In NSDI. USENIX Association , 2011 . D. Wischik et al. Design, implementation and evaluation of congestion control for multipath TCP. In NSDI. USENIX Association, 2011."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098837"},{"key":"e_1_2_1_40_1","volume-title":"Achieving efficient routing in reconfigurable dcns. ACM POMACS, 3(3)","author":"Yang Z.","year":"2019","unstructured":"Z. Yang Achieving efficient routing in reconfigurable dcns. ACM POMACS, 3(3) , 2019 . Z. Yang et al. Achieving efficient routing in reconfigurable dcns. ACM POMACS, 3(3), 2019."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.27"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3337821.3337898"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453953.3453962","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3453953.3453962","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.3453962"}},"subtitle":["Algorithms and Complexity of Flow Routing"],"short-title":[],"issued":{"date-parts":[[2021,3,5]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,3,5]]}},"alternative-id":["10.1145\/3453953.3453962"],"URL":"https:\/\/doi.org\/10.1145\/3453953.3453962","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"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"}}]}}