Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter Topologies

Kathrin Hanauer, Monika Henzinger, Stefan Schmid, Jonathan Trummer

Veröffentlichungen: Beitrag in BuchBeitrag in KonferenzbandPeer Reviewed

Abstract

Reconfigurable optical topologies promise to improve the performance in datacenters by dynamically optimizing the physical network in a demand-aware manner. State-of-theart optical technologies allow to establish and update direct connectivity (in the form of edge-disjoint matchings) between top-of-rack switches within microseconds or less. However, to fully exploit temporal structure in the demand, such fine-grained reconfigurations also require fast algorithms for optimizing the interconnecting matchings. Motivated by the desire to offload a maximum amount of demand to the reconfigurable network, this paper initiates the study of fast algorithms to find k disjoint heavy matchings in graphs. We present and analyze six algorithms, based on iterative matchings, b-matching, edge coloring, and node-rankings. We show that the problem is generally N P-hard and study the achievable approximation ratios. An extensive empirical evaluation of our algorithms on both real-world and synthetic traces (88 in total), including traces collected in Facebook datacenters and in HPC clusters reveals that all our algorithms provide high-quality matchings, and also very fast ones come within 95 the running times differ significantly and what is the best algorithm depends on k and the acceptable runtime-quality tradeoff.
OriginalspracheEnglisch
TitelIEEE Conference on Computer Communications (INFOCOM), Virtual Conference, May 2022
PublikationsstatusVeröffentlicht - 2022

ÖFOS 2012

  • 102025 Verteilte Systeme

Zitationsweisen