Lune

INFOCOM2023Top-tier venue

Dynamic Demand-Aware Link Scheduling for Reconfigurable Datacenters

Kathrin Hanauer, Monika Henzinger, Lara Ost, Stefan Schmid

Abstract

Emerging reconfigurable datacenters allow to dynamically adjust the network topology in a demand-aware manner. These datacenters rely on optical switches which can be reconfigured to provide direct connectivity between racks, in the form of edge-disjoint matchings. While state-of-the-art optical switches in principle support microsecond reconfigurations, the demand-aware topology optimization constitutes a bottleneck.

This paper proposes a dynamic algorithms approach to improve the performance of reconfigurable datacenter networks, by supporting faster reactions to changes in the traffic demand. This approach leverages the temporal locality of traffic patterns in order to update the interconnecting matchings incrementally, rather than recomputing them from scratch. In particular, we present six (batch-)dynamic algorithms and compare them to static ones. We conduct an extensive empirical evaluation on 176 synthetic and 39 real-world traces, and find that dynamic algorithms can both significantly improve the running time and reduce the number of changes to the configuration, especially in networks with high temporal locality, while retaining matching weight.

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.

2 top-tier papers have 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

  • Approximation Algorithms for Minimizing Congestion in Demand-Aware Networks cites Sirius: A Flat Datacenter Network with Nanosecond Optical Switching
  • Optimizing Reconfigurable Optical Datacenters: The Power of Randomization cites Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter Topologies
  • Optimizing Reconfigurable Optical Datacenters: The Power of Randomization cites Sirius: A Flat Datacenter Network with Nanosecond Optical Switching
  • Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter Topologies cites Sirius: A Flat Datacenter Network with Nanosecond Optical Switching
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Approximation Algorithms for Minimizing Congestion in Demand-Aware NetworksWenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, Long Luo et al.INFOCOM 2024 · 4 citations
  2. Optimizing Reconfigurable Optical Datacenters: The Power of RandomizationMarcin Bienkowski, David Fuchssteiner, Stefan SchmidSC 2023 · 2 citations

Builds on3

  1. Sirius: A Flat Datacenter Network with Nanosecond Optical SwitchingHitesh Ballani, Paolo Costa, Raphael Behrendt, Daniel Cletheroe et al.SIGCOMM 2020 · 204 citations
  2. SiP-ML: high-bandwidth optical network interconnects for machine learning trainingMehrdad Khani Shirkoohi, Manya Ghobadi, Mohammad Alizadeh, Ziyi Zhu et al.SIGCOMM 2021 · 94 citations
  3. Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter TopologiesKathrin Hanauer, Monika Henzinger, Stefan Schmid, Jonathan TrummerINFOCOM 2022 · 11 citations

Related papers

  1. NegotiaToR: Towards A Simple Yet Effective On-demand Reconfigurable Datacenter NetworkCong Liang, Xiangli Song, Jing Cheng, Mowei Wang et al.SIGCOMM 2024 · 27 citations
  2. Lazy Self-Adjusting Bounded-Degree Networks for the Matching ModelEvgeniy Feder, Ichha Rathod, Punit Shyamsukha, Robert Sama et al.INFOCOM 2022 · 7 citations
  3. Scheduling for Weighted Flow and Completion Times in Reconfigurable NetworksMichael Dinitz, Benjamin MoseleyINFOCOM 2020 · 18 citations
  4. Working Set Theorems for Routing in Self-Adjusting Skip List NetworksChen Avin, Iosif Salem, Stefan SchmidINFOCOM 2020 · 5 citations
  5. ATRO: A Fast Algorithm for Topology Engineering of Reconfigurable Datacenter NetworksYingming Mao, Qiaozhu Zhai, Ximeng Liu, Xinchi Han et al.INFOCOM 2026 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines