Large-scale network simulation techniques: examples of TCP and OSPF models

Abstract

Simulation of large-scale networks remains to be a challenge, although various network simulators are in place. In this paper, we identify fundamental issues for large-scale networks simulation, and porpose new techniques that address them. First, we exploit optimistic parallel simulation techniques to enable fast execution on inexpensive hyper-threaded, multiprocessor systems. Second, we provide a compact, light-weight implementation framework that greatly reduces the amount of state required to simulate large-scale network models. Based on the proposed techniques, we provide sample simulation models for two networking protocols: TCP and OSPF. We implement these models in a simulation environment ROSSNet, which is an extension to the previously developed optimistic simulator ROSS. We perform validation experoments for TCP and OSPF and present performance reuslts of our techniques by simulating OSPF and TCP on a large and realistic topology, such as AT&T's US network based on rocketfuel data. The end result of these innovations is that we are able to simulate million node network tolopgies using inexpensive commercial off-the-shelf hyper-threaded multiprocessor systems consuming less than 1.4 GB of RAM in total.

References

1. E. G. Coffman, Z. Ge, V. Misra, and D. Towsley, "Network resilience: Exporing cascading failures within bgp", in Proceedings of the 40th annual Allerton Conference on Communications, Computing and Control, 2002.
2. A. Shaikh, L. Kalampoukas, R. Dube, and A. Varma, "Routing stability in congested networks: Experimentation and analysis," in Proceedings of ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communicatins (SIGCOMM), 2000.
3. D. R. Jefferson, "Virtual time," ACM Transactions on Programming Languages and Systems, vol. 7, no. 3, pp. 404--425, July 1985.
4. C. D. Carothers, K. Perumalla, and R. M. Fujimoto, "Efficient parallel simulation using reverse computation," ACM Transactions on Modeling and Computer Simulation, vol. 9, no. 3, pp. 224--253, July 1999.
5. "UCB/LBLN/VINT network simulator - ns (version2)," http://www.nash.cs.berkeley.edu/ns, 1997.
6. J. Cowie, H. Liu, J. Liu, D. Nicol, and A. Ogielski, "Towards realistic million-node internet simulations," in Proceedings of International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), 1999.
7. D. M. Nicol and J. Liu, "Composite synchronization in parallel discrete-event simulation," IEEE Transaciton of Parallel and Distributed Systems, vol. 13, no. 5, 2002.
8. G. F. Railey, R. M. Fujimoto, and M. H. Ammar, "A generic framework for parallelization of network simulatins," in Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), 1999, pp. 128--135.
9. P. L'Ecuyer and T. H. Andres, " A random number generator based on the four legs," Mathematics and Computers in Simulation, vol. 44, pp. 99--107, 1997.
10. R. Brown, "Calendar quenes: A fast o(1) priority queue implementation for the simulation event set problem," Communications of the ACM (CACM), vol. 31, pp. 1220--1227, 1998.
11. R. Ronngren and Rassul Ayani, "A comparative study of parallel and sequential priority queue algorithms", ACM Transactions on Modeling and Computer Simulation, vol.7, no.2, pp. 157--209, April 1997.
12. D. M. Rao and P. A. Wilsey, "An ultra-large scale simulation framework," Journal of Parallel and Distributed Computing (in press), 2002.
13. "JavaSim," http://javasim.cs.uiuc.edu, 1999.
14. V. Jacobson, "Congestion avoidance and control," in Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), 2001.
15. D. M. Chiu and R. Jain, "Analysis of the increase/decrease algorithms for congestion avoidance in computer networks", Journal of Computer Networks and ISDN Systems, vol. 1, pp. 1--14, June 1989.
16. K. Fall and S. Floyd, "Simulation-based comparison of tahoe, reno, and sack tcp", Computer Communicatin Review, vol. 26, pp. 5--21, 1996.
17. F. Gomes, "Optimizing incremental state-saving and restoration," Tech. Rep., Ph.D. thesis, Department of Computer Science, University of Calgary, 1996.
18. J. L. Lo, S. J. Eggers, J. S. Emer, H. M. Levy, R. L. Stamm, and D. M. Tullsen, "Converting thread-level parallelism to instruction parallelism via simultaneous multithreading," Transactions on Computer Sustems, vol. 15, no. 3, pp. 322--354, 1997.
19. "Intel Pentium 4 and Xeon Processor Optimization Reference Manual", http://developer.intel.com/design/pentium4/manuals/248966.htm.
20. "Rocketfuel internet topology databse," http://www.cs.washington.edu/research/networking/rocketfuel.
21. D. Nicol, "Scalability of network simulators revisited," in Procedings of Communications Networks and Distributed Systems Modeling and Simulation Conference (CNDS) part of Western Multi-Confernce (WMC), 2003.
22. N. Spring, R. Mahajan, and D. Wetherall, "Measuring isp topologies with rocketfuel,' in Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), 2002.
23. D. Kotfila [email protected], "Personal communication," Director, Cisco Academy, RPI, 2002.
24. Z. Xiao, B. Unger, R. Simmonds, and J. Cleary, "Scheduling critical channels in conservative parallel discrete event simulation," in Proceedings of the Workshop on Parallel and Distributed Simulation (PADS), 1999, pp. 20--28.
25. R. A. Meyer and R. L. Bagrodia, "Path lookahead: a data flow view of pdes models," in Proceedings of the Workshop on Parallel and Distributed Simulation (PADS), 1999, 99. 12--19.
26. K. Perumalla, A. Ogielskim and R, Fujimoto, "Ted - a language for modeling telecommunication networks," in Proceedings of ACM SIGMETRICS Performance Evaluation Review, 1998, vol. 25.
27. B. J. Premore and D. M. Nicol, "Parallel simulation of top/ip using ted," in Proceedings of the Winter Simulation Conference (WSC), 1997, pp. 437--443.
28. B. Unger, Z. Xiao, J. Cleary, J-J Tsai, and C. Williamson, "Parallel shared-memory simulator performance for large atm networks," ACM Transactions on Modeling and Computer Simulation, vol. 10, no. 4, pp. 358--391, 2000.
29. B. K. Szymanski, A. Saifee, A. Sastry, Y. Liu, and K. Madnani, "Genesis: A system for large-scale parallel network simulation," in Proceedings of Workshop on Parallel and Distributed Simulation (PADS'02), 2002, pp. 89--96.

Index Terms

• Networks

  • Network protocols