NSDI |
Organized by USENIX
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.
Soroush is a general and scalable max-min fair allocator. It consists of a group of approximate and heuristic methods that (a) solve at most one optimization, and (b) enable users to control the trade-offs between efficiency, fairness, and speed. For more information, see our NSDI24 paper (Solving Max-Min Fair Resource Allocations Quickly on Large Graphs).
