Stability, routing and congestion control

Frank Kelly

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. And 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.

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 the above framework permits a surprisingly simple answer to this question.

Based on joint work with Thomas Voice.


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
Congestion control for high performance, stability and fairness in general networks .
Fernando Paganini, Zhikui Wang, John C. Doyle, Steven H. Low