Stochastic Networks  (Eds: F.P. Kelly and R.J. Williams)
Springer-Verlag, New York 1995
The IMA Volumes in Mathematics and its Applications, Volume 71

Research on stochastic networks has powerful driving applications in the modelling of manufacturing, telecommunications, and computer systems. These various applications have raised common mathematical issues of some subtlety, and a notable feature of the workshop was the way in which experts in different areas such as operations research, systems science and engineering, and applied mathematics have been attacking important problems from different viewpoints.

The workshop was timely for both applications and theory. In the past decade the proliferation of local and global communication networks for computer and human communication, the development of parallel computers with large numbers of processors, and the design of flexible and robust manufacturing systems have spurred major advances in our understanding of queueing networks, and the workshop provided an opportunity to review recent progress. While research on queueing networks uses many of the traditional queueing theory insights, it is more concerned with how network components interact than with detailed models of how an individual queue behaves. In the last few years there have been some surprises, in particular with regard to the conditions for stability of multiclass queueing networks, and this area formed a major theme of the workshop. Other important themes concerned the challenges reflected Brownian motion has set both as a mathematical object and as a modelling paradigm; the usefulness of ideas from the interacting particle system world; the application of large deviation theory; and the developing connections with optimization and dynamical systems theory.

Fluid models, and their connections with the stability and performance of multiclass queueing networks, were vigorously discussed in the opening days of the workshop. Intense interest in this subject has been fuelled by recent examples due to Lu and Kumar, Rybko and Stolyar, Bramson and others which show that even if the nominal traffic intensity at each station is strictly less than one, a multiclass network need not be stable, in the sense that the total number of customers in the system may grow towards infinity. Reports on recent efforts at determining conditions for stability of such networks included the work of Kumar, Meyn et. al. on finding Lyapunov functions using a linear programming approach to obtain bounds on performance and conditions for stability of mostly re-entrant lines. An interesting feature is that the linear programs for performance and stability are in duality; this is reminiscent of the duality between the partial differential equations for stability and for steady state distributions of reflected diffusions. In recent work Jim Dai and Gideon Weiss have used piecewise linear Lyapunov functions to show stability of some fluid models which in turn guarantees positive recurrence for the queueing model. An interesting problem has been to determine the conditions under which the fluid model is stable for any work conserving service discipline. Maury Bramson described his striking two station example where there is instability even though the arrivals are Poisson, service is exponential and the service discipline is the egalitarian FIFO. Dimitris Bertsimas showed how bounds on the achievable performance of stochastic networks could be obtained by solving linear and nonlinear optimization problems whose formulation is motivated by conservation law ideas. His wide-ranging talk included some interesting comparisons between the fields of stochastic modelling and mathematical programming.

Fluid limits for closed multiclass queueing networks were introduced by Vi\^{e}n Nguyen (joint work with Michael Harrison). By means of a seemingly simple two station example (a closed analogue of the Lu and Kumar example), she illustrated that fluid limits for closed networks can exhibit very interesting and unexpected behaviour. The behaviour seems to have links with the issue of stability for open multiclass networks.

Assuming the fluid model for a network is stable, one can then propose a Brownian model as an approximation to the network when it is heavily loaded. (The justification of this approximation and what one means by heavily loaded are issues that still need to be resolved.) Another way to view the Brownian model is as a description of deviations from the fluid model or a long time view of a balanced fluid model. Michael Harrison gave a splendid overview of the current state of knowledge in this area and introduced some bold conjectures which fueled discussion in the early part of the workshop. Harrison's paper in volume 10 of these IMA proceedings has been immensely useful as a guide to (then) known and conjectured results on Brownian networks, and his paper here will, we expect, be similarly helpful to workers in the field.

Ruth Williams followed Harrison's talk with an overview of the current state of knowledge regarding reflecting Brownian motions as approximate models of multiclass open queueing networks. She largely focussed on the geometric conditions for existence and uniqueness of these diffusion processes, conditions for positive recurrence and characterization of the stationary distribution. The result of Dupuis and Williams that stability of all solutions of the Skorokhod problem for the drift path is sufficient for positive recurrence of the associated reflecting Brownian motion, is similar (and indeed motivated) the result of Dai that stability of the fluid model is sufficient for positive recurrence of the associated queueing model.

Frank Kelly initiated the discussion of problems of optimal scheduling and routing in stochastic networks, focussing on loss networks and queueing networks. He described various bounds on performance, and limiting regimes involving either heavy traffic or diverse routing under which the bounds may be approached. This was followed by talks of Neil Laws on trunk reservation as a good control mechanism in loss networks, and of Marty Reiman on polling systems and the use of a heavy traffic approximation and averaging principle to approximate the total unfinished work, and the waiting time of an arriving customer, by a one-dimensional diffusion.

