On the reversibility of queueing networks

This paper relates the reversibility of certain discrete state Markovian queueing networks — the class of quasi-reversible networks — to the reversibility of the underlying switching process. Quasi-reversible networks are characterized by a product form equilibrium state distribution.When the state can be represented by customer totals at each node, the reversibility of the state process is equivalent to the reversibility of the switching process. More complicated quasi-reversible networks require additional conditions, to ensure the reversibility of the network state process.     

Estimating variance of output from cyclic exponential queueing systems

Production systems, particularly those making use of a pull production control mechanism, are well-modeled as closed queueing networks. Average throughput is clearly one important performance measure for these systems. However, many control decisions require information concerning the variability of the output process as well as throughput. Because of this, the standard deviation of the number of outputs during a specified interval is a practical performance measure for production systems.In this paper, we consider the standard deviation of the number of outputs during a time interval from a closed queueing network consisting ofM single server exponential queues. Because computing this quantity exactly is extremely cumbersome, we introduce a simple approximation that makes use of (1) known results for the variance of the time a marked job takes to complete a round trip and (2) an approximate correction term for the covariance between successive round trips. We show through comparisons with simulation that our method is quite accurate under a variety of conditions.     

Estimating the sojourn time sensitivity in queueing networks using perturbation analysis

The sample path perturbation analysis technique developed earlier for the analysis of throughput sensitivities (Refs. 1–3) is extended to the performance measures involving mean sojourn times of customers. The major features of the sojourn time sensitivity problem are twofold. Firstly, it is a performance associated with servers, and not with customers. Secondly, the average sojourn time in any finite observation period can be a discontinuous function of mean service times when blocking is involved in a system. This discontinuity causes errors which must be accounted for in the estimation of sensitivities. Numerical experiments and analysis validate this method of computation of the sensitivities.This work was supported by the US Office of Naval Research, Contracts N00014-84-K-0465 and N00014-79-C-0776, and by the National Science Foundation, Grant No. ENG-78-15231.     

On stationary tandem queueing networks with job feedback

The class of tandem queueing networks with job feedback is studied under stationarity conditions on the arrival and service times sequences. Each job, after completing service in the last queue, is fed back (rerouted) to the first one, a random number of times, before leaving the system. The average execution time per job is exactly computed, as the number of jobs becomes large, and is minimized under mild conditions. The degree of parallelism achieved in the processing is also computed. The issue of rate-stability of the system is then considered. The network is defined to be rate-stable iff the job departure rate is equal to the job arrival rate; that depends heavily on the dynamic feedback policy we employ to place rerouted jobs in specific places of the front queue buffer of the network. The condition under which the network is rate-stable is specified, and a dynamic feedback policy is constructed, which rate-stabilizes the system under the maximum possible job arrival rate; thus, it maximizes the dynamic throughput of the network. Other related results concerning the performance of tandem networks with feedback are obtained.Research supported in part by grants NSF-DDM-RIA-9010778, NSF-NCR-9116268, NSF-NCR-NYI-9258 507, by an AT&T Foundation grant and a GTE Fellowship.     

The QNET method for two-moment analysis of open queueing networks

Consider an open network of single-server stations, each with a first-in-first-out discipline. The network may be populated by various customer types, each with its own routing and service requirements. Routing may be either deterministic or stochastic, and the interarrival and service time distributions may be arbitrary. In this paper a general method for steady-state performance analysis is described and illustrated. This analytical method, called QNET, uses both first and second moment information, and it is motivated by heavy traffic theory. However, our numerical examples show that QNET compares favorably with W. Whitt's Queueing Network Analyzer (QNA) and with other approximation schemes, even under conditions of light or moderate loading. In the QNET method one first replaces the original queueing network by what we call an approximating Brownian system model, and then one computes the stationary distribution of the Brownian model. The second step amounts to solving a certain highly structured partial differential equation problem; a promising general approach to the numerical solution of that PDE problem is described by Harrison and Dai [8] in a companion paper. Thus far the numerical solution technique has been implemented only for two-station networks, and it is clear that the computational burden will grow rapidly as the number of stations increases. Thus we also describe and investigate a cruder approach to two-moment network analysis, called ΠNET, which is based on a product form approximation, or decomposition approximation, to the stationary distribution of the Brownian system model. In very broad terms, ΠNET is comparable to QNA in its level of sophistication, whereas QNET captures more subtle system interactions. In our numerical examples the performance of ΠNET and QNA is similar; the performance of QNET is generally better, sometimes much better.     

Bounding blocking probabilities and throughput in queueing networks with buffer capacity constraints

We propose a new technique for upper and lower bounding of the throughput and blocking probabilities in queueing networks with buffer capacity constraints, i.e., some buffers in the network have finite capacity. By studying the evolution of multinomials of the state of the system in its assumed steady state, we obtain constraints on the possible behavior of the system. Using these constraints, we obtain linear programs whose values upper and lower bound the performance measures of interest, namely throughputs or blocking probabilities. The main advantages of this new technique are that the computational complexity does not increase with the size of the finite buffers and that the technique is applicable to systems in which some buffers have infinite capacity. The technique is demonstrated on examples taken from both manufacturing systems and communication networks. As a special case, for the M/M/s/s queue, we establish the asymptotic exactness of the bounds, i.e., that the bounds on the blocking probability asymptotically approach the exact value as the degree of the multinomials considered is increased to infinity. This revised version was published online in June 2006 with corrections to the Cover Date.     

Piecewise linear test functions for stability and instability of queueing networks

We develop the use of piecewise linear test functions for the analysis of stability of multiclass queueing networks and their associated fluid limit models. It is found that if an associated LP admits a positive solution, then a Lyapunov function exists. This implies that the fluid limit model is stable and hence that the network model is positive Harris recurrent with a finite polynomial moment. Also, it is found that if a particular LP admits a solution, then the network model is transient. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Simple proof for the stability of global FIFO queueing networks

We study the stability of multiclass queueing networks under the global FIFO （first in first out） service discipline, which was established by Bramson in 2001. For these networks, the service priority of a customer is determined by his entrance time. Using fluid models, we describe the entrance time of the most senior customer in the networks at time t, which is the key to simplify the proof for the stability of the global FIFO queueing networks.     

A class of hierarchical queueing networks and their analysis

Queueing networks are an adequate model type for the analysis of complex system behavior. Most of the more realistic models are rather complex and do not fall into the easy solvable class of product form networks. Those models have to be analyzed by numerical solution of the underlying Markov chain and/or approximation techniques including simulation. In this paper a class of hierarchically structured queueing networks is considered and it is shown that the hierarchical model structure is directly reflected in the state space and the generator matrix of the underlying Markov chain. Iterative solution techniques for stationary and transient analysis can be modified to make use of the model structure and allow an efficient numerical analysis of large, up to now not solvable queueing networks.     

Value iteration and optimization of multiclass queueing networks

This paper considers in parallel the scheduling problem for multiclass queueing networks, and optimization of Markov decision processes. It is shown that the value iteration algorithm may perform poorly when the algorithm is not initialized properly. The most typical case where the initial value function is taken to be zero may be a particularly bad choice. In contrast, if the value iteration algorithm is initialized with a stochastic Lyapunov function, then the following hold: (i) a stochastic Lyapunov function exists for each intermediate policy, and hence each policy is regular (a strong stability condition), (ii) intermediate costs converge to the optimal cost, and (iii) any limiting policy is average cost optimal. It is argued that a natural choice for the initial value function is the value function for the associated deterministic control problem based upon a fluid model, or the approximate solution to Poisson’s equation obtained from the LP of Kumar and Meyn. Numerical studies show that either choice may lead to fast convergence to an optimal policy. This revised version was published online in June 2006 with corrections to the Cover Date.     

Stability of two families of queueing networks and a discussion of fluid limits

We investigate the stability of two families of queueing networks. The first family consists of a general class of networks, where service is allotted to the lead customer at each buffer. The other generalizes networks considered by Humes [18], and is related to the insertion of “leaky buckets” into the system. The arguments for the stability of the networks in each case rely on the corresponding behavior for the associated fluid models. This connection is employed using the framework established by Dai [10], with some modifications. It is discussed here in a somewhat more general setting, with future applications in mind. This revised version was published online in June 2006 with corrections to the Cover Date.     

Mean-value analysis for a class of Petri nets and batch-movement queueing networks with product-form equilibrium distributions

A number of recent papers have shown that there are classes of queueing networks, with batches of customers served and routed through the network, which have generalized product form equilibrium distributions. This extends to some Petri nets. In this paper, we indicate how a class of these is amenable to a mean-value analysis similar to that used for single-movement networks. To bring out the simplicity of the underlying ideas, we do this by working a simple example rather than presenting the development in its generality.     

Near-optimal analysis of homogeneous central-server queueing networks

The problem of achieving near-optimality in homogeneous central-server queueing networks is investigated by means of a composite approach based on approximate operational analysis and goal programming procedures. A near-optimal solution is shown to exist: this includes the expected overall waiting time, the overall throughput rate, as well as the distribution of queue length values. The need to maintain a balanced network flow and the desire to minimize the overall waiting time are expressed as complimentary objectives. Numerical results, based on past measurements from a multi-server computing facility, indicate that the performance gains obtained by the application of the present methodology are quite significant throughout the network's feasible population scale. © 1997 by John Wiley & Sons, Ltd.     

Approximate mean value performance analysis of cyclic queueing networks with production blocking

A simple approximation method is developed for performance analysis of exponential cyclic queues with production blocking. With a modified Arrival Instant Theorem to cater for finite queue capacity, a set of equations involving the mean values of performance measures are established and an efficient algorithm is proposed. Numerical experiments show that the approximation method is very efficient in providing results with good accuracy.     

Smoothed perturbation analysis algorithms for estimating the derivatives of occupancy-related functions in serial queueing networks

We present unbiased Smoothed Perturbation Analysis (SPA) estimators for the derivatives of occupancy-related performance functions in serial networks ofG/G/1 queues with respect to parameters of the distributions of service times at the queues. The sample functions for these performance measures are piecewise constant, and established Infinitesimal Perturbation Analysis (IPA) methods typically fail to provide unbiased estimators in this case. The performance measures considered in this paper are: the average network occupancy as seen by an arrival, the average occupancy of a specific queue as seen by an arrival to it, the probability that a customer is blocked at a specific queue, and the probability that a customer leaves a queue idle. The SPA estimators derived are quite simple and flexible, and they lend themselves to straightforward analysis. Unlike most of the established SPA algorithms, ours are not based on the comparison of hazard rates, and the proofs of their unbiasedness do not require the boundedness of such hazard rates.Supported in part by the National Science Foundation under Grant ECS-8801912, by the Office of Naval Research under Contract N00014-87-K-0304, and by NASA under Contract NAG 2-595.     

Stochastic petri net analysis of finite-population vacation queueing systems

We consider queueing systems in which the server occasionally takes a vacation of random duration. The vacation can be used to do additional work; it can also be a rest period. Several models of this problem have been analyzed in the past assuming that the population of the system is infinite. Similarly, it is generally assumed that the capacity of the system is infinite. In this paper we show how the finite-population system can be modeled by the stochastic Petri net. We also extend the model to the finite-capacity system. This research was sponsored by the SDIO Innovative Science and Technology Office and was managed by the Office of Naval Research under grant N3014-88-K-0623.     

Approximations of open queueing networks by reflection mappings

This paper presents a three-step procedure which allows to approximate the queue-length and the busy-time processes associated with open queueing networks. These three approximations are based on reflection mappings and are introduced with explicit estimates of their accuracy. The third one may be treated as approximation by accompanying reflection Brownian motions with rates of convergence. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Exact analysis of queueing networks with multiple job classes and blocking-after-service

Two models of closed queueing networks with blocking-after-service and multiple job classes are analyzed. The first model is a network withN stations and each station has either type II or type III. The second model is a star-like queueing network, also called a central server model, in which the stations may have either type I or type IV, with the condition that the neighbors of these stations must be of type II or type III such that blocking will be caused only by this set of station types. Exact product form solutions are obtained for the equilibrium state probabilities in both models. Formulae for performance measures such as throughput and the mean number of jobs are also derived.This work was supported by the National Science Foundation (NSF) under Grant No. CCR-90-11981.