In recent years 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-flow models, 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. The dynamics of the fluid-flow models allow the machinery of control theory to be used to study stability, and to develop rate control algorithms that scale to arbitrary capacities.
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, but the optimization framework is again central.
Finally the talk will describe applications to routing. Dynamic multi-path routing has the potential to improve the reliability and performance of a communication network, but carries a risk. Routing needs to respond quickly to achieve the potential benefits, but not so quickly that the network is destabilized. So, how rapidly can routing respond, without compromising stability? We show that there is a surprisingly simple answer to this question.
Based on joint work with Thomas Voice and Ruth Williams.
Slides (and much else) are available here.
References:
Overlay TCP for multi-path routing and congestion control.
H. Han, S. Shakkottai, C. V. Hollot, R. Srikant and
D. Towsley
Fairness and stability of end-to-end congestion control.
Frank Kelly
Stability of end-to-end algorithms for joint routing and rate control.
Frank Kelly and Thomas Voice
Fluid model for a network operating under a fair bandwidth-sharing policy.
Frank Kelly and Ruth Williams
Bandwidth sharing and admission control for elastic traffic.
L. Massoulié and J.W. Roberts
Congestion control for high performance, stability and fairness in general
networks
.
Fernando Paganini, Zhikui Wang, John C. Doyle, Steven H. Low
The Mathematics of Internet Congestion Control.
R. Srikant