IP Performance Metrics Working Group S. Ono, T. Miyata, H. Fukuda Internet Draft NTT Expiration Date: February 1999 Aug 1998 Loss Metrics of Grouped Packets for IPPM 1. Status of this Memo This document is an Internet Draft. Internet Drafts are working doc- uments of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute work- ing documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months, and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet Drafts as reference material or to cite them other than as ``work in progress''. To learn the current status of any Internet Draft, please check the ``1id-abstracts.txt'' listing contained in the Internet Drafts shadow directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). This memo provides information for the Internet community. This memo does not specify an Internet standard of any kind. Distribution of this memo is unlimited. 2. Introduction This memo defines several metrics for loss of grouped packets across Internet paths. It builds on notions introduced and discussed in the IPPM Framework document (currently ''Framework for IP Performance Metrics'' ); the reader is assumed to be familiar with that document. In addition, this memo is intended to be a generalization of the document for Packet Loss [1] and to be very parallel in structure to that document; the reader is also assumed to be familiar with that document. The structure of the memo is as follows: + A 'singleton' analytic metric, called Type-P-One-way-Grouped- Packets-Loss-Pattern, will be introduced to measure a single observation, which is comprised of multiple related packet transmissions, each of the transmissions may be successful or loss. (Section 3.1) + A 'singleton' analytic metric, called Type-P-One-way-Grouped- Packets-LossTh, will be introduced to measure a single observation, which can be derived from the metric Type-P-One-way-Grouped- Packets-Loss-Pattern. This metric is generalization of Type-P- One-way-Packet-Loss to a packet group such that a packet group is said to be 'lost' when s or more out of w packets in the group are lost, where w (0 < w) is a loss-window size, and s (0 < s <= w) is a loss threshold count. When both w and s are set to 1, it is the same as the conventional metric Type-P-One-way-Packet-Loss. (Section 3.2) + A 'singleton' analytic metric, called Type-P-One-way-Grouped- Packets-Loss, will be introduced to measure a single observation, which is the specialization of Type-P-One-way-Grouped-Packets- LossTh, such that the threshold value s is fixed to 1. Namely, a packet group is said to be lost only when all of w packets in the group are lost, where w (0 < w) is a loss-window size. Naturally, when w is also set to 1, it is the same as Type-P-One-way-Packet-Loss. (Section 3.3) + Using the singleton metric Type-P-One-way-Grouped-Packets- Loss-Pattern, a 'sample', called Type-P-One-way-Grouped-Packets- Loss-Pattern-Stream, will be introduced to measure a sequence of singleton loss patterns of grouped packets, where each measurement is started at times taken from a Poisson process. (Section 4.1) + Using the singleton metric Type-P-One-way-Grouped-Packets-LossTh, a 'sample', called Type-P-One-way-Grouped-Packets-LossTh-Stream, will be introduced to measure a sequence of singleton losses of grouped packets, where each measurement is started at times taken from a Poisson process. (Section 4.2) + Using the singleton metric Type-P-One-way-Grouped-Packets-Loss, a 'sample', called Type-P-One-way-Grouped-Packets-Loss-Stream, will be introduced to measure a sequence of singleton losses of grouped packets, where each measurement is started at times taken from a Poisson process. (Section 4.3) + The relationships among these metrics are discussed. (Section 5) + Using these samples, several 'statistics' of the samples will be defined and discussed. (Section 6) These progressions from singletons to samples to statistics, with clear separation among them, are important. Whenever a technical term from the IPPM Framework document is first used in this memo, it will be tagged with a trailing asterisk, as with >>term*<<. 2.1. Motivation: The work-in-progress document [2] defines the notion of one-way packet loss of type-P packets transmitted from a source host* to a destination host. In that document, the unit of measurement is a packet. The main purpose of this document is to generalize it to a packet group, i.e. a sequence of multiple related packets. Such Generalization is useful for several reasons: + When successive packets are injected at short intervals, the loss probability of each packet may NOT be independent [3]; For example, the loss probability of the next packet may become lower, if the preceding packet has been lost. Metrics using only one packet transmission for each sample cannot detect this kind of conditional loss probability. + The stream-oriented applications which handle audio and/or video are likely to inject packets at short intervals. + There exist applications that use FEC (forward error control/ correction) technology. Typical FEC usage on packet networks is as follows. Application data are scattered among w different packets with redundancy so that the application data can be recovered if only s (0 < s < w) or more packets out of the w packets are successfully received. In such recovered cases, losses of packets are invisible to the application. + Some applications take advantage of both FEC and hierarchical coding. For example, low-quality audio data may be protected more thoroughly than high-quality audio, such that the low-quality data can be retrieved even if only one packet in a group is received. In such a case, the application may provide degraded service to a user due to a heavily lossy network. It is outside the scope of this document to define precisely how packet group loss metrics would be applied to specific problems. 2.2. General Issues Regarding Time Whenever a time (i.e., a moment in history) is mentioned here, it is understood to be measured in seconds (and fractions) relative to UTC. Similar discussions are applicable as described in Section 2.2 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). 3. Singleton Definitions for One-way Losses of Grouped Packets 3.1. A Singleton Definition for One-way Loss Pattern of Grouped Packets 3.1.1. Metric Name: Type-P-One-way-Grouped-Packets-Loss-Pattern 3.1.2. Metric Parameters: + Src, the IP address of a host + Dst, the IP address of a host + T, a time + n, a group size (GS) (positive integer number) + TS, a monotonic sequence of times with length n, where t1 should be always equal to T. + Path, the path* from Src to Dst; in cases where there is only one path from Src to Dst, this optional parameter can be omitted. {Comment: For the discussion on path, please refer to Section 3.2 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). 3.1.3. Metric Units: The value of a Type-P-One-way-Grouped-Packets-Loss-Pattern is a sequence of n (i.e. the group size) values, each of which is either a zero (signifying successful transmission of the packet) or a one (signifying loss). 3.1.4. Definition: >>The *Type-P-One-way-Grouped-Packets-Loss-Pattern* from Src to Dst at for GS n (1 <= n) [via path] is << means that for each i (1 <= i <= n), Src sent the first bit of the i-th type-P packet [via path] to Dst at wire-time ti, and that Dst received that packet correctly if Li is 0, and did not if Li is 1, respectively. 3.1.5. Discussion: It is a rather straight forward extension of Type-P-One-way-Packet-Loss, such that grouped n packets are sent in sequence, and the loss is recorded packet-wise. As can be easily seen, when the group size n is set to 1, the Type-P- One-way-Grouped-Packets-Loss-Pattern is the same as Type-P-One-way-Packet- Loss. + Although no assumption is made for t1, ..., tn, the following are a partial list of possible alternatives. Stream type: Take ti such that ti = t1 + delta * (i - 1) where delta is a constant packet interval. Random type: ti is taken from a Poisson process. Burst type: Take ti as close as possible to the preceding packet. + Similar discussions are applicable as described in Section 3.5 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). 3.1.6. Methodologies: Similar discussions are applicable as described in Section 3.6 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). 3.1.7. Errors and Uncertainties: Similar discussions are applicable as described in Section 3.7 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). 3.2. A Singleton Definition for Window-based One-way Loss of Grouped Packets where Loss is Defined using Thresholds 3.2.1. Metric Name: Type-P-One-way-Grouped-Packets-LossTh 3.2.2. Metric Parameters: + Src, the IP address of a host + Dst, the IP address of a host + T, a time + n, a group size (GS) (positive integer number) + TS, a monotonic sequence of times with length n, where t1 should be always equal to T + w, a loss window size (LWS) (positive integer number, and w <= n) + s, a loss threshold count (LTC) (positive integer number and s <= w) + Path, the path from Src to Dst; in cases where there is only one path from Src to Dst, this optional parameter can be omitted. 3.2.3. Metric Units: The value of a type-P-One-way-Grouped-Packets-LossTh is either a zero (signifying that at least s packets out of w packets have been successfully transmitted) or a one (signifying that less than s packets out of w packets have been successfully transmitted, or all of the w packets have been lost). 3.2.4. Definition: >>The *Type-P-One-way-Grouped-Packets-LossTh* from Src to Dst at for GS n (1 <= n), LWS w (1 <= w <= n), and LTC s (1 <= s <= w) [via path] is 0 << means that for each i (1 <= i <= n), Src sent the first bit of the i-th type-P packet Pi [via path] to Dst at wire-time ti, and that Dst received at least s packets among packets {P1, P2, ..., Pw}. >>The *Type-P-One-way-Grouped-Packets-LossTh* from Src to Dst at for GS n (1 <= n), LWS w (1 <= w <= n), and LTC s (1 <= s <= w) [via path] is 1 << means that for each i (1 <= i <= n), Src sent the first bit of the i-th type-P packet Pi [via path] to Dst at wire-time ti, and that Dst received less than s or none of the packets {P1, P2, ..., Pw}. 3.2.5. Discussion: This metric can be naturally derived from the Type-P-One-way-Grouped- Packets-Loss-Pattern. Assume a sample of Type-P-One-way-Grouped-Packets-Loss-Pattern of GS n (1 <= n) be < , >. Then, Type-P-One-way-Grouped-Packets-LossTh of LWS w (1 <= w <= n) and LTC s (1 <= s <= w) be < , 0 > if ((L1 + L2 + ... + Lw) <= w - s), and < , 1 > if ((L1 + L2 + ... + Lw) > w - s). When w < n, if we ignore the effect of packets Pw+1, ..., Pn to L1, ..., Lw, we can assume the group size to be equal to w. 3.2.6. Methodologies: See Section 3.1.6 of this document. 3.2.7. Errors and Uncertainties: See Section 3.1.7 of this document. 3.3. A Singleton Definition for Window-based One-way Loss of Grouped Packets 3.3.1. Metric Name: Type-P-One-way-Grouped-Packets-Loss 3.3.2. Metric Parameters: + Src, the IP address of a host + Dst, the IP address of a host + T, a time + n, a group size (GS) (positive integer number) + TS, a monotonic sequence of times with length n, where t1 should be always equals to T + Path, the path from Src to Dst; in cases where there is only one path from Src to Dst, this optional parameter can be omitted. + w, a loss window size (LWS) (positive integer number, and w <= n) 3.3.3. Metric Units: The value of a type-P-One-way-Grouped-Packets-Loss is either a zero (signifying that at least one packet out of w packets has been successfully transmitted) or a one (signifying that none of w packets has been successfully transmitted. 3.3.4. Definition: >>The *Type-P-One-way-Grouped-Packets-Loss* from Src to Dst at for GS n (1 <= n), LWS w (1 <= w <= n) [via path] is 0 << means that for each i (1 <= i <= n), Src sent the first bit of the i-th type-P packet Pi [via path] to Dst at wire-time ti, and that Dst received at least one of the packets {P1, P2, ..., Pw}. >>The *Type-P-One-way-Grouped-Packets-Loss* from Src to Dst at for GS n (1 <= n), LWS w (1 <= w <= n) [via path] is 1 << means that for each i (1 <= i <= n), Src sent the first bit of the i-th type-P packet Pi [via path] to Dst at wire-time ti, and that Dst received none of the packets {P1, P2, ..., Pw}. 3.3.5. Discussion: This metric is specialization of Type-P-One-way-Grouped-Packets-LossTh, such that LTC is always fixed to 1. In case w < n, if we ignore the effect of packets Pw+1, ..., Pn to L1, ..., Lw, we can assume the group size be equal to w. 3.3.6. Methodologies: See Section 3.1.6 of this document. 3.3.7. Errors and Uncertainties: See Section 3.1.7 of this document. 4. Definitions for Samples of One-way Losses of Grouped Packets Given the above-defined singleton metrics, namely (1) Type-P-One-way-Grouped-Packets-Loss-Pattern, (2) Type-P-One-way-Grouped-Packets-LossTh and (3) Type-P-One-way-Grouped-Packets-Loss, we now define one particular sample of such singletons. The idea of the sample is to select a particular binding of the parameters Src, Dst, path, Type-P, GS n, LWS w (for metrics (2) and (3)) and LTC s (for the metric (2)), define a sample of values of parameter T. The way to define the values of T is to select a beginning time T0, a final time Tf, and an average rate lambda, then define a pseudo-random Poisson arrival process of rate lambda, whose values fall between T0 and Tf. The time interval between successive values of T will then average 1/lambda. 4.1 A Definition for Samples of One-way Loss Pattern of Grouped Packets 4.1.1. Metric Name: Type-P-One-way-Grouped-Packets-Loss-Pattern-Stream 4.1.2. Metric Parameters: + Src, the IP address of a host + Dst, the IP address of a host + Path, the path from Src to Dst; in cases where there is only one path from Src to Dst, this optional parameter can be omitted + n, a group size (GS) (positive integer number) + T0, a time + Tf, a time + lambda, a rate in reciprocal seconds + Tseq, a (possibly non-deterministic) mapping from a time to a monotonic sequence of times of length n. The first member of the resulting sequence is always the same as the input parameter. 4.1.3. Metric Units: A sequence of triplets; the elements of each triplets are: + T, a time, + TS, a monotonic sequence of times with length n, a valid instance of Tseq(T), + LS, a sequence of values with length n, each of which is either a zero or a one.The values of T in the sequence increase monotonically. Note that T and TS would be valid parameters for the Type-P-One-way-Grouped-Packets-Loss-Pattern, and that LS would be a valid value of the Type-P-One-way-Grouped-Packets-Loss-Pattern. 4.1.4. Definition: Given T0, Tf, and lambda, we compute a pseudo-random Poisson process beginning at or before T0, with an average arrival rate lambda, and end- ing at or after Tf. Those time values greater than or equal to T0 and less than or equal to Tf are then selected. At each time T of the times in this process, we compute a time sequence TS = Tseq(T), and obtain the value of the Type-P-One-way-Grouped-Packets-Loss-Pattern using this time sequence. The value of the sample is the sequence made up of the resulting triplets. If there are no such triplets, the sequence is of length zero and the sample is said to be empty. 4.1.5. Discussion: Similar discussions are applicable as described in Section 4.5 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). 4.1.6. Methodologies: Similar discussions are applicable as described in Section 4.6 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). 4.1.7. Errors and Uncertainties: Similar discussions are applicable as described in Section 4.7 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). Note also that errors could be caused by the algorithm of Tseq, and inaccuracy in the wire-time of the sending of the grouped packets. 4.2. A Definition for Samples of Window-based One-way Loss of Grouped Packets where Loss is Defined using Thresholds 4.2.1. Metric Name: Type-P-One-way-Grouped-Packets-LossTh-Stream 4.2.2. Metric Parameters: + Src, the IP address of a host + Dst, the IP address of a host + Path, the path from Src to Dst; in cases where there is only one path from Src to Dst, this optional parameter can be omitted + n, a group size (GS) (positive integer number) + T0, a time + Tf, a time + lambda, a rate in reciprocal seconds + Tseq, a (possibly non-deterministic) mapping from a time to a monotonic sequence of times of length n. The first member of the resulting sequence is always same as the input parameter. + w, a loss window size (LWS) (positive integer number, and w <= n) + s, a loss threshold count (LTC) (positive integer number and s <= w) 4.2.3. Metric Units: A sequence of triplets; the elements of each triplets are: + T, a time, + TS, a monotonic sequence of times with length n, a valid instance of Tseq(T), + L, either a zero or a one The values of T in the sequence increase monotonically. Note that T and TS would be valid parameters for Type-P-One-way-Grouped-Packets- LossTh, and that L would be a valid value of Type-P-One-way- Grouped-Packets-LossTh. 4.2.4. Definition: Given T0, Tf, and lambda, we compute a pseudo-random Poisson process beginning at or before T0, with an average arrival rate lambda, and end- ing at or after Tf. Those time values greater than or equal to T0 and less than or equal to Tf are then selected. At each time T of the times in this process, we compute a time sequence TS = Tseq(T), and obtain the value of Type-P-One-way-Grouped-Packets-LossTh using this time sequence. The value of the sample is the sequence made up of the resulting triplets. If there are no such triplets, the sequence is of length zero and the sample is said to be empty. 4.2.5. Discussion: Similar discussions are applicable as described in Section 4.5 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). 4.2.6. Methodologies: Similar discussions are applicable as described in Section 4.6 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). 4.2.7. Errors and Uncertainties: Similar discussions are applicable as described in Section 4.7 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). Note also that errors could be caused by the algorithm of Tseq, and inaccuracy in the wire-time of the sending of the grouped packets. 4.3. A Definition for Samples of Window-based One-way Loss of Grouped Packets 4.3.1. Metric Name: Type-P-One-way-Grouped-Packets-Loss-Stream 4.3.2. Metric Parameters: + Src, the IP address of a host + Dst, the IP address of a host + Path, the path from Src to Dst; in cases where there is only one path from Src to Dst, this optional parameter can be omitted + n, a group size (GS) (positive integer number) + T0, a time + Tf, a time + lambda, a rate in reciprocal seconds + Tseq, a (possibly non-deterministic) mapping from a time to a monotonic sequence of times of length n. The first member of the resulting sequence is always same as the input parameter. + w, a loss window size (LWS) (positive integer number, and w <= n) 4.3.3. Metric Units: A sequence of triplets; the elements of each triplets are: + T, a time, + TS, a monotonic sequence of times with length n, a valid instance of Tseq(T), + L, either a zero or a one The values of T in the sequence increase monotonically. Note that T and TS would be valid parameters for Type-P-One-way-Grouped-Packets- Loss, and that L would be a valid value of Type-P-One-way-Grouped- Packets-Loss. 4.3.4. Definition: Given T0, Tf, and lambda, we compute a pseudo-random Poisson process beginning at or before T0, with an average arrival rate lambda, and end- ing at or after Tf. Those time values greater than or equal to T0 and less than or equal to Tf are then selected. At each time T of the times in this process, we compute a time sequence TS = Tseq(T), and obtain the value of Type-P-One-way-Grouped-Packets-Loss using this time sequence. The value of the sample is the sequence made up of the resulting triplets. If there are no such triplets, the sequence is of length zero and the sample is said to be empty. 4.3.5. Discussion: Similar discussions are applicable as described in Section 4.5 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). 4.3.6. Methodologies: Similar discussions are applicable as described in Section 4.6 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). 4.3.7. Errors and Uncertainties: Similar discussions are applicable as described in Section 4.7 of the document for Packet Loss (''A Packet Loss Metric for IPPM'' ). Note also that errors could be caused by the algorithm of Tseq, and inaccuracy in the wire-time of the sending of the grouped packets. 5. Metrics Conversion Examples for One-way Loss of Grouped Packets Among the three metrics defined in Section 3, the first one, i.e. Type-P-One-way-Grouped-Packets-Loss-Pattern, is the most general, and the other two can be computed from it. We will demonstrate this using examples. Suppose that a sample of Type-P-One-way-Grouped-Packets-Loss-Pattern -Stream (group size 3) be as follows: Stream1 = < < t11, , <1, 0, 1> > < t21, , <0, 0, 0> > < t31, , <1, 1, 1> > < t41, , <1, 1, 0> > < t51, , <0, 1, 0> > < t61, , <1, 0, 0> > > From this sample, Type-P-One-way-Grouped-Packets-LossTh-Streams with various loss window sizes and loss threshold counts can be computed as follows: (Comments are added for readers' convenience. A comment starts with a mark '//' and ends at the end of the line.) (1) < // Threshold is 2. < t11, , 1 > // <1,0,1> Only 1 packet arrived. < t21, , 0 > // <0,0,0> 3 packets arrived. < t31, , 1 > // <1,1,1> No packets arrived. < t41, , 1 > // <1,1,0> Only 1 packet arrived. < t51, , 0 > // <0,1,0> 2 packets arrived. < t61, , 0 > // <1,0,0> 2 packets arrived. > (2) < // Threshold is 1. < t11, , 0 > < t21, , 0 > < t31, , 1 > // <1,1,1> No packets arrived. < t41, , 0 > < t51, , 0 > < t61, , 0 > > (3) < // Loss window size is 2. < t11, , 0 > // <1,0> One packet arrived. < t21, , 0 > // <0,0> All packets arrived. < t31, , 1 > // <1,1> No packets arrived. < t41, , 1 > // <1,1> No packets arrived. < t51, , 0 > // <0,1> One packet arrived. < t61, , 0 > // <1,0> One packet arrived. > (We set the group size to be LWS. See Section 3.2.5.) (4) < // Loss window size is 1. < t11, , 1 > // <1> Lost. < t21, , 0 > // <0> Arrived. < t31, , 1 > // <1> Lost. < t41, , 1 > // <1> Lost. < t51, , 0 > // <0> Arrived. < t61, , 1 > // <1> Lost. > (We set the group size to be LWS. See Section 3.2.5.) 6. Some Statistics Definitions for One-way Loss of Grouped Packets Given sample metrics such as Type-P-One-way-Grouped-Packets-Loss- Pattern defined in Section 4 above, we now offer several statistics of that sample. These statistics are offered mostly to be illustrative of what could be done. 6.1. Type-P-One-way-Grouped-Packets-LossTh-Average Given a Type-P-One-way-Grouped-Packets-LossTh-Stream, the average of all the L values in the Stream. In addition, the Type-P-One-way- Grouped-Packets-LossTh-Average is undefined if the sample is empty. Example: Suppose we take a sample and the results are: Stream2 = < < t11, , 1 > < t21, , 0 > < t31, , 1 > < t41, , 1 > < t51, , 0 > < t61, , 0 > > Then the average would be 0.5. 7. Security Considerations This memo raises no security issues. 8. Acknowledgments The authors are indebted to Jean-Chrysostome Bolot and Sacha Fosse-Parisis of the Rodeo Project at inria for their valuable discussions regarding this draft. in addition, we are grateful to guy almes and sunil kalidindi for their valuable internet drafts on metrics. Thanks are also due to Haruhisa Ichikawa of NTT Sofware Laboratories for his helpful comments. 9. References [1] G. Almes and S. Kalidindi, "A One-way Loss Metric for IPPM", Inter- net Draft , November 1997. [2] V. Paxson, G. Almes, J. Mahdavi, and M. Mathis, "Framework for IP Performance Metrics", Internet Draft , November 1997. [3] T. Miyata, H. Fukuda, S. Ono, "New network QoS measures for FEC-based audio application over the Internet", IEEE IPCCC'98, pp. 355 - 362, February 1998. 10. Authors' Addresses Satoshi Ono NTT Software Laboratories 3-9-11, Midori-cho, Musashino-Shi, Tokyo, 180-8585 JAPAN Phone: +81 422/59-3542 Teruko Miyata NTT Software Laboratories 3-9-11, Midori-cho, Musashino-Shi, Tokyo, 180-8585 JAPAN Phone: +81 422/59-2927 Harumoto Fukuda NTT Software Laboratories 3-9-11, Midori-cho, Musashino-Shi, Tokyo, 180-8585 JAPAN Phone: +81 422/59-2882