Fluid heuristics, Lyapunov bounds and efficient importance sampling for a heavy-tailed G/G/1 queue |
| |
Authors: | J Blanchet P Glynn J C Liu |
| |
Institution: | (1) Science Center, Harvard University, 7th Floor, 1 Oxford St., Cambridge, MA 02138, USA;(2) Terman Engineering Center, Stanford University, 3rd Floor, 380 Panama Way, Stanford, CA 94305-4026, USA |
| |
Abstract: | We develop a strongly efficient rare-event simulation algorithm for computing the tail of the steady-state waiting time in
a single server queue with regularly varying service times. Our algorithm is based on a state-dependent importance sampling
strategy that is constructed so as to be straightforward to implement. The construction of the algorithm and its asymptotic
optimality rely on a Lyapunov-type inequality that is used to bound the second moment of the estimator. The solution to the
Lyapunov inequality is constructed using fluid heuristics. Our approach takes advantage of the regenerative ratio formula
for the steady-state distribution—and does not use the first passage time representation that is particular to the delay in
the G/G/1 queue. Hence, the strategy has the potential to be applied in more general queueing models.
|
| |
Keywords: | State-dependent importance sampling Rare-event simulation Heavy-tails Fluid heuristics Lyapunov bounds Single-server queue Change-of-measure |
本文献已被 SpringerLink 等数据库收录! |
|