Decomposition-Based Analysis of Queueing Networks

R. Sadre

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

14 Downloads (Pure)

Abstract

Model-based numerical analysis is an important branch of the model-based performance evaluation. Especially state-oriented 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 well-known 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 fixed-point 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 fixed-point 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 phase-type renewal processes. Over the last decade, traffic measurements have shown the presence of properties such as self-similarity and long-range dependency in network traffic. It has been shown that this can be explained by the heavy-tailedness of many of the involved distributions. We describe how hyper-exponential distributions, which are a special case of phase-type distributions, can be fitted to heavy-tail distributed measurement data. FiFiQueues' traffic descriptors are based on the first and second moment of the inter-arrival 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.
Original languageUndefined
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Haverkort, Boudewijn R.H.M., Supervisor
Award date10 Jan 2007
Place of PublicationEnschede
Publisher
Print ISBNs90-365-2444-X
Publication statusPublished - 10 Jan 2007

Keywords

  • EWI-11631
  • METIS-245888
  • IR-57651

Cite this

Sadre, R. (2007). Decomposition-Based Analysis of Queueing Networks. Enschede: Centre for Telematics and Information Technology (CTIT).
Sadre, R.. / Decomposition-Based Analysis of Queueing Networks. Enschede : Centre for Telematics and Information Technology (CTIT), 2007. 209 p.
@phdthesis{2d6b4b87a0544c428943717475d005f4,
title = "Decomposition-Based Analysis of Queueing Networks",
abstract = "Model-based numerical analysis is an important branch of the model-based performance evaluation. Especially state-oriented 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 well-known 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 fixed-point 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 fixed-point 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 phase-type renewal processes. Over the last decade, traffic measurements have shown the presence of properties such as self-similarity and long-range dependency in network traffic. It has been shown that this can be explained by the heavy-tailedness of many of the involved distributions. We describe how hyper-exponential distributions, which are a special case of phase-type distributions, can be fitted to heavy-tail distributed measurement data. FiFiQueues' traffic descriptors are based on the first and second moment of the inter-arrival 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.",
keywords = "EWI-11631, METIS-245888, IR-57651",
author = "R. Sadre",
year = "2007",
month = "1",
day = "10",
language = "Undefined",
isbn = "90-365-2444-X",
publisher = "Centre for Telematics and Information Technology (CTIT)",
address = "Netherlands",
school = "University of Twente",

}

Sadre, R 2007, 'Decomposition-Based Analysis of Queueing Networks', University of Twente, Enschede.

Decomposition-Based Analysis of Queueing Networks. / Sadre, R.

Enschede : Centre for Telematics and Information Technology (CTIT), 2007. 209 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

TY - THES

T1 - Decomposition-Based Analysis of Queueing Networks

AU - Sadre, R.

PY - 2007/1/10

Y1 - 2007/1/10

N2 - Model-based numerical analysis is an important branch of the model-based performance evaluation. Especially state-oriented 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 well-known 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 fixed-point 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 fixed-point 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 phase-type renewal processes. Over the last decade, traffic measurements have shown the presence of properties such as self-similarity and long-range dependency in network traffic. It has been shown that this can be explained by the heavy-tailedness of many of the involved distributions. We describe how hyper-exponential distributions, which are a special case of phase-type distributions, can be fitted to heavy-tail distributed measurement data. FiFiQueues' traffic descriptors are based on the first and second moment of the inter-arrival 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 - Model-based numerical analysis is an important branch of the model-based performance evaluation. Especially state-oriented 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 well-known 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 fixed-point 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 fixed-point 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 phase-type renewal processes. Over the last decade, traffic measurements have shown the presence of properties such as self-similarity and long-range dependency in network traffic. It has been shown that this can be explained by the heavy-tailedness of many of the involved distributions. We describe how hyper-exponential distributions, which are a special case of phase-type distributions, can be fitted to heavy-tail distributed measurement data. FiFiQueues' traffic descriptors are based on the first and second moment of the inter-arrival 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 - EWI-11631

KW - METIS-245888

KW - IR-57651

M3 - PhD Thesis - Research UT, graduation UT

SN - 90-365-2444-X

PB - Centre for Telematics and Information Technology (CTIT)

CY - Enschede

ER -

Sadre R. Decomposition-Based Analysis of Queueing Networks. Enschede: Centre for Telematics and Information Technology (CTIT), 2007. 209 p.