5th International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Hierarchically constructed Petri-nets and product-forms

Download113 downloads
  • @INPROCEEDINGS{10.4108/icst.valuetools.2011.245746,
        author={Peter Harrison and Catalina Llado},
        title={Hierarchically constructed Petri-nets and product-forms},
        proceedings={5th International ICST Conference on Performance Evaluation Methodologies and Tools},
        keywords={Petri nets product-forms performance modelling interchange formats RAID systems},
  • Peter Harrison
    Catalina Llado
    Year: 2012
    Hierarchically constructed Petri-nets and product-forms
    DOI: 10.4108/icst.valuetools.2011.245746
Peter Harrison1,*, Catalina Llado2
  • 1: Imerial College London
  • 2: Universitat de les Illes Balears
*Contact email: pgh@doc.ic.ac.uk


Stochastic Petri nets (SPNs) provide a convenient, diagrammatic description of concurrent systems, such as computer and communication networks, and can represent quantitative (or performance) aspects such as mean response times and probability of failure. Such models can be supported by performance modelling interchange formats (PMIFs), facilitating sharing and model interoperability. We propose a hierarchical method for constructing a large class of Petri nets, which preserves efficient product-form solutions when they exist. This scalable approach greatly improves the efficiency of finding steady state probabilities in a wide range of SPNs, making much larger SPNs feasible. An existing PMIF is extended by including a new type of node that describes a particular type of small Petri net, called a ``building block'', the synchronisation primitives for which can be used to specify task-spawning and task-gathering, whilst retaining product-form solutions under specified conditions. When there is no product-form, the whole network is translated into a Petri net and solved directly -- either by a Markov chain solver or by simulation. The extended PMIF and the proposed methodology are applied to a model of a computer system with RAID storage.