An important component of the emulation environment is the capability to simulate large-scale network configurations at high-fidelity. In order to achieve this capability, we build on some of the results of our work from the related COMPASS project.
We discovered that a major impediment to realizing large-scale network simulations and emulations with the ns2 package (developed at ISI) is the memory required for routing tables, and the time to compute values to fill in these tables. Observing that the full generality afforded by these tables is almost never required in actual experiments, we developed an approach to eliminate the tables, and replace routing information with dynamically created vectors (termed Nix Vectors) that encode routing information. We have implemented this technique in ns-2 for use in the emulation backplane. Use of Nix Vectors and parallel processing enabled us to simulate wired networks containing more than 250,000 nodes, two orders of magnitude larger than what could be accomplished with the original ns-2 simulator.
The capability of network simulators to simulate larger network configurations is severely limited by their routing table implementations. A straightforward approach to simulation is memory intensive, limiting the number of nodes that can be simulated. The routing tables consume memory in the order of O(N2), where N is the number of nodes. Further, route computation can be computationally intensive, although at runtime all nodes do not need all routes.
In order to improve the simulation capability to enable emulation of much larger number of nodes, we have developed optimizations that increase the limit on the number of emulated nodes by up to two orders of magnitude when compared to traditional approaches.
The enhancement, which we call Nix Vector (Neighbor Index Vector) optimization, involves eliminating the need for explicitly storing routing tables, and instead computes routes on-demand and stores routes in the simulated packets. Nix Vectors are cached at each source, and computed only once for each source-destination pair. Further, a very compact representation using bit vectors is used for storing Nix Vectors.
The Nix Vector technique has been incorporated into the ns-2 simulator and is now operational. However, it is general in nature, and can be applied to other network simulators as well. The Nix Vector optimization is observed to deliver an order of magnitude improvement in the number of nodes that can be simulated on an off-the-shelf desktop computer (10x more nodes simulated on a 500 MHz Pentium, 4Gb memory). When coupled with parallel execution using parallel simulation techniques, an additional order of magnitude improvement is obtained (100x more nodes simulated on a network of 16 processors). On a 16 CPU network, more than 250,000 ns2 nodes were simulated.
In summary, the optimizations resulted in a substantial increase (two orders of magnitude) in the number of simulated nodes than previously possible. We have completed the Nix Vector enhancements to ns-2. Following that, we have initiated its integration into the mainstream ns-2 distribution (VINT project).