PREFACE
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 fueled
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 Vien 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 Francois 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 and Ruth Williams
September 1994