25.1 Random Number Generation

The RNG class contains an implementation of the combined multiple recursive generator MRG32k3a proposed by L'Ecuyer [16]. The C++ code was adapted from [18]. This replaces the previous implementation of RNG, which used the minimal standard multiplicative linear congruential generator of Park and Miller [27]. The newer (MRG32k3a) RNG is used in ns versions 2.1b9 and later.

The MRG32k3a generator provides $1.8$x$10^{19}$ independent streams of random numbers, each of which consists of $2.3$x$10^{15}$ substreams. Each substream has a period (i.e., the number of random numbers before overlap) of $7.6$x$10^{22}$. The period of the entire generator is $3.1$x$10^{57}$. Figure 25.1 provides a graphical idea of how the streams and substreams fit together.

Figure 25.1: Overall arrangement of streams and substreams. [18]
\includegraphics[angle=270,width=6 in]{rng-streams.eps}

A default RNG (defaultRNG), created at simulator initialization time, is provided. If multiple random variables are used in a simulation, each random variable should use a separate RNG object. When a new RNG object is created, it is automatically seeded to the beginning of the next independent stream of random numbers. Used in this manner, the implementation allows for a maximum of $1.8$x$10^{19}$ random variables.

Often, multiple independent replications of a simulation are needed (i.e., to perform statistical analysis given multiple runs with fixed parameters). For each replication, a different substream should be used to ensure that the random number streams are independent. (This process is given as an OTcl example later.) This implementation allows for a maximum of $2.3$x$10^{15}$ independent replications. Each random variable in a single replication can produce up to $7.6$x$10^{22}$ random numbers before overlapping.

Note: Only the most common functions are described here. For more information, see [18] and the source code found in tools/rng.h and tools/rng.cc. For a comparison of this RNG to the more common LCG16807 RNG (and why LCG16807 is not a good RNG), see [17].

Tom Henderson 2011-11-05