Solving Max-Min Fair Resource Allocations Quickly on Large Graphs

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.

The author contributed to this work while at Microsoft. 1 In this paper, we use efficiency and utilization interchangeably. 2 We defer extending to other notions of fairness to future work. Soroush (heuristics) Soroush (α-approx) k-waterfilling Exact Methods (Gavel, Danna)