DistroMatch: Distributed Disjoint Weighted Matchings in Demand-Aware Reconfigurable Optical Datacenters
TL;DR
This paper introduces the first distributed approach to trade solution quality for running time via a parameter ε ∈ [0, 1] and provides an extensive empirical evaluation on 87 real-world and synthetic workloads showing scalability and a speedup over state-of-art algorithms up to 1-2 orders of magnitude on most instances while retaining high-quality solutions.
Abstract
Reconfigurable optical circuit switches revolutionize datacenter networks by allowing to adjust the physical topology in a dynamic and demand-aware manner. These switches directly match currently frequently communicating racks, reducing bandwidth tax and hence improving throughput. The underlying optimization problem is essentially the NP-hard Weighted k-Disjoint Matchings problem. Existing efficient solutions to this problem require a centralized controller, which constitutes a scalability bottleneck. This paper introduces the first distributed approach. Our main contributions are four new algorithms and a new approach to trade solution quality for running time via a parameter ε ∈ [0, 1]. Our best algorithm guarantees a \(\frac{1}{3}\)-approximation. We provide an extensive empirical evaluation on 87 real-world and synthetic workloads with billions of edges showing scalability and a speedup over state-of-art algorithms up to 1-2 orders of magnitude on most instances while retaining high-quality solutions.