RFC 2330
Framework for IP Performance Metrics
Framework for IP Performance Metrics 🎀
Okay bestie, this is RFC 2330, and it's giving Framework for IP Performance Metrics ✨ It came from the Network Working Group in May 1998 🌸 The authors are V. Paxson (Lawrence Berkeley National Lab), G. Almes (Advanced Network & Services), J. Mahdavi, and M. Mathis (Pittsburgh Supercomputer Center) 👑 It's categorised as Informational, and its title block doesn't list anything it obsoletes or updates, so no drama there 💅
1. Status of this Memo ✨
This memo is pure info-sharing 💖 It gives information to the Internet community, and it does not specify an Internet standard of any kind. Distribution is unlimited, no cap 🦋
2. Copyright Notice 🌈
Copyright (C) The Internet Society (1998). All Rights Reserved. 💜
Table of Contents 🧚
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
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.......................................403. Introduction 💖
Okay so the whole point of this memo is to set up a general framework for specific metrics that the IETF's IP Performance Metrics effort will develop 🔥 That effort began in the Benchmarking Methodology Working Group (BMWG) of the Operational Requirements Area, and it's now being continued by the IP Performance Metrics Working Group (IPPM) of the Transport Area 🌸
We start by laying out some criteria for the metrics we adopt ✨ The goal is an IPPM effort that helps Internet users and Internet providers share an accurate common understanding of how well both end-to-end paths through the Internet and specific 'IP clouds' that make up parts of those paths perform and how reliable they are 💅
Next we define some Internet vocabulary so we can talk clearly about things like routers, paths, and clouds 🦋 After that we define the core ideas of 'metric' and 'measurement methodology', which help us talk about measuring things properly 🧚 With those in hand, we tackle measurement uncertainties and errors, and we build a key, kinda subtle idea of how they connect to the analytical framework that so much of Internet engineering relies on 🤯 Then we introduce empirically defined metrics and wrap up this part with how metrics can be 'composed' 🎀
The rest of the document is packed 💜 It covers how to deal with imperfect clocks, the idea of 'wire time' as separate from 'host time', and how to group singleton metrics into samples and get solid statistics from those samples ✨ It also explains why we're encouraged to avoid thinking about Internet properties in probabilistic terms (like the probability that a packet gets dropped), since those terms often hide assumptions about how the network behaves 🙈 Plus it covers the usefulness of defining metrics in terms of packets of a generic type, why IP addresses beat DNS host names, and the idea of 'standard-formed' packets 🫶
There's also an appendix about the Anderson-Darling test, which checks whether a set of values matches a given statistical distribution, and it includes C code for implementing the test 💻
Heads up: in some sections, commentary text gets wrapped in brackets like {Comment: ... } 💅 This commentary is only commentary. It isn't part of the framework document, and it isn't a proposal of particular metrics. Sometimes it talks about properties that metrics might have, but any such discussion is only there to shed light on points in the framework, not to suggest specific metrics 🌈
4. Criteria for IP Performance Metrics 👑
The big overarching goal of the IP Performance Metrics effort is getting users and providers of Internet transport service to have an accurate common understanding of how well the Internet component 'clouds' they use or provide perform and how reliable they are 💖
To get there, we need performance and reliability metrics for paths through the Internet. Several IETF meetings have already specified criteria for these metrics 🔥 The criteria are:
- The metrics must be concrete and well-defined 🎀
- A methodology for a metric should have the property that it is repeatable: if the methodology is used multiple times under identical conditions, the same measurements should result in the same measurements. 🔁
- The metrics must exhibit no bias for IP clouds implemented with identical technology 🦋
- The metrics must exhibit understood and fair bias for IP clouds implemented with non-identical technology ⚖️
- The metrics must be useful to users and providers in understanding the performance they experience or provide 💅
- The metrics must avoid inducing artificial performance goals ✨
5. Terminology for Paths and Clouds 🧚
These definitions need to be precise, because we're going to build path metrics on top of them 🤓 We start with the low-level stuff ('host', 'router', and 'link'), then move up to 'path', 'IP cloud', and 'exchange', which let us chop a path into relevant pieces 🍓
host 💜 A computer capable of communicating using the Internet protocols. It includes "routers".
link 🔗 A single link-level connection between two (or more) hosts. This includes leased lines, ethernets, frame relay clouds, etc.
router 🌸 A host that facilitates network-level communication between 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, and each h1...hn-1 is a router. A pair <li, hi> is termed a 'hop'. In an appropriate operational configuration, the links and routers in the path facilitate network-layer communication of packets from h0 to hn. Note that path is a unidirectional concept ➡️
subpath 🦋 Given a path, a subpath is any subsequence of that path which is itself a path. (So the first and last element of a subpath is a host.)
cloud ☁️ An undirected (possibly cyclic) graph whose vertices are routers and whose edges are links that connect pairs of routers. Formally, ethernets, frame relay clouds, and other links that connect more than two routers are modelled as fully-connected meshes of graph edges. Note that to connect to a cloud means to connect to a router of the cloud over a link. That link is not itself part of the cloud 🙃
exchange 🔁 A special case of a link. An exchange directly connects either a host to a cloud, and/or one cloud to another cloud.
cloud subpath ☁️ A subpath of a given path, all of whose hosts are routers of a given cloud.
path digest 💎 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 each C1 ... Cn-1 is a cloud subpath.
6. Fundamental Concepts 🌟
6.1. Metrics
Okay so, the operational Internet has a bunch of quantities about how well it performs and how reliable it is, and we literally want to know their values 🤩. When one of these quantities is carefully specified, we call it a metric 💅. We expect there to be separate RFCs for each metric (or for each closely related group of metrics) 📚.
Sometimes there's no obvious way to measure a metric effectively. That's allowed! It's even understood to be super useful in some cases ✨. The spec still has to be as clear as possible about what quantity is being specified 🫶. So difficulty in practical measurement is sometimes okay, but ambiguity in meaning is not 🙅♀️.
Each metric gets defined in terms of standard units of measurement. We use the international metric system, with these points specifically noted:
- When a unit is expressed in simple meters (for distance/length) or seconds (for duration), appropriate related units based on thousands or thousandths of acceptable units are acceptable. So distances in kilometers (km), durations in milliseconds (ms), or microseconds (us) are allowed, but not centimeters (because that prefix isn't in terms of thousands or thousandths) 📏
- When a unit is expressed in a combination of units, appropriate related units based on thousands or thousandths of acceptable units are acceptable, but all of those thousands/thousandths must be grouped at the beginning. So kilo-meters per second (km/s) is allowed, but meters per millisecond is not 🏃♀️
- The unit of information is the bit 🧠
- When metric prefixes are used with bits, or with combinations that include bits, those prefixes keep their metric meaning (related to decimal 1000), and not the meaning conventional with computer storage (related to decimal 1024). In any RFC that defines a metric whose units include bits, this convention gets followed and repeated so the reader stays clear 💜
- When a time is given, it's expressed in UTC 🕰️
Note that these points apply to the specifications for metrics, not to things like packet formats, where octets will likely be used in preference to (or alongside) bits 🦋.
Finally, some metrics can be defined purely in terms of other metrics. Those are called 'derived metrics' 🧚.
6.2. Measurement Methodology
For a given set of well-defined metrics, there could be a bunch of different measurement methodologies. A partial list includes:
- Direct measurement of a performance metric using injected test traffic. Example: measuring the round-trip delay of an IP packet of a given size over a given route at a given time 📡.
- Projection of a metric from lower-level measurements. Example: if you have accurate measurements of propagation delay and bandwidth for each step along a path, you can project the complete delay for the path for an IP packet of a given size 🧮.
- Estimation of a constituent metric from a set of more aggregated measurements. Example: if you have accurate measurements of delay for a given one-hop path for IP packets of different sizes, you can estimate the propagation delay for the link of that one-hop path 🔍.
- Estimation of a given metric at one time from a set of related metrics at other times. Example: say you have an accurate measurement of flow capacity at a past time, plus a set of accurate delay measurements for that past time and the current time, and a model of flow dynamics. Then you can estimate the flow capacity that would be observed at the current time 🌊.
This list is by no means exhaustive 💅. The point is just to show how many measurement techniques are out there ✨.
When a given metric is specified, a given measurement approach might be noted and discussed. That approach, however, is not formally part of the specification 🙈.
A methodology for a metric should be repeatable: if you use the methodology multiple times under identical conditions, it should give you consistent measurements 🔁.
Okay, backing off a little from the word 'identical' in that last bit, we could more accurately use the word continuity to describe a property of a methodology. A methodology for a given metric exhibits continuity if, for small variations in conditions, it results in small variations in the resulting measurements. Slightly more precisely: for every positive epsilon, there exists a positive delta, such that if two sets of conditions are within delta of each other, the resulting measurements will be within epsilon of each other. At this point, this should be taken as a heuristic driving our intuition about one kind of robustness property, rather than as a precise notion 🧠✨.
A metric that has at least one methodology that exhibits continuity is said to exhibit continuity itself 🦋.
Note that some metrics, like hop-count along a path, are integer-valued, so they can't exhibit continuity in quite the sense given above 🔢.
Also, in practice it may not be practical to know (or quantify) the conditions relevant to a measurement at a given time 😭. For example, the instantaneous load (in packets to be served) at a given router in a high-speed wide-area network can vary widely over relatively brief periods and is very hard for an external observer to quantify. So various statistics of a given metric may be more repeatable, or may better exhibit continuity. In that case, those particular statistics should be specified when the metric is specified 📊.
Finally, some measurement methodologies may be 'conservative', meaning the act of measurement doesn't modify the value of the performance metric the methodology is trying to measure, or only slightly modifies it 🌸.
Comment: for example, in a wide-are high-speed network under modest load, a test using several small 'ping' packets to measure delay would likely not interfere (much) with the delay properties of that network as observed by others. The corresponding statement about tests using a large flow to measure flow capacity would likely fail. 🙈
6.3. Measurements, Uncertainties, and Errors
Even the very best measurement methodologies for the very most well-behaved metrics will show errors 😤. Those who develop these methodologies, though, should strive to:
- minimize their uncertainties/errors,
- understand and document the sources of uncertainty/error, and
- quantify the amounts of uncertainty/error 📝.
For example, when developing a method for measuring delay, understand how any errors in your clocks introduce errors into your delay measurement, and quantify that effect as well as you can ⏱️. In some cases, this will result in a requirement that a clock be at least up to a certain quality if it's going to be used for a certain measurement 🕰️.
As a second example, consider the timing error due to measurement overheads inside the computer doing the measuring, as opposed to delays due to the Internet component being measured. The former is a measurement error, while the latter reflects the metric of interest 🫠. One technique that can help avoid this overhead is using a packet filter/sniffer running on a separate computer, one that records network packets and timestamps them accurately (see the discussion of 'wire time' below). The resulting trace can then be analyzed to assess the test traffic, which minimizes the effect of measurement host delays, or at least lets you account for them 🔎. This technique may still be beneficial even if the packet filter/sniffer runs on the same machine, because those measurements generally provide 'kernel-level' timestamping, as opposed to less-accurate 'application-level' timestamping 💖.
Finally, derived metrics (defined above) and metrics that exhibit spatial or temporal composition (defined below) are a particular occasion for analyzing measurement uncertainties 🧁. We need to figure out how the uncertainties propagate (conceptually) through the derivation or composition 🌈.
7. Metrics and the Analytical Framework ✨
As the Internet has evolved from the early packet-switching studies of the 1960s, the Internet engineering community has built up a common analytical framework of concepts 🦋. This framework, the A-frame, gets used by protocol designers and implementers, by people doing measurement, and by people who study computer network performance with simulation and analysis tools, and it's a huge advantage to our work 💅. A major goal here is to generate network characterizations that are consistent in both analytical and practical settings 🎀. That matters because it maximizes the chances that non-empirical network study can be better correlated with, and used to further our understanding of, real network behavior 🔥.
So whenever possible, we want to develop and build on the A-frame 🧚. Whenever a metric we're specifying is understood to be closely related to concepts within the A-frame, we'll try to specify it in the A-frame's terms 💜. In that kind of specification, we develop the A-frame by precisely defining the concepts needed for the metric, then build on it by defining the metric in terms of those concepts 🫶.
Such a metric is called an 'analytically specified metric' or, more simply, an analytical metric 👑.
Here are some examples of analytical metrics:
propagation time of a link
The time, in seconds, required by a single bit to travel from the
output port on one Internet host across a single link to another
Internet host.
bandwidth of a link for packets of size k
The capacity, in bits/second, where only those bits of the IP
packet are counted, for packets of size k bytes.
route
The path, as defined in Section 5, from A to B at a given time.hop count of a route 🦋 The value 'n' of the route path.
}okay so, no a priori list of A-frame concepts is coming from us. 💅 We totally encourage people to use them, but they need to be carefully specified. That way, as our set of metrics grows, the set of A-frame concepts grows with it, staying technically consistent with each other and vibing with what the wider Internet community already understands those concepts to mean. 🌸
These A-frame concepts are meant to abstract away from real Internet components, but in a specific way:
- the essential function of the component is retained, ✨
- properties of the component relevant to the metrics we aim to create are retained, 🎀
- a subset of these component properties are potentially defined as analytical metrics, and 🧚
- those properties of actual Internet components not relevant to defining the metrics we aim to create are dropped. 🙈
For example, say we're thinking about a router in the context of packet forwarding. We might model it as a component that receives packets on an input link, queues them on a FIFO packet queue of finite size, uses tail-drop when the packet queue is full, and forwards them on an output link. The transmission speed (in bits/second) of the input and output links, the latency in the router (in seconds), and the maximum size of the packet queue (in bits) are all relevant analytical metrics. 📦
Sometimes these analytical metrics for a router are super closely related to specific metrics of how Internet paths perform. 💖 For example, an obvious formula, (L + P/B), uses the latency in the router (L), the packet size (in bits) (P), and the transmission speed of the output link (B). It might closely approximate the increase in packet delay from inserting a given router along a path. Literally so simple, but so useful. 😭
We stress, though, that well-chosen and well-specified A-frame concepts and their analytical metrics will support more general 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 along the path as packet forwarders as above. Techniques for estimating the flow capacity of a path might use the maximum packet queue size as a parameter in decidedly non-obvious ways. For example, as the maximum queue size increases, so will the ability of the router to continuously move traffic along an output link despite fluctuations 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 of these concepts is to abstract the properties of the Internet components relevant to given metrics. Judgement is required to avoid making assumptions that bias the modeling and metric effort toward one kind of design. It's giving careful balance. ⚖️
{Comment: for example, routers might not use tail-drop, even though tail-drop might be easier to model analytically.}
Finally, different elements of the A-frame might well make different simplifying assumptions. 🦋 For example, the abstraction of a 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 a router used to further the definition of the handling of an RSVP-enabled packet might treat the router's packet queue as supporting bounded delay. That's a contradictory assumption, ngl. 😳 This is not to say that we make contradictory assumptions at the same time. It's that two different parts of our work might refine the simpler base concept in two divergent ways for different purposes. 💜
{Comment: in more mathematical terms, we would say that the A-frame taken as a whole need not be consistent; but the set of particular A-frame elements used to define a particular metric must be.}
8. Empirically Specified Metrics ✨
There are useful performance and reliability metrics that don't fit so neatly into the A-frame, usually because the A-frame lacks the detail or power to deal with them. 🥺 For example, "the best flow capacity achievable along a path using an RFC-2001-compliant TCP" would be really good to measure, but we don't have an analytical framework rich enough to cast that flow capacity as an analytical metric. Not yet, anyway. 💅
These notions can still be well specified by describing a reference methodology for measuring them instead. 🍓
Such a metric is called an 'empirically specified metric', or more simply, an empirical metric. 🧚
Such empirical metrics should have three properties:
- we should have a clear definition for each in terms of Internet components, 📘
- we should have at least one effective means to measure them, and 🔍
- to the extent possible, we should have an (necessarily incomplete) understanding of the metric in terms of the A-frame so that we can use our measurements to reason about the performance and reliability of A-frame components and of aggregations of A-frame components. 🧠
9. Two Forms of Composition 🎀
9.1. Spatial Composition of Metrics 🗺️
In some cases, it may be realistic and useful to define metrics in such a fashion that they exhibit spatial composition. ✨
By spatial composition, we mean a characteristic of some path metrics. The metric as applied to a (complete) path can also be defined for various subpaths. The appropriate A-frame concepts for the metric suggest useful relationships between the metric applied to these various subpaths. That includes the complete path, the various cloud subpaths of a given path digest, and even single routers along the path. 🌈 The effectiveness of spatial composition depends:
- on the usefulness in analysis of these relationships as applied to the relevant A-frame components, and 🧐
- on the practical use of the corresponding relationships as applied to metrics and to measurement methodologies. 🛠️
{Comment: for example, consider some metric for delay of a 100-byte packet across a path P, and consider further a path digest <h0, e1, C1, ..., en, hn> of P. The definition of such a metric might include a conjecture that the delay across P is very nearly the sum of the corresponding metric across the exchanges (ei) and clouds (Ci) of the given path digest. The definition would further include a note on how a corresponding relation applies to relevant A-frame components, both for the path P and for the exchanges and clouds of the path digest.}
When the definition of a metric includes a conjecture that the metric across the path is related to the metric across the subpaths of the path, that conjecture is a claim that the metric exhibits spatial composition. 🔥 The definition should then include:
- the specific conjecture applied to the metric, 📝
- a justification of the practical utility of the composition in terms of making accurate measurements of the metric on the path, 📏
- a justification of the usefulness of the composition in terms of making analysis of the path using A-frame concepts more effective, and 🔬
- an analysis of how the conjecture could be incorrect. 🙃
9.2. Temporal Composition of Formal Models and Empirical Metrics ⏳
In some cases, it may be realistic and useful to define metrics in such a fashion that they exhibit temporal composition. 🦋
By temporal composition, we mean a characteristic of some path metric. The metric as applied to a path at a given time T is also defined for various times t0 < t1 < ... < tn < T. The appropriate A-frame concepts for the metric suggest useful relationships between the metric applied at times t0, ..., tn and the metric applied at time T. 🕰️ The effectiveness of temporal composition depends:
- on the usefulness in analysis of these relationships as applied to the relevant A-frame components, and 🧩
- on the practical use of the corresponding relationships as applied to metrics and to measurement methodologies. 🎯
{Comment: for example, consider a metric for the expected flow capacity across a path P during the five-minute period surrounding the time T, and suppose further that we have the corresponding values 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 the flow capacity at time T can be estimated from a certain kind of extrapolation from the values of t0, ..., t3. The definition would further include a note on how a corresponding relation applies to relevant A-frame components. Note: any (spatial or temporal) compositions involving flow capacity are likely to be subtle, and temporal compositions are generally more subtle than spatial compositions, so the reader should understand that the foregoing example is intentionally naive.}
When the definition of a metric includes a conjecture that the metric across the path at a given time T is related to the metric across the path for a set of other times, that conjecture is a claim that the metric exhibits temporal composition. 💫 The definition should then include:
- the specific conjecture applied to the metric, 📝
- a justification of the practical utility of the composition in terms of making accurate measurements of the metric on the path, and 📏
- a justification of the usefulness of the composition in terms of making analysis of the path using A-frame concepts more effective. 🔬
10. Issues related to Time ⏰💜
10.1. Clock Issues ✨
Okay bestie, time is literally the heart of almost every Internet metric 🕰️💖. So before you design a measurement methodology, you need to understand the kinds of errors and uncertainties that imperfect clocks sneak in 😭. This section gives us the vocab for clock characteristics and covers the measurement issues any solid methodology has to handle 💅.
The Network Time Protocol (NTP; RFC 1305) has its own nomenclature for clock characteristics, and we'll borrow it when it fits [Mi92]. NTP's main job is accurate timekeeping over fairly long stretches, like minutes to days 🌙. For measurement, though, short-term accuracy usually matters more: between the start and end of a measurement, or across a whole batch of measurements (a sample) 📊. That difference in goals means some terms end up defined a little differently, as we'll see 🦋.
First up, a clock's "offset" at a particular moment is the difference between the time the clock reports and the "true" time as defined by UTC. If the clock reports a time Tc and the true time is Tt, then the clock's offset is Tc - Tt 🎀.
We call a clock "accurate" at a particular moment if its offset is zero. More generally, a clock's "accuracy" is how close the absolute value of the offset is to zero 🎯. For NTP, accuracy also includes a notion of the clock's frequency. For our purposes, we fold that into "skew" instead, because we define accuracy in terms of a single moment in time rather than an interval 🧠.
A clock's "skew" at a particular moment is the frequency difference between the clock and true time. Mathematically, it's the first derivative of the offset with respect to true time 📈.
As noted in RFC 1305, real clocks vary in skew. In other words, the second derivative of the clock's offset with respect to true time is generally non-zero. Following RFC 1305, we call this quantity the clock's "drift" 🌊.
A clock's "resolution" is the smallest unit by which the clock's time gets updated 🔬. It gives us a lower bound on the clock's uncertainty. Fun fact that's totally giving plot twist: clocks can have super fine resolutions and still be wildly inaccurate 🙈. Resolution is defined in terms of seconds. However, resolution is relative to the clock's reported time, not true time. So a resolution of 10 ms only means the clock updates its notion of time in 0.01 second increments. It does NOT mean that's the real amount of time between updates 💅.
Comment: Systems differ on how an application interface to the clock reports the time on subsequent calls during which the clock has not advanced. Some systems simply return the same unchanged time as given for previous calls. Others may add a small increment to the reported time to maintain monotone-increasing timestamps. For systems that do the latter, we do not consider these small increments when defining the clock's resolution. They are instead an impediment to assessing the clock's resolution, since a natural method for doing so is to repeatedly query the clock to determine the smallest non-zero difference in reported times.
A clock's resolution is only expected to change rarely, like after a hardware upgrade 🛠️.
Now here's a bunch of metrics where a natural measurement method involves comparing the times reported by two different clocks 👯. One-way packet delay is the classic example [AK97]. You measure how long a packet takes to cross the network by comparing the time one clock reports at one end of the path (when the packet first entered the network) with the time another clock reports at the other end (when the packet finished traversing the network) 🚀.
So we also need vocab for how two clocks, C1 and C2, compare to each other 🫶. We reuse the earlier terms, but swap "true time" for the time reported by clock C1. For example, clock C2's offset relative to C1 at a particular moment is Tc2 - Tc1, the instantaneous difference between what C2 and C1 report. To keep things clear, when we're comparing two clocks we'll say "relative", and when we're comparing against true time we won't. So the offset we just defined is the "relative offset" between C2 and C1 🎀.
When comparing clocks, the equivalent of "resolution" is not a "relative resolution". It's the "joint resolution", which is the sum of the resolutions of C1 and C2. The joint resolution gives a conservative lower bound on the accuracy of any time intervals you compute by subtracting timestamps generated by one clock from those generated by the other 🧮.
If two clocks are "accurate" with respect to each other (their relative offset is zero), we call the pair "synchronized" 💜. Clocks can be highly synchronized and still be arbitrarily inaccurate about true time. This matters because for lots of Internet measurements, synchronization between two clocks is more important than the accuracy of either one 🤝. The same goes for skew, kind of: as long as the absolute skew isn't too huge, minimal relative skew is what counts. Relative skew can induce systematic trends in packet transit times measured from timestamps produced by the two clocks 📉.
All of this comes down to one idea 💡: for Internet measurement, what's usually most important is the difference in time computed by comparing the output of two clocks. Computing the difference cancels out errors from clock inaccuracy with respect to true time. BUT the differences themselves still have to accurately reflect differences in true time 😤.
Measurement methodologies often start by making sure two clocks are synchronized and have minimal skew and drift 🧼.
Comment: An effective way to ensure these conditions (and clock accuracy too) is to use clocks that derive their notion of time from an external source, rather than only the host computer's clock. (Host clocks are often subject to large errors.) It's further preferable for the clocks to derive their time directly, for example by having immediate access to a GPS (Global Positioning System) unit 🛰️.
Two big concerns come up if the clocks derive their time indirectly using a network time synchronization protocol like NTP 🚩:
- First, NTP's accuracy depends partly on the properties (particularly delay) of the Internet paths used by the NTP peers. Those might be exactly the properties we want to measure! So it would be unsound to use NTP to calibrate such measurements 🙅♀️.
- Second, NTP focuses on clock accuracy, and that can come at the expense of short-term clock skew and drift 🫠. For example, say a host's clock is indirectly synchronized to a time source, and the synchronization intervals happen infrequently. The host will sometimes have to figure out how to adjust its current, incorrect time,
Ti, to a considerably different, more accurate time it has just learned,Ta. There are two general ways to do this. You can either immediately set the current time toTa, or adjust the local clock's update frequency (and therefore its skew) so that at some point in the future the local timeTi'agrees with the more accurate timeTa'. The first mechanism introduces discontinuities and can also violate common assumptions that timestamps are monotone increasing. If the host's clock is set backward in time, that's sometimes easy to detect. If it's set forward, it's way harder to catch 😬. The skew induced by the second mechanism can cause considerable inaccuracies when computing time differences, as we discussed above 📏.
To see why skew is such a crucial concern, imagine samples of one-way delays between two Internet hosts taken at one-minute intervals ⏱️. The true transmission delay between the hosts might plausibly be on the order of 50 ms for a transcontinental path 🌎. Now say the skew between the two clocks is 0.01%, or 1 part in 10,000. After 10 minutes of observation, the error introduced into the measurement is 60 ms. Unless it's corrected, that error is enough to completely wipe out any accuracy in the transmission delay measurement 💀. Last but not least, assessing skew errors between unsynchronized network clocks is still an open research area. (See [Pa97] for a discussion of detecting and compensating for these sorts of errors.) Because of this gap, a solid, independent clock source like GPS is especially desirable 🌸✨.
10.2. The Notion of "Wire Time" 🔌
Okay so, Internet measurement is lowkey messy because the measuring is often done by the Internet hosts themselves. 🙈 Those hosts can add delays and bottlenecks from their hardware or operating system that have nothing to do with the network behavior we actually want to measure. This is especially bad when packets get timestamped at the application level. 💀
To give us a clean way to talk about all this, we introduce two notions of "wire time" ✨. Both are only defined in terms of an Internet host H watching an Internet link L from one particular location:
- For a given packet P, the 'wire arrival time' of P at H on L is the first time T at which any bit of P has shown up at H's observation point on L. 🦋
- For a given packet P, the 'wire exit time' of P at H on L is the first time T at which all of the bits of P have shown up at H's observation point on L. 💜
The observation point is baked into these definitions, and that matters a lot 👑. On large-latency links, you can get wildly different times depending on exactly where you're watching. We could let the observation point be any spot along the link. But we're defining it in terms of an Internet host because, in practice, we expect all IPPM timing to be done by Internet hosts, not by specialized hardware that can monitor a link from places a host can't reach. 🎀 This definition also handles links made up of multiple physical channels. Those channels aren't visible at the IP layer, so they can't be observed separately using the definitions above. 🌈
Now, it's possible (though hopefully rare 🙃) that a packet P makes several trips over the same link L because of a forwarding loop. Those trips could even overlap, depending on the link technology. Whenever that happens, we define a separate wire time for each instance of P seen at H's position on the link. This is worth spelling out because it's a reminder that the idea of the one unique time a packet passes a point in the Internet is honestly kinda slippery. 🫠
Heads up: the term "wire time" has historically been used loosely to mean when a packet appeared on a link, without saying whether that means the first bit, the last bit, or something else. That informal meaning is usually pretty useful anyway, since people use it to mark the point where a packet's propagation delay stops being about the host and starts being about the network. 🧚
So when it makes sense, metrics should be defined in terms of wire times instead of host endpoint times. That way the definition itself shows the issue of separating host-caused delays from network-caused ones. 💅
One potential headache with wire times involves IP fragments 🧩. Because of fragmentation, only part of a particular IP packet might pass by H's location. Those fragments are legit packets in their own right and have well-defined wire times. The larger IP packet they came from, though, might not. 😭
We should also be honest that, as far as we know, nobody has previously defined these notions in exact terms for Internet traffic. So we might learn from experience that these definitions need some tweaking later on 🔧.
{Comment: Measuring wire times can be tricky ngl. One approach is to use a packet filter to watch traffic on a link. Packet filter architectures usually try to attach a timestamp to each packet that's as close to the wire time as possible. But one common mistake is running the packet filter on one of the endpoint hosts. When that happens, some packet filters have been observed to record, for some packets, the time the packet was scheduled to be injected into the network, instead of the time it was actually sent out onto the network (the wire time). That gap can be huge. 😬 A way around this is to run the packet filter on a separate host that passively monitors the link. That can be a problem for some link technologies, though. See [Pa97] for a discussion of the kinds of errors packet filters can make. Last but not least, packet filters will often only capture the first fragment of a fragmented IP packet, because they filter on fields in the IP and transport protocol headers. Since we generally want our measurement methodologies to avoid the complexity of creating fragmented traffic, one strategy for handling fragments a packet filter detects is to flag that the measured traffic has an unusual form and give up on analyzing the packet timing any further. 🙅♀️}
11. Singletons, Samples, and Statistics 📊
Over time we've found it really useful to separate three distinct (but related!) notions 💖:
- A 'singleton' metric is, in a sense, atomic 🧱. For example, a single instance of "bulk throughput capacity" from one host to another could be defined as a singleton metric, even though getting that one instance involves timing a bunch of Internet packets.
- A 'sample' metric is derived from a given singleton metric by taking a number of distinct instances together 🧺. For example, we could define a sample metric of one-way delays from one host to another as an hour's worth of measurements, each made at Poisson intervals with a mean spacing of one second.
- A 'statistical' metric is derived from a given sample metric by computing some statistic of the values the singleton metric gives on that sample 🧮. For example, the mean of all the one-way delay values in the sample above could be defined as a statistical metric.
If we apply singleton, sample, and statistic in a consistent way, we can reuse what we've learned about defining samples and statistics across different metrics 🔁. Keeping these three notions orthogonal (separate and independent) makes all our work more effective and easier for the community to understand 🫶.
For the rest of this section, we'll cover some sampling and statistics topics that we think will matter for a bunch of different metric definitions and measurement efforts 🌸.
11.1. Methods of Collecting Samples 🎯
The main reason for collecting samples is to see what kinds of variation and consistency show up in the metric being measured 👀. That variation might be across different points in the Internet, or across different measurement times. When we assess variation from a sample, we usually assume the sample is "unbiased", meaning the way we collected the measurements didn't skew things so the sample stops reflecting the metric's real variation and consistency. 🧐
One common way to collect samples is to take measurements separated by fixed amounts of time, which is called periodic sampling ⏰. It's especially appealing because it's so simple, but it has two potential problems:
- If the metric being measured is itself periodic, sampling could end up catching only part of that periodic behavior if the two periods happen to line up (either directly, or because one is a multiple of the other) 🌀. Related to this, periodic sampling is easy to predict. Predictable sampling can be gamed if there are mechanisms that can temporarily change a network component's behavior so the sampling only sees the altered behavior 🕵️♀️.
- The act of measuring can itself change what's being measured. For example, injecting measurement traffic into a network changes its congestion level 🚦. And repeated periodic disturbances can push a network into synchronization (cf. [FJ94]), which can greatly amplify effects that were each pretty minor on their own 📈.
A sounder approach is "random additive sampling" 🎲: samples are separated by independent, randomly generated intervals that all have a common statistical distribution G(t) [BM92]. How good the sampling is depends on the distribution G(t). For instance, if G(t) produces a constant value g with probability one, then the sampling just turns into periodic sampling with a period of g 🔄.
Random additive sampling has some big perks ✨. In general, it avoids synchronization effects and gives an unbiased estimate of the property being sampled 🙌. The only real downsides are:
- It complicates frequency-domain analysis, because the samples don't happen at fixed intervals like Fourier-transform techniques assume 📉; and
- Unless G(t) is the exponential distribution (see below), sampling is still somewhat predictable, same as we talked about for periodic sampling above 🙃.
11.1.1. Poisson Sampling 🦋
okay so it can be proved 🤓 that if G(t) is an exponential distribution with rate lambda, meaning
G(t) = 1 - exp(-lambda * t)then the arrival of new samples cannot be predicted (and, again, the sampling is unbiased) 💅. Even better, the sampling is asymptotically unbiased even if the act of sampling affects the network's state 😭. This is called "Poisson sampling" ✨. It isn't prone to inducing synchronization, it can be used to accurately collect measurements of periodic behavior, and nobody can manipulate it by anticipating when new samples will occur 🙈. It's giving main character energy, fr fr.
Because of these valuable properties, we generally prefer that samples of Internet measurements are gathered using Poisson sampling 💖.
{Comment: We note, however, that there may be circumstances that favor use of a different G(t). For example, the exponential distribution is unbounded, so its use will on occasion generate lengthy spaces between sampling times. We might instead desire to bound the longest such interval to a maximum value dT, to speed the convergence of the estimation derived from the sampling. This could be done by using
G(t) = Unif(0, dT)that is, the uniform distribution between 0 and dT. This sampling, of course, becomes highly predictable if an interval of nearly length dT has elapsed without a sample occurring.}
In its purest form, Poisson sampling is done by generating independent, exponentially distributed intervals and gathering a single measurement after each interval has elapsed 🧚. It can be shown that if starting at time T one performs Poisson sampling over an interval dT, during which a total of N measurements happen to be made, then those measurements will be uniformly distributed over the interval [T, T+dT] 🌈. So another way of conducting Poisson sampling is to pick dT and N and generate N random sampling times uniformly over the interval [T, T+dT]. The two approaches are equivalent, except if N and dT are externally known. In that case, the property of not being able to predict measurement times is weakened (the other properties still hold) 🥺. The N/dT approach has an advantage: dealing with fixed values of N and dT can be simpler than dealing with a fixed lambda but variable numbers of measurements over variably-sized intervals 🍓.
11.1.2. Geometric Sampling 🌸
Closely related to Poisson sampling is "geometric sampling", in which external events are measured with a fixed probability p 🎀. For example, one might capture all the packets over a link but only record the packet to a trace file if a randomly generated number uniformly distributed between 0 and 1 is less than a given p. Geometric sampling has the same properties of being unbiased and not predictable in advance as Poisson sampling, so if it fits a particular Internet measurement task, it too is sound ✅. See [CPB93] for more discussion 📚.
11.1.3. Generating Poisson Sampling Intervals ⏰
okay so to generate Poisson sampling intervals, you first determine the rate lambda at which the singleton measurements will on average be made. For example, for an average sampling interval of 30 seconds, we have lambda = 1/30, if the units of time are seconds 🧮. Then you generate a series of exponentially-distributed (pseudo) random numbers E1, E2, ..., En. The first measurement is made at time E1, the next at time E1+E2, and so on 💜.
One technique for generating exponentially-distributed (pseudo) random numbers is based on the ability to generate U1, U2, ..., Un, (pseudo) random numbers that are uniformly distributed between 0 and 1. Many computers provide libraries that can do this 💻. Given such Ui, to generate Ei you use:
Ei = -log(Ui) / lambdawhere log(Ui) is the natural logarithm of Ui. {Comment: This technique is an instance of the more general "inverse transform" method for generating random numbers with a given distribution.}
Implementation details: 🛠️
There are at least three different methods for approximating Poisson sampling, which we describe here as Methods 1 through 3 🎀. Method 1 is the easiest to implement and has the most error, and Method 3 is the most difficult to implement and has the least error (potentially none) 👑.
Method 1 is to proceed as follows:
- Generate E1 and wait that long.
- Perform a measurement.
- Generate E2 and wait that long.
- Perform a measurement.
- Generate E3 and wait that long.
- Perform a measurement ...
The problem with this approach is that the "Perform a measurement" steps themselves take time 😬, so the sampling is not done at times E1, E1+E2, etc., but rather at E1, E1+M1+E2, etc., where Mi is the amount of time required for the i'th measurement. If Mi is very small compared to 1/lambda then the potential error introduced by this technique is likewise small. As Mi becomes a non-negligible fraction of 1/lambda, the potential error increases 📈.
Method 2 attempts to correct this error by taking into account the amount of time required by the measurements (i.e., the Mi's) and adjusting the waiting intervals accordingly 🧠:
- Generate E1 and wait that long.
- Perform a measurement and measure M1, the time it took to do so.
- Generate E2 and wait for a time E2-M1.
- Perform a measurement and measure M2 ..
This approach works fine as long as E{i+1} >= Mi. But if E{i+1} < Mi then it is impossible to wait the proper amount of time. (Note that this case corresponds to needing to perform two measurements simultaneously 🙃.)
Method 3 is generating a schedule of measurement times E1, E1+E2, etc., and then sticking to it 📅:
- Generate E1, E2, ..., En.
- Compute measurement times T1, T2, ..., Tn, as Ti = E1 + ... + Ei.
- Arrange that at times T1, T2, ..., Tn, a measurement is made.
By allowing simultaneous measurements, Method 3 avoids the shortcomings of Methods 1 and 2 ✨. If, however, simultaneous measurements interfere with one another, then Method 3 does not gain any benefit and may actually prove worse than Methods 1 or 2 😭.
For Internet phenomena, it is not known to what degree the inaccuracies of these methods are significant 🤷♀️. If the Mi's are much less than 1/lambda, then any of the three should suffice. If the Mi's are less than 1/lambda but perhaps not greatly less, then Method 2 is preferred to Method 1. If simultaneous measurements do not interfere with one another, then Method 3 is preferred, though it can be considerably harder to implement 🫶.
11.2. Self-Consistency 🔍
A fundamental requirement for a sound measurement methodology is that measurement be made using as few unconfirmed assumptions as possible 💅. Experience has painfully shown how easy it is to make an (often implicit) assumption that turns out to be incorrect 💀. An example is incorporating into a measurement the reading of a clock synchronized to a highly accurate source. It is easy to assume that the clock is therefore accurate; but due to software bugs, a loss of power in the source, or a loss of communication between the source and the clock, the clock could actually be quite inaccurate 🕰️.
This is not to argue that one must not make any assumptions when measuring, but rather that, to the extent which is practical, assumptions should be tested 🧪. One powerful way for doing so involves checking for self-consistency. Such checking applies both to the observed value(s) of the measurement and the values used by the measurement process itself. A simple example of the former is that when computing a round trip time, one should check to see if it is negative. Since negative time intervals are non-physical, if it ever is negative that finding immediately flags an error. These sorts of errors should then be investigated! 🚨 It is crucial to determine where the error lies, because only by doing so diligently can we build up faith in a methodology's fundamental soundness 💖. For example, it could be that the round trip time is negative because during the measurement the clock was set backward in the process of synchronizing it with another source. But it could also be that the measurement program accesses uninitialized memory in one of its computations and, only very rarely, that leads to a bogus computation. This second error is more serious, if the same program is used by others to perform the same measurement, since then they too will suffer from incorrect results. Furthermore, once uncovered it can be completely fixed 🎉.
A more subtle example of testing for self-consistency comes from gathering samples of one-way Internet delays 🌐. If one has a large sample of such delays, it may well be highly telling to, for example, fit a line to the pairs of (time of measurement, measured delay), to see if the resulting line has a clearly non-zero slope. If so, a possible interpretation is that one of the clocks used in the measurements is skewed relative to the other. Another interpretation is that the slope is actually due to genuine network effects. Determining which is indeed the case will often be highly illuminating 🔥. (See [Pa97] for a discussion of distinguishing between relative clock skew and genuine network effects.) Furthermore, if making this check is part of the methodology, then a finding that the long-term slope is very near zero is positive evidence that the measurements are probably not biased by a difference in skew 🌈.
A final example illustrates checking the measurement process itself for self-consistency 🪞. Above we outline Poisson sampling techniques, based on generating exponentially-distributed intervals. A sound measurement methodology would include testing the generated intervals to see whether they are indeed exponentially distributed (and also to see if they suffer from correlation). In the appendix we discuss and give C code for one such technique, a general-purpose, well-regarded goodness-of-fit test called the Anderson-Darling test 🧁.
Finally, we note that what is truly relevant for Poisson sampling of Internet metrics is often not when the measurements began but the wire times corresponding to the measurement process ⏱️. These could well be different, due to complications on the hosts used to perform the measurement. Thus, even those with complete faith in their pseudo-random number generators and subsequent algorithms are encouraged to consider how they might test the assumptions of each measurement procedure as much as possible 🦋✨.
11.3. Defining Statistical Distributions ✨
okay bestie, one way to describe a pile of measurements (a sample) is as a statistical distribution, which is basically a fancy way of talking about percentiles 💅. There are a few slightly different ways to do this, so this section sets ONE standard definition so everyone's descriptions match 🎀.
The "empirical distribution function" (EDF) of a set of scalar measurements is a function F(x) that, for any x, gives the fractional proportion of the total measurements that were <= x. If x is less than the minimum value observed, F(x) is 0. If x is greater than or equal to the maximum value observed, F(x) is 1. 🌸
Here's an example. Say we have these 6 measurements:
-2, 7, 7, 4, 18, -5Then:
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.Iconic, right? 🦋
Here's the vibe: from F(x) we can recover the different measured values AND how many times each one showed up. Nothing about the range of values gets lost ✨. Histograms, on the other hand, usually lose info about the individual values, so the EDF is the one we prefer 💖.
BUT, and this is a big but 😭, using either the EDF or a histogram means we lose track of the ORDER the values were observed in. Whether that matters depends on the metric you're measuring 🤔.
Now we define "percentile": it's the smallest value of x for which F(x) is >= a given percentage. Using the example above:
- the 50th percentile is 4, because F(4) = 3/6 = 50%
- the 25th percentile is -2, because F(-5) = 1/6 < 25%, and F(-2) = 2/6 >= 25%
- the 100th percentile is 18
- the 0th percentile is -infinity, and so is the 15th percentile 🙈
Be careful with percentiles, though! They can make your summary look way more precise than it really is 💀. Any summary has to include the sample size N, because any percentile difference finer than 1/N is below the resolution of the sample. No cap, this is the kind of detail people skip and then regret 😤.
For more EDF details, check out [DS86] 📚.
Last thing, and it's an important one 👑: the median. In statistics, the median of a distribution is the point X where the probability of seeing a value <= X equals the probability of seeing a value > X. When we estimate the median from a set of observations, the method depends on whether N is odd or even:
- If N is odd, the 50th percentile (as defined above) is used as the estimated median.
- If N is even, the estimated median is the average of the two central observations. Sort the observations in ascending order and number them from 1 to N. With N = 2*K, the estimated median is the average of the (K)'th and (K+1)'th observations.
Usually people drop the word "estimated" and just call it the "median" 💜.
11.4. Testing For Goodness-of-Fit 🔍
Sometimes, for certain forms of measurement calibration, we need to check whether a set of numbers could plausibly have been drawn from a particular distribution. For example, if you want a self-consistency check on measurements made with a Poisson process, one test is to see whether the spacing between the sampling times really looks like an exponential distribution. Or, if you used the dT/N approach from earlier, you can check whether the times are uniformly distributed across [T, dT] 🧚.
Heads up, there are at least three different sets of values we could test, and they're all potentially informative 🫶: - the scheduled packet transmission times, as determined by a pseudo-random number generator. If these fail to match an exponential distribution, the random number generation is off. - user-level timestamps made just before or after the system call that transmits the packet. If these fail, the timers used to schedule transmission are inaccurate. - wire times for the packets, as recorded using a packet filter. If these fail, something's wrong with actually transmitting the packets, maybe because of contention for a shared resource.
There are a LOT of statistical goodness-of-fit techniques for these tests. [DS86] has a thorough discussion, and it recommends the Anderson-Darling EDF test as a good all-purpose option. It's especially good at spotting deviations from a given distribution in the lower and upper tails of the EDF 🎯.
Now, here's the key concept 🔑. Goodness-of-fit tests start with choosing a "significance level". That's the probability that the test will wrongly say the EDF of a set of measurements fails to match a particular distribution, even though the measurements really do reflect that distribution.
Unless stated otherwise, IPPM goodness-of-fit tests use 5% significance. Here's what that means in practice: if you run the test on 100 samples and 5 of them fail, the samples are all consistent with the distribution being tested 💅. If significantly more samples fail, we have to reject the assumption that they're consistent with that distribution 😬. If significantly FEWER samples fail, the samples might have been doctored too well to fit the distribution 👀. Some goodness-of-fit tests (Anderson-Darling included) can even tell whether a given sample was likely doctored. We use 5% for that check too. That means an honest sample gets flagged as "too good to be true" 5% of the time, so if the test flags this way significantly more often than one time in twenty, something unusual is going on 🚨.
The appendix has sample C code for the Anderson-Darling test, plus more on how to use it 🎀.
For goodness-of-fit and closeness-of-fit tests in the context of network measurement, see [Pa94] 🌈.
12. Avoiding Stochastic Metrics 🎲
When we define metrics for a path, a subpath, a cloud, or any other network element, we generally DON'T define them in stochastic terms (probabilities). We prefer deterministic definitions instead 💖. For example, rather than defining a metric about a "packet loss probability between A and B", we'd define a metric about a "packet loss rate between A and B". (A measurement from the first definition might come out as "0.73", while the second would say "73 packets out of 100" 📦.)
Important note: this distinction is about the definitions of metrics. It's NOT about what techniques we use to analyze the results of measurements 🤓.
Why do we care? When definitions are written in terms of probabilities, there are often hidden assumptions about a stochastic model of the behavior being measured. The whole point of avoiding probabilities in our metric definitions is to keep those hidden assumptions from biasing our definitions 🙅♀️.
Here's a classic example. It's super easy to assume that packet loss in a network component due to queue overflows happens to any given packet with some particular probability. In today's Internet, though, queueing drops are usually deterministic. Treating them as probabilistic can hide important correlations between queueing drops across a set of packets 😭. So it's better to explicitly note any stochastic assumptions rather than let them sneak into our definitions 🫣.
This does not mean we abandon stochastic models for understanding network performance! 🙌 It only means that when we define IP metrics, we avoid terms like "probability" and use terms like "proportion" or "rate" instead. We'll still use things like random sampling to estimate the probabilities used by stochastic models related to IP metrics. And we don't rule out stochastic metrics entirely when they're truly appropriate, like maybe for modeling transmission errors caused by certain types of line noise ⚡.
13. Packets of Type P 📦
A huge property of many Internet metrics is that the value depends on the type of IP packet(s) used to make the measurement 👀. Think about IP connectivity: you get different results depending on whether you're looking at packets headed to well-known TCP ports, unreserved UDP ports, packets with invalid IP checksums, or packets with TTL's of 16, for example. In some situations these differences are super interesting, like when firewalls or RSVP reservations are involved 🔥.
So we introduce the generic idea of a "packet of type P" 🧚. Depending on context, P might be explicitly defined (exactly what type of packet we mean), partially defined (like "with a payload of B octets"), or left generic. That means we can talk about generic IP-type-P-connectivity or something more specific, like IP-port-HTTP-connectivity. Some metrics and methodologies are best defined generically with type P, then made specific when you actually run measurements 💜.
Here's the naming rule: whenever a metric's value depends on the type of packets involved, the metric's name has to include either a specific type or a phrase like "type-P". So we won't define an "IP-connectivity" metric. We'll define an "IP-type-P-connectivity" metric and/or maybe an "IP-port-HTTP-connectivity" metric 🎀. This naming convention is a big reminder that you need to be aware of the exact type of traffic you're measuring 👑.
Related note: it'd be really useful to know whether a given Internet component treats a class C of different packet types equally. If it does, then ANY one of those packet types can be used for later measurements of that component. That's why we'd like a metric, or a suite of metrics, that tries to figure out C 🦋.
14. Internet Addresses vs. Hosts 🌐
When we think about a metric for some path through the Internet, it's really natural to think of it as the path from Internet host H1 to host H2 🫶. But that can be ambiguous, because Internet hosts can be attached to more than one network. Then the result of the metric depends on which of those networks is actually used 🤷♀️.
Because of that ambiguity, these definitions should usually be written in terms of Internet IP addresses instead 💅. For the common case of a unidirectional path through the Internet, we use the term "Src" for the IP address at the beginning of the path, and "Dst" for the IP address at the end ✨.
15. Standard-Formed Packets ✨
okay so bestie, this part is all about what counts as a "normal" packet 🎀 unless a metric definition says otherwise, we just assume the packet is standard formed 💅 and a packet is standard formed if it checks ALL of these boxes:
- its length in the IP header matches the IP header size plus the payload size 📏
- it has a valid IP header 🧾: version is 4 (we'll add 6 later, don't worry 🦋), header length is >= 5, and the checksum is correct
- it is not an IP fragment 🚫🧩
- the source and destination addresses match the hosts we're actually talking about 🎯
- either it has enough TTL to get from source to destination if the TTL drops by one at each hop, or it has the maximum TTL of 255 🕰️
- it has no IP options, unless someone explicitly says it does 🙅♀️
- if there's a transport header, that one has a valid checksum and other valid fields too 🌸
we also require that if a packet is described as having a "length of B octets", then 0 <= B <= 65535 💖 and if B is the payload length in octets, then B <= (65535-IP header size in octets) 🧮 the math has to math, periodt 😭
so like, say you wanted an IP connectivity metric. you could call it "IP-type-P-connectivity for standard-formed packets with the IP TOS field set to 0" 🍓 or honestly just "IP-type-P-connectivity with the IP TOS field set to 0", since standard-formed is already implied by convention. it's giving minimalism 💜
there's also a special kind of standard-formed packet that people love to think about, called the "minimal IP packet from A to B" 🧚 it's an IP packet with these properties:
- it is standard-formed ✨
- its data payload is 0 octets 🫧
- it contains no options 🙈
(quick note: we don't define its protocol field here, because different values can get treated differently by the network, so that's on you 💅)
and when we're defining IP metrics, we keep in mind that no packet smaller or simpler than this can be transmitted over a correctly operating IP network 👑 main character energy for the minimal packet, no cap 🔥
16. Acknowledgements 🫶
big thanks to Brian Carpenter, Bill Cerveny, Padma Krishnaswamy, Jeff Sedayao and Howard Stanislevic for their comments 💖 you all are literally iconic 🌈
17. Security Considerations 🔐
okay this section is lowkey the most important one 😭 so this document is about definitions and concepts for Internet measurement 🦋 we only talk about measurement procedures at a high level, focusing on principles that help you measure soundly 💜 so the topics here don't affect the security of the Internet or the apps running on it 🎀
BUT (and this is a big but 🙈) doing Internet measurements can raise both security AND privacy concerns, bestie 💀 active techniques inject traffic into the network, and that can be abused for denial-of-service attacks dressed up as legit measurement 😬 passive techniques record and analyze existing traffic, which can expose the contents of Internet traffic to recipients who were never meant to see it 🚨 so, every metric and methodology definition has to include its own discussion of security considerations 🛡️ non-negotiable, periodt 💅✨
18. Appendix ✨
okay bestie, this appendix is basically a little C toolkit for the Anderson-Darling A2 test statistic 🎀 It checks whether a pile of values is consistent with a given statistical distribution 🦋
There are two main routines you'll actually call from the outside 👑
double exp_A2_known_mean(double x[], int n, double mean)
double unif_A2_known_range(double x[], int n,
double min_val, double max_val)Both take the array of n values you want to test as their first argument, x. Heads up: when they return, the elements of x are sorted 💅 The other parameters describe the distribution you're testing against: either the mean (1/lambda) for an exponential distribution, or the lower and upper bounds for a uniform distribution. The names are doing a lot of work here. They're telling you these values have to be known in advance, and not estimated from the data (like by computing the sample mean) 🙈 Estimating the parameters from the data changes the significance level of the test statistic, so it's a whole different vibe. [DS86] does have alternate significance tables for some cases where the parameters get estimated from the data, but for our purposes we expect that we should know the parameters ahead of time, since what we're checking are usually values like packet sending times that we want to verify follow a known distribution 🌸
Both routines return a significance level, as described earlier. It's a value between 0 and 1 ✨ The correct way to use them is to pick your threshold for the significance level before you test anything. This is usually 0.05, aka 5%, same as we talked about above 💜 If the routine gives back a value strictly less than that threshold, then the data get declared inconsistent with the presumed distribution, subject to an error corresponding to the significance level. Translation: at a 5% significance level, 5% of the time, data that really did come from the presumed distribution will still get wrongly called inconsistent 😭
So, bestie, if you run these routines a lot, you're going to hit the occasional failure even when your data is perfectly clean 💀 Plan for it 🫶
Another big thing about significance levels: it's not sound to compare them to figure out which of two sets of values is the "better" fit for a presumed distribution 🙅♀️ If you want to do that kind of comparison, use "closeness-of-fit metrics" instead, like the lambda^2 metric described in [Pa94] 🔥
The routines here are for exponential and uniform distributions with known parameters, but it's generally straightforward to write similar routines for any distribution with known parameters 🌈 The heart of the A2 tests is a statistic computed to check whether a set of values is consistent with a uniform distribution between 0 and 1, which we call Unif(0, 1). So if we want to test whether a set of values, X, is consistent with some distribution G(x), we first compute:
Y = G_inverse(X)If X really is distributed according to G(x), then Y will be distributed according to Unif(0, 1). So by testing Y for consistency with Unif(0, 1), we also test X for consistency with G(x) ✨
Now, the process of computing Y might give you values outside the range (0..1). That shouldn't happen if X really follows G(x), but it can easily happen if it doesn't 👀 In that case we need to avoid computing the central A2 statistic, because floating-point exceptions may occur if any of the values fall outside (0..1). So the routines check for this, and if they find it, they return a raw A2 statistic of -1. The routine that turns the raw A2 statistic into a significance level passes that value along too, returning a significance level of -1. So any code that uses these routines has to be ready for a possibly negative significance level 🙃
Heads up: a significance level of -1 is a "bogus" result, not a real answer. Always check for it before comparing against your threshold.
The last important point is about n, the number of values being tested. If n < 5, the test isn't meaningful, so a significance level of -1 is returned 🙈
Here's the plot twist, though 🦋 For "real" data, the test gains power as n gets bigger. The statistics community knows that real data almost never matches a theoretical distribution exactly, even in cases like rolling dice a gazillion times (see [Pa94] for a brief discussion and references). The A2 test is sensitive enough that, with a big enough set of real data, it will almost always fail, because it'll catch tiny imperfections in how well the data fits the distribution 😭
For example, we found that when testing 8,192 measured wire times for packets sent at Poisson intervals, the measurements almost always failed the A2 test 💀 On the other hand, testing 128 measurements failed at 5% significance only about 5% of the time, which is exactly what we expected 🍓 So, in general, when the test fails, you have to take care and figure out why it failed 🧐
The rest of this appendix is the C code for the routines we mentioned above 💖
/* Routines for computing the Anderson-Darling A2 test statistic.
*
* Implemented based on the description in "Goodness-of-Fit
* Techniques," R. D'Agostino and M. Stephens, editors,
* Marcel Dekker, Inc., 1986.
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/* Returns the raw A^2 test statistic for n sorted samples
* z[0] .. z[n-1], for z ~ Unif(0,1).
*/
extern double compute_A2(double z[], int n);
/* Returns the significance level associated with a A^2 test
* statistic value of A2, assuming no parameters of the tested
* distribution were estimated from the data.
*/
extern double A2_significance(double A2);
/* Returns the A^2 significance level for testing n observations
* x[0] .. x[n-1] against an exponential distribution with the
* given mean.
*
* SIDE EFFECT: the x[0..n-1] are sorted upon return.
*/
extern double exp_A2_known_mean(double x[], int n, double mean);
/* Returns the A^2 significance level for testing n observations
* x[0] .. x[n-1] against the uniform distribution [min_val, max_val].
*
* SIDE EFFECT: the x[0..n-1] are sorted upon return.
*/
extern double unif_A2_known_range(double x[], int n,
double min_val, double max_val);
/* Returns a pseudo-random number distributed according to an
* exponential distribution with the given mean.
*/
extern double random_exponential(double mean);
/* Helper function used by qsort() to sort double-precision
* floating-point values.
*/
static int
compare_double(const void *v1, const void *v2)
{
double d1 = *(double *) v1;
double d2 = *(double *) v2;
if (d1 < d2)
return -1;
else if (d1 > d2)
return 1;
else
return 0;
}
double
compute_A2(double z[], int n)
{
int i;
double sum = 0.0;
if ( n < 5 )
/* Too few values. */
return -1.0;
/* If any of the values are outside the range (0, 1) then
* fail immediately (and avoid a possible floating point
* exception in the code below).
*/
for (i = 0; i < n; ++i)
if ( z[i] <= 0.0 || z[i] >= 1.0 )
return -1.0;
/* Page 101 of D'Agostino and Stephens. */
for (i = 1; i <= n; ++i) {
sum += (2 * i - 1) * log(z[i-1]);
sum += (2 * n + 1 - 2 * i) * log(1.0 - z[i-1]);
}
return -n - (1.0 / n) * sum;
}
double
A2_significance(double A2)
{
/* Page 105 of D'Agostino and Stephens. */
if (A2 < 0.0)
return A2; /* Bogus A2 value - propagate it. */
/* Check for possibly doctored values. */
if (A2 <= 0.201)
return 0.99;
else if (A2 <= 0.240)
return 0.975;
else if (A2 <= 0.283)
return 0.95;
else if (A2 <= 0.346)
return 0.90;
else if (A2 <= 0.399)
return 0.85;
/* Now check for possible inconsistency. */
if (A2 <= 1.248)
return 0.25;
else if (A2 <= 1.610)
return 0.15;
else if (A2 <= 1.933)
return 0.10;
else if (A2 <= 2.492)
return 0.05;
else if (A2 <= 3.070)
return 0.025;
else if (A2 <= 3.880)
return 0.01;
else if (A2 <= 4.500)
return 0.005;
else if (A2 <= 6.000)
return 0.001;
else
return 0.0;
}
double
exp_A2_known_mean(double x[], int n, double mean)
{
int i;
double A2;
/* Sort the first n values. */
qsort(x, n, sizeof(x[0]), compare_double);
/* Assuming they match an exponential distribution, transform
* them to Unif(0,1).
*/
for (i = 0; i < n; ++i) {
x[i] = 1.0 - exp(-x[i] / mean);
}
/* Now make the A^2 test to see if they're truly uniform. */
A2 = compute_A2(x, n);
return A2_significance(A2);
}
double
unif_A2_known_range(double x[], int n, double min_val, double max_val)
{
int i;
double A2;
double range = max_val - min_val;
/* Sort the first n values. */
qsort(x, n, sizeof(x[0]), compare_double);
/* Transform Unif(min_val, max_val) to Unif(0,1). */
for (i = 0; i < n; ++i)
x[i] = (x[i] - min_val) / range;
/* Now make the A^2 test to see if they're truly uniform. */
A2 = compute_A2(x, n);
return A2_significance(A2);
}
double
random_exponential(double mean)
{
return -mean * log1p(-drand48());
}19. References 📚
[AK97] G. Almes and S. Kalidindi, "A One-way Delay Metric for IPPM", Work in Progress, November 1997.
[BM92] I. Bilinskis and A. Mikelsons, Randomized Signal Processing, Prentice Hall International, 1992.
[DS86] R. D'Agostino and M. Stephens, editors, Goodness-of-Fit Techniques, Marcel Dekker, Inc., 1986.
[CPB93] K. Claffy, G. Polyzos, and H-W. Braun, "Application of Sampling Methodologies to Network Traffic Characterization," Proc. SIGCOMM '93, pp. 194-203, San Francisco, September 1993.
[FJ94] S. Floyd and V. Jacobson, "The Synchronization of Periodic Routing Messages," IEEE/ACM Transactions on Networking, 2(2), pp. 122-136, April 1994.
[Mi92] Mills, D., "Network Time Protocol (Version 3) Specification, Implementation and Analysis", RFC 1305, March 1992.
[Pa94] V. Paxson, "Empirically-Derived Analytic Models of Wide-Area TCP Connections," IEEE/ACM Transactions on Networking, 2(4), pp. 316-336, August 1994.
[Pa96] V. Paxson, "Towards a Framework for Defining Internet Performance Metrics," Proceedings of INET '96, ftp://ftp.ee.lbl.gov/papers/metrics-framework-INET96.ps.Z
[Pa97] V. Paxson, "Measurements and Analysis of End-to-End Internet Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997, ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz.
20. Authors' Addresses 💌
okay bestie, here are the four amazing humans who wrote this, with all their contact info so you can slide into their inbox 🦋
Vern Paxson
MS 50B/2239
Lawrence Berkeley National Laboratory
University of California
Berkeley, CA 94720
USA
Phone: +1 510/486-7504
EMail: vern@ee.lbl.gov
Guy Almes
Advanced Network & Services, Inc.
200 Business Park Drive
Armonk, NY 10504
USA
Phone: +1 914/765-1120
EMail: almes@advanced.org
Jamshid Mahdavi
Pittsburgh Supercomputing Center
4400 5th Avenue
Pittsburgh, PA 15213
USA
Phone: +1 412/268-6282
EMail: mahdavi@psc.edu
Matt Mathis
Pittsburgh Supercomputing Center
4400 5th Avenue
Pittsburgh, PA 15213
USA
Phone: +1 412/268-3319
EMail: mathis@psc.edu21. Full Copyright Statement 🌸
okay so this is the legal part, but it's still important 💅 the wording stays exactly as written so nobody gets confused about what's allowed
Copyright (C) The Internet Society (1998). All Rights Reserved.
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
📦 where this page comes from
- ietf: rfc2330 1998-05
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms