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: Aman Shaikh , Anujan Varma , Lampros Kalampoukas , Rohit Dube, Routing stability in congested networks: experimentation and analysis, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.163-174, August 28-September 01, 2000, Stockholm, Sweden
• 3: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 4: Christopher D. Carothers , Kalyan S. Perumalla , Richard M. Fujimoto, Efficient optimistic parallel simulations using reverse computation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.9 n.3, p.224-253, July 1999 [doi>10.1145/347823.347828]
• 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: David M. Nicol , Jason Liu, Composite Synchronization in Parallel Discrete-Event Simulation, IEEE Transactions on Parallel and Distributed Systems, v.13 n.5, p.433-446, May 2002 [doi>10.1109/TPDS.2002.1003854]
• 8: George F. Riley , Richard M. Fujimoto , Mostafa H. Ammar, A Generic Framework for Parallelization of Network Simulations, Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.128, March 24-28, 1999
• 9: Pierre L'Ecuyer , Terry H. Andres, A random number generator based on the combination of four LCGs, Mathematics and Computers in Simulation, v.44 n.1, p.99-107, May 1997 [doi>10.1016/S0378-4754(97)00052-9]
• 10: R. Brown, Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem, Communications of the ACM, v.31 n.10, p.1220-1227, Oct. 1988 [doi>10.1145/63039.63045]
• 11: Robert Rönngren , Rassul Ayani, A comparative study of parallel and sequential priority queue algorithms, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.2, p.157-209, April 1997 [doi>10.1145/249204.249205]
• 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 , R. Jain, Analysis of the increase and decrease algorithms for congestion avoidance in computer networks, Computer Networks and ISDN Systems, v.17 n.1, p.1-14, June 10, 1989 [doi>10.1016/0169-7552(89)90019-6]
• 16: Kevin Fall , Sally Floyd, Simulation-based comparisons of Tahoe, Reno and SACK TCP, ACM SIGCOMM Computer Communication Review, v.26 n.3, p.5-21, July 1996 [doi>10.1145/235160.235162]
• 17: Fabian Anthony Francis Bosco Gomes , Brian Unger, Optimizing incremental state-saving and restoration, 1996
• 18: Jack L. Lo , Joel S. Emer , Henry M. Levy , Rebecca L. Stamm , Dean M. Tullsen , S. J. Eggers, Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.322-354, Aug. 1997 [doi>10.1145/263326.263382]
• 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: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 23: D. Kotfila [e-mail], "Personal communication," Director, Cisco Academy, RPI, 2002.
• 24: Z. Xiao , B. Unger , R. Simmonds , J. Cleary, Scheduling critical channels in conservative parallel discrete event simulation, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.20-28, May 01-04, 1999, Atlanta, Georgia, United States
• 25: Richard A. Meyer , Rajive L. Bargrodia, Path lookahead: a data flow view of PDES models, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.12-19, May 01-04, 1999, Atlanta, Georgia, United States
• 26: Kalyan Perumalla , Richard Fujimoto , Andrew Ogielski, TED—a language for modeling telecommunication networks, ACM SIGMETRICS Performance Evaluation Review, v.25 n.4, p.4-11, March 1998 [doi>10.1145/274084.274085]
• 27: Brian J. Premore , David M. Nicol, Parallel simulation of TCP/IP using TeD, Proceedings of the 29th conference on Winter simulation, p.437-443, December 07-10, 1997, Atlanta, Georgia, United States [doi>10.1145/268437.268522]
• 28: Brian Unger , Zhonge Xiao , John Cleary , Jya-Jang Tsai , Carey Williamson, Parallel shared-memory simulator performance for large ATM networks, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.10 n.4, p.358-391, Oct. 2000 [doi>10.1145/369534.369537]
• 29: Boleslaw K. Szymanski , Adnan Saifee , Anand Sastry , Yu Liu , Kiran Madnani, Genesis: a system for large-scale parallel network simulation, Proceedings of the sixteenth workshop on Parallel and distributed simulation, May 12-15, 2002, Washington, D.C.

INDEX TERMS

Keywords:
OSPF, TCP, large-scale network simulation, optimistic synchronization protocol