A Caltech Library Service

Fair and efficient router congestion control

Gao, Xiaojie and Jain, Kamal and Schulman, Leonard J. (2004) Fair and efficient router congestion control. In: SODA '04 Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. SIAM , Philadelphia, PA, pp. 1050-1059. ISBN 0-89871-558-X.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Congestion is a natural phenomenon in any network queuing system, and is unavoidable if the queuing system is operated near capacity. In this paper we study how to set the rules of a queuing system so that all the users have a self-interest in controlling congestion when it happens. Routers in the internet respond to local congestion by dropping packets. But if packets are dropped indiscriminately, the effect can be to encourage senders to actually increase their transmission rates, worsening the congestion and destabilizing the system. Alternatively, and only slightly more preferably, the effect can be to arbitrarily let a few insistent senders take over most of the router capacity. We approach this problem from first principles: a router packet-dropping protocol is a mechanism that sets up a game between the senders, who are in turn competing for link capacity. Our task is to design this mechanism so that the game equilibrium is desirable: high total rate is achieved and is shared widely among all senders. In addition, equilibrium should be reestablished quickly in response to changes in transmission rates. Our solution is based upon auction theory: in principle, although not always in practice, we drop packets of the highest-rate sender, in case of congestion. We will prove the game-theoretic merits of our method. We'll also describe a variant of the method with some further advantages that will be supported by network simulations.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. Supported by National Science Foundation grant no. 0049092 and by the Charles Lee Powell Foundation.
Funding AgencyGrant Number
Charles Lee Powell FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20161025-172050851
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71487
Deposited By: Kristin Buxton
Deposited On:26 Oct 2016 18:48
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page