Presentation
SIGN IN TO VIEW THIS PRESENTATION Sign In
Optimizing Reconfigurable Optical Datacenters: The Power of Randomization
DescriptionReconfigurable optical topologies are a promising new technology to improve datacenter network performance and cope with the explosive growth of traffic. In particular, these networks allow to adaptively connect racks between which there is currently much traffic, hence making an optimal use of the bandwidth by avoiding multi-hop forwarding.
This paper studies the dynamic optimization of such reconfigurable topologies, adapting to the traffic in an online manner. The underlying algorithmic problem can be described as an online maximum weight b-matching problem, a generalization of maximum weight matching where each node has at most b>=1 incident matching edges.
We make the case for a randomized approach for matching optimization. Our main contribution is a O(log b)-competitive algorithm and we show that it is asymptotically optimal. This algorithm is exponentially better than the best possible deterministic online algorithm.
We complement our theoretical results with trace-driven simulations, based on real-world datacenter workloads.
This paper studies the dynamic optimization of such reconfigurable topologies, adapting to the traffic in an online manner. The underlying algorithmic problem can be described as an online maximum weight b-matching problem, a generalization of maximum weight matching where each node has at most b>=1 incident matching edges.
We make the case for a randomized approach for matching optimization. Our main contribution is a O(log b)-competitive algorithm and we show that it is asymptotically optimal. This algorithm is exponentially better than the best possible deterministic online algorithm.
We complement our theoretical results with trace-driven simulations, based on real-world datacenter workloads.
Event Type
Paper
TimeThursday, 16 November 20232pm - 2:30pm MST
Location403-404
Algorithms
Cloud Computing
Distributed Computing
Heterogeneous Computing
Large Scale Systems
State of the Practice
TP