The model based analysis of computer and communication systems requires adequate software tools to handle the inherent complexity of today's systems. Furthermore it is more and more agreed upon that analysis has to be performed according to both qualitative and quantitative aspects of a system, preferably using one model. Many modelling paradigms and analysis techniques exist for these purposes, in particular models based on underlying Markov chains are well suited for a quantitative analysis and can also be used for qualitative analysis by neglecting timing information. Markov chains are often analysed by numerical techniques, which are more accurate than simulation and more flexible than analytical analysis techniques. However, any approach for a state based analysis is faced with the following problems:
It has to support the modelling of complex systems, such that models are understandable and can be easily modified, and it has to manage the state space explosion which results from the usually exponential growth of the number of states as a function of the size of the model specification.
A rich variety of techniques exists for a high level specification of Markov chains; two particularly important ones concerning performance analysis are extended queueing networks and generalised stochastic Petri nets (GSPNs, [1]). Both techniques have their specific advantages and disadvantages. The possible exploitation of the advantages of both approaches led to the development of QPNs, combining coloured GSPNs and queueing networks in one modelling formalism [2], and the QPN-Tool supporting the graphical specification and automatic analysis of QPNs [4]. However, QPNs also suffer from the above mentioned problems since they describe a flat model which becomes complex when the system to be modelled is complex and the size of the resulting Markov chain often exceeds the capacity of today's computers.
A general method to handle complexity is the use of hierarchical structuring mechanisms. This route has already been pursued in some performance modelling tools, as an example we refer to HIT [6]. Furthermore hierarchical untimed Petri net models are widespread (e.g. [16]). However, all mentioned approaches use hierarchies only for specification purposes, while analysis is performed on the underlying flat model. More recently a hierarchical approach for the specification and analysis of queueing networks [9], coloured GSPNs [7] and a subclass of HQPNs [3] has been developed. This approach allows the hierarchical specification of models and an efficient numerical analysis that exploits the hierarchical structure. The central idea of the analysis is to represent the huge generator matrix of the underlying Markov chain by much smaller matrices, each describing a submodel, which are combined using tensor operations. Using this technique, Markov chains can be solved which are about an order of magnitude larger than those analyzable with conventional techniques. A salient property of our hierarchical approach is that it does not depend on model symmetries and leads to exact results.
HQPNs as introduced here allow the specification of a system in several levels: The top-level is a QPN additionally comprising special places which themselves include HQPN subnets. The lowest levels of the hierarchy are described by QPN subnets which are coloured GSPNs with some additional places including queues. In this paper we describe a new version of the QPN-Tool [4] which supports the specification and analysis of HQPNs. Specification of HQPNs is supported by a graphical interface which allows a convenient specification and the reuse of submodel specifications in one or several models. Analysis can be performed according to qualitative and quantitative aspects using the same model. Qualitative analysis is based on established algorithms for the analysis of Petri nets. QPN-Tool offers standard Petri net algorithms and also very efficient methods based on special net classes [17]. Quantitative analysis can be performed using conventional analysis techniques on the flat Markov chain, which is often preferable for small state spaces up to 50,000 states, or by the hierarchical technique, which allows the analysis of models with several millions of states on standard workstations. For larger models, approximate analysis based on aggregation/disaggregation can be performed.
A variety of other tools have been developed in the last years to support the specification and analysis of stochastically time-augmented Petri nets, e.g.: DSPNexpress [19], GreatSPN [11], SPNP [12], TimeNET [15] and UltraSAN [23]. All these tools provide numerical solution facilities for the underlying Markov chain, some also include simulation. Apart from UltraSAN all tools rely on flat and uncoloured nets. As far as the authors know there exists presently one other tool which supports Markov chain analysis based on a tensor representation of the generator matrix, namely the tool PEPS for the analysis of stochastic automata networks (SANs) [21]. However, SANs are completely different from the model class introduced here since they specify stochastic automata which communicate via synchronised transitions, rather than by asynchronous exchange of entities. There is also work going on to transfer the results for SANs in the GSPN area [14].
The outline of the rest of this paper is as follows. In the next
section we introduce HQPNs in some more detail and briefly explain the
hierarchical analysis approach. The following section is dedicated to
the QPN-Tool version 
. In Sect. 4 a simple example model is
presented to compare the performance of different analysis approaches.