Modeling Background

From Mobius Wiki
Revision as of 22:04, 18 February 2014 by Duyenle2 (talk | contribs)
Jump to: navigation, search

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.


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. ↑ 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.

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=37"