Jose Blanchet and Jing Dong. 2012. Rare-event simulation for multi-server queues in the Halfin-Whitt regime. SIGMETRICS Perform. Eval. Rev. 39, 4 (March 2012), 35. https://doi.org/10.1145/2185395.2185426

View Publication

Abstract

We consider a FCFS M/Hd/n queue which has a Poisson arrival process (M) and iid service times following a hyper-exponential distribution with d components (Hd). We develop rare-event simulation methodology to analyze large deviations for the queue length process in steady-state under the Halfin-Whitt regime. The key strategy consists of constructing two objects: I) a regenerative set A whose probability is bounded away from zero as n→∞, and II) a free process for which the most likely path to overflow is easy to handle. In particular, the free process is coupled with the original system outside the set A and it is not sensitive to boundary behavior. The successful application of the algorithm takes crucial advantage of the simulation and evaluation of a time-inhomogeneous Markov chain that is defined in terms of matrix exponential functions.

Authors
Jose Blanchet, Jing Dong
Publication date
2012/4/9
Journal
ACM SIGMETRICS Performance Evaluation Review
Volume
39
Issue
4
Pages
35-35
Publisher
ACM