Efficient Calculation of Rare Event Probabilities in Markovian Queueing Networks

Linar Mikeev; Werner Sandmann; Verena Wolf

5th International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Efficient Calculation of Rare Event Probabilities in Markovian Queueing Networks

Download478 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.4108/icst.valuetools.2011.245597,
    author={Linar Mikeev and Werner Sandmann and Verena Wolf},
    title={Efficient Calculation of Rare Event Probabilities in Markovian Queueing Networks},
    proceedings={5th International ICST Conference on Performance Evaluation Methodologies and Tools},
    publisher={ICST},
    proceedings_a={VALUETOOLS},
    year={2012},
    month={6},
    keywords={queueing networks markov chains rare events importance sampling transient analysis},
    doi={10.4108/icst.valuetools.2011.245597}
}

Linar Mikeev
Werner Sandmann
Verena Wolf
Year: 2012
Efficient Calculation of Rare Event Probabilities in Markovian Queueing Networks
VALUETOOLS
ICST
DOI: 10.4108/icst.valuetools.2011.245597

Linar Mikeev¹, Werner Sandmann², Verena Wolf¹^,*

1: Saarland University
2: Clausthal University of Technology

*Contact email: wolf@cs.uni-saarland.de

Abstract

We address the computation of rare event probabilities in Markovian queueing networks with huge or possibly even infinite state spaces. For this purpose, we incorporate ideas from importance sampling simulations into a non-simulative numerical method that approximates transient probabilities based on a dynamical truncation of the state space. A change of measure technique is applied in order to accomplish a guided state space exploration. Numerical results for three different example networks demonstrate the efficiency and accuracy of our method.

Keywords: queueing networks markov chains rare events importance sampling transient analysis

Published: 2012-06-26
Publisher: ICST

: http://dx.doi.org/10.4108/icst.valuetools.2011.245597