Home | History | Annotate | only in /external/iproute2/netem
Up to higher level directory
NameDateSize
experimental.dat22-Oct-202078.8K
Makefile22-Oct-2020638
maketable.c22-Oct-20205K
normal.c22-Oct-2020952
pareto.c22-Oct-2020771
paretonormal.c22-Oct-20201.6K
README.distribution22-Oct-20204.4K
stats.c22-Oct-20201.5K

README.distribution

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