SOME RECENT DEVELOPMENTS FOR QUEUEING NETWORKS

R. J. WILLIAMS


Early investigations in queueing theory provided detailed analysis of the behavior of a single queue and of networks that in a sense could be decomposed into a product of single queues. Whilst insights from these early investigations are still used, more recent investigations have focussed on understanding how network components interact.

In particular, queueing network models are of current relevance for analyzing congestion and delay in computer systems, communication networks and complex manufacturing systems. Many of these systems have stations that can process more than one class of customer or job (so-called multiclass networks) and/or have complex feedback structures. For example, in a computer communication network one may have voice, video and data being transmitted through each node in the network, and in the manufacture of semiconductor wafers, a job may return to the same machine several times for different stages of processing. Generally such systems cannot be analyzed in closed form and frequently are heavily loaded. One method for analyzing the performance of such systems is to approximate them by more tractable objects.

A certain class of diffusion processes, known as reflecting Brownian motions in polyhedral domains, have been shown to approximate normalized versions of the queue length or workload processes in single class queueing networks and some multiclass queueing networks under conditions of heavy traffic, i.e., when the networks are heavily loaded. There is now a substantial theory for these diffusion processes which are generally more tractable than the original queueing networks, although some open problems remain.

One of the outstanding challenges in contemporary research on approximate models for queueing networks is to understand which multiclass networks can be approximated by reflecting Brownian motions in heavy traffic and to prove limit theorems justifying such approximations. In the last few years there have been some surprises both with regard to conditions for the stability of multiclass queueing networks and to the behavior of such networks in heavy traffic. The aim of this paper is to describe some of the recent developments in this area.

In Probability Towards 2000, L. Accardi and C. C. Heyde (eds.), Springer, 1998.