On Ultra-Sharp Queueing Bounds

We present a robust method to analyze a broad range of classical queueing models, e.g., the GI/G/1 queue with renewal arrivals, an AR/G/1 queue with alternating renewals (AR), as a special class of Semi-Markovian processes, and Markovian fluids queues. At the core of the method lies a standard change-of-measure argument to reverse the sign of the negative drift in the underlying random walks. Combined with a suitable representation of the overshoot, we obtain exact results in terms of series. Closed-form and computationally fast bounds follow by taking the series’ first terms, which are the dominant ones because of the positive drift under the new probability measure. The obtained bounds generalize the state-of-the-art class of martingale bounds and can be much sharper by orders of magnitude.