Exponential Approximations for Tail Probabilities in Queues, I: Waiting Times

Abstract

This paper focuses on simple exponential approximations for tail probabilities of the steady-state waiting time in infinite-capacity multiserver queues based on small-tail asymptotics. For the GI/GI/s model, we develop a heavy-traffic asymptotic expansion in powers of one minus the traffic intensity for the waiting-time asymptotic decay rate. We propose a two-term approximation for the asymptotic decay rate based on the first three moments of the interarrival-time and service-time distributions. We also suggest approximating the asymptotic constant by the product of the mean and the asymptotic decay rate. We evaluate the exponential approximations based on the exact asymptotic parameters and their approximations by making comparisons with exact results obtained numerically for the BMAP/GI/1 queue, which has a batch Markovian arrival process, and the GI/GI/s queue. Numerical examples show that the exponential approximations are remarkably accurate, especially for higher percentiles, such as the 90th percentile and beyond.