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.     

Diffusion approximations for double-ended queues with reneging in heavy traffic

We study a double-ended queue consisting of two classes of customers. Whenever there is a pair of customers from both classes, they are matched and leave the system. The matching is instantaneous following the first-come–first-match principle. If a customer cannot be matched immediately, he/she will stay in a queue. We also assume customers are impatient with generally distributed patience times. Under suitable heavy traffic conditions, we establish simple linear asymptotic relationships between the diffusion-scaled queue length process and the diffusion-scaled offered waiting time processes and show that the diffusion-scaled queue length process converges weakly to a diffusion process that admits a unique stationary distribution.

     

Spectral gap for open Jackson networks

We generalize the decomposition method of the finite Markov chains for Poincaré inequality in Jerrum et al. (Ann. Appl. Probab., 14, 1741-1765 (2004)) to the reversible continuous-time Markov chains. And inductively, we give the lower bound of spectral gap for the ergodic open Jackson network by the decomposition method and the symmetrization procedure. The upper bound of the spectral gap is also presented.     

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.     

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.     

Importance sampling for Jackson networks

Rare event simulation in the context of queueing networks has been an active area of research for more than two decades. A commonly used technique to increase the efficiency of Monte Carlo simulation is importance sampling. However, there are few rigorous results on the design of efficient or asymptotically optimal importance sampling schemes for queueing networks. Using a recently developed game/subsolution approach, we construct simple and efficient state-dependent importance sampling schemes for simulating buffer overflows in stable open Jackson networks. The sampling distributions do not depend on the particular event of interest, and hence overflow probabilities for different events can be estimated simultaneously. A by-product of the analysis is the identification of the minimizing trajectory for the calculus of variation problem that is associated with the sample-path large deviation rate function.     

Diffusion approximations for re-entrant lines with a first-buffer-first-served priority discipline

The diffusion approximation is proved for a class of queueing networks, known as re-entrant lines, under a first-buffer-first-served (FBFS) service discipline. The diffusion limit for the workload process is a semi-martingale reflecting Brownian motion on a nonnegative orthant. This approximation has recently been used by Dai, Yeh and Zhou [21] in estimating the performance measures of the re-entrant lines with a FBFS discipline.Supported in part by a grant from NSERC (Canada).Supported in part by a grant from NSERC (Canada); the research was done while the author was visiting the Faculty of Commerce and Business Administration, UBC, Canada.     

Diffusion approximations for models of population growth with logarithmic interactions

In this paper we have studied the diffusion approximations for the stochastic Gompertz and logarithmic models of population growth. These approximations are of particular importance whenever the corresponding Markov population processes are not analytically tractable. For each model we have shown that, as the resource-size tends to infinity, the process on suitable scaling and normalization converges to a non-stationary Ornstein–Uhlenbeck process. Consequently the sizes of species have in the steady state normal distributions whose means and covariance functions are determinable.     

Strong approximations for Markovian service networks

Inspired by service systems such as telephone call centers, we develop limit theorems for a large class of stochastic service network models. They are a special family of nonstationary Markov processes where parameters like arrival and service rates, routing topologies for the network, and the number of servers at a given node are all functions of time as well as the current state of the system. Included in our modeling framework are networks of M _t /M _t /n _t queues with abandonment and retrials. The asymptotic limiting regime that we explore for these networks has a natural interpretation of scaling up the number of servers in response to a similar scaling up of the arrival rate for the customers. The individual service rates, however, are not scaled. We employ the theory of strong approximations to obtain functional strong laws of large numbers and functional central limit theorems for these networks. This gives us a tractable set of network fluid and diffusion approximations. A common theme for service network models with features like many servers, priorities, or abandonment is “non-smooth” state dependence that has not been covered systematically by previous work. We prove our central limit theorems in the presence of this non-smoothness by using a new notion of derivative. This revised version was published online in June 2006 with corrections to the Cover Date.     

Diffusion approximations for nonlinear phase locked loop-type systems with wide band inputs

Communication systems often involve differential equation models whose inputs are noises and signals with wide bandwidths. It is frequently of interest to approximate them by some Markov-diffusion process, since then many analytical and numerical methods can be used. Here, recent results on getting diffusion approximations to systems with such inputs are applied to three classes of detection systems which are very important in applications: (1) A phase locked loop with a limiter; (2) a quadricorrelator with and without a limiter (the function is to track changes in phase and frequency); (3) a “squaring” loop whose purpose is the tracking of the carrier frequency despite the carrier modulation. In (3), a type of pulse phase modulation is used. The method is natural, systematic and relatively straightforward. Under natural scaling of the signals and noises, the appropriate diffusion approximations (for band-pass, but wide-band noise) are obtained. The approximation is in the sense of weak convergence. The first two problems have been hard to analyze owing to the nature of the non-linearity, and the results clearly indicate the advantage and disadvantages of the use of the limiter. The third problem has been difficult to analyze, partly due to the periodicities which occur naturally in such problems. All three classes represent widely used and important systems, and much information can be obtained from the limit process. For example, the results show that the use of a limiter can actually improve the tracking ability of the systems, when the noise is small. The system signal and noise models to which the methods can be applied are much broader than those used here. But the results, together with the results in H. J. Kushner, IEEE Trans. Inform. TheoryIT-26 (1980), 715–725, for different classes of problems, illustrate the great potential of the approximation methods for problems in control and communication theory. In certain cases, the limit processes are of the type which have been obtained via more formal arguments.     

Higher order approximations for tandem queueing networks

In this paper a higher order approximation for single server queues and tandem queueing networks is proposed and studied. Different from the most popular two-moment based approximations in the literature, the higher order approximation uses the higher moments of the interarrival and service distributions in evaluating the performance measures for queueing networks. It is built upon the MacLaurin series analysis, a method that is recently developed to analyze single-node queues, along with the idea of decomposition using higher orders of the moments matched to a distribution. The approximation is computationally flexible in that it can use as many moments of the interarrival and service distributions as desired and produce the corresponding moments for the waiting and interdeparture times. Therefore it can also be used to study several interesting issues that arise in the study of queueing network approximations, such as the effects of higher moments and correlations. Numerical results for single server queues and tandem queueing networks show that this approximation is better than the two-moment based approximations in most cases.     

Importance functions for restart simulation of general Jackson networks

RESTART is an accelerated simulation technique that allows the evaluation of extremely low probabilities. In this method a number of simulation retrials are performed when the process enters regions of the state space where the chance of occurrence of the rare event is higher. These regions are defined by means of a function of the system state called the importance function. Guidelines for obtaining suitable importance functions and formulas for the importance function of two-stage networks were provided in previous papers. In this paper, we obtain effective importance functions for RESTART simulation of Jackson networks where the rare set is defined as the number of customers in a particular (‘target’) node exceeding a predefined threshold. Although some rough approximations and assumptions are used to derive the formulas of the importance functions, they are good enough to estimate accurately very low probabilities for different network topologies within short computational time.     

Neural networks and finite-order approximations

Email: Curry{at}Cardiff.ac.uk This paper investigates the approximation properties of standardfeedforward neural networks (NNs) through the application ofmultivanate Thylor-series expansions. The capacity to approximatearbitrary functional forms is central to the NN philosophy,but is usually proved by allowing the number of hidden nodesto increase to infinity. The Thylor-series approach does notdepend on such limiting cases, lie paper shows how the seriesapproximation depends on individual network weights. The roleof the bias term is taken as an example. We are also able tocompare the sigmoid and hyperbolic-tangent activation functions,with particular emphasis on their impact on the bias term. Thepaper concludes by discussing the potential importance of ourresults for NN modelling: of particular importance is the trainingprocess.     

Neural networks and flexible approximations

Email: cuny{at}cardiff.ac.uk This paper supports the view that neural networks are best seenas devices that can approximate a wide range of functions. Theauthors argue the need to consider the precise details of howthe approximations operate in practice. The paper shows howstandard network models can be regarded as polynomial functions,obtained from expanding exponential terms. Multivariate Taylor-seriesexpansions, obtained through the MAPLE software package, areused for this purpose. The expansions serve to cast light onthe role of the hidden nodes. Also considered is the relativedifficulty of fitting different types of function. Quadraticfunctions are compared with Gaussian shapes.     

Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers

In this paper, we propose a fully polynomial-time randomized approximation scheme (FPRAS) for a closed Jackson network. Our algorithm is based on the Markov chain Monte Carlo (MCMC) method. Thus our scheme returns an approximate solution, for which the size of the error satisfies a given bound. To our knowledge, this algorithm is the first polynomial time MCMC algorithm for closed Jackson networks with multiple servers. We propose two new ergodic Markov chains, both of which have a unique stationary distribution that is the product form solution for closed Jackson networks. One of them is for an approximate sampler, and we show that it mixes rapidly. The other is for a perfect sampler based on the monotone coupling from the past (CFTP) algorithm proposed by Propp and Wilson, and we show that it has a monotone update function.     

Diffusion approximations of age-and-position dependent branching processes

By a (G, F, h) age-and-position dependent branching process we mean a process in which individuals reproduce according to an age dependent branching process with age distribution function G(t) and offspring distribution generating function F, the individuals (located in R^N) can not move and the distance of a new individual from its parent is governed by a probability density function h(r). For each positive integer n, let Z_n(t,dx) be the number of individuals in dx at time t of the (G, F_n,h_n) age-and-position dependent branching process. It is shown that under appropriate conditions on G, F_n and h_n, the finite dimensional distribution of $\text{Z}{}_{\mathrm{n}}\text{(nt, dx)}\text{n}$ converges, as n → ∞, to the corresponding law of a diffusion continuous state branching process X(t,dx) determined by a ψ-semigroup {ψ_t: t ? 0}. The ψ-semigroup {ψ_t} is the solution of a non-linear evolution equation. A semigroup convergence theorem due to Kurtz [10], which gives conditions for convergence in distribution of a sequence of non-Markovian processes to a Markov process, provides the main tools.     

On product form approximations for communication networks with losses: Error bounds

This paper studies communication networks with packet or message losses due to collisions, transmission errors or finite buffer constraints. Analytic error bounds are derived for simple product form approximations. The approximations are based on ignoring and bounding loss probabilities. The error bounds can be computed easily. Two extreme situations are considered: (1) Networks with infinite capacities but state-dependent loss probabilities; (2) Networks with finite capacities (buffers) and losses due to saturated buffers. The error bounds are of the order when: (1) the loss probabilities are uniformly bounded by , or when (2) the steady-state probability of capacity excess is of order . The results provide formal justification for practical engineering approximations. Extensions to more complex communication networks seem possible.     

Error bounds for state space truncation of finite Jackson networks

A computational and an analytic error bound are derived for the truncation of finite Jackson networks. Numerical support is provided for the special application of a cellular mobile communication network.