As per Relevance of the word framework, we have this rfc below:
Network Working Group V.
Request for Comments: 2330 Lawrence Berkeley National
Category: Informational G.
Advanced Network &
J.
M.
Pittsburgh Supercomputer
May 1998
Framework for IP Performance
1. Status of this
This memo provides information for the Internet community. It
not specify an Internet standard of any kind. Distribution of
memo is unlimited
2. Copyright
Copyright (C) The Internet Society (1998). All Rights Reserved
Table of
1. STATUS OF THIS MEMO.............................................1
2. COPYRIGHT NOTICE................................................1
3. INTRODUCTION....................................................2
4. CRITERIA FOR IP PERFORMANCE METRICS.............................3
5. TERMINOLOGY FOR PATHS AND CLOUDS................................4
6. FUNDAMENTAL CONCEPTS............................................5
6.1 Metrics......................................................5
6.2 Measurement Methodology......................................6
6.3 Measurements, Uncertainties, and Errors......................7
7. METRICS AND THE ANALYTICAL FRAMEWORK............................8
8. EMPIRICALLY SPECIFIED METRICS..................................11
9. TWO FORMS OF COMPOSITION.......................................12
9.1 Spatial Composition of Metrics..............................12
9.2 Temporal Composition of Formal Models and Empirical Metrics.13
10. ISSUES RELATED TO TIME........................................14
10.1 Clock Issues...............................................14
10.2 The Notion of "Wire Time"..................................17
11. SINGLETONS, SAMPLES, AND STATISTICS............................19
11.1 Methods of Collecting Samples..............................20
11.1.1 Poisson Sampling........................................21
11.1.2 Geometric Sampling......................................22
11.1.3 Generating Poisson Sampling Intervals...................22
Paxson, et. al. Informational [Page 1]
RFC 2330 Framework for IP Performance Metrics May 1998
11.2 Self-Consistency...........................................24
11.3 Defining Statistical Distributions.........................25
11.4 Testing For Goodness-of-Fit................................27
12. AVOIDING STOCHASTIC METRICS....................................28
13. PACKETS OF TYPE P..............................................29
14. INTERNET ADDRESSES VS. HOSTS...................................30
15. STANDARD-FORMED PACKETS........................................30
16. ACKNOWLEDGEMENTS...............................................31
17. SECURITY CONSIDERATIONS........................................31
18. APPENDIX.......................................................32
19. REFERENCES.....................................................38
20. AUTHORS' ADDRESSES.............................................39
21. FULL COPYRIGHT STATEMENT.......................................40
3.
The purpose of this memo is to define a general framework
particular metrics to be developed by the IETF's IP
Metrics effort, begun by the Benchmarking Methodology Working
(BMWG) of the Operational Requirements Area, and being continued
the IP Performance Metrics Working Group (IPPM) of the
Area
We begin by laying out several criteria for the metrics that
adopt. These criteria are designed to promote an IPPM effort
will maximize an accurate common understanding by Internet users
Internet providers of the performance and reliability both of end
to-end paths through the Internet and of specific 'IP clouds'
comprise portions of those paths
We next define some Internet vocabulary that will allow us to
clearly about Internet components such as routers, paths, and clouds
We then define the fundamental concepts of 'metric' and '
methodology', which allow us to speak clearly about
issues. Given these concepts, we proceed to discuss the
issue of measurement uncertainties and errors, and develop a key
somewhat subtle notion of how they relate to the analytical
shared by many aspects of the Internet engineering discipline.
then introduce the notion of empirically defined metrics, and
this part of the document with a general discussion of how
can be 'composed'.
The remainder of the document deals with a variety of issues
to defining sound metrics and methodologies: how to deal
imperfect clocks; the notion of 'wire time' as distinct from '
time'; how to aggregate sets of singleton metrics into samples
Paxson, et. al. Informational [Page 2]
RFC 2330 Framework for IP Performance Metrics May 1998
derive sound statistics from those samples; why it is recommended
avoid thinking about Internet properties in probabilistic terms (
as the probability that a packet is dropped), since these terms
include implicit assumptions about how the network behaves;
utility of defining metrics in terms of packets of a generic type
the benefits of preferring IP addresses to DNS host names; and
notion of 'standard-formed' packets. An appendix discusses
Anderson-Darling test for gauging whether a set of values matches
given statistical distribution, and gives C code for
implementation of the test
In some sections of the memo, we will surround some commentary
with the brackets {Comment: ... }. We stress that this commentary
only commentary, and is not itself part of the framework document
a proposal of particular metrics. In some cases this commentary
discuss some of the properties of metrics that might be envisioned
but the reader should assume that any such discussion is
only to shed light on points made in the framework document, and
to suggest any specific metrics
4. Criteria for IP Performance
The overarching goal of the IP Performance Metrics effort is
achieve a situation in which users and providers of
transport service have an accurate common understanding of
performance and reliability of the Internet component 'clouds'
they use/provide
To achieve this, performance and reliability metrics for
through the Internet must be developed. In several IETF
criteria for these metrics have been specified
+ The metrics must be concrete and well-defined
+ A methodology for a metric should have the property that it
repeatable: if the methodology is used multiple times
identical conditions, the same measurements should result in
same measurements
+ The metrics must exhibit no bias for IP clouds implemented
identical technology
+ The metrics must exhibit understood and fair bias for IP
implemented with non-identical technology
+ The metrics must be useful to users and providers in
the performance they experience or provide
Paxson, et. al. Informational [Page 3]
RFC 2330 Framework for IP Performance Metrics May 1998
+ The metrics must avoid inducing artificial performance goals
5. Terminology for Paths and
The following list defines terms that need to be precise in
development of path metrics. We begin with low-level notions
'host', 'router', and 'link', then proceed to define the notions
'path', 'IP cloud', and 'exchange' that allow us to segment a
into relevant pieces
host A computer capable of communicating using the
protocols; includes "routers".
link A single link-level connection between two (or more) hosts
includes leased lines, ethernets, frame relay clouds, etc
routerA host which facilitates network-level communication
hosts by forwarding IP packets
path A sequence of the form < h0, l1, h1, ..., ln, hn >, where n >=
0, each hi is a host, each li is a link between hi-1 and hi
each h1...hn-1 is a router. A pair is termed a 'hop'.
In an appropriate operational configuration, the links
routers in the path facilitate network-layer communication
packets from h0 to hn. Note that path is a
concept
Given a path, a subpath is any subsequence of the given
which is itself a path. (Thus, the first and last element of
subpath is a host.)
cloudAn undirected (possibly cyclic) graph whose vertices are
and whose edges are links that connect pairs of routers
Formally, ethernets, frame relay clouds, and other links
connect more than two routers are modelled as fully-
meshes of graph edges. Note that to connect to a cloud means
connect to a router of the cloud over a link; this link is
itself part of the cloud
A special case of a link, an exchange directly connects either
host to a cloud and/or one cloud to another cloud
cloud
A subpath of a given path, all of whose hosts are routers of
given cloud
Paxson, et. al. Informational [Page 4]
RFC 2330 Framework for IP Performance Metrics May 1998
path
A sequence of the form < h0, e1, C1, ..., en, hn >, where n >=
0, h0 and hn are hosts, each e1 ... en is an exchange, and
C1 ... Cn-1 is a cloud subpath
6. Fundamental
6.1.
In the operational Internet, there are several quantities related
the performance and reliability of the Internet that we'd like
know the value of. When such a quantity is carefully specified,
term the quantity a metric. We anticipate that there will
separate RFCs for each metric (or for each closely related group
metrics).
In some cases, there might be no obvious means to effectively
the metric; this is allowed, and even understood to be very useful
some cases. It is required, however, that the specification of
metric be as clear as possible about what quantity is
specified. Thus, difficulty in practical measurement is
allowed, but ambiguity in meaning is not
Each metric will be defined in terms of standard units
measurement. The international metric system will be used, with
following points specifically noted
+ When a unit is expressed in simple meters (for distance/length)
seconds (for duration), appropriate related units based
thousands or thousandths of acceptable units are acceptable
Thus, distances expressed in kilometers (km), durations
in milliseconds (ms), or microseconds (us) are allowed, but
centimeters (because the prefix is not in terms of thousands
thousandths).
+ When a unit is expressed in a combination of units,
related units based on thousands or thousandths of
units are acceptable, but all such thousands/thousandths must
grouped at the beginning. Thus, kilo-meters per second (km/s)
allowed, but meters per millisecond is not
+ The unit of information is the bit
+ When metric prefixes are used with bits or with
including bits, those prefixes will have their metric
(related to decimal 1000), and not the meaning conventional
computer storage (related to decimal 1024). In any RFC
defines a metric whose units include bits, this convention will
followed and will be repeated to ensure clarity for the reader
Paxson, et. al. Informational [Page 5]
RFC 2330 Framework for IP Performance Metrics May 1998
+ When a time is given, it will be expressed in UTC
Note that these points apply to the specifications for metrics
not, for example, to packet formats where octets will likely be
in preference/addition to bits
Finally, we note that some metrics may be defined purely in terms
other metrics; such metrics are call 'derived metrics'.
6.2. Measurement
For a given set of well-defined metrics, a number of
measurement methodologies may exist. A partial list includes
+ Direct measurement of a performance metric using injected
traffic. Example: measurement of the round-trip delay of an
packet of a given size over a given route at a given time
+ Projection of a metric from lower-level measurements. Example
given accurate measurements of propagation delay and bandwidth
each step along a path, projection of the complete delay for
path for an IP packet of a given size
+ Estimation of a constituent metric from a set of more
measurements. Example: given accurate measurements of delay for
given one-hop path for IP packets of different sizes,
of propagation delay for the link of that one-hop path
+ Estimation of a given metric at one time from a set of
metrics at other times. Example: given an accurate measurement
flow capacity at a past time, together with a set of
delay measurements for that past time and the current time,
given a model of flow dynamics, estimate the flow capacity
would be observed at the current time
This list is by no means exhaustive. The purpose is to point out
variety of measurement techniques
When a given metric is specified, a given measurement approach
be noted and discussed. That approach, however, is not formally
of the specification
A methodology for a metric should have the property that it
repeatable: if the methodology is used multiple times under
conditions, it should result in consistent measurements
Backing off a little from the word 'identical' in the
paragraph, we could more accurately use the word 'continuity'
describe a property of a given methodology: a methodology for a
metric exhibits continuity if, for small variations in conditions,
Paxson, et. al. Informational [Page 6]
RFC 2330 Framework for IP Performance Metrics May 1998
results in small variations in the resulting measurements.
more precisely, for every positive epsilon, there exists a
delta, such that if two sets of conditions are within delta of
other, then the resulting measurements will be within epsilon of
other. At this point, this should be taken as a heuristic
our intuition about one kind of robustness property rather than as
precise notion
A metric that has at least one methodology that exhibits
is said itself to exhibit continuity
Note that some metrics, such as hop-count along a path, are integer
valued and therefore cannot exhibit continuity in quite the
given above
Note further that, in practice, it may not be practical to know (
be able to quantify) the conditions relevant to a measurement at
given time. For example, since the instantaneous load (in packets
be served) at a given router in a high-speed wide-area network
vary widely over relatively brief periods and will be very hard
an external observer to quantify, various statistics of a
metric may be more repeatable, or may better exhibit continuity.
that case those particular statistics should be specified when
metric is specified
Finally, some measurement methodologies may be 'conservative' in
sense that the act of measurement does not modify, or only
modifies, the value of the performance metric the
attempts to measure. {Comment: for example, in a wide-are high-
network under modest load, a test using several small 'ping'
to measure delay would likely not interfere (much) with the
properties of that network as observed by others. The
statement about tests using a large flow to measure flow
would likely fail.}
6.3. Measurements, Uncertainties, and
Even the very best measurement methodologies for the very most
behaved metrics will exhibit errors. Those who develop
measurement methodologies, however, should strive to
Paxson, et. al. Informational [Page 7]
RFC 2330 Framework for IP Performance Metrics May 1998
+ minimize their uncertainties/errors
+ understand and document the sources of uncertainty/error,
+ quantify the amounts of uncertainty/error
For example, when developing a method for measuring delay,
how any errors in your clocks introduce errors into your
measurement, and quantify this effect as well as you can. In
cases, this will result in a requirement that a clock be at least
to a certain quality if it is to be used to make a
measurement
As a second example, consider the timing error due to
overheads within the computer making the measurement, as opposed
delays due to the Internet component being measured. The former is
measurement error, while the latter reflects the metric of interest
Note that one technique that can help avoid this overhead is the
of a packet filter/sniffer, running on a separate computer
records network packets and timestamps them accurately (see
discussion of 'wire time' below). The resulting trace can then
analyzed to assess the test traffic, minimizing the effect
measurement host delays, or at least allowing those delays to
accounted for. We note that this technique may prove beneficial
if the packet filter/sniffer runs on the same machine, because
measurements generally provide 'kernel-level' timestamping as
to less-accurate 'application-level' timestamping
Finally, we note that derived metrics (defined above) or metrics
exhibit spatial or temporal composition (defined below)
particular occasion for the analysis of measurement uncertainties
namely how the uncertainties propagate (conceptually) due to
derivation or composition
7. Metrics and the Analytical
As the Internet has evolved from the early packet-switching
of the 1960s, the Internet engineering community has evolved a
analytical framework of concepts. This analytical framework, or A
frame, used by designers and implementers of protocols, by
involved in measurement, and by those who study computer
performance using the tools of simulation and analysis, has
advantage to our work. A major objective here is to generate
characterizations that are consistent in both analytical
practical settings, since this will maximize the chances that non
empirical network study can be better correlated with, and used
further our understanding of, real network behavior
Paxson, et. al. Informational [Page 8]
RFC 2330 Framework for IP Performance Metrics May 1998
Whenever possible, therefore, we would like to develop and
off of the A-frame. Thus, whenever a metric to be specified
understood to be closely related to concepts within the A-frame,
will attempt to specify the metric in the A-frame's terms. In such
specification we will develop the A-frame by precisely defining
concepts needed for the metric, then leverage off of the A-frame
defining the metric in terms of those concepts
Such a metric will be called an 'analytically specified metric' or
more simply, an analytical metric
{Comment: Examples of such analytical metrics might include
propagation time of a
The time, in seconds, required by a single bit to travel from
output port on one Internet host across a single link to
Internet host
bandwidth of a link for packets of size
The capacity, in bits/second, where only those bits of the
packet are counted, for packets of size k bytes
routeThe path, as defined in Section 5, from A to B at a given time
hop count of a
The value 'n' of the route path
}
Note that we make no a priori list of just what A-frame
will emerge in these specifications, but we do encourage their
and urge that they be carefully specified so that, as our set
metrics develops, so will a specified set of A-frame
technically consistent with each other and consonant with
common understanding of those concepts within the general
community
These A-frame concepts will be intended to abstract from
Internet components in such a way that
+ the essential function of the component is retained
+ properties of the component relevant to the metrics we aim
create are retained
+ a subset of these component properties are potentially defined
analytical metrics,
Paxson, et. al. Informational [Page 9]
RFC 2330 Framework for IP Performance Metrics May 1998
+ those properties of actual Internet components not relevant
defining the metrics we aim to create are dropped
For example, when considering a router in the context of
forwarding, we might model the router as a component that
packets on an input link, queues them on a FIFO packet queue
finite size, employs tail-drop when the packet queue is full,
forwards them on an output link. The transmission speed (
bits/second) of the input and output links, the latency in the
(in seconds), and the maximum size of the packet queue (in bits)
relevant analytical metrics
In some cases, such analytical metrics used in relation to a
will be very closely related to specific metrics of the
of Internet paths. For example, an obvious formula (L + P/B
involving the latency in the router (L), the packet size (in bits
(P), and the transmission speed of the output link (B) might
approximate the increase in packet delay due to the insertion of
given router along a path
We stress, however, that well-chosen and well-specified A-
concepts and their analytical metrics will support more
metric creation efforts in less obvious ways
{Comment: for example, when considering the flow capacity of a path
it may be of real value to be able to model each of the routers
the path as packet forwarders as above. Techniques for
the flow capacity of a path might use the maximum packet queue
as a parameter in decidedly non-obvious ways. For example, as
maximum queue size increases, so will the ability of the router
continuously move traffic along an output link despite
in traffic from an input link. Estimating this increase, however
remains a research topic.}
Note that, when we specify A-frame concepts and analytical metrics
we will inevitably make simplifying assumptions. The key role
these concepts is to abstract the properties of the
components relevant to given metrics. Judgement is required to
making assumptions that bias the modeling and metric effort
one kind of design
{Comment: for example, routers might not use tail-drop, even
tail-drop might be easier to model analytically.}
Finally, note that different elements of the A-frame might well
different simplifying assumptions. For example, the abstraction of
router used to further the definition of path delay might treat
router's packet queue as a single FIFO queue, but the abstraction
Paxson, et. al. Informational [Page 10]
RFC 2330 Framework for IP Performance Metrics May 1998
a router used to further the definition of the handling of an RSVP
enabled packet might treat the router's packet queue as
bounded delay -- a contradictory assumption. This is not to say
we make contradictory assumptions at the same time, but that
different parts of our work might refine the simpler base concept
two divergent ways for different purposes
{Comment: in more mathematical terms, we would say that the A-
taken as a whole need not be consistent; but the set of
A-frame elements used to define a particular metric must be.}
8. Empirically Specified
There are useful performance and reliability metrics that do not
so neatly into the A-frame, usually because the A-frame lacks
detail or power for dealing with them. For example, "the best
capacity achievable along a path using an RFC-2001-compliant TCP
would be good to be able to measure, but we have no
framework of sufficient richness to allow us to cast that
capacity as an analytical metric
These notions can still be well specified by instead describing
reference methodology for measuring them
Such a metric will be called an 'empirically specified metric',
more simply, an empirical metric
Such empirical metrics should have three properties
+ we should have a clear definition for each in terms of
components
+ we should have at least one effective means to measure them,
+ to the extent possible, we should have an (necessarily incomplete
understanding of the metric in terms of the A-frame so that we
use our measurements to reason about the performance
reliability of A-frame components and of aggregations of A-
components
Paxson, et. al. Informational [Page 11]
RFC 2330 Framework for IP Performance Metrics May 1998
9. Two Forms of
9.1. Spatial Composition of
In some cases, it may be realistic and useful to define metrics
such a fashion that they exhibit spatial composition
By spatial composition, we mean a characteristic of some
metrics, in which the metric as applied to a (complete) path can
be defined for various subpaths, and in which the appropriate A-
concepts for the metric suggest useful relationships between
metric applied to these various subpaths (including the
path, the various cloud subpaths of a given path digest, and
single routers along the path). The effectiveness of
composition depends
+ on the usefulness in analysis of these relationships as applied
the relevant A-frame components,
+ on the practical use of the corresponding relationships as
to metrics and to measurement methodologies
{Comment: for example, consider some metric for delay of a 100-
packet across a path P, and consider further a path digest
C1, ..., en, hn> of P. The definition of such a metric might
a conjecture that the delay across P is very nearly the sum of
corresponding metric across the exchanges (ei) and clouds (Ci) of
given path digest. The definition would further include a note
how a corresponding relation applies to relevant A-frame components
both for the path P and for the exchanges and clouds of the
digest.}
When the definition of a metric includes a conjecture that the
across the path is related to the metric across the subpaths of
path, that conjecture constitutes a claim that the metric
spatial composition. The definition should then include
Paxson, et. al. Informational [Page 12]
RFC 2330 Framework for IP Performance Metrics May 1998
+ the specific conjecture applied to the metric
+ a justification of the practical utility of the composition
terms of making accurate measurements of the metric on the path
+ a justification of the usefulness of the composition in terms
making analysis of the path using A-frame concepts more effective
+ an analysis of how the conjecture could be incorrect
9.2. Temporal Composition of Formal Models and Empirical
In some cases, it may be realistic and useful to define metrics
such a fashion that they exhibit temporal composition
By temporal composition, we mean a characteristic of some
metric, in which the metric as applied to a path at a given time T
also defined for various times t0 < t1 < ... < tn < T, and in
the appropriate A-frame concepts for the metric suggests
relationships between the metric applied at times t0, ..., tn and
metric applied at time T. The effectiveness of temporal
depends
+ on the usefulness in analysis of these relationships as applied
the relevant A-frame components,
+ on the practical use of the corresponding relationships as
to metrics and to measurement methodologies
{Comment: for example, consider a metric for the expected
capacity across a path P during the five-minute period
the time T, and suppose further that we have the corresponding
for each of the four previous five-minute periods t0, t1, t2, and t3.
The definition of such a metric might include a conjecture that
flow capacity at time T can be estimated from a certain kind
extrapolation from the values of t0, ..., t3. The definition
further include a note on how a corresponding relation applies
relevant A-frame components
Note: any (spatial or temporal) compositions involving flow
are likely to be subtle, and temporal compositions are generally
subtle than spatial compositions, so the reader should
that the foregoing example is intentionally naive.}
When the definition of a metric includes a conjecture that the
across the path at a given time T is related to the metric across
path for a set of other times, that conjecture constitutes a
that the metric exhibits temporal composition. The definition
then include
Paxson, et. al. Informational [Page 13]
RFC 2330 Framework for IP Performance Metrics May 1998
+ the specific conjecture applied to the metric
+ a justification of the practical utility of the composition
terms of making accurate measurements of the metric on the path
+ a justification of the usefulness of the composition in terms
making analysis of the path using A-frame concepts more effective
10. Issues related to
10.1. Clock
Measurements of time lie at the heart of many Internet metrics
Because of this, it will often be crucial when designing
methodology for measuring a metric to understand the different
of errors and uncertainties introduced by imperfect clocks. In
section we define terminology for discussing the characteristics
clocks and touch upon related measurement issues which need to
addressed by any sound methodology
The Network Time Protocol (NTP; RFC 1305) defines a nomenclature
discussing clock characteristics, which we will also use
appropriate [Mi92]. The main goal of NTP is to provide
timekeeping over fairly long time scales, such as minutes to days
while for measurement purposes often what is more important
short-term accuracy, between the beginning of the measurement and
end, or over the course of gathering a body of measurements (
sample). This difference in goals sometimes leads to
definitions of terminology as well, as discussed below
To begin, we define a clock's "offset" at a particular moment as
difference between the time reported by the clock and the "true"
as defined by UTC. If the clock reports a time Tc and the true
is Tt, then the clock's offset is Tc - Tt
We will refer to a clock as "accurate" at a particular moment if
clock's offset is zero, and more generally a clock's "accuracy"
how close the absolute value of the offset is to zero. For NTP
accuracy also includes a notion of the frequency of the clock;
our purposes, we instead incorporate this notion into that of "skew",
because we define accuracy in terms of a single moment in time
than over an interval of time
A clock's "skew" at a particular moment is the frequency
(first derivative of its offset with respect to true time)
the clock and true time
Paxson, et. al. Informational [Page 14]
RFC 2330 Framework for IP Performance Metrics May 1998
As noted in RFC 1305, real clocks exhibit some variation in skew
That is, the second derivative of the clock's offset with respect
true time is generally non-zero. In keeping with RFC 1305, we
this quantity as the clock's "drift".
A clock's "resolution" is the smallest unit by which the clock's
is updated. It gives a lower bound on the clock's uncertainty
(Note that clocks can have very fine resolutions and yet be
inaccurate.) Resolution is defined in terms of seconds. However
resolution is relative to the clock's reported time and not to
time, so for example a resolution of 10 ms only means that the
updates its notion of time in 0.01 second increments, not that
is the true amount of time between updates
{Comment: Systems differ on how an application interface to the
reports the time on subsequent calls during which the clock has
advanced. Some systems simply return the same unchanged time
given for previous calls. Others may add a small increment to
reported time to maintain monotone-increasing timestamps.
systems that do the latter, we do *not* consider these
increments when defining the clock's resolution. They are instead
impediment to assessing the clock's resolution, since a
method for doing so is to repeatedly query the clock to determine
smallest non-zero difference in reported times.}
It is expected that a clock's resolution changes only rarely (
example, due to a hardware upgrade).
There are a number of interesting metrics for which some
measurement methodologies involve comparing times reported by
different clocks. An example is one-way packet delay [AK97]. Here
the time required for a packet to travel through the network
measured by comparing the time reported by a clock at one end of
packet's path, corresponding to when the packet first entered
network, with the time reported by a clock at the other end of
path, corresponding to when the packet finished traversing
network
We are thus also interested in terminology for describing how
clocks C1 and C2 compare. To do so, we introduce terms related
those above in which the notion of "true time" is replaced by
time as reported by clock C1. For example, clock C2's
relative to C1 at a particular moment is Tc2 - Tc1, the
difference in time reported by C2 and C1. To disambiguate
the use of the terms to compare two clocks versus the use of
terms to compare to true time, we will in the former case use
phrase "relative". So the offset defined earlier in this
is the "relative offset" between C2 and C1.
Paxson, et. al. Informational [Page 15]
RFC 2330 Framework for IP Performance Metrics May 1998
When comparing clocks, the analog of "resolution" is not "
resolution", but instead "joint resolution", which is the sum of
resolutions of C1 and C2. The joint resolution then indicates
conservative lower bound on the accuracy of any time
computed by subtracting timestamps generated by one clock from
generated by the other
If two clocks are "accurate" with respect to one another (
relative offset is zero), we will refer to the pair of clocks
"synchronized". Note that clocks can be highly synchronized
arbitrarily inaccurate in terms of how well they tell true time
This point is important because for many Internet measurements
synchronization between two clocks is more important than
accuracy of the clocks. The is somewhat true of skew, too: as
as the absolute skew is not too great, then minimal relative skew
more important, as it can induce systematic trends in packet
times measured by comparing timestamps produced by the two clocks
These distinctions arise because for Internet measurement what
often most important are differences in time as computed by
the output of two clocks. The process of computing the
removes any error due to clock inaccuracies with respect to
time; but it is crucial that the differences themselves
reflect differences in true time
Measurement methodologies will often begin with the step of
that two clocks are synchronized and have minimal skew and drift
{Comment: An effective way to assure these conditions (and also
accuracy) is by using clocks that derive their notion of time from
external source, rather than only the host computer's clock. (
latter are often subject to large errors.) It is further
that the clocks directly derive their time, for example by
immediate access to a GPS (Global Positioning System) unit.}
Two important concerns arise if the clocks indirectly derive
time using a network time synchronization protocol such as NTP
+ First, NTP's accuracy depends in part on the
(particularly delay) of the Internet paths used by the NTP peers
and these might be exactly the properties that we wish to measure
so it would be unsound to use NTP to calibrate such measurements
+ Second, NTP focuses on clock accuracy, which can come at
expense of short-term clock skew and drift. For example, when
host's clock is indirectly synchronized to a time source, if
synchronization intervals occur infrequently, then the host
sometimes be faced with the problem of how to adjust its current
incorrect time, Ti, with a considerably different, more
time it has just learned, Ta. Two general ways in which this
Paxson, et. al. Informational [Page 16]
RFC 2330 Framework for IP Performance Metrics May 1998
done are to either immediately set the current time to Ta, or
adjust the local clock's update frequency (hence, its skew)
that at some point in the future the local time Ti' will
with the more accurate time Ta'. The first mechanism
discontinuities and can also violate common assumptions
timestamps are monotone increasing. If the host's clock is
backward in time, sometimes this can be easily detected. If
clock is set forward in time, this can be harder to detect.
skew induced by the second mechanism can lead to
inaccuracies when computing differences in time, as
above
To illustrate why skew is a crucial concern, consider samples
one-way delays between two Internet hosts made at one
intervals. The true transmission delay between the hosts
plausibly be on the order of 50 ms for a transcontinental path.
the skew between the two clocks is 0.01%, that is, 1 part in 10,000,
then after 10 minutes of observation the error introduced into
measurement is 60 ms. Unless corrected, this error is enough
completely wipe out any accuracy in the transmission
measurement. Finally, we note that assessing skew errors
unsynchronized network clocks is an open research area. (See [Pa97]
for a discussion of detecting and compensating for these sorts
errors.) This shortcoming makes use of a solid, independent
source such as GPS especially desirable
10.2. The Notion of "Wire Time
Internet measurement is often complicated by the use of
hosts themselves to perform the measurement. These hosts
introduce delays, bottlenecks, and the like that are due to
or operating system effects and have nothing to do with the
behavior we would like to measure. This problem is
acute when timestamping of network events occurs at the
level
In order to provide a general way of talking about these effects,
introduce two notions of "wire time". These notions are only
in terms of an Internet host H observing an Internet link L at
particular location
+ For a given packet P, the 'wire arrival time' of P at H on L
the first time T at which any bit of P has appeared at H'
observational position on L
Paxson, et. al. Informational [Page 17]
RFC 2330 Framework for IP Performance Metrics May 1998
+ For a given packet P, the 'wire exit time' of P at H on L is
first time T at which all the bits of P have appeared at H'
observational position on L
Note that intrinsic to the definition is the notion of where on
link we are observing. This distinction is important because
large-latency links, we may obtain very different times depending
exactly where we are observing the link. We could allow
observational position to be an arbitrary location along the link
however, we define it to be in terms of an Internet host because
anticipate in practice that, for IPPM metrics, all such timing
be constrained to be performed by Internet hosts, rather
specialized hardware devices that might be able to monitor a link
locations where a host cannot. This definition also takes care
the problem of links that are comprised of multiple
channels. Because these multiple channels are not visible at the
layer, they cannot be individually observed in terms of the
definitions
It is possible, though one hopes uncommon, that a packet P might
multiple trips over a particular link L, due to a forwarding loop
These trips might even overlap, depending on the link technology
Whenever this occurs, we define a separate wire time associated
each instance of P seen at H's position on the link. This
is worth making because it serves as a reminder that notions
*the* unique time a packet passes a point in the Internet
inherently slippery
The term wire time has historically been used to loosely denote
time at which a packet appeared on a link, without exactly
whether this refers to the first bit, the last bit, or some
consideration. This informal definition is generally already
useful, as it is usually used to make a distinction between when
packet's propagation delays begin and cease to be due to the
rather than the endpoint hosts
When appropriate, metrics should be defined in terms of wire
rather than host endpoint times, so that the metric's
highlights the issue of separating delays due to the host from
due to the network
We note that one potential difficulty when dealing with wire
concerns IP fragments. It may be the case that, due
fragmentation, only a portion of a particular packet passes by H'
location. Such fragments are themselves legitimate packets and
well-defined wire times associated with them; but the larger
packet corresponding to their aggregate may not
Paxson, et. al. Informational [Page 18]
RFC 2330 Framework for IP Performance Metrics May 1998
We also note that these notions have not, to our knowledge,
previously defined in exact terms for Internet traffic
Consequently, we may find with experience that these
require some adjustment in the future
{Comment: It can sometimes be difficult to measure wire times.
technique is to use a packet filter to monitor traffic on a link
The architecture of these filters often attempts to associate
each packet a timestamp as close to the wire time as possible.
note however that one common source of error is to run the
filter on one of the endpoint hosts. In this case, it has
observed that some packet filters receive for some packets
corresponding to when the packet was *scheduled* to be injected
the network, rather than when it actually was *sent* out onto
network (wire time). There can be a substantial difference
these two times. A technique for dealing with this problem is to
the packet filter on a separate host that passively monitors
given link. This can be problematic however for some
technologies. See [Pa97] for a discussion of the sorts of
packet filters can exhibit. Finally, we note that packet
will often only capture the first fragment of a fragmented IP packet
due to the use of filtering on fields in the IP and
protocol headers. As we generally desire our
methodologies to avoid the complexity of creating fragmented traffic
one strategy for dealing with their presence as detected by a
filter is to flag that the measured traffic has an unusual form
abandon further analysis of the packet timing.}
11. Singletons, Samples, and
With experience we have found it useful to introduce a
between three distinct -- yet related -- notions
+ By a 'singleton' metric, we refer to metrics that are, in a sense
atomic. For example, a single instance of "bulk
capacity" from one host to another might be defined as a
metric, even though the instance involves measuring the timing
a number of Internet packets
+ By a 'sample' metric, we refer to metrics derived from a
singleton metric by taking a number of distinct
together. For example, we might define a sample metric of one-
delays from one host to another as an hour's worth
measurements, each made at Poisson intervals with a mean
of one second
Paxson, et. al. Informational [Page 19]
RFC 2330 Framework for IP Performance Metrics May 1998
+ By a 'statistical' metric, we refer to metrics derived from
given sample metric by computing some statistic of the
defined by the singleton metric on the sample. For example,
mean of all the one-way delay values on the sample given
might be defined as a statistical metric
By applying these notions of singleton, sample, and statistic in
consistent way, we will be able to reuse lessons learned about how
define samples and statistics on various metrics. The
among these three notions will thus make all our work more
and more intelligible by the community
In the remainder of this section, we will cover some topics
sampling and statistics that we believe will be important to
variety of metric definitions and measurement efforts
11.1. Methods of Collecting
The main reason for collecting samples is to see what sort
variations and consistencies are present in the metric
measured. These variations might be with respect to different
in the Internet, or different measurement times. When
variations based on a sample, one generally makes an assumption
the sample is "unbiased", meaning that the process of collecting
measurements in the sample did not skew the sample so that it
longer accurately reflects the metric's variations and consistencies
One common way of collecting samples is to make
separated by fixed amounts of time: periodic sampling.
sampling is particularly attractive because of its simplicity, but
suffers from two potential problems
+ If the metric being measured itself exhibits periodic behavior
then there is a possibility that the sampling will observe
part of the periodic behavior if the periods happen to
(either directly, or if one is a multiple of the other).
to this problem is the notion that periodic sampling can be
anticipated. Predictable sampling is susceptible to
if there are mechanisms by which a network component's
can be temporarily changed such that the sampling only sees
modified behavior
+ The act of measurement can perturb what is being measured (
example, injecting measurement traffic into a network alters
congestion level of the network), and repeated
perturbations can drive a network into a state of
(cf. [FJ94]), greatly magnifying what might individually be
effects
Paxson, et. al. Informational [Page 20]
RFC 2330 Framework for IP Performance Metrics May 1998
A more sound approach is based on "random additive sampling":
are separated by independent, randomly generated intervals that
a common statistical distribution G(t) [BM92]. The quality of
sampling depends on the distribution G(t). For example, if G(t
generates a constant value g with probability one, then the
reduces to periodic sampling with a period of g
Random additive sampling gains significant advantages. In general
it avoids synchronization effects and yields an unbiased estimate
the property being sampled. The only significant drawbacks with
are
+ it complicates frequency-domain analysis, because the samples
not occur at fixed intervals such as assumed by Fourier-
techniques;
+ unless G(t) is the exponential distribution (see below),
still remains somewhat predictable, as discussed for
sampling above
11.1.1. Poisson
It can be proved that if G(t) is an exponential distribution
rate lambda, that
G(t) = 1 - exp(-lambda * t
then the arrival of new samples *cannot* be predicted (and, again
the sampling is unbiased). Furthermore, the sampling
asymptotically unbiased even if the act of sampling affects
network's state. Such sampling is referred to as "Poisson sampling".
It is not prone to inducing synchronization, it can be used
accurately collect measurements of periodic behavior, and it is
prone to manipulation by anticipating when new samples will occur
Because of these valuable properties, we in general prefer
samples of Internet measurements are gathered using Poisson sampling
{Comment: We note, however, that there may be circumstances
favor use of a different G(t). For example, the
distribution is unbounded, so its use will on occasion
lengthy spaces between sampling times. We might instead desire
bound the longest such interval to a maximum value dT, to speed
convergence of the estimation derived from the sampling. This
be done by
G(t) = Unif(0, dT
Paxson, et. al. Informational [Page 21]
RFC 2330 Framework for IP Performance Metrics May 1998
that is, the uniform distribution between 0 and dT. This sampling
of course, becomes highly predictable if an interval of nearly
dT has elapsed without a sample occurring.}
In its purest form, Poisson sampling is done by
independent, exponentially distributed intervals and gathering
single measurement after each interval has elapsed. It can be
that if starting at time T one performs Poisson sampling over
interval dT, during which a total of N measurements happen to
made, then those measurements will be uniformly distributed over
interval [T, T+dT]. So another way of conducting Poisson sampling
to pick dT and N and generate N random sampling times uniformly
the interval [T, T+dT]. The two approaches are equivalent, except
N and dT are externally known. In that case, the property of
being able to predict measurement times is weakened (the
properties still hold). The N/dT approach has an advantage
dealing with fixed values of N and dT can be simpler than
with a fixed lambda but variable numbers of measurements
variably-sized intervals
11.1.2. Geometric
Closely related to Poisson sampling is "geometric sampling", in
external events are measured with a fixed probability p.
example, one might capture all the packets over a link but
record the packet to a trace file if a randomly generated
uniformly distributed between 0 and 1 is less than a given p
Geometric sampling has the same properties of being unbiased and
predictable in advance as Poisson sampling, so if it fits
particular Internet measurement task, it too is sound. See [CPB93]
for more discussion
11.1.3. Generating Poisson Sampling
To generate Poisson sampling intervals, one first determines the
lambda at which the singleton measurements will on average be
(e.g., for an average sampling interval of 30 seconds, we have
= 1/30, if the units of time are seconds). One then generates
series of exponentially-distributed (pseudo) random numbers E1, E2,
..., En. The first measurement is made at time E1, the next at
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
1. Many computers provide libraries that can do this. Given
Paxson, et. al. Informational [Page 22]
RFC 2330 Framework for IP Performance Metrics May 1998
Ui, to generate Ei one uses
Ei = -log(Ui) /
where log(Ui) is the natural logarithm of Ui. {Comment:
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
sampling, which we describe here as Methods 1 through 3. Method 1
the easiest to implement and has the most error, and method 3 is
most difficult to implement and has the least error (
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
of time required for the i'th measurement. If Mi is very
compared to 1/lambda then the potential error introduced by
technique is likewise small. As Mi becomes a non-negligible
of 1/lambda, the potential error increases
Method 2 attempts to correct this error by taking into account
amount of time required by the measurements (i.e., the Mi's)
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} <
then it is impossible to wait the proper amount of time. (Note
this case corresponds to needing to perform two
simultaneously.)
Paxson, et. al. Informational [Page 23]
RFC 2330 Framework for IP Performance Metrics May 1998
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
shortcomings of Methods 1 and 2. If, however,
measurements interfere with one another, then Method 3 does not
any benefit and may actually prove worse than Methods 1 or 2.
For Internet phenomena, it is not known to what degree
inaccuracies of these methods are significant. If the Mi's are
less than 1/lambda, then any of the three should suffice. If
Mi's are less than 1/lambda but perhaps not greatly less, then
2 is preferred to Method 1. If simultaneous measurements do
interfere with one another, then Method 3 is preferred, though it
be considerably harder to implement
11.2. Self-
A fundamental requirement for a sound measurement methodology is
measurement be made using as few unconfirmed assumptions as possible
Experience has painfully shown how easy it is to make an (
implicit) assumption that turns out to be incorrect. An example
incorporating into a measurement the reading of a clock
to a highly accurate source. It is easy to assume that the clock
therefore accurate; but due to software bugs, a loss of power in
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
measuring, but rather that, to the extent which is practical
assumptions should be tested. One powerful way for doing so
checking for self-consistency. Such checking applies both to
observed value(s) of the measurement *and the values used by
measurement process itself*. A simple example of the former is
when computing a round trip time, one should check to see if it
negative. Since negative time intervals are non-physical, if it
is negative that finding immediately flags an error. *These sorts
errors should then be investigated!* It is crucial to determine
the error lies, because only by doing so diligently can we build
faith in a methodology's fundamental soundness. For example,
could be that the round trip time is negative because during
measurement the clock was set backward in the process
synchronizing it with another source. But it could also be that
Paxson, et. al. Informational [Page 24]
RFC 2330 Framework for IP Performance Metrics May 1998
measurement program accesses uninitialized memory in one of
computations and, only very rarely, that leads to a
computation. This second error is more serious, if the same
is used by others to perform the same measurement, since then
too will suffer from incorrect results. Furthermore, once
it can be completely fixed
A more subtle example of testing for self-consistency comes
gathering samples of one-way Internet delays. If one has a
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),
see if the resulting line has a clearly non-zero slope. If so,
possible interpretation is that one of the clocks used in
measurements is skewed relative to the other. Another
is that the slope is actually due to genuine network effects
Determining which is indeed the case will often be
illuminating. (See [Pa97] for a discussion of distinguishing
relative clock skew and genuine network effects.) Furthermore,
making this check is part of the methodology, then a finding that
long-term slope is very near zero is positive evidence that
measurements are probably not biased by a difference in skew
A final example illustrates checking the measurement process
for self-consistency. Above we outline Poisson sampling techniques
based on generating exponentially-distributed intervals. A
measurement methodology would include testing the generated
to see whether they are indeed exponentially distributed (and also
see if they suffer from correlation). In the appendix we discuss
give C code for one such technique, a general-purpose, well-
goodness-of-fit test called the Anderson-Darling test
Finally, we note that what is truly relevant for Poisson sampling
Internet metrics is often not when the measurements began but
wire times corresponding to the measurement process. These
well be different, due to complications on the hosts used to
the measurement. Thus, even those with complete faith in
pseudo-random number generators and subsequent algorithms
encouraged to consider how they might test the assumptions of
measurement procedure as much as possible
11.3. Defining Statistical
One way of describing a collection of measurements (a sample) is as
statistical distribution -- informally, as percentiles. There
several slightly different ways of doing so. In this section
define a standard definition to give uniformity to
descriptions
Paxson, et. al. Informational [Page 25]
RFC 2330 Framework for IP Performance Metrics May 1998
The "empirical distribution function" (EDF) of a set of
measurements is a function F(x) which for any x gives the
proportion of the total measurements that were <= x. If x is
than the minimum value observed, then F(x) is 0. If it is greater
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
times each occurred from F(x) -- no information regarding the
in values is lost. Summarizing measurements using histograms, on
other hand, in general loses information about the different
observed, so the EDF is preferred
Using either the EDF or a histogram, however, we do lose
regarding the order in which the values were observed. Whether
loss is potentially significant will depend on the metric
measured
We will use the term "percentile" to refer to the smallest value of
for which F(x) >= a given percentage. So the 50th percentile of
example above is 4, since F(4) = 3/6 = 50%; the 25th percentile
-2, since F(-5) = 1/6 < 25%, and F(-2) = 2/6 >= 25%; the 100
percentile is 18; and the 0th percentile is -infinity, as is the 15
percentile
Care must be taken when using percentiles to summarize a sample
because they can lend an unwarranted appearance of more
than is really available. Any such summary must include the
size N, because any percentile difference finer than 1/N is below
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
point X for which the probability of observing a value <= X is
to the probability of observing a value > X. When estimating
median of a set of observations, the estimate depends on whether
number of observations, N, is odd or even
Paxson, et. al. Informational [Page 26]
RFC 2330 Framework for IP Performance Metrics May 1998
+ If N is odd, then the 50th percentile as defined above is used
the estimated median
+ If N is even, then the estimated median is the average of
central two observations; that is, if the observations are
in ascending order and numbered from 1 to N, where N = 2*K,
the estimated median is the average of the (K)'th and (K+1)'
observations
Usually the term "estimated" is dropped from the phrase "
median" and this value is simply referred to as the "median".
11.4. Testing For Goodness-of-
For some forms of measurement calibration we need to test whether
set of numbers is consistent with those numbers having been
from a particular distribution. An example is that to apply a self
consistency check to measurements made using a Poisson process,
test is to see whether the spacing between the sampling times
indeed reflect an exponential distribution; or if the dT/N
discussed above was used, whether the times are uniformly
across [T, dT].
{Comment: There are at least three possible sets of values we
test: the scheduled packet transmission times, as determined by
of a pseudo-random number generator; user-level timestamps made
before or after the system call for transmitting the packet; and
times for the packets as recorded using a packet filter. All
of these are potentially informative: failures for the
times to match an exponential distribution indicate inaccuracies
the random number generation; failures for the user-level
indicate inaccuracies in the timers used to schedule transmission
and failures for the wire times indicate inaccuracies in
transmitting the packets, perhaps due to contention for a
resource.}
There are a large number of statistical goodness-of-fit
for performing such tests. See [DS86] for a thorough discussion
That reference recommends the Anderson-Darling EDF test as being
good all-purpose test, as well as one that is especially good
detecting deviations from a given distribution in the lower and
tails of the EDF
It is important to understand that the nature of goodness-of-
tests is that one first selects a "significance level", which is
probability that the test will erroneously declare that the EDF of
given set of measurements fails to match a particular
when in fact the measurements do indeed reflect that distribution
Paxson, et. al. Informational [Page 27]
RFC 2330 Framework for IP Performance Metrics May 1998
Unless otherwise stated, IPPM goodness-of-fit tests are done using 5%
significance. This means that if the test is applied to 100
and 5 of those samples are deemed to have failed the test, then
samples are all consistent with the distribution being tested.
significantly more of the samples fail the test, then the
that the samples are consistent with the distribution being
must be rejected. If significantly fewer of the samples fail
test, then the samples have potentially been doctored too well to
the distribution. Similarly, some goodness-of-fit tests (
Anderson-Darling) can detect whether it is likely that a given
was doctored. We also use a significance of 5% for this case;
is, the test will report that a given honest sample is "too good
be true" 5% of the time, so if the test reports this
significantly more often than one time out of twenty, it is
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-
tests in the context of network measurement
12. Avoiding Stochastic
When defining metrics applying to a path, subpath, cloud, or
network element, we in general do not define them in stochastic
(probabilities). We instead prefer a deterministic definition. So
for example, rather than defining a metric about a "packet
probability between A and B", we would define a metric about
"packet loss rate between A and B". (A measurement given by
first definition might be "0.73", and by the second "73 packets
of 100".)
We emphasize that the above distinction concerns the *definitions*
*metrics*. It is not intended to apply to what sort of techniques
might use to analyze the results of measurements
The reason for this distinction is as follows. When definitions
made in terms of probabilities, there are often hidden assumptions
the definition about a stochastic model of the behavior
measured. The fundamental goal with avoiding probabilities in
metric definitions is to avoid biasing our definitions by
hidden assumptions
Paxson, et. al. Informational [Page 28]
RFC 2330 Framework for IP Performance Metrics May 1998
For example, an easy hidden assumption to make is that packet loss
a network component due to queueing overflows can be described
something that happens to any given packet with a
probability. In today's Internet, however, queueing drops
actually usually *deterministic*, and assuming that they should
described probabilistically can obscure crucial correlations
queueing drops among a set of packets. So it's better to
note stochastic assumptions, rather than have them sneak into
definitions implicitly
This does *not* mean that we abandon stochastic models
*understanding* network performance! It only means that when
IP metrics we avoid terms such as "probability" for terms
"proportion" or "rate". We will still use, for example,
sampling in order to estimate probabilities used by stochastic
related to the IP metrics. We also do not rule out the
of stochastic metrics when they are truly appropriate (for example
perhaps to model transmission errors caused by certain types of
noise).
13. Packets of Type
A fundamental property of many Internet metrics is that the value
the metric depends on the type of IP packet(s) used to make
measurement. Consider an IP-connectivity metric: one
different results depending on whether one is interested
connectivity for packets destined for well-known TCP ports
unreserved UDP ports, or those with invalid IP checksums, or
with TTL's of 16, for example. In some circumstances
distinctions will be highly interesting (for example, in the
of firewalls, or RSVP reservations).
Because of this distinction, we introduce the generic notion of
"packet of type P", wh