Difference between revisions of "Modeling Background"

From Mobius Wiki
Jump to: navigation, search
Line 34: Line 34:
 
Möbius takes an integrated multi-formalism, multi-solution approach; the goal was to build a tool in which each model formalism or solver was, to the extent possible, modular, in order to maximize potential interaction. A modular modeling tool is possible because many operations on models, such as composition (described later), state-space generation, and simulation are largely independent of the formalism being used to express the model.
 
Möbius takes an integrated multi-formalism, multi-solution approach; the goal was to build a tool in which each model formalism or solver was, to the extent possible, modular, in order to maximize potential interaction. A modular modeling tool is possible because many operations on models, such as composition (described later), state-space generation, and simulation are largely independent of the formalism being used to express the model.
  
−
This approach has several advantages. First, it allows for novel combinations of modeling techniques. For example, to the best of our knowledge, the Replicate/Join model composition approach of <ref>W. H. Sanders and J. F. Meyer. Reduced base model construction methods for stochastic activity networks. ''IEEE Journal on Selected Areas in Communications, special issue on Computer-Aided Modeling, Analysis, and Design of Communication Networks'', 9(1):25–36, January 1991.</ref> has been used exclusively with SANs. This exclusivity is artificial, and in the Möbius tool, Replicate/Join can be used with virtually any formalism that can produce a labeled transition system, such as PEPA<ref>G. Clark and W. H. Sanders. Implementing a stochastic process algebra within the Möbius modeling framework. In ''Process Algebra and Probabilistic Methods: Performance Modelling and Verification: Proc. of the Joint International Workshop, PAPM-PROBMIV 2001'', volume 2165 of ''Lecture Notes In Computer Science'', pages 200–215, Aachen, Germany, September 2001. Berlin: Springer.</ref>.
+
This approach has several advantages. First, it allows for novel combinations of modeling techniques. For example, to the best of our knowledge, the Replicate/Join model composition approach of <ref name=Sanders:SAIC:91>W. H. Sanders and J. F. Meyer. Reduced base model construction methods for stochastic activity networks. ''IEEE Journal on Selected Areas in Communications, special issue on Computer-Aided Modeling, Analysis, and Design of Communication Networks'', 9(1):25–36, January 1991.</ref> has been used exclusively with SANs. This exclusivity is artificial, and in the Möbius tool, Replicate/Join can be used with virtually any formalism that can produce a labeled transition system, such as PEPA<ref>G. Clark and W. H. Sanders. Implementing a stochastic process algebra within the Möbius modeling framework. In ''Process Algebra and Probabilistic Methods: Performance Modelling and Verification: Proc. of the Joint International Workshop, PAPM-PROBMIV 2001'', volume 2165 of ''Lecture Notes In Computer Science'', pages 200–215, Aachen, Germany, September 2001. Berlin: Springer.</ref>.
  
 
The ability to add new components benefits researchers and users alike. Researchers can add a new component to the tool and expect it to be able to interact immediately with other components. Additionally, researchers have access to the work of others, and are able to extend and compare techniques. Users benefit by having access to the most recent developments in conjunction with previously existing techniques. They also benefit from having a modular, “toolbox” approach that allows them to choose the most appropriate tool or tools for the job.
 
The ability to add new components benefits researchers and users alike. Researchers can add a new component to the tool and expect it to be able to interact immediately with other components. Additionally, researchers have access to the work of others, and are able to extend and compare techniques. Users benefit by having access to the most recent developments in conjunction with previously existing techniques. They also benefit from having a modular, “toolbox” approach that allows them to choose the most appropriate tool or tools for the job.
Line 49: Line 49:
 
To define the framework, it is necessary to identify and abstract the common concepts found in most formalisms. It is also necessary to generalize the process of building and categorizing models. The model’s construction process has been divided into several steps. Each step in the process generates a new type of model. The illustration shown in Figure 1.1 highlights the various model types and other
 
To define the framework, it is necessary to identify and abstract the common concepts found in most formalisms. It is also necessary to generalize the process of building and categorizing models. The model’s construction process has been divided into several steps. Each step in the process generates a new type of model. The illustration shown in Figure 1.1 highlights the various model types and other
 
