summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc4737.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/rfc/rfc4737.txt')
-rw-r--r--doc/rfc/rfc4737.txt2523
1 files changed, 2523 insertions, 0 deletions
diff --git a/doc/rfc/rfc4737.txt b/doc/rfc/rfc4737.txt
new file mode 100644
index 0000000..165fa3b
--- /dev/null
+++ b/doc/rfc/rfc4737.txt
@@ -0,0 +1,2523 @@
+
+
+
+
+
+
+Network Working Group A. Morton
+Request for Comments: 4737 L. Ciavattone
+Category: Standards Track G. Ramachandran
+ AT&T Labs
+ S. Shalunov
+ Internet2
+ J. Perser
+ Veriwave
+ November 2006
+
+
+ Packet Reordering Metrics
+
+Status of This Memo
+
+ This document specifies an Internet standards track protocol for the
+ Internet community, and requests discussion and suggestions for
+ improvements. Please refer to the current edition of the "Internet
+ Official Protocol Standards" (STD 1) for the standardization state
+ and status of this protocol. Distribution of this memo is unlimited.
+
+Copyright Notice
+
+ Copyright (C) The IETF Trust (2006).
+
+Abstract
+
+ This memo defines metrics to evaluate whether 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 toward assessment of reordering effects on TCP. Several
+ examples of evaluation using the various sample metrics are included.
+ An appendix gives extended definitions for evaluating order with
+ packet fragmentation.
+
+
+
+
+
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 1]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+Table of Contents
+
+ 1. Introduction ....................................................4
+ 1.1. Motivation .................................................4
+ 1.2. Goals and Objectives .......................................5
+ 1.3. Required Context for All Reordering Metrics ................6
+ 2. Conventions Used in this Document ...............................7
+ 3. A Reordered Packet Singleton Metric .............................7
+ 3.1. Metric Name ................................................8
+ 3.2. Metric Parameters ..........................................8
+ 3.3. Definition .................................................8
+ 3.4. Sequence Discontinuity Definition ..........................9
+ 3.5. Evaluation of Reordering in Dimensions of Time or Bytes ...10
+ 3.6. Discussion ................................................10
+ 4. Sample Metrics .................................................11
+ 4.1. Reordered Packet Ratio ....................................11
+ 4.1.1. Metric Name ........................................11
+ 4.1.2. Metric Parameters ..................................11
+ 4.1.3. Definition .........................................12
+ 4.1.4. Discussion .........................................12
+ 4.2. Reordering Extent .........................................12
+ 4.2.1. Metric Name ........................................12
+ 4.2.2. Notation and Metric Parameters .....................12
+ 4.2.3. Definition .........................................13
+ 4.2.4. Discussion .........................................13
+ 4.3. Reordering Late Time Offset ...............................14
+ 4.3.1. Metric Name ........................................14
+ 4.3.2. Metric Parameters ..................................14
+ 4.3.3. Definition .........................................15
+ 4.3.4. Discussion .........................................15
+ 4.4. Reordering Byte Offset ....................................16
+ 4.4.1. Metric Name ........................................16
+ 4.4.2. Metric Parameters ..................................16
+ 4.4.3. Definition .........................................16
+ 4.4.4. Discussion .........................................17
+ 4.5. Gaps between Multiple Reordering Discontinuities ..........17
+ 4.5.1. Metric Names .......................................17
+ 4.5.2. Parameters .........................................17
+ 4.5.3. Definition of Reordering Discontinuity .............17
+ 4.5.4. Definition of Reordering Gap .......................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 and Illustration ........................20
+
+
+
+
+
+Morton, et al. Standards Track [Page 2]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric ..21
+ 5.1. Metric Name ...............................................21
+ 5.2. Parameter Notation ........................................21
+ 5.3. Definitions ...............................................22
+ 5.4. Discussion ................................................22
+ 6. Measurement and Implementation Issues ..........................23
+ 6.1. Passive Measurement Considerations ........................26
+ 7. Examples of Arrival Order Evaluation ...........................26
+ 7.1. Example with a Single Packet Reordered ....................26
+ 7.2. Example with Two Packets Reordered ........................28
+ 7.3. Example with Three Packets Reordered ......................30
+ 7.4. Example with Multiple Packet Reordering Discontinuities ...31
+ 8. Security Considerations ........................................32
+ 8.1. Denial-of-Service Attacks .................................32
+ 8.2. User Data Confidentiality .................................32
+ 8.3. Interference with the Metric ..............................32
+ 9. IANA Considerations ............................................33
+ 10. Normative References ..........................................35
+ 11. Informative References ........................................36
+ 12. Acknowledgements ..............................................37
+ Appendix A. Example Implementations in C (Informative) ............38
+ Appendix B. Fragment Order Evaluation (Informative) ...............41
+ B.1. Metric Name ...............................................41
+ B.2. Additional Metric Parameters ..............................41
+ B.3. Definition ................................................42
+ B.4. Discussion: Notes on Sample Metrics When Evaluating
+ Fragments .................................................43
+ Appendix C. Disclaimer and License ................................43
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 3]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+1. 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] [RFC2460] has no mechanisms to ensure either packet delivery
+ or sequencing, and higher-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 the
+ source sequence.
+
+ The detection of reordering at the destination is based on packet
+ arrival order in comparison with a non-reversing reference value
+ [Cia03].
+
+ This metric is consistent with [RFC2330] and classifies arriving
+ packets with sequence numbers smaller than their predecessors as
+ 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], and [Cia03].
+
+1.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, packets traversing the
+ longer path(s) may arrive out-of-order. Multiple paths may be used
+ to achieve load balancing or may arise from route instability.
+
+
+
+Morton, et al. Standards Track [Page 4]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ * To increase capacity, a network device designed with multiple
+ processors serving a single port (or parallel links) may reorder as
+ a byproduct.
+
+ * A layer-2 retransmission protocol that compensates for an error-
+ prone link may cause packet reordering.
+
+ * If for any 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 different occupation levels and/or service rates, then
+ order will likely change.
+
+ When one or more of the above path characteristics are present
+ continuously, reordering 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 by long, in-order streams with
+ occasional instances of reordering, sometimes with extreme
+ correlation. However, we do not expect packet delivery in a
+ completely random order, where, for example, the last packet or the
+ first packet in a sample is equally likely to arrive first at the
+ destination. Thus, 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.
+
+1.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
+
+
+
+Morton, et al. Standards Track [Page 5]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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 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
+ 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 to real-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.
+
+1.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 information that may result in
+ different packet treatments.
+
+
+
+
+Morton, et al. Standards Track [Page 6]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 2. The stream parameter set for the sending discipline, such as the
+ parameters unique to periodic streams (as in [RFC3432]), TCP-like
+ streams (as in [RFC3148]), or Poisson streams (as in [RFC2330]).
+ The stream parameters include the packet size, specified 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 number rollover is
+ discussed in Section 6.
+
+ The second supporting concept is a stored value that 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 message numbering. (In general, the receiver reproduces the
+
+
+
+Morton, et al. Standards Track [Page 7]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ sender's algorithm and the sequence of identifiers so that the "next
+ expected" can be determined.)
+
+ Each packet within a packet stream can be evaluated with this order
+ singleton metric.
+
+3.1. Metric Name
+
+ Type-P-Reordered
+
+3.2. Metric Parameters
+
+ + Src, the IP address of a host.
+
+ + 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. 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
+ transferred.
+
+ + SrcByte, the packet sequence number applied at the source, in
+ units of payload bytes.
+
+3.3. Definition
+
+ If a packet s (sent at time, SrcTime) is found to be reordered by
+ comparison with the NextExp 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 for
+ comparison with the next packet to arrive.
+
+
+
+Morton, et al. Standards Track [Page 8]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ Since the NextExp 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;
+ else /* when s < NextExp */
+ Type-P-Reordered = True
+
+3.4. Sequence Discontinuity Definition
+
+ Packets with s > NextExp are a special case of in-order delivery.
+ This condition indicates a sequence discontinuity, because of either
+ packet loss or reordering. Reordered packets must arrive for the
+ sequence discontinuity to be defined as a reordering discontinuity
+ (see Section 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;
+
+
+
+
+Morton, et al. Standards Track [Page 9]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ Whether any sequence 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 one point
+ and subsequently lost elsewhere on the path, but this cannot be known
+ from observations at the destination.
+
+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 of Section 3.3, as long as
+ the SrcTimes and SrcBytes are unique and reliable. Sequence
+ Discontinuities are easily defined and detected with message
+ numbering; however, this is not so simple in the dimensions of time
+ or bytes. This is a detractor for the alternate dimensions because
+ the sequence discontinuity definition plays a key role in the sample
+ metrics that follow.
+
+ It is possible to detect sequence 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 the
+ 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 detect sequence discontinuities with periodic
+ streams and source 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 in Sections 4.3
+ and 4.4.
+
+3.6. Discussion
+
+ Any arriving packet bearing a sequence number from the sequence that
+ establishes the NextExp value can be evaluated to determine whether
+ it is in-order or reordered, based on a previous packet's arrival.
+ In the case where NextExp is Undefined (because the arriving packet
+ is the first successful transfer), the packet is designated in-order
+ (Type-P-Reordered=FALSE).
+
+ This metric assumes reassembly 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. See Appendix B, "Fragment Order
+ Evaluation", for more detail.
+
+
+
+Morton, et al. Standards Track [Page 10]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ If duplicate packets (multiple non-corrupt copies) arrive at the
+ destination, they MUST be noted, 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 IPPM 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 single source sequence number system. When reordering occurs,
+ it is highly desirable to assert the degree to which a packet is
+ 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.1. Reordered Packet Ratio
+
+4.1.1. Metric Name
+
+ Type-P-Reordered-Ratio-Stream
+
+4.1.2. Metric Parameters
+
+ The parameter set includes Type-P-Reordered singleton parameters; the
+ parameters unique to Poisson streams (as in [RFC2330]), periodic
+ streams (as in [RFC3432]), or TCP-like streams (as in [RFC3148]);
+ packet size or size 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 from source to
+ destination
+
+ + 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.
+
+
+
+
+Morton, et al. Standards Track [Page 11]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ + 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.3. Definition
+
+ Given a stream of packets sent from a source to a 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.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.2. Reordering Extent
+
+ This section defines the extent to which packets are reordered and
+ associates a specific sequence discontinuity with each reordered
+ packet. This section inherits the Parameters defined above.
+
+4.2.1. Metric Name
+
+ Type-P-Packet-Reordering-Extent-Stream
+
+4.2.2. Notation and Metric Parameters
+
+ Recall that K is the number of packets in the stream at the source,
+ and L is the number of packets received at the 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] represent the original sequence numbers
+ associated with the packets in order of arrival.
+
+
+
+Morton, et al. Standards Track [Page 12]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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, any source
+ 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.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 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 (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.
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 13]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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
+ Section 4.4 on Reordering Byte Offset and the 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 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
+ Section 3.
+
+4.3.1. Metric Name
+
+ Type-P-Packet-Late-Time-Stream
+
+4.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 below
+
+
+
+
+
+Morton, et al. Standards Track [Page 14]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+4.3.3. Definition
+
+ Lateness in time is calculated using destination times. When
+ received packet s[i] is reordered and has a reordering extent e,
+ then:
+
+ LateTime(s[i]) = DstTime(i)-DstTime(i-e)
+
+ Alternatively, using similar notation to that of Section 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.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 the one-way IP Packet Delay Variation (IPDV) [RFC3393]
+ gives the delay variation for a packet 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 the source 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 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.
+
+
+
+Morton, et al. Standards Track [Page 15]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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
+ cumulative distribution function (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.
+ 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:
+
+ + ByteOffset(s[i]), the offset of packet s[i] in bytes
+
+4.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:
+
+ * The 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]
+
+
+
+Morton, et al. Standards Track [Page 16]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+
+4.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 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 Names
+
+ Type-P-Packet-Reordering-Gap-Stream
+ Type-P-Packet-Reordering-GapTime-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:
+
+ + 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
+ seconds
+
+4.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].
+
+
+
+
+
+Morton, et al. Standards Track [Page 17]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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 in Section 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.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:
+
+ the 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']) (and GapTime(s[j']) ) for packet s[j'] is 0.
+
+4.5.5. Discussion
+
+ When separate reordering discontinuities can be distinguished, a
+ 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
+
+
+
+
+
+Morton, et al. Standards Track [Page 18]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ sample's reordering discontinuities may be expressed as a histogram
+ to easily summarize the frequency of various gaps. Reporting the
+ mode, average, range, 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-Free Runs
+
+ This section defines a metric based on a count of consecutive
+ in-order packets between reordered packets.
+
+4.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-Stream
+
+4.6.2. Parameters
+
+ We use the same parameters defined 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 counted
+
+4.6.3. Definition
+
+ As packets in a sample arrive at the 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. A pseudo-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 */
+
+
+
+Morton, et al. Standards Track [Page 19]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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-order 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
+ indicate 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 the Reordering-Free
+ runs from the average by comparing q/a to a/x ((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 run lengths;
+ therefore, a key application of this metric is network evaluation.
+
+ For 36 packets with 3 runs of 11 in-order packets, we have:
+
+ p = 36
+ x = 3
+ a = 33
+ q = 3 * (11*11) = 363
+ ave. reordering-free run = 11
+ q/a = 11
+ (q/a)/(a/x) = 1.0
+
+ For 36 packets with 3 runs, 2 runs of length 1, and one of length 31,
+ we have:
+
+
+
+Morton, et al. Standards Track [Page 20]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ p = 36
+ x = 3
+ a = 33
+ q = 1 + 1 + 961 = 963
+ ave. 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 (in Section 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.1. Metric Name
+
+ Type-P-Packet-n-Reordering-Stream
+
+5.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.
+
+
+
+
+
+Morton, et al. Standards Track [Page 21]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+5.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: If, by this definition, a packet is n-reordered and 0 < n' <
+ n, then the packet is also n'-reordered.
+
+ Note: This definition is illustrated by C code in Appendix A. The
+ code determines and reports the n-reordering for n from 1 to a
+ specified parameter (MAXN in the code, set to 100). The value of n
+ conjectured to be relevant for TCP is the TCP duplicate ACK threshold
+ (set to the value of 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 of a sample is m/l, where m
+ is the number of n-reordered packets in the sample.
+
+ Definition 3: The degree of monotonic reordering of a 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 is 0 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.
+
+
+
+Morton, et al. Standards Track [Page 22]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ - 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 a 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 the 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 use periodic
+ streams as in [RFC3432]
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 23]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ It is acceptable to report the metrics of Sections 3 and 4 with other
+ IPPM metrics using Poisson streams [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 interval
+ in order to maintain a known temporal bias and allow simplified
+ results analysis (as described in [RFC3432]). In this case, it is
+ RECOMMENDED that the periodic sending interval 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 an 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, the
+ NextExp value cannot decrease, and all packets received after a
+ rollover would be declared reordered. Sequence number rollover can
+ be avoided by using combinations of counter size and test duration
+ where rollover 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-term testing).
+ The elements of mitigation are:
+
+ 1. There must be a test to detect if a rollover 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 as rollover.
+
+
+
+
+Morton, et al. Standards Track [Page 24]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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
+ rollover 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
+ will be limited ability to determine 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 declared 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.
+
+
+
+
+
+Morton, et al. Standards Track [Page 25]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+6.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 a source-destination path, recognizing that intermediate
+ measurements may differ from those made at the destination (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, 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 avoid 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.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,...
+
+
+
+
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 26]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ Table 1: Example with Packet 4 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
+ 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 the source.
+ NextExp The value of NextExp when the packet arrived (before
+ update).
+ SrcTime Packet time stamp at the source, ms.
+ DstTime Packet time stamp at the 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 the destination.
+ Byte Offset The byte 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 of 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.
+
+
+
+Morton, et al. Standards Track [Page 27]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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 of Section 5.1, Packet 4 is designated
+ 4-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) 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
+ /\ /\
+
+
+
+
+
+Morton, et al. Standards Track [Page 28]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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 of Section 5, Packet 5 is designated
+ 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 29]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+7.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, 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.
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 30]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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 same result 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 singleton Type-P-Reordered =
+ TRUE for Packets 5 and 6, and they are all associated with a single
+ reordering discontinuity).
+
+7.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 values are computed after the packet 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.
+
+
+
+Morton, et al. Standards Track [Page 31]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+8. Security Considerations
+
+8.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 for denial-of-service attacks directed at
+ destination and/or the intervening network(s).
+
+ Administrators of the source, destination, and intervening network(s)
+ should establish bilateral or multilateral 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.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.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., 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 injected 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
+
+
+
+
+
+Morton, et al. Standards Track [Page 32]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ in [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 memo have been registered in the IANA IPPM
+ METRICS REGISTRY as described in initial version of the registry
+ [RFC4148].
+
+ IANA has registered the following metrics in the IANA-IPPM-METRICS-
+ REGISTRY-MIB:
+
+ ietfReorderedSingleton OBJECT-IDENTITY
+ STATUS current
+ DESCRIPTION
+ "Type-P-Reordered"
+ REFERENCE
+ "Reference RFC 4737, Section 3"
+ ::= { ianaIppmMetrics 34 }
+
+ ietfReorderedPacketRatio OBJECT-IDENTITY
+ STATUS current
+ DESCRIPTION
+ "Type-P-Reordered-Ratio-Stream"
+ REFERENCE
+ "Reference RFC 4737, Section 4.1"
+ ::= { ianaIppmMetrics 35 }
+
+ ietfReorderingExtent OBJECT-IDENTITY
+ STATUS current
+ DESCRIPTION
+ "Type-P-Packet-Reordering-Extent-Stream"
+ REFERENCE
+ "Reference RFC 4737, Section 4.2"
+ ::= { ianaIppmMetrics 36 }
+
+ ietfReorderingLateTimeOffset OBJECT-IDENTITY
+ STATUS current
+ DESCRIPTION
+ "Type-P-Packet-Late-Time-Stream"
+ REFERENCE
+ "Reference RFC 4737, Section 4.3"
+ ::= { ianaIppmMetrics 37 }
+
+ ietfReorderingByteOffset OBJECT-IDENTITY
+ STATUS current
+ DESCRIPTION
+
+
+
+Morton, et al. Standards Track [Page 33]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ "Type-P-Packet-Byte-Offset-Stream"
+ REFERENCE
+ "Reference RFC 4737, Section 4.4"
+ ::= { ianaIppmMetrics 38 }
+
+ ietfReorderingGap OBJECT-IDENTITY
+ STATUS current
+ DESCRIPTION
+ "Type-P-Packet-Reordering-Gap-Stream"
+ REFERENCE
+ "Reference RFC 4737, Section 4.5"
+ ::= { ianaIppmMetrics 39 }
+
+ ietfReorderingGapTime OBJECT-IDENTITY
+ STATUS current
+ DESCRIPTION
+ "Type-P-Packet-Reordering-GapTime-Stream"
+ REFERENCE
+ "Reference RFC 4737, Section 4.5"
+ ::= { ianaIppmMetrics 40 }
+
+ ietfReorderingFreeRunx OBJECT-IDENTITY
+ STATUS current
+ DESCRIPTION
+ "Type-P-Packet-Reordering-Free-Run-x-numruns-Stream"
+ REFERENCE
+ "Reference RFC 4737, Section 4.6"
+ ::= { ianaIppmMetrics 41 }
+
+ ietfReorderingFreeRunq OBJECT-IDENTITY
+ STATUS current
+ DESCRIPTION
+ "Type-P-Packet-Reordering-Free-Run-q-squruns-Stream"
+ REFERENCE
+ "Reference RFC 4737, Section 4.6"
+ ::= { ianaIppmMetrics 42 }
+
+ ietfReorderingFreeRunp OBJECT-IDENTITY
+ STATUS current
+ DESCRIPTION
+ "Type-P-Packet-Reordering-Free-Run-p-numpkts-Stream"
+ REFERENCE
+ "Reference RFC 4737, Section 4.6"
+ ::= { ianaIppmMetrics 43 }
+
+ ietfReorderingFreeRuna OBJECT-IDENTITY
+ STATUS current
+ DESCRIPTION
+
+
+
+Morton, et al. Standards Track [Page 34]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ "Type-P-Packet-Reordering-Free-Run-a-accpkts-Stream"
+ REFERENCE
+ "Reference RFC 4737, Section 4.6"
+ ::= { ianaIppmMetrics 44 }
+
+ ietfnReordering OBJECT-IDENTITY
+ STATUS current
+ DESCRIPTION
+ "Type-P-Packet-n-Reordering-Stream"
+ REFERENCE
+ "Reference RFC 4737, Section 5"
+ ::= { ianaIppmMetrics 45 }
+
+10. Normative References
+
+ [RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791, September
+ 1981.
+
+ [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
+ Requirement Levels", BCP 14, RFC 2119, March 1997.
+
+ [RFC2330] Paxson, V., Almes, G., Mahdavi, J., and M. Mathis,
+ "Framework for IP Performance Metrics", RFC 2330, May
+ 1998.
+
+ [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6
+ (IPv6) Specification", RFC 2460, December 1998.
+
+ [RFC3148] Mathis, M. and M. Allman, "A Framework for Defining
+ Empirical Bulk Transfer Capacity Metrics", RFC 3148, July
+ 2001.
+
+ [RFC3432] Raisanen, V., Grotefeld, G., and A. Morton, "Network
+ performance measurement with periodic streams", RFC 3432,
+ November 2002.
+
+ [RFC3763] Shalunov, S. and B. Teitelbaum, "One-way Active
+ Measurement Protocol (OWAMP) Requirements", RFC 3763,
+ April 2004.
+
+ [RFC4148] Stephan, E., "IP Performance Metrics (IPPM) Metrics
+ Registry", BCP 108, RFC 4148, August 2005.
+
+ [RFC4656] Shalunov, S., Teitelbaum, B., Karp, A., Boote, J., and M.
+ Zeckauskas, "A One-way Active Measurement Protocol
+ (OWAMP)", RFC 4656, September 2006.
+
+
+
+
+
+Morton, et al. Standards Track [Page 35]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+11. Informative References
+
+ [Bel02] J. Bellardo and 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, and N. Shectman, "Packet
+ Reordering is Not Pathological Network Behavior," IEEE/ACM
+ Transactions on Networking, vol. 7, no. 6, pp. 789-798,
+ December 1999.
+
+ [Cia00] L. Ciavattone and A. Morton, "Out-of-Sequence Packet
+ Parameter Definition (for Y.1540)", Contribution number
+ T1A1.3/2000-047, October 30, 2000,
+ http://home.comcast.net/~acmacm/IDcheck/0A130470.doc.
+
+ [Cia03] L. Ciavattone, A. Morton, and G. Ramachandran,
+ "Standardized Active Measurements on a Tier 1 IP
+ Backbone," IEEE Communications Mag., pp. 90-97, June 2003.
+
+ [I.356] ITU-T Recommendation I.356, "B-ISDN ATM layer cell
+ transfer performance", March 2000.
+
+ [Jai02] S. 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. Loguinov and H. Radha, "Measurement Study of Low-
+ bitrate Internet Video Streaming", Proceedings of the ACM
+ SIGCOMM Internet Measurement Workshop 2001 November 1-2,
+ 2001, San Francisco, USA.
+
+ [Mat03] M. Mathis, J. Heffner, and R. Reddy, "Web100: Extended TCP
+ Instrumentation for Research, Education and Diagnosis",
+ ACM Computer Communications Review, Vol 33, Num 3, July
+ 2003, http://www.web100.org/docs/mathis03web100.pdf.
+
+ [Pax98] 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.
+
+ [RFC1323] Jacobson, V., Braden, R., and D. Borman, "TCP Extensions
+ for High Performance", RFC 1323, May 1992.
+
+
+
+
+Morton, et al. Standards Track [Page 36]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ [RFC2581] Allman, M., Paxson, V., and W. Stevens, "TCP Congestion
+ Control ", RFC 2581, April 1999.
+
+ [RFC2679] Almes, G., Kalidindi, S., and M. Zekauskas, "A One-way
+ Delay Metric for IPPM", RFC 2679, September 1999.
+
+ [RFC2680] Almes, G., Kalidindi, S., and M. Zekauskas, "A One-way
+ Packet Loss Metric for IPPM", RFC 2680, September 1999.
+
+ [RFC2960] Stewart, R., 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. and P. Chimento, "IP Packet Delay Variation
+ Metric for IP Performance Metrics (IPPM)", RFC 3393,
+ November 2002.
+
+ [RFC4340] Kohler, E., Handley, M., and S. Floyd, "Datagram
+ Congestion Control Protocol (DCCP)", RFC 4340, March 2006.
+
+ [RFC4341] Floyd, S. and E. Kohler, "Profile for Datagram Congestion
+ Control Protocol (DCCP) Congestion Control ID 2: TCP-like
+ Congestion Control", RFC 4341, March 2006.
+
+ [TBABAJ02] T. Banka, 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. Acknowledgements
+
+ 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 performance framework [RFC2330].
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 37]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+Appendix A. 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;
+ }
+
+
+
+Morton, et al. Standards Track [Page 38]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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 */
+
+
+
+Morton, et al. Standards Track [Page 39]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 40]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+Appendix B. Fragment Order Evaluation (Informative)
+
+ Section 3 stated that fragment reassembly is assumed prior to order
+ evaluation, but that similar procedures could be applied prior to
+ reassembly. This appendix gives definitions and procedures to
+ identify reordering in a packet stream that includes fragmentation.
+
+B.1. Metric Name
+
+ The Metric retains the same name, Type-P-Reordered, but additional
+ parameters are required.
+
+ This appendix assumes that the device that divides a packet into
+ fragments sends them according to ascending fragment offset. Early
+ Linux OS sent fragments in reverse order, so this possibility is
+ worth checking.
+
+B.2. Additional Metric Parameters
+
+ + MoreFrag, the state of the More Fragments Flag in the IP header.
+
+ + 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, the next expected fragment offset at the 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.
+
+
+
+
+
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 41]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+B.3. Definition
+
+ The value of Type-P-Reordered is typically false (the packet is
+ in-order) when
+
+ * the sequence number s >= NextExp, AND
+
+ * the fragment offset FragOffset >= NextExpFrag
+
+ However, it is more efficient to define reordered conditions 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.
+ Housekeeping for the new 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 */
+
+
+
+Morton, et al. Standards Track [Page 42]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+ 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.
+
+B.4. Discussion: Notes on Sample Metrics When Evaluating Fragments
+
+ All fragments with the same source sequence number are assigned the
+ same 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.
+
+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.
+
+
+
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 43]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+Authors' 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
+
+
+ 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
+
+
+ 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
+
+
+ Stanislav Shalunov
+ Internet2
+ 1000 Oakbrook DR STE 300
+ Ann Arbor, MI 48104
+ Phone: +1 734 995 7060
+ EMail: 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
+
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 44]
+
+RFC 4737 Packet Reordering Metrics November 2006
+
+
+Full Copyright Statement
+
+ Copyright (C) The IETF 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 INTERNET SOCIETY, 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 at
+ ietf-ipr@ietf.org.
+
+Acknowledgement
+
+ Funding for the RFC Editor function is currently provided by the
+ Internet Society.
+
+
+
+
+
+
+Morton, et al. Standards Track [Page 45]
+