Queueing networks: Rare events and fast simulations

D.I. Miretskiy

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. 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.
Original languageEnglish
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Mandjes, M.R.H., Supervisor
  • Scheinhardt, Willem R.W., Advisor
  • Boucherie, Richardus J., Supervisor
Sponsors
Date of Award11 Nov 2009
Place of PublicationZutphen
Publisher
Print ISBNs978-90-365-2909-9
DOIs
StatePublished - 11 Nov 2009

Fingerprint

Trajectory
Heuristics
Simplicity
Combinatorics
Decay
Discontinuity
Methodology
Sampling
Replication

Keywords

  • Importance sampling
  • IR-68376
  • EWI-17145
  • Slowdown
  • METIS-264307
  • Multilevel splitting
  • Tandem queue
  • Rare event simulation

Cite this

Miretskiy, D. I. (2009). Queueing networks: Rare events and fast simulations Zutphen: Wöhrmann DOI: 10.3990/1.9789036529099
Miretskiy, D.I.. / Queueing networks : Rare events and fast simulations. Zutphen : Wöhrmann, 2009. 149 p.
@misc{0405cc5a2e25495da7da3de006e73163,
title = "Queueing networks: Rare events and fast simulations",
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. 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.",
keywords = "Importance sampling, IR-68376, EWI-17145, Slowdown, METIS-264307, Multilevel splitting, Tandem queue, Rare event simulation",
author = "D.I. Miretskiy",
note = "10.3990/1.9789036529099",
year = "2009",
month = "11",
doi = "10.3990/1.9789036529099",
isbn = "978-90-365-2909-9",
publisher = "Wöhrmann",
school = "University of Twente",

}

Miretskiy, DI 2009, 'Queueing networks: Rare events and fast simulations', University of Twente, Zutphen. DOI: 10.3990/1.9789036529099

Queueing networks : Rare events and fast simulations. / Miretskiy, D.I.

Zutphen : Wöhrmann, 2009. 149 p.

Research output: ScientificPhD Thesis - Research UT, graduation UT

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 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.

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 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.

KW - Importance sampling

KW - IR-68376

KW - EWI-17145

KW - Slowdown

KW - METIS-264307

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 - 978-90-365-2909-9

PB - Wöhrmann

ER -

Miretskiy DI. Queueing networks: Rare events and fast simulations. Zutphen: Wöhrmann, 2009. 149 p. Available from, DOI: 10.3990/1.9789036529099