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.     

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.     

Dynamic scheduling in multiclass queueing networks: Stability under discrete-review policies

This paper describes a family of discrete-review policies for scheduling open multiclass queueing networks. Each of the policies in the family is derived from what we call a dynamic reward function: such a function associates with each queue length vector q and each job class k a positive value r _k (q), which is treated as a reward rate for time devoted to processing class k jobs. Assuming that each station has a traffic intensity parameter less than one, all policies in the family considered are shown to be stable. In such a policy, system status is reviewed at discrete points in time, and at each such point the controller formulates a processing plan for the next review period, based on the queue length vector observed. Stability is proved by combining elementary large deviations theory with an analysis of an associated fluid control problem. These results are extended to systems with class dependent setup times as well as systems with alternate routing and admission control capabilities. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

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.     

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.     

Control and scheduling in a two-station queueing network: Optimal policies and heuristics

Consider a two-station queueing network with two types of jobs: type 1 jobs visit station 1 only, while type 2 jobs visit both stations in sequence. Each station has a single server. Arrival and service processes are modeled as counting processes with controllable stochastic intensities. The problem is to control the arrival and service processes, and in particular to schedule the server in station 1 among the two job types, in order to minimize a discounted cost function over an infinite time horizon. Using a stochastic intensity control approach, we establish the optimality of a specific stationary policy, and show that its value function satisfies certain properties, which lead to a switching-curve structure. We further classify the problem into six parametric cases. Based on the structural properties of the stationary policy, we establish the optimality of some simple priority rules for three of the six cases, and develop heuristic policies for the other three cases.     

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.     

Bottleneck analysis in multiclass closed queueing networks and its application

Asymptotic behavior of queues is studied for large closed multi-class queueing networks consisting of one infinite server station with K classes and M processor sharing (PS) stations. A simple numerical procedure is derived that allows us to identify all bottleneck PS stations. The bottleneck station is defined asymptotically as the station where the number of customers grows proportionally to the total number of customers in the network, as the latter increases simultaneously with service rates at PS stations. For the case when K=M=2, the set of network parameters is identified that corresponds to each of the three possible types of behavior in heavy traffic: both PS stations are bottlenecks, only one PS station is a bottleneck, and a group of two PS stations is a bottleneck while neither PS station forms a bottleneck by itself. In the last case both PS stations are equally loaded by each customer class and their individual queue lengths, normalized by the large parameter, converge to uniformly distributed random variables. These results are directly generalized for arbitrary K=M. Generalizations for K≠M are also indicated. The case of two bottlenecks is illustrated by its application to the problem of dimensioning bandwidth for different data sources in packet-switched communication networks. An engineering rule is provided for determining the link rates such that a service objective on a per-class throughput is satisfied. This revised version was published online in June 2006 with corrections to the Cover Date.     

Nonexistence of Brownian models for certain multiclass queueing networks

We present two multiclass queueing networks where the Brownian models proposed by Harrison and Nguyen [3,4] do not exist. If self-feedback is allowed, we can construct such an example with a two-station network. For a three-station network, we can construct such an example without self-feedback.Research supported in part by Texas Instruments Corporation Grant 90456-034.     

Towards better multi-class parametric-decomposition approximations for open queueing networks

Methods are developed for approximately characterizing the departure process of each customer class from a multi-class single-server queue with unlimited waiting space and the first-in-first-out service discipline. The model is (GT _i /GI _i )/1 with a non-Poisson renewal arrival process and a non-exponential service-time distribution for each class. The methods provide a basis for improving parametric-decomposition approximations for analyzing non-Markov open queueing networks with multiple classes. For example, parametric-decomposition approximations are used in the Queueing Network Analyzer (QNA). The specific approximations here extend ones developed by Bitran and Tirupati [5]. For example, the effect of class-dependent service times is considered here. With all procedures proposed here, the approximate variability parameter of the departure process of each class is a linear function of the variability parameters of the arrival processes of all the classes served at that queue, thus ensuring that the final arrival variability parameters in a general open network can be calculated by solving a system of linear equations.     

Estimating characteristics of queueing networks using transactional data

We are motivated by queueing networks in which queues are difficult to observe but services are easy to record. Our goal is to estimate the queues from service data. More specifically, we consider an open queueing network with Poisson external arrivals, multi‐server stations, general service times and Markovian switches of customers between stations. Customers' transitions between stations may be either immediate or of exponentially distributed durations. Each customer is supplied with an Identification Number (ID) upon entering the network. Operational data is collected which includes transaction times (starts and terminations of services) and ID's of served customers. Our objective is to estimate the evolution of the queues in the network, given the collected data. We cover estimation at both end of busy periods and in real time. The applicability of the theory is demonstrated by analyzing a service operation. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

A general formulation for mean-value analysis in product-form batch-movement queueing networks

A number of recent papers have shown that many classes of queueing networks with batches of customers served and routed through the network have equilibrium distributions which factorise into product forms over the nodes of the network. In this paper we demonstrate how such networks are amenable to a mean-value analysis which generalises that used for single-movement networks.Since product-form stochastic Petri nets (SPNs) can be viewed as batch-movement queueing networks, our algorithm is also applicable to their analysis.     

Product form stationary distributions for queueing networks with blocking and rerouting

In this paper we study Markovian queueing networks in which the service and the routing characteristics have a particular form which leads to a product form stationary distribution for the number of customers in the various queues of the network. We show that if certain transitions are prohibited due to blocking conditions, then the form of the stationary distribution is preserved under a certain rerouting protocol. Several examples are presented which illustrate the wide applicability of the model. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Review of a fast simulation method for the analysis of queueing networks

This paper presents a review of and refinements to a class of discrete-event models for the analysis of unreliable queueing systems. In contrast to conventional piece-by-piece simulators, these models observe a number of rare events that affect the inflow and outflow rates at each queue. Between events, the evolution of the system is approximated by a linear function. Several experiments confirm the accuracy of this approximation and its computational efficiency over conventional simulation. © 1997 by John Wiley & Sons, Ltd.     

Instability of LAS multiclass queueing networks

We provide an example of a strictly subcritical multiclass queueing network which is unstable under the least attained service (LAS) service protocol. It is a reentrant line with two servers and six customer classes. The customer interarrival times in our system are bounded below and have finite exponential moments, while the corresponding service times are deterministic. As a special case, we obtain a deterministic, strictly subcritical unstable LAS network.     

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.     

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.