More Web Proxy on the site http://driver.im/

research-article

Performance Analysis of Stochastic Timed Petri Nets Using Linear Programming Approach

Author:

Zhen LiuAuthors Info & Claims

IEEE Transactions on Software Engineering, Volume 24, Issue 11

Pages 1014 - 1030

https://doi.org/10.1109/32.730548

Published: 01 November 1998 Publication History

Abstract

Stochastic timed Petri nets are a useful tool in performance analysis of concurrent systems such as parallel computers, communication networks, and flexible manufacturing systems. In general, performance measures of stochastic timed Petri nets are difficult to obtain for practical problems due to their sizes. In this paper, we provide a method to compute efficiently upper and lower bounds for the throughputs and mean token numbers for a large class of stochastic timed Petri nets. Our approach is based on uniformization technique and linear programming.

References

[1]

M. Ajmone Marsan G. Balbo A. Bobbio G. Chiola G. Conte A. Cumani, "The Effect of Execution Policies on the Semantics and Analysis of Stochastic Petri Nets," IEEE Trans. Software Eng., vol. 15, pp. 832-846, 1989.

Digital Library

[2]

M. Ajmone Marsan G. Balbo and G. Conte, "A Class of Generalized Stochastic Petri Nets for the Performance Analysis of Multiprocessor Systems," ACM Trans. Computer Systems, vol. 2, no. 1, May 1984.

Digital Library

[3]

M. Ajmone Marsan G. Balbo and G. Conte, Performance Models of Multiprocessor Systems. Cambridge, Mass.: MIT Press, 1986.

Digital Library

[4]

F. Baccelli, "Ergodic Theory of Stochastic Petri Nets," The Annals of Probability, vol. 20, pp. 375-396, 1992.

[5]

F. Baccelli G. Balbo R.J. Boucherie J. Campos and G. Chiola, "Annotated Bibliography on Stochastic Petri Nets," Performance Evaluation of Parallel and Distributed Systems—Solution Methods, O.J. Boxma and G.M. Koole, eds., CWI Tract 105 & 106. Amsterdam: CWI, 1994.

[6]

F. Baccelli and P. Bremaud, Elements of Queueing Theory. Berlin: Springer-Verlag, 1994.

[7]

F. Baccelli and M. Canales, "Parallel Simulation of Stochastic Petri Nets Using Recursive Equations," ACM Trans. Machines and Computer Systems, vol. 3, pp. 20-41, 1993.

Digital Library

[8]

F. Baccelli G. Cohen and B. Gaujal, "Recursive Equations and Basic Properties of Timed Petri Nets," J. Discrete Event Systems, vol. 1, pp. 415-439, 1992.

[9]

F. Baccelli S. Foss and B. Gaujal, "Free Choice Nets, An Algebraic Approach," IEEE Trans, Automatic Control, vol. 41, pp. 1,751-1,778, 1996.

[10]

F. Baccelli A. Jean-Marie and Z. Liu, "A Survey on Solution Methods for Task Graph Models," Second QMIPS Workshop, N. Götz, U. Herzog, and M. Rettelbach, eds., vol. 26, no. 14, pp. 163-183, Arbeitsberichte der IMMD, Erlangen, 1993.

[11]

Quantitative Methods in Parallel Systems, F. Baccelli, A. Jean-Marie, and I. Mitrani, eds. Springer-Verlag, 1995.

Digital Library

[12]

F. Baccelli and P. Konstantopoulos, "Estimates of Cycle Times in Stochastic Petri Nets," Lecture Notes in Control and Information Sciences, vol. 177, pp. 1-21. Springer-Verlag, 1992.

[13]

O.J. Boxma G.M. Koole and Z. Liu, "Queueing-Theoretic Solution Methods for Models of Parallel and Distributed Systems," Performance Evaluation of Parallel and Distributed Systems—Solution Methods, O.J. Boxma and G.M. Koole, eds., CWI Tract 105 & 106. Amsterdam: CWI, 1994.

