Contracting Wide-area Network Topologies to Solve Flow Problems Quickly


Firas Abuzaid, Microsoft Research and Stanford University; Srikanth Kandula, Behnaz Arzani, and Ishai Menache, Microsoft Research; Matei Zaharia and Peter Bailis, Stanford University


Many enterprises today manage traffic on their wide-area networks using software-defined traffic engineering schemes, which scale poorly with network size; the solver runtimes and number of forwarding entries needed at switches increase to untenable levels. We describe a novel method, which, instead of solving a multi-commodity flow problem on the network, solves (1) a simpler problem on a contraction of the network, and (2) a set of sub-problems in parallel on disjoint clusters within the network. Our results on the topology and demands from a large enterprise, as well as on publicly available topologies, show that, in the median case, our method nearly matches the solution quality of currently deployed solutions, but is 8x faster and requires 6x fewer FIB entries. We also show the value-add from using a faster solver to track changing demands and to react to faults.

NSDI '21 Open Access Sponsored by NetApp

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 {262026,
author = {Firas Abuzaid and Srikanth Kandula and Behnaz Arzani and Ishai Menache and Matei Zaharia and Peter Bailis},
title = {Contracting Wide-area Network Topologies to Solve Flow Problems Quickly},
booktitle = {18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21)},
year = {2021},
isbn = {978-1-939133-21-2},
pages = {175--200},
url = {},
publisher = {USENIX Association},
month = apr

Presentation Video