components within the Möbius framework.
 
components within the Möbius framework.
 +
 +
 +
[[Image:Ct.png|center|275px|Figure 1.1: Möbius framework components.]]
 +
<br/>
 +
<center>Figure 1.1: Möbius framework components.</center>
 +
 +
 +
The first step in the model construction process is to generate a model using some formalism. The most basic model in the framework is called an ''atomic model'', and is made up of state variables and actions. State variables (for example, places in the various stochastic extensions to Petri nets, or queues in queuing networks) hold state information about a model, while actions (such as transitions in SPNs or servers in queuing networks) are the mechanism for changing model state.
 +
 +
If the model being constructed is intended to be part of a larger model, then the next step is to ''compose'' it with other models (i.e., atomic or composed models) to form a larger model. This is sometimes used as a convenient technique to make the model modular and easier to construct; at other times, the ways that models are composed can lead to efficiencies in the solution process. Examples include the Replicate/Join composition formalism<ref name=Sanders:SAIC:91 />, in which symmetries may be detected and state lumping may be performed. Although a composed model is a single model with its own state space, it is not a “flat” model. It is hierarchically built from submodels, which largely preserve their formalism-specific characteristics so that the composed model does not destroy the structural properties of the submodels. Note that the compositional techniques do not depend on the particular formalism of the atomic models that are being composed.
 +
 +
After a composed model is created, the next step is to specify some measures of interest on the model using some reward specification formalism, e.g., that is described in <ref>W. H. Sanders and J. F. Meyer. A unified approach for specifying measures of performance, dependability, and performability. In A. Avizienis, J. Kopetz, and J. Laprie, editors, ''Dependable Computing for Critical Applications'', volume 4 of ''Dependable Computing and Fault-Tolerant Systems'', pages 215–237. Heidelberg: Springer-Verlag, 1991.</ref>. The Möbius tool captures this pattern by having a separate model type, called ''reward models'', that augments composed models with reward variables.
 +
  
  

Revision as of 22:34, 18 February 2014

Möbius Tool

Motivation

Performance and dependability modeling is an integral part of the design process of many computer and communication systems. A variety of techniques have been developed to address different issues of modeling. For example, combinatorial models were developed to assess reliability and availability under strong independence assumptions; queuing networks were developed to assess system performance; and Markov process-based approaches have become popular for evaluating performance with synchronization or dependability without independence assumptions. Finally, simulation has been used extensively when other methods fail.

As techniques for solving models advanced, formalisms (or formal languages for expressing models) were also developed. Each formalism has its own merits. Some formalisms afford very efficient solution methods; for example, BCMP[1] queuing networks admit product-form solutions, while superposed generalized stochastic Petri nets (SGSPNs)[2] afford Kronecker-based solution methods, and colored GSPNs (CGSPNs)[3] yield state-space reductions. Other formalisms, such as SPNs[4] and SPAs[5], provide a simple elegance in their modeling primitives, while a number of extensions, such as stochastic activity networks (SANs)[6], were developed for compactly expressing complex behaviors.

Along with formalisms, tools have been developed. A tool is generally built around a single formalism and one or more solution techniques, with simulation sometimes available as a second solution method. [7] lists a number of such tools, such as DyQN-Tool+[8], which uses dynamic queuing networks as its high-level formalism; GreatSPN[9], which is based on GSPNs[10]; UltraSAN[11], which is based on SANs[6]; SPNP[12], which is based on stochastic reward networks[13]; and TANGRAM-II[14], which is an object- and message-based formalism for evaluating computer and communication systems. While all of these tools are useful within the domains for which they were intended, they are limited in that all parts of a model must be built in the single formalism that is supported by the tool. Thus, it is difficult to model systems that cross different domains and would benefit from multiple modeling techniques.

Möbius takes an integrated multi-formalism, multi-solution approach; the goal was to build a tool in which each model formalism or solver was, to the extent possible, modular, in order to maximize potential interaction. A modular modeling tool is possible because many operations on models, such as composition (described later), state-space generation, and simulation are largely independent of the formalism being used to express the model.

This approach has several advantages. First, it allows for novel combinations of modeling techniques. For example, to the best of our knowledge, the Replicate/Join model composition approach of [15] has been used exclusively with SANs. This exclusivity is artificial, and in the Möbius tool, Replicate/Join can be used with virtually any formalism that can produce a labeled transition system, such as PEPA[16].

The ability to add new components benefits researchers and users alike. Researchers can add a new component to the tool and expect it to be able to interact immediately with other components. Additionally, researchers have access to the work of others, and are able to extend and compare techniques. Users benefit by having access to the most recent developments in conjunction with previously existing techniques. They also benefit from having a modular, “toolbox” approach that allows them to choose the most appropriate tool or tools for the job.


Möbius Overview

The Möbius tool is an environment for supporting multiple modeling formalisms1. For a formalism to be compatible with Möbius, the developer must be able to translate a model built in his/her formalism into an equivalent model that uses Möbius components. Since models are constructed in specific formalisms, the expressive advantages of the particular formalisms are preserved. Because all models are transformed into Möbius components, all models and solution techniques in Möbius with compatible properties are able to interact with each other.

1 Technically speaking, the given definition is the definition of the Möbius framework, which is described in detail in [17]. However, for the sake of simplicity, we use the terms Möbius tool and Möbius framework interchangeably.
Framework components

To define the framework, it is necessary to identify and abstract the common concepts found in most formalisms. It is also necessary to generalize the process of building and categorizing models. The model’s construction process has been divided into several steps. Each step in the process generates a new type of model. The illustration shown in Figure 1.1 highlights the various model types and other components within the Möbius framework.


Figure 1.1: Möbius framework components.


Figure 1.1: Möbius framework components.


The first step in the model construction process is to generate a model using some formalism. The most basic model in the framework is called an atomic model, and is made up of state variables and actions. State variables (for example, places in the various stochastic extensions to Petri nets, or queues in queuing networks) hold state information about a model, while actions (such as transitions in SPNs or servers in queuing networks) are the mechanism for changing model state.

If the model being constructed is intended to be part of a larger model, then the next step is to compose it with other models (i.e., atomic or composed models) to form a larger model. This is sometimes used as a convenient technique to make the model modular and easier to construct; at other times, the ways that models are composed can lead to efficiencies in the solution process. Examples include the Replicate/Join composition formalism[15], in which symmetries may be detected and state lumping may be performed. Although a composed model is a single model with its own state space, it is not a “flat” model. It is hierarchically built from submodels, which largely preserve their formalism-specific characteristics so that the composed model does not destroy the structural properties of the submodels. Note that the compositional techniques do not depend on the particular formalism of the atomic models that are being composed.

After a composed model is created, the next step is to specify some measures of interest on the model using some reward specification formalism, e.g., that is described in [18]. The Möbius tool captures this pattern by having a separate model type, called reward models, that augments composed models with reward variables.



