Abstract
If in stochastic modeling the idealized assumption of exponential distributions is removed, the resulting stochastic process is non-Markovian. In this tutorial paper we give an overview of possible analytic approaches for such non-Markovian models. The modeling framework of stochastic Petri nets is used, but the ideas are applicable to other frameworks as well, if a state space can be constructed. We give a detailed presentation of one analysis approach which is based on the method of supplementary variables and give a brief review of another analysis approach which is based on embedding. A model of a timer for holding a connection is used as a tutorial example and a model for a medium access mechanism in wireless networks is used as a more complex example.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G. Balbo. Introduction to stochastic Petri nets. This volume.
A. Bobbio, V.G. Kulkarni, A. Puliafito, M. Telek, and K. Trivedi. Preemptive repeat identical transitions in Markov regenerative stochastic Petri nets. In Proc. 6th Int. Conf. on Petri Nets and Performance Models, pages 113–122, Durham, NC, 1995.
A. Bobbio, A. Puliafito, M. Telek, and K.S. Trivedi. Recent developments in non-Markovian stochastic Petri nets. Journal of Systems Circuits and Computers, 8(1):119–158, 1998.
A. Bobbio and M. Telek. Markov regenerative SPN with non-overlapping activity cycles. In Proc. Int. Performance and Dependability Symp., pages 124–133, Erlangen, Germany, 1995.
R. M.L.R. Carmo, L.R. de Carvalho, E. de Souza e Silva, M.C. Diniz, and R.R. Muntz. Performance/availability modeling with the TANGRAM-II modeling environment. Perf. Eval., 33:45–65, 1998.
H. Choi, V.G. Kulkarni, and K.S. Trivedi. Markov regenerative stochastic Petri nets. Performance Evaluation, 20:337–357, 1994.
G. Ciardo. Discrete-time Markovian stochastic Petri nets. In W. Stewart, editor, Numerical Solution of Markov Chains, pages 339–358, Raleigh, NC, 1995. Kluwer.
G. Ciardo and A.S. Miner. SMART simulation and Markovian analyzer for reliability and timing. In Multi-Workshop on Formal Methods in Performance Evaluation and Applications, Tool Descriptions. Zaragoza, Spain, 1999.
J. Couvillion, R. Freire, R. Johnson, Obal W.D. II, M.A. Qureshi, M. Rai, W.H. Sanders, and J. Tvedt. Performability modeling with UltraSAN. IEEE Software, 8:69–80, 1991.
A. Cumani. ESP-a package for the evaluation of stochastic Petri nets with phasetype distributed transition times. In Proc. Int. Workshop Timed Petri Nets, pages 278–184, Turin, Italy, 1985.
D. Daly, D.D. Deavours, J.M. Doyle, P.G. Webster, and W.H. Sanders. Möbius: An extensible framework for performance and dependability modeling. In Computer Performance Evaluation, Modeling Techniques and Tools, volume 1786 of LNCS, pages 332–336. Springer-Verlag, 2000. 11th Int. Conference, TOOLS 2000.
J. Freiheit, A. Zimmermann, R. German, and G. Hommel. Petri net modeling and performability evaluation with TimeNET 3.0. In Computer Performance Evaluation, Modeling Techniques and Tools, volume 1786 of LNCS, pages 188–202. Springer-Verlag, 2000. 1th Int. Conference, TOOLS 2000.
R. Fricks, C. Hirel, S. Wells, C.W. Ro, X. Zhang, and K.S. Trivedi. IDEAS: an integrated design environment for assessment of computer systems and communication networks. Technical report, Duke University, 1998.
R. German. Cascaded deterministic and stochastic Petri nets. In Proc. 3rd Int. Meeting on the Numerical Solution of Markov Chains, pages 111–130, Zaragoza, Spain, 1999.
R. German. Markov regenerative stochastic Petri nets with general execution policies: Supplementary variable analysis and a prototype tool. Performance Evaluation, 39:165–188, 2000.
R. German. Performance Analysis of Communication Systems: Modeling with Non-Markovian Stochastic Petri Nets. John Wiley and Sons, 2000.
R. German. Iterative analysis of Markov regenerative models. Journal of Performance Evaluation, 2001. To appear.
R. German, C. Kelling, A. Zimmermann, and G. Hommel. TimeNET: A toolkit for evaluating non-Markovian stochastic Petri nets. Performance Evaluation, 24:69–87, 1995.
R. German and C. Lindemann. Analysis of stochastic Petri nets by the method of supplementary variables. Performance Evaluation, 20:317–335, 1994.
R. German and M. Telek. Formal relation of Markov renewal theory and supplementary variables in the analysis of stochastic Petri nets. In Proc. 8th Int. Workshop on Petri Nets and Performance Models, pages 64–73, Zaragoza, Spain, 1999.
S. Haddad, P. Moreaux, and G. Chiola. Efficient handling of phase-type distributions in generalized stochastic Petri nets. In Application and Theory of Petri Nets 1997, Proc. 18th Int. Conf., pages 175–194. Springer-Verlag, 1997.
B. Haverkort. Performance of Computer Communication Systems: A Model-Based Approach. John Wiley, 1998.
B.R. Haverkort. Markovian models for performance and dependability evaluation. This volume.
B.R. Haverkort. Matrix-geometric solution of infinite stochastic Petri nets. In Proc. IEEE Int. Performance and Dependability Symp., pages 72–81, Erlangen, Germany, 1995.
A. Heindl and R. German. Performance modeling of IEEE 802.11 wireless LANs with stochastic Petri nets. Journal of Performance Evaluation, 2001. To appear.
A. Horvath, A. Puliafito, M. Scarpa, and M. Telek. Analysis and evaluation of non-Markovian stochastic Petri nets. In Computer Performance Evaluation, Modeling Techniques and Tools, volume 1786 of LNCS, pages 171–187. Springer-Verlag, 2000. 11th Int. Conference, TOOLS 2000.
IEEE. 802.11: IEEE Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, November 1997.
R. Jones. Analysis of phase-type stochastic Petri nets with discrete and continuous timing. Technical Report NASA/CR-2000-210296, NASA Langley Research Center, Hampton, VA, USA, 2000.
L. Kleinrock. Queueing Systems, volume I. John Wiley, 1975.
C. Lindemann. DSPNexpress: A software package for the efficient solution of deterministic and stochastic Petri nets. Performance Evaluation, 22:3–21, 1995.
C. Lindemann. Performance Modeling with Deterministic and Stochastic Petri Net. John Wiley, 1998.
C. Lindemann and G. Shedler. Numerical analysis of deterministic and stochastic Petri nets with concurrent deterministic transitions. Performance Evaluation, 23:565–582, 1996.
M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli, and G. Franceschinis. Modelling with Generalized Stochastic Petri Nets. John Wiley, 1995.
M. Ajmone Marsan and G. Chiola. On Petri nets with deterministic and exponentially distributed firing times. In Advances in Petri Nets 1986, LNCS 266, pages 132–145. Springer-Verlag, 1987.
M.F. Neuts. Matrix-Geometric Solutions in Stochastic Models. John Hopkins University Press, 1981.
M.F. Neuts. Structured Stochastic Matrices of M/G/1_Type and Their Applications. Marcel Dekker, New York, 1989.
A. Puliafito, M. Scarpa, and K.S. Trivedi. Petri nets with k simultaneously enabled generally distributed timed transitions. Performance Evaluation, 32(1):1–34, 1998.
R.A. Sahner, K.S. Trivedi, and A. Puliafito. Performance and Reliability Analysis of Computer Systems: An Example-Based Approach Using the SHARPE Software Package. Kluwer Academic, 1996.
W.H. Sanders, Obal W.D.II, M.A. Qureshi, and F. K. Widjanarko. The Ultra-SAN modeling environment. Performance Evaluation, 24:89–115, 1995.
M. Scarpa and A. Bobbio. Kronecker representation of stochastic Petri nets with discrete and continuous PH distributions. In Proc. 3rd IEEE Int. Performance and Dependability Symp., Durham, NC, 1998.
M. Telek and A. Bobbio. Markov regenerative stochastic Petri nets with age type general transitions. In Application and Theory of Petri Nets, Proc. 16th Int. Conf., LNCS 935, pages 471–489. Springer-Verlag, 1995.
M. Telek, A. Bobbio, L. Jereb, A. Puliafito, and K.S. Trivedi. Steady state analysis of Markov regenerative SPN with age memory policy. In Quantitative Evaluation of Computing and Communication Systems, LNCS 977, pages 165–179. Springer-Verlag, 1995.
M. Telek, A. Bobbio, and A. Puliafito. Steady state solution of MRSPNs with mixed preemption policies. In Proc. 2nd IEEE Int. Performance and Dependability Symp., pages 106–115, Urbana-Champaign, IL, 1996.
M. Telek and A. Horvath. Supplementary variable approach applied to the transient analysis of age-MRSPNs. In Proc. 3rd IEEE Int. Performance and Dependability Symp., pages 44–51, Durham, NC, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
German, R. (2001). Non-Markovian Analysis. In: Brinksma, E., Hermanns, H., Katoen, JP. (eds) Lectures on Formal Methods and PerformanceAnalysis. EEF School 2000. Lecture Notes in Computer Science, vol 2090. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44667-2_4
Download citation
DOI: https://doi.org/10.1007/3-540-44667-2_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42479-6
Online ISBN: 978-3-540-44667-5
eBook Packages: Springer Book Archive