State-dependent importance sampling for a slowdown tandem queue

In this paper we investigate an advanced variant of the classical (Jackson) tandem queue, viz. a two-node system with server slowdown. By this mechanism, the service speed of the upstream queue is reduced as soon as the number of jobs in the downstream queue reaches some pre-specified threshold. We focus on the estimation of the probability of overflow in the downstream queue before the system becomes empty, starting from any given state in the state space. The principal contribution of this paper is that we construct importance sampling schemes to estimate these probabilities in case they are small; in particular: (1) We use powerful heuristics to identify the exponential decay rate of the probability under consideration, and verify this result by applying sample-path large deviations techniques. (2) Based on these heuristics we develop a change of measure to be used in importance sampling. (3) We prove that this scheme is asymptotically efficient, using a shorter and more straightforward method than usually provided in the literature. Unfortunately, this scheme is difficult to use in practice, therefore (4) we propose an algorithm that offers considerable computational advantage over the first scheme. For this scheme we provide a proof of asymptotic efficiency for certain parameter settings, as well as numerical results showing that the scheme works well for all parameters. Copyright Springer Science+Business Media, LLC 2011