State-dependent Coupling of Quasireversible Nodes

The seminal paper of Jackson began a chain of research on queueing networks with product-form stationary distributions which continues strongly to this day. Hard on the heels of the early results on queueing networks followed a series of papers which discussed the relationship between product-form stationary distributions and the quasireversibility of network nodes. More recently, the definition of quasireversibility and the coupling mechanism between nodes have been extended so that they apply to some of the later product-form queueing networks incorporating negative customers, signals, and batch movements.In parallel with this research, it has been shown that some special queueing networks can have arrival and service parameters which depend upon the network state, rather than just the node state, and still retain a generalised product-form stationary distribution.In this paper we begin by offering an alternative proof of a product-form result of Chao and Miyazawa and then build on this proof by postulating a state-dependent coupling mechanism for a quasireversible network. Our main theorem is that the resultant network has a generalised product form stationary distribution. We conclude the paper with some examples.     

Markovian network processes: Congestion-dependent routing and processing

A Markovian network process describes the movement of discrete units among a set of nodes that process the units. There is considerable knowledge of such networks, often called queueing networks, in which the nodes operate independently and the routes of the units are independent. The focus of this study, in contrast, is on networks with dependent nodes and routings. Examples of dependencies are parallel processing across several nodes, blocking of transitions because of capacity constraints on nodes, alternate routing of units to avoid congestion, and accelerating or decelerating the processing rate at a node depending on downstream congestion. We introduce a general network process representing the numbers of units at the nodes and derive its equilibrium distribution. This distribution takes the form of a product of functions of vectors in which the arguments of the functions satisfy an interchangeability property. This new type of distribution may apply to other multi-variate processes as well. A basic idea in our approach is a linking of certain micro-level balance properties of the network routing to the processing rates at the nodes. The link is via routing-balance partitions of nodes that are inherent in any network. A byproduct of this approach is a general characterization of blocking of transitions without the restriction that the process is reversible, which had been a standard assumption. We also give necessary and sufficient conditions under which a unit moving in the network sees a time average for the unmoved units (called the MUSTA property). Finally, we discuss when certain flows between nodes in an open network are Poisson processes.This research was sponsored in part by Air Force Office of Scientific Research contract 84-0367.     

Some Results for Large Closed Queueing Networks with and without Bottleneck: Up- and Down-Crossings Approach

The paper provides the up- and down-crossing method to study the asymptotic behavior of queue-length and waiting time in closed Jackson-type queueing networks. These queueing networks consist of central node (hub) and k single-server satellite stations. The case of infinite server hub with exponentially distributed service times is considered in the first section to demonstrate the up- and down-crossing approach to such kind of problems and help to understand the readers the main idea of the method. The main results of the paper are related to the case of single-server hub with generally distributed service times depending on queue-length. Assuming that the first k–1 satellite nodes operate in light usage regime, we consider three cases concerning the kth satellite node. They are the light usage regime and limiting cases for the moderate usage regime and heavy usage regime. The results related to light usage regime show that, as the number of customers in network increases to infinity, the network is decomposed to independent single-server queueing systems. In the limiting cases of moderate usage regime, the diffusion approximations of queue-length and waiting time processes are obtained. In the case of heavy usage regime it is shown that the joint limiting non-stationary queue-lengths distribution at the first k–1 satellite nodes is represented in the product form and coincides with the product of stationary GI/M/1 queue-length distributions with parameters depending on time.     

A network of priority queues in heavy traffic: One bottleneck station

In this paper we consider an open queueing network having multiple classes, priorities, and general service time distributions. In the case where there is a single bottleneck station we conjecture that normalized queue length and sojourn time processes converge, in the heavy traffic limit, to one-dimensional reflected Brownian motion, and present expressions for its drift and variance. The conjecture is motivated by known heavy traffic limit theorems for some special cases of the general model, and some conjectured “Heavy Traffic Principles” derived from them. Using the known stationary distribution of one-dimensional reflected Brownian motion, we present expressions for the heavy traffic limit of stationary queue length and sojourn time distributions and moments. For systems with Markov routing we are able to explicitly calculate the limits.     

The tightness in the ergodic analysis of regenerative queueing processes

The tightness of some queueing stochastic processes is proved and its role in an ergodic analysis is considered. It is proved that the residual service time process in an open Jackson-type network is tight. The same problem is solved for a closed network, where the basic discrete time process is embedded at the service completion epochs. An extention of Kiefer and Wolfowitz's “key” lemma to a nonhomogeneous multiserver queue with an arbitrary initial state is obtained. These results are applied to get the ergodic theorems for the basic regenerative network processes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Stability analysis of parallel server systems under longest queue first

