{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:17:30Z","timestamp":1761621450979,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:00:00Z","timestamp":1558396800000},"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":["SIGCOMM Comput. Commun. Rev."],"published-print":{"date-parts":[[2019,5,21]]},"abstract":"<jats:p>By enhancing the traditional static network (e.g., based on electric switches) with a dynamic topology (e.g., based on reconfigurable optical switches), emerging reconfigurable data centers introduce unprecedented flexibilities in how networks can be optimized toward the workload they serve. However, such hybrid data centers are currently limited by a restrictive routing policy enforcing artificial segregation: each network flow can only use either the static or the flexible topology, but not a combination of the two.<\/jats:p>\n          <jats:p>This paper explores the algorithmic problem of supporting more general routing policies, which are not limited by segregation. While the potential benefits of non-segregated routing have been demonstrated in recent work, the underlying algorithmic complexity is not well-understood.<\/jats:p>\n          <jats:p>We present a range of novel results on the algorithmic complexity of non-segregated routing. In particular, we show that in certain specific scenarios, optimal data center topologies with nonsegregated routing policies can be computed in polynomial-time. In many variants of the problem, however, introducing a more flexible routing comes at a price of complexity: we prove several important variants to be NP-hard.<\/jats:p>","DOI":"10.1145\/3336937.3336939","type":"journal-article","created":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T18:01:38Z","timestamp":1558634498000},"page":"2-8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["On the Complexity of Non-Segregated Routing in Reconfigurable Data Center Architectures"],"prefix":"10.1145","volume":"49","author":[{"given":"Klaus-Tycho","family":"Foerster","sequence":"first","affiliation":[{"name":"University of Vienna, Austria"}]},{"given":"Maciej","family":"Pacut","sequence":"additional","affiliation":[{"name":"University of Wroclaw, Poland"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"University of Vienna, Austria"}]}],"member":"320","published-online":{"date-parts":[[2019,5,21]]},"reference":[{"key":"e_1_2_1_1_2","doi-asserted-by":"crossref","unstructured":"Faez Ahmed et al. 2017. Diverse Weighted Bipartite b-Matching. In IJCAI.   Faez Ahmed et al. 2017. Diverse Weighted Bipartite b-Matching. In IJCAI .","DOI":"10.24963\/ijcai.2017\/6"},{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1402946.1402967"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.11.036"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.12.008"},{"key":"e_1_2_1_5_2","unstructured":"Chen Avin Kaushik Mondal and Stefan Schmid. 2017. Demand-Aware Network Designs of Bounded Degree. In DISC.  Chen Avin Kaushik Mondal and Stefan Schmid. 2017. Demand-Aware Network Designs of Bounded Degree. In DISC ."},{"key":"e_1_2_1_6_2","volume-title":"Push-Down Trees: Optimal Self-Adjusting Complete Trees. CoRR abs\/1807.04613v1","author":"Avin Chen","year":"2018","unstructured":"Chen Avin , Kaushik Mondal , and Stefan Schmid . 2018b. Push-Down Trees: Optimal Self-Adjusting Complete Trees. CoRR abs\/1807.04613v1 ( 2018 ). Chen Avin, Kaushik Mondal, and Stefan Schmid. 2018b. Push-Down Trees: Optimal Self-Adjusting Complete Trees. CoRR abs\/1807.04613v1 (2018)."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737431"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3310165.3310170"},{"key":"e_1_2_1_9_2","volume-title":"ReNets: Toward Statically Optimal Self-Adjusting Networks. CoRR arXiv:1904.03263","author":"Avin Chen","year":"2019","unstructured":"Chen Avin and Stefan Schmid . 2019. ReNets: Toward Statically Optimal Self-Adjusting Networks. CoRR arXiv:1904.03263 ( 2019 ). Chen Avin and Stefan Schmid. 2019. ReNets: Toward Statically Optimal Self-Adjusting Networks. CoRR arXiv:1904.03263 (2019)."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2619239.2626328"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.05.014"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2013.2253120"},{"key":"e_1_2_1_13_2","unstructured":"Li Chen et al. 2017. Enabling Wide-Spread Communications on Optical Fabric with MegaSwitch. In NSDI.   Li Chen et al. 2017. Enabling Wide-Spread Communications on Optical Fabric with MegaSwitch. In NSDI ."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13731-0_39"},{"key":"e_1_2_1_15_2","unstructured":"Nikhil Devanur et al. 2016. Stable Matching Algorithm for an Agile Reconfigurable Data Center Interconnect. Technical Report. Microsoft Research.  Nikhil Devanur et al. 2016. Stable Matching Algorithm for an Agile Reconfigurable Data Center Interconnect . Technical Report. Microsoft Research."},{"key":"e_1_2_1_16_2","unstructured":"Ramakrishnan Durairajan et al. 2018. GreyFiber: A System for Providing Flexible Access to Wide-Area Connectivity. arXiv:1807.05242 (2018).  Ramakrishnan Durairajan et al. 2018. GreyFiber: A System for Providing Flexible Access to Wide-Area Connectivity. arXiv:1807.05242 (2018)."},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1851275.1851223"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"Thomas Fenz et al. 2019. Efficient Non-Segregated Routing for Reconfigurable Demand-Aware Networks. In IFIP Networking.  Thomas Fenz et al. 2019. Efficient Non-Segregated Routing for Reconfigurable Demand-Aware Networks. In IFIP Networking .","DOI":"10.23919\/IFIPNetworking.2019.8816859"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3230718.3230722"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934911"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2017.09.020"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1594977.1592576"},{"key":"e_1_2_1_23_2","unstructured":"Chuanxiong Guo et al. 2009. BCube: a high performance server-centric network architecture for modular data centers. In SIGCOMM.  Chuanxiong Guo et al. 2009. BCube: a high performance server-centric network architecture for modular data centers. In SIGCOMM ."},{"key":"e_1_2_1_24_2","unstructured":"Matt Hall Vijay Chidambaram and Ramakrishnan Durairajan. 2018. vFiber: Virtualizing Unused Optical Fibers (Extended Abstract). In NSDI.  Matt Hall Vijay Chidambaram and Ramakrishnan Durairajan. 2018. vFiber: Virtualizing Unused Optical Fibers (Extended Abstract). In NSDI ."},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2018436.2018442"},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"Sikder Huq and Sukumar Ghosh. 2017. Locally Self-Adjusting Skip Graphs. In ICDCS.  Sikder Huq and Sukumar Ghosh. 2017. Locally Self-Adjusting Skip Graphs. In ICDCS .","DOI":"10.1109\/ICDCS.2017.249"},{"key":"e_1_2_1_27_2","doi-asserted-by":"crossref","unstructured":"Su Jia et al. 2017. Competitive analysis for online scheduling in software-defined optical WAN. In INFOCOM.  Su Jia et al. 2017. Competitive analysis for online scheduling in software-defined optical WAN. In INFOCOM .","DOI":"10.1109\/INFOCOM.2017.8056969"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934904"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/2414752"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00140-1"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098836"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/060664793"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.003"},{"key":"e_1_2_1_34_2","unstructured":"He Liu et al. 2014. Circuit Switching Under the Radar with REACToR. In NSDI.   He Liu et al. 2014. Circuit Switching Under the Radar with REACToR. In NSDI ."},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2716281.2836126"},{"key":"e_1_2_1_36_2","unstructured":"Vincent Liu et al. 2013. F10: A Fault-Tolerant Engineered Network. In NSDI.   Vincent Liu et al. 2013. F10: A Fault-Tolerant Engineered Network. In NSDI ."},{"key":"e_1_2_1_37_2","doi-asserted-by":"crossref","unstructured":"Luo Long et al. 2019. DaRTree: Deadline-Aware Multicast Transfers in Reconfigurable Wide-Area Networks. In IEEE IWQoS.  Luo Long et al. 2019. DaRTree: Deadline-Aware Multicast Transfers in Reconfigurable Wide-Area Networks. In IEEE IWQoS .","DOI":"10.1145\/3326285.3329063"},{"key":"e_1_2_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098838"},{"key":"e_1_2_1_39_2","volume-title":"Expanding across time to deliver bandwidth efficiency and low latency. CoRR abs\/1903.12307","author":"Mellette William M.","year":"2019","unstructured":"William M. Mellette , Rajdeep Das , Yibo Guo , Rob McGuinness , Alex C. Snoeren , and George Porter . 2019. Expanding across time to deliver bandwidth efficiency and low latency. CoRR abs\/1903.12307 ( 2019 ). William M. Mellette, Rajdeep Das, Yibo Guo, Rob McGuinness, Alex C. Snoeren, and George Porter. 2019. Expanding across time to deliver bandwidth efficiency and low latency. CoRR abs\/1903.12307 (2019)."},{"key":"e_1_2_1_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_21"},{"key":"e_1_2_1_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2017.2782753"},{"key":"e_1_2_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063952"},{"key":"e_1_2_1_43_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.4"},{"key":"e_1_2_1_44_2","doi-asserted-by":"crossref","unstructured":"Bruna Peres et al. 2019. Distributed Self-Adjusting Tree Networks. In INFOCOM.  Bruna Peres et al. 2019. Distributed Self-Adjusting Tree Networks. In INFOCOM .","DOI":"10.1109\/INFOCOM.2019.8737417"},{"key":"e_1_2_1_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2015.2410313"},{"key":"e_1_2_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230570"},{"key":"e_1_2_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/1868447.1868455"},{"key":"e_1_2_1_48_2","volume-title":"Jellyfish: Networking Data Centers Randomly","author":"Ankit Singla","year":"2012","unstructured":"Ankit Singla et al. 2012 . Jellyfish: Networking Data Centers Randomly . In NSDI. USENIX Association , 225\u2013238. Ankit Singla et al. 2012. Jellyfish: Networking Data Centers Randomly. In NSDI. USENIX Association, 225\u2013238."},{"key":"e_1_2_1_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"},{"key":"e_1_2_1_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-017-9546-x"},{"key":"e_1_2_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851222"},{"key":"e_1_2_1_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2016.2626784"},{"key":"e_1_2_1_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098837"},{"key":"e_1_2_1_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2342356.2342440"},{"key":"e_1_2_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098849"}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3336937.3336939","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3336937.3336939","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:25Z","timestamp":1750273645000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3336937.3336939"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,21]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,5,21]]}},"alternative-id":["10.1145\/3336937.3336939"],"URL":"https:\/\/doi.org\/10.1145\/3336937.3336939","relation":{},"ISSN":["0146-4833"],"issn-type":[{"type":"print","value":"0146-4833"}],"subject":[],"published":{"date-parts":[[2019,5,21]]},"assertion":[{"value":"2019-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}