Queueing networks : rare events and fast simulations


Miretskiy, Denis (2009) Queueing networks : rare events and fast simulations. thesis.

open access
Abstract: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.
Item Type:Thesis
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:http://purl.utwente.nl/publications/68376
Official URL:https://doi.org/10.3990/1.9789036529099
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page