We consider the stability of parallel server systems under the longest queue first (LQF) rule. We show that when the underlying graph of a parallel server system is a tree, the standard nominal traffic condition is sufficient for the stability of that system under LQF when interarrival and service times have general distributions. Then we consider a special parallel server system, which is known as the X-model, whose underlying graph is not a tree. We provide additional “drift” conditions for the stability and transience of these queueing systems with exponential interarrival and service times. Drift conditions depend in general on the stationary distribution of an induced Markov chain that is derived from the underlying queueing system. We illustrate our results with examples and simulation experiments. We also demonstrate that the stability of the LQF depends on the tie-breaking rule used and that it can be unstable even under arbitrary low loads.     

Traffic Flows and Product Form Solutions in Stochastic Transfer Networks

This paper focuses on product form and related tractable stationary distributions in a general class of stochastic networks with finite numbers of nodes such that their network states are changed through signal transfers as well as internal transitions. Signals may be customers in traditional queueing applications, but we do not make any restriction on their effects at departing as well as arriving nodes. They may also instantaneously move around among different nodes. Furthermore, signal routing may depend on the whole network state. For analytical simplicity, we assume that the state space is countable. For such a network, we propose an abstract model, called a stochastic transfer network, and consider the stationary distribution of the network state. We introduce conditional traffic rates for arrivals and departures. Using them, we consider when the network has product form or some other tractable stationary distributions.     

服务率可变的批服务排队网络

大部分排队网络的研究结果是在服务率不变的条件下给出的。本文分析了两类成批服务的排队网络。并在服务率依赖于批服务大小的条件下，利用各节点的准可逆性，给出了不带信号和带消极信号的两类排队网络的乘积形式稳态解．并利用不动点原理，证明了交通方程解的存在性．并给出求法。     

A survey of product form queueing networks with blocking and their equivalences

Queueing network models have been extensively used to represent and analyze resource sharing systems, such as production, communication and information systems. Queueing networks with blocking are used to represent systems with finite capacity resources and with resource constraints. Different blocking mechanisms have been defined and analyzed in the literature to represent distinct behaviors of real systems with limited resources. Exact product form solutions of queueing networks with blocking have been derived, under special constraints, for different blocking mechanisms. In this paper we present a survey of product form solutions of queueing networks with blocking and equivalence properties among different blocking network models. By using such equivalences we can extend product form solutions to queueing network models with different blocking mechanisms. The equivalence properties include relationships between open and closed product form queueing networks with different blocking mechanisms.This work has been partially supported by CNR Project Research Funds Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo and by MURST Project Research Funds Performability hw/sw di sistemi distribuiti e paralleli.     

Analysis of multiserver retrial queueing system: A martingale approach and an algorithm of solution

The paper studies a multiserver retrial queueing system withm servers. Arrival process is a point process with strictly stationary and ergodic increments. A customer arriving to the system occupies one of the free servers. If upon arrival all servers are busy, then the customer goes to the secondary queue, orbit, and after some random time retries more and more to occupy a server. A service time of each customer is exponentially distributed random variable with parameter μ₁. A time between retrials is exponentially distributed with parameter μ₂ for each customer. Using a martingale approach the paper provides an analysis of this system. The paper establishes the stability condition and studies a behavior of the limiting queue-length distributions as μ₂ increases to infinity. As μ₂→∞, the paper also proves the convergence of appropriate queue-length distributions to those of the associated “usual” multiserver queueing system without retrials. An algorithm for numerical solution of the equations, associated with the limiting queue-length distribution of retrial systems, is provided. AMS 2000 Subject classifications: 60K25 60H30.     

Regularly varying tails in a queue with discrete autoregressive arrivals of order p

We consider a discrete time single server queueing system where the service time of a customer is one slot, and the arrival process is governed by a discrete autoregressive process of order p (DAR(p)). For this queueing system, we investigate the tail behavior of the queue size and the waiting time distributions. Specifically, we show that if the stationary distribution of DAR(p) input has a tail of regular variation with index −β−1, then the stationary distributions of the queue size and the waiting time have tails of regular variation with index −β. This research was supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment).     

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.     

Exact asymptotics for the stationary distribution of a Markov chain: a production model

