math.tex

柯老师网站上找到的

%
% personal commentary:
%        DRAFT DRAFT DRAFT
%        - KFALL
% RNG section reviewed and revised 11-Sep-98, johnh.
%
\chapter{Mathematical Support}
\label{chap:math}

The simulator includes a small collection of mathematical
functions used to implement random variate generation and integration.
This area of the simulator is currently undergoing some
changes.

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

\section{Random Number Generation}
\label{sec:random}

The \code{RNG} class contains an implementation of the minimal standard
multiplicative linear congruential generator of
Park and Miller~\cite{Park88:Random}.

Multiple instances of the RNG class can be created to allow a
simulation to draw random numbers from independent random number
streams.  For instance, a user who wants to generate the same traffic
(based on some random process) in 2 different simulation experiments
that compare different dropping algorithms that are themselves based
on random processes may choose to base the traffic generation on one
random number stream and the dropping algorithms on another stream.
However, when using multiple RNG objects in a simulation care should
be taken to insure that they are seeded in such a way as to guarantee
that they produce independent, high-quality streams of random numbers.
We describe approaches to seed the RNG below.

Most users will be satisfied with a single instance of the RNG.
Hence, a default RNG, created at simulator initialization time, is
provided.

\paragraph{C++ Support}
This random number generator is
implemented by the RNG class, defined in \nsf{rng.h}:
\begin{program}
class RNG : public TclObject \{
enum RNGSources \{ RAW_SEED_SOURCE, PREDEF_SEED_SOURCE, HEURISTIC_SEED_SOURCE \};
        ...
        // These are primitive but maybe useful.
        inline int uniform_positive_int() \{  // range [0, MAXINT]
                return (int)(stream_.next());
        \}
        inline double uniform_double() \{ // range [0.0, 1.0)
                return stream_.next_double();
        \}

        inline int uniform(int k)
                \{ return (uniform_positive_int() % (unsigned)k); \}
        inline double uniform(double r) 
                \{ return (r * uniform_double());\}
        inline double uniform(double a, double b)
                \{ return (a + uniform(b - a)); \}
        inline double exponential()
                \{ return (-log(uniform_double())); \}
        inline double exponential(double r)
                \{ return (r * exponential());\}
        inline double pareto(double scale, double shape)
                \{ return (scale * (1.0/pow(uniform_double(), 1.0/shape)));\}
        ...
\};
\end{program}

The \code{uniform_positive_int} method generates random integers in the
range $[0,2^{31}-1]$.
In particular,
Additional member functions provide the following random variate
generation:

\begin{tabularx}{\linewidth}{rX}
\fcn[double r]{uniform} & generate a floating-point number
                          uniformly distributed on $[0,r]$ \\
\fcn[double a, double b]{uniform} & generate a floating-point number
                                    uniformly distributed on $[a,b]$ \\
\fcn[]{exponential} & generate a floating-point number
                      exponentially distributed (with parameter 1)
                      on $[0, \infty)$ \\
\fcn[int k]{integer} & generate an integer
                       uniformly distributed on $[0, (k-1)]$ \\
\end{tabularx}

The \code{Random} class (in random.h) is an older interface to the standard
random number stream.

Here's a sample use of RNG modeled on RED.  rng\_ is an instance of class RNG:
\begin{program}
        \ldots
        // {\cf drop probability is computed, pick random number and act}
        double u = rng_->uniform_double();
        if (u <= edv_.v_prob) \{
                edv_.count = 0;
                if (edp_.setbit) 
                        iph->flags() |= IP_ECN; \* ip ecn bit */
                else
                        return (1);
        \}
        \ldots
\end{program}

\paragraph{Seeding the random number generator}
When doing simulations often you will either want to get absolutely
repeatable (deterministic) results or different results each time.
Each approach requires a different seeding method.

To get deterministic behavior, invoke the \fcn[]{set\_seed} method
with the first parameter either RAW\_SEED\_SOURCE or
PREDEF\_SEED\_SOURCE.  With a raw seed, the second parameter specifies
the numeric seed that will be used (any integer).  The alternative is
predefined seeds, where the second selects seeds from a table of 64
known good seeds (which happen to be about 33 million steps apart in
the default random number generation stream).
Predefined seeds are know to provide a good random number stream,
but there are limited numbers of them.
Raw seeds may
not provide a statistically good random number stream but are easy to generate.

To get non-deterministic behavior, pick a seed with either 
RAW\_SEED\_SOURCE or HEURISTIC\_SEED\_SOURCE.
For raw streams the second argument specifies the stream.
For heuristic streams the second argument is ignored and a seed is generated
based on the current time of day and a counter.
Both have the caveat that they may not provide a
statistically good random number stream.
It is very unlikely that any two heuristic seeds will be identical.

\paragraph{OTcl support}
The RNG class can be accessed from OTcl.  For example, a new RNG is
created and seeded with:

\begin{program}
set rng [new RNG]
$rng seed 0 \; seeds the RNG heuristically;
$rng seed n \; seeds the RNG with value n;
$rng next-random \;  return the next random number;
$rng uniform a b \; return a number uniformly distributed on [a, b];
$rng integer k \; return an integer uniformly distributed on [0, (k-1)];
$rng exponential \; return a number from an exponential distribution with average 1.;
\end{program}

Currently there is no way to select predefined seeds from OTcl.

\section{Random Variables}
\label{sec:ranvar}

The \clsref{RandomVariable}{../ns-2/ranvar.h}
provides a thin layer of functionality on top
of the base random number generator and the default random number stream.
It is defined in \nsf{ranvar.h}:

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

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:

\begin{tabular}{rl}
\clsref{UniformRandomVariable}{../ns-2/ranvar.h} & \code{min_}, \code{max_} \\
\clsref{ExponentialRandomVariable}{../ns-2/expoo.h} & \code{avg_} \\
\clsref{ParetoRandomVariable}{../ns-2/pareto.h} & \code{avg_}, \code{shape_}\\
\clsref{ConstantRandomVariable} & \code{val_}\\
\clsref{HyperExponentialRandomVariable}{../ns-2/ranvar.h} & \code{avg_}, \code{cov_}\\
\end{tabular}

The RandomVariable class is available in OTcl.  For instance, to
create a random variable that generates number uniformly on [10, 20]:
\begin{program}
        set u [new RandomVariable/Uniform]
        $u set min_ 10
        $u set max_ 20
        $u value
\end{program}
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:
\begin{program}
        set rng [new RNG]
        $rng seed 0

        set e [new RandomVariable/Exponential]
        $e use-rng $rng
\end{program}


\section{Integrals}
\label{sec:integral}

The  \clsref{Integrator}{../ns-2/integrator.h}
supports the approximation of (continuous) integration by (discrete)
sums; it is defined in \nsf{integrator.h} as
\begin{program}
{\rm 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_;
        \};

{\rm 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));
        \}
\end{program}
This class provides a base class used by other classes such
as \code{QueueMonitor} that keep running sums.
Each new element of the running sum is added by
the \fcn[x, y]{newPoint} function.
After the $k$th execution of \code{newPoint}, the running sum
is equal to $\sum_{i=1}^{k}y_{i-1}(x_i - x_{i-1})$ where
$x_0 = y_0 = 0$ unless \code{lastx\_}, \code{lasty\_}, or \code{sum\_}
are reset via OTcl.
Note that a new point in the sum can be added either by the
C++ member \code{newPoint} or the OTcl member \code{newpoint}.
The use of integrals to compute certain types of averages
(e.g. mean queue lengths) is given in (pp. 429--430, \cite{Jain91:Art}).

\section{\code{ns-random}}

{\bf \code{ns-random} is an obsolete way to generate random numbers. 
This information is provided only for backward compatibility.}

\code{ns-random} is implemented in \nsf{misc.\{cc,h\}}. 
When called with no argument, it generates a random number with
uniform distribution between 0 and \code{MAXINT}.
When an integer argument is provided, it seeds the random generater
with the given number.
A special case is when \code{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.

\section{Some mathematical-support related objects}
\label{sec:mathobjects}

\textsc{Integrator objects}
Integrator Objects support the approximate computation of continuous
integrals using discrete sums. The running sum(integral) is computed as:
\code{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\_). 
\code{$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:
\begin{description}
\item[lastx\_]
x-coordinate of the last sample point. 

\item[lasty\_]
y-coordinate of the last sample point. 

\item[sum\_] Running sum (i.e. the integral) of the sample points. 
\end{description}


\textsc{Samples Object}
Samples Objects support the computation of mean and variance statistics
for a given sample. 

\code{$samples mean}\\
Returns mean of the sample. 

\code{$samples variance}\\
Returns variance of the sample. 

\code{$samples cnt}\\
Returns a count of the sample points considered. 

\code{$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. 



\section{Commands at a glance}
\label{sec:mathcommand}

Following is a list of mathematical support related commands commonly used
in simulation scripts:
\begin{flushleft}
\code{set rng [new RNG]}\\
This creates a new random number generator.


\code{$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>.


\code{$rng next-random}\\
This returns the next random number from RNG.


\code{$rng uniform <a> <b>}\\
This returns a number uniformly distributed on <a> and <b>.


\code{$rng integer <k>}\\
This returns an integer uniformly distributed on 0 and k-1.


\code{$rng exponential}\\
This returns a number that has exponential distribution with average 1.


\code{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 \ref{sec:ranvar} of this
chapter.


\code{$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.


\end{flushleft}




% LocalWords:  ranvar pareto expoo tcl lib ns cc integrator RNG rng TclObject
% LocalWords:  enum RNGSources PREDEF int MAXINT rX edv prob edp setbit iph ECN
% LocalWords:  ip ecn eed OURCE OTcl RandomVariable argc const argv min avg val
% LocalWords:  UniformRandomVariable ExponentialRandomVariable cov newPoint pp
% LocalWords:  ParetoRandomVariable ConstantRandomVariable lastx lasty strcmp
% LocalWords:  HyperExponentialRandomVariable newpoint atof QueueMonitor