Queueing networks: Rare events and fast simulations

This monograph focuses on rare events. Even though they are extremely unlikely, they can still occur and then could have significant consequences. We mainly consider rare events in queueing networks. More precisely, we are interested in the probability of collecting some large number of jobs in the downstream queue of a two-node tandem network. We consider the Jackson network case, as well as a generalization, the so-called slowdown network. In practice these models can be used to model overflows in telecommunication networks. We chose these networks as a first step in developing a methodology that can be extended to more general networks. We investigate rare events from two different sides. On the one hand we are interested in the nature of the event, i.e., how the event ‘builds up’. At first we identify the structure of a specific path to overflow, which plays the role of our candidate for the most probable trajectory to overflow. We use some simple, but powerful large deviations based heuristics to this end. The shape of the trajectory crucially depends on both the starting state and the system parameters. We then provide a rigorous proof that this trajectory is indeed the most probable path to overflow. Thus our method combines simplicity (as it is easy to identify) and precision (as it is backed up by rigorous mathematical support). On the other hand our ultimate goal is to design accurate and efficient techniques to estimate the probability of our interest; in particular we aim for techniques that are asymptotically efficient, which effectively means that the number of replications needed to obtain an estimator with predetermined relative error grows sub-exponentially when the probability of interest decays exponentially. We present several importance sampling schemes based on the large deviations results. We begin with naıve, state-independent algorithms and end up with a family of simple and efficient state-dependent schemes. We also develop a multilevel splitting scheme, which turns out to be efficient for a wider class of processes. Strengths and weaknesses of the importance sampling schemes and multilevel splitting schemes are also discussed in this work. We start in Chapter 2 by identifying the most likely path to overflow. Here we develop a family of state-independent importance sampling schemes that are mimicking the most probable path ‘on average’, i.e., without any adaptation. These schemes are very simple to implement. However, in general they are not asymptotically efficient. In Chapter 3 and Chapter 4 we focus on the development of state-dependent importance sampling schemes for these two networks. We generalize the procedure described in Chapter 2 to identify the most likely path to overflow starting from any state. Based on this we design a family of importance sampling schemes for any initial state and prove its asymptotic efficiency. These schemes, in contrast to the ones from Chapter 2, are state-dependent, i.e., they require the recalculation of a new measure after each transition. We stress that the discontinuity of the measure around the slowdown threshold was an additional complication in the analysis of the schemes in Chapter 4. These asymptotically efficient schemes have a drawback, namely that the computational efforts required to determine the importance sampling algorithm are excessively large. In the following two chapters we reduce the complexity of the schemes while retaining their efficiency. Thus, in Chapter 5 and Chapter 6 we design a family of simpler state-dependent important sampling schemes based on the results of the previous two chapters. The main idea is to reduce dependence of the new measure on the current state of the process without losing asymptotic efficiency of the schemes. As a result we have a family of simplified schemes which are asymptotically efficient for all parameter values for the two-node Jackson network. For the slowdown model, the same holds for the major part of starting states, while for the rest of the starting states we proved efficiency under some mild condition. The accuracy of these schemes is comparable to those from Chapter 3 and Chapter 4. At the same time they are almost as easy to implement as the state-independent schemes in Chapter 2. Chapter 7 is dedicated to the multilevel splitting method. Here we design a family of asymptotically efficient multilevel splitting schemes for a rather broad class of models, which includes both networks of our interest. The proof of asymptotic efficiency relies on some elementary combinatorics and a number of simple facts from the theory of branching processes. Applying the proposed scheme to both networks of our interest, our numerical findings show high accuracy and time efficiency, comparable to what we obtained via importance sampling.