Manual: Mathematical Support

From nsnam
Revision as of 19:49, 23 July 2008 by Lachlan (Talk | contribs) (Restore deleted top navigation)

Jump to: navigation, search

Previous Chapter "Debugging ns" | Index | Next Chapter "Trace and Monitoring Support"

The procedures and functions described in this chapter can be found in ~ns/tools/rng.{cc, h}, ~ns/tools/random.{cc, h}, ~ns/tools/ranvar.{cc, h}, ~ns/tools/pareto.{cc, h}, ~ns/tools/expoo.{cc, h}, ~ns/tools/integrator.{cc, h}, and ~ns/tcl/lib/nsrandom.tcl.

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.8x1019 independent streams of random numbers, each of which consists of 2.3x1015 substreams. Each substream has a period (i.e., the number of random numbers before overlap) of 7.6x1022. The period of the entire generator is 3.1x1057. Figure 25.1 provides a graphical idea of how the streams and substreams fit together.

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.8x1019 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.3x1015 independent replications. Each random variable in a single replication can produce up to 7.6x1022 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].

Seeding The RNG

Due to the nature of the RNG and its implementation, it is not necessary to set a seed (the default is 12345). If you wish to change the seed, functions are available. You should only set the seed of the default RNG. Any other RNGs you create are automatically seeded such that they produce independent streams. The range of valid seeds is 1 to MAXINT.

To get non-deterministic behavior, set the seed of the default RNG to 0. This will set the seed based on the current time of day and a counter. This method should not be used to set seeds for independent replications. There is no guarantee that the streams produced by two random seeds will not overlap. The only way to guarantee that two streams do not overlap is to use the substream capability provided by the RNG implementation.

Example

# Usage: ns rng-test.tcl [replication number]
if {$argc > 1} {
  puts "Usage: ns rng-test.tcl \[replication number\]"
  exit
}
set run 1
if {$argc == 1} {
  set run [lindex $argv 0]
}
if {$run < 1} {
  set run 1
}

# seed the default RNG
global defaultRNG
$defaultRNG seed 9999

# create the RNGs and set them to the correct substream
set arrivalRNG [new RNG]
set sizeRNG [new RNG]
for {set j 1} {$j < $run} {incr j} {
  $arrivalRNG next-substream
  $sizeRNG next-substream
}

# arrival_ is a exponential random variable describing the time
# between consecutive packet arrivals
set arrival_ [new RandomVariable/Exponential]
$arrival_ set avg_ 5
$arrival_ use-rng $arrivalRNG

# size_ is a uniform random variable describing packet sizes
set size_ [new RandomVariable/Uniform]
$size_ set min_ 100
$size_ set max_ 5000
$size_ use-rng $sizeRNG

# print the first 5 arrival times and sizes
for {set j 0} {$j < 5} {incr j} {
  puts [format "%-8.3f %-4d" [$arrival_ value] \
         [expr round([$size_ value])]]
}

Output

% ns rng-test.tcl 1
6.358 4783
5.828 1732
1.469 2188
0.732 3076
4.002 626
% ns rng-test.tcl 5
0.691 1187
0.204 4924
8.849 857
2.111 4505
3.200 1143

OTcl Support

Commands

The following commands on the RNG class can be accessed from OTcl and are found in tools/rng.cc:

  • seed n – seed the RNG to n, if n == 0, the seed is set according to the current time and a counter
  • next-random – return the next random number
  • seed – return the current value of the seed
  • next-substream – advance to the next substream
  • reset-start-substream – reset the stream to the beginning of the current substream
  • normal avg std – return a number sampled from a normal distribution with the given average and standard deviation
  • lognormal avg std – return a number sampled from a lognormal distribution with the given average and standard deviation

The following commands on the RNG class can be accessed from OTcl and are found in tcl/lib/ns-random.tcl:

  • exponential mu – return a number sampled from an exponential distribution with mean mu
  • uniform min max – return an integer sampled from a uniform distribution on [min, max]
  • integer k – return an integer sampled from a uniform distribution on [0, k-1]

Example

