Rate control for communication networks shadow.pdf

Rate control for communication networks: shadow prices, proportional fairness and stability FP Kelly, AK Maulloo and DKH Tan University of Cambridge, UK This paper analyses the stability and fairness of two classes of rate control algorithm for communication networks. The algorithms provide natural generalisations to large-scale networks of simple additive increase/multiplicative decrease schemes, and are shown to be stable about a system optimum characterised by a proportional fairness criterion. Stability is established by showing that, with an appropriate formulation of the overall optimisation problem, the networks implicit objective function provides a Lyapunov function for the dynamical system de?ned by the rate control algorithm. The networks optimisation problem may be cast in primal or dual form: this leads naturally 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 may be generalised to include routing control, and provide natural implementations of proportionally fair pricing. Keywords: ATM network; congestion indication; elastic traf?c; Internet; Lyapunov function; proportionally fair pricing; queues; routing Introduction The design and control of modern communication networks raises several issues well suited to study using techniques of operational research such as optimisation, network programming and stochastic modelling. In this paper we illustrate this theme, through the presentation and analysis of a mathematical model that arises in connection with the development and deployment of large-scale broadband networks. In future communication networks there are expected to be applications that are able to modify their data transfer rates according to the available bandwidth within the network. Traf?c from such applications is termed elastic;1 a typical current example is TCP traf?c over the Internet,2 and future examples may