CaltechTHESIS
  A Caltech Library Service

Heterogeneous congestion control protocols

Citation

Tang, Ao (2006) Heterogeneous congestion control protocols. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-05242006-170918

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.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Congestion control; Efficiency and fairness; Equilibrium analysis; Heterogeneous protocols; Multiprotocol networks; Resource allocation
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Awards:Charles and Ellen Wilts Prize, 2007
Thesis Availability:Restricted to Caltech community only
Research Advisor(s):
  • Low, Steven H.
Thesis Committee:
  • Low, Steven H. (chair)
  • Hassibi, Babak
  • Bruck, Jehoshua
  • Doyle, John Comstock
  • Chandy, K. Mani
Defense Date:3 May 2006
Record Number:CaltechETD:etd-05242006-170918
Persistent URL:http://resolver.caltech.edu/CaltechETD:etd-05242006-170918
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2011
Collection:CaltechTHESIS
Deposited By: Imported from ETD-db
Deposited On:30 May 2006
Last Modified:26 Dec 2012 02:45

Thesis Files

[img] PDF (thesis.pdf) - Final Version
Restricted to Caltech community only
See Usage Policy.

1770Kb
[img] Postscript (thesis.ps) - Final Version
Restricted to Caltech community only
See Usage Policy.

12Mb

Repository Staff Only: item control page