TRACK 1 8.30-10.20 Advances in Layered Queue Modelling for Distributed Systems Speaker: Murray Woodside (Carleton University) Performance modelling for distributed systems is fraught with difficulties, because they have concurrency, parallel paths, and logical resources such as shared buffers, single-threaded tasks, and critical sections, and blocking communications (or rendezvous, hence the name "rendezvous nets" in some layered modelling work). Layered modelling is designed to make performance analysis more direct. It follows the structure of the software. It sees the system as a hierarchy of resources and workloads organized in layers. Execution paths go up and down through the layers, depending on the resources required to execute. It is a kind of structured Extended Queuing Network, with a structure that strongly resembles the software structure of a distributed system. Two sets of tools have recently been described for solving these models, the "Method of Layers" and "Rendezvous Networks". Outline: 1. Layered Resources and Queues 2. Asynchronous Interactions 3. Parallel Servers and Parallel Paths 4. Scale-up to large systems 10.20-10.40 Break 10.40-11.30 Quality of Service (QoS) Modelling Speaker: Dr. Hermann G. de Meer (University of Hamburg) The evaluation and prediction of QoS becomes increasingly important in high-speed networks supporting advanced applications like multimedia. Quantitative modeling will play an important role to appropriately support such a scenario of dynamic management and control. In this tutorial we will introduce the essentials of QoS modeling, discuss the main issues concerning QoS provisioning, and give an overview of approaches that have been followed so far in the literature. In detail, typical QoS requirements of multimedia applications will be explained with respect to metrics and service categories. Particular emphasis will be on the notion of QoS specification and QoS mapping as prerequisites for any evaluation studies. Models presented in the survey include Markov models, queueing models, and neural networks. Issues related to QoS monitoring and measurement will also be outlined. 11.40-12.30 Providing Tools over the Internet and Intranet Speaker: Aad van Moorsel (Bell Labs) Internet and Intranet are becoming very important in working with a variety of software applications. The unifying way of accessing tools through web browsers is very attractive for software users. Offering tools from a local web server is equally interesting for tool developers since it makes software updating, maintaining and releasing so much easier. Furthermore, distributing functionality may improve the performance of the tool. The tutorial will be devoted to talk about how to offer performance and reliability evaluation tools over the Internet or Intranet. The outline of the talk will be subject to continuing changes because of the rapidly evolving technology, but will most likely be along the following lines: 1. Introduction: The hazzles of the current system of ''down loading'' Why users want web browsers Why tool developers would benefit from an Internet solution 2. Implementation: Using Java applet or Tcl/Tk plug-ins The need for C programming of solvers The consequences of security provisions Different scenario's for different environments (this would be a main part, and would go from a full-fledged Internet solutions to environment adjusted solutions) 3. Evaluation: A discussion of the potential of Internet solutions Experimental results in Bell Labs 12.30-14.00 Lunch 14.00-15.50 Performance-Oriented Design for Object-Oriented Systems (I) Speakers: Connie U. Smith, Performance Engineering Services (Santa Fe, NM) Lloyd G. Williams, Software Engineering Research (Boulder, CO) Many organizations have avoided object-oriented technology due to concerns over performance. Our experience is that it is possible to develop object-oriented software systems that exhibit adequate performance while preserving the properties, such as modifiability, maintainability, and reusability, that have made object-oriented techniques so successful. This tutorial discusses a set of principles for designing responsive software and their application to object-oriented systems. These guidelines may be used with any object-oriented modeling and design technique. Use of the principles during both requirements-level and design-level modeling is discussed. Some common object-oriented design guidelines and their performance implications are also discussed. Objectives: - To introduce a set of performance principles for software - To discuss how these principles may be applied to the design of object-oriented systems - To discuss some object-oriented design guidelines and their performance implications. Outline: 1. Introduction and Overview 2. Basic Principes (Centering, Fixing-Point, Locality, Processing vs Frequency, Instrumenting, Shared Resource, Parallel Processing) 3. Additional Principles for Concurrent and Distributed Systems 4. Design Guidelines 15.50-16.10 Break 16.10-18.00 Performance-Oriented Design for Object-Oriented Systems (II) Speakers: Connie U. Smith, Performance Engineering Services (Santa Fe, NM) Lloyd G. Williams, Software Engineering Research (Boulder, CO) __________________________________________________ TRACK 2 8.30-10.20 Stochastic Process Algebras - Foundation and Relations with SPN Speakers: G. Balbo, H. Hermanns, U. Herzog, V. Mertsiotakis, and M. Ribaudo (Universities of Erlangen and Torino) Stochastic Process Algebras (SPA) have recently gained some attention in the performance evaluation community. Their unique feature is compositionality. In this tutorial we will introduce the audience into the benefits of compositionality on the level of model construction and its potential for model solution. In the main part of the tutorial we will discuss the potential cross fertilization between SPN and SPA. On the one side, the large repertoire on efficient solution algorithms for SPN can be transferred to SPA. On the other side, construction of SPN for real (thus complex) systems can be greatly enhanced by providing compositional methods. We discuss examples for both directions. A number of case studies, as well as recent results and the implications of the formal development for tool support will also be discussed. Outline: 1. Introduction and Motivation 2. SPA approach: compositionality 3. Comparison of modelling style in SPA and SPN 4. Cross fertilization 5. Summary and conclusions 10.20-10.40 Break 10.40-12.30 Equivalence and exact aggregation of labelled (G)SPNs Speaker: Peter Buchholz ( University of Dortmund) Notions of equivalence are established in most paradigms for the functional analysis of dynamic systems. For untimed Petri Nets a large number of equivalence definitions has been proposed. The goal of most equivalence definitions is twofold. First, they allows us to compare whether two different systems behave equivalent or not. Second, they can be used to substitute a subsystem by less complex, but equivalently behaving aggregate. In this way, the enormous complexity of state based analysis techniques can be reduced up to certain extend. The tutorial aims to give an overview of equivalence notations for (G)SPNs. It starts with an introduction of labelled (G)SPN, which are(G)SPNs extended by transition and place labels. Labels are introduced to describe result measures and composition of (G)SPNs in a formalised way. Such a formalisation is mandatory for any equivalence definition. Different concepts of equivalence including symmetries, ordinary performance bisimulation and exact performance bisimulation are introduced. The theoretical definition of equivalence relations is followed by the introduction of algorithms to decide equivalence of two labelled (G)SPNs and to compute minimal equivalent state space realisations for labelled (G)SPNs. Afterwards, it is shown how labelled (G)SPNs are composed such that equivalence is preserved by the composition. The interleaving of minimisation and composition is an efficient and exact analysis approach for many (G)SPN models. The tutorial ends with an extension of exact equivalence to approximate equivalence which possibly allows further state space reduction, but introduces an approximation error. 12.30-14.00 Lunch 14.00-15.50 Kronnecker operators for the description and solution of large Markov models generated by stochastic PNs Speakers: G. Ciardo (Williams and Mary College) S. Donatelli (Univ. of Torino) We present background and recent results on the use of Kronecker operators for the description and solution of large Markovian stochastic models. We believe that researchers interested in building computer-based stochastic modeling tools, and, in more generality, practitioners using discrete-state stochastic models, can benefit from the application of these techniques, which result in memory savings for the numerical solution, thus allowing the exact solution of much larger models than ever before. Outline: 1.Background Kronecker algebra Markov chains and the infinitesimal generator High-level discrete-state stochastic formalisms The state space Numerical solution methods 2. Structured description Example The SGSPN class Potential vs. actual state space 3. Structured description Example A Kronecker expression 4. Algorithms for the solution The algorithms (under full and sparse storage schema) Storage and execution costs 15.50-16.10 Break 16.10-18.00 Approximation methods based on net-driven decompositions Speaker: Javier Campos (University of Zaragoza) A major drawback for the practical use of stochastic Petri net models lies in the state explosion problem originated when the exact solution of the associated CTMC is achieved. This tutorial presents some ideas an examples on approximation techniques that try to overcome the state explosion problem within a divide and conquer strategy and with a strong exploitation of structural (qualitative) knowledge of the underlying Petri net model for both the decomposition and the solution phases. Outline: 1. Principles of approximation techniques based on decomposition. Some general considerations on decomposition techniques: - Partition of the system into subsystems. - Characterization of subsystems. - Writing equations among the unknown parameters. - Computational algorithms for solving the fixed point equation. Several classification criteria for decomposition based approximation techniques. 2. A technique with PF subsystems and non-PF skeleton. 4. A technique with non-PF subsystems and non-PF skeleton. 5. Final comments and forthcoming research efforts. __________________________________________________ TRACK 3 8.30-10.20 Parallel and Distributed Simulation of Petri Nets Speaker: Alois Ferscha ( Universitat Wien ) This tutorial will study (timed) Petri nets as specifications of simulation models, and both the adaptation classical (Chandy/Misra and Time Warp) as well as the development of new (Windowing, Probabilistic Optimism) distributed simulation protocols will be presented. The partitioning of large Petri net models will be studied in order to optimize the elapsed (parallel) simulation time and run time load balance. The possibilities to exploit time parallelism for a simulation in a SIMD fashion will be exemplified. For both cases, the analysis of the mathematical properties of the structure of the Petri net model that can be effectively computed off-line before the start of the simulation experiment is essential: these properties statically identify portions of models that potentially yield concurrent events and portions that have no chance to yield useful parallelism. Based on this information an automated partitioning and space-time decomposition is possible yielding an optimum balance of communication and computation requirements of the distributed simulation, or an efficient utilization of a dedicated parallel processor respectively. A variety of "adaptive" simulation mechanisms is currently emerging in the literature, supporting the hypothesis that controlling different simulation execution parameters allows to dynamically adjust a simulation engines execution behavior to the respective peak performance. Such approaches shall be presented in a formal format. Outline: 1. Petri Nets and Discrete Event Systems 2. Distributed Simulation of Timed Petri Nets (TPNs) 3. Adaptive Distributed Simulation of TPNs 4. Massively Parallel Simulation of Timed Petri Nets 5. Future Directions in Accelerating TPN Simulations 10.20-10.40 Break 10.40-12.30 Non-Exponential Stochastic Petri Nets: an Overview of Methods and Techniques Speakers: Andrea Bobbio ( Universita` di Torino) Miklos Telek (Technical University of Budapest) Title: Non-Exponential Stochastic Petri Nets: an Overview of Methods and Techniques Andrea Bobbio, Dipartimento di Informatica, Universita` di Torino Miklos Telek, Department of Telecommunications, Technical University of Budapest The analysis of stochastic systems with non-exponential timing requires the development of suitable modeling tools. Recently, some effort has been devoted to generalize the concept of Stochastic Petri nets, by allowing the firing times to be generally distributed. However, in order to univocally define the marking process associated to a non-markovian PN, further specifications must be added at the net level. These specifications can be referred to as the firing policy. The tutorial discusses the semantics of different firing policies that have appeared in the literature and the nature of the associated marking process. In particular, the tutorial will address a class of non-markovian Petri nets, whose associated marking process is in the form of a Markov Regenerative process, for which closed form solution techniques are available in transient as well as in steady state. Finally, the tutorial will explain the problems connected to the numerical solution for this class of PN models, and presents several examples. 12.30-14.00 Lunch 14.00-15.50 Fluid Petri Net Speaker: Kishor Trivedi ( Duke University) A class of stochastic Petri Nets is introduced. In this class of nets one or more places can hold fluid rather than discrete tokens. We define a class of fluid stochastic Petri Nets in such a way that the discrete and continuous portions may affect each other. Following this definition we provide equations for their transient and steady-state behavior. We present several examples showing the utility of the construct in communication network modeling and realiability analysis, and discuss important special cases. We then discuss numerical methods for computing the transient behavior of such nets. Finally, some numerical examples are presented and evidence of the accuracy of the fluid approximation is given. 15.50-16.10 Break 16.10-18.00 On the use of matrix-geometric methods for the performance evaluation of computer and communication systems Speaker: B. Haverkort (University of Aachen) The aim of this tutorial is to bring the powerful Matrix Geometric Methods (MGM) and the closely related phase-type distributions closer to more practically-oriented performance analists, by (i) showing that the underlying mathematics are not that complex in the first place, (ii) by illustrating that high-level tool support for such methods is possible (and does exist) so that many of the mathematical details can even be hidden from the modellers, and (iii) by showing a veriety of applications from the fields of communication and computer systems. The tutorial participants will have the possibility to actually use a MGM-based performance evaluation tool. Outline: 1. Introduction. 2. Phase-type distributions 3. Markov-modulated arrival processes 4. The basic matrix-geometric method 5. The matrix-geometric method: algorithmic details 6. Stochastic Petri Nets which allow for a matrix-geometric solution 7. Application studies