# Usage: ns rng-test2.tcl [replication number]
if {$argc > 1} {
  puts "Usage: ns rng-test2.tcl \[replication number\]"
exit
}
set run 1
if {$argc == 1} {
  set run [lindex $argv 0]
}
if {$run < 1} {
  set run 1
}
# the default RNG is seeded with 12345
# create the RNGs and set them to the correct substream
set arrivalRNG [new RNG]
set sizeRNG [new RNG]
for {set j 1} {$j < $run} {incr j} {
  $arrivalRNG next-substream
  $sizeRNG next-substream
}
# print the first 5 arrival times and sizes
for {set j 0} {$j < 5} {incr j} {
  puts [format "%-8.3f %-4d" [$arrivalRNG lognormal 5 0.1] \
          [expr round([$sizeRNG normal 5000 100])]]
}

Output

% ns rng-test2.tcl 1
142.776 5038
174.365 5024
147.160 4984
169.693 4981
187.972 4982
% ns rng-test2.tcl 5
160.993 4907
119.895 4956
149.468 5131
137.678 4985
158.936 4871

C++ Support

Member Functions

The random number generator is implemented by the RNG class and is defined in tools/rng.h.

Note: The Random class in tools/random.h is an older interface to the standard random number stream.

Member functions provide the following operations:

  • void set_seed (long seed) – set the seed of the RNG, if seed == 0, the seed is set according to the current time and a counter
  • long seed (void) – return the current seed
  • long next (void) – return the next random number as an integer on [0, MAXINT]
  • double next_double (void) – return the next random number on [0, 1]
  • void reset_start_substream (void) – reset the stream to the beginning of the current substream
  • void reset_next_substream (void) – advance to the next substream
  • int uniform (int k) – return an integer sampled from a uniform distribution on [0, k-1]
  • double uniform (double r) – return a number sampled from a uniform distribution on [0, r]
  • double uniform (double a, double b) – return a number sampled from a uniform distribution on [a, b]
  • double exponential (void) – return a number sampled from an exponential distribution with mean 1.0
  • double exponential (double k) – return a number sampled from an exponential distribution with mean k
  • double normal (double avg, double std) – return a number sampled from a normal distribution with the given average and standard deviation
  • double lognormal (double avg, double std) – return a number sampled from a lognormal distribution with the given average and standard deviation

Example

/* create new RNGs */
RNG arrival (23456);
RNG size;
/* set the RNGs to the appropriate substream */
for (int i = 1; i < 3; i++) {
  arrival.reset_next_substream();
  size.reset_next_substream();
}
/* print the first 5 arrival times and sizes */
for (int j = 0; j < 5; j++) {
  printf ("%-8.3f %-4d\n", arrival.lognormal(5, 0.1),
  int(size.normal(500, 10)));
}

Output

161.826 506
160.591 503
157.145 509
137.715 507
118.573 496

Random Variables

The class RandomVariable provides a thin layer of functionality on top of the base random number generator and the default random number stream. It is defined in ~ns/ranvar.h:

class RandomVariable : public TclObject {
public:
  virtual double value() = 0;
  int command(int argc, const char*const* argv);
  RandomVariable();
protected:
  RNG* rng_;
};

Classes derived from this abstract class implement specific distributions. Each distribution is parameterized with the values of appropriate parameters. The value method is used to return a value from the distribution.

The currently defined distributions, and their associated parameters are:

class UniformRandomVariable          min_, max_
class ExponentialRandomVariable      avg_
class ParetoRandomVariable           avg_, shape_
class ParetoIIRandomVariable         avg_, shape_
class ConstantRandomVariable         val_
class HyperExponentialRandomVariable avg_, cov_
class NormalRandomVariable           avg_, std_
class LogNormalRandomVariable        avg_, std_

The RandomVariable class is available in OTcl. For instance, to create a random variable that generates number uniformly on [10, 20]:

set u [new RandomVariable/Uniform]
$u set min_ 10
$u set max_ 20
$u value

By default, RandomVariable objects use the default random number generator described in the previous section. The use-rng method can be used to associate a RandomVariable with a non-default RNG:

set rng [new RNG]
$rng seed 0
set e [new RandomVariable/Exponential]
$e use-rng $rng

Integrals

The class Integrator supports the approximation of (continuous) integration by (discrete) sums; it is defined in ~ns/integrator.h as

From integrator.h:

class Integrator : public TclObject {
public:
  Integrator();
  void set(double x, double y);
  void newPoint(double x, double y);
  int command(int argc, const char*const* argv);
protected:
  double lastx_;
  double lasty_;
  double sum_;
};

