Dynamic routing in stochastic networks

In Stochastic Networks (Editors F.P. Kelly and R.J. Williams)
The IMA Volumes in Mathematics and its Applications, 71.
Springer-Verlag, New York. 1995. 169-186.

Abstract

This paper reviews some current work on routing in loss and queueing networks. We describe two classes of bound on the performance of any dynamic routing scheme, together with some open questions concerning whether the bounds can be approached under certain limiting regimes. The first class of bound is particularly appropriate for networks in heavy traffic, where the key feature of a good routing scheme is its effective utilization of various pooled resources identified by a fluid version of the routing problem. The second class of bound is particularly appropriate for highly connected networks, with many alternative paths. Again, a network flow representation is central, but this time involving a collection of Markov decision processes, one for each resource of the network. Despite their simplicity, the bounds are able to identify the great variety of qualitatively distinct behaviour expected of a good dynamic routing scheme, depending on a network's size, connectivity, asymmetry and degree of overload.

Available as postscript.