Abstract
Original language  Undefined 

Awarding Institution 

Supervisors/Advisors 

Award date  10 Jan 2007 
Place of Publication  Enschede 
Publisher  
Print ISBNs  903652444X 
Publication status  Published  10 Jan 2007 
Keywords
 EWI11631
 METIS245888
 IR57651
Cite this
}
DecompositionBased Analysis of Queueing Networks. / Sadre, R.
Enschede : Centre for Telematics and Information Technology (CTIT), 2007. 209 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT › Academic
TY  THES
T1  DecompositionBased Analysis of Queueing Networks
AU  Sadre, R.
PY  2007/1/10
Y1  2007/1/10
N2  Modelbased numerical analysis is an important branch of the modelbased performance evaluation. Especially stateoriented formalisms and methods based on Markovian processes, like stochastic Petri nets and Markov chains, have been successfully adopted because they are mathematically well understood and allow the intuitive modeling of many processes of the real world. However, these methods are sensitive to the wellknown phenomenon called state space explosion. One way to handle this problem is the decomposition approach. In this thesis, we present a decomposition framework for the analysis of a fairly general class of open and closed queueing networks. The decomposition is done at queueing station level, i.e., the queueing stations are independently analyzed. During the analysis, traffic descriptors are exchanged between the stations, representing the streams of jobs flowing between them. Networks with feedback are analyzed using a fixedpoint iteration. Based on the decomposition framework, we have developed an efficient analysis method called FiFiQueues. The method supports open queueing networks with infinite and finite capacity queues. We present the method and discuss its fixedpoint behavior, as well as various extensions to the original algorithm. We also show how the method can be applied in the efficient analysis of closed queueing networks. The service processes in FiFiQueues can be arbitrary phasetype renewal processes. Over the last decade, traffic measurements have shown the presence of properties such as selfsimilarity and longrange dependency in network traffic. It has been shown that this can be explained by the heavytailedness of many of the involved distributions. We describe how hyperexponential distributions, which are a special case of phasetype distributions, can be fitted to heavytail distributed measurement data. FiFiQueues' traffic descriptors are based on the first and second moment of the interarrival time and, hence, cannot account for correlations in the traffic streams. To approach this problem, we also introduce MAPs as traffic descriptors. Since a queueing network analysis based on MAP traffic descriptors suffers under the state space explosion problem, we present five different MAP reduction methods in order to decrease the effect of the state space explosion.
AB  Modelbased numerical analysis is an important branch of the modelbased performance evaluation. Especially stateoriented formalisms and methods based on Markovian processes, like stochastic Petri nets and Markov chains, have been successfully adopted because they are mathematically well understood and allow the intuitive modeling of many processes of the real world. However, these methods are sensitive to the wellknown phenomenon called state space explosion. One way to handle this problem is the decomposition approach. In this thesis, we present a decomposition framework for the analysis of a fairly general class of open and closed queueing networks. The decomposition is done at queueing station level, i.e., the queueing stations are independently analyzed. During the analysis, traffic descriptors are exchanged between the stations, representing the streams of jobs flowing between them. Networks with feedback are analyzed using a fixedpoint iteration. Based on the decomposition framework, we have developed an efficient analysis method called FiFiQueues. The method supports open queueing networks with infinite and finite capacity queues. We present the method and discuss its fixedpoint behavior, as well as various extensions to the original algorithm. We also show how the method can be applied in the efficient analysis of closed queueing networks. The service processes in FiFiQueues can be arbitrary phasetype renewal processes. Over the last decade, traffic measurements have shown the presence of properties such as selfsimilarity and longrange dependency in network traffic. It has been shown that this can be explained by the heavytailedness of many of the involved distributions. We describe how hyperexponential distributions, which are a special case of phasetype distributions, can be fitted to heavytail distributed measurement data. FiFiQueues' traffic descriptors are based on the first and second moment of the interarrival time and, hence, cannot account for correlations in the traffic streams. To approach this problem, we also introduce MAPs as traffic descriptors. Since a queueing network analysis based on MAP traffic descriptors suffers under the state space explosion problem, we present five different MAP reduction methods in order to decrease the effect of the state space explosion.
KW  EWI11631
KW  METIS245888
KW  IR57651
M3  PhD Thesis  Research UT, graduation UT
SN  903652444X
PB  Centre for Telematics and Information Technology (CTIT)
CY  Enschede
ER 