Fairness and stability of end-to-end congestion control

Frank Kelly

European Journal of Control 9 (2003) 159-176.

Abstract

In recent years the Internet has attracted the attention of many theoreticians, eager to understand the remarkable success of this diverse and complex artefact. A central element of the design philosophy that shaped the Internet is the end-to-end argument, and a key illustration of the argument is provided by the congestion avoidance algorithm of the Transmission Control Protocol (TCP). Why does this algorithm work so well? How might, or should, it evolve in the future? In this paper we outline some of the mathematical models that have been developed to help address these questions.

We review the equilibrium and dynamic properties of primal and dual algorithms, concentrating upon fairness, delay instability and stochastic instability. Primal algorithms broadly correspond with congestion control mechanisms where noisy feedback from the network is averaged at endpoints, using increase and decrease rules generalizing those of TCP. Vinnicombe has shown that delay instability is characterized in terms of the increase rule; Ott has shown that stochastic instability is primarily influenced by the decrease rule. The need to control both forms of instability places constraints on possible variants of TCP, and on attempts to remove TCP's round-trip time bias.

Dual algorithms broadly correspond with congestion control mechanisms where averaging at resources precedes the feedback of more explicit information to endpoints, and may be especially appropriate where round-trip times are short, as in ad-hoc networks. Previous work has concentrated on delay-based dual algorithms, which find fairness and stability difficult to reconcile. We describe a fair dual algorithm, with attractive stability properties.

postscript, pdf.

Citations, from Google Scholar.

Frank Kelly's papers