Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 2009 | Published
Book Section - Chapter Open

How Bad is Single-Path Routing


This paper investigates the network performance loss of using only single-path routing when multiple paths are available. The performance metric is the aggregate utility achieved by the joint optimization of congestion control and routing. As computing the exact loss for a general network topology is NP-hard, we develop analytical bounds on this "cost of not splitting". Our bound is independent of the number of source-destination pairs when the latter one is larger than the number of links in a network. We also propose a vertex projection method and combine it with branch-and-bound to provide progressively tighter bounds on the performance loss. Numerical examples are used to show the effectiveness of our approximation technique.

Additional Information

© 2009 IEEE. The authors thank J. Rexford of Princeton for helpful comments. The research is supported by NSF under CCF-0835706.

Attached Files

Published - 05425408.pdf


Files (174.4 kB)
Name Size Download all
174.4 kB Preview Download

Additional details

August 19, 2023
October 25, 2023