[14]

F. Baccelli and Z. Liu, "Comparison Properties of Stochastic Decision Free Petri Nets," IEEE Trans. Automatic Control, vol. 37, pp. 1,905-1,920, 1992.

[15]

F. Baccelli Z. Liu and M. Silva, "Global and Local Monotonicities of Stochastic Petri Nets," in preparation.

[16]

F. Baccelli and A.M. Makowski, "Queueing Models for Systems with Synchronization Constraints," Proc. IEEE, vol. 77, pp. 138-161, 1989.

[17]

D. Bertsimas I. Paschalidis and J. Tsitsiklis, "Optimization of Multiclass Queueing Networks: Polyhedral and Nonlinear Characterizations of Achievable Performance," Annals of Applied Probability, vol. 4, pp. 43-73, 1994

[18]

D. Bertsimas I. Paschalidis and J. Tsitsiklis, "Branching Bandits and Klimov's Problem: Achievable Region and Side Constraints," IEEE Trans. Automatic Control, vol. 40, pp. 2,063-2,075, 1995.

[19]

R.J. Boucherie, "A Characterisation of Independence for Competing Markov Chains with Applications to Stochastic Petri Nets," Proc. Petri Nets and Performance Models, 1993.

[20]

J.P. Buzen, "A Computational Algorithm for Closed Queueing Networks with Exponential Servers." Comm. ACM, vol. 14, pp. 527-531, 1973.

Digital Library

[21]

J. Campos G. Chiola and M. Silva, "Ergodicity and Throughput Bounds of Petri Nets with Unique Consistent Firing Count Vector," IEEE Trans. Software Eng., vol. 17, no. 2, pp. 117-125, Feb. 1991.

Digital Library

[22]

J. Campos G. Chiola and M. Silva, "Properties and Performance Bounds for Closed Free Choice Synchronized Monoclass Queueing Networks," IEEE Trans. Automatic Control, vol. 36, pp. 1,368-1,382, Dec. 1991.

[23]

J. Campos J.M. Colom H. Jungnitz and M. Silva, "A General Iterative Technique for Approximate Throughput Computation of Stochastique Marked Graphs," Proc. Fifth Int'l Workshop Petri Nets and Performance Models, pp. 138-147, Toulouse, France, Oct. 1993.

[24]

J. Campos B. Sánchez and M. Silva, "Throughput Lower Bounds for Markovian Petri Nets: Transformation Techniques," Proc. Fourth Int'l Workshop Petri Nets and Performance Models, pp. 322-331, Melbourne, Australia, Dec. 1991.

[25]

J. Campos and M. Silva, "Embedded Product-Form Queueing Networks and the Improvement of Performance Bounds for Petri Net Systems," Performance Evaluation, vol. 18, pp. 3-19, 1993.

Digital Library

[26]

K.M. Chandy and C.H. Sauer, "Computational Algorithms for Product Form Queueing Networks," Comm. ACM, vol. 23, pp. 573-583, 1980.

Digital Library

[27]

G. Chiola, "GreatSPN 1.5 Software Architecture," Proc. Fifth Int'l Conf. Modeling Techniques and Tools for Computer Performance Evaluation, Torino, Italy, Feb. 1991.

[28]

G. Chiola M. Ajmone Marsan G. Balbo and G. Conte, "Generalized Stochastic Petri Nets: A Definition at the Net Level and Its Implications," IEEE Trans. Software Eng., vol. 19, pp. 89-107, Feb. 1993.

Digital Library

[29]

G. Chiola C. Anglano J. Campos J.M. Colom and M. Silva, "Operational Analysis of Timed Petri Nets and Application to the Computation of Performance Bounds," Proc. Fifth Int'l Workshop Petri Nets and Performance Models, pp. 128-137, Toulouse, France, Oct. 1993.

[30]

