Approximation Algorithms for Minimizing Congestion in Demand-Aware Networks
Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, Long Luo, Stefan Schmid
Abstract
Emerging reconfigurable optical communication technologies allow to enhance datacenter topologies with demand-aware links optimized towards traffic patterns. This paper studies the algorithmic problem of jointly optimizing topology and routing in such demand-aware networks to minimize congestion, along two dimensions: (1) splittable or unsplittable flows, and (2) whether routing is segregated, i.e., whether routes can or cannot combine both demand-aware and demand-oblivious (static) links.For splittable and segregated routing, we show that the problem is generally 2-approximable, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we establish upper and lower bounds of O (log m/ log log m) and Ω (log m/ log log m), respectively, for polynomial-time approximation algorithms, where m is the number of static links. We further reveal that under un-/splittable and non-segregated routing, even for demands of a single source (resp., d estina tion), the problem cannot be approximated better than unless P=NP, where cmax(resp., cmin) denotes the maximum (resp., minimum) capacity. It remains NP-hard for uniform capacities, but is tractable for a single commodity and uniform capacities.Our trace-driven simulations show a significant reduction in network congestion compared to existing solutions.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Sirius: A Flat Datacenter Network with Nanosecond Optical Switching cites Expanding across time to deliver bandwidth efficiency and low latency
- Jupiter evolving: transforming google's datacenter network via optical circuit switches and software-defined networking cites Sirius: A Flat Datacenter Network with Nanosecond Optical Switching
- Jupiter evolving: transforming google's datacenter network via optical circuit switches and software-defined networking cites Expanding across time to deliver bandwidth efficiency and low latency
Cited by top-tier papers1
Builds on7
- Jupiter evolving: transforming google's datacenter network via optical circuit switches and software-defined networkingLeon Poutievski, Omid Mashayekhi, Joon Ong, Arjun Singh et al.SIGCOMM 2022 · 230 citations
- Sirius: A Flat Datacenter Network with Nanosecond Optical SwitchingHitesh Ballani, Paolo Costa, Raphael Behrendt, Daniel Cletheroe et al.SIGCOMM 2020 · 204 citations
- Expanding across time to deliver bandwidth efficiency and low latencyWilliam M. Mellette, Rajdeep Das, Yibo Guo, Rob McGuinness et al.NSDI 2020 · 194 citations
- Shortest Paths in a Hybrid Network ModelJohn Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler et al.SODA 2020 · 23 citations
- Scheduling for Weighted Flow and Completion Times in Reconfigurable NetworksMichael Dinitz, Benjamin MoseleyINFOCOM 2020 · 18 citations
Related papers
- Optimal oblivious reconfigurable networksDaniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon et al.STOC 2022 · 18 citations
- Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter TopologiesKathrin Hanauer, Monika Henzinger, Stefan Schmid, Jonathan TrummerINFOCOM 2022 · 11 citations
- Dynamic Demand-Aware Link Scheduling for Reconfigurable DatacentersKathrin Hanauer, Monika Henzinger, Lara Ost, Stefan SchmidINFOCOM 2023 · 9 citations
- Optimizing Reconfigurable Optical Datacenters: The Power of RandomizationMarcin Bienkowski, David Fuchssteiner, Stefan SchmidSC 2023 · 2 citations
- Designing Optimal Compact Oblivious Routing for Datacenter Networks in Polynomial TimeKanatip Chitavisutthivong, Chakchai So-In, Sucha SupittayapornpongINFOCOM 2023 · 2 citations
