1.2 Background

Simulations use a lot of random numbers; the study in [cite] found that most network simulations spend as much as 50% of the CPU generating random numbers. Simulation users need to be concerned with the quality of the (pseudo) random numbers and the independence between different streams of random numbers.

Users need to be concerned with a few issues, such as:

• the seeding of the random number generator and whether a simulation run is deterministic or not,
• how to acquire different streams of random numbers that are independent from one another, and
• how long it takes for streams to cycle

We will introduce a few terms here: a RNG provides a long sequence of (pseudo) random numbers. The length of this sequence is called the cycle length or period, after which the RNG will repeat itself. This sequence can be partitioned into disjoint streams. A stream of a RNG is a contiguous subset or block of the RNG sequence. For instance, if the RNG period is of length N, and two streams are provided from this RNG, then the first stream might use the first N/2 values and the second stream might produce the second N/2 values. An important property here is that the two streams are uncorrelated. Likewise, each stream can be partitioned disjointly to a number of uncorrelated substreams. The underlying RNG hopefully produces a pseudo-random sequence of numbers with a very long cycle length, and partitions this into streams and substreams in an efficient manner.

ns-3 uses the same underlying random number generator as does ns-2: the MRG32k3a generator from Pierre L'Ecuyer. A detailed description can be found in http://www.iro.umontreal.ca/~lecuyer/myftp/papers/streams00.pdf. The MRG32k3a generator provides 1.8x10^19 independent streams of random numbers, each of which consists of 2.3x10^15 substreams. Each substream has a period (i.e., the number of random numbers before overlap) of 7.6x10^22. The period of the entire generator is 3.1x10^57. Figure ref-streams provides a graphical idea of how the streams and substreams fit together.

Class ns3::RandomVariable is the public interface to this underlying random number generator. When users create new RandomVariables (such as UniformVariable, ExponentialVariable, etc.), they create an object that uses one of the distinct, independent streams of the random number generator. Therefore, each object of type RandomVariable has, conceptually, its own "virtual" RNG. Furthermore, each RandomVariable can be configured to use one of the set of substreams drawn from the main stream.

An alternate implementation would be to allow each RandomVariable to have its own (differently seeded) RNG. However, we cannot guarantee as strongly that the different sequences would be uncorrelated in such a case; hence, we prefer to use a single RNG and streams and substreams from it.

This document was generated on September, 23 2008 using texi2html 1.76.