Adding Auxiliary Information

Models can contain two kinds of information: information that is necessary for modelling the behaviour of the system, and auxiliary information that does not influence the behaviour of the model. In some cases, it is possible to analyse additional aspects of a system when auxiliary information can be added to

4.3. Related Work 43 models. We have seen how annotations can be used in CP-nets to measure, e.g.

average packet delay. This is possible only because relevant information can be associated with each token. Measuring average packet delay is more complicated when using low-level Petri nets or SANs because the tokens cannot carry any information. For example, average packet delay could be measured using a technique similar to what is used by Sanders and Meyers [111] to measure average response time for jobs in a multiprocessor system. Average response time must be calculated as the number of jobs in the system divided by the average arrival rate of jobs. This requires a detailed understanding both of the model and of relevant statistical formulas.

In high-level PNs tokens can carry information. In ExSpect all auxiliary information must be hard-coded in token colours, in contrast to defining an-notations separate from a CP-net. However, a user can use standard building blocks and predefined colour sets which contain many useful kinds of auxiliary information. For example, the object colour set has components for arrival time, processing time, and object type, which can be updated and monitored at appropriate times during a simulation. Thegenerator building block gener-ates tokens withobjectdata values, and it will, e.g. add the appropriate arrival time to a token colour when a particular transition occurs.

General simulation packages often have a notion of entities, where entities represent, among other things, objects that move about in the system being modelled. Entities could be used to model, e.g. packets in a computer network, customers in a bank, or cars in an assembly plant. Auxiliary information can be associated with entities using attributes which contain information that is specific for individual entities. Attributes can contain information that deter-mine the behaviour of the model, such as a customer type that deterdeter-mines how a customer is added to a priority queue. Attributes can also contain auxiliary information which does not influence the behaviour of the system but which does aid in analysing the behaviour of the model. An example of this kind of attribute is the arrival time of a customer.

Incorporating auxiliary information in a model generally requires either manually encoding the information in the model or building the model with predefined modules and data types. The advantages of using standard mod-ules and data types is that they are easy to use and they generally contain the information that is relevant for most situations. Problems arise, however, when a user is confronted with a new kind of system which cannot be properly modelled by the standard modules and data types. Models containing auxiliary information will generally be more complicated than models that do not contain auxiliary information. As a result, the models with auxiliary information may be more difficult to understand and to validate. With annotations, auxiliary information can be added to a model without modifying the model and without affecting the behaviour of the model.

4.3.2 Comparing Behaviour

Work that is closely related to our notion of annotations can be found in Lakos’

work on abstraction [83]. He defines a so-called colour refinement within the

context of behaviour-respecting abstractions of CP-nets. This colour refinement is used to specify more detailed behaviour in sub-modules by extending colour sets to larger domains. The refined colours are only visible in the sub-modules, and the refined colours will typically contain information that is necessary for modelling the behaviour of the system in question. This colour refinement cor-responds somewhat to our way of extending colour sets by adding annotations to colours, and it respects the behaviour of the CP-net. I am not aware of work other than our own that addresses the issue of introducingauxiliary information into a CP-net (or any other type of simulation model) while at the same time preserving the behaviour of the CP-net. Nor do I know of any other method that can be used to automatically enable or disable auxiliary information when analysing different aspects of one particular model.

The Renew tool supports a relaxed syntax [81] for defining reference nets that allows the addition of auxiliary information to a model without affecting the behaviour of the model. The tool allows the use of untyped places and untyped variables. In other words, a place can contain tokens with token values from many different data types, and arcs can be used to add and remove any kind of token from these places. Adding auxiliary information to the initial marking of untyped places will not affect the behaviour of the model, assuming that the auxiliary information never needs to be attached to a token on a typed place. When a transition occurs, the auxiliary information can be accessed via the binding of an untyped variable in transition inscriptions. The tool requires that all variables on arcs from transitions to typed places must be typed, and if one variable is typed then all variables in the model must be typed.

It is often useful to know that two different models have equivalent, or at least very similar behaviour. When analysing the functionality of a system, an analyst may develop and validate a fairly detailed model which captures many aspects of the system. For example, a model of an application layer protocol, such as HTTP, may contain a detailed description of lower-level protocols such as TCP or IP. When the time comes to analyse the behaviour of the model, the model may be too detailed, and the desired analysis methods cannot be employed, e.g. full state space analysis cannot be used because the state space is infinite. It is then up to the user either to try to reduce the complexity of the model in such a way that the behaviour of the model is preserved, or to find alternative analysis methods that can handle the problem. For example, when modelling and analysing HTTP, it should not be necessary to include a detailed description of TCP, in which case the parts of the model representing TCP could be simplified in an attempt to obtain a smaller state space. In some cases, a user must use elaborate proofs to show that the results obtained by analysing the reduced model or by using an alternative analysis technique are, in fact, applicable for the original model.

