Saarland University (SAARBRÜCKEN, GERMANY)
Albert-Ludwigs-University (FREIBURG, GERMANY)
OFFIS (OLDENBURG, GERMANY)
Interactive Markov Chain
uniform Continuous Time Markov Decision Process
CADP (Construction and Analysis of Distributed Processes)
up to 1,016,400 states and 13,521,376 transitions.
This case study describes the compositional performability evaluation
of the ETCS (European Train Control System) which allows high speed
trains to follow each other at close distances. To guarantee safety,
each train periodically reports its position to trackside control
centers that respond by delivering "movement authorities" (i.e., the
right to move on). The communication infrastructure used is GSM-based
and hence error-prone and subject to failures; thus even critical
messages might be delayed.
Performability analysis of the ETCS proceeds in several steps, combining symbolic and explicit representations. First, the ETCS is modeled as a statechart in Statemate, using dedicated labels to identify delayed transitions. Applying symbolic transformations to this description, yields a symbolic LTS (Labeled Transition System), represented as a BDD, which is minimized symbolically with respect to branching bisimulation using the sigref tool. After exporting the resulting quotient into a BCG file, the further analysis steps are performed using CADP. The minimized LTS is compositionally transformed into a uniform IMC (Interactive Markov Chain), alternating construction steps (time-constraint weaving) with minimization modulo stochastic branching bisimulation using BCG_MIN. These compositional steps are automated by the use of SVL. Last, but not least, the final uniform IMC is transformed to an uniform CTMDP (Continuous Time Markov Decision Process) which is used to compute the worst-case probability of reaching a safety critical state.
Experiments with scenarios for two trains show that the compositional techniques of CADP allow to reduce the size of the final IMC by a factor of up to 326, and that the largest intermediate IMC are up to a factor 206 smaller than the monolithically generated state space. Furthermore, the generation time was reduced by a factor of up to 10. Altogether, these performance improvements allowed to handle a scenario with four trains in about the same time as the monolithic approach required for a similar scenario with only two trains.
The advantages of the compositional techniques provided by CADP are
described in the paper [Boede-Herbstritt-Hermanns-et-al-06] as
Eckard Böde, Marc Herbstritt, Holger Hermanns, Sven Johr, Thomas
Peikenkamp, Reza Pulungan, Ralf Wimmer, and Bernd Becker.
"Compositional Performability Evaluation for Statemate". In
Proceedings of the 3rd International Conference on the Quantitative
Evaluation of Systems QEST '06 (Riverside, California, USA),
pp. 167-178, IEEE Computer Society Press, September 2006.
Available on-line from our FTP site in PDF or PostScript
Department of Computer Science
Tel: +49 681 302 5631
Fax: +49 681 302 5636
|Further remarks:||This case study, amongst others, is described on the CADP Web site: http://cadp.inria.fr/case-studies|