Networked Systems SeminarSeminar #4: Thursday, April 23rd, 2009DBH 6011, 2pm 
Reverse Engineering TCP/IPlike NetworksSteven LowCaltech 
About the Talk:
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 delayinsensitive utility over both source
rates and routes, provided pure congestion prices are used as link
costs in the shortestpath 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
delaysensitive utility functions and identify a class
of utility functions that such a TCP/IP equilibrium optimizes.
We exhibit some counterintuitive properties that any class of
delaysensitive 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 multipath routing is
polynomialtime, NUM with singlepath routing is in general
NPhard. The loss in utility by restricting routing
to single paths is exactly the duality gap between singlepath
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, CheeWei Tan, Ao Tang) [slides]

About the Speaker:
