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.

NSDI '24 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {295705,
author = {Pooria Namyar and Behnaz Arzani and Srikanth Kandula and Santiago Segarra and Daniel Crankshaw and Umesh Krishnaswamy and Ramesh Govindan and Himanshu Raj},
title = {Solving {Max-Min} Fair Resource Allocations Quickly on Large Graphs},
booktitle = {21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24)},
year = {2024},
isbn = {978-1-939133-39-7},
address = {Santa Clara, CA},
pages = {1937--1958},
url = {},
publisher = {USENIX Association},
month = apr

Presentation Video