2025/05/06 by Miguel Pedrosa Ferreira, Ferreira, Miguel, Nirav Atre +7
Computer Science · #Cloud Computing and Resource Management #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #Networking and Internet Architecture (cs.NI) #Performance (cs.PF) #Software-Defined Networks and 5G
paper · pdf · doi:10.48550/arxiv.2505.03908
openalex publication_date 2025/05/06 · openalex created_date 2025/10/16 · openalex updated_date 2026/07/28
Millions of flows are routed concurrently through a modern data-center. These networks are often built as Clos topologies, and flow demands are constrained only by the link capacities at the ingress and egress points. The minimum congestion routing problem seeks to route a set of flows through a data center while minimizing the maximum flow demand on any link. This is easily achieved by splitting flow demands along all available paths. However, arbitrary flow splitting is unrealistic. Instead, network operators rely on heuristics for routing unsplittable flows, the best of which results in a worst-case congestion of 2 (twice the uniform link capacities). But is 2 the lowest possible congestion? If not, can an efficient routing algorithm attain congestion below 2? Guided by these questions, we investigate the minimum congestion routing problem in Clos networks with unsplittable flows. First, we show that for some sets of flows the minimum congestion is at least \nicefrac32, and that it is NP-hard to approximate a minimum congestion routing by a factor less than \nicefrac32. Second, addressing the motivating questions directly, we present a polynomial-time algorithm that guarantees a congestion of at most \nicefrac95 for any set of flows, while also providing a \nicefrac95 approximation of a minimum congestion routing. Last, shifting to the online setting, we demonstrate that no online algorithm (even randomized) can approximate a minimum congestion routing by a factor less than 2, providing a strict separation between the online and the offline setting.