Research activity in 1998
During 1998 the activity of the research group working on Methods and Tools for the Analysis and Development of Performance Oriented Computer Systems has been focused on several methodological and application aspects that can be summarized in the following way.
1. General Firing Time Distributions
The Stochastic Petri Net (SPN) formalism is currently accepted as one of the most convenient method for the description and the analysis of Discrete Event Dynamic Systems (DEDS).
The increasing use of SPN models in different fields of science and industry has brought up the need of extending the formalism so that activities with generally distributed durations can be conveniently represented.
SPNs that include general firing time distributions are amenable to a preliminary structural analysis useful for validation, provided that the characteristics of these distributions are accounted for only at the time of the construction of the corresponding probabilistic models.
The computation of performance and reliability evaluation indices from these representations requires the solution of problems that are either characterized by a complex probabilistic structure or by very large state spaces.
These two different types of problems have been addressed by the group during this last year achieving the following results:
a. The formalism of Generalized Stochastic Petri Nets (GSPN) has been extended with transitions characterized by generally distributed firing times and different memory policies.
Memory policies have been introduced that are state dependent and that can thus be modified by the occurrence of certain "events" on the Petri net.
Adhering to the spirit of the graphical PN language, the investigated memory policies have been represented as new primitivesin the form of suitable "memory resetting" arcs.
New techniques to study the transient and the steady state behavior were developed. Particular attention was devoted to the complexity of the algorithms, trying to avoid the state space explosion using the formalism of tensor algebra.
b. Additional work has been done in the field of the structured solution methods for SPN, where tensor algebra is used to devise solution methods of reduced temporal and space complexity.
The set of models that can be studied with this method has been enlarged and a complexity analysis has been performed to actually quantify the improvements deriving from this new technique.
Tensor based methods have also been applied to the state space construction and subsequent solution of SPNs with Phase-type distributions.
2. Stochastic Process Algebras
Stochastic Process Algebras (SPA) represent an alternative method for modeling DEDS in which composition of basic modules is achieved by using proper construction operators.
SPA models are often characterized by intrinsic symmetries that make them comparable with Petri net based representations developed with the use of Stochastic Well Formed Petri Nets (SWN).
A thorough comparison of the advantages and disadvantages of the two formalisms has been conducted with a discussion of the classes of problems for which the two techniques are best suited.
Solution methods originally devised for the SWN formalism have been ported within the SPA framework to increase the analysis capability of this new technique.
3. Product Form SPNs
The research activity on the relationships between SPNs and Queueing Networks (QN) has been continued with the investigation of the impact that the structural properties of the underlying PN models has on the efficiency of their numerical solutions.
Interesting results have been derived with respect to the definition and solution of traffic equations that are related with the presence of T-invariants.
Structural properties of Petri nets have also been investigated with respect to their use in the efficient computation of the equilibrium distributions of queueing networks with blocking that can be conveniently represented as product form SPNs.
4. Performance Efficient Parallel Applications
Design techniques that allow the development of performance efficient parallel applications have been devised and applied to real world case studies such as concept induction, load balancing and protocols for distributed simulation.
The design and implementation of a parallel algorithm for concept induction, able to semi-automatically adapt its characteristics to those of the computing platform used for its execution, has been carried out.
In order to be suitable for a wide class of parallel executing platforms, ranging from classical parallel computing systems to cluster of workstations connected by a local area network, appropriate load balancing and latency toleration techniques have been devised and implemented.
Typical applications of this system include data-mining in large databases and classification problems.
Techniques for effective performance management of distributed applications have been studied. In particular, a new approach called pro-active performance management has been defined. The approach is based on the use of forecast techniques that allow to predict the instant in time when a given resource management action should be carried out, rather than waiting that the system reaches a given (possibly undesired) state, as it is done with classical reactive approaches.
As a consequence of its greater timeliness, our approach results in a more efficient management.
Pro-active management strategies can be applied to a broad class of problems, including load balancing and protocols for distributed simulation.
5. Applications
GSPNs have been extensively used during this year for the analysis of problems coming from different application fields.
The GSPN modeling paradigm has been adapted to the performance analysis of ATM networks at the cell level. The approach is based on the use of many immediate transitions, and only one timed transition whose firing time distribution is irrelevant for the computation of several performance indices, and on the exploitation of well-known results developed in the framework of the theory of stochastic processes. This methodology has been applied to the investigation of complex systems such as ATM switch architectures (Knockout and Gauss), and ATM LANs with Available Bit Rate (ABR) users.
For the latter system the GSPN model is one of the first analytical representations of the behavior of the ABR service category, that has been thoroughly investigated by simulation, and that is one of the prominent approaches for the provision of best effort communication services within ATM networks.
To cope with the complexity of the problem, SWNs have been adapted to to the performance analysis of symmetric ATM switch architectures, developing models with limited state spaces.
Finally, non-Markovian extensions of the GSPN formalism have been used for performance and reliability analysis of Universal Mobile Telecommunications System, with particular emphasis on the data bases architecture employed in the system.
GSPNs have also been applied for the performance analysis of a wavelength division multiplexing bus.
State space aggregation driven by symmetries and behavioural characteristics has been emploied for the analysis of a simple communication protocol expressed as a SPA model.
GSPN and SWN models have also been used for the analysis of concurrent programs targeted to different classes of parallel architectures. Programs targeted to Transputer-based parallel computers with a hypercube topology have been modeled and analyzed with Stochastic Well Formed nets, since the inherent symmetries of these topologies allowed a convenient use of this formalism. GSPN models have instead been used to study the performance of concurrent programs executed on heterogeneous distributed computing systems, including clusters of heterogeneous workstations.
Finally, GSPNs and SWNs have also been used to specify and to study the behaviour of fault-tolerance mechanisms adopted in plant automation control software and to study the problem of "software rejuvenation" that is periodically needed in order to recover from the performance decay that is consequence of possible data structure degenerations.
1998 Publications
M. Ajmone Marsan, A. Bobbio, and S. Donatelli. Petri nets in performance analysis: An Introduction. In W. Reisig and G. Rozemberg, editors, Lectures on Petri Nets I: Basic Models, Lecture Notes in Computer Science, Springer Verlag, vol. LNCS-1491:211-256, 1998.
M. Ajmone Marsan and R. Gaeta: SWN Analysis and Simulation of Large Knockout ATM Switches. In: Desel,J., Silva,M. (eds.): ICATPN 98. Lecture Notes in Computer Science, Vol. 1420. Springer-Verlag, Berlin Heidelberg New York (1998) 326-344
M. Ajmone Marsan and R. Gaeta: Modeling ATM systems with GSPNs and SWNs. ACM Performance Evaluation Review, Vol. 26, n. 2, August 1998, pp. 28-37
C. Anglano. Predicting Parallel Application Performance on Non-Dedicated Cluster Platforms. In Proc. of the 12th ACM International Conference on Supercomputing (ICS 98), 322-331. IEEE CS Press, July 1998.
C. Anglano, C. Casetti, E. Leonardi, and F.Neri. Multicasting at the Host Interface Level in Wormhole Networks. In Proc. of the 6th IEEE International Conference on Network Protocols (ICNP'98), 320-328. IEEE CS Press, October 1998.
C. Anglano, A. Ferscha, J. Johnson, and G. Kotsis. Pro-active Performance Management of Distributed Applications. In Proc. of the 6th International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS '98), 151-158. IEEE CS Press, July 1998.
C. Anglano, A. Giordana, G. Lo Bello, and L. Saitta. An Experimental Evaluation of Coevolutive Concept Learning. In Proc. of the 15th International Conference on Machine Learning, 600-609. Morgan Kaufman, July 1998.
C. Anglano, A. Giordana, G. Lo Bello, and L. Saitta. Coevolutionary, Distributed Search for Inducing Concept Descriptions. In Proc. of the 10th European Conference on Machine Learning (ECML 98), Lecture Notes in Artificial Intelligence, 101-110. Springer Verlag, April1998.
G. Balbo and M. Silva Ed.s. Performance Models for Discrete Event Systems with Synchronizations: Formalisms and Analysis Techniques. KRONOS, Zaragoza, Spain, 1998 (924 pages).
G. Balbo. Exponential Stochastic Petri Nets. In Performance Models for Discrete Event Systems with Synchronisations: Formalisms and Analysis Techniques, Book of the MATCH Advanced School. KRONOS, Zaragoza, Spain, 1998, pages 307 -- 344.
G. Balbo. Non-Exponential Stochastic Petri Nets. In Performance Models for Discrete Event Systems with Synchronisations: Formalisms and Analysis Techniques, Book of the MATCH Advanced School. KRONOS, Zaragoza, Spain, 1998, pages 345 -- 385.
A. Bobbio, D. Del Corso, L. Farinetti, G. Malnati, E. Ovcin, and D. Vidotto. SICURO Project. In 7-th World Conference on Continuing Engineering Education - WCCEE98, 334-338, 1998.
A. Bobbio, A. Puliafito, M. Scarpa, and M. Telek. WebSPN: A WEB-accessible Petri net tool. In International Conference on Web-Based Modeling Simulation, 137--142, 1998.
A. Bobbio, A. Puliafito, M. Telek, and K. Trivedi. Recent developments in non-Markovian stochastic Petri nets. Journal of Systems Circuits and Computers, 8:1, 119-158, 1998.
A. Bobbio and M. Sereno. Fine Grained Software Rejuvenation Models. In Proc. 3-th International Computer Performance Dependability Symposium (IPDS '98), pages 4--12, Durham, North Carolina, USA, September 1998. IEEE Comp. Soc. Press.
A. Bobbio and M. Telek. Non-exponential stochastic Petri nets: An overview of methods and techniques. Computer Systems: Science Engineering, 13:6, 339-351, 1998.
R. J. Boucherie and M. Sereno. On closed support t-invariants and traffic equations. Journal of Applied Probability, (35):473--481, 1998.
L. Capra, R. Gaeta, and O. Botti. Using SWN Nets to Specify and Analyze FT Mechanisms Adopted in Electric Plant Automation. IEEE Proc. of Int. Conf. on Systems, Man and Cybernetics, 11-14 October, San Diego (USA), 1998, 111-120.
S. Donatelli. Tensor based methods in in GSPN In G.Balbo and M.Silva, editors, Performance Models for Discrete Event Systems with Synchronisations: Formalisms and Analysis Techniques. Volume I, 429-460. KRONOS, Zaragoza, ES, 1998.
S. Donatelli and G. Franceschinis. Modelling and analysis of distributed software using gspns. In W.Reisig and G.Rozenberg, editors, Lectures on Petri Nets II: Applications, 438-477. Springer Verlag, 1998.
S. Donatelli, S. Haddad, and P. Moreaux. Structured characterization of the Markov chain of phase-type SPN. 10th International conference TOOLS98, LNCS 1469, 243-254, Springer-Verlag, Heidelberg.
S. Donatelli, C. Simone, and D. Trentin. Combining abstraction and context: a challenge in formal approaches to workflow management. WFM98: Workshop on workflow management: net-based concepts, models, techniques, and tools, June 98, Lisbona, Portugal, 110-125.
C. Dutheillet, S. Haddad, and G. Franceschinis. Analysis techniques for colored well-formed systems. In G.Balbo and M.Silva, editors, Performance Models for Discrete Event Systems with Synchronisations: Formalisms and Analysis Techniques. Volume I, 233-284. KRONOS, Zaragoza, ES, 1998.
G. Franceschinis. Bounds for quasi-lumpable swns. In G.Balbo and M.Silva, editors, Performance Models for Discrete Event Systems with Synchronisations: Formalisms and Analysis Techniques. Volume II, 495-524. KRONOS, Zaragoza, ES, 1998.
G. Franceschinis and L. Capra. Symmetries and exact lumping in swn. In G.Balbo and M.Silva, editors, Performance Models for Discrete Event Systems with Synchronisations: Formalisms and Analysis Techniques. Volume II, 461-464. KRONOS, Zaragoza, ES, 1998.
G. Franceschinis, A. Fumagalli, and R. Grasso. Performance analysis of a wavelength division multiplexing bus network based on gspn models. In Proc. International Conference on Modelling Techniques and Tools for Computer Performance Evaluation, 207-218, Palma, Spain, Sep 1998. Springer Verlag.
G. Franceschinis and M. Ribaudo. Efficient performance analysis techniques for stochastic well-formed nets and stochastic process algebras. In W.Reisig and G.Rozenberg, editors, Lectures on Petri Nets II: Applications, 386-437. Springer Verlag, 1998.
G. Franceschinis and M. Ribaudo. Symmetric and behavioural aggregation in a simple protocol example. In Proc. International workshop on Process Algebra and Performance Modeling (PAPM '98), 119-136, Sep 1998.
R. Gaeta, K. Begain, and M. Ajmone Marsan, "Stop Go ABR in ATM LANs: Performance Analysis with GSPNs,'' in Proc. rd IEEE International Computer Performance and Dependability Symposium. Durham, NC, USA, pp. 64-75, September 1998.
M. Gribaudo and M. Sereno. On the use of structural Petri net analysis for studying product form equilibrium distributions of queueing networks with blocking. Proc. Intern. Conference on Petri Nets ICATPN 98, IEEE-CS Press, 246-265, 1998, Lisbona, Portugal
H. Hermanns and M. Ribaudo. Exploiting Symmetries in Stochastic Process Algebras. In Proc. of 12th European Simulation Multiconference, 763-770, (Manchester, UK). SCS Europe, 1998.
J. Hillston and M. Ribaudo. Stochastic Process Algebras. In G.Balbo and M.Silva, editors, Performance Models for Discrete Event Systems with Synchronisations: Formalisms and Analysis Techniques. Volume I, 135-181. KRONOS, Zaragoza, ES, 1998.
J. Hillston and M. Ribaudo. Stochastic Process Algebras: a New Approach to Performance Modeling. In Advanced Computer Performance Modeling and Simulation, pages 235 -- 256. Gordon and Breach Science Publishers, 1998.
M. Scarpa and A. Bobbio. Kronecker representation of stochastic Petri nets with discrete PH distributions. In International Computer Performance and Dependability Symposium - IPDS98, IEEE Computer Society Press, 52-61, 1998.
M. Sereno. Binary search with errors and variable cost queries. Information Processing Letters, 68(5):261--270, Dec 1998.
M. Sereno. Product Form & Petri Nets, In G.Balbo and M.Silva, editors, Performance Models for Discrete Event Systems with Synchronisations: Formalisms and Analysis Techniques. Volume I. KRONOS, Zaragoza, ES, 1998, pages 637-660.
M. Sereno. Computational Algorithms for Product Form Solution Stochastic Petri Nets, In G.Balbo and M.Silva, editors, Performance Models for Discrete Event Systems with Synchronisations: Formalisms and Analysis Techniques. Volume I. KRONOS, Zaragoza, ES, 1998, pages 661-692.
