LARGE DEVIATIONS AND OVERFLOW PROBABILITIES FOR THE GENERAL SINGLE-SERVER QUEUE, WITH APPLICATIONS

We consider 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 epsilon R(+)) and a rate function I such that if (W-t, t epsilon R(+)) denotes the workload process, then [GRAPHICS] 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 greater than or equal to 0 W?t) decays exponentially: P(Q > b) similar to e(-delta b) and the decay rate delta 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-->infinity) a(t)/v(t) is finite and strictly positive; other:wise, provided our conditions are satisfied, the tail probabilities decay like P (Q > b) similar to e(-delta 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[15, 16]) to account for self-similarity and long range dependence) and, more generally, Gaussian processes with stationary increments. We show that the martingale upper bound estimates obtained by Kulkarni and Rolski [5], when the workload is modelled as Ornstein-Uhlenbeck position process, are asymptotically correct. Finally we consider a non-Gaussian example, where the arrivals are modelled by a squared Bessel process.