We derive rough and exact asymptotic expressions for the stationary distribution π of a Markov chain arising in a queueing/production context. The approach we develop can also handle “cascades,” which are situations where the fluid limit of the large deviation path from the origin to the increasingly rare event is nonlinear. Our approach considers a process that starts at the rare event. In our production example, we can have two sequences of states that asymptotically lie on the same line, yet π has different asymptotics on the two sequences.     

State-space collapse in stationarity and its application to a multiclass single-server queue in heavy traffic

Recently Gamarnik and Zeevi (Ann. Appl. Probab. 16:56–90, 2006) and Budhiraja and Lee (Math. Oper. Res. 34:45–56, 2009) established that, under suitable conditions, a sequence of the stationary scaled queue lengths in a generalized Jackson queueing network converges to the stationary distribution of multidimensional reflected Brownian motion in the heavy-traffic regime. In this work we study the corresponding problem in multiclass queueing networks (MQNs).     

G-networks: a unifying model for neural and queueing networks

We survey results concerning a new stochastic network we have developed [1–7], which was initially motivated by neural network modelling [1], or — as we called it — by queueing networks with positive and negative customers [2, 3]. Indeed, it is well known that signals in neural networks are formed by impulses or action potentials, traveling much like customers in a queueing network. We call this model a G-network because it serves as a unifying basis for diverse areas of stochastic modelling in queueing networks, computer networks, computer system performance and neural networks. In its simplest version, negative and positive signals or customers circulate among a finite set of units, modelling inhibitory and excitatory signals of a neural network, or negative and positive customers of a queueing network. Signals can arrive either from other units or from the outside world. Positive signals are accumulated at the input of each unit, and constitute its signal potential. The state of each unit or neuron is its signal potential (which is equivalent to the queue length), while the network state is the vector of signal potentials at each neuron. If its potential is positive, a unit or neuron fires, and sends out signals to the other neurons or to the outside world. As it does so, its signal potential is depleted. In the Markovian case, this model has product form, i.e. the steady-state probability distribution of its potential vector is the product of the marginal probabilities of the potential at each neuron. The signal flow equations of the network, which describe the rate at which positive or negative signals arrive to each neuron, are non-linear. We discuss the relationship between this model and the usual connectionist (formal) model of neural networks, and present applications to combinatorial optimization and to image texture processing. Extensions of the model to the case of multiple signal classes, and to networks with triggered customer motion are presented. We also examine the general stability conditions which guarantee that the network has a well-defined steady-state behaviour.     

Analysis of the M [X]/G/1 queues with second multi-optional service and unreliable server

A bulk-arrival single server queueing system with second multi-optional service and unreliable server is studied in this paper. Customers arrive in batches according to a homogeneous Poisson process, all customers demand the first ＂essential＂ service, whereas only some of them demand the second ＂multi-optional＂ service. The first service time and the second service all have general distribution and they are independent. We assume that the server has a service-phase dependent, exponentially distributed life time as well as a servicephase dependent, generally distributed repair time. Using a supplementary variable method, we obtain the transient and the steady-state solutions for both queueing and reliability measures of interest.     

An Alternative Model for Queueing Systems with Single Arrivals,Batch Services and Customer Coalescence

In this paper we consider a queueing system with single arrivals, batch services and customer coalescence and we use it as a building block for constructing queueing networks that incorporate such characteristics. Chao et al. (1996) considered a similar model and they proved that it possesses a geometric product form stationary distribution, under the assumption that if the number of units present at a service completion epoch is less than the required number of units, then all the units coalesce into an incomplete (defective) batch which leaves the system. We drop this assumption and we study a model without incomplete batches. We prove that the stationary distribution of such a queue has a nearly geometric form. Using quasi-reversibility arguments we construct a network model with such queues which provides relevant bounds and approximations for the behaviour of assembly processes. Several issues about the validity of these bounds and approximations are also discussed.     

Discrete and Continuous Time Modulated Random Walks with Heavy-Tailed Increments

We consider a modulated process S which, conditional on a background process X, has independent increments. Assuming that S drifts to −∞ and that its increments (jumps) are heavy-tailed (in a sense made precise in the paper), we exhibit natural conditions under which the asymptotics of the tail distribution of the overall maximum of S can be computed. We present results in discrete and in continuous time. In particular, in the absence of modulation, the process S in continuous time reduces to a Lévy process with heavy-tailed Lévy measure. A central point of the paper is that we make full use of the so-called “principle of a single big jump” in order to obtain both upper and lower bounds. Thus, the proofs are entirely probabilistic. The paper is motivated by queueing and Lévy stochastic networks.     

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.     

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.