Lune

INFOCOM2024Top-tier venue

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 Ω(cmax⁡cmin⁡)\Omega \left({\frac{{{c_{\max }}}}{{{c_{\min }}}}}\right) 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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. No Traffic to Cry: Traffic-Oblivious Link Deactivation for Green Traffic EngineeringMax Ilsen, Daniel Otten, Nils Aschenbruck, Markus ChimaniINFOCOM 2026 · 1 citation

Builds on7

  1. 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
  2. Sirius: A Flat Datacenter Network with Nanosecond Optical SwitchingHitesh Ballani, Paolo Costa, Raphael Behrendt, Daniel Cletheroe et al.SIGCOMM 2020 · 204 citations
  3. Expanding across time to deliver bandwidth efficiency and low latencyWilliam M. Mellette, Rajdeep Das, Yibo Guo, Rob McGuinness et al.NSDI 2020 · 194 citations
  4. Shortest Paths in a Hybrid Network ModelJohn Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler et al.SODA 2020 · 23 citations
  5. Scheduling for Weighted Flow and Completion Times in Reconfigurable NetworksMichael Dinitz, Benjamin MoseleyINFOCOM 2020 · 18 citations

Related papers

  1. Optimal oblivious reconfigurable networksDaniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon et al.STOC 2022 · 18 citations
  2. Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter TopologiesKathrin Hanauer, Monika Henzinger, Stefan Schmid, Jonathan TrummerINFOCOM 2022 · 11 citations
  3. Dynamic Demand-Aware Link Scheduling for Reconfigurable DatacentersKathrin Hanauer, Monika Henzinger, Lara Ost, Stefan SchmidINFOCOM 2023 · 9 citations
  4. Optimizing Reconfigurable Optical Datacenters: The Power of RandomizationMarcin Bienkowski, David Fuchssteiner, Stefan SchmidSC 2023 · 2 citations
  5. Designing Optimal Compact Oblivious Routing for Datacenter Networks in Polynomial TimeKanatip Chitavisutthivong, Chakchai So-In, Sucha SupittayapornpongINFOCOM 2023 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines