Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse

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 within 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- 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. This revised version was published online in June 2006 with corrections to the Cover Date.     

Long time asymptotics for constrained diffusions in polyhedral domains

We study long time asymptotic properties of constrained diffusions that arise in the heavy traffic analysis of multiclass queueing networks. We first consider the classical diffusion model with constant coefficients, namely a semimartingale reflecting Brownian motion (SRBM) in a d$d$-dimensional positive orthant. Under a natural stability condition on a related deterministic dynamical system [P. Dupuis, R.J. Williams, Lyapunov functions for semimartingale reflecting brownian motions, Annals of Probability 22 (2) (1994) 680–702] showed that an SRBM is ergodic. We strengthen this result by establishing geometric ergodicity for the process. As consequences of geometric ergodicity we obtain finiteness of the moment generating function of the invariant measure in a neighborhood of zero, uniform time estimates for polynomial moments of all orders, and functional central limit results. Similar long time properties are obtained for a broad family of constrained diffusion models with state dependent coefficients under a natural condition on the drift vector field. Such models arise from heavy traffic analysis of queueing networks with state dependent arrival and service rates.     

Computing the Stationary Distribution of an SRBM in an Orthant with Applications to Queueing Networks

In [15], a BNAfm (Brownian network analyzer with finite element method) algorithm was developed for computing the stationary distribution of a semimartingale reflecting Brownian motion (SRBM) in a hypercube. In this companion paper, that BNAfm algorithm is extended to computing the stationary distribution of an SRBM in an orthant, which is achieved by constructing a converging sequence of SRBMs in hypercubes. The SRBM in the orthant serves as an approximation model of queueing networks with infinite buffers. We show that the constructed sequence of SRBMs in the hypercubes converges weakly to the SRBM in the orthant as the hypercubes approach the orthant. Under the conjecture that the set of the stationary distributions of the SRBMs in the hypercubes is relatively compact, we prove that the sequence of the stationary distributions of the SRBMs in the hypercubes converges weakly to the stationary distribution of the SRBM in the orthant. A three-machine job shop example is presented to illustrate the effectiveness of the SRBM approximation model and our BNAfm algorithm. The BNAfm algorithm is shown to produce good estimates for stationary probabilities of queueing networks.     

On the Analysis of the Virtual Waiting Time in Open Queueing Networks

The model of an open queueing network in heavy traffic has been developed. These models are mathematical models of computer networks in heavy traffic. A limit theorem has been presented for the virtual waiting time of a customer in heavy traffic in open queueing networks. Finally, we present an application of the theorem—a reliability model from computer network practice.     

Heavy traffic analysis of maximum pressure policies for stochastic processing networks with multiple bottlenecks

A class of open processing networks operating under a maximum pressure policy is considered in the heavy traffic regime. We prove that the diffusion-scaled workload process for a network with several bottleneck resources converges to a semimartingale reflecting Brownian motion (SRBM) living in a polyhedral cone. We also establish a state space collapse result that the queue length process can be lifted from the lower-dimensional workload process.     

On the law of the iterated logarithm in open queueing networks

An open queueing network model in heavy traffic is developed. Such models are mathematical models of computer networks in heavy traffic. Laws of the iterated logarithm for the virtual waiting time of the customer in open queueing networks and homogeneous computer networks are proved.     

Brownian models of multiclass queueing networks: Current status and open problems

This paper is concerned with Brownian system models that arise as heavy traffic approximations for open queueing networks. The focus is on model formulation, and more specifically, on the formulation of Brownian models for networks with complex routing. We survey the current state of knowledge in this dynamic area of research, including important open problems. Brownian approximations culminate in estimates of complete distributions; we present numerical examples for which complete sojourn time distributions are estimated, and those estimates are compared against simulation.     

State space collapse with application to heavy traffic limits for multiclass queueing networks

Heavy traffic limits for multiclass 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, first-in first-out (FIFO) queueing networks of Kelly type and head-of-the-line proportional processor sharing (HLPPS) queueing networks. We then apply our techniques to more general networks. To demonstrate state space collapse for FIFO networks of Kelly type and HLPPS networks, 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 [4,5] on the asymptotic behavior of these limits then imply state space collapse. The desired heavy traffic limits for FIFO networks of Kelly type and HLPPS networks follow from this and the general criteria set forth in the companion paper Williams [41]. 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. This revised version was published online in June 2006 with corrections to the Cover Date.     

On extreme values in open queueing networks

