IRUS Total

Automated Customer-Centric Performance Analysis of Generalised Stochastic Petri Nets Using Tagged Tokens

File Description SizeFormat 
entcs-paper.pdfAccepted version794.74 kBAdobe PDFView/Open
Title: Automated Customer-Centric Performance Analysis of Generalised Stochastic Petri Nets Using Tagged Tokens
Authors: Knottenbelt, W
Dingle, N
Item Type: Journal Article
Abstract: Since tokens in Generalised Stochastic Petri Net (GSPN) models are indistinguishable, it is not always possible to reason about customer-centric performance measures. To remedy this, we propose tagged tokens - a variant of the tagged customer technique used in the analysis of queueing networks. Under this scheme, one token in a structurally restricted net is tagged and its position tracked as it moves around the net. Performance queries can then be phrased in terms of the position of the tagged token. To date, the tagging of customers or tokens has been a time-consuming, manual and model-specific process. By contrast, we present here a completely automated methodology for the tagged token analysis of GSPNs. We first describe an intuitive graphical means of specifying the desired tagging configuration, along with the constraints on GSPN structure which must be observed for tagged tokens to be incorporated. We then present the mappings required for automatically converting a GSPN with a user-specified tagging structure into a Coloured GSPN (CGSPN), and thence into an unfolded GSPN which can be analysed for performance measures of interest by existing tools. We further show how our methodology integrates with Performance Trees, a formalism for the specification of performance queries. We have implemented our approach in the open source PIPE Petri net tool, and use this to illustrate the extra expressibility granted by tagged tokens through the analysis of a GSPN model of a hospitals Accident and Emergency department. © 2009 Elsevier B.V. All rights reserved.
Issue Date: 26-Mar-2009
Citation: Electronic Notes in Theoretical Computer Science Vol.( 232 ) No.( ) pp 75 - 88
URI: http://hdl.handle.net/10044/1/5767
Publisher Link: http://dx.doi.org/10.1016/j.entcs.2009.02.051
ISSN: 1571-0661
Publisher: Elsevier
Start Page: 75
End Page: 88
Copyright Statement: © 2009 Elsevier B.V. All rights reserved. NOTICE: this is the author’s version of a work that was accepted for publication in Electronic Notes in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, VOL:232,(2009) DOI:10.1016/j.entcs.2009.02.051
Volume: 232
Appears in Collections:High Performance Informatics