Several techniques exist for comparing the behaviour of different models and for comparing different behavioural representations of the same model. A com-mon technique for testing the behavioural similarities of two process algebraic models is the use ofbisimularities [22], where a(weak) strong bisimulation is a binary relation that shows that two process algebraic models have (observably) identical behaviour. It must be possible to investigate the complete behaviour

4.3. Related Work 45 of each model in order to show that two models are bisimilar. There are also rules for reducing low-level Petri nets [20] and for reducing CP-nets [58] to nets with similar behaviour. An alternative to reducing a model itself is to try to reduce the size of the state space of the model in order to analyse the behaviour of the model. State spaces with equivalence classes [70] is a technique that can be used to group similar markings and binding elements together in order to generate a representation of the behaviour of the model that is smaller than the full state space of the model. The techniques mentioned above require reducing either a model or the representation of the behaviour of the model in order to obtain a smaller, alternative representation with similar behaviour. In contrast to these techniques, we have shown that adding annotations to a CP-net will result in a CP-net which behaves very similarly to the original CP-net. I am not aware of any other techniques for augmenting a model that preserves the behaviour of the model.

4.3.3 Performance Analysis and Formal Methods

A large amount of research is concerned with using formal methods to anal-yse the performance of systems, and a recent summer school [23] provided an introduction to the formal methods that are most commonly used for perfor-mance analysis. Formal methods are characterised by Clarke et al. [34] as mathematically-based languages, techniques and tools for specifying and veri-fying systems, and formal specification uses a language with a mathematically defined syntax and semantics. The formal methods that are most commonly used for performance analysis are (G)SPNs, SWNs, SANs, the Performance Evaluation Process Algebra (PEPA) language [62], and queueing networks [78].

The PEPA Workbench [102, 52] supports the PEPA language, and M¨obius [33]

is an innovative, multi-paradigm modelling tool that supports the creation and analysis of models consisting of components that are expressed in different for-malisms, such as SAN, PEPA, and SPN.

Many of the formal methods that are used for performance analysis were derived from formal methods that originally were only used for functional anal-ysis of systems. Formal methods, such as Petri nets, activity nets, and process algebras, are used both to specify and verify system behaviour. Timing infor-mation was added to these formal methods in order to support modelling and analysis of both functionality and performance of systems. Many of the result-ing formal methods, such as (G)SPNs, SANs, and stochastic process algebras, require that time delays are, for example, all exponentially distributed. When these requirements are fulfilled, it is possible to derive an analytical model, such as a continuous-time Markov chain, from the original model.

There are a number advantages associated with using formal methods for performance analysis. One major advantage is the fact that they can describe the behaviour of a system in an unambiguous way. Moreover, the same model can potentially be used to analyse both the functionality and the performance of a system, since an untimed model can be created for functional analysis, timing information can be added, and the performance of the model can then be analysed. Markovian models, which are also a formal methods, can provide

exact values for relevant performance measures, and advanced techniques exist for solving such models. However, it is often to difficult to manually define accurate Markovian models, therefore it is also advantageous that Markovian models can be automatically generated from higher-level specifications, such as SANs and GSPNs.

There are also a number of disadvantages to using formal methods for per-formance analysis. In 1996, Clarke observed that some of the problems with formal methods are: the notations were too obscure, the techniques did not scale, and the tool support was inadequate or too hard to use. On a positive note, Petri nets are becoming more widely accepted, case studies have shown that formal methods can be used to analyse the performance of industrial-sized systems (see Sect. 5.3.3), and the most widely used PN performance tools are quite stable. While there have been improvements in these areas during the past decade, these problems still exist. For example, textual PEPA models are not easy to understand, industrial-sized models can rarely be analysed us-ing Markovian models due to the state explosion problem, and tools that are developed in academic research groups frequently use state-of-the-art analysis techniques, but they are sometimes difficult to use, poorly documented, and not terribly robust. With respect to these problems, commercial products that are based on informal modelling languages are likely to be more popular (and useful) than formal methods for several reasons: industrial-sized models can be built using predefined, drag-and-drop modules of familiar components; every syntactically-correct model can be simulated; customer support is provided for mature, stable, and well-documented tools; and for the average user it is still fairly time consuming to learn to understand a formal method.

Chapter 5

Case Study: Analysis of Web Servers

This chapter discusses the paper “Simulation Based Performance Analysis of Web Servers.” Section 5.1 introduces the CAPLAN project in which the work presented in this paper was done. Section 5.2 summarises the main contribu-tions of the paper and evaluates the techniques that were applied. Section 5.3 discusses related work.