Search

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.

Efficient Simulation of a Tandem Queue with Tandem Jackson networks and more sophisticated variants have found widespread application in various domains. One such variant is the tandem queue with server slow-down, in which the server of the upstreamqueue reduces its service speed as soon as the downstream queue exceeds some prespecified threshold, to provide the downstream queue some sort of ‘protection’. This paper focuses on the overflow probabilities in the downstream queue. Owing to the Markov structure these can be solved numerically, but the resulting system of linear equations is usually large. An attractive alternative could be to resort to simulation, but this approach is cumbersome due to the rarity of the event under consideration. A powerful remedy is to use importance sampling, i.e. simulation under an alternative measure, where unbiasedness of the estimator is retrieved by weighing the observations by appropriate likelihood ratios. To find a good alternative measure, we first identify the most likely path to overflow. For the standard tandem queue (i.e. no slow-down) this path was known, but we develop an appealing novel heuristic which can also be applied to the model with slowdown. The knowledge of the most likely path is then used to devise importance sampling algorithms, both for the standard tandem system and for the system with slow-down. Our experiments indicate that the corresponding new measure is sometimes asymptotically optimal, and sometimes not. We systematically analyze the cases that may occur.

This article focuses on estimating rare events using multilevel splitting schemes. The event of interest is that a Markov process enters some rare set before another (“tabu”) set. It is known that in this setting a large deviations analysis is not always sufficient for constructing asymptotically efficient importance sampling schemes; additional modifications to the change of measure suggested by large deviations are needed. As an alternative, we design an asymptotically efficient multilevel splitting scheme that relies on the large deviations analysis only. This property makes it more flexible and easier to implement than corresponding importance sampling schemes.

This paper considers importance sampling as a tool for rare-event simulation. The focus is on estimating the probability of overflow in the downstream queue of a Jackson two-node tandem queue. It is known that in this setting 'traditional' state-independent importance-sampling distributions perform poorly. We therefore concentrate on developing a state-dependent change of measure that is provably asymptotically efficient. More specific contributions are the following. (i) We concentrate on the probability of the second queue exceeding a certain predefined threshold before the system empties. Importantly, we identify an asymptotically efficient importance-sampling distribution for any initial state of the system. (ii) The choice of the importance-sampling distribution is backed up by appealing heuristics that are rooted in large-deviations theory. (iii) Our method for proving asymptotic efficiency is substantially more straightforward than some that have been used earlier. Keywords: Rare event simulation, importance sampling, state-dependent change of measure, asymptotic optimality, tandem queue

We study how rare events happen in the standard two-node tandem Jackson queue and in a generalization, the socalled slow-down network, see [2]. In the latter model the service rate of the first server depends on the number of jobs in the second queue: the first server slows down if the amount of jobs in the second queue is above some threshold and returns to its normal speed when the number of jobs in the second queue is below the threshold. This property protects the second queue, which has a finite capacity B , from overflow. In fact this type of overflow is precisely the rare event we are interested in. More precisely, consider the probability of overflow in the second queue before the entire system becomes empty. The starting position of the two queues may be any state in which at least one job is present.

This article considers importance sampling as a tool for rare-event simulation. The focus is on estimating the probability of overflow in the downstream queue of a Jacksonian two-node tandem queue; it is known that in this setting “traditional” state-independent importance-sampling distributions perform poorly. We therefore concentrate on developing a state-dependent change of measure, that we prove to be asymptotically efficient. More specific contributions are the following. (i) We concentrate on the probability of the second queue exceeding a certain predefined threshold before the system empties. Importantly, we identify an asymptotically efficient importance-sampling distribution for any initial state of the system. (ii) The choice of the importance-sampling distribution is backed up by appealing heuristics that are rooted in large-deviations theory. (iii) The method for proving asymptotic efficiency relies on probabilistic arguments only. The article is concluded by simulation experiments that show a considerable speedup.