This volume is a collection of invited papers written after the event by some of the participants at the Royal Statistical Society research workshop on stochastic networks, held at Heriot-Watt University, Edinburgh, from 1 to 11 August 1995. This workshop gathered together most of the leading researchers in this field, including many from industry. All the major themes of current interest were considered, and these are well represented in this volume.
One such theme is the study of approximations to network queueing models via various natural time and space scalings, and the use of these approximations in determining optimal controls. Two scalings are of special interest. The first gives an (essentially deterministic) fluid model in the limit, and fluid models have become an important tool in the investigation of open multiclass queueing networks. Maury Bramson discusses the asymptotic behaviour of fluid models of important classes of FIFO and processor sharing queueing networks. He considers recent results of Dai and others on the connection between the stability of the fluid limit and that of the network itself, and uses powerful ideas of entropy to show that such networks are stable whenever the traffic intensity is strictly less than one. Gideon Weiss considers directly the problem of optimal control for fluid models of transient queueing networks appropriate to manufacturing systems with re-entrant lines (in which components may be required to be processed by the same machine several times, as is typically the case in modern semi-conductor wafer fabrication plants). He shows how continuous linear programming techniques may be applied to the solution of such problems, and solves fully a range of instructive examples.
The second natural scaling typically gives a Brownian model in the limit and is particularly appropriate to studying the more detailed behaviour of stable but heavily loaded networks. Ruth Williams describes the current state of research in this area. She concludes her paper with an important example (due to Harrison and Williams) of an unconventional heavy traffic limit theorem, where it is necessary to combine different scalings to obtain a full characterisation of the limiting behaviour. Mike Harrison uses the Brownian model as the basis for a new, very general and effective approach to dynamic flow control in stochastic networks. See also the papers of Majewski and Kurtz, mentioned below.
A second major theme deals with the use of large deviations theory in analysing queueing and loss systems. In modern telecommunications networks it is necessary to ensure that data are transmitted with a high degree of reliability (for example, such that packets have a maximum loss probability of the order of $10^{-9}$). The theory of large deviations is central to the study of such rare events, and large deviations bounds are used in many of the papers in this volume (see, for instance, those of Hajek, Harrison, and Kelly). Neil O'Connell discusses the general problem of using large deviations theory to establish probability approximations for aspects of a system (such as queue lengths) under very general ergodicity and mixing assumptions about the network inputs. He then applies this theory to the characterisation of queue length and sojourn time distributions for single-server resources with multiple arrival streams. Kurt Majewski studies similar questions for sequences of "feedforward" queueing networks, whose traffic intensities approach one, by developing the large deviations theory of the corresponding stationary reflected Brownian motions, thus combining both of the major themes already mentioned.
A third theme deals with the statistical analysis, modelling and control of network arrival processes. Recent work has shown that traffic in modern packet-based high-speed networks frequently exhibits a self-similar, essentially fractal, behaviour over a wide range of time scales. Such behaviour arises in models with long-range time dependence. It has major implications for the statistical analysis of such traffic, and can call into question the validity of traditional modelling techniques based on the assumption of arrival processes with short-range dependence. The paper by Walter Willinger, Murad Taqqu and Ashok Erramilli gives a very comprehensive bibliography of recent work on these issues, including references to closely related work in other branches of science and engineering such as hydrology, financial economics, and biophysics.
Of course it is highly desirable to understand how such arrival process behaviour arises, and to develop realistic analytic models for it. Much recent work (referenced in the above bibliography of Willinger et al suggests that it may sometimes arise as the result of the superposition of inputs from many on-off sources. Tom Kurtz considers general models for such workload input processes, and gives limit theorems for the formulation of both fluid and heavy traffic approximations for systems with these inputs. He shows that under appropriate assumptions fractional Brownian motion, which possesses long-range dependence and self-similarity properties, can be obtained as the limiting workload input process.
Frank Kelly provides an overview of the use of effective bandwidths as a summary of the statistical characteristics of sources over different time and space scales, as well as in various models of statistical sharing. His framework assumes only stationarity of sources, and illustrative examples include Brownian bridge and fractional Brownian models, as well as various large deviations models. Richard Gibbens uses the notion of effective bandwidth as a graphical descriptor in several examples, including an MPEG-1 video encoding of the Star Wars movie and traces of ethernet traffic taken at Bellcore, and compares the latter with fractional Brownian motion. There remains much work to be done on the analysis of data collected in networks, and on the development of more formal methodologies. In a contribution to this area, Susan Pitts describes results on nonparametric estimation for queues, and on the parallels with methods developed in risk theory.
The mathematics of loss networks continues to play a very important role in the analysis and control of modern telecommunications and computer networks - for example in ATM networks where effective bandwidth takes the role of a capacity requirement, and in cellular radio networks (where there remain severe capacity constraints). Of particular interest here is the study of control processes which, while themselves operating on a very fast time scale, both determine and are determined by the much longer time-scale behaviour of the network. Stan Zachary reviews some recent work in the application of these ideas to the study of the dynamic and equilibrium behaviour of loss networks with high arrival rates and capacities, while Iain MacPhee and Ilze Ziedins use similar ideas to consider design and optimal control in networks with diverse routing. Murat Alanyali and Bruce Hajek give important new results for dynamic load balancing in loss networks, focusing on the simple and robust control strategy of least load routing. They use fluid approximations to study typical behaviour under this strategy, and large deviations theory to analyse significant departures from such behaviour. Suzanne Evans takes a different approach to the analysis of system behaviour on different time scales, potentially applicable to both loss and queueing networks.
Problems of job selection and scheduling are of great importance in manufacturing. The papers by Weiss and Harrison, previously mentioned, consider these problems. Additionally, Renate Garbe and Kevin Glazebrook give a careful review of the very recent and powerful theory of Bertsimas and Nino-Mora on the optimal control of stochastic systems satisfying generalized conservation laws. They further develop significant extensions to this theory.
Analysis of the effects of unreliability in queueing networks is notoriously difficult. In general only approximate analyses are possible, and even then such approximations are often unsatisfactory. Ram Chakka and Isi Mitrani introduce new and improved approximation techniques.
François Baccelli, Serguei Foss and Jean Mairesse develop a comprehensive theory of generalized Jackson networks in which classical Markovian assumptions are replaced by those of stationarity and ergodicity. (One motivation for this is the need to model long-range dependence in arrival processes, as discussed above.) They consider in particular the stability and transience of such networks, and give also a range of important counter-examples. One classical queueing model that still generates much interest is that of a tandem queue (a number of queues in series). Tom Mountford and Balaji Prabhakar present new results on the convergence of the successive departure processes from an infinite series of ./GI/I queues, again subject to stationary and ergodic inputs. Yurii Suhov and David Rose study fully connected queueing networks in which the number of nodes is allowed to grow. They show that under certain conditions the so-called Poisson-independence hypothesis holds in the limit, permitting the deduction of the limiting distribution of the end-to-end delay.
Financial support for the workshop was provided primarily by a Visiting Fellowship Grant from the Engineering and Physical Sciences Research Council. Further very generous assistance was provided by British Telecom Laboratories and by Hewlett-Packard's Basic Research Institute in the Mathematical Sciences. The Royal Statistical Society contributed to the expenses of a number of the research students. The editors wish to thank all of these bodies for their support.
We are also very grateful to the many colleagues (some participants at the workshop) who carefully reviewed the papers in the present volume, and made many helpful suggestions for their improvement. We are grateful to Elizabeth Johnston, Julia Tompson, Anna Drage and the staff of Oxford University Press for their patient assistance in the production of the volume. We are especially grateful to Richard Gibbens for being our LaTeX/PostScript expert and providing simple and elegant solutions to many of the problems involved in putting together a multi-authored work.
Frank Kelly
Stan Zachary
Ilze Ziedins