This paper presents heavy traffic limit theorems for the extreme virtual waiting time of a customer in an open queueing network. In this paper, functional limit theorems are proved for extreme values of important probability characteristics of the open queueing network investigated as the maximum and minimum of the total virtual waiting time of a customer, and the maximum and minimum of the virtual waiting time of a customer. Also, the paper presents the previous related works for extreme values in queues and the virtual waiting time in heavy traffic.     

About the Sojourn Time Process in Multiphase Queueing Systems

Multiphase queueing systems (MQS) (tandem queues, queues in series) are of special interest both in theory and in practical applications (packet switch structures, cellular mobile networks, message switching systems, retransmission of video images, asembly lines, etc.). In this paper, we deal with approximations of MQS and present a heavy traffic limit theorems for the sojourn time of a customer in MQS. Functional limit theorems are proved for the customer sojourn time – an important probability characteristic of the queueing system under conditions of heavy traffic.      

On the law of the iterated logarithm in multiserver open queueing networks

The paper is devoted to the analysis of queueing systems in the context of the network and communication theory. We investigate a theorem on the law of the iterated logarithm for a queue of jobs in a multiserver open queueing network under heavy traffic conditions.     

The Finite Element Method for Computing the Stationary Distribution of an SRBM in a Hypercube with Applications to Finite Buffer Queueing Networks

This paper proposes an algorithm, referred to as BNAfm (Brownian network analyzer with finite element method), for computing the stationary distribution of a semimartingale reflecting Brownian motion (SRBM) in a hypercube. The SRBM serves as an approximate model of queueing networks with finite buffers. Our BNAfm algorithm is based on the finite element method and an extension of a generic algorithm developed by Dai and Harrison [14]. It uses piecewise polynomials to form an approximate subspace of an infinite-dimensional functional space. The BNAfm algorithm is shown to produce good estimates for stationary probabilities, in addition to stationary moments. This is in contrast to the BNAsm algorithm (Brownian network analyzer with spectral method) of Dai and Harrison [14], which uses global polynomials to form the approximate subspace and which sometimes fails to produce meaningful estimates of these stationary probabilities. Extensive computational experiences from our implementation are reported, which may be useful for future numerical research on SRBMs. A three-station tandem network with finite buffers is presented to illustrate the effectiveness of the Brownian approximation model and our BNAfm algorithm.     

Diffusion approximation for a heavily loaded multi-user wireless communication system with cooperation

A cellular wireless communication system in which data is transmitted to multiple users over a common channel is considered. When the base stations in this system can cooperate with each other, the link from the base stations to the users can be considered a multi-user multiple-input multiple-output (MIMO) downlink system. For such a system, it is known from information theory that the total rate of transmission can be enhanced by cooperation. The channel is assumed to be fixed for all transmissions over the period of interest and the ratio of anticipated average arrival rates for the users, also known as the relative traffic rate, is fixed. A packet-based model is considered where data for each user is queued at the transmit end. We consider a simple policy which, under Markovian assumptions, is known to be throughput-optimal for this coupled queueing system. Since an exact expression for the performance of this policy is not available, as a measure of performance, we establish a heavy traffic diffusion approximation. To arrive at this diffusion approximation, we use two key properties of the policy; we posit the first property as a reasonable manifestation of cooperation, and the second property follows from coordinate convexity of the capacity region. The diffusion process is a semimartingale reflecting Brownian motion (SRBM) living in the positive orthant of N-dimensional space (where N is the number of users). This SRBM has one direction of reflection associated with each of the 2 ^N −1 boundary faces, but show that, in fact, only those directions associated with the (N−1)-dimensional boundary faces matter for the heavy traffic limit. The latter is likely of independent theoretical interest.     

Expansions for Joint Laplace Transform of Stationary Waiting Times in (max,+)-linear Systems with Poisson Input

We give a Taylor series expansion for the joint Laplace transform of stationary waiting times in open (max,+)-linear stochastic systems with Poisson input. Probabilistic expressions are derived for coefficients of all orders. Even though the computation of these coefficients can be hard for certain systems, it is sufficient to compute only a few coefficients to obtain good approximations (especially under the assumption of light traffic). Combining this new result with the earlier expansion formula for the mean stationary waiting times, we also provide a Taylor series expansion for the covariance of stationary waiting times in such systems.It is well known that (max,+)-linear systems can be used to represent stochastic Petri nets belonging to the class of event graphs. This class contains various instances of queueing networks like acyclic or cyclic fork-and-join queueing networks, finite or infinite capacity tandem queueing networks with various types of blocking, synchronized queueing networks and so on. It also contains some basic manufacturing models such as kanban networks, assembly systems and so forth. The applicability of this expansion technique is discussed for several systems of this type.     

Heavy traffic approximations of large deviations of feedforward queueing networks

