TCP/IP can be interpreted as a distributed primaldual algorithm to maximize aggregate utility over source rates. It has recently been shown that an equilibrium of TCP/IP, if exists, maximizes the same delay-insensitive utility over both source rates and routes, provided pure congestion prices are used as link costs in the shortest-path calculation of IP. In practice, however, pure dynamic routing is never used and link costs are weighted sums of both static as well as dynamic components. We present delay-sensitive utility functions and identify a class of utility functions that such a TCP/IP equilibrium optimizes. We exhibit some counter-intuitive properties that any class of delay-sensitive utility functions optimized by TCP/IP necessarily possess. We provide a sufficient condition for global stability of routing updates for general networks. While the network utility maximization (NUM problem with multi-path routing is polynomial-time, NUM with single-path routing is in general NP-hard. The loss in utility by restricting routing to single paths is exactly the duality gap between single-path NUM and its dual. We bound this cost of not splitting and show that it is independent of the number of users.

(Joint work with John Pongsajapan, Meng Wang, Chee-Wei Tan, Ao Tang)

[slides]

Steven Low received his PhD from Berkeley in EE. He is a Professor of the Computer Science and Electrical Engineering Departments at Caltech, and an adjunct professor of Swinbourne University, Australia. Before that, he was with AT&T Bell Laboratories, Murray Hill, and the University of Melbourne, Australia. He was a co-recipient of the IEEE Bennett Prize Paper Award in 1997 and the 1996 R&D 100 Award and was a member of the Networking and Information Technology Technical Advisory Group for the US President's Council of Advisors on Science and Technology (PCAST). He is an IEEE Fellow.