References

  1. ↑ F. Baskett, K. M. Chandy, R. R. Muntz, and F. G. Palacios. Open, closed, and mixed networks of queues with different classes of customers. Journal of the Association for Computing Machinery, 22(2):248–260, April 1975.
  2. ↑ S. Donatelli. Superposed generalized stochastic Petri nets: Definition and efficient solution. In R. Valette, editor, Application and Theory of Petri Nets 1994, LNCS 815 (Proc. 15th International Conference on Application and Theory of Petri Nets, Zaragoza, Spain), pages 258–277. Springer-Verlag, June 1994.
  3. ↑ G. Chiola, G. Bruno, and T. Demaria. Introducing a color formalism into generalized stochastic Petri nets. In Proc. 9th European Workshop on the Application and Theory of Petri Nets, pages 202–215, Venice, Italy, June 1988.
  4. ↑ M. K. Molloy. Performance analysis using stochastic Petri nets. IEEE Trans. on Comp., 31:913–917, September 1982.
  5. ↑ J. Hillston. A Compositional Approach to Performance Modelling. Cambridge University Press, Cambridge, 1996.
  6. ↑ 6.0 6.1 J. F. Meyer, A. Movaghar, and W. H. Sanders. Stochastic activity networks: Structure, behavior, and application. In Proc. International Workshop on Timed Petri Nets, pages 106–115, Torino, Italy, July 1985.
  7. ↑ W. H. Sanders. Integrated frameworks for multi-level and multi-formalism modeling. In Proceedings of the 8th International Workshop on Petri Nets and Performance Models, pages 2–9, Zaragoza, Spain, September 1999.
  8. ↑ B. R. Haverkort. Performability evaluation of fault-tolerant computer systems using DyQN-Tool+. International Journal of Reliability, Quality, and Safety Engineering, 2(4):383–404, 1995.
  9. ↑ G. Chiola, G. Franceschinis, R. Gaeta, and M. Ribaudo. GreatSPN 1.7: Graphical Editor and Analyzer for Timed and Stochastic Petri Nets. Performance Evaluation, 24(1–2):47–68, November 1995.
  10. ↑ M. Ajmone Marsan, G. Balbo, and G. Conte. A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems. ACM Transactions on Computer Systems, 2:93–122, May 1984.
  11. ↑ W. H. Sanders, W. D. Obal II, M. A. Qureshi, and F. K. Widjanarko. The UltraSAN modeling environment. Performance Evaluation, 24(1):89–115, October 1995.
  12. ↑ G. Ciardo and K. S. Trivedi. SPNP: The stochastic Petri net package (version 3.1). In Proceedings of the 1st International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS’93), pages 390–391, San Diego, California, January 1993.
  13. ↑ G. Ciardo, A. Blakemore, P. F. J. Chimento, J. K. Muppala, and K. S. Trivedi. Automated generation and analysis of Markov reward models using stochastic reward nets. In C. Meyer and R. J. Plemmons, editors, Linear Algebra, Markov Chains, and Queueing Models, pages 141–191. Heidelberg: Springer-Verlag, 1993.
  14. ↑ R. M. L. R. Carmo, L. R. de Carvalho, E. de Souza e Silva, M. C. Diniz, and R. R. Muntz. TANGRAM-II. In Raymond Marie, Brigitte Plateau, Maria Calzarossa, and Gerardo Rubino, editors, Computer Performance Evaluation: Modelling Techniques and Tools: Proceedings of the 9th International Conference, pages 6–18, St. Malo, France, June 1997.
  15. ↑ 15.0 15.1 W. H. Sanders and J. F. Meyer. Reduced base model construction methods for stochastic activity networks. IEEE Journal on Selected Areas in Communications, special issue on Computer-Aided Modeling, Analysis, and Design of Communication Networks, 9(1):25–36, January 1991.
  16. ↑ G. Clark and W. H. Sanders. Implementing a stochastic process algebra within the Möbius modeling framework. In Process Algebra and Probabilistic Methods: Performance Modelling and Verification: Proc. of the Joint International Workshop, PAPM-PROBMIV 2001, volume 2165 of Lecture Notes In Computer Science, pages 200–215, Aachen, Germany, September 2001. Berlin: Springer.
  17. ↑ D. D. Deavours, G. Clark, T. Courtney, D. Daly, S. Derisavi, J. M. Doyle, W. H. Sanders, and P. G. Webster. The Möbius framework and its implementation. IEEE Transactions on Software Engineering, 28(10):956–969, October 2002.
  18. ↑ W. H. Sanders and J. F. Meyer. A unified approach for specifying measures of performance, dependability, and performability. In A. Avizienis, J. Kopetz, and J. Laprie, editors, Dependable Computing for Critical Applications, volume 4 of Dependable Computing and Fault-Tolerant Systems, pages 215–237. Heidelberg: Springer-Verlag, 1991.

Möbius Tool[edit]

Motivation[edit]

