Citation
Pongsajapan, John (2007) Optimization and stability of TCP/IP with delaysensitive utility functions. Master's thesis, California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd06022006162638
Abstract
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, maximize the same aggregate utility function over both source rates and routes, provided pure congestion prices are used as link costs in the shortestpath calculation of IP. Moreover, the utility functions are delayinsensitive, i.e., they are functions of rates only. We extend this result in several ways.
First, we show that if utility functions are delayinsensitive, then there are networks for which TCP/IP optimizes aggregate utility only if routing is based on pure congestion prices. Routing based on the weighted sum of congestion prices and propagation delays optimizes aggregate utility for general networks only if the utility functions are delaysensitive. Moreover, we identify such a class of delaysensitive utility functions that is implicitly optimized by TCP/IP. As for the delayinsensitive case, we show for this class of utility functions, equilibrium of TCP/IP exists if and only if the optimization problem has zero duality gap. In that case, there is no penalty for not splitting the traffic. We exhibit some counterintuitive properties of this class of utility functions. We also prove that any class of delaysensitive utility functions that are optimized by TCP/IP necessarily possess some strange properties.
We prove that, for general networks, if the weight on congestion prices is small enough, only minimumpropagationdelay paths are selected. Hence if all sourcedestination pairs have unique minimumpropagationdelay paths, then equilibrium of TCP/IP exists and is asymptotically stable. For general networks, their equilibrium properties are the same as a modified network where paths with nonminimum propagation delays are deleted and routing is based on pure congestion prices.
It is commonly believed that there is generally an inevitable tradeoff between utility maximization and stability in TCP/IP networks. In particular, as the weight on congestion prices increases, the routing will change from stable to unstable. We exhibit a counterexample where routing changes from stable to unstable and then to stable again, as the weight on congestion prices increases. Moreover, one can construct a network with any given utility profile as a function of the weight on congestion prices.
Item Type:  Thesis (Master's thesis) 

Subject Keywords:  Networks; TCP/AQM; TCP/IP 
Degree Grantor:  California Institute of Technology 
Division:  Engineering and Applied Science 
Major Option:  Computer Science 
Thesis Availability:  Public (worldwide access) 
Research Advisor(s): 

Thesis Committee: 

Defense Date:  2 June 2006 
Record Number:  CaltechETD:etd06022006162638 
Persistent URL:  http://resolver.caltech.edu/CaltechETD:etd06022006162638 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  2406 
Collection:  CaltechTHESIS 
Deposited By:  Imported from ETDdb 
Deposited On:  03 Aug 2006 
Last Modified:  26 Dec 2012 02:50 
Thesis Files

PDF (thesis.pdf)
 Final Version
See Usage Policy. 318Kb 
Repository Staff Only: item control page