HEAVY TRAFFIC LIMITS FOR MULTICLASS QUEUEING NETWORKS
The following are
abstracts for
a triple of papers (two by R. J. Williams
and one by M. Bramson) concerned with
heavy traffic limits for open multiclass queueing networks.
AN INVARIANCE PRINCIPLE FOR SEMIMARTINGALE REFLECTING
BROWNIAN MOTIONS IN AN ORTHANT
R. J. Williams,
Department of Mathematics,
University of California, San Diego,
La Jolla CA 92093-0112
Semimartingale reflecting Brownian motions in an orthant (SRBMs)
are of interest in applied probability
because of their role as heavy traffic
approximations for open queueing
networks. It is shown in this paper
that a process which satisfies
the definition of an SRBM, except that small
random perturbations in the defining conditions are allowed, is
close in distribution to an SRBM.
This perturbation result is called an invariance principle
by analogy with the
invariance principle of Stroock and Varadhan for diffusions with boundary conditions.
A crucial ingredient in the proof of this result is
an oscillation inequality for solutions of a related
Skorokhod problem.
In a subsequent paper,
the invariance principle is used to
give general conditions under which
a heavy traffic limit theorem
holds for open multiclass queueing networks.
Appears in Queueing Systems: Theory and
Applications, 30
(1998), 5--25. The original published manuscript is available from the publisher
by clicking here.
For a copy of a preprint for personal, scientific, non commercial use,
click here for postscript or here for pdf.
DIFFUSION APPROXIMATIONS FOR
OPEN MULTICLASS QUEUEING NETWORKS:
SUFFICIENT CONDITIONS INVOLVING STATE SPACE
COLLAPSE
R. J. Williams,
Department of Mathematics,
University of California, San Diego,
La Jolla CA 92093-0112
Certain diffusion processes known as
semimartingale reflecting Brownian motions (SRBMs) have been shown to
approximate many single class and some multiclass open queueing
networks under conditions
of heavy traffic.
While it is known that not all multiclass networks with feedback
can be approximated
in heavy traffic by SRBMs, one of the outstanding challenges in contemporary
research on queueing networks
is to identify broad categories of
networks that can be so approximated and to prove a heavy traffic
limit theorem justifying the approximation.
In this paper,
general sufficient conditions are given
under which a
heavy traffic limit theorem holds
for open multiclass queueing networks
with head-of-the-line (HL)
service disciplines,
which in particular
require that service
\it within \rm each class
is on a
first-in-first-out (FIFO) basis.
The two main conditions that need to be
verified
are that
(a) the reflection matrix for the SRBM
is well defined and
completely-${\cal S}$, and (b) a form
of state
space collapse holds.
A result of Dai and Harrison shows that condition
(a) holds
for FIFO networks of Kelly type
and their proof is extended here to cover
networks with the HLPPS
(head-of-the-line proportional
processor sharing) service discipline.
In a companion work, Bramson
shows that
a multiplicative form of
state space collapse holds for these two families
of networks.
These results, when combined with the main theorem of this paper,
yield new heavy traffic limit theorems for
FIFO networks of Kelly type and networks with the HLPPS service discipline.
Appears in Queueing Systems: Theory and
Applications, 30 (1998), 27--88. The original manuscript is available
from the publisher by clicking here.
For a copy of a preprint for personal, scientific, non commercial use,
click here for postscript or here for pdf.
STATE SPACE COLLAPSE WITH APPLICATION TO HEAVY TRAFFIC
LIMITS FOR MULTICLASS QUEUEING NETWORKS
Maury Bramson,
School of Mathematics, University of Minnesota,
Minneapolis, MN 55455, USA
Heavy traffic limits for queueing networks are a topic of continuing
interest. Presently, the class of networks for which these limits have
been
rigorously derived is restricted. An important ingredient in such work is
the demonstration of state space collapse. Here, we demonstrate state
space collapse for
two families of networks, FIFO queueing networks of Kelly type and HLPPS
queueing networks. We then discuss the ramifications of our techniques for
more general networks. For FIFO networks of Kelly type, the discipline is
first-in, first-out,
and the service rate depends only on the station. For HLPPS networks, the
discipline is head-of-the-line proportional processor sharing, where the
fraction of time spent serving a class present at a station is proportional
to the quantity of the class there, with all of the service going into the
first customer of each class. When the service times are exponentially
distributed, this discipline has queue length process which is equivalent
to that of standard processor sharing, where all customers of a class receive
equal service. To demonstrate state space collapse for both families, we
employ law of large number estimates to show a form of compactness for
appropriately scaled solutions. The limits of these solutions are next
shown to satisfy fluid model equations corresponding to the above queueing
networks. Results from Bramson (1996, 1997) on the asymptotic behavior of
these limits then imply state space collapse. The desired heavy traffic
limits for FIFO and HLPPS networks follow from this and the general
criteria set forth in the companion
paper Williams (1997). State space collapse and the ensuing heavy
traffic limits also hold for more general queueing networks, provided the
solutions of their fluid model equations converge. Partial results are
given for such networks, which include the static priority disciplines.
Appears in Queueing
Systems: Theory and Applications, 30 (1998), 89--148. The original published
manuscript is available from the publisher by clicking here.