Modeling communication software execution for accurate simulation of distributed systems

ABSTRACT

Network simulation is commonly used to evaluate the performance of distributed systems, but these approaches do not account for the performance impact that protocol execution on nodes has on performance, which may be significant. We propose a methodology to capture execution models from communication software running on real devices where the execution models can be integrated with discrete event network simulators to improve their accuracy. We provide a set of rules to instrument the software to obtain the events of importance, and present techniques to create executable models based on the obtained traces. To make the models scalable, processing stages are reduced to statistical distributions. When the resulting models are executed in a device model with a scheduler simulator, we are able to model the dynamics of multithreading and parallel execution. Our initial results from a proof-of-concept extension to Ns-3 show that our models are able to accurately model protocol execution on the Google Nexus One with low simulation overhead.

References

1. Documentation/kprobes.txt. The Linux kernel sources.
2. N. Binkert, R. Dreslinski, L. Hsu, K. Lim, A. Saidi, and S. Reinhardt. The m5 simulator: Modeling networked systems. Micro, IEEE, 26(4):52--60, july-aug. 2006.
3. J. M. Calandrino, D. P. Baumberger, Y. Li, Tong, J. C., and S. Hahn. Linsched: The linux scheduler simulator. PDCCS, 2008.
4. V. G. Cerf. Where is the science in computer science? Commun. ACM, 55(10):5--5, Oct. 2012.
5. R. Chertov, S. Fahmy, and N. B. Shroff. A device-independent router model. INFOCOM. IEEE, 2008.
6. J. Cook, J. Cook, and W. Alkohlani. A statistical performance model of the opteron processor. SIGMETRICS Perform. Eval. Rev., 38(4):75--80, Mar. 2011.
7. T. Grotker. System Design with SystemC. Kluwer Academic Publishers, Norwell, MA, USA, 2002.
8. S. Kristiansen, M. Lindeberg, D. Rodriguez-Fernandez, and T. Plagemann. On the forwarding capability of mobile handhelds for video streaming over manets. MobiHeld. ACM, 2010.
9. S. Kristiansen and T. Plagemann. Accuracy and scalability of ns-2's distributed emulation extension. Simulation, 87(1-2):45--65, Jan. 2011.
10. S. Kristiansen, T. Plagemann, and V. Goebel. Modelling communication software for accurate simulation of distributed systems. Technical report, University of Oslo, Department of Informatics, 2012.
11. S. Kristiansen, T. Plagemann, and V. Goebel. Extending network simulators with communication software execution models. In COMSNETS. IEEE, 2013.
12. O. Landsiedel, H. Alizai, and K. Wehrle. When timing matters: Enabling time accurate and scalable simulation of sensor network applications. In IPSN. IEEE, 2008.
13. B. Muller-Rathgeber and H. Rauchfuss. A cosimulation framework for a distributed system of systems. In VTC. IEEE, 2008.
14. R. Olsson. pktgen the linux packet generator. In Proc. of the Linux Symposium, 2005.
15. P. Pagano, M. Chitnis, G. Lipari, C. Nastasi, and Y. Liang. Simulating real-time aspects of wireless sensor networks. EURASIP Journal on Wireless Communication and Networking, 2010:2:1--2:12, April 2010.
16. R. Ramaswamy, N. Weng, and T. Wolf. Considering processing cost in network simulations. MoMeTools. ACM, 2003.
17. M. Rosenblum, S. A. Herrod, E. Witchel, and A. Gupta. Complete computer system simulation: The simos approach. IEEE Parallel Distrib. Technol., 3(4):34--43, Dec. 1995.
18. K. Salah. Modeling and analysis of pc-based software routers. Comp. Commun., 33(12):1462 -- 1470, 2010.
19. K. Salah and K. El-Badawi. Throughput-delay analysis of interrupt-driven kernels with dma enabled and disabled in high-speed networks. J. High Speed Netw., 15(2):157--172, Jan. 2006.
20. K. Salah and M. Hamawi. Comparative packet-forwarding measurement of three popular operating systems. Jour. of Netw. and Comp. Applications, 32(5):1039 -- 1048, 2009.
21. F. Trahay, E. Brunet, and A. Denis. An analysis of the impact of multi-threading on communication performance. In IPDPS. IEEE, 2009.
22. R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, and P. Stenström. The worst-case execution-time problem-overview of methods and survey of tools. ACM Trans. Embed. Comput. Syst., 7(3):36:1--36:53, May 2008.
23. E. Witchel and M. Rosenblum. Embra: fast and flexible machine simulation. SIGMETRICS. ACM, 1996.
24. W. Wu, M. Crawford, and M. Bowden. The performance analysis of linux networking-packet receiving. Comp. Commun., 30(5):1044 -- 1057, 2007.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

    • Simulation evaluation

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Software architectures

        • Simulator / interpreter