Difference between revisions of "Modeling Background"

Revision as of 22:41, 19 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 formalisms¹. 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.

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

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.

The next step is typically to apply some solver to compute a solution to the reward model. We call any mechanism that calculates the solution to reward variables a solver. The calculation method could be exact, approximate, or statistical. Consequently, a solver may operate on a model independent of the formalism in which the model was constructed, so long as the model has the properties necessary for the solver.

The computed solution to a reward variable is called a result. Since the reward variable is a random variable, the result is expressed as some characteristic of a random variable. This may be, for example, the mean, variance, or distribution of the reward variable. The result may also include any solver-specific information that relates to the solution, such as any errors, the stopping criterion used, or the confidence interval. A solution calculated in this way may be the final desired measure, or it may be an intermediate step in further computation. If a result is intended for further computation, then the result may capture the interaction among multiple reward models that together form a connected model.

Tool description

The Möbius tool ensures that all formalisms translate model components into framework components through the use of the abstract functional interface (AFI)^[19]. The AFI provides the common interface between model formalisms and solvers that allows formalism-to-formalism and formalism-to-solver interactions. It uses abstract classes to implement Möbius framework components. The AFI is built from three main base classes: one for state variables, one for actions, and one that defines overall atomic model behavior. Each of these classes defines an interface used by the Möbius tool when building composed models, specifying reward variables, and solving models.

The various components of a model formalism must be presented as classes derived from the Möbius AFI classes in order to be implemented in the Möbius tool. Other model formalisms and model solvers in the tool are then able to interact with the new formalism by accessing its components through the Möbius abstract class interfaces.

The main user interface for the Möbius tool presents a series of editors that are classified according to model type. Each formalism or solver supported by Möbius has a corresponding editor in the main interface. These editors are used to construct and specify the model, possibly performing some formalism-specific analysis and property discovery, and to define the parameters for the solution techniques. The tool dynamically loads each formalism-specific editor from a java archive (jar file) at startup. This design allows new formalisms and their editors to be incorporated into the tool without modification or recompilation of the existing code, thus supporting the extensibility of the Möbius tool.

Models can be solved either analytically/numerically or by simulation. From each model, C++ source code is generated and compiled, and the object files are packaged to form a library archive. These libraries are linked together along with the tool’s base libraries to form the executable for the solver. The executable is run to generate the results. The base libraries implement the components of the particular model formalism, the AFI, and the solver algorithms. The organization of Möbius components to support this model construction procedure is shown in Figure 1.2.

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.
19. ↑ J. M. Doyle. Abstract model specification using the Möbius modeling tool. Master’s thesis, University of Illinois at Urbana-Champaign, January 2000.

Contents

• 1 Möbius Tool
  • 1.1 Motivation
  • 1.2 Möbius Overview
    • 1.2.1 Framework components
• 2 References

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 formalisms¹. 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.

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

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[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. ↑ ^{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.