Towards performance evaluation of conservative distributed discrete-event network simulations using second-order simulation

ABSTRACT

Whether a given simulation model of a computer network will benefit from parallelization is difficult to determine in advance, complicated by the fact that hardware properties of the simulation execution environment can substantially affect the execution time of a given simulation. We describe SONSim, an approach to predict the execution time based on a simulation of an envisioned distributed network simulation (second-order simulation). SONSim takes into account both network model characteristics and hardware properties of the simulation execution environment. To show that a SONSim prototype is able to predict distributed performance with acceptable accuracy, we study three reference network simulation models differing fundamentally in topology and levels of model detail - simple topologies comprised of interconnected subnetworks, peer-to-peer networks and wireless networks. We evaluate the performance predictions for multiple configurations by comparing predictions for the three reference network models to execution time measurements of distributed simulations on physical hardware using both Ethernet and InfiniBand interconnects. In addition, utilizing the freedom to vary simulation hardware and model parameters in the second-order simulation, we demonstrate how SONSim can be used to identify general model characteristics that determine distributed simulation performance.

References

1. P. Andelfinger, J. Mittag, and H. Hartenstein. GPU-Based Architectures and Their Benefit for Accurate and Efficient Wireless Network Simulations. In 19th Int'l Symp. on Modeling, Analysis and Simulation of Comp. and Telecomm. Systems, pages 421--424, 2011.
2. R. Bagrodia and M. Takai. Performance Evaluation of Conservative Algorithms in Parallel Simulation Languages. IEEE Transactions on Parallel and Distributed Systems, pages 395--411, 2000.
3. R. L. Bagrodia. Perils and Pitfalls of Parallel Discrete-Event Simulation. In Proc. of the 28th Winter Simulation Conference, pages 136--143. IEEE Computer Society, 1996.
4. O. Balci. The Implementation of Four Conceptual Frameworks for Simulation Modeling in High-Level Languages. In Proceedings of the Winter Simulation Conference, pages 287--295, 1988.
5. L. Barriga, R. Ronngren, and R. Ayani. Benchmarking Parallel Simulation Algorithms. In Proceedings of the IEEE First International Conference on Algorithms and Architectures for Parallel Processing, 1995.
6. S. Becker, H. Koziolek, and R. Reussner. Model-Based Performance Prediction with the Palladio Component Model. In Proceedings of the 6th International Workshop on Software and Performance, pages 54--65. ACM, 2007.
7. O. Berry and D. Jefferson. Critical Path Analysis of Distributed Simulation. In Proceedings of the 1985 SCS Multiconference on Distributed Simulation.
8. R. E. Bryant. Simulation of Packet Communication Architecture Computer Systems. Technical report, 1977.
9. K. Chandy and J. Misra. Distributed Simulation: A Case Study in Design and Verification of Distributed Programs. IEEE Transactions on Software Engineering, SE-5(5):440--452, 1979.
10. S. De Munck, K. Vanmechelen, and J. Broeckhove. Revisiting Conservative Time Synchronization Protocols in Parallel and Distributed Simulation. Concurrency and Computation: Practice and Experience, 2013.
11. R. Ewald, J. Himmelspach, A. Uhrmacher, D. Chen, and G. Theodoropoulos. A Simulation Approach to Facilitate Parallel and Distributed Discrete-Event Simulator Development. In IEEE Int'l Symposium on Distr. Simulation and Real-Time Applications, pages 209--218, 2006.
12. R. Fujimoto, K. Perumalla, A. Park, H. Wu, M. Ammar, and G. Riley. Large-Scale Network Simulation: How Big? How Fast? In 11th IEEE/ACM Int'l Symposium on Modeling, Analysis and Simulation of Computer Telecommun. Systems, pages 116--123, 2003.
13. D. Gianni, G. Iazeolla, and A. D'Ambrogio. A Methodology to Predict the Performance of Distributed Simulations. In Workshop on Principles of Advanced and Distributed Simulation (PADS), pages 31--39, 2010.
14. A. Gupta, L. V. Kale, D. S. Milojicic, P. Faraboschi, R. Kaufmann, V. March, F. Gioachin, C. H. Suen, and B.-S. Lee. Exploring the Performance and Mapping of HPC Applications to Platforms in the Cloud. In Proceedings of the 21st International Symposium on High-Performance Parallel and Distributed Computing, HPDC, pages 121--122, 2012.
15. S. D. Hammond, G. R. Mudalige, J. A. Smith, S. A. Jarvis, J. A. Herdman, and A. Vadgama. WARPP: a Toolkit for Simulating High-Performance Parallel Scientific Codes. In Proc. of the 2nd Int'l Conference on Simulation Tools and Techniques, pages 19:1--19:10, 2009.
16. Q. He, M. Ammar, G. Riley, H. Raj, and R. Fujimoto. Mapping Peer Behavior to Packet-Level Details: a Framework for Packet-Level Simulation of Peer-to-Peer Systems. In 11th IEEE/ACM Int'l Symposium on Modeling, Analysis and Simulation of Computer Telecommunications Systems, pages 71--78, 2003.
17. Z. Juhasz, S. Turner, K. Kuntner, and M. Gerzson. A Performance Analyser and Prediction Tool for Parallel Discrete Event Simulation. In UKSIM 2001: Conference On Computer Simulation, pages 148--155, 2001.
18. P. Konas and P.-C. Yew. Parallel Discrete Event Simulation on Shared-Memory Multiprocessors. In Proc. of the 24th Annual Simulation Symposium, pages 134--148, 1991.
19. J. Liu, D. Nicol, B. Premore, and A. Poplawski. Performance Prediction of a Parallel Simulator. In Thirteenth Workshop on Parallel and Distributed Simulation, pages 156--164, 1999.
20. J. Mittag, S. Papanastasiou, H. Hartenstein, and E. Strom. Enabling Accurate Cross-Layer PHY/MAC/NET Simulation Studies of Vehicular Communication Networks. Proceedings of the IEEE, 99(7):1311--1326, 2011.
21. K. Perumalla, R. Fujimoto, P. Thakare, S. Pande, H. Karimabadi, Y. Omelchenko, and J. Driscoll. Performance Prediction of Large-Scale Parallel Discrete Event Models of Physical Systems. In Proc. of the Winter Simulation Conference, pages 356--364, 2005.
22. M. Quinson, C. Rosa, and C. Thiery. Parallel Simulation of Peer-to-Peer Systems. In CCGrid 2012 - The 12th IEEE/ACM Int'l Symposium on Cluster, Cloud and Grid Computing, pages 668--675, 2012.
23. P. F. Reynolds, Jr., and P. M. Dickens. SPECTRUM: A Parallel Simulation Testbed. In Proceedings of the Hypercube Conference, 1989.
24. G. F. Riley, M. H. Ammar, R. M. Fujimoto, A. Park, K. Perumalla, and D. Xu. A Federated Approach to Distributed Network Simulation. ACM Transactions on Modeling and Computer Simulation, pages 116--148, 2004.
25. G. F. Riley and T. R. Henderson. The NS-3 Network Simulator. In Modeling and Tools for Network Simulation, pages 15--34. Springer Berlin Heidelberg, 2010.
26. A. F. Rodrigues, K. S. Hemmert, B. W. Barrett, C. Kersey, R. Oldfield, M. Weston, R. Risen, J. Cook, P. Rosenfeld, E. Cooper-Balls, and B. Jacob. The Structural Simulation Toolkit. SIGMETRICS Performance Evaluation Review, 38(4):37--42, 2011.
27. C. A. Schaefer, V. Pankratius, and W. F. Tichy. Engineering Parallel Applications with Tunable Architectures. In Proc. of the 32nd ACM/IEEE Int'l Conference on Software Engineering - Volume 1, pages 405--414, 2010.
28. M. Snir, S. W. Otto, D. W. Walker, J. Dongarra, and S. Huss-Lederman. MPI: The Complete Reference. MIT Press, 1995.
29. H. Sutter and J. Larus. Software and the Concurrency Revolution. Queue, 3(7):54--62, 2005.
30. S. M. Swope and R. M. Fujimoto. Optimal Performance of Distributed Simulation Programs. In Proc. of the 19th Winter Simulation Conference, 1987.
31. K. Vanmechelen, S. De Munck, and J. Broeckhove. Conservative Distributed Discrete Event Simulation on Amazon EC2. In Proceedings of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID, pages 853--860, 2012.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

    • Simulation theory