Exact buffer overflow calculations for queues via martingales. (English) Zbl 1035.90018

Summary: Let \(\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 \(\mathbb E\tau_n\) and the Laplace transform \(\mathbb Ee^{-s\tau_n}\) is derived in closed form using a martingale introduced in O. Kella and W. Whitt [J. Appl. Probab. 29, 396–403 (1992; Zbl 0761.60065)]. For workload processes and more general systems like MAP/PH/1, we use a Markov additive extension given in the first author and O. Kella [Adv. appl. Probab. 32, 376–393 (2000; Zbl 0961.60081)] 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.


90B22 Queues and service in operations research
60J27 Continuous-time Markov processes on discrete state spaces
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
60G48 Generalizations of martingales
Full Text: DOI