Decomposition-Based Analysis of Queueing Networks

R. Sadre

    Research output: ThesisPhD Thesis - Research UT, graduation UT

    17 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 Remigius Heinrich Maria, 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 UT

    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.