The International Conference for High Performance Computing, Networking, Storage, and Analysis
The International Conference for High Performance Computing, Networking, Storage, and Analysis
Authors: Marcin Bienkowski (University of Wroclaw), David Fuchssteiner (University of Vienna), and Stefan Schmid (Technical University of Berlin)
Abstract: Reconfigurable 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.
Back to Technical Papers Archive Listing