From integrator.cc:

Integrator::Integrator() : lastx_(0.), lasty_(0.), sum_(0.)
{
  bind("lastx_", &lastx_);
  bind("lasty_", &lasty_);
  bind("sum_", &sum_);
}
void Integrator::set(double x, double y)
{
  lastx_ = x;
  lasty_ = y;
  sum_ = 0.;
}
void Integrator::newPoint(double x, double y)
{
  sum_ += (x - lastx_) * lasty_;
  lastx_ = x;
  lasty_ = y;
}
int Integrator::command(int argc, const char*const* argv)
{
  if (argc == 4) {
     if (strcmp(argv[1], "newpoint") == 0) {
        double x = atof(argv[2]);
        double y = atof(argv[3]);
        newPoint(x, y);
        return (TCL_OK);
     }
  }
  return (TclObject::command(argc, argv));
}

This class provides a base class used by other classes such as QueueMonitor that keep running sums. Each new element of the running sum is added by the newPoint(x, y) function. After the kth execution of newPoint, the running sum is equal to <math>\sum_{i=1}^k y_{i−1}(x_i − x_{i−1})</math> where x0 = y0 = 0 unless lastx_, lasty_, or sum_ are reset via OTcl. Note that a new point in the sum can be added either by the C++ member newPoint or the OTcl member newpoint. The use of integrals to compute certain types of averages (e.g. mean queue lengths) is given in (pp. 429–430, [15]).

ns-random

ns-random is an obsolete way to generate random numbers. This information is provided only for backward compatibility.

ns-random is implemented in ~ns/misc.{cc,h}. When called with no argument, it generates a random number with uniform distribution between 0 and MAXINT. When an integer argument is provided, it seeds the random generator with the given number. A special case is when ns-random 0 is called, it randomly seeds the generator based on current time. This feature is useful to produce non-deterministic results across runs.

Some mathematical-support related objects

INTEGRATOR OBJECTS: Integrator Objects support the approximate computation of continuous integrals using discrete sums. The running sum(integral) is computed as: sum_ += [lasty_ * (x lastx_)] where (x, y) is the last element entered and (lastx_, lasty_) was the element previous to that added to the sum. lastx_ and lasty_ are updated as new elements are added. The first sample point defaults to (0,0) that can be changed by changing the values of (lastx_,lasty_). $integrator newpoint <x> <y>

Add the point (x,y) to the sum. Note that it does not make sense for x to be less than lastx_.

There are no configuration parameters specific to this object.

State Variables are:

  • lastx_ x-coordinate of the last sample point.
  • lasty_ y-coordinate of the last sample point.
  • sum_ Running sum (i.e. the integral) of the sample points.

SAMPLES OBJECT: Samples Objects support the computation of mean and variance statistics for a given sample.

$samples mean Returns mean of the sample.
$samples variance Returns variance of the sample.
$samples cnt Returns a count of the sample points considered.
$samples reset Reset the Samples object to monitor a fresh set of samples.

There are no configuration parameters or state variables specific to this object.

Commands at a glance

Following is a list of mathematical support related commands commonly used in simulation scripts:

set rng [new RNG] This creates a new random number generator.
$rng seed <0 or n> This command seeds the RNG. If 0 is specified, the RNG is seeded heuristically. Otherwise the RNG is seeded with the value <n>.
$rng next-random This returns the next random number from RNG.
$rng uniform <a> This returns a number uniformly distributed on <a> and <b>.
$rng integer <k> This returns an integer uniformly distributed on 0 and k-1.
$rng exponential This returns a number that has exponential distribution with average 1.
set rv [new Randomvariable/<type of random-variable>] This creates an instance of a random variable object that generates random variables with specific distribution. The different types of random variables derived from the base class are:

RandomVariable/Uniform, RandomVariable/Exponential, RandomVariable/Pareto, RandomVariable/Constant, RandomVariable/HyperExponential. Each of these distribution types are parameterized with values of appropriate parameters. For details see section Random Variables above.

$rv use-rng <rng> This method is used to associated a random variable object with a non-default RNG. Otherwise by default, the random variable object is associated with the default random number generator.

Previous Chapter "Debugging ns" | Index | Next Chapter "Trace and Monitoring Support"