We consider a multi-class feedforward queueing network with first come first serve queueing discipline and deterministic services and routing. The large deviation asymptotics of tail probabilities of the distribution of the workload vector can be characterized by convex path space minimization problems with non-linear constraints. So far there exists no numerical algorithm which could solve such minimization problems in a general way. When the queueing network is heavily loaded it can be approximated by a reflected Brownian motion. The large deviation asymptotics of tail probabilities of the distribution of this heavy traffic limit can again be characterized by convex path space minimization problems with non-linear constraints. However, due to their less complicated structure there exist algorithms to solve such minimization problems. In this paper we show that, as the network tends to a heavy traffic limit, the solution of the large deviation minimization problems of the network approaches the solution of the corresponding minimization problems of a reflected Brownian motion. Stated otherwise, we show that large deviation and heavy traffic asymptotics can be interchanged. We prove this result in the case when the network is initially empty. Without proof we state the corresponding result in the stationary case. We present an illuminating example with two queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

Heavy traffic analysis of controlled multiplexing systems

The paper develops the mathematics of the heavy traffic approach to the control and optimal control problem for multiplexing systems, where there are many mutually independent sources which feed into a single channel via a multiplexer (or of networks composed of such subsystems). Due to the widely varying bit rates over all sources, control over admission, bandwidth, etc., is needed to assure good performance. Optimal control and heavy traffic analysis has been shown to yield systems with greatly improved performance. Indeed, the heavy traffic approach covers many cases of great current interest, and provides a useful and practical approach to problems of analysis and control arising in modern high speed telecommunications. Past works on the heavy traffic approach to the multiplexing problem concentrated on the uncontrolled system or on the use of the heavy traffic limit control problem for applications, and did not provide details of the proofs. This is done in the current paper. The basic control problem for the physical system is hard, and the heavy traffic approach provides much simplification. Owing to the presence of the control, as well as to the fact that the cost function of main interest is “ergodic”, the problem cannot be fully treated with “classical” methods of heavy traffic analysis for queueing networks. A basic result is that the optimal average costs per unit time for the physical problem converge to the optimal cost per unit time for the limit stationary process as the number of sources and the time interval goes to infinity. This convergence is both in the mean and pathwise senses. Furthermore, a “nice” nearly optimal control for the limit system provides nearly optimal values for the physical system, under heavy traffic, in both a mean and pathwise sense. This revised version was published online in June 2006 with corrections to the Cover Date.     

Existence Condition for the Diffusion Approximations of Multiclass Priority Queueing Networks

In this paper, we extend the work of Chen and Zhang [12] and establish a new sufficient condition for the existence of the (conventional) diffusion approximation for multiclass queueing networks under priority service disciplines. This sufficient condition relates to the weak stability of the fluid networks and the stability of the high priority classes of the fluid networks that correspond to the queueing networks under consideration. Using this sufficient condition, we prove the existence of the diffusion approximation for the last-buffer-first-served reentrant lines. We also study a three-station network example, and observe that the diffusion approximation may not exist, even if the proposed limiting semimartingale reflected Brownian motion (SRBM) exists.     

An interpolation approximation for the GI/G/1 queue based on multipoint Padé approximation

The performance evaluation of many complex manufacturing, communication and computer systems has been made possible by modeling them as queueing systems. Many approximations used in queueing theory have been drawn from the behavior of queues in light and heavy traffic conditions. In this paper, we propose a new approximation technique, which combines the light and heavy traffic characteristics. This interpolation approximation is based on the theory of multipoint Padé approximation which is applied at two points: light and heavy traffic. We show how this can be applied for estimating the waiting time moments of the ^GI/G/1 queue. The light traffic derivatives of any order can be evaluated using the MacLaurin series analysis procedure. The heavy traffic limits of the ^GI/G/1 queue are well known in the literature. Our technique generalizes the previously developed interpolation approximations and can be used to approximate any order of the waiting time moments. Through numerical examples, we show that the moments of the steady state waiting time can be estimated with extremely high accuracy under all ranges of traffic intensities using low orders of the approximant. We also present a framework for the development of simple analytical approximation formulas. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Full Idle Time in Multiphase Queueing Systems

The modern queueing theory is a powerful tool for a quantitative and qualitative analysis of communication systems, computer networks, transportation systems, and many other technical systems. The paper is designated to the analysis of queueing systems arising in the network theory and communications theory (such as the so-called multiphase queueing systems, tandem queues, or series of queueing systems). We present heavy traffic limit theorems for the full idle time in multiphase queueing systems. We prove functional limit theorems for values of the full idle time of a queueing system, which is its important probability characteristic. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 3, pp. 367–386, July–September, 2005.