iproute2/netem/README.distribution
<<
>>
Prefs
   1Notes about distribution tables from Nistnet
   2-------------------------------------------------------------------------------
   3I. About the distribution tables
   4
   5The table used for "synthesizing" the distribution is essentially a scaled,
   6translated, inverse to the cumulative distribution function.
   7
   8Here's how to think about it: Let F() be the cumulative distribution
   9function for a probability distribution X.  We'll assume we've scaled
  10things so that X has mean 0 and standard deviation 1, though that's not
  11so important here.  Then:
  12
  13        F(x) = P(X <= x) = \int_{-inf}^x f
  14
  15where f is the probability density function.
  16
  17F is monotonically increasing, so has an inverse function G, with range
  180 to 1.  Here, G(t) = the x such that P(X <= x) = t.  (In general, G may
  19have singularities if X has point masses, i.e., points x such that
  20P(X = x) > 0.)
  21
  22Now we create a tabular representation of G as follows:  Choose some table
  23size N, and for the ith entry, put in G(i/N).  Let's call this table T.
  24
  25The claim now is, I can create a (discrete) random variable Y whose
  26distribution has the same approximate "shape" as X, simply by letting
  27Y = T(U), where U is a discrete uniform random variable with range 1 to N.
  28To see this, it's enough to show that Y's cumulative distribution function,
  29(let's call it H), is a discrete approximation to F.  But
  30
  31        H(x) = P(Y <= x)
  32             = (# of entries in T <= x) / N   -- as Y chosen uniformly from T
  33             = i/N, where i is the largest integer such that G(i/N) <= x
  34             = i/N, where i is the largest integer such that i/N <= F(x)
  35                        -- since G and F are inverse functions (and F is
  36                           increasing)
  37             = floor(N*F(x))/N
  38
  39as desired.
  40
  41II. How to create distribution tables (in theory)
  42
  43How can we create this table in practice? In some cases, F may have a
  44simple expression which allows evaluating its inverse directly.  The
  45pareto distribution is one example of this.  In other cases, and
  46especially for matching an experimentally observed distribution, it's
  47easiest simply to create a table for F and "invert" it.  Here, we give
  48a concrete example, namely how the new "experimental" distribution was
  49created.
  50
  511. Collect enough data points to characterize the distribution.  Here, I
  52collected 25,000 "ping" roundtrip times to a "distant" point (time.nist.gov).
  53That's far more data than is really necessary, but it was fairly painless to
  54collect it, so...
  55
  562. Normalize the data so that it has mean 0 and standard deviation 1.
  57
  583. Determine the cumulative distribution.  The code I wrote creates a table
  59covering the range -10 to +10, with granularity .00005.  Obviously, this
  60is absurdly over-precise, but since it's a one-time only computation, I
  61figured it hardly mattered.
  62
  634. Invert the table: for each table entry F(x) = y, make the y*TABLESIZE
  64(here, 4096) entry be x*TABLEFACTOR (here, 8192).  This creates a table
  65for the ("normalized") inverse of size TABLESIZE, covering its domain 0
  66to 1 with granularity 1/TABLESIZE.  Note that even with the granularity
  67used in creating the table for F, it's possible not all the entries in
  68the table for G will be filled in.  So, make a pass through the
  69inverse's table, filling in any missing entries by linear interpolation.
  70
  71III. How to create distribution tables (in practice)
  72
  73If you want to do all this yourself, I've provided several tools to help:
  74
  751. maketable does the steps 2-4 above, and then generates the appropriate
  76header file.  So if you have your own time distribution, you can generate
  77the header simply by:
  78
  79        maketable < time.values > header.h
  80
  812. As explained in the other README file, the somewhat sleazy way I have
  82of generating correlated values needs correction.  You can generate your
  83own correction tables by compiling makesigtable and makemutable with
  84your header file.  Check the Makefile to see how this is done.
  85
  863. Warning: maketable, makesigtable and especially makemutable do
  87enormous amounts of floating point arithmetic.  Don't try running
  88these on an old 486.  (NIST Net itself will run fine on such a
  89system, since in operation, it just needs to do a few simple integral
  90calculations.  But getting there takes some work.)
  91
  924. The tables produced are all normalized for mean 0 and standard
  93deviation 1.  How do you know what values to use for real?  Here, I've
  94provided a simple "stats" utility.  Give it a series of floating point
  95values, and it will return their mean (mu), standard deviation (sigma),
  96and correlation coefficient (rho).  You can then plug these values
  97directly into NIST Net.
  98