Statedependent Importance Sampling for a Slowdown Tandem Queue
Miretskiy, D.I. and Scheinhardt, W.R.W. and Mandjes, M.R.H. (2008) Statedependent Importance Sampling for a Slowdown Tandem Queue. [Report]

PDF
414kB 
Abstract:  In this paper we investigate an advanced variant of the classical (Jackson) tandem queue, viz. a twonode system with server slowdown. The slowdown mechanism has the primary objective to protect the downstream queue from frequent overflows, and it does so by reducing the service speed of the upstream queue as soon as the number of jobs in the downstream queue reaches some prespecified threshold. To assess the efficacy of such a policy, techniques are needed for evaluating overflow metrics of the second queue. We focus on the estimation of the probability of the following rare event: overflow in the downstream queue before exhausting the system, starting from any given state in the state space.
Due to the rarity of the event under consideration, naive, direct Monte Carlo simulation is often infeasible. We therefore rely on the application of importance sampling to obtain variance reduction. The principal contribution of this paper is that we construct an importance sampling scheme that is asymptotically efficient. In more detail, the paper addresses the following issues. (i) We rely on powerful heuristics to identify the exponential decay rate of the probability under consideration, and verify this result by applying samplepath large deviations techniques. (2) Immediately from these heuristics, we develop a proposal for a change of measure to be used in importance sampling. (3) We prove that the resulting algorithm is asymptotically efficient, which effectively means that the number of runs required to obtain an estimate with fixed precision grows subexponentially in the buffer size. We stress that our method to prove asymptotic efficiency is substantially shorter and more straightforward than those usually provided in the literature. Also our setting is more general than the situations analyzed so far, as we allow the process to start off at any state of the state space, and in addition we do not impose any conditions on the values of the arrival rate and service rates, as long as the underlying queueing system is stable. 
Item Type:  Report 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/64929 
Official URL:  http://www.math.utwente.nl/publications 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 251140