| < 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/ | ||||