  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\times$
speedup.
