Creating and sharing knowledge for telecommunications

Impossibility Results for Data-Center Routing with Congestion Control and Unsplittable Flows

Ferreira, M. F. ; Atre, N. A. ; Sherry, JSM ; Sobrinho, J. L. S.

Impossibility Results for Data-Center Routing with Congestion Control and Unsplittable Flows, Proc ACM Symposium On Principles of Distributed Computing ACM PODC, Nantes, France, Vol. , pp. - , June, 2024.

Digital Object Identifier: https://doi.org/10.1145/3662158.3662777

 

Abstract
Clos networks have a long history in networking. In former telephone networks and classic network flow problems, Clos networks have been shown to guarantee the performance properties of an ideal macro-switch connecting sources to destinations: they can ensure that (individual) flow demands are satisfied, and that (aggregate) throughput is easily maximized. These properties made Clos networks an attractive choice for modern data-centers, and hence they are widely deployed. However, data-centers operate on different traffic assumptions than those prevalent in telephone networks and network flow problems: sources and destinations are not limited to at most one flow, and each flow must be assigned to a single path. Subject to these constraints, the performance of a Clos network is no longer equivalent to that of a macro-switch. In this paper, we study the discrepancies between a Clos network and a macro-switch in terms of throughput and max-min fairness, considering routing inside the network as a design variable. In this context, we prove three fundamental results regarding the performance of data-center networks. First, we show that even if routing could replicate the macro-switch rates, imposing max-min fair rates halves the throughput. Second, we prove that routing for max-min fairness reduces the max-min fair rates of some flows by factor of 1/𝑛 relative to the macro-switch, where 𝑛 is the number of middle switches in the network. Finally, we find that routing for maximum throughput doubles the throughput but brings the max-min fair rates of some flows to zero. These results call into question several common assumptions design options in data-centers.