Network control: modelling the Internet

Frank Kelly
47th IEEE Conference on Decision and Control,
Cancun, Mexico, December 2008.


The Internet has attracted the attention of many theoreticians, eager to understand the remarkable success of this diverse and complex artefact. An important aspect of its success has been that simple decentralized algorithms, working with limited information, can produce coherent and purposeful behaviour at the macroscopic level. The challenge is to understand how.

One of the more fruitful approaches has been based on a framework that allows a congestion control algorithm such as Jacobson's TCP to be interpreted as a distributed mechanism solving a global optimization problem. The framework is based on fluid models of packet flows, and the form of the optimization problem makes explicit the equilibrium resource allocation policy of the algorithm, which can often be restated in terms of a fairness criterion, such as proportional fairness or max-min fairness. The dynamics of the fluid models allow the machinery of control theory to be used to study stability, to understand TCP's success and its potential for improvement, and to inform the development of future routing and rate control algorithms.

A further strand of theoretical work has developed a connection level model, that represents the randomly varying number of flows present in a network. Stability on this time-scale is interpreted in terms of recurrence of a Markov chain. In joint work with Kang, Lee and Williams we have begun to understand more about the heavy traffic behaviour of this Markov chain, and hence about the performance of joint routing and congestion control. Under proportional fairness and a local traffic condition, the diffusion approximation has a product form invariant distribution with a strikingly simple interpretation in terms of dual random variables, one for each of a set of virtual resources.

References:

Layering as optimization decomposition: a mathematical theory of network architectures
M. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle
Proceedings of the IEEE 95 (2007) 255-312.

Multi-Path TCP: a joint congestion control and routing scheme to exploit path diversity on the Internet
H. Han, S. Shakkottai, C.V. Hollot, R. Srikant and D. Towsley
IEEE/ACM Transactions on Networking 14 (2006) 1260-1271.

State space collapse and diffusion approximation for a network operating under a proportional fair sharing policy
W. Kang, F. P. Kelly, N. H. Lee and R. J. Williams

Fairness and stability of end-to-end congestion control
Frank Kelly
European Journal of Control 9 (2003) 159-176.

Stability of end-to-end algorithms for joint routing and rate control
Frank Kelly and Thomas Voice
Computer Communication Review 35:2 (2005) 5-12.

Combined multipath routing and congestion control: a robust Internet architecture
Peter Key, Laurent Massoulié and Don Towsley

Bandwidth sharing and admission control for elastic traffic
L. Massoulié and J.W. Roberts
Telecommunication Systems 15 (2000) 185-201.

Network Optimization and Control
Srinivas Shakkottai and R. Srikant
Foundations and Trends in Networking (2007) NoW Publishers.