A Caltech Library Service

Router Congestion Control


Gao, Xiaojie (2004) Router Congestion Control. Master's thesis, California Institute of Technology. doi:10.7907/VZ4D-4047.


Congestion is a natural phenomenon in any network queuing system, and is unavoidable if the queuing system is operated at capacity. In this thesis, 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.

Queueing system is a crucial component in effective router congestion control since it determines the way packets from different sources interact with each other. If packets are dropped by the queueing system indiscriminately, in some cases, the effect can be to encourage senders to actually increase their transmission rates, worsening the congestion, and destabilizing the system.

We approach this problem from game theory. We look on each flow as a competing player in the game; each player is trying to get as much bandwidth as possible. Our task is to design a game at the router that will protect low-volume flows and punish high-volume ones. Because of the punishment, being high-volume will be counter productive, so flows will tend to use a responsive protocol as their transport-layer protocol. The key aspect of our solution is that by sending no packets from high-volume flows in case of congestion, it gives these flows an incentive to use a more responsive protocol.

In the thesis, we will describe several implementations of our solution, and show that we achieve the desired game-theoretic equilibrium while also maintaining bounded queue lengths and responding to changes in network flow conditions. Finally, we accompany the theoretical analysis with network simulations under a variety of conditions.

Item Type:Thesis (Master's thesis)
Subject Keywords:efficiency; fairness
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Schulman, Leonard J.
Thesis Committee:
  • Unknown, Unknown
Defense Date:3 June 2004
Record Number:CaltechETD:etd-06142004-161237
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2582
Deposited By: Imported from ETD-db
Deposited On:19 Jul 2004
Last Modified:05 Jan 2021 22:51

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page