Large deviations and overflow probabilities for the general single-server queue, with applications

Duffield, N. G. and O'Connell, Neil (1993) Large deviations and overflow probabilities for the general single-server queue, with applications. (Preprint)

Text DIAS-STP-93-30.pdf Download (617kB)

Abstract

We consider from a thermodynamic viewpoint queueing systems where the workload process is assumed to have an associated large deviation principle with arbitrary scaling: there exist increasing scaling functions (a_t, v_t, t ϵ R_+) and a rate function I such that if (W_t, t ϵ R_+) denotes the workload process, then lim_(t→∞) (v_t)^(-1)logP(W_t/a_t > w) = -I(w) on the continuity set of I. In the case that a_t = v_t = t it has been argued heuristically, and recently proved in a fairly general context (for discrete time models) by Glynn and Whitt [8], that the queue-length distribution (that is, the distribution of supremum of the workload process Q = sup_(t≥0) W_t) decays exponentially: P(Q > b) ~ e^(-δb) and the decay rate δ is directly related to the rate function I. We establish conditions for a more general result to hold, where the scaling functions are not necessarily linear in t: we find that the queue-length distribution has an exponential tail only if lim_(t→∞) a_t/v_t is finite and strictly positive; otherwise, provided our conditions are satisfied, the tail probabilities decay like P(Q > b) ~ e^(-δv(a^(-1)(b))). We apply our results to a range of workload processes, including fractional Brownian motion (a model that has been proposed in the literature (see, for example, Leland et al [10] and Norros [13]) to account for self-similarity and long range dependence) and, more generally, Gaussian processes with stationary increments. We also show that the martingale upper bound estimates obtained by Daley and Duffield [5], when the workload is modelled as an Ornstein-Uhlenbeck position process, are asymptotically correct.

Item Type:	Article
Divisions:	School of Theoretical Physics > Preprints
Date Deposited:	19 Jun 2018 14:12
Last Modified:	16 Dec 2022 02:49
URI:	https://dair.dias.ie/id/eprint/720

Actions (login required)

View Item

Downloads