Performance and dependability modeling is an integral part of the design process of many computer and communication systems. A variety of techniques have been developed to address different issues of modeling. For example, combinatorial models were developed to assess reliability and availability under strong independence assumptions; queuing networks were developed to assess system performance; and Markov process-based approaches have become popular for evaluating performance with synchronization or dependability without independence assumptions. Finally, simulation has been used extensively when other methods fail.

As techniques for solving models advanced, formalisms (or formal languages for expressing models) were also developed. Each formalism has its own merits. Some formalisms afford very efficient solution methods; for example, BCMP[1] queuing networks admit product-form solutions, while superposed generalized stochastic Petri nets (SGSPNs)[2] afford Kronecker-based solution methods, and colored GSPNs (CGSPNs)[3] yield state-space reductions. Other formalisms, such as SPNs[4] and SPAs[5], provide a simple elegance in their modeling primitives, while a number of extensions, such as stochastic activity networks (SANs)[6], were developed for compactly expressing complex behaviors.

Along with formalisms, tools have been developed. A tool is generally built around a single formalism and one or more solution techniques, with simulation sometimes available as a second solution method. [7] lists a number of such tools, such as DyQN-Tool+[8], which uses dynamic queuing networks as its high-level formalism; GreatSPN[9], which is based on GSPNs[10]; UltraSAN[11], which is based on SANs[6]; SPNP[12], which is based on stochastic reward networks[13]; and TANGRAM-II[14], which is an object- and message-based formalism for evaluating computer and communication systems. While all of these tools are useful within the domains for which they were intended, they are limited in that all parts of a model must be built in the single formalism that is supported by the tool. Thus, it is difficult to model systems that cross different domains and would benefit from multiple modeling techniques.

Möbius takes an integrated multi-formalism, multi-solution approach; the goal was to build a tool in which each model formalism or solver was, to the extent possible, modular, in order to maximize potential interaction. A modular modeling tool is possible because many operations on models, such as composition (described later), state-space generation, and simulation are largely independent of the formalism being used to express the model.

This approach has several advantages. First, it allows for novel combinations of modeling techniques. For example, to the best of our knowledge, the Replicate/Join model composition approach of [15] has been used exclusively with SANs. This exclusivity is artificial, and in the Möbius tool, Replicate/Join can be used with virtually any formalism that can produce a labeled transition system, such as PEPA[16].

The ability to add new components benefits researchers and users alike. Researchers can add a new component to the tool and expect it to be able to interact immediately with other components. Additionally, researchers have access to the work of others, and are able to extend and compare techniques. Users benefit by having access to the most recent developments in conjunction with previously existing techniques. They also benefit from having a modular, “toolbox” approach that allows them to choose the most appropriate tool or tools for the job.


Möbius Overview[edit]

The Möbius tool is an environment for supporting multiple modeling formalisms1. For a formalism to be compatible with Möbius, the developer must be able to translate a model built in his/her formalism into an equivalent model that uses Möbius components. Since models are constructed in specific formalisms, the expressive advantages of the particular formalisms are preserved. Because all models are transformed into Möbius components, all models and solution techniques in Möbius with compatible properties are able to interact with each other.

1 Technically speaking, the given definition is the definition of the Möbius framework, which is described in detail in [17]. However, for the sake of simplicity, we use the terms Möbius tool and Möbius framework interchangeably.
Framework components[edit]

To define the framework, it is necessary to identify and abstract the common concepts found in most formalisms. It is also necessary to generalize the process of building and categorizing models. The model’s construction process has been divided into several steps. Each step in the process generates a new type of model. The illustration shown in Figure 1.1 highlights the various model types and other components within the Möbius framework.


