People

Research activity in 2000

1. Approximating non-Markovian behaviour by Markovian models

Performance and dependability analysis is a fundamental task in system design and validation. Non-Markovian Stochastic Petri Nets (NMSPN), which are Stochastic Petri Nets with general firing times, are a flexible and effective model to describe the system under study. General firing time distributions allow us to model exactly deterministic durations which can be of significant importance in case of systems with timeouts.

A new approach for the analysis of NMSPN models, which is based on a discrete time approximation of the stochastic behaviour of the marking process, was presented and resulted in a modeling tool called WebSPN.

Traffic measurement studies on real high speed networks carrying data packets of various applications show high variability and burstiness of the traffic process over several time scales. It is commonly assumed that Markovian models are not appropriate to capture this "burst in burst" behaviour and several other models are considered in the literature: fractional Gaussian noises, traditional and fractional ARIMA processes, fractals and multi-fractals. These models are analytically hardly tractable and often computationally expensive. The analytical tractability of Markovian models initiated a research effort to approximate real traffic behaviour with Markovian models.

High variability and burstiness may be caused by the presence of heavy-tailed distributions. A procedure for the approximation of heavy-tailed behaviour with Phase type (PH) distributions have been found. High variability is often quantified through measuring the degree of self-similarity of the process. A method have been invented for the construction of a Markovian arrival process that exhibits the desired degree of self-similarity over several time scales.

 

2. Stochastic Process algebra

Stochastic Process Algebras (SPA) are a specification language for the compositional modelling and analysis of functional and performance properties of computer, communication, and software systems.

During year 2000 we have defined a multiparadigm framework based on SPA and SPN thanks to the definition of a compact net semantics for SPA specifications, which improves on all the previous net semantics proposed in the literature.

The SPA-based software tool TwoTowers has been extended in two directions. First, the language of TwoTowers has been enriched by allowing for value passing among different communicating components, which is treated symbolically at the state space level. Second, the net semantics above has been implemented to integrate TwoTowers and GreatSPN.

The SPA formalism has been used for diagnosis analysis of hydraulic systems and for the performance analysis of a distributed fault detection algorithm.

3. Solution of SPNs and SWNs

The tensor based solution for GSPN has been extended to include synchronization of components over immediate actions: this has allowed a significant enlargement of the application that can benefit of the efficiency of tensor based analysis. The solution has been implemented inside APNNtoolbox of the University of Dortmund, and a translator from GreatSPN to APNNtoolbox has been implemented as well that allows the use of the layer facility of GreatSPN to define the net components.

The tensor algebra approach has proved very effective in moving the space bottleneck for the solution of Markovian models from the infinitesimal generator matrix to the probability vector. To be able to evaluate performance also in those cases in which the vector does not fit in memory an approximation technique has been defined and implemented in collaboration with the College of William and Mary of Williamsburg (USA) inside their tool SMART. The technique tries to gain precision from the availability of exact information on the infinitesimal generator, implicitly given by its tensor expression.

Studies have also been continued on the exploitation of symmetries in the SWN formalism: to cope with partially symmetrical models, an Extended Symbolic Reachability Graph (ESRG) was proposed, leading to better aggregations than the standard SRG, thanks to a double representation level in symmetrical and, respectively, asymmetrical classes of states. The ESRG retains significant qualitative properties of the SRG, but 1) it cannot directly used for performance evaluation purposes, 2) it shows an actual improvement w.r.t. the SRG only for "nearly symmetrical" models.

The research activity in year 2000 has devised a technique for performing steady-state performance analysis with the ESRG, based on the construction of a lumped CTMC directly from the ESRG (once the ergodicity of the underlying stochastic model has been checked, directly on the ESRG. Moreover, a more general ESRG definition has been proposed based on the concept of "local symmetry", which allows to apply the approach based on (partial) symmetries in a larger number of cases.

4. Software Architecture

The software architecture level of design focuses on the overall structure of a software system, which is seen as a collection of components interacting through connectors according to specific patterns. The vocabulary for components and connectors varies depending on the particular architectural style (client-server, pipe-filter, layered, ...).

Due to their compositional nature, process algebras are well suited for the formalism description of software architectures. Based on this consideration during year 2000 we proposed an architectural description language based on process algebras that elucidates the concepts of component and connector.

Aiming at a formal characterization of architectural styles, the language supports the description of families of software architectures that share common features. Moreover, the language is equipped with an efficient architectural check based on behavioural equivalencies for verifying whether an architectural description belongs to a given family. An extended version of the architectural description language, taking into account timing information, has also been proposed.

5. Applications

GSPNs and SWN have been extensively used during this year for the analysis of problems coming from different application fields.

GSPN and SWN have been used inside the European project TIRAN to evaluate a software solution to fault tolerance in embedded systems: models have been used to evaluate the correctness of the fault tolerant function proposed, as well as the impact on the performability of the applications that use the functions.

The need to reflect the compositionality of the TIRAN specification into the model has lead to the definition of a new class of SWN, called Parametric SWN, that allows to exchange colour types and colour values among component nets. To support the evaluation a software has been built to allow the composition of SWN nets specified using GreatSPN according to two compositional rules: superposition of places and/or superposition of transitions.

Finally the case study application proposed by ENEL inside TIRAN has been evaluated using coloured nets.

Modeling and analysis of dual band mobile communication networks has also been addressed using GSPN. For this kind of system one of the main problems is the dimension of the state space that prevents the analysis of realistic system. In this paper we present an ad-hoc approximate technique for alleviating a such problem.

Another topic in the communication network field the study of TCP connections. New models have been developed to describe the behaviour of a number of TCP connections that share a bottleneck link, considering the effects of the synchronization among connections is developed.

The model is based on Markovian assumptions and on two GSPN descriptions of the system.

From the two GSPN descriptions, using a fixed point algorithm, several interesting performance metrics referring to the TCP connections are derived.

6. Fluid Stochastic Petri Nets

Fluid Stochastic Petri Nets, has been used in the past to analyze software systems with checkpointing, rejuvenation and self-restoration, and it has been demonstrated that they are capable of including non-Markovian Petri nets.

The simulation of the FSPN models is one of the possibilities for computing performance measures using a such formalism when the application of other methods (analytical or numerical) is not possible. In this year we have investigated some of the peculiarities of the simulation of FSPN models.