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.