References[edit]

  1. ↑ F. Baskett, K. M. Chandy, R. R. Muntz, and F. G. Palacios. Open, closed, and mixed networks of queues with different classes of customers. Journal of the Association for Computing Machinery, 22(2):248–260, April 1975.
  2. ↑ S. Donatelli. Superposed generalized stochastic Petri nets: Definition and efficient solution. In R. Valette, editor, Application and Theory of Petri Nets 1994, LNCS 815 (Proc. 15th International Conference on Application and Theory of Petri Nets, Zaragoza, Spain), pages 258–277. Springer-Verlag, June 1994.
  3. ↑ G. Chiola, G. Bruno, and T. Demaria. Introducing a color formalism into generalized stochastic Petri nets. In Proc. 9th European Workshop on the Application and Theory of Petri Nets, pages 202–215, Venice, Italy, June 1988.
  4. ↑ M. K. Molloy. Performance analysis using stochastic Petri nets. IEEE Trans. on Comp., 31:913–917, September 1982.
  5. ↑ J. Hillston. A Compositional Approach to Performance Modelling. Cambridge University Press, Cambridge, 1996.
  6. ↑ 6.0 6.1 J. F. Meyer, A. Movaghar, and W. H. Sanders. Stochastic activity networks: Structure, behavior, and application. In Proc. International Workshop on Timed Petri Nets, pages 106–115, Torino, Italy, July 1985.
  7. ↑ W. H. Sanders. Integrated frameworks for multi-level and multi-formalism modeling. In Proceedings of the 8th International Workshop on Petri Nets and Performance Models, pages 2–9, Zaragoza, Spain, September 1999.
  8. ↑ B. R. Haverkort. Performability evaluation of fault-tolerant computer systems using DyQN-Tool+. International Journal of Reliability, Quality, and Safety Engineering, 2(4):383–404, 1995.
  9. ↑ G. Chiola, G. Franceschinis, R. Gaeta, and M. Ribaudo. GreatSPN 1.7: Graphical Editor and Analyzer for Timed and Stochastic Petri Nets. Performance Evaluation, 24(1–2):47–68, November 1995.
  10. ↑ M. Ajmone Marsan, G. Balbo, and G. Conte. A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems. ACM Transactions on Computer Systems, 2:93–122, May 1984.
  11. ↑ W. H. Sanders, W. D. Obal II, M. A. Qureshi, and F. K. Widjanarko. The UltraSAN modeling environment. Performance Evaluation, 24(1):89–115, October 1995.
  12. ↑ G. Ciardo and K. S. Trivedi. SPNP: The stochastic Petri net package (version 3.1). In Proceedings of the 1st International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS’93), pages 390–391, San Diego, California, January 1993.
  13. ↑ G. Ciardo, A. Blakemore, P. F. J. Chimento, J. K. Muppala, and K. S. Trivedi. Automated generation and analysis of Markov reward models using stochastic reward nets. In C. Meyer and R. J. Plemmons, editors, Linear Algebra, Markov Chains, and Queueing Models, pages 141–191. Heidelberg: Springer-Verlag, 1993.
  14. ↑ R. M. L. R. Carmo, L. R. de Carvalho, E. de Souza e Silva, M. C. Diniz, and R. R. Muntz. TANGRAM-II. In Raymond Marie, Brigitte Plateau, Maria Calzarossa, and Gerardo Rubino, editors, Computer Performance Evaluation: Modelling Techniques and Tools: Proceedings of the 9th International Conference, pages 6–18, St. Malo, France, June 1997.
  15. ↑ W. H. Sanders and J. F. Meyer. Reduced base model construction methods for stochastic activity networks. IEEE Journal on Selected Areas in Communications, special issue on Computer-Aided Modeling, Analysis, and Design of Communication Networks, 9(1):25–36, January 1991.
  16. ↑ G. Clark and W. H. Sanders. Implementing a stochastic process algebra within the Möbius modeling framework. In Process Algebra and Probabilistic Methods: Performance Modelling and Verification: Proc. of the Joint International Workshop, PAPM-PROBMIV 2001, volume 2165 of Lecture Notes In Computer Science, pages 200–215, Aachen, Germany, September 2001. Berlin: Springer.
  17. ↑ D. D. Deavours, G. Clark, T. Courtney, D. Daly, S. Derisavi, J. M. Doyle, W. H. Sanders, and P. G. Webster. The Möbius framework and its implementation. IEEE Transactions on Software Engineering, 28(10):956–969, October 2002.
Retrieved from "https://www.mobius.illinois.edu/wiki/index.php?title=Modeling_Background&oldid=39"