Fair and efficient router congestion control

Abstract

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.

Files

Additional details