Exact buffer overflow calculations for queues via martingales

Sören Asmussen, Manfred Jobmann and Hans-Peter Schwefel

Abstract:: Let $\tau=\tau_n$ be the first time a queueing process like the queue length or workload exceeds a level $n$. For
the M/M/1 queue length process, the mean $E\tau$ and the Laplace transform $E e^{-s\tau}$ is derived in
closed form using a martingale introduced in Kella \& Whitt (1992). For workload processes and more general systems like MAP/PH/1, we use a Markov additive extension given in Asmussen \& Kella (2000) to derive sets of linear equations determining the same quantities. Numerical illustrations are presented in the framework of M/M/1 and MMPP/M/1 with an application to performance evaluation of telecommunication systems with long--range dependent properties in the packet arrival process. Different approximations that are obtained from asymptotic theory are compared with exact numerical results.

Key words:: Exponential martingale, extreme value theory, Lévy process, local time, Markov-modulation, martingale, power tail, queue length, regenerative process, Wald martingale