Rate control in communication networks

Frank Kelly

1999 British Applied Mathematics Colloquium,
Bath, England, April 1999.

This talk will discuss the stability and fairness of rate control algorithms for communication networks. Algorithms that provide natural generalizations to large-scale networks of simple additive increase/multiplicative decrease schemes are shown to be stable about a system optimum characterized by a proportional fairness criterion. Stability is established by showing that, with an appropriate formulation of an overall optimization problem, the network's implicit objective function provides a Lyapunov function for the dynamical system defined by the rate control algorithm. The network's optimization problem may be cast in primal or dual form: this leads to two classes of algorithm, which may be interpreted in terms of either congestion indication feedback signals or explicit rates based on shadow prices. Both classes of algorithm provide natural implementations of proportionally fair pricing, and can be viewed as "charge-aware" developments of, respectively, Jacobson's TCP algorithm and ATM available bit rate algorithms.

As an application of the theory, the talk will conclude with a discussion of ways in which the transmission control protocol of the Internet may evolve to support heterogeneous applications. The claim will be made that by appropriately marking packets at overloaded resources and by charging a fixed small amount for each mark received, end-nodes are provided with the necessary information and the correct incentive to use the network efficiently.

(Talk based on joint work with Richard Gibbens, Aman Maulloo and David Tan.)

Frank Kelly's home page