Larry Wein expanded on the analysis of polling models by discussing the optimal scheduling of a multiclass single server station, which can be used to model a polling system or a stochastic economic lot scheduling problem. In both the talks of Reiman and Wein, heavy traffic diffusion approximations provided the intuitive motivation for the proposed policies. In his talk Mete Soner provided a rigorous connection between the optimal scheduling problem for a two station, two customer class (criss-cross) queueing network and the optimal control problem for a multidimensional diffusion obtained via a heavy traffic limit from the original queueing problem. The theme of polling models recurred in the talk of Guy Fayolle where certain state-dependent polling models were analysed for ergodicity or transience and, in the case of symmetric ergodic systems, various polling strategies could be compared.

Another approach to optimization problems was described by Harold Kushner with the objective being to facilitate efficient numerical computations. His method is to approximate a system in heavy traffic by a diffusion and then to approximate the diffusion by a Markov chain with small step size. This discretizes the problem and allows rapid numerical computations to be performed on the Markov chains corresponding to networks with up to four nodes. Kushner's experience suggests that for such systems, the optimal controls for the Markov chains are good controls for the original queueing network.

A further perspective on the stability of queueing networks was presented by Fran\c cois Baccelli with his saturation rule for stability of open queueing networks under stationary ergodic assumptions. This has application to Jackson-type networks and stochastic Petri networks. Matrix product form solutions allowed Bhaskar Sengupta to analyse a multiclass queue with LCFS service discipline and non-exponential service or interarrival times. Sergei Berezner reported on his work with Suhov and Rose on synchronization rules for star-like networks.

Balaji Prabhakar sketched his recent proof with Tom Mountford of the long standing Reiman-Simon conjecture that a stationary ergodic arrival process of rate $\alpha<1$ fed through a sequence of independent rate one memoryless queues yields an output that tends to a Poisson process of rate $\alpha$ as the number of queues tends to infinity. The usefulness of ideas from the field of interacting particle systems was well illustrated in this talk, and in the talk of Bramson.

Avi Mandelbaum described some of his experiences modelling real service networks involving people as servers and customers and applying existing tools in novel ways to enhance the performance of these networks. The term `Queueing Science' which came up in the talk seems to be an especially appropriate one for this activity. Many of the early operational research applications of queueing theory involved service networks, but in more recent times the focus of applications has shifted to technological applications where customers are jobs in a manufacturing system, or messages in a telecommunication system. In some respects the technological applications are easier in that there is no need to worry about predicting the various ways people may react to disparate circumstances. Avi emphasised that for service networks the application of queueing theory results must involve various other disciplines such as psychology and organizational behaviour.

Walter Willinger's talk on data he has collected from telecommunications networks stimulated thought on what might be the best model for the primitive processes (service times etc.) associated with these networks. The self-similar properties of his data raised the question of whether fractional Brownian motion might not be a useful model in some circumstances. The talk provoked valuable discussion of the assumptions underlying many of the existing models in the field.

Jean Walrand talked about design and control of ATM (asynchronous transfer mode) networks, the high speed telecommunication networks currently under development. He described two ideas for this, with the objective of having simple design rules and robust control strategies for networks. ATM networks are rapidly becoming a very important application area for stochastic networks. There remains much further work to be done on the formulation of basic models, but the central role of large deviations is already clear.

Large deviations was a common theme in several of the talks of the last two days of the workshop. These included Alan Weiss' analysis of Aloha-type protocols for multiple access channels, the analysis of infinite server queues of Peter Glynn and Paul Dupuis' general large deviation principle for queueing systems. The use of dynamical systems ideas in the evaluation of the rate function indicates another connection between deterministic dynamical systems with non-smooth constraints and stochastic networks. A. Ganesh reported on the stationary tail probabilities of a tandem of exponential servers fed by a renewal process (joint work with Venkat Anantharam).

Much of the workshop was concerned with coarse approximate models (primarily diffusion and fluid approximations) and coarse performance estimates (for example large deviation estimates, or limits as a network becomes large), rather than with high-fidelity models and exact performance analysis methods. This search for more robust and general insights is a salient feature of much contemporary research in the field.

The workshop provided an immensely valuable opportunity for participants to learn from and argue with each other, and to boldly conjecture. It was an exciting, intense week, and we have included in this volume the workshop's schedule and list of participants as a reminder and to help contacts to be pursued. Many of the speakers have contributed papers to the volume related to their own talks, to later developments, or to other topics in the area of the workshop.

The workshop was funded by the IMA and the National Science Foundation. We thank Avner Friedman, Willard Miller, and Michael Steele for their invitation to organize the workshop, and for their support. The excellent local arrangements were cheerfully and efficiently administered by Pam Rech and Kathi Polley. Finally we thank Patricia Brick for her unfailing assistance in the production of this volume.

Frank Kelly

Ruth Williams