Solving Max-Min Fair Resource Allocations Quickly on Large Graphs

We consider the problem of allocating resources in a max-min fair manner. The best known solutions either use 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) generalize waterfilling to the multi-path case. We empirically show that 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 the traffic engineering pipeline of a large production WAN and show a speedup of roughly \(3×\) without affecting solution quality.