QoS modelling and analysis with UML-statecharts: the StoCharts approach

ABSTRACT

The UML is an influential and widespread notation for high-level modelling of information processing systems. UML statechart diagrams are a graphical language to describe system behaviour. They consitute one of the most intensively-used formalisms comprised by the UML. However, statechart diagrams are lacking concepts for describing real-time, performance, dependability and quality of service (QoS) characteristics at a behavioural level.This note describes a QoS-oriented extension of UML statechart diagrams, called StoCharts. StoCharts enhance the basic statechart formalism with two distinguished features, both simple and easy to understand, yet powerful enough to model a sufficiently rich class of stochastic processes. This is illustrated by a selection of case studies performed using StoCharts. We review the main ingredients of StoCharts and survey tool support and case studies performed with the language, and place StoCharts in the context of other extensions of statechart diagrams.

REFERENCES

• 1: Marco Ajmone Marsan , Gianni Conte , Gianfranco Balbo, A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.93-122, May 1984 [doi>10.1145/190.191]
• 2: Rajeev Alur , David L. Dill, A theory of timed automata, Theoretical Computer Science, v.126 n.2, p.183-235, April 25, 1994 [doi>10.1016/0304-3975(94)90010-8]
• 3: C. Baier, B. R. Haverkort, H. Hermanns, and J.-P. Katoen. Model-checking algorithms for continuous-time Markov chains. IEEE Trans. on Softw. Eng., 29(6):524--541, 2003.
• 4: Christel Baier , Boudewijn R. Haverkort , Holger Hermanns , Joost-Pieter Katoen, Model checking meets performance evaluation, ACM SIGMETRICS Performance Evaluation Review, v.32 n.4, p.10-15, March 2005 [doi>10.1145/1059816.1059819]
• 5: S. Balsamo and M. Simeoni. On transforming UML models into performance models. In Workshop on Transformations in UML 2001, 6 p., http://ase.arc.nasa.gov/wtuml01/.
• 6: Simona Bernardi , Susanna Donatelli , José Merseguer, From UML sequence diagrams and statecharts to analysable petri net models, Proceedings of the 3rd international workshop on Software and performance, July 24-26, 2002, Rome, Italy [doi>10.1145/584369.584376]
• 7: H. Bohnenkamp, H. Hermanns, J.-P. Katoen, and R. Klaren. The MoDeST modeling tool and its implementation. LNCS 2794:116--133.
• 8: H. C. Bohnenkamp , H. Hermanns , R. Klaren , A. Mader , Y. S. Usenko, Synthesis and Stochastic Assessment of Schedules for Lacquer Production, Proceedings of the The Quantitative Evaluation of Systems, First International Conference on (QEST'04), p.28-37, September 27-30, 2004 [doi>10.1109/QEST.2004.42]
• 9: C. Cavenet, S. Gilmore, J. Hillston, and P. Stevens. Performance modelling with UML and stochastic process algebra. In UKPEW 2002, 12 p., 2002.
• 10: Cristian Constantinescu, Impact of Deep Submicron Technology on Dependability of VLSI Circuits, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.205-209, June 23-26, 2002
• 11: P. R. D'Argenio. Algebras and automata for timed and stochastic systems. PhD thesis, Universiteit Twente, Enschede, November 1999.
• 12: Pedro R. D'Argenio , Holger Hermanns , Joost-Pieter Katoen , Ric Klaren, MoDeST - A Modelling and Description Language for Stochastic Timed Systems, Proceedings of the Joint International Workshop on Process Algebra and Probabilistic Methods, Performance Modeling and Verification, p.87-104, September 12-14, 2001
• 13: Daniel D. Deavours , Graham Clark , Tod Courtney , David Daly , Salem Derisavi , Jay M. Doyle , William H. Sanders , Patrick G. Webster, The Möbius Framework and Its Implementation, IEEE Transactions on Software Engineering, v.28 n.10, p.956-969, October 2002 [doi>10.1109/TSE.2002.1041052]
• 14: F. Dehne, H. van de Zandschulp, and R. Wieringa. Toolkit for conceptual modeling (TCM). http://www.cs.utwente.nl/~tcm/.
• 15: Rik Eshuis , Roel Wieringa, Requirements-level semantics for UML statecharts, Fourth International Conference on Formal methods for open object-based distributed systems IV, p.121-140, September 2000, Stanford, California, United States
• 16: S. Gnesi, D. Latella, and M. Massink. A stochastic extension of a behavioural subset of UML statechart diagrams. In HASE 2000, 55--64. IEEE CS Press, 2000.
• 17: Norbert Götz , Ulrich Herzog , Michael Rettelbach, Multiprocessor and Distributed System Design: The Integration of Functional Specification and Performance Analysis Using Stochastic Process Algebras, Performance Evaluation of Computer and Communication Systems, Joint Tutorial Papers of Performance '93 and Sigmetrics '93, p.121-146, May 10-14, 1993
• 18: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 19: David Harel , Amnon Naamad, The STATEMATE semantics of statecharts, ACM Transactions on Software Engineering and Methodology (TOSEM), v.5 n.4, p.293-333, Oct. 1996 [doi>10.1145/235321.235322]
• 20: H. Hermanns, J.-P. Katoen, J. Meyer-Kayser, and M. Siegle. A tool for model-checking Markov chains. Intl. Journal on Softw. Tools for Techn. Transfer, 4(2):153--172, 2003.
• 21: Jane Hillston, A compositional approach to performance modelling, Cambridge University Press, New York, NY, 1996
• 22: G. Huszerl, I. Majzik, A. Pataricza, K. Kosmidis, and M. Dal Cin. Quantitative analysis of UML statechart models of dependable systems. The Computer Journal, 45(3):260--277, 2002.
• 23: D. N. Jansen. Probabilistic UML statecharts for specification and verification : a case study. In CSDUML 2002, Technical Report TUM-I0208, 121--131, TU Munich, 2002.
• 24: D. N. Jansen. Extensions of statecharts with probability, time, and stochastic timing. PhD thesis, Universiteit Twente, Inmarks, Bern, October 2003.
• 25: David N. Jansen , Holger Hermanns , Joost-Pieter Katoen, A Probabilistic Extension of UML Statecharts, Proceedings of the 7th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems: Co-sponsored by IFIP WG 2.2, p.355-374, September 09-12, 2002
• 26: D. N. Jansen, H. Hermanns, and J.-P. Katoen. A QoS-oriented extension of UML statecharts. LNCS 2863:76--91.
• 27: David N. Jansen , Holger Hermanns, Dependability Checking with StoCharts: Is Train Radio Reliable Enough for Trains?, Proceedings of the The Quantitative Evaluation of Systems, First International Conference on (QEST'04), p.250-259, September 27-30, 2004 [doi>10.1109/QEST.2004.15]
• 28: Peter J. B. King , Rob Pooley, Derivation of Petri Net Performance Models from UML Specifications of Communications Software, Proceedings of the 11th International Conference on Computer Performance Evaluation: Modelling Techniques and Tools, p.262-276, March 27-31, 2000
• 29: D. Latella, I. Majzik, and M. Massink. Automatic verification of a behavioural subset of UML statechart diagrams using the SPIN model-checker. Formal Aspects of Computing, 11(6):637--664, 1999.
• 30: Christoph Lindemann , Axel Thümmler , Alexander Klemm , Marco Lohmann , Oliver P. Waldhorst, Performance analysis of time-enhanced UML diagrams based on stochastic processes, Proceedings of the 3rd international workshop on Software and performance, July 24-26, 2002, Rome, Italy [doi>10.1145/584369.584375]
• 31: N. A. Lynch and M. R. Tuttle. An introduction to input/output automata. CWI Quarterly, pages 219--246, 1989.
• 32: P. Mitton and R. Holton. PEPA performability modelling using UML statecharts. In UKPEW 2000, 15 p., 2000.
• 33: OMG unified modeling language specification, version 1.5. Object Management Group, Needham, MA, 2003.
• 34: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 35: G. Reggio and R. J. Wieringa. Thirty one problems in the semantics of UML 1.3 dynamics. In OOPSLA 99 Workshop on Rigorous Modeling and Analysis with the UML, 1999.
• 36: James Rumbaugh , Ivar Jacobson , Grady Booch, The Unified Modeling Language reference manual, Addison-Wesley Longman Ltd., Essex, UK, 1998
• 37: Roberto Segala , Nancy Lynch, Probabilistic simulations for probabilistic processes, Nordic Journal of Computing, v.2 n.2, p.250-273, Summer 1995
• 38: G. S. Shedler. Regenerative stochastic simulation. Academic Press, Boston, MA, 1993.
• 39: W. J. Stewart. Introduction to the numerical solution of Markov chains. Princeton University Press, Princeton, NJ, 1994.
• 40: Mariëlle Stoelinga , Frits W. Vaandrager, Root Contention in IEEE 1394, Proceedings of the 5th International AMAST Workshop on Formal Methods for Real-Time and Probabilistic Systems, p.53-74, May 26-28, 1999
• 41: David Tennenhouse, Proactive computing, Communications of the ACM, v.43 n.5, p.43-50, May 2000 [doi>10.1145/332833.332837]
• 42: UML profile for modeling quality of service and fault tolerance characteristics and mechanisms. Object Management Group, Inc., Needham, MA, September 2004. http://www.omg.org/cgi-bin/doc?ptc/2004-09-01.
• 43: UML Profile for Schedulability, Performance, and Time Specification: OMG Adopted Specification. Object Management Group, Inc., Needham, MA, November 2002. http://www.omg.org/cgi-bin/doc?ptc/2002-03-02.
• 44: Håkan L. S. Younes , Reid G. Simmons, Probabilistic Verification of Discrete Event Systems Using Acceptance Sampling, Proceedings of the 14th International Conference on Computer Aided Verification, p.223-235, July 27-31, 2002

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: State diagrams

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Statistical methods
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: UML

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Algorithms, Languages