Limit non-stationary behavior of large closed queueing networks with bottlenecks

In this paper martingales methods are applied for analyzing limit non-stationary behavior of the queue length processes in closed Jackson queueing networks with a single class consisting of a large number of customers, a single infinite server queue, and a fixed number of single server queues with large state independent service rates. It is assumed that one of the single server nodes forms a bottleneck. For the non-bottleneck nodes we show that the queue length distribution at timet converges in generalized sense to the stationary distribution of the M/M/1 queue whose parameters explicitly depend ont. For the bottleneck node a diffusion approximation with reflection is proved in the moderate usage regime while fluid and Gaussian diffusion approximations are established for the heavy usage regime.     

Some limit theorems for regenerative queues

We consider a single server queue with the interarrival times and the service times forming a regenerative sequence. This traffic class includes the standard models: iid, periodic, Markov modulated (e.g., BMAP model of Lucantoni [18]) and their superpositions. This class also includes the recently proposed traffic models in high speed networks, exhibiting long range dependence. Under minimal conditions we obtain the rates of convergence to stationary distributions, finiteness of stationary moments, various functional limit theorems and the continuity of stationary distributions and moments. We use the continuity results to obtain approximations for stationary distributions and moments of an MMPP/GI/1 queue where the modulating chain has a countable state space. We extend all our results to feed-forward networks where the external arrivals to each queue can be regenerative. In the end we show that the output process of a leaky bucket is regenerative if the input process is and hence our results extend to a queue with arrivals controlled by a leaky bucket. This revised version was published online in June 2006 with corrections to the Cover Date.     

Calculating the normalization constants in queueing networks

Many queueing network models have a product-form solution for their steady-state probability distributions. However, the calculation of the normalization constants involved in the solutions is nontrivial. Recently, Gordon proposed a method to derive the closed form formula for normalization constants for certain closed networks. In this paper, we describe a simpler method using Z-transform. In the cases of networks of multiple server queues or of single server queues with equal traffic intensities, the computation involved in proposed approach is much simpler than that in Gordon's paper. For multichain closed networks, we propose to use FFT (Fast-Fourier-Transform) to calculate the normalization constants.     

Multidimensional large deviation local limit theorems

An earlier paper by the author ([4], 97–114) established large deviation local limit theorems for arbitrary sequences of real valued random variables. This work showed clearly the connection between the Cramér series and large deviation rates. In this article we present large deviation local limit theorems for arbitrary multidimensional random variables based solely on conditions imposed on their moment generating functions. These results generalize the theorems of [12], 100–106) for sums of independent and identically distributed random vectors.     

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.     

On central limit theorems for shrunken random variables

We discuss Central Limit Theorems and absence of limiting distributions for shrunken random variables.

     

On almost sure noncentral limit theorems

LetX(t) be a fractional Brownian motion or Hermite process of indexH. SetX _m (t)=m ^–H X(mt), which we view as an element ofC[0, 1]. Let {x} denote a point mass at x. Then The corresponding results for certain partial sums in the domain of attraction toX(t) are shown to hold.     

Heavy traffic limit theorems for a sequence of shortest queueing systems

A sequence of shortest queueing systems is considered in this paper. We give weak convergence theorems for the queue length and waiting time processes when the sequence of traffic intensities associated with the sequence of shortest queueing systems approaches the critical value (=1) at appropriate rates.Research supported by the National Natural Science Foundation of China.     

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.     

Stability and continuity of polling systems

The stability of a polling system with exhaustive service and a finite number of users, each with infinite buffers is considered. The arrival process is more general than a Poisson process and the system is not slotted. Stochastic continuity of the stationary distributions, rates of convergence and functional limit theorems for the queue length and waiting time processes have also been proved. The results extend to the gated service discipline.     

Limit theorems for records from discrete distributions

Weak and strong functional limit theorems are obtained for record values and record epochs in a sequence of independent random variables with common distribution F. The emphasis is on the case in which F is concentrated on the non-negative integers. For contrast, the well-known case of continuous F is also considered. Analogues of results obtained earlier by Resnick, de Haan and the author for continuous F are presented here for F concentrated on the non-negative integers. Also is investigated under which circumstances the latter case is so close to the continuous F case that the resulting limit theorems are the same.     

Asymptotic analysis for closed multiclass queueing networks in critical usage

