**SNS** uses **staged simulation**, a technique for improving the
run time performance and scale of discrete event simulators. Typical
network simulations are limited in speed and scale due to **redundant
computations**, both within a single simulation run and between successive
runs. Staged simulation restructures discrete event simulators to operate
in stages that precompute, cache, and reuse partial results to drastically
reduce redundant computation within and across simulations.

Experience with applying staged simulation in the **SNS** simulator shows
that staging can improve execution time by an order of magnitude or more and
enable the simulation of wireless networks with tens of thousands of nodes.

## Why do we need staging?

Network simulations are critical for the design and evaluation of
distributed systems and networking protocols. Especially in newly emerging
domains such as mobile ad hoc and sensor networks, simulations are crucial
to evaluating new systems and protocols across a range of deployment
scenarios. While thorough evaluations require accurate, efficient and
scalable network simulators, achieving all three of these properties
simultaneously is a challenging task. We assert that a significant source of
inefficiency in discrete event simulators stems from redundant computation,
and that this wasted computation presents a significant limit to simulation
speed and scale.

Staging addresses this inefficiency by identify and reducing two different
classes of redundancy in traditional discrete-event network simulators.

The first class of redundant computation occurs within a single run of
the simulator, and stems from an overly strict notion of accuracy.
Traditional network simulators are conservative, that is, they reevaluate
complex functions whenever their results *may* have changed, even
though in reality the results may have changed very little, if at all, since
the last time they were evaluated. An illustrative example is the
computation of a node's one hop neighbor-set in wireless network
simulations. This is an expensive and frequently-used primitive in wireless
simulations. It computes the positions of all nodes relative to the sending
node, calculates the power level of the signal at each receiver, and
determines the set of nodes that can capture transmitted packets. In the
most general case, nodes may change position, alter sending and receiving
power thresholds, or modify antenna models or parameters at any time. A
conservative wireless network simulator which has computed the neighbors of
a wireless node at time *t* will still recompute the neighbor-set from
scratch at time step *t+ε*. In reality, however, few wireless
simulation scenarios will change dramatically over short time-scales. Nodes
move smoothly and relatively slowly, if at all. Other variables, such as
antenna model, reception threshold, and transmission power change
infrequently. In general, the neighbor-set computed at time *t* is
likely to remain valid for some time, changing slowly and gradually as nodes
move into or out of range. Much of the time spent re-computing
neighbor-sets from scratch at each time step is therefore effectively
wasted.

A second class of redundant computation occurs between multiple runs of a
simulator, and stems from performing calculations which were already
computed in previous runs. Simulations are often performed in batches of
tens or hundreds of simulation runs, with only slightly varying simulation
parameters within each batch. While each run will differ in some inputs,
such as the random number seed, network traffic pattern, or protocol
parameters, often there is still a significant overlap between the work
performed in multiple invocations of the simulator. Executing each
simulation independently and without the benefit of past computations leads
to redundantly computing many identical results.

## How does staging work?

**Function caching and reuse** forms the foundation of the staging
approach. Without loss of generality, each event in a discrete-event
simulator can be treated as a sequence of function invocations. A staged
simulator caches arguments, results and side-effects of function
invocations, and later avoids redundant computations by reusing results and
reapplying side effects when the same function is invoked with the same
arguments. This space-for-time trade-off ensures that each expensive
function invocation is computed at most once. While function caching and
reuse is effective at eliminating redundant computations, it is not directly
suitable for application in realistic wireless simulators because it is
overly sensitive to changes in the arguments to function invocations. In
typical wireless simulations, many computations depend on continuously
varying inputs, such as the current simulator time, and any change in
inputs, no matter how small, precludes reuse of previous results.
Similarly, real-valued parameters make it difficult to achieve effective
cache hit rates. These properties make naive function caching ineffective
for a large class of computations in a simulator.

**Event-restructuring** improves on function caching by modifying the
low-level events in a discrete event simulator such that their results are
reusable even when a change in inputs would normally preclude reuse. We
introduce three comprehensive techniques, called **currying**,
**incremental computation** and **auxiliary results**, for decomposing
the events in a discrete-event simulator into a series of events with an
equivalent effect. The equivalent transformations retain the semantics of
the original event and preserve accuracy. The resulting smaller
subcomputations, whose dependencies are better isolated, can then be reused
more frequently, leading to significant improvements in simulation speed and
scale.

**Time-shifting** takes advantage of the small, fine-grained events
created through event-restructuring by reordering them into an equivalent,
but more efficient, schedule. Restructured, fine-grained events have fewer
inputs and tend to be time-independent. Consequently, restructuring
provides the simulator with freedom to judiciously pick when to schedule
these events. Time-shifting can speed up simulations through architectural
or algorithmic improvements. First, time-shifting can simply reorder the
events into a sequence that is better suited to the machine architecture on
which the simulator is running. For instance, time-shifting events to access
memory sequentially instead of randomly can speed up execution by taking
advantage of memory caching and prefetching. And second, time-shifting and
batching similar operations can enable a series of piecemeal, small,
consecutive events to be computed by a single, more efficient algorithm. For
instance, time-shifting sufficiently many node distance calculations may
allow a long sequence of such computations to be replaced with an efficient
all-pairs shortest paths algorithm.