G. Chiola S. Donatelli and G. Franceschinis, "GSPN versus SPN: What Is the Actual Role of Immediate Transitions?" Proc. Fourth Int'l Workshop Petri Nets and Performance Models, pp. 20-31, Melbourne, Australia, Dec. 1991.

[31]

G. Ciardo J. Muppala and K.S. Trivedi, "SPNP: Stochastic Petri Net Package," Proc. Third Int'l Workshop Petri Nets and Performance Models, Kyoto, Japan, Dec. 1989.

Digital Library

[32]

Y. Dallery Z. Liu and D. Towsley, "Equivalence, Reversibility and Symmetry Properties in Assembly/Disassembly Networks," J. ACM., vol. 41, no. 5, pp. 903-942, 1994.

Digital Library

[33]

Y. Dallery Z. Liu and D. Towsley, "Properties of Fork/Join Queueing Networks with Blocking Under Various Operating Mechanisms," IEEE Trans. Robotics and Automation, vol. 13, no. 4, pp. 503-518, Aug. 1997.

[34]

J. Desel and J. Esparza, Free Choice Petri Nets. Cambridge Univ. Press, 1995.

Digital Library

[35]

J.B. Dugan K.S. Trivedi R.M. Geist and V.F. Nicola, "Extended Stochastic Petri Nets: Applications and Analysis," Proc. PERFORMANCE'84, Paris, Dec. 1984.

Digital Library

[36]

G. Florin and S. Natkin, "Les réseaux de Petri stochastiques," Technique et Science Informatiques, vol. 4, Feb. 1985.

[37]

B. Gaujal, "Liveness in Weighted Routed Nets," INRIA Research Report No. 2899, 1996.

[38]

C. Hanen and A. Munier, "Cyclic Scheduling on Parallel Processors: An Overview," Scheduling Theory and Its Applications, P. Chretienne et al., eds., John Wiley & Sons, 1995.

[39]

A. Jean-Marie S. Lefebvre-Barbaroux and Z. Liu, "An Analytical Approach to the Performance Evaluation of Master-Slave Computational Models," Parallel Computing, vol. 24, nos. 4-5, 1998.

Digital Library

[40]

N.D. Jones L.H. Landweber and Y. E Lien, "Complexity of Some Problems in Petri Nets," Theoretical Computer Science, vol. 4, pp. 277-299, 1977.

[41]

J. Keilson, Markov Chain Models|Rarity and Exponentiality. Springer-Verlag, 1979.

[42]

S. Kumar and P.R. Kumar, "Performance Bounds for Queueing Networks and Scheduling Policies," IEEE Trans. Automatic Control, vol. 39, pp. 1,600-1,611, 1994.

[43]

P.R. Kumar and S.P. Meyn, "Stability of Queueing Networks and Scheduling Policies," IEEE Trans. Automatic Control, vol. 40, pp. 251-260, 1995.

[44]

Y. Li and C.M. Woodside, "Complete Decomposition of Stochastic Petri Nets Representing Generalized Service Networks," IEEE Trans. Computers, vol. 44, pp. 577-592, 1995.

Digital Library

[45]

Z. Liu, "Performance Bounds for Stochastic Timed Petri Nets," Proc. 16th Int'l Conf. Applications and Theory of Petri Nets, Torino, Italy, 1995.

Digital Library

[46]

Z. Liu, "Performance Analysis of Stochastic Timed Petri Nets using Linear Programming Approach," INRIA Research Report No. 2642, 1995.

[47]

M.K. Molloy, "Performance Analysis using Stochastic Petri Nets," IEEE Trans. Computers, vol. 31, no. 9, pp. 913-917, Sept. 1982.

Digital Library

[48]

T. Murata, "Petri Nets: Properties, Analysis and Applications," Proc. IEEE, vol. 77, pp. 541-580, 1989.

[49]

M. Neuts, Matrix-Geometric Solutions in Stochastic Models. Baltimore, Md.: Johns Hopkins, 1981.

