of course, becomes highly predictable if an interval of nearly length
dT has elapsed without a sample occurring.}
In its purest form, Poisson sampling is done by generating
independent, exponentially distributed intervals and gathering a
single measurement after each interval has elapsed. It can be shown
that if starting at time T one performs Poisson sampling over an
interval dT, during which a total of N measurements happen to be
made, then those measurements will be uniformly distributed over the
interval [T, T+dT]. So another way of conducting Poisson sampling is
to pick dT and N and generate N random sampling times uniformly over
the interval [T, T+dT]. The two approaches are equivalent, except if
N and dT are externally known. In that case, the property of not
being able to predict measurement times is weakened (the other
properties still hold). The N/dT approach has an advantage that
dealing with fixed values of N and dT can be simpler than dealing
with a fixed lambda but variable numbers of measurements over
variably-sized intervals.
11.1.2. Geometric Sampling
Closely related to Poisson sampling is "geometric sampling", in which
external events are measured with a fixed probability p. For
example, one might capture all the packets over a link but only
record the packet to a trace file if a randomly generated number
uniformly distributed between 0 and 1 is less than a given p.
Geometric sampling has the same properties of being unbiased and not
predictable in advance as Poisson sampling, so if it fits a
particular Internet measurement task, it too is sound. See [CPB93]
for more discussion.
11.1.3. Generating Poisson Sampling Intervals
To generate Poisson sampling intervals, one first determines the rate
lambda at which the singleton measurements will on average be made
(e.g., for an average sampling interval of 30 seconds, we have lambda
= 1/30, if the units of time are seconds). One then generates a
series of exponentially-distributed (pseudo) random numbers E1, E2,
..., En. The first measurement is made at time E1, the next at time
E1+E2, and so on.
One technique for generating exponentially-distributed (pseudo)
random numbers is based on the ability to generate U1, U2, ..., Un,
(pseudo) random numbers that are uniformly distributed between 0 and
1. Many computers provide libraries that can do this. Given such
Ui, to generate Ei one uses:
Ei = -log(Ui) / lambda
where log(Ui) is the natural logarithm of Ui. {Comment: This
technique is an instance of the more general "inverse transform"
method for generating random numbers with a given distribution.}
Implementation details:
There are at least three different methods for approximating Poisson
sampling, which we describe here as Methods 1 through 3. Method 1 is
the easiest to implement and has the most error, and method 3 is the
most difficult to implement and has the least error (potentially
none).
Method 1 is to proceed as follows:
1. Generate E1 and wait that long.
2. Perform a measurement.
3. Generate E2 and wait that long.
4. Perform a measurement.
5. Generate E3 and wait that long.
6. Perform a measurement ...
The problem with this approach is that the "Perform a measurement"
steps themselves take time, so the sampling is not done at times E1,
E1+E2, etc., but rather at E1, E1+M1+E2, etc., where Mi is the amount
of time required for the i'th measurement. If Mi is very small
compared to 1/lambda then the potential error introduced by this
technique is likewise small. As Mi becomes a non-negligible fraction
of 1/lambda, the potential error increases.
Method 2 attempts to correct this error by taking into account the
amount of time required by the measurements (i.e., the Mi's) and
adjusting the waiting intervals accordingly:
1. Generate E1 and wait that long.
2. Perform a measurement and measure M1, the time it took to do so.
3. Generate E2 and wait for a time E2-M1.
4. Perform a measurement and measure M2 ..
This approach works fine as long as E{i+1} >= Mi. But if E{i+1} < Mi
then it is impossible to wait the proper amount of time. (Note that
this case corresponds to needing to perform two measurements
simultaneously.)
Method 3 is generating a schedule of measurement times E1, E1+E2,
etc., and then sticking to it:
1. Generate E1, E2, ..., En.
2. Compute measurement times T1, T2, ..., Tn, as Ti = E1 + ... + Ei.
3. Arrange that at times T1, T2, ..., Tn, a measurement is made.
By allowing simultaneous measurements, Method 3 avoids the
shortcomings of Methods 1 and 2. If, however, simultaneous
measurements interfere with one another, then Method 3 does not gain
any benefit and may actually prove worse than Methods 1 or 2.
For Internet phenomena, it is not known to what degree the
inaccuracies of these methods are significant. If the Mi's are much
less than 1/lambda, then any of the three should suffice. If the
Mi's are less than 1/lambda but perhaps not greatly less, then Method
2 is preferred to Method 1. If simultaneous measurements do not
interfere with one another, then Method 3 is preferred, though it can
be considerably harder to implement.
11.2. Self-Consistency
A fundamental requirement for a sound measurement methodology is that
measurement be made using as few unconfirmed assumptions as possible.
Experience has painfully shown how easy it is to make an (often
implicit) assumption that turns out to be incorrect. An example is
incorporating into a measurement the reading of a clock synchronized
to a highly accurate source. It is easy to assume that the clock is
therefore accurate; but due to software bugs, a loss of power in the
source, or a loss of communication between the source and the clock,
the clock could actually be quite inaccurate.
This is not to argue that one must not make *any* assumptions when
measuring, but rather that, to the extent which is practical,
assumptions should be tested. One powerful way for doing so involves
checking for self-consistency. Such checking applies both to the
observed value(s) of the measurement *and the values used by the
measurement process itself*. A simple example of the former is that
when computing a round trip time, one should check to see if it is
negative. Since negative time intervals are non-physical, if it ever
is negative that finding immediately flags an error. *These sorts of
errors should then be investigated!* It is crucial to determine where
the error lies, because only by doing so diligently can we build up
faith in a methodology's fundamental soundness. For example, it
could be that the round trip time is negative because during the
measurement the clock was set backward in the process of
synchronizing it with another source. But it could also be that the
measurement program accesses uninitialized memory in one of its
computations and, only very rarely, that leads to a bogus
computation. This second error is more serious, if the same program
is used by others to perform the same measurement, since then they
too will suffer from incorrect results. Furthermore, once uncovered
it can be completely fixed.
A more subtle example of testing for self-consistency comes from
gathering samples of one-way Internet delays. If one has a large
sample of such delays, it may well be highly telling to, for example,
fit a line to the pairs of (time of measurement, measured delay), to
see if the resulting line has a clearly non-zero slope. If so, a
possible interpretation is that one of the clocks used in the
measurements is skewed relative to the other. Another interpretation
is that the slope is actually due to genuine network effects.
Determining which is indeed the case will often be highly
illuminating. (See [Pa97] for a discussion of distinguishing between
relative clock skew and genuine network effects.) Furthermore, if
making this check is part of the methodology, then a finding that the
long-term slope is very near zero is positive evidence that the
measurements are probably not biased by a difference in skew.
A final example illustrates checking the measurement process itself
for self-consistency. Above we outline Poisson sampling techniques,
based on generating exponentially-distributed intervals. A sound
measurement methodology would include testing the generated intervals
to see whether they are indeed exponentially distributed (and also to
see if they suffer from correlation). In the appendix we discuss and
give C code for one such technique, a general-purpose, well-regarded
goodness-of-fit test called the Anderson-Darling test.
Finally, we note that what is truly relevant for Poisson sampling of
Internet metrics is often not when the measurements began but the
wire times corresponding to the measurement process. These could
well be different, due to complications on the hosts used to perform
the measurement. Thus, even those with complete faith in their
pseudo-random number generators and subsequent algorithms are
encouraged to consider how they might test the assumptions of each
measurement procedure as much as possible.
11.3. Defining Statistical Distributions
One way of describing a collection of measurements (a sample) is as a
statistical distribution -- informally, as percentiles. There are
several slightly different ways of doing so. In this section we
define a standard definition to give uniformity to these
descriptions.
The "empirical distribution function" (EDF) of a set of scalar
measurements is a function F(x) which for any x gives the fractional
proportion of the total measurements that were <= x. If x is less
than the minimum value observed, then F(x) is 0. If it is greater or
equal to the maximum value observed, then F(x) is 1.
For example, given the 6 measurements:
-2, 7, 7, 4, 18, -5
Then F(-8) = 0, F(-5) = 1/6, F(-5.0001) = 0, F(-4.999) = 1/6, F(7) =
5/6, F(18) = 1, F(239) = 1.
Note that we can recover the different measured values and how many
times each occurred from F(x) -- no information regarding the range
in values is lost. Summarizing measurements using histograms, on the
other hand, in general loses information about the different values
observed, so the EDF is preferred.
Using either the EDF or a histogram, however, we do lose information
regarding the order in which the values were observed. Whether this
loss is potentially significant will depend on the metric being
measured.
We will use the term "percentile" to refer to the smallest value of x
for which F(x) >= a given percentage. So the 50th percentile of the
example above is 4, since F(4) = 3/6 = 50%; the 25th percentile is
-2, since F(-5) = 1/6 < 25%, and F(-2) = 2/6 >= 25%; the 100th
percentile is 18; and the 0th percentile is -infinity, as is the 15th
percentile.
Care must be taken when using percentiles to summarize a sample,
because they can lend an unwarranted appearance of more precision
than is really available. Any such summary must include the sample
size N, because any percentile difference finer than 1/N is below the
resolution of the sample.
See [DS86] for more details regarding EDF's.
We close with a note on the common (and important!) notion of median.
In statistics, the median of a distribution is defined to be the
point X for which the probability of observing a value <= X is equal
to the probability of observing a value > X. When estimating the
median of a set of observations, the estimate depends on whether the
number of observations, N, is odd or even:
+ If N is odd, then the 50th percentile as defined above is used as
the estimated median.
+ If N is even, then the estimated median is the average of the
central two observations; that is, if the observations are sorted
in ascending order and numbered from 1 to N, where N = 2*K, then
the estimated median is the average of the (K)'th and (K+1)'th
observations.
Usually the term "estimated" is dropped from the phrase "estimated
median" and this value is simply referred to as the "median".
11.4. Testing For Goodness-of-Fit
For some forms of measurement calibration we need to test whether a
set of numbers is consistent with those numbers having been drawn
from a particular distribution. An example is that to apply a self-
consistency check to measurements made using a Poisson process, one
test is to see whether the spacing between the sampling times does
indeed reflect an exponential distribution; or if the dT/N approach
discussed above was used, whether the times are uniformly distributed
across [T, dT].
{Comment: There are at least three possible sets of values we could
test: the scheduled packet transmission times, as determined by use
of a pseudo-random number generator; user-level timestamps made just
before or after the system call for transmitting the packet; and wire
times for the packets as recorded using a packet filter. All three
of these are potentially informative: failures for the scheduled
times to match an exponential distribution indicate inaccuracies in
the random number generation; failures for the user-level times
indicate inaccuracies in the timers used to schedule transmission;
and failures for the wire times indicate inaccuracies in actually
transmitting the packets, perhaps due to contention for a shared
resource.}
There are a large number of statistical goodness-of-fit techniques
for performing such tests. See [DS86] for a thorough discussion.
That reference recommends the Anderson-Darling EDF test as being a
good all-purpose test, as well as one that is especially good at
detecting deviations from a given distribution in the lower and upper
tails of the EDF.
It is important to understand that the nature of goodness-of-fit
tests is that one first selects a "significance level", which is the
probability that the test will erroneously declare that the EDF of a
given set of measurements fails to match a particular distribution
when in fact the measurements do indeed reflect that distribution.
Unless otherwise stated, IPPM goodness-of-fit tests are done using 5%
significance. This means that if the test is applied to 100 samples
and 5 of those samples are deemed to have failed the test, then the
samples are all consistent with the distribution being tested. If
significantly more of the samples fail the test, then the assumption
that the samples are consistent with the distribution being tested
must be rejected. If significantly fewer of the samples fail the
test, then the samples have potentially been doctored too well to fit
the distribution. Similarly, some goodness-of-fit tests (including
Anderson-Darling) can detect whether it is likely that a given sample
was doctored. We also use a significance of 5% for this case; that
is, the test will report that a given honest sample is "too good to
be true" 5% of the time, so if the test reports this finding
significantly more often than one time out of twenty, it is an
indication that something unusual is occurring.
The appendix gives sample C code for implementing the Anderson-
Darling test, as well as further discussing its use.
See [Pa94] for a discussion of goodness-of-fit and closeness-of-fit
tests in the context of network measurement.
12. Avoiding Stochastic Metrics
When defining metrics applying to a path, subpath, cloud, or other
network element, we in general do not define them in stochastic terms
(probabilities). We instead prefer a deterministic definition. So,
for example, rather than defining a metric about a "packet loss
probability between A and B", we would define a metric about a
"packet loss rate between A and B". (A measurement given by the
first definition might be "0.73", and by the second "73 packets out
of 100".)
We emphasize that the above distinction concerns the *definitions* of
*metrics*. It is not intended to apply to what sort of techniques we
might use to analyze the results of measurements.
The reason for this distinction is as follows. When definitions are
made in terms of probabilities, there are often hidden assumptions in
the definition about a stochastic model of the behavior being
measured. The fundamental goal with avoiding probabilities in our
metric definitions is to avoid biasing our definitions by these
hidden assumptions.
For example, an easy hidden assumption to make is that packet loss in
a network component due to queueing overflows can be described as
something that happens to any given packet with a particular
probability. In today's Internet, however, queueing drops are
actually usually *deterministic*, and assuming that they should be
described probabilistically can obscure crucial correlations between
queueing drops among a set of packets. So it's better to explicitly
note stochastic assumptions, rather than have them sneak into our
definitions implicitly.
This does *not* mean that we abandon stochastic models for
*understanding* network performance! It only means that when defining
IP metrics we avoid terms such as "probability" for terms like
"proportion" or "rate". We will still use, for example, random
sampling in order to estimate probabilities used by stochastic models
related to the IP metrics. We also do not rule out the possibility
of stochastic metrics when they are truly appropriate (for example,
perhaps to model transmission errors caused by certain types of line
noise).
13. Packets of Type P
A fundamental property of many Internet metrics is that the value of
the metric depends on the type of IP packet(s) used to make the
measurement. Consider an IP-connectivity metric: one obtains
different results depending on whether one is interested in
connectivity for packets destined for well-known TCP ports or
unreserved UDP ports, or those with invalid IP checksums, or those
with TTL's of 16, for example. In some circumstances these
distinctions will be highly interesting (for example, in the presence
of firewalls, or RSVP reservations).
Because of this distinction, we introduce the generic notion of a
"packet of type P", where in some contexts P will be explicitly
defined (i.e., exactly what type of packet we mean), partially
defined (e.g., "with a payload of B octets"), or left generic. Thus
we may talk about generic IP-type-P-connectivity or more specific
IP-port-HTTP-connectivity. Some metrics and methodologies may be
fruitfully defined using generic type P definitions which are then
made specific when performing actual measurements.
Whenever a metric's value depends on the type of the packets involved
in the metric, the metric's name will include either a specific type
or a phrase such as "type-P". Thus we will not define an "IP-
connectivity" metric but instead an "IP-type-P-connectivity" metric
and/or perhaps an "IP-port-HTTP-connectivity" metric. This naming
convention serves as an important reminder that one must be conscious
of the exact type of traffic being measured.
A closely related note: it would be very useful to know if a given
Internet component treats equally a class C of different types of
packets. If so, then any one of those types of packets can be used
for subsequent measurement of the component. This suggests we devise
a metric or suite of metrics that attempt to determine C.
14. Internet Addresses vs. Hosts
When considering a metric for some path through the Internet, it is
often natural to think about it as being for the path from Internet
host H1 to host H2. A definition in these terms, though, can be
ambiguous, because Internet hosts can be attached to more than one
network. In this case, the result of the metric will depend on which
of these networks is actually used.
Because of this ambiguity, usually such definitions should instead be
defined in terms of Internet IP addresses. For the common case of a
unidirectional path through the Internet, we will use the term "Src"
to denote the IP address of the beginning of the path, and "Dst" to
denote the IP address of the end.
15. Standard-Formed Packets
Unless otherwise stated, all metric definitions that concern IP
packets include an implicit assumption that the packet is *standard
formed*. A packet is standard formed if it meets all of the
following criteria:
+ Its length as given in the IP header corresponds to the size of
the IP header plus the size of the payload.
+ It includes a valid IP header: the version field is 4 (later, we
will expand this to include 6); the header length is >= 5; the
checksum is correct.
+ It is not an IP fragment.
+ The source and destination addresses correspond to the hosts in
question.
+ Either the packet possesses sufficient TTL to travel from the
source to the destination if the TTL is decremented by one at each
hop, or it possesses the maximum TTL of 255.
+ It does not contain IP options unless explicitly noted.
+ If a transport header is present, it too contains a valid checksum
and other valid fields.
We further require that if a packet is described as having a "length
of B octets", then 0 <= B <= 65535; and if B is the payload length in
octets, then B <= (65535-IP header size in octets).
So, for example, one might imagine defining an IP connectivity metric
as "IP-type-P-connectivity for standard-formed packets with the IP
TOS field set to 0", or, more succinctly, "IP-type-P-connectivity
with the IP TOS field set to 0", since standard-formed is already
implied by convention.
A particular type of standard-formed packet often useful to consider
is the "minimal IP packet from A to B" - this is an IP packet with
the following properties:
+ It is standard-formed.
+ Its data payload is 0 octets.
+ It contains no options.
(Note that we do not define its protocol field, as different values
may lead to different treatment by the network.)
When defining IP metrics we keep in mind that no packet smaller or
simpler than this can be transmitted over a correctly operating IP
network.
16. Acknowledgements
The comments of Brian Carpenter, Bill Cerveny, Padma Krishnaswamy
Jeff Sedayao and Howard Stanislevic are appreciated.
17. Security Considerations
This document concerns definitions and concepts related to Internet
measurement. We discuss measurement procedures only in high-level
terms, regarding principles that lend themselves to sound
measurement. As such, the topics discussed do not affect the
security of the Internet or of applications which run on it.
That said, it should be recognized that conducting Internet
measurements can raise both security and privacy concerns. Active
techniques, in which traffic is injected into the network, can be
abused for denial-of-service attacks disguised as legitimate
measurement activity. Passive techniques, in which existing traffic
is recorded and analyzed, can expose the contents of Internet traffic
to unintended recipients. Consequently, the definition of each
metric and methodology must include a corresponding discussion of
security considerations.
18. Appendix
Below we give routines written in C for computing the Anderson-
Darling test statistic (A2) for determining whether a set of values
is consistent with a given statistical distribution. Externally, the
two main routines of interest are:
double exp_A2_known_mean(double x[], int n, double mean)
double unif_A2_known_range(double x[], int n,
double min_val, double max_val)
Both take as their first argument, x, the array of n values to be
tested. (Upon return, the elements of x are sorted.) The remaining
parameters characterize the distribution to be used: either the mean
(1/lambda), for an exponential distribution, or the lower and upper
bounds, for a uniform distribution. The names of the routines stress
that these values must be known in advance, and *not* estimated from
the data (for example, by computing its sample mean). Estimating the
parameters from the data *changes* the significance level of the test
statistic. While [DS86] gives alternate significance tables for some
instances in which the parameters are estimated from the data, for
our purposes we expect that we should indeed know the parameters in
advance, since what we will be testing are generally values such as
packet sending times that we wish to verify follow a known
distribution.
Both routines return a significance level, as described earlier. This
is a value between 0 and 1. The correct use of the routines is to
pick in advance the threshold for the significance level to test;
generally, this will be 0.05, corresponding to 5%, as also described
above. Subsequently, if the routines return a value strictly less
than this threshold, then the data are deemed to be inconsistent with
the presumed distribution, *subject to an error corresponding to the
significance level*. That is, for a significance level of 5%, 5% of
the time data that is indeed drawn from the presumed distribution
will be erroneously deemed inconsistent.
Thus, it is important to bear in mind that if these routines are used
frequently, then one will indeed encounter occasional failures, even
if the data is unblemished.
Another important point concerning significance levels is that it is
unsound to compare them in order to determine which of two sets of
values is a "better" fit to a presumed distribution. Such testing
should instead be done using "closeness-of-fit metrics" such as the
lambda^2 metric described in [Pa94].
While the routines provided are for exponential and uniform
distributions with known parameters, it is generally straight-forward
to write comparable routines for any distribution with known
parameters. The heart of the A2 tests lies in a statistic computed
for testing whether a set of values is consistent with a uniform
distribution between 0 and 1, which we term Unif(0, 1). If we wish
to test whether a set of values, X, is consistent with a given
distribution G(x), we first compute
Y = G_inverse(X)
If X is indeed distributed according to G(x), then Y will be
distributed according to Unif(0, 1); so by testing Y for consistency
with Unif(0, 1), we also test X for consistency with G(x).
We note, however, that the process of computing Y above might yield
values of Y outside the range (0..1). Such values should not occur
if X is indeed distributed according to G(x), but easily can occur if
it is not. In the latter case, we need to avoid computing the
central A2 statistic, since floating-point exceptions may occur if
any of the values lie outside (0..1). Accordingly, the routines
check for this possibility, and if encountered, return a raw A2
statistic of -1. The routine that converts the raw A2 statistic to a
significance level likewise propagates this value, returning a
significance level of -1. So, any use of these routines must be
prepared for a possible negative significance level.
The last important point regarding use of A2 statistic concerns n,
the number of values being tested. If n < 5 then the test is not
meaningful, and in this case a significance level of -1 is returned.
On the other hand, for "real" data the test *gains* power as n
becomes larger. It is well known in the statistics community that
real data almost never exactly matches a theoretical distribution,
even in cases such as rolling dice a great many times (see [Pa94] for
a brief discussion and references). The A2 test is sensitive enough
that, for sufficiently large sets of real data, the test will almost
always fail, because it will manage to detect slight imperfections in
the fit of the data to the distribution.
For example, we have found that when testing 8,192 measured wire
times for packets sent at Poisson intervals, the measurements almost
always fail the A2 test. On the other hand, testing 128 measurements
failed at 5% significance only about 5% of the time, as expected.
Thus, in general, when the test fails, care must be taken to
understand why it failed.
The remainder of this appendix gives C code for the routines
mentioned above.
/* Routines for computing the Anderson-Darling A2 test statistic.
*
* Implemented based on the description in "Goodness-of-Fit
* Techniques," R. D'Agostino and M. Stephens, editors,
* Marcel Dekker, Inc., 1986.
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/* Returns the raw A^2 test statistic for n sorted samples
* z[0] .. z[n-1], for z ~ Unif(0,1).
*/
extern double compute_A2(double z[], int n);
/* Returns the significance level associated with a A^2 test
* statistic value of A2, assuming no parameters of the tested
* distribution were estimated from the data.
*/
extern double A2_significance(double A2);
/* Returns the A^2 significance level for testing n observations
* x[0] .. x[n-1] against an exponential distribution with the
* given mean.
*
* SIDE EFFECT: the x[0..n-1] are sorted upon return.
*/
extern double exp_A2_known_mean(double x[], int n, double mean);
/* Returns the A^2 significance level for testing n observations
* x[0] .. x[n-1] against the uniform distribution [min_val, max_val].
*
* SIDE EFFECT: the x[0..n-1] are sorted upon return.
*/
extern double unif_A2_known_range(double x[], int n,
double min_val, double max_val);
/* Returns a pseudo-random number distributed according to an
* exponential distribution with the given mean.
*/
extern double random_exponential(double mean);
/* Helper function used by qsort() to sort double-precision
* floating-point values.
*/
static int
compare_double(const void *v1, const void *v2)
{
double d1 = *(double *) v1;
double d2 = *(double *) v2;
if (d1 < d2)
return -1;
else if (d1 > d2)
return 1;
else
return 0;
}
double
compute_A2(double z[], int n)
{
int i;
double sum = 0.0;
if ( n < 5 )
/* Too few values. */
return -1.0;
/* If any of the values are outside the range (0, 1) then
* fail immediately (and avoid a possible floating point
* exception in the code below).
*/
for (i = 0; i < n; ++i)
if ( z[i] <= 0.0 || z[i] >= 1.0 )
return -1.0;
/* Page 101 of D'Agostino and Stephens. */
for (i = 1; i <= n; ++i) {
sum += (2 * i - 1) * log(z[i-1]);
sum += (2 * n + 1 - 2 * i) * log(1.0 - z[i-1]);
}
return -n - (1.0 / n) * sum;
}
double
A2_significance(double A2)
{
/* Page 105 of D'Agostino and Stephens. */
if (A2 < 0.0)
return A2; /* Bogus A2 value - propagate it. */
/* Check for possibly doctored values. */
if (A2 <= 0.201)
return 0.99;
else if (A2 <= 0.240)
return 0.975;
else if (A2 <= 0.283)
return 0.95;
else if (A2 <= 0.346)
return 0.90;
else if (A2 <= 0.399)
return 0.85;
/* Now check for possible inconsistency. */
if (A2 <= 1.248)
return 0.25;
else if (A2 <= 1.610)
return 0.15;
else if (A2 <= 1.933)
return 0.10;
else if (A2 <= 2.492)
return 0.05;
else if (A2 <= 3.070)
return 0.025;
else if (A2 <= 3.880)
return 0.01;
else if (A2 <= 4.500)
return 0.005;
else if (A2 <= 6.000)
return 0.001;
else
return 0.0;
}
double
exp_A2_known_mean(double x[], int n, double mean)
{
int i;
double A2;
/* Sort the first n values. */
qsort(x, n, sizeof(x[0]), compare_double);
/* Assuming they match an exponential distribution, transform
* them to Unif(0,1).
*/
for (i = 0; i < n; ++i) {
x[i] = 1.0 - exp(-x[i] / mean);
}
/* Now make the A^2 test to see if they're truly uniform. */
A2 = compute_A2(x, n);
return A2_significance(A2);
}
double
unif_A2_known_range(double x[], int n, double min_val, double max_val)
{
int i;
double A2;
double range = max_val - min_val;
/* Sort the first n values. */
qsort(x, n, sizeof(x[0]), compare_double);
/* Transform Unif(min_val, max_val) to Unif(0,1). */
for (i = 0; i < n; ++i)
x[i] = (x[i] - min_val) / range;
/* Now make the A^2 test to see if they're truly uniform. */
A2 = compute_A2(x, n);
return A2_significance(A2);
}
double
random_exponential(double mean)
{
return -mean * log1p(-drand48());
}
19. References
[AK97] G. Almes and S. Kalidindi, "A One-way Delay Metric for IPPM",
Work in Progress, November 1997.
[BM92] I. Bilinskis and A. Mikelsons, Randomized Signal Processing,
Prentice Hall International, 1992.
[DS86] R. D'Agostino and M. Stephens, editors, Goodness-of-Fit
Techniques, Marcel Dekker, Inc., 1986.
[CPB93] K. Claffy, G. Polyzos, and H-W. Braun, "Application of
Sampling Methodologies to Network Traffic Characterization," Proc.
SIGCOMM '93, pp. 194-203, San Francisco, September 1993.
[FJ94] S. Floyd and V. Jacobson, "The Synchronization of Periodic
Routing Messages," IEEE/ACM Transactions on Networking, 2(2), pp.
122-136, April 1994.
[Mi92] Mills, D., "Network Time Protocol (Version 3) Specification,
Implementation and Analysis", RFC1305, March 1992.
[Pa94] V. Paxson, "Empirically-Derived Analytic Models of Wide-Area
TCP Connections," IEEE/ACM Transactions on Networking, 2(4), pp.
316-336, August 1994.
[Pa96] V. Paxson, "Towards a Framework for Defining Internet
Performance Metrics," Proceedings of INET '96,
ftp://ftp.ee.lbl.gov/papers/metrics-framework-INET96.ps.Z
[Pa97] V. Paxson, "Measurements and Analysis of End-to-End Internet
Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997,
ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz.
20. Authors' Addresses
Vern Paxson
MS 50B/2239
Lawrence Berkeley National Laboratory
University of California
Berkeley, CA 94720
USA
Phone: +1 510/486-7504
EMail: vern@ee.lbl.gov
Guy Almes
Advanced Network & Services, Inc.
200 Business Park Drive
Armonk, NY 10504
USA
Phone: +1 914/765-1120
EMail: almes@advanced.org
Jamshid Mahdavi
Pittsburgh Supercomputing Center
4400 5th Avenue
Pittsburgh, PA 15213
USA
Phone: +1 412/268-6282
EMail: mahdavi@psc.edu
Matt Mathis
Pittsburgh Supercomputing Center
4400 5th Avenue
Pittsburgh, PA 15213
USA
Phone: +1 412/268-3319
EMail: mathis@psc.edu
21. Full Copyright Statement
Copyright (C) The Internet Society (1998). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.