A discrete-event simulation tool for the analysis of simultaneous events

ABSTRACT

Discrete-event simulation is a very popular technique for the performance evaluation of systems, and in widespread use in network simulation tools. It is well known, however, that discrete-event simulation suffers from the problem of simultaneous events: Different execution orders of events with identical timestamps may lead to different simulation results. Current simulation tools apply tie-breaking mechanisms which order simultaneous events for execution. While this is an accepted solution, a legitimate question is: Why should only a single simulation result be selected, and other possible results be ignored?

In this paper, we argue that confidence in simulation results may be increased by analyzing the impact of simultaneous events. We present a branching mechanism which examines different execution orders of simultaneous events, and may be used in conjunction with, or as an alternative to tie-breaking rules. We have developed a new simulation tool, MOOSE, which provides branching mechanisms for both sequential and distributed discrete-event simulation. While MOOSE has originally been developed for network simulation, it is fully usable as a general simulation tool.

REFERENCES

• 1: C. Barz, R. Göpffarth, P. Martini, and A. Wenzel. A new framework for the analysis of simultaneous events. In Proceedings of the 2003 Summer Computer Simulation Conference (SCSC '03), 2003.
• 2: L. Bononi, M. Bracuto, G. D'Angelo, and L. Donatiello. Analysis of high performance communication and computation solutions for parallel and distributed simulation. In Proceedings of the 2005 International Conference on High Performance Computing and Communications (HPCC '05), 2005.
• 3: Dan Chen , Stephen J. Turner , Wentong Cai , Boon Ping Gan , Malcolm Yoke Hean Low, Algorithms for HLA-based distributed simulation cloning, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.4, p.316-345, October 2005 [doi>10.1145/1113316.1113318]
• 4: Bruce A. Cota , Robert G. Sargent, Simultaneous events and distributed simulation, Proceedings of the 22nd conference on Winter simulation, p.436-440, December 09-12, 1990, New Orleans, Louisiana, United States
• 5: Roger Curry , Cameron Kiddle , Rob Simmonds , Brian Unger, Sequential Performance of Asynchronous Conservative PDES Algorithms, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.217-226, June 01-03, 2005 [doi>10.1109/PADS.2005.25]
• 6: DaSSF. version 3.2.5. http://www.crhc.uiuc.edu/~jasonliu/projects/ssf/.
• 7: R. M. Fujimoto. Zero lookahead and repeatability in the high level architecture. In Proceedings of the 1997 Spring Simulation Interoperability Workshop, 1997.
• 8: Richard M. Fujimoto, Parallel and Distribution Simulation Systems, John Wiley & Sons, Inc., New York, NY, 1999
• 9: GloMoSim. version 2.03. http://pcl.cs.ucla.edu/projects/glomosim/.
• 10: GTNetS. http://www.ece.gatech.edu/research/labs/MANIACS/GTNetS/.
• 11: Maria Hybinette , Richard M. Fujimoto, Cloning parallel simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.11 n.4, p.378-407, October 2001 [doi>10.1145/508366.508370]
• 12: J-Sim. version 1.3. http://www.j-sim.org/.
• 13: Vikas Jha , Rajive Bagrodia, Simultaneous events and lookahead in simulation protocols, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.10 n.3, p.241-267, July 2000 [doi>10.1145/361026.361032]
• 14: JiST/SWANS. version 1.0.6. http://jist.ece.cornell.edu/.
• 15: Cameron Kiddle , Rob Simmonds , Brian Unger, Channel based sequential simulation, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
• 16: H. Mehl. A deterministic tie-breaking scheme for sequential and distributed simulation. In Proceedings of the 6th Workshop on Parallel and Distributed Simulation (PADS '92), 1992.
• 17: MOOSE - Module-based Object-Oriented Simulation Environment. http://web.cs.uni-bonn.de/IV/MOOSE/.
• 18: NCTUns. version 3.0. http://nsl.csie.nctu.edu.tw/nctuns.html.
• 19: Ns-2. http://www.isi.edu/nsnam/ns/.
• 20: OMNET++. version 3.4b2. http://www.omnetpp.org/.
• 21: ParSec. version 1.1. http://pcl.cs.ucla.edu/projects/parsec/.
• 22: PDNS. version 2.27.la. http://www.cc.gatech.edu/computing/compass/pdns/.
• 23: Patrick Peschlow , Tobias Honecker , Peter Martini, A Flexible Dynamic Partitioning Algorithm for Optimistic Distributed Simulation, Proceedings of the 21st International Workshop on Principles of Advanced and Distributed Simulation, p.219-228, June 12-15, 2007 [doi>10.1109/PADS.2007.6]
• 24: P. Peschlow and P. Martini. Analyzing simultaneous events in distributed simulation. In Proceedings of the 19th European Modeling and Simulation Symposium (EMSS '07), October 2007.
• 25: Patrick Peschlow , Peter Martini, Efficient Analysis of Simultaneous Events in Distributed Simulation, Proceedings of the 11th IEEE International Symposium on Distributed Simulation and Real-Time Applications, p.244-251, October 22-26, 2007 [doi>10.1109/DS-RT.2007.24]
• 26: Robert Rönngren , Michael Liljenstam, On event ordering in parallel discrete event simulation, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.38-45, May 01-04, 1999, Atlanta, Georgia, United States
• 27: Thomas J. Schriber , Daniel T. Brunner, Inside discrete-event simulation software: how it works and why it matters, Proceedings of the 38th conference on Winter simulation, December 03-06, 2006, Monterey, California
• 28: SWAN. version 1.0.1a. http://www.eg.bucknell.edu/swan/.
• 29: TCP. Transmission Control Protocol (RFC 793), 1981.
• 30: Xiaoguang Wang , Stephen John Turner , Simon J. E. Taylor, COTS Simulation Package (CSP) Interoperability -A Solution to Synchronous Entity Passing, Proceedings of the 20th Workshop on Principles of Advanced and Distributed Simulation, p.201-210, May 24-26, 2006 [doi>10.1109/PADS.2006.13]
• 31: A. Wenzel. Experiences with simultaneous events using discrete-event simulation. In Proceedings of the IASTED International Conference on Modeling and Simulation, 1999.
• 32: Frederick Wieland, The threshold of event simultaneity, Proceedings of the eleventh workshop on Parallel and distributed simulation, p.56-59, June 10-13, 1997, Lockenhaus, Austria