Christian Kelling
ABSTRACT
For the performability evaluation of complex systems simulation remains often the only feasible method. Unfortunately, simulation experiments tend to be very time consuming if rare events have to be considered. This paper describes an algorithmic approach for fast simulation of rare events applied in a Petri net modeling environment. The technique is based on the RESTART method, which is applicable for rare events in a wide range of simulation models, and has the potential to reduce the simulation overhead extremely. The paper presents selection and refinement techniques for the most important input parameters of RESTART. The techniques allow an efficient execution of RESTART simulations especially in a flexible evaluation tool. The results show run length reductions up to six orders of magnitude.
- Bayes, A.J. 1972. A Minimum Variance Samp}Ling Technique for Simulation Models, Journal of the ACM 19: 734-741. Google Scholar
Digital Library
- Blondia, C. 1992. Performance Evaluation on an M/I- Stage in an ATM Switching Element. Performance Evaluation 15(1): 1-20. Google ScholarDigital Library
- Buchholz, P. and P. Kemper 1995. Numerical Analysis of Stochastic Marked Graph Nets. In Proc of the Sixt Int. Workshop on Petri Nets and Performance Models, Durham, North Carolina, USA, IEEE Press: 32-41. Google ScholarDigital Library
- Ciardo, G. and K. S. Trivedi 1993. A Decomposition Approach for Stochastic Reward Net Models. Performance Evaluation 18(1): 37-59. Google ScholarDigital Library
- Ciardo, G., R. German, and C. Lindemann 1994. A Characterization of the Stochastic Process Underlying a Stochastic Petri Net. Trans. on Softw. Eng., 20(7): 506- 515. Google ScholarDigital Library
- German, R., C. Kelling, A. Zimmermann and G. Hommel 1995. TimeNET- A Toolkit for Evaluating Non-Markovian Stochastic Petri Nets. Performance Evaluation 24 (1995): 69-87. Google ScholarDigital Library
- Heidelberger, P.1995. Fast Simulation of Rare Events in Queueing and Reliability Models. A CM Transactions on Modeling and Computer Simulation, 5(1): 43--85. Google ScholarDigital Library
- Hopmans, A.C.M. and J.P.C. Kleijnen 1979. Importance Sampling in Systems Simulation: A Practical Failure. In Mathematics and Computing in Simulation XXI. North- Holland: 209-220.Google ScholarCross Ref
- Kelling, C. 1995(a). TimeNET-Sim - a Parallel Simulator for Stochastic Petri Nets. In Proc. of the 28th Annual Simulation Symposium, Phoenix, AZ, USA, IEEE Press: 250-258. Google ScholarDigital Library
- Kelling, C. 1995(b). Rare Event Simulation with REST- ART in a Petri Net Modeling Environment. In Proc of the 1995 European Simulation Symposium, Erlangen, Germany. SCS: 370-374.Google Scholar
- Lucantoni, D. 1993. The BMAP/G/1-Queue: A Tutorial. In Models and Techniques for the Performance Evaluation of Computer and Communications Systems. L. Donatiello and R. Nelson. Berlin, Springer Verlag: 330- 358. Google ScholarDigital Library
- Obal, W. D. and W. H. Sanders 1994. Importance Sampiing Simulation in UltraSAN. Simulation 62(2): 98- 111.Google ScholarCross Ref
- Vill6n-Altamirano, M. and j. Vill6n-Altamirano 1991. RESTART: A Method for Accelerating Rare Event Simulations. In Queueing Performance and Control in ATM (ITC-13). J. W. Cohen and C. D. Pack, Elsevier Science Publishers B. V. (North-Holland): 71-76.Google Scholar
- Vill6n-Altamirano, M. and J. Vill6n-Altamirano 1994. Enhancement of the Accelerated Simulation Method RESTART by Considering Multiple Thresholds. In ITC-14. J. Labetoulle and J. W. Roberts, Elsevier Science Publishers B. V. (North-Holland): 797-810.Google Scholar
- Wilson, J.R. 1984. Variance Reduction Techniques for Digital Simulation. American Journal on Mathematics in Managment Science, 4(3, 4): 277-312.Google Scholar
- Ziegler, P. and H. Szczerbicka 1995. A Structure Based Decomposition Approach for GSPN. In Proc of the Sixt Int. Workshop on Petri Nets and Performance Models, Durham, North Carolina, USA, IEEE Press: 261-270. Google ScholarDigital Library
Recommendations
Rare Event Simulation with an Adaptive RESTART Method in a Petri net Modeling Environment
WPDRTS '96: Proceedings of the 4th International Workshop on Parallel and Distributed Real-Time SystemsFor the performability evaluation of complex soft real-time systems simulation often remains the only feasible method. Simulation experiments tend to be very time consuming if rare events have to be considered. This paper describes a fast simulation ...
Efficient Discrete-Event Simulation of Colored Petri Nets
Special issue: best papers of the sixth international workshop on Petri nets and performance models (PNPM'95)Colored Petri nets are a powerful formalism for the description of complex, asynchronous distributed systems. They can express in a very concise way the behavior of very large systems, especially in case these systems are composed of many replications ...
The rare event simulation method RESTART: efficiency analysis and guidelines for its application
Network performance engineeringThis paper is a tutorial on RESTART, a widely applicable accelerated simulation technique for estimating rare event probabilities. The method is based on performing a number of simulation retrials when the process enters regions of the state space where ...
Comments