Large deviation analysis of the single server queue

We establish the large deviation principle (LDP) for the virtual waiting time and queue length processes in the GI/GI/1 queue. The rate functions are found explicitly. As an application, we obtain the logarithmic asymptotics of the probabilities that the virtual waiting time and queue length exceed high levels at large times. Additional new results deal with the LDP for renewal processes and with the derivation of unconditional LDPs for conditional ones. Our approach applies in large deviations ideas and methods of weak convergence theory.This work was supported in part by AT&T Bell Labs.     

On the limit law of a random walk conditioned to reach a high level

We consider a random walk with a negative drift and with a jump distribution which under Cramér’s change of measure belongs to the domain of attraction of a spectrally positive stable law. If conditioned to reach a high level and suitably scaled, this random walk converges in law to a nondecreasing Markov process which can be interpreted as a spectrally positive Lévy process conditioned not to overshoot level 1.     

A critically loaded multirate link with trunk reservation

We consider a loss system model of interest in telecommunications. There is a single service facility with N servers and no waiting room. There are K types of customers, with type ί customers requiring A _ί servers simultaneously. Arrival processes are Poisson and service times are exponential. An arriving type ί customer is accepted only if there are Rί(⩾A_ί ) idle servers. We examine the asymptotic behavior of the above system in the regime known as critical loading where both N and the offered load are large and almost equal. We also assume that R ₁,..., R _K-1 remain bounded, while R _K ^N ←∞ and R _K ^N /√N ← 0 as N ← ∞. Our main result is that the K dimensional “queue length” process converges, under the appropriate normalization, to a particular K dimensional diffusion. We show that a related system with preemption has the same limit process. For the associated optimization problem where accepted customers pay, we show that our trunk reservation policy is asymptotically optimal when the parameters satisfy a certain relation. This revised version was published online in June 2006 with corrections to the Cover Date.     

A mean-field limit for a class of queueing networks

A model of centralized symmetric message-switched networks is considered, where the messages having a common address must be served in the central node in the order which corresponds to their epochs of arrival to the network. The limitN is discussed, whereN is the branching number of the network graph. This procedure is inspired by an analogy with statistical mechanics (the mean-field approximation). The corresponding limit theorems are established and the limiting probability distribution for the network response time is obtained. Properties of this distribution are discussed in terms of an associated boundary problem.     

A heavy-traffic analysis of a closed queueing system with a GI/∞ service center

This paper studies the heavy-traffic behavior of a closed system consisting of two service stations. The first station is an infinite server and the second is a single server whose service rate depends on the size of the queue at the station. We consider the regime when both the number of customers, n, and the service rate at the single-server station go to infinity while the service rate at the infinite-server station is held fixed. We show that, as n→∞, the process of the number of customers at the infinite-server station normalized by n converges in probability to a deterministic function satisfying a Volterra integral equation. The deviations of the normalized queue from its deterministic limit multiplied by √n converge in distribution to the solution of a stochastic Volterra equation. The proof uses a new approach to studying infinite-server queues in heavy traffic whose main novelty is to express the number of customers at the infinite server as a time-space integral with respect to a time-changed sequential empirical process. This gives a new insight into the structure of the limit processes and makes the end results easy to interpret. Also the approach allows us to give a version of the classical heavy-traffic limit theorem for the G/GI/∞ queue which, in particular, reconciles the limits obtained earlier by Iglehart and Borovkov. This revised version was published online in June 2006 with corrections to the Cover Date.     

Limiting results for multiprocessor systems with breakdowns and repairs

An M/M/N queue, where each of the processors is subject to independent random breakdowns and repairs, is analyzed in the steady state under two limiting regimes. The first is the usual heavy traffic limit where the offered load approaches the available processing capacity. The (suitably normalized) queue size is shown to be asymptotically exponentially distributed and independent of the number of operative processors. The second limiting regime involves increasing the average lengths of the operative and inoperative periods, while keeping their ratio constant. Again the asymptotic distribution of an appropriately normalized queue size is determined. This time it turns out to have a rational Laplace transform with simple poles. In both cases, the relevant parameters are easily computable.     

On Large Deviation Convergence of Invariant Measures

We present new results on the connection between large deviation principles for trajectories of stochastic processes and the associated invariant measures. Applications to diffusion and queuing processes are provided.     

On the M_t/M_t/K_t+M_t queue in heavy traffic

The focus of this paper is on the asymptotics of large-time numbers of customers in time-periodic Markovian many-server queues with customer abandonment in heavy traffic. Limit theorems are obtained for the periodic number-of-customers processes under the fluid and diffusion scalings. Other results concern limits for general time-dependent queues and for time-homogeneous queues in steady state.