Caltech Library System

About | Browse | Search | Caltech Student Instructions

Type of Document	Dissertation
Author	Tang, Ao
URN	etd-05242006-170918
Persistent URL	http://resolver.caltech.edu/CaltechETD:etd-05242006-170918
Title	Heterogeneous congestion control protocols
Degree	PhD
Option	Electrical Engineering
Advisory Committee	Advisor Name Title Steven H. Low Committee Chair Babak Hassibi Committee Member Jehoshua Bruck Committee Member John Comstock Doyle Committee Member K. Mani Chandy Committee Member
Keywords	Congestion control Resource allocation Multiprotocol networks Efficiency and fairness Heterogeneous protocols Equilibrium analysis
Date of Defense	2006-05-03
Availability	unrestricted
Abstract Homogeneity of price is an implicit yet fundamental assumption underlying price based resource allocation theory. In this thesis, we study the effects of relaxing this assumption by examining a concrete engineering system (network with heterogeneous congestion control protocols). The behavior of the system turns out to be very different from the homogeneous case and can potentially be much more complicated. A systematic theory is developed that includes all major properties of equilibrium of the system such as existence, uniqueness, optimality, and stability. In addition to analysis, we also present numerical examples, simulations, and experiments to illustrate the theory and verify its predictions. When heterogeneous congestion control protocols that react to different pricing signals share the same network, the resulting equilibrium can no longer be interpreted as a solution to the standard utility maximization problem as the current theory suggests. After introducing a mathematical formulation of network equilibrium for multi-protocol networks, we prove the existence of equilibrium under mild assumptions. For almost all networks, the equilibria are locally unique. They are finite and odd in number. They cannot all be locally stable unless the equilibrium is globally unique. We also derive two conditions for global uniqueness. By identifying an optimization problem associated with every equilibrium, we show that every equilibrium is Pareto efficient and provide an upper bound on efficiency loss due to pricing heterogeneity. Both intra-protocol and inter-protocol fairness are then discussed. On dynamics, various stability results are provided. In particular it is shown that if the degree of pricing heterogeneity is small enough, the network equilibrium is not only unique but also locally stable. Finally, a distributed algorithm is proposed to steer a network to the unique equilibrium that maximizes the aggregate utility, by only updating a linear parameter in the sources' algorithms in a slow timescale.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    thesis.pdf 1.81 Mb 00:08:23 00:04:18 00:03:46 00:01:53 00:00:09   thesis.ps 12.72 Mb 00:58:54 00:30:17 00:26:30 00:13:15 00:01:07