Router Congestion Control

Author: Gao, Xiaojie

Year: 2004

Degree: Master's thesis

Advisor: Schulman, Leonard J.

Committee Member: Unknown, Unknown

Option: Computer Science

DOI: 10.7907/VZ4D-4047

Abstract

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.

Files