< draft-ietf-ippm-framework-01.txt   draft-ietf-ippm-framework-02.txt >
Network Working Group V. Paxson, Lawrence Berkeley National Lab Network Working Group V. Paxson, Lawrence Berkeley National Lab
Internet Draft G. Almes, Advanced Network & Services Internet Draft G. Almes, Advanced Network & Services
J. Mahdavi, Pittsburgh Supercomputer Center J. Mahdavi, Pittsburgh Supercomputer Center
M. Mathis, Pittsburgh Supercomputer Center M. Mathis, Pittsburgh Supercomputer Center
Expiration Date: May 1998 November 1997 Expiration Date: July 1998 February 1998
Framework for IP Performance Metrics Framework for IP Performance Metrics
<draft-ietf-ippm-framework-01.txt> <draft-ietf-ippm-framework-02.txt>
1. Status of this Memo 1. Status of this Memo
This document is an Internet Draft. Internet Drafts are working This document is an Internet Draft. Internet Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute and its working groups. Note that other groups may also distribute
working documents as Internet Drafts. working documents as Internet Drafts.
Internet Drafts are draft documents valid for a maximum of six Internet Drafts are draft documents valid for a maximum of six
months, and may be updated, replaced, or obsoleted by other documents months, and may be updated, replaced, or obsoleted by other documents
skipping to change at page 1, line 34 skipping to change at page 2, line 5
To learn the current status of any Internet Draft, please check the To learn the current status of any Internet Draft, please check the
``1id-abstracts.txt'' listing contained in the Internet Drafts shadow ``1id-abstracts.txt'' listing contained in the Internet Drafts shadow
directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast). ftp.isi.edu (US West Coast).
This memo provides information for the Internet community. This memo This memo provides information for the Internet community. This memo
does not specify an Internet standard of any kind. Distribution of does not specify an Internet standard of any kind. Distribution of
this memo is unlimited. this memo is unlimited.
ID Framework for IP Performance Metrics February 1998
Table of Contents
1. STATUS OF THIS MEMO.............................................1
2. INTRODUCTION....................................................2
3. CRITERIA FOR IP PERFORMANCE METRICS.............................4
4. TERMINOLOGY FOR PATHS AND CLOUDS................................4
5. FUNDAMENTAL CONCEPTS............................................5
5.1 Metrics......................................................5
5.2 Measurement Methodology......................................6
5.2 Measurements, Uncertainties, and Errors......................8
6. METRICS AND THE ANALYTICAL FRAMEWORK............................9
7. EMPIRICALLY SPECIFIED METRICS..................................11
8. TWO FORMS OF COMPOSITION.......................................12
8.1 Spatial Composition of Metrics..............................12
8.2 Temporal Composition of Formal Models and Empirical Metrics.13
9. ISSUES RELATED TO TIME.........................................14
9.1 Clock Issues................................................14
9.2 The Notion of "Wire Time"...................................17
10. SINGLETONS, SAMPLES, AND STATISTICS............................19
10.1 Methods of Collecting Samples..............................20
10.1.1 Poisson Sampling........................................21
10.1.2 Geometric Sampling......................................22
10.1.3 Generating Poisson Sampling Intervals...................22
10.2 Self-Consistency...........................................23
10.3 Defining Statistical Distributions.........................25
10.4 Testing For Goodness-of-Fit................................26
11. AVOIDING STOCHASTIC METRICS....................................27
12. PACKETS OF TYPE P..............................................28
13. INTERNET ADDRESSES VS. HOSTS...................................29
14. STANDARD-FORMED PACKETS........................................29
15. ACKNOWLEDGEMENTS...............................................30
16. SECURITY CONSIDERATIONS........................................31
17. APPENDIX.......................................................31
18. REFERENCES.....................................................37
19. AUTHORS' ADDRESSES.............................................37
2. Introduction 2. Introduction
The purpose of this memo is to define a general framework for The purpose of this memo is to define a general framework for
particular metrics to be developed by the IETF's IP Performance particular metrics to be developed by the IETF's IP Performance
Metrics effort, begun by the Benchmarking Methodology Working Group Metrics effort, begun by the Benchmarking Methodology Working Group
(BMWG) of the Operational Requirements Area, and being continued by (BMWG) of the Operational Requirements Area, and being continued by
the IP Performance Metrics Working Group (IPPM) of the Transport the IP Performance Metrics Working Group (IPPM) of the Transport
Area. Area.
We begin by laying out several criteria for the metrics that we We begin by laying out several criteria for the metrics that we
adopt. These criteria are designed to promote an IPPM effort that adopt. These criteria are designed to promote an IPPM effort that
ID Framework for IP Performance Metrics February 1998
will maximize an accurate common understanding by Internet users and will maximize an accurate common understanding by Internet users and
Internet providers of the performance and reliability both of end- Internet providers of the performance and reliability both of end-
to-end paths through the Internet and of specific 'IP clouds' that to-end paths through the Internet and of specific 'IP clouds' that
ID Framework for IP Performance Metrics November 1997
comprise portions of those paths. comprise portions of those paths.
We next define some Internet vocabulary that will allow us to speak We next define some Internet vocabulary that will allow us to speak
clearly about Internet components such as routers, paths, and clouds. clearly about Internet components such as routers, paths, and clouds.
We then define the fundamental concepts of 'metric' and 'measurement We then define the fundamental concepts of 'metric' and 'measurement
methodology', which allow us to speak clearly about measurement methodology', which allow us to speak clearly about measurement
issues. Given these concepts, we proceed to discuss the important issues. Given these concepts, we proceed to discuss the important
issue of measurement uncertainties and errors, and develop a key, issue of measurement uncertainties and errors, and develop a key,
somewhat subtle notion of how they relate to the analytical framework somewhat subtle notion of how they relate to the analytical framework
skipping to change at page 3, line 5 skipping to change at page 4, line 5
In some sections of the memo, we will surround some commentary text In some sections of the memo, we will surround some commentary text
with the brackets {Comment: ... }. We stress that this commentary is with the brackets {Comment: ... }. We stress that this commentary is
only commentary, and is not itself part of the framework document or only commentary, and is not itself part of the framework document or
a proposal of particular metrics. In some cases this commentary will a proposal of particular metrics. In some cases this commentary will
discuss some of the properties of metrics that might be envisioned, discuss some of the properties of metrics that might be envisioned,
but the reader should assume that any such discussion is intended but the reader should assume that any such discussion is intended
only to shed light on points made in the framework document, and not only to shed light on points made in the framework document, and not
to suggest any specific metrics. to suggest any specific metrics.
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
3. Criteria for IP Performance Metrics 3. Criteria for IP Performance Metrics
The overarching goal of the IP Performance Metrics effort is to The overarching goal of the IP Performance Metrics effort is to
achieve a situation in which users and providers of Internet achieve a situation in which users and providers of Internet
transport service have an accurate common understanding of the transport service have an accurate common understanding of the
performance and reliability of the Internet component 'clouds' that performance and reliability of the Internet component 'clouds' that
they use/provide. they use/provide.
To achieve this, performance and reliability metrics for paths To achieve this, performance and reliability metrics for paths
skipping to change at page 4, line 5 skipping to change at page 5, line 5
hosts by forwarding IP packets. hosts by forwarding IP packets.
path A sequence of the form < h0, l1, h1, ..., ln, hn >, where n >= 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, 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 <li, hi> is termed a 'hop'. each h1...hn-1 is a router. A pair <li, hi> is termed a 'hop'.
In an appropriate operational configuration, the links and In an appropriate operational configuration, the links and
routers in the path facilitate network-layer communication of routers in the path facilitate network-layer communication of
packets from h0 to hn. Note that path is a unidirectional con- packets from h0 to hn. Note that path is a unidirectional con-
cept. cept.
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
subpath subpath
Given a path, a subpath is any subsequence of the given path Given a path, a subpath is any subsequence of the given path
which is itself a path. (Thus, the first and last element of a which is itself a path. (Thus, the first and last element of a
subpath is a host.) subpath is a host.)
cloudAn undirected (possibly cyclic) graph whose vertices are routers cloudAn undirected (possibly cyclic) graph whose vertices are routers
and whose edges are links that connect pairs of routers. For- and whose edges are links that connect pairs of routers. For-
mally, ethernets, frame relay clouds, and other links that con- mally, ethernets, frame relay clouds, and other links that con-
nect more than two routers are modelled as fully-connected nect more than two routers are modelled as fully-connected
skipping to change at page 5, line 5 skipping to change at page 6, line 5
In some cases, there might be no obvious means to effectively measure In some cases, there might be no obvious means to effectively measure
the metric; this is allowed, and even understood to be very useful in the metric; this is allowed, and even understood to be very useful in
some cases. It is required, however, that the specification of the some cases. It is required, however, that the specification of the
metric be as clear as possible about what quantity is being speci- metric be as clear as possible about what quantity is being speci-
fied. Thus, difficulty in practical measurement is sometimes fied. Thus, difficulty in practical measurement is sometimes
allowed, but ambiguity in meaning is not. allowed, but ambiguity in meaning is not.
Each metric will be defined in terms of standard units of measure- Each metric will be defined in terms of standard units of measure-
ment. The international metric system will be used, with the ment. The international metric system will be used, with the
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
following points specifically noted: following points specifically noted:
+ When a unit is expressed in simple meters (for distance/length) or + When a unit is expressed in simple meters (for distance/length) or
seconds (for duration), appropriate related units based on seconds (for duration), appropriate related units based on
thousands or thousandths of acceptable units are acceptable. thousands or thousandths of acceptable units are acceptable.
Thus, distances expressed in kilometers (km), durations expressed Thus, distances expressed in kilometers (km), durations expressed
in milliseconds (ms), or microseconds (us) are allowed, but not in milliseconds (ms), or microseconds (us) are allowed, but not
centimeters (because the prefix is not in terms of thousands or centimeters (because the prefix is not in terms of thousands or
thousandths). thousandths).
+ When a unit is expressed in a combination of units, appropriate + When a unit is expressed in a combination of units, appropriate
skipping to change at page 6, line 5 skipping to change at page 7, line 5
packet of a given size over a given route at a given time. packet of a given size over a given route at a given time.
+ Projection of a metric from lower-level measurements. Example: + Projection of a metric from lower-level measurements. Example:
given accurate measurements of propagation delay and bandwidth for given accurate measurements of propagation delay and bandwidth for
each step along a path, projection of the complete delay for the each step along a path, projection of the complete delay for the
path for an IP packet of a given size. path for an IP packet of a given size.
+ Estimation of a consituent metric from a set of more aggregated + Estimation of a consituent metric from a set of more aggregated
measurements. Example: given accurate measurements of delay for a measurements. Example: given accurate measurements of delay for a
given one-hop path for IP packets of different sizes, estimation given one-hop path for IP packets of different sizes, estimation
of propagation delay for the link of that one-hop path. of propagation delay for the link of that one-hop path.
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
+ Estimation of a given metric at one time from a set of related + Estimation of a given metric at one time from a set of related
metrics at other times. Example: given an accurate measurement of metrics at other times. Example: given an accurate measurement of
flow capacity at a past time, together with a set of accurate flow capacity at a past time, together with a set of accurate
delay measurements for that past time and the current time, and delay measurements for that past time and the current time, and
given a model of flow dynamics, estimate the flow capacity that given a model of flow dynamics, estimate the flow capacity that
would be observed at the current time. would be observed at the current time.
This list is by no means exhaustive. The purpose is to point out the This list is by no means exhaustive. The purpose is to point out the
variety of measurement techniques. variety of measurement techniques.
skipping to change at page 7, line 5 skipping to change at page 8, line 5
be served) at a given router in a high-speed wide-area network can be served) at a given router in a high-speed wide-area network can
vary widely over relatively brief periods and will be very hard for vary widely over relatively brief periods and will be very hard for
an external observer to quantify, various statistics of a given an external observer to quantify, various statistics of a given
metric may be more repeatable, or may better exhibit continuity. In metric may be more repeatable, or may better exhibit continuity. In
that case those particular statistics should be specified when the that case those particular statistics should be specified when the
metric is specified. metric is specified.
Finally, some measurement methodologies may be 'conservative' in the Finally, some measurement methodologies may be 'conservative' in the
sense that the act of measurement does not modify, or only slightly sense that the act of measurement does not modify, or only slightly
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
modifies, the value of the performance metric the methodology modifies, the value of the performance metric the methodology
attempts to measure. {Comment: for example, in a wide-are high-speed attempts to measure. {Comment: for example, in a wide-are high-speed
network under modest load, a test using several small 'ping' packets network under modest load, a test using several small 'ping' packets
to measure delay would likely not interfere (much) with the delay to measure delay would likely not interfere (much) with the delay
properties of that network as observed by others. The corresponding properties of that network as observed by others. The corresponding
statement about tests using a large flow to measure flow capacity statement about tests using a large flow to measure flow capacity
would likely fail.} would likely fail.}
5.3. Measurements, Uncertainties, and Errors 5.3. Measurements, Uncertainties, and Errors
skipping to change at page 8, line 5 skipping to change at page 9, line 5
if the packet filter/sniffer runs on the same machine, because such if the packet filter/sniffer runs on the same machine, because such
measurements generally provide 'kernel-level' timestamping as opposed measurements generally provide 'kernel-level' timestamping as opposed
to less-accurate 'application-level' timestamping. to less-accurate 'application-level' timestamping.
Finally, we note that derived metrics (defined above) or metrics that Finally, we note that derived metrics (defined above) or metrics that
exhibit spatial or temporal composition (defined below) offer partic- exhibit spatial or temporal composition (defined below) offer partic-
ular occasion for the analysis of measurement uncertainties, namely ular occasion for the analysis of measurement uncertainties, namely
how the uncertainties propagate (conceptually) due to the derivation how the uncertainties propagate (conceptually) due to the derivation
or composition. or composition.
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
6. Metrics and the Analytical Framework 6. Metrics and the Analytical Framework
As the Internet has evolved from the early packet-switching studies As the Internet has evolved from the early packet-switching studies
of the 1960s, the Internet engineering community has evolved a common of the 1960s, the Internet engineering community has evolved a common
analytical framework of concepts. This analytical framework, or A- analytical framework of concepts. This analytical framework, or A-
frame, used by designers and implementers of protocols, by those frame, used by designers and implementers of protocols, by those
involved in measurement, and by those who study computer network per- involved in measurement, and by those who study computer network per-
formance using the tools of simulation and analysis, has great advan- formance using the tools of simulation and analysis, has great advan-
tage to our work. A major objective here is to generate network tage to our work. A major objective here is to generate network
skipping to change at page 9, line 5 skipping to change at page 10, line 5
The value 'n' of the route path. The value 'n' of the route path.
} }
Note that we make no a priori list of just what A-frame concepts Note that we make no a priori list of just what A-frame concepts
will emerge in these specifications, but we do encourage their use will emerge in these specifications, but we do encourage their use
and urge that they be carefully specified so that, as our set of and urge that they be carefully specified so that, as our set of
metrics develops, so will a specified set of A-frame concepts metrics develops, so will a specified set of A-frame concepts
technically consistent with each other and consonent with the com- technically consistent with each other and consonent with the com-
mon understanding of those concepts within the general Internet mon understanding of those concepts within the general Internet
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
community. community.
These A-frame concepts will be intended to abstract from actual These A-frame concepts will be intended to abstract from actual
Internet components in such a way that: Internet components in such a way that:
+ the essential function of the component is retained, + the essential function of the component is retained,
+ properties of the component relevant to the metrics we aim to + properties of the component relevant to the metrics we aim to
create are retained, create are retained,
+ a subset of these component properties are potentially defined as + a subset of these component properties are potentially defined as
analytical metrics, and analytical metrics, and
skipping to change at page 10, line 5 skipping to change at page 11, line 5
continuously move traffic along an output link despite fluctuations continuously move traffic along an output link despite fluctuations
in traffic from an input link. Estimating this increase, however, in traffic from an input link. Estimating this increase, however,
remains a research topic.} remains a research topic.}
Note that, when we specify A-frame concepts and analytical metrics, Note that, when we specify A-frame concepts and analytical metrics,
we will inevitably make simplifying assumptions. The key role of we will inevitably make simplifying assumptions. The key role of
these concepts is to abstract the properties of the Internet com- these concepts is to abstract the properties of the Internet com-
ponents relevant to given metrics. Judgement is required to avoid ponents relevant to given metrics. Judgement is required to avoid
making assumptions that bias the modeling and metric effort toward making assumptions that bias the modeling and metric effort toward
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
one kind of design. one kind of design.
{Comment: for example, routers might not use tail-drop, even though {Comment: for example, routers might not use tail-drop, even though
tail-drop might be easier to model analytically.} tail-drop might be easier to model analytically.}
Finally, note that different elements of the A-frame might well make Finally, note that different elements of the A-frame might well make
different simplifying assumptions. For example, the abstraction of a different simplifying assumptions. For example, the abstraction of a
router used to further the definition of path delay might treat the router used to further the definition of path delay might treat the
router's packet queue as a single FIFO queue, but the abstraction of router's packet queue as a single FIFO queue, but the abstraction of
skipping to change at page 11, line 5 skipping to change at page 12, line 5
Such empirical metrics should have three properties: Such empirical metrics should have three properties:
+ we should have a clear definition for each in terms of Internet + we should have a clear definition for each in terms of Internet
components, components,
+ we should have at least one effective means to measure them, and + we should have at least one effective means to measure them, and
+ to the extent possible, we should have an (necessarily incomplete) + to the extent possible, we should have an (necessarily incomplete)
understanding of the metric in terms of the A-frame so that we can understanding of the metric in terms of the A-frame so that we can
use our measurements to reason about the performance and reliabil- use our measurements to reason about the performance and reliabil-
ity of A-frame components and of aggregations of A-frame com- ity of A-frame components and of aggregations of A-frame com-
ponents. ponents.
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
8. Two Forms of Composition 8. Two Forms of Composition
8.1. Spatial Composition of Metrics 8.1. Spatial Composition of Metrics
In some cases, it may be realistic and useful to define metrics in In some cases, it may be realistic and useful to define metrics in
such a fashion that they exhibit spatial composition. such a fashion that they exhibit spatial composition.
By spatial composition, we mean a characteristic of some path By spatial composition, we mean a characteristic of some path
metrics, in which the metric as applied to a (complete) path can also metrics, in which the metric as applied to a (complete) path can also
skipping to change at page 12, line 5 skipping to change at page 13, line 5
path, that conjecture constitutes a claim that the metric exhibits path, that conjecture constitutes a claim that the metric exhibits
spatial composition. The definition should then include: spatial composition. The definition should then include:
+ the specific conjecture applied to the metric, + the specific conjecture applied to the metric,
+ a justification of the practical utility of the composition in + a justification of the practical utility of the composition in
terms of making accurate measurements of the metric on the path, terms of making accurate measurements of the metric on the path,
+ a justification of the usefulness of the composition in terms of + a justification of the usefulness of the composition in terms of
making analysis of the path using A-frame concepts more effective, making analysis of the path using A-frame concepts more effective,
and and
+ an analysis of how the conjecture could be incorrect. + an analysis of how the conjecture could be incorrect.
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
8.2. Temporal Composition of Formal Models and Empirical Metrics 8.2. Temporal Composition of Formal Models and Empirical Metrics
In some cases, it may be realistic and useful to define metrics in In some cases, it may be realistic and useful to define metrics in
such a fashion that they exhibit temporal composition. such a fashion that they exhibit temporal composition.
By temporal composition, we mean a characteristic of some path By temporal composition, we mean a characteristic of some path
metric, in which the metric as applied to a path at a given time T is metric, in which the metric as applied to a path at a given time T is
also defined for various times t0 < t1 < ... < tn < T, and in which also defined for various times t0 < t1 < ... < tn < T, and in which
the appropriate A-frame concepts for the metric suggests useful rela- the appropriate A-frame concepts for the metric suggests useful rela-
skipping to change at page 13, line 5 skipping to change at page 14, line 5
path for a set of other times, that conjecture constitutes a claim path for a set of other times, that conjecture constitutes a claim
that the metric exhibits temporal composition. The definition should that the metric exhibits temporal composition. The definition should
then include: then include:
+ the specific conjecture applied to the metric, + the specific conjecture applied to the metric,
+ a justification of the practical utility of the composition in + a justification of the practical utility of the composition in
terms of making accurate measurements of the metric on the path, terms of making accurate measurements of the metric on the path,
and and
+ a justification of the usefulness of the composition in terms of + a justification of the usefulness of the composition in terms of
making analysis of the path using A-frame concepts more effective. making analysis of the path using A-frame concepts more effective.
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
9. Issues related to Time 9. Issues related to Time
9.1. Clock Issues 9.1. Clock Issues
Measurements of time lie at the heart of many Internet metrics. Measurements of time lie at the heart of many Internet metrics.
Because of this, it will often be crucial when designing a methodol- Because of this, it will often be crucial when designing a methodol-
ogy for measuring a metric to understand the different types of ogy for measuring a metric to understand the different types of
errors and uncertainties introduced by imperfect clocks. In this errors and uncertainties introduced by imperfect clocks. In this
section we define terminology for discussing the characteristics of section we define terminology for discussing the characteristics of
skipping to change at page 14, line 5 skipping to change at page 15, line 5
As noted in RFC 1305, real clocks exhibit some variation in skew. As noted in RFC 1305, real clocks exhibit some variation in skew.
That is, the second derivative of the clock's offset with respect to That is, the second derivative of the clock's offset with respect to
true time is generally non-zero. In keeping with RFC 1305, we define true time is generally non-zero. In keeping with RFC 1305, we define
this quantity as the clock's "drift". this quantity as the clock's "drift".
A clock's "resolution" is the smallest unit by which the clock's time A clock's "resolution" is the smallest unit by which the clock's time
is updated. It gives a lower bound on the clock's uncertainty. is updated. It gives a lower bound on the clock's uncertainty.
(Note that clocks can have very fine resolutions and yet be wildly (Note that clocks can have very fine resolutions and yet be wildly
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
inaccurate.) Resolution is defined in terms of seconds. However, inaccurate.) Resolution is defined in terms of seconds. However,
resolution is relative to the clock's reported time and not to true resolution is relative to the clock's reported time and not to true
time, so for example a resolution of 10 ms only means that the clock time, so for example a resolution of 10 ms only means that the clock
updates its notion of time in 0.01 second increments, not that this updates its notion of time in 0.01 second increments, not that this
is the true amount of time between updates. is the true amount of time between updates.
{Comment: Systems differ on how an application interface to the clock {Comment: Systems differ on how an application interface to the clock
reports the time on subsequent calls during which the clock has not reports the time on subsequent calls during which the clock has not
advanced. Some systems simply return the same unchanged time as advanced. Some systems simply return the same unchanged time as
skipping to change at page 14, line 29 skipping to change at page 15, line 29
when defining the clock's resolution. They are instead an impediment when defining the clock's resolution. They are instead an impediment
to assessing the clock's resolution, since a natural method for doing to assessing the clock's resolution, since a natural method for doing
so is to repeatedly query the clock to determine the smallest non- so is to repeatedly query the clock to determine the smallest non-
zero difference in reported times.} zero difference in reported times.}
It is expected that a clock's resolution changes only rarely (for It is expected that a clock's resolution changes only rarely (for
example, due to a hardware upgrade). example, due to a hardware upgrade).
There are a number of interesting metrics for which some natural There are a number of interesting metrics for which some natural
measurement methodologies involve comparing times reported by two measurement methodologies involve comparing times reported by two
different clocks. An example is one-way packet delay (currently an different clocks. An example is one-way packet delay [AK96]. Here,
Internet Draft [AK96]). Here, the time required for a packet to the time required for a packet to travel through the network is meas-
travel through the network is measured by comparing the time reported ured by comparing the time reported by a clock at one end of the
by a clock at one end of the packet's path, corresponding to when the packet's path, corresponding to when the packet first entered the
packet first entered the network, with the time reported by a clock network, with the time reported by a clock at the other end of the
at the other end of the path, corresponding to when the packet fin- path, corresponding to when the packet finished traversing the net-
ished traversing the network. work.
We are thus also interested in terminology for describing how two We are thus also interested in terminology for describing how two
clocks C1 and C2 compare. To do so, we introduce terms related to clocks C1 and C2 compare. To do so, we introduce terms related to
those above in which the notion of "true time" is replaced by the those above in which the notion of "true time" is replaced by the
time as reported by clock C1. For example, clock C2's offset rela- time as reported by clock C1. For example, clock C2's offset rela-
tive to C1 at a particular moment is Tc2 - Tc1, the instantaneous tive to C1 at a particular moment is Tc2 - Tc1, the instantaneous
difference in time reported by C2 and C1. To disambiguate between difference in time reported by C2 and C1. To disambiguate between
the use of the terms to compare two clocks versus the use of the the use of the terms to compare two clocks versus the use of the
terms to compare to true time, we will in the former case use the terms to compare to true time, we will in the former case use the
phrase "relative". So the offset defined earlier in this paragraph phrase "relative". So the offset defined earlier in this paragraph
is the "relative offset" between C2 and C1. is the "relative offset" between C2 and C1.
When comparing clocks, the analog of "resolution" is not "relative When comparing clocks, the analog of "resolution" is not "relative
resolution", but instead "joint resolution", which is the sum of the resolution", but instead "joint resolution", which is the sum of the
resolutions of C1 and C2. The joint resolution then indicates a con- resolutions of C1 and C2. The joint resolution then indicates a con-
servative lower bound on the accuracy of any time intervals computed servative lower bound on the accuracy of any time intervals computed
by subtracting timestamps generated by one clock from those generated by subtracting timestamps generated by one clock from those generated
by the other. by the other.
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
If two clocks are "accurate" with respect to one another (their rela- If two clocks are "accurate" with respect to one another (their rela-
tive offset is zero), we will refer to the pair of clocks as "syn- tive offset is zero), we will refer to the pair of clocks as "syn-
chronized". Note that clocks can be highly synchronized yet arbi- chronized". Note that clocks can be highly synchronized yet arbi-
trarily inaccurate in terms of how well they tell true time. This trarily inaccurate in terms of how well they tell true time. This
point is important because for many Internet measurements, synchroni- point is important because for many Internet measurements, synchroni-
zation between two clocks is more important than the accuracy of the zation between two clocks is more important than the accuracy of the
clocks. The is somewhat true of skew, too: as long as the absolute clocks. The is somewhat true of skew, too: as long as the absolute
skew is not too great, then minimal relative skew is more important, skew is not too great, then minimal relative skew is more important,
as it can induce systematic trends in packet transit times measured as it can induce systematic trends in packet transit times measured
skipping to change at page 16, line 5 skipping to change at page 17, line 5
time it has just learned, Ta. Two general ways in which this is time it has just learned, Ta. Two general ways in which this is
done are to either immediately set the current time to Ta, or to done are to either immediately set the current time to Ta, or to
adjust the local clock's update frequency (hence, its skew) so adjust the local clock's update frequency (hence, its skew) so
that at some point in the future the local time Ti' will agree that at some point in the future the local time Ti' will agree
with the more accurate time Ta'. The first mechanism introduces with the more accurate time Ta'. The first mechanism introduces
discontinuities and can also violate common assumptions that discontinuities and can also violate common assumptions that
timestamps are monotone increasing. If the host's clock is set timestamps are monotone increasing. If the host's clock is set
backward in time, sometimes this can be easily detected. If the backward in time, sometimes this can be easily detected. If the
clock is set forward in time, this can be harder to detect. The clock is set forward in time, this can be harder to detect. The
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
skew induced by the second mechanism can lead to considerable skew induced by the second mechanism can lead to considerable
inaccuracies when computing differences in time, as discussed inaccuracies when computing differences in time, as discussed
above. above.
To illustrate why skew is a crucial concern, consider samples of To illustrate why skew is a crucial concern, consider samples of
one-way delays between two Internet hosts made at one minute inter- one-way delays between two Internet hosts made at one minute inter-
vals. The true transmission delay between the hosts might plausibly vals. The true transmission delay between the hosts might plausibly
be on the order of 50 ms for a transcontinental path. If the skew be on the order of 50 ms for a transcontinental path. If the skew
between the two clocks is 0.01%, that is, 1 part in 10,000, then between the two clocks is 0.01%, that is, 1 part in 10,000, then
skipping to change at page 17, line 5 skipping to change at page 18, line 5
Note that intrinsic to the definition is the notion of where on the Note that intrinsic to the definition is the notion of where on the
link we are observing. This distinction is important because for link we are observing. This distinction is important because for
large-latency links, we may obtain very different times depending on large-latency links, we may obtain very different times depending on
exactly where we are observing the link. We could allow the observa- exactly where we are observing the link. We could allow the observa-
tional position to be an arbitrary location along the link; however, tional position to be an arbitrary location along the link; however,
we define it to be in terms of an Internet host because we anticipate we define it to be in terms of an Internet host because we anticipate
in practice that, for IPPM metrics, all such timing will be con- in practice that, for IPPM metrics, all such timing will be con-
strained to be performed by Internet hosts, rather than specialized strained to be performed by Internet hosts, rather than specialized
hardware devices that might be able to monitor a link at locations hardware devices that might be able to monitor a link at locations
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
where a host cannot. This definition also takes care of the problem where a host cannot. This definition also takes care of the problem
of links that are comprised of multiple physical channels. Because of links that are comprised of multiple physical channels. Because
these multiple channels are not visible at the IP layer, they cannot these multiple channels are not visible at the IP layer, they cannot
be individually observed in terms of the above definitions. be individually observed in terms of the above definitions.
It is possible, though one hopes uncommon, that a packet P might make It is possible, though one hopes uncommon, that a packet P might make
multiple trips over a particular link L, due to a forwarding loop. multiple trips over a particular link L, due to a forwarding loop.
These trips might even overlap, depending on the link technology. These trips might even overlap, depending on the link technology.
Whenever this occurs, we define a separate wire time associated with Whenever this occurs, we define a separate wire time associated with
skipping to change at page 18, line 5 skipping to change at page 19, line 5
{Comment: It can sometimes be difficult to measure wire times. One {Comment: It can sometimes be difficult to measure wire times. One
technique is to use a packet filter to monitor traffic on a link. technique is to use a packet filter to monitor traffic on a link.
The architecture of these filters often attempts to associate with The architecture of these filters often attempts to associate with
each packet a timestamp as close to the wire time as possible. We each packet a timestamp as close to the wire time as possible. We
note however that one common source of error is to run the packet note however that one common source of error is to run the packet
filter on one of the endpoint hosts. In this case, it has been filter on one of the endpoint hosts. In this case, it has been
observed that some packet filters receive for some packets timestamps observed that some packet filters receive for some packets timestamps
corresponding to when the packet was *scheduled* to be injected into corresponding to when the packet was *scheduled* to be injected into
the network, rather than when it actually was *sent* out onto the the network, rather than when it actually was *sent* out onto the
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
network (wire time). There can be a substantial difference between network (wire time). There can be a substantial difference between
these two times. A technique for dealing with this problem is to run these two times. A technique for dealing with this problem is to run
the packet filter on a separate host that passively monitors the the packet filter on a separate host that passively monitors the
given link. This can be problematic however for some link technolo- given link. This can be problematic however for some link technolo-
gies. See [Pa97] for a discussion of the sorts of errors packet gies. See [Pa97] for a discussion of the sorts of errors packet
filters can exhibit. Finally, we note that packet filters will often filters can exhibit. Finally, we note that packet filters will often
only capture the first fragment of a fragmented IP packet, due to the only capture the first fragment of a fragmented IP packet, due to the
use of filtering on fields in the IP and transport protocol headers. use of filtering on fields in the IP and transport protocol headers.
As we generally desire our measurement methodologies to avoid the As we generally desire our measurement methodologies to avoid the
skipping to change at page 19, line 5 skipping to change at page 20, line 5
By applying these notions of singleton, sample, and statistic in a By applying these notions of singleton, sample, and statistic in a
consistent way, we will be able to reuse lessons learned about how to consistent way, we will be able to reuse lessons learned about how to
define samples and statistics on various metrics. The orthogonality define samples and statistics on various metrics. The orthogonality
among these three notions will thus make all our work more effective among these three notions will thus make all our work more effective
and more intelligible by the community. and more intelligible by the community.
In the remainder of this section, we will cover some topics in sam- In the remainder of this section, we will cover some topics in sam-
pling and statistics that we believe will be important to a variety pling and statistics that we believe will be important to a variety
of metric definitions and measurement efforts. of metric definitions and measurement efforts.
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
10.1. Methods of Collecting Samples 10.1. Methods of Collecting Samples
The main reason for collecting samples is to see what sort of varia- The main reason for collecting samples is to see what sort of varia-
tions and consistencies are present in the metric being measured. tions and consistencies are present in the metric being measured.
These variations might be with respect to different points in the These variations might be with respect to different points in the
Internet, or different measurement times. When assessing variations Internet, or different measurement times. When assessing variations
based on a sample, one generally makes an assumption that the sample based on a sample, one generally makes an assumption that the sample
is "unbiased", meaning that the process of collecting the measure- is "unbiased", meaning that the process of collecting the measure-
ments in the sample did not skew the sample so that it no longer ments in the sample did not skew the sample so that it no longer
skipping to change at page 20, line 5 skipping to change at page 21, line 5
reduces to periodic sampling with a period of g. reduces to periodic sampling with a period of g.
Random additive sampling gains significant advantages. In general, Random additive sampling gains significant advantages. In general,
it avoids synchronization effects and yields an unbiased estimate of it avoids synchronization effects and yields an unbiased estimate of
the property being sampled. The only significant drawbacks with it the property being sampled. The only significant drawbacks with it
are: are:
+ it complicates frequency-domain analysis, because the samples do + it complicates frequency-domain analysis, because the samples do
not occur at fixed intervals such as assumed by Fourier-transform not occur at fixed intervals such as assumed by Fourier-transform
techniques; and techniques; and
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
+ unless G(t) is the exponential distribution (see below), sampling + unless G(t) is the exponential distribution (see below), sampling
still remains somewhat predictable, as discussed for periodic sam- still remains somewhat predictable, as discussed for periodic sam-
pling above. pling above.
10.1.1. Poisson Sampling 10.1.1. Poisson Sampling
It can be proved that if G(t) is an exponential distribution with It can be proved that if G(t) is an exponential distribution with
rate lambda, that is rate lambda, that is
G(t) = 1 - exp(-lambda * t) G(t) = 1 - exp(-lambda * t)
skipping to change at page 21, line 5 skipping to change at page 22, line 5
measurements will be uniformly distributed over the interval [T, measurements will be uniformly distributed over the interval [T,
T+dT]. So another way of conducting Poisson sampling is to pick dT T+dT]. So another way of conducting Poisson sampling is to pick dT
and N and generate N random sampling times uniformly over the inter- and N and generate N random sampling times uniformly over the inter-
val [T, T+dT]. The two approaches are equivalent, except if N and dT val [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 are externally known. In that case, the property of not being able
to predict measurement times is weakened (the other properties still to predict measurement times is weakened (the other properties still
hold). The N/dT approach has an advantage that dealing with fixed 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 values of N and dT can be simpler than dealing with a fixed lambda
but variable numbers of measurements over variably-sized intervals. but variable numbers of measurements over variably-sized intervals.
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
10.1.2. Geometric Sampling 10.1.2. Geometric Sampling
Closely related to Poisson sampling is "geometric sampling", in which Closely related to Poisson sampling is "geometric sampling", in which
external events are measured with a fixed probability p. For exam- external events are measured with a fixed probability p. For exam-
ple, one might capture all the packets over a link but only record ple, one might capture all the packets over a link but only record
the packet to a trace file if a randomly generated number uniformly the packet to a trace file if a randomly generated number uniformly
distributed between 0 and 1 is less than a given p. Geometric sam- distributed between 0 and 1 is less than a given p. Geometric sam-
pling has the same properties of being unbiased and not predictable pling has the same properties of being unbiased and not predictable
in advance as Poisson sampling, so if it fits a particular Internet in advance as Poisson sampling, so if it fits a particular Internet
skipping to change at page 22, line 5 skipping to change at page 23, line 5
none). none).
Method 1 is to proceed as follows: Method 1 is to proceed as follows:
1. Generate E1 and wait that long. 1. Generate E1 and wait that long.
2. Perform a measurement. 2. Perform a measurement.
3. Generate E2 and wait that long. 3. Generate E2 and wait that long.
4. Perform a measurement. 4. Perform a measurement.
5. Generate E3 and wait that long. 5. Generate E3 and wait that long.
6. Perform a measurement ... 6. Perform a measurement ...
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
The problem with this approach is that the "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, 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 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 com- of time required for the i'th measurement. If Mi is very small com-
pared to 1/lambda then the potential error introduced by this tech- pared to 1/lambda then the potential error introduced by this tech-
nique is likewise small. As Mi becomes a non-negligible fraction of nique is likewise small. As Mi becomes a non-negligible fraction of
1/lambda, the potential error increases. 1/lambda, the potential error increases.
Method 2 attempts to correct this error by taking into account the Method 2 attempts to correct this error by taking into account the
skipping to change at page 23, line 5 skipping to change at page 24, line 5
siderably harder to implement. siderably harder to implement.
10.2. Self-Consistency 10.2. Self-Consistency
A fundamental requirement for a sound measurement methodology is that A fundamental requirement for a sound measurement methodology is that
measurement be made using as few unconfirmed assumptions as possible. measurement be made using as few unconfirmed assumptions as possible.
Experience has painfully shown how easy it is to make an (often Experience has painfully shown how easy it is to make an (often
implicit) assumption that turns out to be incorrect. An example is implicit) assumption that turns out to be incorrect. An example is
incorporating into a measurement the reading of a clock synchronized incorporating into a measurement the reading of a clock synchronized
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
to a highly accurate source. It is easy to assume that the clock is 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 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, source, or a loss of communication between the source and the clock,
the clock could actually be quite inaccurate. the clock could actually be quite inaccurate.
This is not to argue that one must not make *any* assumptions when This is not to argue that one must not make *any* assumptions when
measuring, but rather that, to the extent which is practical, assump- measuring, but rather that, to the extent which is practical, assump-
tions should be tested. One powerful way for doing so involves tions should be tested. One powerful way for doing so involves
checking for self-consistency. Such checking applies both to the checking for self-consistency. Such checking applies both to the
skipping to change at page 24, line 5 skipping to change at page 25, line 5
very near zero is positive evidence that the measurements are prob- very near zero is positive evidence that the measurements are prob-
ably not biased by a difference in skew. ably not biased by a difference in skew.
A final example illustrates checking the measurement process itself A final example illustrates checking the measurement process itself
for self-consistency. Above we outline Poisson sampling techniques, for self-consistency. Above we outline Poisson sampling techniques,
based on generating exponentially-distributed intervals. A sound based on generating exponentially-distributed intervals. A sound
measurement methodology would include testing the generated intervals measurement methodology would include testing the generated intervals
to see whether they are indeed exponentially distributed (and also to to see whether they are indeed exponentially distributed (and also to
see if they suffer from correlation). In the appendix we discuss and see if they suffer from correlation). In the appendix we discuss and
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
give C code for one such technique, a general-purpose, well-regarded give C code for one such technique, a general-purpose, well-regarded
goodness-of-fit test called the Anderson-Darling test. goodness-of-fit test called the Anderson-Darling test.
Finally, we note that what is truly relevant for Poisson sampling of Finally, we note that what is truly relevant for Poisson sampling of
Internet metrics is often not when the measurements began but the Internet metrics is often not when the measurements began but the
wire times corresponding to the measurement process. These could wire times corresponding to the measurement process. These could
well be different, due to complications on the hosts used to perform well be different, due to complications on the hosts used to perform
the measurement. Thus, even those with complete faith in their the measurement. Thus, even those with complete faith in their
pseudo-random number generators and subsequent algorithms are pseudo-random number generators and subsequent algorithms are
skipping to change at page 25, line 5 skipping to change at page 26, line 5
regarding the order in which the values were observed. Whether this regarding the order in which the values were observed. Whether this
loss is potentially significant will depend on the metric being meas- loss is potentially significant will depend on the metric being meas-
ured. ured.
We will use the term "percentile" to refer to the smallest value of x 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 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 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 per- -2, since F(-5) = 1/6 < 25%, and F(-2) = 2/6 >= 25%; the 100th per-
centile is 18; and the 0th percentile is -infinity, as is the 15th centile is 18; and the 0th percentile is -infinity, as is the 15th
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
percentile. percentile.
Care must be taken when using percentiles to summarize a sample, Care must be taken when using percentiles to summarize a sample,
because they can lend an unwarranted appearance of more precision because they can lend an unwarranted appearance of more precision
than is really available. Any such summary MUST include the sample than is really available. Any such summary must include the sample
size N, because any percentile difference finer than 1/N is below the size N, because any percentile difference finer than 1/N is below the
resolution of the sample. resolution of the sample.
See [DS86] for more details regarding EDF's. See [DS86] for more details regarding EDF's.
We close with a note on the common (and important!) notion of median. 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 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 point X for which the probability of observing a value <= X is equal
to the probability of observing a value > X. When estimating the to the probability of observing a value > X. When estimating the
median of a set of observations, the estimate depends on whether the median of a set of observations, the estimate depends on whether the
skipping to change at page 26, line 5 skipping to change at page 27, line 5
test: the scheduled packet transmission times, as determined by use test: the scheduled packet transmission times, as determined by use
of a pseudo-random number generator; user-level timestamps made just of a pseudo-random number generator; user-level timestamps made just
before or after the system call for transmitting the packet; and wire before or after the system call for transmitting the packet; and wire
times for the packets as recorded using a packet filter. All three times for the packets as recorded using a packet filter. All three
of these are potentially informative: failures for the scheduled of these are potentially informative: failures for the scheduled
times to match an exponential distribution indicate inaccuracies in times to match an exponential distribution indicate inaccuracies in
the random number generation; failures for the user-level times indi- the random number generation; failures for the user-level times indi-
cate inaccuracies in the timers used to schedule transmission; and cate inaccuracies in the timers used to schedule transmission; and
failures for the wire times indicate inaccuracies in actually failures for the wire times indicate inaccuracies in actually
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
transmitting the packets, perhaps due to contention for a shared transmitting the packets, perhaps due to contention for a shared
resource.} resource.}
There are a large number of statistical goodness-of-fit techniques There are a large number of statistical goodness-of-fit techniques
for performing such tests. See [DS86] for a thorough discussion. for performing such tests. See [DS86] for a thorough discussion.
That reference recommends the Anderson-Darling EDF test as being a That reference recommends the Anderson-Darling EDF test as being a
good all-purpose test, as well as one that is especially good at good all-purpose test, as well as one that is especially good at
detecting deviations from a given distribution in the lower and upper detecting deviations from a given distribution in the lower and upper
tails of the EDF. tails of the EDF.
skipping to change at page 27, line 5 skipping to change at page 28, line 5
11. Avoiding Stochastic Metrics 11. Avoiding Stochastic Metrics
When defining metrics applying to a path, subpath, cloud, or other When defining metrics applying to a path, subpath, cloud, or other
network element, we in general do not define them in stochastic terms network element, we in general do not define them in stochastic terms
(probabilities). We instead prefer a deterministic definition. So, (probabilities). We instead prefer a deterministic definition. So,
for example, rather than defining a metric about a "packet loss pro- for example, rather than defining a metric about a "packet loss pro-
bability between A and B", we would define a metric about a "packet bability between A and B", we would define a metric about a "packet
loss rate between A and B". (A measurement given by the first defin- loss rate between A and B". (A measurement given by the first defin-
ition might be "0.73", and by the second "73 packets out of 100".) ition might be "0.73", and by the second "73 packets out of 100".)
ID Framework for IP Performance Metrics November 1997 ID Framework for IP Performance Metrics February 1998
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 The reason for this distinction is as follows. When definitions are
made in terms of probabilities, there are often hidden assumptions in made in terms of probabilities, there are often hidden assumptions in
the definition about a stochastic model of the behavior being meas- the definition about a stochastic model of the behavior being meas-
ured. The fundamental goal with avoiding probabilities in our metric ured. The fundamental goal with avoiding probabilities in our metric
definitions is to avoid biasing our definitions by these hidden definitions is to avoid biasing our definitions by these hidden
assumptions. assumptions.
For example, an easy hidden assumption to make is that packet loss in For example, an easy hidden assumption to make is that packet loss in
a network component due to queueing overflows can be described as a network component due to queueing overflows can be described as
something that happens to any given packet with a particular proba- something that happens to any given packet with a particular proba-
bility. Usually, however, queueing drops are actually *determinis- bility. In today's Internet, however, queueing drops are actually
tic*, and assuming that they should be described probabilistically usually *deterministic*, and assuming that they should be described
can obscure crucial correlations between queueing drops among a set probabilistically can obscure crucial correlations between queueing
of packets. So it's better to explicitly note stochastic assump- drops among a set of packets. So it's better to explicitly note sto-
tions, rather than have them sneak into our definitions implicitly. chastic assumptions, rather than have them sneak into our definitions
implicitly.
This does *not* mean that we abandon stochastic models for under- This does *not* mean that we abandon stochastic models for *under-
standing network performance! It only means that when defining IP standing* network performance! It only means that when defining IP
metrics we avoid terms such as "probability" for terms like "propor- metrics we avoid terms such as "probability" for terms like "propor-
tion" or "rate". We will still use, for example, random sampling in tion" or "rate". We will still use, for example, random sampling in
order to estimate probabilities used by stochastic models related to order to estimate probabilities used by stochastic models related to
the IP metrics. We also do not rule out the possibility of stochas- the IP metrics. We also do not rule out the possibility of stochas-
tic metrics when they are truly appropriate (for example, perhaps to tic metrics when they are truly appropriate (for example, perhaps to
model transmission errors caused by certain types of line noise). model transmission errors caused by certain types of line noise).
12. Packets of Type P 12. Packets of Type P
A fundamental property of many Internet metrics is that the value of A fundamental property of many Internet metrics is that the value of
skipping to change at page 27, line 49 skipping to change at page 29, line 4
those with invalid IP checksums, or those with TTL's of 16, for exam- those with invalid IP checksums, or those with TTL's of 16, for exam-
ple. In some circumstances these distinctions will be highly ple. In some circumstances these distinctions will be highly
interesting (for example, in the presence of firewalls, or RSVP interesting (for example, in the presence of firewalls, or RSVP
reservations). reservations).
Because of this distinction, we introduce the generic notion of a Because of this distinction, we introduce the generic notion of a
"packet of type P", where in some contexts P will be explicitly "packet of type P", where in some contexts P will be explicitly
defined (i.e., exactly what type of packet we mean), partially defined (i.e., exactly what type of packet we mean), partially
defined (e.g., "with a payload of B octets"), or left generic. Thus 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 we may talk about generic IP-type-P-connectivity or more specific
ID Framework for IP Performance Metrics February 1998
IP-port-HTTP-connectivity. Some metrics and methodologies may be IP-port-HTTP-connectivity. Some metrics and methodologies may be
fruitfully defined using generic type P definitions which are then fruitfully defined using generic type P definitions which are then
made specific when performing actual measurements. made specific when performing actual measurements.
Whenever a metric's value depends on the type of the packets involved Whenever a metric's value depends on the type of the packets involved
ID Framework for IP Performance Metrics November 1997
in the metric, the metric's name will include either a specific type 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- or a phrase such as "type-P". Thus we will not define an "IP-
connectivity" metric but instead an "IP-type-P-connectivity" metric connectivity" metric but instead an "IP-type-P-connectivity" metric
and/or perhaps an "IP-port-HTTP-connectivity" metric. This naming and/or perhaps an "IP-port-HTTP-connectivity" metric. This naming
convention serves as an important reminder that one must be conscious convention serves as an important reminder that one must be conscious
of the exact type of traffic being measured. of the exact type of traffic being measured.
A closely related note: it would be very useful to know if a given 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 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 packets. If so, then any one of those types of packets can be used
skipping to change at page 28, line 43 skipping to change at page 30, line 4
"Dst" to denote the IP address of the end. "Dst" to denote the IP address of the end.
14. Standard-Formed Packets 14. Standard-Formed Packets
Unless otherwise stated, all metric definitions that concern IP pack- Unless otherwise stated, all metric definitions that concern IP pack-
ets include an implicit assumption that the packet is *standard ets include an implicit assumption that the packet is *standard
formed*. A packet is standard formed if it meets all of the follow- formed*. A packet is standard formed if it meets all of the follow-
ing criteria: ing criteria:
+ Its length as given in the IP header corresponds to the size of + Its length as given in the IP header corresponds to the size of
the IP header plus the size of the payload. the IP header plus the size of the payload.
ID Framework for IP Performance Metrics February 1998
+ It includes a valid IP header: the version field is 4 (later, we + 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 will expand this to include 6); the header length is >= 5; the
checksum is correct. checksum is correct.
+ It is not an IP fragment. + It is not an IP fragment.
+ The source and destination addresses correspond to the hosts in + The source and destination addresses correspond to the hosts in
question. question.
ID Framework for IP Performance Metrics November 1997
+ Either the packet possesses sufficient TTL to travel from the + Either the packet possesses sufficient TTL to travel from the
source to the destination if the TTL is decremented by one at each source to the destination if the TTL is decremented by one at each
hop, or it possesses the maximum TTL of 255. hop, or it possesses the maximum TTL of 255.
+ It does not contain IP options unless explicitly noted. + It does not contain IP options unless explicitly noted.
+ If a transport header is present, it too contains a valid checksum + If a transport header is present, it too contains a valid checksum
and other valid fields. and other valid fields.
We further require that if a packet is described as having a "length 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 of B octets", then 0 <= B <= 65535; and if B is the payload length in
octets, then B <= (65535-IP header size in octets). octets, then B <= (65535-IP header size in octets).
skipping to change at page 29, line 41 skipping to change at page 31, line 5
When defining IP metrics we keep in mind that no packet smaller or When defining IP metrics we keep in mind that no packet smaller or
simpler than this can be transmitted over a correctly operating IP simpler than this can be transmitted over a correctly operating IP
network. network.
15. Acknowledgements 15. Acknowledgements
The comments of Brian Carpenter, Bill Cerveny, Padma Krishnaswamy The comments of Brian Carpenter, Bill Cerveny, Padma Krishnaswamy
Jeff Sedayao and Howard Stanislevic are appreciated. Jeff Sedayao and Howard Stanislevic are appreciated.
ID Framework for IP Performance Metrics February 1998
16. Security Considerations 16. Security Considerations
This memo raises no security issues. 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 measure-
ment. As such, the topics discussed do not affect the security of
the Internet or of applications which run on it.
ID Framework for IP Performance Metrics November 1997 That said, it should be recognized that conducting Internet measure-
ments can raise both security and privacy concerns. Active tech-
niques, 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 unin-
tended recipients. Consequently, the definition of each metric and
methodology must include a corresponding discussion of security con-
siderations.
17. Appendix 17. Appendix
Below we give routines written in C for computing the Anderson- Below we give routines written in C for computing the Anderson-
Darling test statistic (A2) for determining whether a set of values Darling test statistic (A2) for determining whether a set of values
is consistent with a given statistical distribution. Externally, the is consistent with a given statistical distribution. Externally, the
two main routines of interest are: two main routines of interest are:
double exp_A2_known_mean(double x[], int n, double mean) double exp_A2_known_mean(double x[], int n, double mean)
double unif_A2_known_range(double x[], int n, double unif_A2_known_range(double x[], int n,
double min_val, double max_val) double min_val, double max_val)
skipping to change at page 30, line 36 skipping to change at page 32, line 4
our purposes we expect that we should indeed know the parameters in our purposes we expect that we should indeed know the parameters in
advance, since what we will be testing are generally values such as advance, since what we will be testing are generally values such as
packet sending times that we wish to verify follow a known distribu- packet sending times that we wish to verify follow a known distribu-
tion. tion.
Both routines return a significance level, as described earlier. This 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 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; pick in advance the threshold for the significance level to test;
generally, this will be 0.05, corresponding to 5%, as also described generally, this will be 0.05, corresponding to 5%, as also described
above. Subsequently, if the routines return a value strictly less above. Subsequently, if the routines return a value strictly less
ID Framework for IP Performance Metrics February 1998
than this threshold, then the data are deemed to be inconsistent with than this threshold, then the data are deemed to be inconsistent with
the presumed distribution, *subject to an error corresponding to the the presumed distribution, *subject to an error corresponding to the
significance level*. That is, for a significance level of 5%, 5% of significance level*. That is, for a significance level of 5%, 5% of
the time data that is indeed drawn from the presumed distribution the time data that is indeed drawn from the presumed distribution
will be erroneously deemed inconsistent. will be erroneously deemed inconsistent.
Thus, it is important to bear in mind that if these routines are used Thus, it is important to bear in mind that if these routines are used
frequently, then one will indeed encounter occasional failures, even frequently, then one will indeed encounter occasional failures, even
if the data is unblemished. if the data is unblemished.
Another important point concerning significance levels is that it is Another important point concerning significance levels is that it is
unsound to compare them in order to determine which of two sets of unsound to compare them in order to determine which of two sets of
values is a "better" fit to a presumed distribution. Such testing values is a "better" fit to a presumed distribution. Such testing
should instead be done using "closeness-of-fit metrics" such as the should instead be done using "closeness-of-fit metrics" such as the
lambda^2 metric described in [Pa94]. lambda^2 metric described in [Pa94].
While the routines provided are for exponential and uniform distribu- While the routines provided are for exponential and uniform distribu-
tions with known parameters, it is generally straight-forward to tions with known parameters, it is generally straight-forward to
write comparable routines for any distribution with known parameters. write comparable routines for any distribution with known parameters.
ID Framework for IP Performance Metrics November 1997
The heart of the A2 tests lies in a statistic computed for testing The heart of the A2 tests lies in a statistic computed for testing
whether a set of values is consistent with a uniform distribution 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 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 whether a set of values, X, is consistent with a given distribution
G(x), we first compute G(x), we first compute
Y = G_inverse(X) Y = G_inverse(X)
If X is indeed distributed according to G(x), then Y will be distri- If X is indeed distributed according to G(x), then Y will be distri-
buted according to Unif(0, 1); so by testing Y for consistency with buted according to Unif(0, 1); so by testing Y for consistency with
Unif(0, 1), we also test X for consistency with G(x). Unif(0, 1), we also test X for consistency with G(x).
skipping to change at page 31, line 36 skipping to change at page 33, line 4
of -1. So, any use of these routines must be prepared for a possible of -1. So, any use of these routines must be prepared for a possible
negative significance level. negative significance level.
The last important point regarding use of A2 statistic concerns n, 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 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. 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 On the other hand, for "real" data the test *gains* power as n
becomes larger. It is well known in the statistics community that becomes larger. It is well known in the statistics community that
real data almost never exactly matches a theoretical distribution, real data almost never exactly matches a theoretical distribution,
ID Framework for IP Performance Metrics February 1998
even in cases such as rolling dice a great many times (see [Pa94] for 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 a brief discussion and references). The A2 test is sensitive enough
that, for sufficiently large sets of real data, the test will almost that, for sufficiently large sets of real data, the test will almost
always fail, because it will manage to detect slight imperfections in always fail, because it will manage to detect slight imperfections in
the fit of the data to the distribution. the fit of the data to the distribution.
For example, we have found that when testing 8,192 measured wire For example, we have found that when testing 8,192 measured wire
times for packets sent at Poisson intervals, the measurements almost times for packets sent at Poisson intervals, the measurements almost
always fail the A2 test. On the other hand, testing 128 measurements always fail the A2 test. On the other hand, testing 128 measurements
failed at 5% significance only about 5% of the time, as expected. failed at 5% significance only about 5% of the time, as expected.
Thus, in general, when the test fails, care must be taken to under- Thus, in general, when the test fails, care must be taken to under-
stand why it failed. stand why it failed.
The remainder of this appendix gives C code for the routines men- The remainder of this appendix gives C code for the routines men-
tioned above. tioned above.
/* Routines for computing the Anderson-Darling A2 test statistic. /* Routines for computing the Anderson-Darling A2 test statistic.
* *
* Implememented based on the description in "Goodness-of-Fit * Implememented based on the description in "Goodness-of-Fit
ID Framework for IP Performance Metrics November 1997
* Techniques," R. D'Agostino and M. Stephens, editors, * Techniques," R. D'Agostino and M. Stephens, editors,
* Marcel Dekker, Inc., 1986. * Marcel Dekker, Inc., 1986.
*/ */
#include <stdio.h> #include <stdio.h>
#include <stdlib.h> #include <stdlib.h>
#include <math.h> #include <math.h>
/* Returns the raw A^2 test statistic for n sorted samples /* Returns the raw A^2 test statistic for n sorted samples
* z[0] .. z[n-1], for z ~ Unif(0,1). * z[0] .. z[n-1], for z ~ Unif(0,1).
skipping to change at page 32, line 36 skipping to change at page 34, line 4
/* Returns the A^2 significance level for testing n observations /* Returns the A^2 significance level for testing n observations
* x[0] .. x[n-1] against an exponential distribution with the * x[0] .. x[n-1] against an exponential distribution with the
* given mean. * given mean.
* *
* SIDE EFFECT: the x[0..n-1] are sorted upon return. * SIDE EFFECT: the x[0..n-1] are sorted upon return.
*/ */
extern double exp_A2_known_mean(double x[], int n, double mean); extern double exp_A2_known_mean(double x[], int n, double mean);
/* Returns the A^2 significance level for testing n observations /* Returns the A^2 significance level for testing n observations
* x[0] .. x[n-1] against the uniform distribution [min_val, max_val]. * x[0] .. x[n-1] against the uniform distribution [min_val, max_val].
ID Framework for IP Performance Metrics February 1998
* *
* SIDE EFFECT: the x[0..n-1] are sorted upon return. * SIDE EFFECT: the x[0..n-1] are sorted upon return.
*/ */
extern double unif_A2_known_range(double x[], int n, extern double unif_A2_known_range(double x[], int n,
double min_val, double max_val); double min_val, double max_val);
/* Returns a pseudo-random number distributed according to an /* Returns a pseudo-random number distributed according to an
* exponential distribution with the given mean. * exponential distribution with the given mean.
*/ */
extern double random_exponential(double mean); extern double random_exponential(double mean);
/* Helper function used by qsort() to sort double-precision /* Helper function used by qsort() to sort double-precision
* floating-point values. * floating-point values.
*/ */
static int static int
compare_double(const void *v1, const void *v2) compare_double(const void *v1, const void *v2)
{ {
double d1 = *(double *) v1; double d1 = *(double *) v1;
ID Framework for IP Performance Metrics November 1997
double d2 = *(double *) v2; double d2 = *(double *) v2;
if (d1 < d2) if (d1 < d2)
return -1; return -1;
else if (d1 > d2) else if (d1 > d2)
return 1; return 1;
else else
return 0; return 0;
} }
skipping to change at page 33, line 36 skipping to change at page 35, line 4
/* If any of the values are outside the range (0, 1) then /* If any of the values are outside the range (0, 1) then
* fail immediately (and avoid a possible floating point * fail immediately (and avoid a possible floating point
* exception in the code below). * exception in the code below).
*/ */
for (i = 0; i < n; ++i) for (i = 0; i < n; ++i)
if ( z[i] <= 0.0 || z[i] >= 1.0 ) if ( z[i] <= 0.0 || z[i] >= 1.0 )
return -1.0; return -1.0;
/* Page 101 of D'Agostino and Stephens. */ /* Page 101 of D'Agostino and Stephens. */
ID Framework for IP Performance Metrics February 1998
for (i = 1; i <= n; ++i) { for (i = 1; i <= n; ++i) {
sum += (2 * i - 1) * log(z[i-1]); sum += (2 * i - 1) * log(z[i-1]);
sum += (2 * n + 1 - 2 * i) * log(1.0 - z[i-1]); sum += (2 * n + 1 - 2 * i) * log(1.0 - z[i-1]);
} }
return -n - (1.0 / n) * sum; return -n - (1.0 / n) * sum;
} }
double double
A2_significance(double A2) A2_significance(double A2)
{ {
/* Page 105 of D'Agostino and Stephens. */ /* Page 105 of D'Agostino and Stephens. */
if (A2 < 0.0) if (A2 < 0.0)
return A2; /* Bogus A2 value - propagate it. */ return A2; /* Bogus A2 value - propagate it. */
/* Check for possibly doctored values. */ /* Check for possibly doctored values. */
if (A2 <= 0.201) if (A2 <= 0.201)
return 0.99; return 0.99;
else if (A2 <= 0.240) else if (A2 <= 0.240)
return 0.975; return 0.975;
ID Framework for IP Performance Metrics November 1997
else if (A2 <= 0.283) else if (A2 <= 0.283)
return 0.95; return 0.95;
else if (A2 <= 0.346) else if (A2 <= 0.346)
return 0.90; return 0.90;
else if (A2 <= 0.399) else if (A2 <= 0.399)
return 0.85; return 0.85;
/* Now check for possible inconsistency. */ /* Now check for possible inconsistency. */
if (A2 <= 1.248) if (A2 <= 1.248)
return 0.25; return 0.25;
skipping to change at page 34, line 36 skipping to change at page 36, line 4
return 0.01; return 0.01;
else if (A2 <= 4.500) else if (A2 <= 4.500)
return 0.005; return 0.005;
else if (A2 <= 6.000) else if (A2 <= 6.000)
return 0.001; return 0.001;
else else
return 0.0; return 0.0;
} }
double double
ID Framework for IP Performance Metrics February 1998
exp_A2_known_mean(double x[], int n, double mean) exp_A2_known_mean(double x[], int n, double mean)
{ {
int i; int i;
double A2; double A2;
/* Sort the first n values. */ /* Sort the first n values. */
qsort(x, n, sizeof(x[0]), compare_double); qsort(x, n, sizeof(x[0]), compare_double);
/* Assuming they match an exponential distribution, transform /* Assuming they match an exponential distribution, transform
* them to Unif(0,1). * them to Unif(0,1).
*/ */
for (i = 0; i < n; ++i) { for (i = 0; i < n; ++i) {
x[i] = 1.0 - exp(-x[i] / mean); x[i] = 1.0 - exp(-x[i] / mean);
} }
/* Now make the A^2 test to see if they're truly uniform. */ /* Now make the A^2 test to see if they're truly uniform. */
A2 = compute_A2(x, n); A2 = compute_A2(x, n);
return A2_significance(A2); return A2_significance(A2);
} }
ID Framework for IP Performance Metrics November 1997
double double
unif_A2_known_range(double x[], int n, double min_val, double max_val) unif_A2_known_range(double x[], int n, double min_val, double max_val)
{ {
int i; int i;
double A2; double A2;
double range = max_val - min_val; double range = max_val - min_val;
/* Sort the first n values. */ /* Sort the first n values. */
qsort(x, n, sizeof(x[0]), compare_double); qsort(x, n, sizeof(x[0]), compare_double);
skipping to change at page 35, line 32 skipping to change at page 37, line 5
A2 = compute_A2(x, n); A2 = compute_A2(x, n);
return A2_significance(A2); return A2_significance(A2);
} }
double double
random_exponential(double mean) random_exponential(double mean)
{ {
return -mean * log1p(-drand48()); return -mean * log1p(-drand48());
} }
ID Framework for IP Performance Metrics February 1998
18. References 18. References
[AK96] G. Almes and S. Kalidindi, "A One-way Delay Metric for IPPM", [AK96] G. Almes and S. Kalidindi, "A One-way Delay Metric for IPPM",
Internet Draft <draft-ietf-ippm-delay-02.txt>, November 1997. work in progress, November 1997.
[BM92] I. Bilinskis and A. Mikelsons, Randomized Signal Processing, [BM92] I. Bilinskis and A. Mikelsons, Randomized Signal Processing,
Prentice Hall International, 1992. Prentice Hall International, 1992.
[DS86] R. D'Agostino and M. Stephens, editors, Goodness-of-Fit Tech- [DS86] R. D'Agostino and M. Stephens, editors, Goodness-of-Fit Tech-
niques, Marcel Dekker, Inc., 1986. niques, Marcel Dekker, Inc., 1986.
[CPB93] K. Claffy, G. Polyzos, and H-W. Braun, ``Application of Sam- [CPB93] K. Claffy, G. Polyzos, and H-W. Braun, ``Application of Sam-
pling Methodologies to Network Traffic Characterization,'' Proc. pling Methodologies to Network Traffic Characterization,'' Proc.
SIGCOMM '93, pp. 194-203, San Francisco, September 1993. SIGCOMM '93, pp. 194-203, San Francisco, September 1993.
[FJ94] S. Floyd and V. Jacobson, ``The Synchronization of Periodic [FJ94] S. Floyd and V. Jacobson, ``The Synchronization of Periodic
Routing Messages,'' IEEE/ACM Transactions on Networking, 2(2), pp. Routing Messages,'' IEEE/ACM Transactions on Networking, 2(2), pp.
122-136, April 1994. 122-136, April 1994.
[Mi92] D. Mills, "Network Time Protocol (Version 3) Specification, [Mi92] D. Mills, "Network Time Protocol (Version 3) Specification,
Implementation and Analysis", RFC 1305, March 1992. Implementation and Analysis", RFC 1305, March 1992.
ID Framework for IP Performance Metrics November 1997
[Pa94] V. Paxson, ``Empirically-Derived Analytic Models of Wide-Area [Pa94] V. Paxson, ``Empirically-Derived Analytic Models of Wide-Area
TCP Connections,'' IEEE/ACM Transactions on Networking, 2(4), pp. TCP Connections,'' IEEE/ACM Transactions on Networking, 2(4), pp.
316-336, August 1994. 316-336, August 1994.
[Pa96] V. Paxson, ``Towards a Framework for Defining Internet Perfor- [Pa96] V. Paxson, ``Towards a Framework for Defining Internet Perfor-
mance Metrics,'' Proceedings of INET '96, mance Metrics,'' Proceedings of INET '96,
ftp://ftp.ee.lbl.gov/papers/metrics-framework-INET96.ps.Z ftp://ftp.ee.lbl.gov/papers/metrics-framework-INET96.ps.Z
[Pa97] V. Paxson, ``Measurements and Analysis of End-to-End Internet [Pa97] V. Paxson, ``Measurements and Analysis of End-to-End Internet
Dynamics,'' Ph.D. dissertation, U.C. Berkeley, 1997, Dynamics,'' Ph.D. dissertation, U.C. Berkeley, 1997,
skipping to change at page 36, line 32 skipping to change at page 38, line 4
MS 50B/2239 MS 50B/2239
Lawrence Berkeley National Laboratory Lawrence Berkeley National Laboratory
University of California University of California
Berkeley, CA 94720 Berkeley, CA 94720
USA USA
Phone: +1 510/486-7504 Phone: +1 510/486-7504
Guy Almes <almes@advanced.org> Guy Almes <almes@advanced.org>
Advanced Network & Services, Inc. Advanced Network & Services, Inc.
200 Business Park Drive 200 Business Park Drive
ID Framework for IP Performance Metrics February 1998
Armonk, NY 10504 Armonk, NY 10504
USA USA
Phone: +1 914/273-7863 Phone: +1 914/273-7863
Jamshid Mahdavi <mahdavi@psc.edu> Jamshid Mahdavi <mahdavi@psc.edu>
Pittsburgh Supercomputing Center Pittsburgh Supercomputing Center
4400 5th Avenue 4400 5th Avenue
Pittsburgh, PA 15213 Pittsburgh, PA 15213
USA USA
Phone: +1 412/268-6282 Phone: +1 412/268-6282
 End of changes. 55 change blocks. 
70 lines changed or deleted 131 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/