This work 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 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, 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.
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 naive, 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.