Models of routing and congestion control

Frank Kelly
INFORMS Applied Probability Conference,
Eindhoven, the Netherlands, July 2007.

The Internet has attracted the attention of many theoreticians, eager to understand the remarkable success of this diverse and complex artefact. One strand of this effort has been 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, and to develop joint 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. Under proportional fairness and a local traffic condition, recent work with Kang, Lee and Williams has developed a heavy traffic diffusion approximation under which the workload process behaves like Brownian motion in the interior of a polyhedral cone and is confined to the cone by reflection at the boundary. The diffusion has a product form invariant distribution with a strikingly simple interpretation in terms of dual random variables, one for each of the resources of the network. When routing is incorporated, the product form distribution has a dual random variable for each of a set of generalised cut constraints.

Slides

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.

Fluid and Brownian approximations for an Internet congestion control model.
W. Kang, F. P. Kelly, N. H. Lee and R. J. Williams
Proceedings of the 43rd IEEE Conference on Decision and Control (2004).

Product form stationary distributions for diffusion approximations to a flow level model operating under a proportional fair sharing policy.
W. Kang, F. P. Kelly, N. H. Lee and R. J. Williams.
Extended abstract for MAMA 07 - to appear in Performance Evaluation Review (2007)

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.

Fluid model for a network operating under a fair bandwidth-sharing policy.
F.P. Kelly and R. J. Williams
Annals of Applied Probability 14 (2004) 1055-1083.

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.