A Caltech Library Service

Can shortest-path routing and TCP maximize utility

Wang, Jiantao and Li, Lun and Low, Steven H. and Doyle, John C. (2003) Can shortest-path routing and TCP maximize utility. In: 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM 2003). Vol.3. IEEE , Piscataway, NJ, pp. 2049-2056. ISBN 0-7803-7752-4.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


TCP-AQM protocol can be interpreted as distributed primal-dual algorithms over the Internet to maximize aggregate utility. In this paper, we study whether TCP-AQM together with shortest-path routing can maximize utility with appropriate choice of link cost, on a slower timescale, over both source rates and routes. We show that this is generally impossible because the addition of route maximization makes the problem NP-hard. We exhibit an inevitable tradeoff between routing instability and utility maximization. For the special case of ring network, we prove rigorously that shortest-path routing based purely on congestion prices is unstable. Adding a sufficiently large static component to link cost, stabilizes it, but the maximum utility achievable by shortest-path routing decreases with the weight on the static component. We present simulation results to illustrate that these conclusions generalize to general network topology, and that routing instability can reduce utility to less than that achievable by the necessarily stable static routing.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Low, Steven H.0000-0001-6476-3048
Doyle, John C.0000-0002-1828-2486
Additional Information:© 2003 IEEE.
Record Number:CaltechAUTHORS:20190306-132657017
Persistent URL:
Official Citation:J. Wang, L. Li, S. H. Low and J. C. Doyle, "Can shortest-path routing and TCP maximize utility," IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428), San Francisco, CA, 2003, pp. 2049-2056 vol.3. doi: 10.1109/INFCOM.2003.1209226
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93600
Deposited By: Tony Diaz
Deposited On:06 Mar 2019 22:48
Last Modified:16 Nov 2021 16:59

Repository Staff Only: item control page