[50]

M. Reiser and H. Kobayashi, "Queueing Networks with Multiple Closed Chains: Theory and Computational Algorithms." IBM J. Research and Development, vol. 19, pp. 283-294, 1975.

Digital Library

[51]

M. Reiser and S.S. Lavenberg, "Mean-Value Analysis of Closed Multichain Queueing Networks,." J. ACM, vol. 27, pp. 313-322, 1980.

Digital Library

[52]

S. Stidham, "A Last Word on L = λW," Operations Research, vol. 22, pp. 417-421, 1974.

Digital Library

[53]

E. Teruel P. Chrzastowski-Watchel J.M. Colom and M. Silva, "On Weighted T-Systems," Proc. Application and Theory of Petri Nets, K. Jensen, ed., 1992.

Digital Library

[54]

E. Teruel and M. Silva, "Well-Formedness of Equal Conflict Systems," Application and Theory of Petri Nets, R. Valette ed., 1994.

Digital Library

Cited By

Júlvez JCortadella JKishinevsky M(2018)On the Performance Evaluation of Multi-Guarded Marked Graphs with Single-Server SemanticsDiscrete Event Dynamic Systems10.1007/s10626-009-0079-220:3(377-407)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10626-009-0079-2
Mir UMerghem-Boulahia LGaïti D(2010)COMASEURASIP Journal on Wireless Communications and Networking10.1155/2010/9876912010(1-15)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1155/2010/987691
Chen JYang Y(2005)Flexible temporal consistency for fixed-time constraint verification in grid workflow systemsProceedings of the 4th international conference on Grid and Cooperative Computing10.1007/11590354_41(300-311)Online publication date: 30-Nov-2005
https://dl.acm.org/doi/10.1007/11590354_41

Index Terms

Performance Analysis of Stochastic Timed Petri Nets Using Linear Programming Approach

Recommendations

Discrete Time Stochastic Petri Nets

Basic graph models of processes, such as Petri nets, have usually omitted the concept of time as a parameter. Time has been added to the Petri net model in two ways. The timed Petri net (TPN) uses a fixed number of discrete time intervals. The ...
From Stochastic Petri Nets to Markov Regenerative Stochastic Petri Nets
MASCOTS '95: Proceedings of the 3rd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems

In this paper we survey the Petri net literature and focus on Petri nets with generally distributed transition firing times. In the framework of Markov regenerative stochastic Petri nets (MRSPN) we develop and solve two examples to illustrate the ...
Performance Analysis Using Stochastic Petri Nets

An isomorphism between the behavior of Petri nets with exponentially distributed transition rates and Markov processes is presented. In particular, k-bounded Petri nets are isomorphic to finite Markov processes and can be solved by standard techniques ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Software Engineering

IEEE Transactions on Software Engineering Volume 24, Issue 11

November 1998

137 pages

ISSN:0098-5589

Editors:
Richard A. Kemmerer
Univ. of California, Santa Barbara
,
Carlos Ghezzi
Politecnico di Milano, Milano, Italia

Issue’s Table of Contents

Copyright © Copyright © 1998 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 November 1998

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Júlvez JCortadella JKishinevsky M(2018)On the Performance Evaluation of Multi-Guarded Marked Graphs with Single-Server SemanticsDiscrete Event Dynamic Systems10.1007/s10626-009-0079-220:3(377-407)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10626-009-0079-2
Mir UMerghem-Boulahia LGaïti D(2010)COMASEURASIP Journal on Wireless Communications and Networking10.1155/2010/9876912010(1-15)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1155/2010/987691
Chen JYang Y(2005)Flexible temporal consistency for fixed-time constraint verification in grid workflow systemsProceedings of the 4th international conference on Grid and Cooperative Computing10.1007/11590354_41(300-311)Online publication date: 30-Nov-2005
https://dl.acm.org/doi/10.1007/11590354_41

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents