--- 1/draft-ietf-ippm-reordering-09.txt 2006-02-04 23:46:20.000000000 +0100 +++ 2/draft-ietf-ippm-reordering-10.txt 2006-02-04 23:46:20.000000000 +0100 @@ -1,29 +1,31 @@ Network Working Group A.Morton Internet Draft L.Ciavattone -Document: G.Ramachandran +Document: G.Ramachandran Category: Standards Track AT&T Labs S.Shalunov Internet2 J.Perser Consultant Packet Reordering Metric for IPPM Status of this Memo + By submitting this Internet-Draft, each author represents that any + applicable patent or other IPR claims of which he or she is aware + have been or will be disclosed, and any of which he or she becomes + aware will be disclosed, in accordance with Section 6 of BCP 79. + This document is an Internet-Draft and is subject to all provisions - of section 3 of RFC 3667. By submitting this Internet-Draft, each - author represents that any applicable patent or other IPR claims of - which he or she is aware have been disclosed, and any of which he or - she becomes aware will be disclosed, in accordance with RFC 3668. + of section 3 of BCP 78. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working 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." @@ -61,60 +63,60 @@ Abstract...........................................................1 1. Conventions used in this document...............................3 2. Introduction....................................................3 2.1 Motivation.....................................................4 2.2 Goals and Objectives...........................................5 3. A Reordered Packet Singleton Metric.............................6 3.1 Metric Name:...................................................7 3.2 Metric Parameters:.............................................7 3.3 Definition:....................................................7 3.4 Sequence Discontinuity Definition..............................8 - 3.5 Evaluation of Reordering in Dimensions of Time or Bytes........8 + 3.5 Evaluation of Reordering in Dimensions of Time or Bytes........9 3.6 Discussion.....................................................9 - 4. Sample Metrics..................................................9 + 4. Sample Metrics.................................................10 4.1 Reordered Packet Ratio........................................10 4.1.1 Metric Name:................................................10 4.1.2 Metric Parameters:..........................................10 4.1.3 Definition:.................................................10 - 4.1.4 Discussion..................................................10 + 4.1.4 Discussion..................................................11 4.2 Reordering Extent.............................................11 4.2.1 Metric Name:................................................11 4.2.2 Parameter Notation:.........................................11 - 4.2.3 Definition:.................................................11 + 4.2.3 Definition:.................................................12 4.2.4 Discussion:.................................................12 - 4.3 Reordering Late Time Offset...................................12 - 4.3.1 Metric Name:................................................12 + 4.3 Reordering Late Time Offset...................................13 + 4.3.1 Metric Name:................................................13 4.3.2 Metric Parameters:..........................................13 4.3.3 Definition:.................................................13 4.3.4 Discussion..................................................13 4.4 Reordering Byte Offset........................................14 4.4.1 Metric Name:................................................14 4.4.2 Metric Parameters:..........................................14 4.4.3 Definition:.................................................14 - 4.4.4 Discussion..................................................14 + 4.4.4 Discussion..................................................15 4.5 Gaps between multiple Reordering Discontinuities..............15 4.5.1 Metric Name:................................................15 4.5.2 Parameters:.................................................15 - 4.5.3 Definition of Reordering Discontinuity:.....................15 - 4.5.4 Definition of Reordering Gap:...............................15 + 4.5.3 Definition of Reordering Discontinuity:.....................16 + 4.5.4 Definition of Reordering Gap:...............................16 4.5.5 Discussion..................................................16 - 4.6 Reordering-free Runs..........................................16 - 4.6.1 Metric Name:................................................16 + 4.6 Reordering-free Runs..........................................17 + 4.6.1 Metric Name:................................................17 4.6.2 Parameters:.................................................17 4.6.3 Definition:.................................................17 4.6.4 Discussion:.................................................18 - 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..18 - 5.1 Metric Name:..................................................18 + 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..19 + 5.1 Metric Name:..................................................19 5.2 Parameter Notation:...........................................19 5.3 Definitions...................................................19 - 5.4 Discussion:...................................................19 - 6. Measurement and Implementation Issues..........................20 + 5.4 Discussion:...................................................20 + 6. Measurement and Implementation Issues..........................21 7. Examples of Arrival Order Evaluation...........................24 7.1 Example with a single packet reordered........................24 7.2 Example with two packets reordered............................25 7.3 Example with three packets reordered..........................27 7.4 Example with Multiple Packet Reordering Discontinuities.......28 8. Security Considerations........................................28 8.1 Denial of Service Attacks.....................................28 8.2 User data confidentiality.....................................29 8.3 Interference with the metric..................................29 9. IANA Considerations............................................29 @@ -230,21 +232,23 @@ 2.2 Goals and Objectives The definitions below intend to satisfy the goals of: 1. Determining whether or not packet reordering has occurred. 2. Quantifying the degree of reordering. (We define a number of metrics to meet this goal, because receiving procedures differ by protocol or application. Since the affects of packet reordering vary with these procedures, a metric that quantifies a key aspect of one receiver's behavior could be irrelevant to - a different receiver.) + a different receiver. If all the metrics defined below are + reported, they give a wide-ranging view of reordering + conditions.) Reordering Metrics MUST: + have one or more applications, such as receiver design or network characterization, and a compelling relevance in the working group's view. + be computable "on the fly" + work even if the stream has duplicate or lost packets It is desirable for Reordering Metrics to have one or more of the @@ -325,21 +330,22 @@ + Dst, the IP address of a host + SrcTime, the time of packet emission from the Source (or wire time) + s, the unique packet sequence number applied at the Source, in units of messages. + NextExp, the Next Expected Sequence number at the Destination, in - units of messages. + units of messages. The stored value in NextExp is determined from + a previously arriving packet. And optionally: + PayloadSize, the number of bytes contained in the information field and referred to when the SrcByte sequence is based on bytes transfered. + SrcByte, the packet sequence number applied at the Source, in units of payload bytes. @@ -347,21 +353,22 @@ If a packet s, (sent at time, SrcTime) is found to be reordered by comparison with the Next Expected value, its Type-P-Reordered = TRUE; otherwise Type-P-Reordered = FALSE, as defined below: The value of Type-P-Reordered is defined as TRUE if s < NextExp (the packet is reordered). In this case, the NextExp value does not change. The value of Type-P-Reordered is defined as FALSE if s >= NextExp - (the packet is in-order). In this case, NextExp is set to s+1. + (the packet is in-order). In this case, NextExp is set to s+1 for + comparison with the next packet to arrive. Since the Next Expected value cannot decrease, it provides a non- reversing order criterion to identify reordered packets. This definition can also be specified in pseudo-code. On successful arrival of a packet with sequence number s: if s >= NextExp then /* s is in-order */ NextExp = s + 1; Type-P-Reordered = False; @@ -563,46 +569,48 @@ packets, from a reordered packet to the earliest packet received that has a larger sequence number. If a packet is in-order, its reordering extent is undefined. The first packet to arrive is in- order by definition, and has undefined reordering extent. Comment on the definition of extent: For some arrival orders, the assignment of a simple position/distance as the reordering extent tends to overestimate the receiver storage needed to restore order. A more accurate and complex procedure to calculate packet storage would be to subtract any earlier reordered packets that the receiver - could pass on to the upper layers. With the bias understood, this - definition is deemed sufficient, especially for those who demand "on - the fly" calculations. + could pass on to the upper layers (see the Byte Offset metric). With + the bias understood, this definition is deemed sufficient, + especially for those who demand "on the fly" calculations. 4.2.4 Discussion: The packet with index j (s[j], identified in the Definition above) is the reordering discontinuity associated with packet s at index i (s[i]). This definition is formalized below. Note that the K packets in the stream could be some subset of a larger stream, but L is still the total number of packets received out of the K packets sent in that subset. If a receiver intends to restore order, then its buffer capacity determines its ability to handle packets that are reordered. For cases with single reordered packets, the extent e gives the number of packets that must be held in the receiver's buffer while waiting for the reordered packet to complete the sequence. For more complex scenarios, the extent may be an overestimate of required storage - (see the Examples section). + (see section 4.4 on Reordering Byte Offset and the Examples + section). - Knowledge of the reordering extent, e, is particularly useful for - determining the portion of reordered packets that can or cannot be - restored to order in a typical receiver buffer based on their - arrival order alone (and without the aid of retransmission). + Although reordering extent primarily quantifies the offset in terms + of arrival position, it may also be useful for determining the + portion of reordered packets that can or cannot be restored to order + in a typical receiver buffer based on their arrival order alone (and + without the aid of retransmission). A sample's reordering extents may be expressed as a histogram, to easily summarize the frequency of various extents. 4.3 Reordering Late Time Offset Reordered packets can be assigned offset values indicating their lateness in terms of buffer time that a receiver must possess to accommodate them. Offset metrics are calculated only on reordered packets, as identified by the reordered packet singleton metric in @@ -664,26 +672,32 @@ metric. If presented with the arrival sequence 1, 10, 5 (where packets 2, 3, 4, and 6 through 9 are lost), LateTime would not indicate exactly how "late" packet 5 is from its intended arrival position. IPDV [RFC3393] would not capture this either, because of the lack of adjacent packet pairs. Assuming a Periodic Stream [RFC3432], an expected arrival time could be defined for all packets, but this is essentially a single-point delay variation metric (as defined in ITU-T Recommendations [I.356] and [Y.1540]), and not a reordering metric. + A sample's LateTime results may be expressed as a histogram, to + summarize the frequency of buffer times needed to accommodate + reordered packets and permit buffer tuning on that basis. A CDF with + buffer time vs. percent of reordered packets accommodated may be + informative. + 4.4 Reordering Byte Offset Reordered packets can be assigned offset values indicating the storage in bytes that a receiver must possess to accommodate them. - The various offset metrics are calculated only on reordered packets, - as identified by the reordered packet singleton metric in Section 3. + Offset metrics are calculated only on reordered packets, as + identified by the reordered packet singleton metric in Section 3. 4.4.1 Metric Name: Type-P-packet-Byte-Offset-Stream 4.4.2 Metric Parameters: We use the same parameters defined earlier, including the optional parameters of SrcByte and PayloadSize, and define: @@ -718,20 +733,26 @@ packets and their size, especially when packet size is variable. In these and other circumstances, it may be most useful to characterize offset in terms of the payload size(s) of stored packets, using the Type-P-packet-Byte-Offset-Stream metric. The byte offset metric can help predict whether reordered packets will be useful in a general receiver buffer system with finite limits. The limit is expressed as the number of bytes the buffer can store. + A sample's ByteOffset results may be expressed as a histogram, to + summarize the frequency of buffer lengths needed to accommodate + reordered packets and permit buffer tuning on that basis. A CDF with + buffer size vs. percent of reordered packets accommodated may be + informative. + 4.5 Gaps between multiple Reordering Discontinuities 4.5.1 Metric Name: Type-P-packet-Reordering-Gap-Stream 4.5.2 Parameters: We use the same parameters defined earlier, but add the convention that index i' is greater than i, likewise j' > j, and define: @@ -1033,42 +1055,42 @@ Test stream designers may prefer to use a periodic sending interval so that a known temporal bias is maintained, also bringing simplified results analysis (as described in [RFC3432]). In this case, it is RECOMMENDED that the periodic sending interval should be chosen to reproduce the closest Source packet spacing expected. Testers must recognize that streams sent at the link speed serialization limit MUST have limited duration and MUST consider packet loss as an indication that the stream has caused congestion, and suspend further testing. - When intending to compare or concatenate independent measurements of - reordering, it is RECOMMENDED to use the same test stream parameters - in each measurement system. + When intending to compare independent measurements of reordering, it + is RECOMMENDED to use the same test stream parameters in each + measurement system. Packet lengths might also be varied to attempt to detect instances of parallel processing (they may cause steady state reordering). For example, a line-speed burst of the longest (MTU-length) packets followed by a burst of the shortest possible packets may be an effective detecting pattern. Other size patterns are possible. The non-reversing order criterion and all metrics described above remain valid and useful when a stream of packets experiences packet loss, or both loss and reordering. In other words, losses alone do not cause subsequent packets to be declared reordered. Assuming that the necessary sequence information (message number) is included in the packet payload (possibly in application headers such as RTP), reordering metrics may be evaluated in a passive measurement arrangement. Also, it is possible to evaluate order at any point along a Source-Destination path, recognizing that intermediate measurements may differ from those made at the - Destination (where reordering's affect on applications can be + Destination (where the reordering affect on applications can be inferred). It is possible to apply these metrics to evaluate reordering in a TCP sender's stream. In this case, the Source sequence numbers would be based on byte stream, or segment numbering. Since the stream may include retransmissions due to loss or reordering, care must be taken to avoid declaring retransmitted packets reordered. The additional sequence reference of s or SrcTime helps to avoid this ambiguity, or the optional TCP timestamp field [RFC1323]. @@ -1092,21 +1114,21 @@ 2. All sequence numbers used in computations are represented in a sufficiently large precision. The numbers have a correction applied (equivalent to adding a significant digit) whenever roll-over is detected. 3. Reordered packets coincident with sequence numbers reaching end- of-range must also be detected for proper application of correction factor. Ideally, the test instrument would have the ability to use all - earlier packets at any point in the test stream. In practice, there + earlier packets at any point in the test stream. In practice there will be limited ability to determine reordering extent, due to the storage requirements for previous packets. Saving only packets that indicate discontinuities (and their arrival positions) will reduce storage volume. Another solution is to use a sliding history window of packets, where the window size would be determined by an upper bound on the useful reordering extent. This bound could be several packets or several seconds-worth of packets, depending on the intended analysis. When discarding all stream information beyond the window, @@ -1116,20 +1138,27 @@ would not be possible. The requirement to ignore duplicate packets also mandates storage. Here, tracking the sequence numbers of missing packets may minimize storage size. Missing packets may eventually be declared lost, or reordered if they arrive. The missing packet list and the largest sequence number received thus far (NextExp - 1) are sufficient information to determine if a packet is a duplicate (assuming a manageable storage size for packets that are missing due to loss). + It is important to note that practical IP networks also have limited + ability to "store" packets, even when routing loops appear + temporarily. Therefore, the storage for reordering metrics (and + their complexity) would only approach the number packets in the + sample, K, when the sending time for K packets is small with respect + to the network's largest possible transfer time. + Last, we note that determining reordering extents and gaps is tricky when there are overlapped or nested events. Test instrument complexity and reordering complexity are directly correlated. 7. Examples of Arrival Order Evaluation This section provides some examples to illustrate how the non- reversing order criterion works, how n-reordering works in comparison, and the value of quantifying reordering in all the dimensions of time, bytes, and position. @@ -1137,22 +1166,22 @@ Throughout this section, we will refer to packets by their source sequence number, except where noted. So "Packet 4" refers to the packet with source sequence number 4, and the reader should refer to the tables in each example to determine packet 4's arrival index number, if needed. 7.1 Example with a single packet reordered Table 1 gives a simple case of reordering, where one packet is reordered, Packet 4. Packets are listed according to their arrival, - and message numbering is used. All packets contain 100 bytes, - beginning with s=1 and (s x 100)-99 for s=2,3,4,... + and message numbering is used. All packets contain PayloadSize=100 + bytes, with SrcByte=(s x 100)-99 for s=1,2,3,4,... Table 1 Example with Packet 4 Reordered, Sending order(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10 s Src Dst Dst Byte Late @Dst NextExp Time Time Delay IPDV Order Offset Time 1 1 0 68 68 1 2 2 20 88 68 0 2 3 3 40 108 68 0 3 5 4 80 148 68 -82 4 6 6 100 168 68 0 5 @@ -1487,25 +1516,26 @@ 3393, November 2002. [Y.1540] ITU-T Recommendation Y.1540, "Internet protocol data communication service - IP packet transfer and availability performance parameters", December 2002. 12. Acknowledgments The authors would like to acknowledge many helpful discussions with Matt Zekauskas, Jon Bennett (who authored the sections on Reordering-Free Runs), and Matt Mathis. We thank David Newman, Henk - Uijterwall, Mark Allman, Vern Paxson, and Phil Chimento for their + Uijterwaal, Mark Allman, Vern Paxson, and Phil Chimento for their reviews and suggestions, and Michal Przybylski for sharing - implementation experiences with us on the ippm-list. We gratefully - acknowledge the foundation laid by the authors of the IP performance - Framework [RFC2330]. + implementation experiences with us on the ippm-list. Anura + Jayasumana and Nischal Piratla brought in recent work-in-progress. + We gratefully acknowledge the foundation laid by the authors of the + IP performance Framework [RFC2330]. 13. Appendix A Example Implementations in C (Informative) Two example c-code implementations of reordering definitions follow: Example 1 n-reordering ============================================ #include #define MAXN 100 @@ -1784,23 +1812,25 @@ EMail: Jerry Perser Consultant Calabasas, CA 91302 USA Phone: + 1 EMail: Full Copyright Statement - Copyright (C) The Internet Society (2005). This document is subject - to the rights, licenses and restrictions contained in BCP 78 and - except as set forth therein, the authors retain all their rights. + Copyright (C) The Internet Society (2005). + + This document is subject to the rights, licenses and restrictions + contained in BCP 78, and except as set forth therein, the authors + retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property