We propose a technique called staged simulation to improve the scale and run time performance of wireless mobile network simulators. Traditional wireless network simulators are limited in speed and scale because they perform many redundant computations both within a single simulation run, as well as across multiple invocations of the simulator. For instance, traditional simulators typically recompute node positions and power levels from scratch every time they may have changed, when, in fact, these values change infrequently and incrementally in practice.

Staged simulation proposes to eliminate redundant computations through function caching and reuse. The central idea behind staging is to cache the results of expensive operations and reuse them whenever possible. A naive application of function caching, however, would not achieve much speedup, as most events in a traditional simulator are dependent on simulation time. We provide a theoretical model of simulator operation, describe three fundamental ways (namely, currying, auxiliary result computation and time-shifting) to restructure events in a simulator, and show that they decouple events from simulation time and enable function caching to work effectively. This, in turn, enables expensive computations to be cached on disk and to be reused both within and across simulation runs.

We have built a staged simulator, called SNS, based on ns2. On a commonly used ad-hoc network simulation setup with 1500 nodes, SNS executes ~50 times faster than regular ns2; approximately 30x of this improvement is due to staging, the rest to engineering. This level of performance enables SNS to simulate large networks -- we have run 10000 node simulations in under an hour. SNS supports previously implemented protocols in ns2 and is freely available.

->  Project Members Who we are.
->  Motivation The motivation behind staging.
->  Overview How staging works in SNS.
->  Papers Paper trail.
->  Downloads The SNS implementation is freely available.
->  Acknowledgements Our sources of research support.

Computer Science Department
Cornell University