Abstract
Original language  English 

Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  11 Nov 2009 
Place of Publication  Zutphen 
Publisher  
Print ISBNs  9789036529099 
DOIs  
Publication status  Published  11 Nov 2009 
Fingerprint
Keywords
 Importance sampling
 IR68376
 EWI17145
 Slowdown
 METIS264307
 Multilevel splitting
 Tandem queue
 Rare event simulation
Cite this
}
Queueing networks : Rare events and fast simulations. / Miretskiy, D.I.
Zutphen : Wöhrmann, 2009. 149 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT › Academic
TY  THES
T1  Queueing networks
T2  Rare events and fast simulations
AU  Miretskiy, D.I.
N1  10.3990/1.9789036529099
PY  2009/11/11
Y1  2009/11/11
N2  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 twonode tandem network. We consider the Jackson network case, as well as a generalization, the socalled 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 subexponentially when the probability of interest decays exponentially. We present several importance sampling schemes based on the large deviations results. We begin with naıve, stateindependent algorithms and end up with a family of simple and efficient statedependent 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 stateindependent 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 statedependent 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 statedependent, 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 statedependent 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 twonode 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 stateindependent 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.
AB  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 twonode tandem network. We consider the Jackson network case, as well as a generalization, the socalled 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 subexponentially when the probability of interest decays exponentially. We present several importance sampling schemes based on the large deviations results. We begin with naıve, stateindependent algorithms and end up with a family of simple and efficient statedependent 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 stateindependent 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 statedependent 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 statedependent, 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 statedependent 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 twonode 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 stateindependent 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.
KW  Importance sampling
KW  IR68376
KW  EWI17145
KW  Slowdown
KW  METIS264307
KW  Multilevel splitting
KW  Tandem queue
KW  Rare event simulation
U2  10.3990/1.9789036529099
DO  10.3990/1.9789036529099
M3  PhD Thesis  Research UT, graduation UT
SN  9789036529099
PB  Wöhrmann
CY  Zutphen
ER 