Tail Quantile Estimation for Non-Preemptive Priority Queues

Motivated by applications in computing and telecommunication systems, we investigate the problem of estimating $p$-quantile of steady-state sojourn times in a single-server multi-class queueing system with non-preemptive priorities for $p$ close to 1. The main challenge in this problem lies in efficient sampling from the tail event. To address this issue, we develop a regenerative simulation algorithm with importance sampling. In addition, we establish a central limit theorem for the estimator to construct the confidence interval. Numerical experiments show that our algorithm outperforms benchmark simulation methods. Our result contributes to the literature on rare event simulation for queueing systems.

1 Introduction

In computing and telecommunication industries, service-level agreement (SLA) usually takes the form of a guarantee on the tail probability of response times, \begin{equation*} P(\text{response time} > \gamma) < 1-p.\end{equation*}