NSDI '24 - Solving Max-Min Fair Resource Allocations Quickly on Large Graphs

Описание: NSDI '24 - Solving Max-Min Fair Resource Allocations Quickly on Large Graphs

Pooria Namyar, Microsoft and University of Southern California; Behnaz Arzani and Srikanth Kandula, Microsoft; Santiago Segarra, Microsoft and Rice University; Daniel Crankshaw and Umesh Krishnaswamy, Microsoft; Ramesh Govindan, University of Southern California; Himanshu Raj, Microsoft

We consider the max-min fair resource allocation problem. The best-known solutions use either a sequence of optimizations or waterfilling, which only applies to a narrow set of cases. These solutions have become a practical bottleneck in WAN traffic engineering and cluster scheduling, especially at larger problem sizes. We improve both approaches: (1) we show how to convert the optimization sequence into a single fast optimization, and (2) we generalize waterfilling to the multi-path case. We empirically show our new algorithms Pareto-dominate prior techniques: they produce faster, fairer, and more efficient allocations. Some of our allocators also have theoretical guarantees: they trade off a bounded amount of unfairness for faster allocation. We have deployed our allocators in Azure's WAN traffic engineering pipeline, where we preserve solution quality and achieve a roughly 3× speedup.

View the full NSDI '24 program at https://www.usenix.org/conference/nsd...