Reverse Engineering TCP/IP-like Networks using Delay-Sensitive Utility Functions

Steven Low
California Institute of Technology

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. In this paper, we introduce 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 prove a sufficient condition for global stablity of routing updates for general networks. We construct example networks that defy conventional wisdom on the effect of link cost parameters on network stability and utility.

Back to Workshops IV: New Mathematical Frontiers in Network Multi-Resolution Analysis