Network Working GroupA.Morton Internet Draft L.Ciavattone Document: <draft-ietf-ippm-reordering-13.txt> G.RamachandranA. Morton Request for Comments: 4737 L. Ciavattone Category: Standards Track G. Ramachandran AT&T LabsS.ShalunovS. Shalunov Internet2J.PerserJ. Perser Veriwave November 2006 Packet ReorderingMetric for IPPMMetrics Status ofthisThis MemoBy 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 documentisspecifies anInternet-Draft and is subject to all provisions of section 3 of BCP 78. Internet-Drafts are working documents ofInternet standards track protocol for the InternetEngineering Task Force (IETF), its areas,community, andits working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents validrequests discussion and suggestions fora maximumimprovements. Please refer to the current edition ofsix monthsthe "Internet Official Protocol Standards" (STD 1) for the standardization state andmay 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." The liststatus ofcurrent Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The listthis protocol. Distribution ofInternet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html.this memo is unlimited. Copyright Notice Copyright (C) TheInternet SocietyIETF Trust (2006). Abstract This memo defines metrics to evaluateifwhether a network has maintained packet order on a packet-by-packet basis. It provides motivations for the new metrics and discusses the measurement issues, including the context information required for all metrics. The memo first defines a reordered singleton, and then uses it as the basis for sample metrics to quantify the extent of reordering in several useful dimensions for network characterization or receiver design. Additional metrics quantify the frequency of reordering and the distance between separate occurrences. We then define a metric oriented towardassessingassessment of reordering effects on TCP. Several examples of evaluation using the various sample metrics are included. AnAppendixappendix gives extended definitions for evaluating order with packet fragmentation.Contents StatusTable ofthis Memo................................................1 Copyright Notice...................................................1 Abstract...........................................................1Contents 1.Conventions Used in this Document...............................3 2. Introduction....................................................4 2.1 Motivation.....................................................4 2.2Introduction ....................................................4 1.1. Motivation .................................................4 1.2. Goals andObjectives...........................................5 2.3Objectives .......................................5 1.3. Required Context for All ReorderingMetrics....................6Metrics ................6 2. Conventions Used in this Document ...............................7 3. A Reordered Packet SingletonMetric.............................6 3.1MetricName....................................................7 3.2.............................7 3.1. Metric Name ................................................8 3.2. MetricParameters..............................................7 3.3 Definition.....................................................8 3.4Parameters ..........................................8 3.3. Definition .................................................8 3.4. Sequence DiscontinuityDefinition..............................8 3.5Definition ..........................9 3.5. Evaluation of Reordering in Dimensions of Time orBytes........9 3.6 Discussion.....................................................9Bytes ...10 3.6. Discussion ................................................10 4. SampleMetrics.................................................10 4.1Metrics .................................................11 4.1. Reordered PacketRatio........................................10 4.1.1Ratio ....................................11 4.1.1. MetricName.................................................10 4.1.2Name ........................................11 4.1.2. MetricParameters...........................................10 4.1.3 Definition..................................................11 4.1.4 Discussion..................................................11 4.2Parameters ..................................11 4.1.3. Definition .........................................12 4.1.4. Discussion .........................................12 4.2. ReorderingExtent.............................................11 4.2.1Extent .........................................12 4.2.1. MetricName.................................................11 4.2.2Name ........................................12 4.2.2. Notation and MetricParameters..............................11 4.2.3 Definition..................................................12 4.2.4 Discussion..................................................12 4.3Parameters .....................12 4.2.3. Definition .........................................13 4.2.4. Discussion .........................................13 4.3. Reordering Late TimeOffset...................................13 4.3.1Offset ...............................14 4.3.1. MetricName.................................................13 4.3.2Name ........................................14 4.3.2. MetricParameters...........................................13 4.3.3 Definition..................................................14 4.3.4 Discussion..................................................14 4.4Parameters ..................................14 4.3.3. Definition .........................................15 4.3.4. Discussion .........................................15 4.4. Reordering ByteOffset........................................15 4.4.1Offset ....................................16 4.4.1. MetricName.................................................15 4.4.2Name ........................................16 4.4.2. MetricParameters...........................................15 4.4.3 Definition..................................................15 4.4.4 Discussion..................................................15 4.5Parameters ..................................16 4.4.3. Definition .........................................16 4.4.4. Discussion .........................................17 4.5. Gaps betweenmultipleMultiple ReorderingDiscontinuities..............16 4.5.1Discontinuities ..........17 4.5.1. MetricNames................................................16 4.5.2 Parameters..................................................16 4.5.3Names .......................................17 4.5.2. Parameters .........................................17 4.5.3. Definition of ReorderingDiscontinuity......................16 4.5.4Discontinuity .............17 4.5.4. Definition of ReorderingGap................................16 4.5.5 Discussion..................................................17 4.6 Reordering-free Runs..........................................17 4.6.1 Metric Names................................................18 4.6.2 Parameters..................................................18 4.6.3 Definition..................................................18 4.6.4Gap .......................18 4.5.5. Discussion .........................................18 4.6. Reordering-Free Runs ......................................19 4.6.1. Metric Names .......................................19 4.6.2. Parameters .........................................19 4.6.3. Definition .........................................19 4.6.4. Discussion andIllustration.................................19Illustration ........................20 5. Metrics Focused on Receiver Assessment: A TCP-RelevantMetric..19 5.1MetricName...................................................20 5.2..21 5.1. Metric Name ...............................................21 5.2. ParameterNotation............................................20 5.3 Definitions...................................................20 5.4 Discussion....................................................21Notation ........................................21 5.3. Definitions ...............................................22 5.4. Discussion ................................................22 6. Measurement and ImplementationIssues..........................21 6.1Issues ..........................23 6.1. Passive MeasurementConsiderations............................24Considerations ........................26 7. Examples of Arrival OrderEvaluation...........................25 7.1Evaluation ...........................26 7.1. Example with a Single PacketReordered........................25 7.2Reordered ....................26 7.2. Example with Two PacketsReordered............................26 7.3Reordered ........................28 7.3. Example with Three PacketsReordered..........................28 7.4Reordered ......................30 7.4. Example with Multiple Packet ReorderingDiscontinuities.......29Discontinuities ...31 8. SecurityConsiderations........................................29 8.1 Denial of Service Attacks.....................................29 8.2Considerations ........................................32 8.1. Denial-of-Service Attacks .................................32 8.2. User DataConfidentiality.....................................30 8.3Confidentiality .................................32 8.3. Interference with theMetric..................................30Metric ..............................32 9. IANAConsiderations............................................30Considerations ............................................33 10. NormativeReferences..........................................32References ..........................................35 11. InformativeReferences........................................33References ........................................36 12.Acknowledgments...............................................35 13.Acknowledgements ..............................................37 AppendixAA. Example Implementations in C(Informative).........35 14.(Informative) ............38 AppendixBB. Fragment Order Evaluation(Informative)............38 14.1(Informative) ...............41 B.1. MetricName..................................................38 14.2Name ...............................................41 B.2. Additional MetricParameters.................................38 14.3 Definition...................................................38 14.4Parameters ..............................41 B.3. Definition ................................................42 B.4. Discussion: Notes on Sample MetricswhenWhen EvaluatingFragments40 15.Fragments .................................................43 Appendix C. Disclaimer andLicense........................................40 16. Author's Addresses............................................40 Full Copyright Statement..........................................41 Intellectual Property.............................................41 Acknowledgement...................................................42License ................................43 1.Conventions Used in this Document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. Although RFC 2119 was written with protocols in mind, the key words are used in this document for similar reasons. They are used to ensure the results of measurements from two different implementations are comparable, and to note instances when an implementation could perturb the network. In this memo, the characters "<=" should be read as "less than or equal to" and ">=" as "greater than or equal to". 2.Introduction Ordered arrival is a property found in packets that transit their path, where the packet sequence number increases with each new arrival and there are no backward steps. The Internet Protocol [RFC791][RFC2640][RFC2460] has no mechanisms toassureensure either packet delivery or sequencing, andhigher layerhigher-layer protocols (above IP) should be prepared to deal with both loss and reordering. This memo defines reordering metrics. A unique sequence identifier carried in each packet, such as an incrementing consecutive integer message number, establishes theSource Sequence.source sequence. The detection of reordering at theDestinationdestination is based on packet arrival order in comparison with a non-reversing reference value [Cia03]. This metric is consistent with[RFC2330],[RFC2330] and classifies arriving packets with sequence numbers smaller than their predecessors asout-of-order,out-of-order or reordered. For example, if sequentially numbered packets arrive 1,2,4,5,3, then packet 3 is reordered. This is equivalent to Paxon's reordering definition in [Pax98], where "late" packets were declared reordered. The alternative is to emphasize "premature" packets instead (4 and 5 in the example), but only the arrival of packet 3 distinguishes this circumstance from packet loss. Focusing attention on late packets allows us to maintain orthogonality with the packet loss metric. The metric's construction is very similar to the sequence space validation for received segments in [RFC793]. Earlier work to define ordered delivery includes [Cia00], [Ben99], [Lou01], [Bel02],[Jai02][Jai02], and [Cia03].2.11.1. Motivation A reordering metric is relevant for most applications, especially when assessing network support for Real-Time media streams. The extent of reordering may be sufficient to cause a received packet to be discarded by functions above the IP layer. Packet order may change during transfer, and several specific path characteristics can make reordering more likely. Examples are: * When two (or more) paths with slightly differing transfer times support a single packet stream or flow,thenpackets traversing the longer path(s) may arrive out-of-order. Multiple paths may be used to achieve loadbalancing,balancing or may arise from route instability. * To increase capacity, a network device designed with multiple processors serving a single port (or parallel links) may reorder as a byproduct. * Alayer 2layer-2 retransmission protocol that compensates for an error- prone link may cause packet reordering. * If for anyreason,reason the packets in a buffer are not serviced in the order of their arrival, their order will change. * If packets in a flow are assigned to multiple buffers (following evaluation of traffic characteristics, for example), and the buffers have differentoccupationsoccupation levels and/or service rates, then order will likely change. When one or more of the above path characteristics are present continuously,thenreordering may be present on a steady-state basis. The steady-state reordering condition typically causes an appreciable fraction of packets to be reordered. This form of reordering is most easily detected by minimizing the spacing between test packets. Transient reordering may occur in response to network instability; temporary routing loops can cause periods of extreme reordering. This condition is characterized bylonglong, in-order streams with occasional instances of reordering, sometimes with extreme correlation. However, we do not expect packet delivery in a completely random order,wherewhere, for example, the last packet or the first packet in a sample is equally likely to arrive first at the destination.ThusThus, we expect at least a minimal degree of order in the packet arrivals, as exhibited in real networks. The ability to restore order at the destination will likely have finite limits. Practical hosts have receiver buffers with finite size in terms of packets, bytes, or time (such as de-jitter buffers). Once the initial determination of reordering is made, it is useful to quantify the extent of reordering, or lateness, in all meaningful dimensions.2.21.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 effects 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. 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 view of the interested community. + be computable "on thefly"fly". + work even if the stream has duplicate or lostpacketspackets. It is desirable for Reordering Metrics to have one or more of the following attributes: + ability to concatenate results for segments measured separately to estimate the reordering of an entire path + simplicity for easy consumption and understanding + relevance to TCP design + relevance toReal-timereal-time application performance The current set of metrics meets all the requirements above and provides all but the concatenation attribute (except in the case where measurements of path segments exhibit no reordering, and one may estimate that the complete path composed of these segments would also exhibit no reordering). However, satisfying these goals restricts the set of metrics to those that provide some clear insight into network characterization or receiver design. They are not likely to be exhaustive in their coverage of reordering effects on applications, and additional measurements may be possible.2.31.3. Required Context for All Reordering Metrics A critical aspect of all reordering metrics is their inseparable bond with the measurement conditions. Packet reordering is not well defined unless the full measurement context is reported. Therefore, all reordering metric definitions include the following parameters: 1. The "Packet of Type-P" [RFC2330] identifiers for the packet stream, including the transport addresses for source and destination, and any other informationwhichthat may result in different packet treatments. 2. The stream parameter set for the sending discipline, such as the parameters unique toPeriodic Streamsperiodic streams (as in [RFC3432]), TCP-likeStreamsstreams (as in [RFC3148]), or PoissonStreamsstreams (as in [RFC2330]). The stream parameters include the packet size,eitherspecified either as a fixed value or as a pattern of sizes (as applicable). Whenever a metric is reported, it MUST include a description of these parameters to provide a context for the results. 2. Conventions Used in this Document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. Although RFC 2119 was written with protocols in mind, the key words are used in this document for similar reasons. They are used to ensure the results of measurements from two different implementations are comparable, and to note instances when an implementation could perturb the network. In this memo, the characters "<=" should be read as "less than or equal to" and ">=" as "greater than or equal to". 3. A Reordered Packet Singleton Metric The IPPM framework [RFC2330] describes the notions of singletons, samples, and statistics. For easy reference: By a 'singleton' metric, we refer to metrics that are, in a sense, atomic. For example, a single instance of "bulk throughput capacity" from one host to another might be defined as a singleton metric, even though the instance involves measuring the timing of a number of Internet packets. The evaluation of packet order requires several supporting concepts. The first is an algorithm (function) that produces a series of strictly monotonically increasing identifiers applied to packets at the source to uniquely establish the order of packet transmission (where a function, g(x), is strictly monotonically increasing if for any x>y, g(x)>g(y) ). The unique sequence identifier may simply be an incrementing consecutive integer message number, or a sequence number as used below. The prospect of sequence numberroll-overrollover is discussed in Section 6. The second supporting concept is a stored valuewhichthat is the "next expected" packet number. Under normal conditions, the value of Next Expected (NextExp) is the sequence number of the previous packet plus 1 for messagenumbering (innumbering. (In general, the receiver reproduces the sender's algorithm and the sequence of identifiers so that the "next expected" can bedetermined).determined.) Each packet within a packet stream can be evaluated with this order singleton metric.3.13.1. Metric Name Type-P-Reordered3.23.2. Metric Parameters + Src, the IP address of ahosthost. + Dst, the IP address of ahosthost. + SrcTime, the time of packet emission from theSourcesource (or wiretime)time). + s, the unique packet sequence number applied at theSource,source, in units of messages. + NextExp, theNext Expected Sequencenext expected sequence number at theDestination,destination, in 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 theSource,source, in units of payload bytes.3.33.3. Definition If a packets,s (sent at time, SrcTime) is found to be reordered by comparison with theNext ExpectedNextExp value, its Type-P-Reordered = TRUE;otherwiseotherwise, 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 for comparison with the next packet to arrive. Since theNext ExpectedNextExp value cannot decrease, it provides anon- reversingnon-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; else /* when s < NextExp */ Type-P-Reordered = True3.43.4. Sequence Discontinuity Definition Packets with s > NextExp are a special case of in-order delivery. This condition indicates a sequence discontinuity,eitherbecause of either packet loss or reordering. Reordered packets must arrive for the sequence discontinuity to be defined as a reordering discontinuity (seesectionSection 4). We define two different states for in-order packets. When s = NextExp, the original sequence has been maintained, and there is no discontinuity present. When s > NextExp, some packets in the original sequence have not yet arrived, and there is a sequence discontinuity associated with packet s. The size of the discontinuity is s - NextExp, equal to the number of packets presently missing, either reordered or lost. In pseudo-code: On successful arrival of a packet with sequence number s: if s >= NextExp, then /* s is in-order */ if s > NextExp then SequenceDiscontinuty = True; SeqDiscontinutySize = s - NextExp; else SequenceDiscontinuty = False; NextExp = s + 1; Type-P-Reordered = False; else /* when s < NextExp */ Type-P-Reordered = True; SequenceDiscontinuty = False; Whether anySequence Discontinuitiessequence discontinuities occur (and their size) is determined by the conditions causing loss and/or reordering along the measurement path. Note that a packet could be reordered at onepoint,point and subsequently lost elsewhere on the path, but this cannot be known from observations at theDestination. 3.5destination. 3.5. Evaluation of Reordering in Dimensions of Time or Bytes It is possible to use alternate dimensions of time or payload bytes to test for reordering in the definition ofsectionSection 3.3, as long as the SrcTimes and SrcBytes are unique and reliable. Sequence Discontinuities are easily defined and detected with messagenumbering,numbering; however, this is not so simple in the dimensions of time or bytes. This is a detractor for the alternate dimensions because theSequence Discontinuitysequence discontinuity definition plays a key role in the sample metrics that follow. It is possible to detectSequence Discontinuitiessequence discontinuities with payload byte numbering, but only when the test device knows exactly what value to assign as NextExp in response to any packet arrival. This is possible when the complete pattern of payload sizes is stored at theDestination,destination, or if the size pattern can be generated using a pseudo- random number generator and a shared seed. If payload size is constant, byte numbering adds needless complexity over message numbering. It may be possible to detectSequence Discontinuitiessequence discontinuities withPeriodic Streamsperiodic streams andSource Timesource time numbering, but there are practical pitfalls with sending exactly on-schedule and with clock reliability. The dimensions of time and bytes remain an important basis for characterizing the extent of reordering, as described insectionsSections 4.3 and 4.4.3.63.6. Discussion Any arriving packet bearing a sequence number from the sequence that establishes theNext ExpectedNextExp value can be evaluated to determine whether it is in-order or reordered, based on a previous packet's arrival. In the case whereNext ExpectedNextExp is Undefined (because the arriving packet is the first successful transfer), the packet is designated in-order (Type-P-Reordered=FALSE). This metric assumesre-assemblyreassembly of packet fragments before evaluation. In principle, it is possible to use the Type-P-Reordered metric to evaluate reordering among packet fragments, but each fragment must contain source sequence information. SeetheAppendixon fragment order evaluationB, "Fragment Order Evaluation", for more detail. If duplicate packets (multiple non-corrupt copies) arrive at the destination, they MUST benotednoted, and only the first to arrive is considered for further analysis (copies would be declared reordered according to the definition above). This requirement has the same storage implications as earlier IPPMmetrics,metrics and follows the precedent of [RFC2679]. We provide a suggestion to minimize storage size needed in Section 6 on Measurement and Implementation Issues. 4. Sample Metrics In this section, we define metrics applicable to a sample of packets from a singleSourcesource sequence number system. When reordering occurs, it is highly desirable to assert the degree to which a packet isout-of-order,out-of-order or reordered with respect other packets. This section defines several metrics that quantify the extent of reordering in various units of measure. Each metric highlights a relevant use. The metrics in the sub-sections below have a network characterization orientation, but also have relevance to receiver design where reordering compensation is of interest. We begin with a simple ratio metric indicating the reordered portion of the sample.4.14.1. Reordered Packet Ratio4.1.14.1.1. Metric Name Type-P-Reordered-Ratio-Stream4.1.24.1.2. Metric Parameters The parameter set includes Type-P-Reordered singletonparameters,parameters; the parameters unique to PoissonStreamsstreams (as in[RFC2330], Periodic Streams[RFC2330]), periodic streams (as in [RFC3432]), or TCP-likeStreamsstreams (as in[RFC3148]),[RFC3148]); packet size or sizepatterns,patterns; and the following: + T0, a start time + Tf, an end time + dT, a waiting time for each packet to arrive, in seconds + K, the total number of packets in the stream sent fromSourcesource toDestinationdestination + L, the total number of packets received (arriving between T0 and Tf+dT) out of the K packets sent. Recall that identical copies (duplicates) have been removed, so L <= K. + R, the ratio of reordered packets to received packets, defined below Note that parameter dT is effectively the threshold for declaring a packet as lost. The IPPM Packet Loss Metric [RFC2680] declines to recommend a value for this threshold, saying instead that "good engineering, including an understanding of packet lifetimes, will be needed in practice."4.1.34.1.3. Definition Given a stream of packets sent from aSourcesource to aDestination,destination, the ratio of reordered packets in the sample is R = (Count of packets with Type-P-Reordered=TRUE) / ( L ) This fraction may be expressed as a percentage (multiply by 100). Note that in the case of duplicate packets, only the first copy is used.4.1.44.1.4. Discussion When the Type-P-Reordered-Ratio-Stream is zero, no further reordering metrics need be examined for that sample. Therefore, the value of this metric is its simple ability to summarize the results for a reordering-free sample.4.24.2. Reordering Extent This section defines the extent to which packets arereordered,reordered and associates a specificSequence Discontinuitysequence discontinuity with each reordered packet. This section inherits the Parameters defined above.4.2.14.2.1. Metric Name Type-P-Packet-Reordering-Extent-Stream4.2.24.2.2. Notation and Metric Parameters Recall that K is the number of packets in the stream at theSourcesource, and L is the number of packets received at theDestination.destination. Each packet has been assigned a sequence number, s, a consecutive integer from 1 to K in the order of packet transmission (at the source). Let s[1], s[2], ...,s[L],s[L] represent the original sequence numbers associated with the packets in order of arrival. s[i] can be thought of as a vector, where the index i is the arrival position of the packet with sequence number s. In theory, anySourcesource sequence number could appear in any arrival position, but this is unlikely in reality. Consider a reordered packet (Type-P-Reordered=TRUE) with arrival index i and source sequence number s[i]. There exists a set of indexes j (1 <= j < i) such that s[j] > s[i]. The new parameters are: + i, the index for arrival position, where i-1 represents an arrival earlier than i. + j, a set of one or more arrival indexes, where 1 <= j < i. + s[i], the original sequence numbers, s, in order of arrival. + e, the Reordering Extent, in units of packets, defined below.4.2.34.2.3. Definition The reordering extent, e, of packet s[i] is defined to be i-j for the smallest value of j where s[j] > s[i]. Informally, the reordering extent is the maximum distance, in 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 isin- orderin-order bydefinition,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 (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.44.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 (seesectionSection 4.4 on Reordering Byte Offset and theExamples section).examples in Section 7). Also, if the receiver purges its buffer for any reason, the extent metric would not reflect this behavior, assuming instead that the receiver would exhaustively attempt to restore order. 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 ahistogram,histogram to easily summarize the frequency of various extents.4.34.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 Section 3.4.3.14.3.1. Metric Name Type-P-Packet-Late-Time-Stream4.3.24.3.2. Metric Parameters In addition to the parameters defined for Type-P-Reordered-Ratio- Stream, we specify: + DstTime, the time that each packet in the stream arrives at the destination, and may be associated with index i, or packet s[i] + LateTime(s[i]), the offset of packet s[i] in units of seconds, defined below4.3.34.3.3. Definition Lateness in time is calculated using destination times. When received packet s[i] isreordered,reordered and has a reordering extent e, then: LateTime(s[i]) = DstTime(i)-DstTime(i-e) Alternatively, using similar notation to that ofsectionSection 4.2, an equivalent definition is: LateTime(s[i]) = DstTime(i)-DstTime(j), for min{j|1<=j<i} that satisfies s[j]>s[i].4.3.44.3.4. Discussion The offset metrics can help predict whether reordered packets will be useful in a general receiver buffer system with finite limits. The limit may be the time of storage prior to a cyclic play-out instant (as with de-jitter buffers). Note that theOne-way IPDVone-way IP Packet Delay Variation (IPDV) [RFC3393] gives the delay variation for a packetw.r.t.with respect to the preceding packet in the source sequence. Lateness and IPDV give an indication of whether a buffer at the destination has sufficient storage to accommodate the network's behavior and restore order. When an earlier packet in theSourcesource sequence is lost, IPDV will necessarily be undefined for adjacent packets, and LateTime may provide the only way to evaluate the usefulness of a packet. In the case of de-jitter buffers, there are circumstances where the receiver employs loss concealment at the intended play-out time of a late packet. However, if this packet arrives out of order, the Late Time determines whether the packet is still useful. IPDV no longer applies, because the receiver establishes a new play-out schedule with additional buffer delay to accommodate similar events in the future (this requires very minimal processing). The combination of loss and reordering influences the LateTime 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 aPeriodic Streamperiodic 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 ahistogram,histogram to summarize the frequency of buffer times needed to accommodate reordered packets and permit buffer tuning on that basis. ACDFcumulative distribution function (CDF) with buffer time vs. percent of reordered packets accommodated may be informative.4.44.4. Reordering Byte Offset Reordered packets can be assigned offset values indicating the storage in bytes 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 Section 3.4.4.14.4.1. Metric Name Type-P-Packet-Byte-Offset-Stream4.4.24.4.2. Metric Parameters We use the same parameters defined earlier, including the optional parameters of SrcByte and PayloadSize, and define: + ByteOffset(s[i]), the offset of packet s[i] in bytes4.4.34.4.3. Definition The Byte stream offset for reordered packet s[i] is the sum of the payload sizes of packets qualified by the following criteria: *ArrivalThe arrival is prior to the reordered packet, s[i], and * The send sequence number, s, is greater than s[i]. Packets that meet both these criteria are normally buffered until the sequence beneath them is complete. Note that these criteria apply to both in-order and reordered packets. For reordered packet s[i] with a reordering extent e: ByteOffset(s[i]) = Sum[qualified packets] = Sum[PayloadSize(packet at i-1 if qualified), PayloadSize(packet at i-2 if qualified), ... PayloadSize(packet at i-e always qualified)] Using our earlier notation: ByteOffset(s[i]) = Sum[payloads of s[j] where s[j]>s[i] and i > j >= i-e]4.4.44.4.4. Discussion We note that estimates of buffer size due to reordering depend greatly on the test stream, in terms of the spacing between test 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 ahistogram,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.54.5. Gaps betweenmultipleMultiple Reordering Discontinuities4.5.14.5.1. Metric Names Type-P-Packet-Reordering-Gap-Stream Type-P-Packet-Reordering-GapTime-Stream4.5.24.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: + Gap(s[j']), the Reordering Gap of packet s[j'] in units of integer messages and the OPTIONAL parameter: + GapTime(s[j']), the Reordering Gap of packet s[j'] in units of seconds4.5.34.5.3. Definition of Reordering Discontinuity All reordered packets are associated with a packet at a reordering discontinuity, defined as the in-order packet s[j] that arrived at the minimum value of j (1<=j<i) for which s[j]> s[i]. Note that s[j] will have been found to cause a sequence discontinuity, where s > NextExp when evaluated with the reordered singleton metric as described insectionSection 3.4. Recall that i - e = min(j). Subsequent reordered packets may be associated with the same s[j], or with a different discontinuity. This fact is used in the definition of the Reordering Gap, below.4.5.44.5.4. Definition of Reordering Gap A reordering gap is the distance between successive reordering discontinuities. The Type-P-Packet-Reordering-Gap-Stream metric assigns a value for Gap(s[j']) to (all) packets in a stream (and a value for GapTime(s[j']), when reported). If:Thethe packet s[j'] is found to be a reordering discontinuity, based on the arrival of reordered packet s[i'] with extent e', and an earlier reordering discontinuity s[j], based on the arrival of reordered packet s[i] with extent e was already detected, and i' > i, and there are no reordering discontinuities between j and j', then the Reordering Gap for packet s[j'] is the difference between the arrival positions the reordering discontinuities, as shown below: Gap(s[j']) = (j') - (j) Gaps MAY also be expressed in time: GapTime(s[j']) = DstTime(j') - DstTime(j) Otherwise:Gap(s[j’])Gap(s[j']) (and GapTime(s[j']) ) for packets[j’]s[j'] is 0.4.5.54.5.5. Discussion When separate reordering discontinuities can be distinguished,thena count may also be reported (along with the discontinuity description, such as the number of reordered packets associated with that discontinuity and their extents and offsets). The Gaps between a sample's reordering discontinuities may be expressed as ahistogram,histogram to easily summarize the frequency of various gaps. Reporting the mode, average, range,etc.etc., may also summarize the distributions. The Gap metric may help to correlate the frequency of reordering discontinuities with their cause. Gap lengths are also informative to receiver designers, revealing the period of reordering discontinuities. The combination of reordering gaps and extent reveals whether receivers will be required to handle cases of overlapping reordered packets.4.6 Reordering-free4.6. Reordering-Free Runs This section defines a metric based on a count of consecutivein- orderin-order packets between reordered packets.4.6.14.6.1. Metric Names Type-P-Packet-Reordering-Free-Run-x-numruns-Stream Type-P-Packet-Reordering-Free-Run-q-squruns-Stream Type-P-Packet-Reordering-Free-Run-p-numpkts-Stream Type-P-Packet-Reordering-Free-Run-a-accpkts-Stream4.6.24.6.2. Parameters We use the same parameters definedearlier,earlier and define the following: + r, the run counter + x, the number of runs, also the number of reordered packets + a, the accumulator of in-order packets + p, the number of packets (when the stream is complete, p=(x+a)=L) + q, the sum of the squares of the runs counted4.6.34.6.3. Definition As packets in a sample arrive at theDestination,destination, the count of in- order packets between reordered packets is a Reordering-Free run. Note that the minimum run-length is zero according to this definition. Apseudo codepseudo-code example follows: r = 0; /* r is the run counter */ x = 0; /* x is the number of runs */ a = 0; /* a is the accumulator of in-order packets */ p = 0; /* p is the number of packets */ q = 0; /* q is the sum of the squares of the runs counted */ while(packets arrive with sequence number s) { p++; if (s >= NextExp) /* s is in-order */ then r++; a++; else /* s is reordered */ q+= r*r; r = 0; x++; } Each in-order arrival increments the run counter and the accumulator of in-orderpackets,packets; each reordered packet resets the run counter after adding it to the sum of the squared lengths. Each arrival of a reordered packet yields a new run count. Long runs accompany periods where order was maintained, while short runs indicatefrequent,frequent or multi-packet reordering. The percent of packets in-order is 100*a/p The average Reordering-Free run length is a/x The q counter gives an indication of variation of theReordering- FreeReordering-Free runs from the average by comparing q/a to a/x((q/a)/(a/x)) 4.6.4((q/a)/(a/x)). 4.6.4. Discussion and Illustration Type-P-packet-Reordering-Free-Run-Stream parameters give a brief summary of the stream's reordering characteristics including the average reordering-free run length, and the variation of runlengths, thereforelengths; therefore, a key application of this metric is network evaluation. For 36 packets with 3 runs of 11 in-orderpacketspackets, we have: p = 36 x = 3 a = 33 q = 3 * (11*11) = 363aveave. reordering-free run = 11 q/a = 11 (q/a)/(a/x) = 1.0 For 36 packets with 3 runs, 2 runs of length11, and one of length3131, we have: p = 36 x = 3 a = 33 q = 1 + 1 + 961 = 963aveave. reordering-free run = 11 q/a = 29.18 (q/a)/(a/x) = 2.65 The variability in run length is prominent in the difference between the q values (sum of the squared run lengths) and in comparing average run length to the (q/a)/(a/x) ratios (equals 1 when all runs are the same length). 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric This section describes a metric that conveys information associated with the effect of reordering on TCP. However, in order to infer anything about TCP performance, the test stream MUST bear a close resemblance to the TCP sender of interest. [RFC3148] lists the specific aspects of congestion control algorithms that must be specified. Further, RFC 3148 recommends that Bulk Transfer Capacity metrics SHOULD have instruments to distinguish three cases of packet reordering (insectionSection 3.3). The sample metrics defined above satisfy the requirements to classify packets that are slightly or grossly out-of-order. The metric in this section adds the capability to estimate whether reordering might cause the DUP-ACK threshold to be exceeded causing the Fast Retransmit algorithm to be invoked. Additional TCP Kernel Instruments are summarized in [Mat03].5.15.1. Metric Name Type-P-Packet-n-Reordering-Stream5.25.2. Parameter Notation Let n be a positive integer (a parameter). Let k be a positive integer equal to the number of packets sent (sample size). Let l be a non-negative integer representing the number of packets that were received out of the k packets sent. (Note that there is no relationship between k and l: on one hand, losses can make l less than k; on the other hand, duplicates can make l greater than k.) Assign each sent packet a sequence number, 1 to k, in order of packet emission. Let s[1], s[2], ..., s[l] be the original sequence numbers of the received packets, in the order of arrival.5.35.3. Definitions Definition 1: Received packet number i (n < i <= l), with source sequence number s[i], is n-reordered if and only if for all j such that i-n <= j < i, s[j] > s[i]. Claim:IfIf, by this definition, apacket's reorderingpacket isnn-reordered and 0 < n' < n, then the packet is alsoreordered to the n' extent.n'-reordered. Note: This definition is illustrated by C code in Appendix A.ItThe code determines and reports the n-reordering for n from 1 to a specified parameter (MAXN in the code, set to 100). The value ofn=3 (when actually writing applications that would report the metric, one would probably report itn conjectured to be relevant forseveral valuesTCP is the TCP duplicate ACK threshold (set to the value ofn, such as 1, 2, 3, 4 -- and maybe a few more consecutive values).3 by paragraph 2 of Section 3.2 of [RFC 2581]). This definition does not assign an n to all reordered packets as defined by the singleton metric, in particular when blocks of successive packets are reordered. (In the arrival sequence s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only packet 4 is n-reordered, with n=3.) Definition 2: The degree of n-reordering ofthea sample is m/l, where m is the number of n-reordered packets in the sample. Definition 3: The degree of"monotonic reordering"monotonic reordering ofthea sample is its degree of 1-reordering. Definition 4: A sample is said to have no reordering if its degree of monotonic reordering is 0. Note: As follows from the claim above, if monotonic reordering of a sample is 0, then the n-reordering of the sample is0. 5.40 for all n. 5.4. Discussion The degree of n-reordering may be expressed as a percentage, in which case the number from Definition 2 is multiplied by 100. The n-reordering metric is helpful for matching the duplicate ACK threshold setting to a given path. For example, if a path exhibits no more than 5-reordering, a DUP-ACK threshold of 6 may avoid unnecessary retransmissions. Important special cases are n=1 and n=3: - For n=1, absence of 1-reordering means the sequence numbers that the receiver sees are monotonically increasing with respect to the previous arriving packet. - For n=3, a NewReno TCP sender would retransmit 1 packet in response to an instance of 3-reordering and therefore consider this packet lost for the purposes of congestion control (the sender will halve its congestion window, see [RFC2581]). Three is the default threshold for Stream Control Transport Protocol (SCTP) [RFC2960], and the Datagram Congestion Control Protocol (DCCP) [RFC4340] when used with Congestion Control ID 2: TCP-like Congestion Control [RFC4341]. A sample's n-reordering may be expressed as ahistogram,histogram to summarize the frequency for each value of n. We note that the definition of n-reordering cannot predict the exact number of packets unnecessarily retransmitted by a TCP sender under some circumstances, such as cases with closely-spaced reordered singletons. Both time and position influence the sender's behavior. A packet's n-reordering designation is sometimes equal to its reordering extent, e. n-reordering is different in the following ways: 1. n is a count of early packets with consecutive arrival positions at the receiver. 2. Reordered packets (Type-P-Reordered=TRUE) may not be n-reordered, but will have an extent, e (see the examples). 6. Measurement and Implementation Issues The results of tests will be dependent on the time interval between measurement packets (both at theSource,source, and during transport where spacing may change). Clearly, packets launched infrequently (e.g., 1 per 10 seconds) are unlikely to be reordered. In order to gauge the reordering for an application according to the metrics defined in this memo, it is RECOMMENDED to use the same sending pattern as the application of interest. In any case, the exact method of packet generation MUST be reported with the measurement results, including all stream parameters. + To make inferences about applications that use TCP, it is REQUIRED to use TCP-like Streams as in [RFC3148] + For real-time applications, it is RECOMMENDED to usePeriodic Streamsperiodic streams as in [RFC3432] It is acceptable to report the metrics of Sections 3 and 4 with other IPPM metrics using PoissonStreamsstreams [RFC2330]. Poisson streams represent an "unbiased sample" of network performance for packet loss and delay metrics. However, it would be incorrect to make inferences about the application categories above using reordering metrics measured with Poisson streams. Test stream designers may prefer to use a periodic sending intervalso thatin order to maintain a known temporal biasis maintained, also bringingand allow simplified results analysis (as described in [RFC3432]). In this case, it is RECOMMENDED that the periodic sending intervalshouldbe chosen to reproduce the closestSourcesource packet spacing expected. Testers must recognize that streams sent at the link speed serialization limit MUST have limited duration and MUST consider packet lossasan indication that the stream has caused congestion, and suspend further testing. 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. Since this metric definition may use sequence numbers with finite range, it is possible that the sequence numbers could reach end-of- range and roll over to zero during a measurement. By definition, theNext ExpectedNextExp value cannot decrease, and all packets received after aroll-overrollover would be declared reordered. Sequence numberroll-overrollover can be avoided by using combinations of counter size and test duration whereroll-overrollover is impossible (and sequence is reset to zero at the start). Also, message-based numbering results in slower sequence consumption. There may still be cases where methodological mitigation of this problem is desirable (e.g.,long- termlong-term testing). The elements of mitigation are: 1. There must be a test to detect if aroll-overrollover has occurred. It would be nearly impossible for the sequence numbers of successive packets to jump by more than half the total range, so these large discontinuities are designated asroll-over.rollover. 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) wheneverroll-overrollover 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. Inpracticepractice, there will be limited ability to determinereordering extent,the extent of reordering, 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, the reordering extent or degree of n-reordering may need to be expressed as greater than the window length if the reordering discontinuity information has been discarded, and Gap calculations 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 declaredlost,lost or be 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 maximum 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. Another possible limitation on storage is the maximum length of the sequence number field, assuming that most test streams do not exhaust this length in practice. 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.6.16.1. Passive Measurement Considerations As with other IPPM metrics, the definitions have been constructed primarily for Active measurements. 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 aSource-Destinationsource-destination path, recognizing that intermediate measurements may differ from those made at theDestinationdestination (where the reordering effect on applications can be inferred). It is possible to apply these metrics to evaluate reordering in a TCP sender's stream. In this case, theSourcesource sequence numbers would be based on bytestream,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 helpstoavoid this ambiguity in active measurement, or the optional TCP timestamp field [RFC1323] in passive measurement. 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. 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.17.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 PayloadSize=100 bytes, with SrcByte=(s x 100)-99 for s=1,2,3,4,... Table11: Example with Packet 4 Reordered, Sendingorder(SrcNum@Src):order( s @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 7 7 120 188 68 0 6 8 8 140 208 68 0 7 4 9 60 210 150 82 8 400 62 9 9 160 228 68 0 9 10 10 180 248 68 0 10 Each column gives the following information: s Packet sequence number at theSource.source. NextExp The value of NextExp when the packetarrived(beforearrived (before update). SrcTime Packet time stamp at theSource,source, ms. DstTime Packet time stamp at theDestination,destination, ms. Delay 1-way delay of the packet, ms. IPDV IP Packet Delay Variation, ms IPDV = Delay(SrcNum)-Delay(SrcNum-1) DstOrder Order in which the packet arrived at theDestination.destination. Byte Offset TheByte Offsetbyte offset of a reordered packet, in bytes. LateTime The lateness of a reordered packet, in ms. We can see that when Packet 4 arrives, NextExp=9, and it is declared reordered. We compute the extent of reordering as follows: Using the notation <s[1], ..., s[i], ..., s[L]>, the received packets are represented as: \/ s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 /\ Applying the definition ofType-P-packet-Reordering-Extent-Stream:Type-P-Packet-Reordering-Extent-Stream: when j=7, 8 > 4, so the reordering extent is 1 or more. when j=6, 7 > 4, so the reordering extent is 2 or more. when j=5, 6 > 4, so the reordering extent is 3 or more. when j=4, 5 > 4, so the reordering extent is 4 or more. when j=3, but 3 < 4, and 4 is the maximum extent, e=4 (assuming there are no earlier sequence discontinuities, as in this example). Further, we can compute the Late Time (210-148=62ms using DstTime) compared to Packet 5's arrival. If the receiver has a de-jitter buffer that holds more than 4 packets, or at least 62 ms storage, Packet 4 may be useful. Note that 1-way delay and IPDV indicate unusual behavior for Packet 4. Also, if Packet 4 had arrived at least 62ms earlier, it would have been in-order in this example. If all packets contained 100 byte payloads, then Byte Offset is equal to 400 bytes. Following the definitions ofsectionSection 5.1, Packet 4 is designated4- reordered. 7.24-reordered. 7.2. Example with Two Packets Reordered Table 2 Example with Packets 5 and 6 Reordered, Sending order(s @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 4 4 60 128 68 0 4 7 5 120 188 68 -22 5 5 8 80 189 109 41 6 100 1 6 8 100 190 90 -19 7 100 2 8 8 140 208 68 0 8 9 9 160 228 68 0 9 10 10 180 248 68 0 10 Table 2 shows a case where Packets 5 and 6 arrive just behind Packet 7, so both 5 and 6 are reordered. The Late times (189-188=1,190- 188=2)190-188=2) are small. Using the notation <s[1], ..., s[i], ..., s[l]>, the received packets are represented as: \/ \/ s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 /\ /\ Considering Packet 5 first: when j=5, 7 > 5, so the reordering extent is 1 or more. when j=4, we have 4 < 5, so 1 is its maximum extent, and e=1. Considering Packet 6 next: when j=6, 5 < 6, the extent is not yet defined. when j=5, 7 > 6, so the reordering extent is i-j=2 or more. when j=4, 4 < 6, and we find 2 is its maximum extent, and e=2. We can also associate each of these reordered packets with a reordering discontinuity. We find the minimum j=5 (for both packets) according to Section 4.2.3. So Packet 6 is associated with the same reordering discontinuity as Packet 5, the Reordering Discontinuity at Packet 7. This is a case where reordering extent e would over-estimate the packet storage required to restore order. Only one packet storage is required (to hold Packet 7), but e=2 for Packet 6. Following the definitions ofsectionSection 5, Packet 5 is designated1- reordered,1-reordered, but Packet 6 is not designated n-reordered. A hypothetical sender/receiver pair may retransmit Packet 5 unnecessarily, since it is 1-reordered (in agreement with the singleton metric). Though Packet 6 may not be unnecessarily retransmitted, the receiver cannot advance Packet 7 to the higher layers until after Packet 6 arrives. Therefore, the singleton metric correctly determined that Packet 6 is reordered.7.37.3. Example with Three Packets Reordered Table 3 Example with Packets 4, 5, and 6 reordered Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11 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 7 4 120 188 68 -88 4 8 8 140 208 68 0 5 9 9 160 228 68 0 6 10 10 180 248 68 0 7 4 11 60 250 190 122 8 400 62 5 11 80 252 172 -18 9 400 64 6 11 100 256 156 -16 10 400 68 11 11 200 268 68 0 11 The case in Table 3 is where three packets in sequence have long transit times (Packets with s =4,5,and4, 5, and 6). Delay, Late time, and Byte Offset capture this very well, and indicate variation in reordering extent, while IPDV indicates that the spacing between packets 4,5,and 6 has changed. The histogram of Reordering extents (e) would be: Bin 1 2 3 4 5 6 7 Frequency 0 0 0 1 1 1 0 Using the notation <s[1], ..., s[i], ..., s[l]>, the received packets are represented as: s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 We first calculate the n-reordering. Considering Packet 4 first: when n=1, 7<=j<8, and 10> 4, so the packet is 1-reordered. when n=2, 6<=j<8, and 9 > 4, so the packet is 2-reordered. when n=3, 5<=j<8, and 8 > 4, so the packet is 3-reordered. when n=4, 4<=j<8, and 7 > 4, so the packet is 4-reordered. when n=5, 3<=j<8, but 3 < 4, and 4 is the maximum n-reordering. Considering packet 5[9] next: when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not designated as n-reordered. We find the sametoresult for Packet 6. We now consider whether reordered Packets 5 and 6 are associated with the same reordering discontinuity as Packet 4. Using the test of Section 4.2.3, we find that the minimum j=4 for all three packets. They are all associated with the reordering discontinuity at Packet 7. This example shows again that the n-reordering definition identifies a single Packet (4) with a sufficient degree of n-reordering that might cause one unnecessary packet retransmission by the New Reno TCP sender (with DUP-ACK threshold=3 or 4). Also, the reordered arrival of Packets 5 and 6 will allow the receiver process to pass Packets 7 through 10 up the protocol stack (the singletonType-P- ReorderedType-P-Reordered = TRUE for Packets 5 and 6, and they are all associated with a single reordering discontinuity).7.47.4. Example with Multiple Packet Reordering Discontinuities Table 4 Example with Multiple Packet Reordering Discontinuities Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 Discontinuity Discontinuity |---------Gap---------| s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 r = 1, 2, 3, 4, 5, 0, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, ... number of runs,n = 1 2 3 end r counts = 5 0 5(these(These values are computed after the packetarrives)arrives.) Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has e=2. There are two different reordering discontinuities, one at Packet 6 (where j=4) and one at Packet 12 (where j'=11). According to the definition of Reordering Gap Gap(s[j']) = (j') - (j) Gap(Packet 12) = (11) - (4) = 7 We also have three reordering-free runs of lengths 5, 0, and 5. The differences between these two multiple-event metrics are evident here. Gaps are the distance between sequence discontinuities that are subsequently defined as reordering discontinuities, while reordering-free runs capture the distance between reordered packets. 8. Security Considerations8.1 Denial of Service8.1. Denial-of-Service Attacks This metric requires a stream of packets sent from one host (source) to another host (destination) through intervening networks. This method could be abused fordenial of servicedenial-of-service attacks directed at destination and/or the intervening network(s). Administrators of the source, destination, andtheintervening network(s) should establish bilateral ormulti-lateralmultilateral agreements regarding the timing, size, and frequency of collection of sample metrics. Use of this method in excess of the terms agreed between the participants may be cause for immediate rejection or discard of packets or other escalation procedures defined between the affected parties.8.28.2. User Data Confidentiality Active use of this method generates packets for a sample, rather than taking samples based on user data, and does not threaten user data confidentiality. Passive measurement must restrict attention to the headers of interest. Since user payloads may be temporarily stored for length analysis, suitable precautions MUST be taken to keep this information safe and confidential. In most cases, a hashing function will produce a value suitable for payload comparisons.8.38.3. Interference with the Metric It may be possible to identify that a certain packet or stream of packets is part of a sample. With that knowledge at the destination and/or the intervening networks, it is possible to change the processing of the packets(e.g.(e.g., increasing or decreasing delay) that may distort the measured performance. It may also be possible to generate additional packets that appear to be part of the sample metric. These additional packets are likely to perturb the results of the sample measurement. The likely consequences of packet injection are that the additional packets would be declared duplicates, or that the original packets would be seen as duplicates (if they arrive after the corresponding injectedpackets)packets), causing invalid measurements on the injected packets. The requirements for data collection resistance to interference by malicious parties and mechanisms to achieve such resistance are available in other IPPM memos. A set of requirements for a data collection protocol can be found in [RFC3763], and a protocol specification for the One-Way Active Measurement Protocol (OWAMP) is in[RFCyyyy].[RFC4656]. The security considerations sections of the two OWAMP documents are extensive and should be consulted for additional details. 9. IANA Considerations Metrics defined in this memoare designed to behave been registered in the IANA IPPM METRICS REGISTRY as described in initial version of the registry [RFC4148]. IANAis asked to registerhas registered the following metrics in theIANA-IPPM- METRICS-REGISTRY-MIB (where RFC xxxx is replaced with the number of this memo):IANA-IPPM-METRICS- REGISTRY-MIB: ietfReorderedSingleton OBJECT-IDENTITY STATUS current DESCRIPTION "Type-P-Reordered" REFERENCE "Reference RFCxxxx, section4737, Section 3" ::= { ianaIppmMetricsnn34 }-- IANA assigns nnietfReorderedPacketRatio OBJECT-IDENTITY STATUS current DESCRIPTION "Type-P-Reordered-Ratio-Stream" REFERENCE "Reference RFCxxxx, section4737, Section 4.1" ::= { ianaIppmMetricsnn35 }-- IANA assigns nnietfReorderingExtent OBJECT-IDENTITY STATUS current DESCRIPTION "Type-P-Packet-Reordering-Extent-Stream" REFERENCE "Reference RFCxxxx, section4737, Section 4.2" ::= { ianaIppmMetricsnn36 }-- IANA assigns nnietfReorderingLateTimeOffset OBJECT-IDENTITY STATUS current DESCRIPTION "Type-P-Packet-Late-Time-Stream" REFERENCE "Reference RFCxxxx, section4737, Section 4.3" ::= { ianaIppmMetricsnn37 }-- IANA assigns nnietfReorderingByteOffset OBJECT-IDENTITY STATUS current DESCRIPTION "Type-P-Packet-Byte-Offset-Stream" REFERENCE "Reference RFCxxxx, section4737, Section 4.4" ::= { ianaIppmMetricsnn38 }-- IANA assigns nnietfReorderingGap OBJECT-IDENTITY STATUS current DESCRIPTION "Type-P-Packet-Reordering-Gap-Stream" REFERENCE "Reference RFCxxxx, section4737, Section 4.5" ::= { ianaIppmMetricsnn39 }-- IANA assigns nnietfReorderingGapTime OBJECT-IDENTITY STATUS current DESCRIPTION "Type-P-Packet-Reordering-GapTime-Stream" REFERENCE "Reference RFCxxxx, section4737, Section 4.5" ::= { ianaIppmMetricsnn40 }-- IANA assigns nnietfReorderingFreeRunx OBJECT-IDENTITY STATUS current DESCRIPTION "Type-P-Packet-Reordering-Free-Run-x-numruns-Stream" REFERENCE "Reference RFCxxxx, section4737, Section 4.6" ::= { ianaIppmMetricsnn41 }-- IANA assigns nnietfReorderingFreeRunq OBJECT-IDENTITY STATUS current DESCRIPTION "Type-P-Packet-Reordering-Free-Run-q-squruns-Stream" REFERENCE "Reference RFCxxxx, section4737, Section 4.6" ::= { ianaIppmMetricsnn42 }-- IANA assigns nnietfReorderingFreeRunp OBJECT-IDENTITY STATUS current DESCRIPTION "Type-P-Packet-Reordering-Free-Run-p-numpkts-Stream" REFERENCE "Reference RFCxxxx, section4737, Section 4.6" ::= { ianaIppmMetricsnn43 }-- IANA assigns nnietfReorderingFreeRuna OBJECT-IDENTITY STATUS current DESCRIPTION "Type-P-Packet-Reordering-Free-Run-a-accpkts-Stream" REFERENCE "Reference RFCxxxx, section4737, Section 4.6" ::= { ianaIppmMetricsnn44 }-- IANA assigns nnietfnReordering OBJECT-IDENTITY STATUS current DESCRIPTION "Type-P-Packet-n-Reordering-Stream" REFERENCE "Reference RFCxxxx, section4737, Section 5" ::= { ianaIppmMetricsnn45 }-- IANA assigns nn10. Normative References [RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981.Obtain via: http://www.rfc-editor.org/rfc/rfc791.txt[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.Obtain via: http://www.rfc-editor.org/rfc/rfc2119.txt[RFC2330] Paxson, V., Almes, G., Mahdavi, J., and M. Mathis,M.,"Framework for IP Performance Metrics", RFC 2330, May 1998.Obtain via: http://www.rfc-editor.org/rfc/rfc2330.txt[RFC2460] Deering, S. and R. Hinden,R.,"InternetProtocolProtocol, Version 6 (IPv6) Specification", RFC 2460, December 1998.Obtain via: http://www.rfc-editor.org/rfc/rfc2460.txt[RFC3148] Mathis, M. and M. Allman,M.,"A Framework for Defining Empirical Bulk Transfer Capacity Metrics", RFC 3148, July 2001.Obtain via: http://www.rfc-editor.org/rfc/rfc3148.txt[RFC3432] Raisanen, V., Grotefeld, G., and A. Morton,A.,"Network performance measurement with periodic streams", RFC 3432, November 2002.Obtain via: http://www.rfc-editor.org/rfc/rfc3432.txt[RFC3763] Shalunov, S. and B. Teitelbaum,B.,"One-way Active Measurement Protocol (OWAMP) Requirements", RFC 3763, April 2004.Obtain via: http://www.rfc-editor.org/rfc/rfc3763.txt[RFC4148] Stephan, E., "IP Performance Metrics (IPPM) Metrics Registry",RFC 4148,BCP 108, RFC 4148, August 2005.Obtain via: http://www.rfc-editor.org/rfc/rfc4148.txt [RFCyyyy][RFC4656] Shalunov, S., Teitelbaum, B., Karp, A., Boote, J., and M. Zeckauskas,M., "One-way"A One-way Active Measurement Protocol(OWAMP) Requirements",(OWAMP)", RFCyyyy,4656, September 2006.Obtain via: http://www.rfc-editor.org/rfc/rfcyyyy.txt11. Informative References [Bel02]J.BellardoJ. Bellardo andS.Savage,S. Savage, "Measuring Packet Reordering," Proceedings of the ACM SIGCOMM Internet Measurement Workshop 2002, November 6-8, Marseille, France. [Ben99]J.C.R.Bennett, C.Partridge,J.C.R. Bennett, C. Partridge, andN.Shectman,N. Shectman, "Packet Reordering is Not Pathological Network Behavior," IEEE/ACM Transactions on Networking,vol.7, no.6, pp.789- 798,vol. 7, no. 6, pp. 789-798, December 1999. [Cia00]L.CiavattoneL. Ciavattone andA.Morton,A. Morton, "Out-of-Sequence Packet Parameter Definition (for Y.1540)", Contribution number T1A1.3/2000-047, October 30,2000. ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc2000, http://home.comcast.net/~acmacm/IDcheck/0A130470.doc. [Cia03]L.Ciavattone, A.Morton,L. Ciavattone, A. Morton, andG.Ramachandran,G. Ramachandran, "Standardized Active Measurements on a Tier 1 IP Backbone," IEEE Communications Mag.,pppp. 90-97, June 2003. [I.356] ITU-T Recommendation I.356, "B-ISDN ATM layer cell transfer performance", March 2000. [Jai02]S.JaiswalS. Jaiswal et al., "Measurement and Classification of Out- of-Sequence Packets in a Tier-1 IP Backbone," Proceedings of the ACM SIGCOMM Internet Measurement Workshop 2002, November 6-8, Marseille, France. [Lou01]D.LoguinovD. Loguinov andH.Radha,H. Radha, "Measurement Study ofLow-bitrateLow- bitrate Internet Video Streaming", Proceedings of the ACM SIGCOMM Internet Measurement Workshop 2001 November 1-2, 2001, San Francisco, USA. [Mat03] M. Mathis,J HeffnerJ. Heffner, andRR. Reddy, "Web100: Extended TCP Instrumentation for Research, Education and Diagnosis", ACM Computer Communications Review, Vol 33, Num 3, July2003. http://www.web100.org/docs/mathis03web100.pdf2003, http://www.web100.org/docs/mathis03web100.pdf. [Pax98]V.Paxson,V. Paxson, "Measurements and Analysis of End-to-End Internet Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997, ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz. [RFC793] Postel, J., "Transmission Control Protocol", STD 7, RFC 793, September 1981.Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt[RFC1323] Jacobson, V., Braden, R., and D. Borman,D.,"TCP Extensions for High Performance", RFC 1323, May 1992. [RFC2581] Allman, M., Paxson, V., and W. Stevens,W.,"TCP CongestionControl",Control ", RFC 2581, April 1999. [RFC2679] Almes, G., Kalidindi, S., and M. Zekauskas,M.,"A One-way Delay Metric for IPPM", RFC 2679, September 1999.Obtain via: http://www.rfc-editor.org/rfc/rfc2679.txt[RFC2680] Almes, G., Kalidindi, S., and M. Zekauskas,M.,"A One-way Packet Loss Metric for IPPM", RFC 2680, September 1999.Obtain via: http://www.rfc-editor.org/rfc/rfc2680.txt[RFC2960] Stewart, R.,et al.,Xie, Q., Morneault, K., Sharp, C., Schwarzbauer, H., Taylor, T., Rytina, I., Kalla, M., Zhang, L., and V. Paxson, "Stream Control Transmission Protocol", RFC 2960, October 2000. [RFC3393] Demichelis,C.,C. and P. Chimento,P.,"IP Packet Delay Variation Metric for IP Performance Metrics (IPPM)", RFC 3393, November 2002. [RFC4340] Kohler, E., Handley,M.M., and S. Floyd,S.,"Datagram Congestion Control Protocol (DCCP)", RFC 4340, March 2006. [RFC4341] Floyd, S. and E. Kohler,E.,"Profile for Datagram Congestion Control Protocol (DCCP) Congestion Control ID 2: TCP-like Congestion Control", RFC 4341, March 2006. [TBABAJ02] T. Banka, A.A.Bare, A. P. Jayasumana, "Metrics for Degree of Reordering in Packet Sequences", Proc. 27th IEEE Conference on Local Computer Networks, Tampa, FL, Nov. 2002. [Y.1540] ITU-T Recommendation Y.1540, "Internet protocol data communication service - IP packet transfer and availability performance parameters", December 2002. 12.AcknowledgmentsAcknowledgements 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 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. Anura Jayasumana and Nischal Piratla brought in recent work-in-progress [TBABAJ02]. We gratefully acknowledge the foundation laid by the authors of the IP performanceFrameworkframework [RFC2330].13.AppendixAA. Example Implementations in C (Informative) Two example c-code implementations of reordering definitions follow: Example 1 n-reordering ============================================ #include <stdio.h> #define MAXN 100 #define min(a, b) ((a) < (b)? (a): (b)) #define loop(x) ((x) >= 0? x: x + MAXN) /* * Read new sequence number and return it. Return a sentinel value * of EOF (at least once) when there are no more sequence numbers. * In this example, the sequence numbers come from stdin; * in an actual test, they would come from the network. * */ int read_sequence_number() { int res, rc; rc = scanf("%d\n", &res); if (rc == 1) return res; else return EOF; } int main() { int m[MAXN]; /* We have m[j-1] == number of * j-reordered packets. */ int ring[MAXN]; /* Last sequence numbers seen. */ int r = 0; /* Ring pointer for next write. */ int l = 0; /* Number of sequence numbers read. */ int s; /* Last sequence number read. */ int j; for (j = 0; j < MAXN; j++) m[j] = 0; for (;(s = read_sequence_number())!= EOF;l++,r=(r+1)%MAXN) { for (j=0; j<min(l, MAXN)&&s<ring[loop(r-j-1)];j++) m[j]++; ring[r] = s; } for (j = 0; j < MAXN && m[j]; j++) printf("%d-reordering = %f%%\n", j+1, 100.0*m[j]/(l-j-1)); if (j == 0) printf("no reordering\n"); else if (j < MAXN) printf("no %d-reordering\n", j+1); else printf("only up to %d-reordering is handled\n", MAXN); exit(0); } /* Example 2 singleton and n-reordering comparison ======= Author: Jerry Perser 7-2002 (mod by acm 12-2004) Compile: $ gcc -o jpboth file.c Usage: $ jpboth 1 2 3 7 8 4 5 6 (pkt sequence given on cmdline) Note to cut/pasters: line 59 may need repair */ #include <stdio.h> #define MAXN 100 #define min(a, b) ((a) < (b)? (a): (b)) #define loop(x) ((x) >= 0? x: x + MAXN) /* Global counters */ int receive_packets=0; /* number of received */ int reorder_packets_Al=0; /* num reordered pkts (singleton) */ int reorder_packets_Stas=0; /* num reordered pkts(n-reordering)*/ /* function to test if current packet has been reordered * returns 0 = not reordered * 1 = reordered */ int testorder1(int seqnum) // Al { static int NextExp = 1; int iReturn = 0; if (seqnum >= NextExp) { NextExp = seqnum+1; } else { iReturn = 1; } return iReturn; } int testorder2(int seqnum) // Stanislav { static int ring[MAXN]; /* Last sequence numbers seen. */ static int r = 0; /* Ring pointer for next write */ int l = 0; /* Number of sequence numbers read. */ int j; int iReturn = 0; l++; r = (r+1) % MAXN; for (j=0; j<min(l, MAXN) && seqnum<ring[loop(r-j-1)]; j++) iReturn = 1; ring[r] = seqnum; return iReturn; } int main(int argc, char *argv[]) { int i, packet; for (i=1; i< argc; i++) { receive_packets++; packet = atoi(argv[i]); reorder_packets_Al += testorder1(packet); // singleton reorder_packets_Stas += testorder2(packet); //n-reord. } printf("Received packets = %d, Singleton Reordered = %d, n- reordered = %d\n", receive_packets, reorder_packets_Al, reorder_packets_Stas ); exit(0); } Reference ISO/IEC 9899:1999 (E), as amended by ISO/IEC 9899:1999/Cor.1:2001 (E). Also published as: The C Standard: Incorporating Technical Corrigendum 1, British Standards Institute, ISBN: 0-470-84573-2, Hardcover, 558 pages, September 2003.14.AppendixBB. Fragment Order Evaluation (Informative) Section 3 stated that fragmentre-assemblyreassembly is assumed prior to order evaluation, but that similar procedures could be applied prior tore-assembly.reassembly. This appendix gives definitions and procedures to identify reordering in a packet stream that includes fragmentation.14.1B.1. Metric Name The Metric retains the same name, Type-P-Reordered, but additional parameters are required. ThisAppendixappendix assumes that the device that divides a packet into fragmentssendsends them according to ascending fragment offset. Early Linux OS sent fragments in reverse order, so this possibility is worth checking.14.2B.2. Additional Metric Parameters + MoreFrag, the state of the More Fragments Flag in the IPheaderheader. + FragOffset, the offset from the beginning of a fragmented packet, in 8 octet units (also from the IP header). + FragSeq#, the sequence number from the IP header of a fragmented packet currently under evaluation for reordering. When set to zero, fragment evaluation is not in progress. + NextExpFrag, theNext Expected Fragment Offsetnext expected fragment offset at theDestination,destination, in 8 octet units. Set to zero when fragment evaluation is not in progress. The packet sequence number, s, is assumed to be the same as the IP header sequence number. Also, the value of NextExp does not change with the in-order arrival of fragments. NextExp is only updated when a last fragment or a complete packet arrives. Note that packets with missing fragments MUST be declared lost, and the Reordering status of any fragments that do arrive MUST be excluded from sample metrics.14.3B.3. Definition The value of Type-P-Reordered is typically false (the packet isin- order)in-order) when * the sequence number s >= NextExp,*AND * the fragment offset FragOffset >= NextExpFrag However, it is more efficient to define reordered conditionsexactly,exactly and designate Type-P-Reordered as False otherwise. The value of Type-P-Reordered is defined as True (the packet is reordered) under the conditions below. In these cases, the NextExp value does not change. Case 1: if s < NextExp Case 2: if s < FragSeq# Case 3: if s>= NextExp AND s = FragSeq# AND FragOffset < NextExpFrag This definition can also be illustrated in pseudo-code. A version of the code follows, and some simplification may be possible.A challenging aspect surrounds the housekeepingHousekeeping for the newparameters.parameters will be challenging. NextExp=0; NextExpFrag=0; FragSeq#=0; while(packets arrive with s, MoreFrag, FragOffset) { if (s>=NextExp AND MoreFrag==0 AND s>=FragSeq#){ /* a normal packet or last frag of an in-order packet arrived */ NextExp = s+1; FragSeq# = 0; NextExpFrag = 0; Reordering = False; } if (s>=NextExp AND MoreFrag==1 AND s>FragSeq#>=0){ /* a fragment of a new packet arrived, possibly with a higher sequence number than the current fragmented packet */ FragSeq# = s; NextExpFrag = FragOffset+1; Reordering = False; } if (s>=NextExp AND MoreFrag==1 AND s==FragSeq#){ /* a fragment of the "current packet s" arrived */ if (FragOffset >= NextExpFrag){ NextExpFrag = FragOffset+1; Reordering = False; } else{ Reordering = True; /* fragment reordered */ } } if (s>=NextExp AND MoreFrag==1 AND s < FragSeq#){ /* case where a late fragment arrived, for illustration only, redundant with else below */ Reordering = True; } else { /* when s < NextExp, or MoreFrag==0 AND s < FragSeq# */ Reordering = True; } } A working version of the code would include a check to ensure that all fragments of a packet arrive before using the Reordered status further, such as in sample metrics.14.4B.4. Discussion: Notes on Sample MetricswhenWhen Evaluating Fragments All fragments with the sameSource Sequence Numbersource sequence number are assigned the sameSource Time.source time. Evaluation with byte stream numbering may be simplified if the fragment offset is simply added to the SourceByte of the first packet (with fragment offset = 0), keeping the 8 octet units of the offset in mind.15.Appendix C. Disclaimer and License Regarding this entire document or any portion of it (including the pseudo-code and C code), the authors make no guarantees and are not responsible for any damage resulting from its use. The authors grant irrevocable permission to anyone to use, modify, and distribute it in any way that does not diminish the rights of anyone else to use, modify, and distribute it, provided that redistributed derivative works do not contain misleading author or version information. Derivative works need not be licensed under similar terms.16. Author'sAuthors' Addresses Al Morton AT&T Labs Room D3 - 3C06 200 Laurel Ave. South Middletown, NJ 07748 USA Phone +1 732 420 1571 EMail:<acmorton@att.com>acmorton@att.com Len Ciavattone AT&T Labs Room A2 - 4G06 200 Laurel Ave. South Middletown, NJ 07748 USA Phone +1 732 420 1239 EMail:<lencia@att.com>lencia@att.com Gomathi Ramachandran AT&T Labs Room C4 - 3D22 200 Laurel Ave. South Middletown, NJ 07748 USA Phone +1 732 420 2353 EMail:<gomathi@att.com>gomathi@att.com Stanislav Shalunov Internet2 1000 Oakbrook DR STE 300 Ann Arbor, MI 48104 Phone: +1 734 995 7060 EMail:<shalunov@internet2.edu>shalunov@internet2.edu Jerry Perser Veriwave 8770 SW Nimbus Ave. Suite B Beaverton, OR 97008 USA Phone: +1 818 338 4112 EMail:<jperser@veriwave.com>jperser@veriwave.com Full Copyright Statement Copyright (C) TheInternet SocietyIETF Trust (2006). 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 INTERNETSOCIETYSOCIETY, THE IETF TRUST, 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 The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF atietf- ipr@ietf.org.ietf-ipr@ietf.org. Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society.