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: | 19 Jul 2018 09:34 |

URI: | http://dair.dias.ie/id/eprint/720 |

### Actions (login required)

View Item |

### Downloads

Downloads per month over past year