We consider a class of closed multiclass queueing networks containing First-Come-First-Serve (FCFS) and Infinite Server (IS) stations. These networks have a productform solution for their equilibrium probabilities. We study these networks in an asymptotic regime for which the number of customers and the service rates at the FCFS stations go to infinity with the same order. We assume that the regime is in critical usage, whereby the utilizations of the FCFS servers slowly approach one. The asymptotic distribution of the normalized queue lengths is shown to be in many cases a truncated multivariate normal distribution. Traffic conditions for which the normalized queue lengths arealmost asymptotically independent are determined. Asymptotic expansions of utilizations and expected queue lengths are presented. We show through an example how to obtain asymptotic expansions of performance measures when the networks are in mixed usage and how to apply the results to networks with finite data.Supported partially by NSF grant NCR93-04601.     

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.     

Asymptotic expansions in functional limit theorems

Asymptotic expansions for a class of functional limit theorems are investigated. It is shown that the expansions in this class fit into a common scheme, defined by a sequence of functions h_n (ε₁,…, ε_n), n ≥ 1, of “weights” (for n observations), which are smooth, symmetric, compatible and have vanishing first derivatives at zero. Then $\text{h}{}_{\mathrm{n}}\text{(n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{,…, n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{)}$ admits an asymptotic expansion in powers of $\text{n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}$. Applications to quadratic von Mises functionals, the C.L.T. in Banach spaces, and the invariance principle are discussed.     

Deadlock properties of queueing networks with finite capacities and multiple routing chains

Blocking in queueing network models with finite capacities can lead to deadlock situations. In this paper, deadlock properties are investigated in queueing networks with multiple routing chains. The necessary and sufficient conditions for deadlockfree queueing networks with blocking are provided. An optimization algorithm is presented for finding deadlock-free capacity assignments with the least total capacity. The optimization algorithm maps the queueing network into a directed graph and obtains the deadlock freedom conditions from a specified subset of cycles in the directed graph. In certain network topologies, the number of deadlock freedom conditions can be large, thus, making any optimization computationally expensive. For a special class of topologies, so-calledtandem networks, it is shown that a minimal capacity assignment can be directly obtained without running an optimization algorithm. Here, the solution to the minimal capacity assignment takes advantage of the regular topology of tandem networks.This work was supported by the National Science Foundation under Grant No. CCR-90-11981.     

Approximation and limit theorems for quantum stochastic models with unbounded coefficients

We prove a limit theorem for quantum stochastic differential equations with unbounded coefficients which extends the Trotter-Kato theorem for contraction semigroups. From this theorem, general results on the convergence of approximations and singular perturbations are obtained. The results are illustrated in several examples of physical interest.     

Strong limit theorems for quasi-orthogonal random fields

This is a systematic and unified treatment of a variety of seemingly different strong limit problems. The main emphasis is laid on the study of the a.s. behavior of the rectangular means ζ_mn = 1/(λ₁(m) λ₂(n)) Σ_i=1^m Σ_k=1ⁿ X_ik as either max{m, n} → ∞ or min{m, n} → ∞. Here {X_ik: i, k ≥ 1} is an orthogonal or merely quasi-orthogonal random field, whereas {λ₁(m): m ≥ 1} and {λ₂(n): n ≥ 1} are nondecreasing sequences of positive numbers subject to certain growth conditions. The method applied provides the rate of convergence, as well. The sufficient conditions obtained are shown to be the best possible in general. Results on double subsequences and 1-parameter limit theorems are also included.     

Diffusion approximations for open queueing networks with service interruptions

This paper establishes functional central limit theorems describing the heavy-traffic behavior of open single-class queueing networks with service interruptions. In particular, each station has a single server which is alternatively up and down. There are two treatments of the up and down times. The first treatment corresponds to fixed up and down times and leads to a reflected Brownian motion, just as when there are no service interruptions, but with different parameters. To represent long rare interruptions, the second treatment has growing up and down times with the up and down times being of ordern andn ^1/2, respectively, when the traffic intensities are of order 1-n^–1/2. In this case we establish convergence in the SkorohodM ₁ topology to a multidimensional reflection of multidimensional Brownian motion plus a multidimensional jump process.     

Functional central limit theorems for approximate Martingale arrays in a locally compact Abelian group

This paper uses a Martingale-like approach and establishes, among other things, the existence of continuous Gaussian processes with independent increments on those locally compact Abelian groups whose duals support corresponding continuous nonnegative quadratic forms.     

On functional central limit theorems for certain continuous time parameter stochastic processes

Weak invariance principles for certain continuous time parameter stochastic processes (including martingales and reverse martingales) are considered. Weak convergence in the sup-norm metric is also studied.