draft-ietf-ippm-reordering-12.txt   draft-ietf-ippm-reordering-13.txt 
Network Working Group A.Morton Network Working Group A.Morton
Internet Draft L.Ciavattone Internet Draft L.Ciavattone
Document: <draft-ietf-ippm-reordering-12.txt> G.Ramachandran Document: <draft-ietf-ippm-reordering-13.txt> G.Ramachandran
Category: Standards Track AT&T Labs Category: Standards Track AT&T Labs
S.Shalunov S.Shalunov
Internet2 Internet2
J.Perser J.Perser
Veriwave Veriwave
Packet Reordering Metric for IPPM Packet Reordering Metric for IPPM
Status of this Memo Status of this Memo
skipping to change at line 72 skipping to change at line 72
Copyright Notice...................................................1 Copyright Notice...................................................1
Abstract...........................................................1 Abstract...........................................................1
1. Conventions Used in this Document...............................3 1. Conventions Used in this Document...............................3
2. Introduction....................................................4 2. Introduction....................................................4
2.1 Motivation.....................................................4 2.1 Motivation.....................................................4
2.2 Goals and Objectives...........................................5 2.2 Goals and Objectives...........................................5
2.3 Required Context for All Reordering Metrics....................6 2.3 Required Context for All Reordering Metrics....................6
3. A Reordered Packet Singleton Metric.............................6 3. A Reordered Packet Singleton Metric.............................6
3.1 Metric Name....................................................7 3.1 Metric Name....................................................7
3.2 Metric Parameters..............................................7 3.2 Metric Parameters..............................................7
3.3 Definition.....................................................7 3.3 Definition.....................................................8
3.4 Sequence Discontinuity Definition..............................8 3.4 Sequence Discontinuity Definition..............................8
3.5 Evaluation of Reordering in Dimensions of Time or Bytes........9 3.5 Evaluation of Reordering in Dimensions of Time or Bytes........9
3.6 Discussion.....................................................9 3.6 Discussion.....................................................9
4. Sample Metrics.................................................10 4. Sample Metrics.................................................10
4.1 Reordered Packet Ratio........................................10 4.1 Reordered Packet Ratio........................................10
4.1.1 Metric Name.................................................10 4.1.1 Metric Name.................................................10
4.1.2 Metric Parameters...........................................10 4.1.2 Metric Parameters...........................................10
4.1.3 Definition..................................................10 4.1.3 Definition..................................................11
4.1.4 Discussion..................................................11 4.1.4 Discussion..................................................11
4.2 Reordering Extent.............................................11 4.2 Reordering Extent.............................................11
4.2.1 Metric Name.................................................11 4.2.1 Metric Name.................................................11
4.2.2 Notation and Metric Parameters..............................11 4.2.2 Notation and Metric Parameters..............................11
4.2.3 Definition..................................................12 4.2.3 Definition..................................................12
4.2.4 Discussion..................................................12 4.2.4 Discussion..................................................12
4.3 Reordering Late Time Offset...................................13 4.3 Reordering Late Time Offset...................................13
4.3.1 Metric Name.................................................13 4.3.1 Metric Name.................................................13
4.3.2 Metric Parameters...........................................13 4.3.2 Metric Parameters...........................................13
4.3.3 Definition..................................................13 4.3.3 Definition..................................................14
4.3.4 Discussion..................................................13 4.3.4 Discussion..................................................14
4.4 Reordering Byte Offset........................................14 4.4 Reordering Byte Offset........................................15
4.4.1 Metric Name.................................................14 4.4.1 Metric Name.................................................15
4.4.2 Metric Parameters...........................................14 4.4.2 Metric Parameters...........................................15
4.4.3 Definition..................................................14 4.4.3 Definition..................................................15
4.4.4 Discussion..................................................15 4.4.4 Discussion..................................................15
4.5 Gaps between multiple Reordering Discontinuities..............15 4.5 Gaps between multiple Reordering Discontinuities..............16
4.5.1 Metric Name.................................................15 4.5.1 Metric Names................................................16
4.5.2 Parameters..................................................15 4.5.2 Parameters..................................................16
4.5.3 Definition of Reordering Discontinuity......................16 4.5.3 Definition of Reordering Discontinuity......................16
4.5.4 Definition of Reordering Gap................................16 4.5.4 Definition of Reordering Gap................................16
4.5.5 Discussion..................................................17 4.5.5 Discussion..................................................17
4.6 Reordering-free Runs..........................................17 4.6 Reordering-free Runs..........................................17
4.6.1 Metric Name.................................................17 4.6.1 Metric Names................................................18
4.6.2 Parameters..................................................17 4.6.2 Parameters..................................................18
4.6.3 Definition..................................................17 4.6.3 Definition..................................................18
4.6.4 Discussion and Illustration.................................18 4.6.4 Discussion and Illustration.................................19
5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..19 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..19
5.1 Metric Name...................................................19 5.1 Metric Name...................................................20
5.2 Parameter Notation............................................19 5.2 Parameter Notation............................................20
5.3 Definitions...................................................19 5.3 Definitions...................................................20
5.4 Discussion....................................................20 5.4 Discussion....................................................21
6. Measurement and Implementation Issues..........................21 6. Measurement and Implementation Issues..........................21
7. Examples of Arrival Order Evaluation...........................24 6.1 Passive Measurement Considerations............................24
7.1 Example with a Single Packet Reordered........................24 7. Examples of Arrival Order Evaluation...........................25
7.2 Example with Two Packets Reordered............................25 7.1 Example with a Single Packet Reordered........................25
7.3 Example with Three Packets Reordered..........................27 7.2 Example with Two Packets Reordered............................26
7.4 Example with Multiple Packet Reordering Discontinuities.......28 7.3 Example with Three Packets Reordered..........................28
8. Security Considerations........................................28 7.4 Example with Multiple Packet Reordering Discontinuities.......29
8.1 Denial of Service Attacks.....................................28 8. Security Considerations........................................29
8.2 User Data Confidentiality.....................................29 8.1 Denial of Service Attacks.....................................29
8.3 Interference with the Metric..................................29 8.2 User Data Confidentiality.....................................30
9. IANA Considerations............................................29 8.3 Interference with the Metric..................................30
10. Normative References..........................................31 9. IANA Considerations............................................30
11. Informative References........................................31 10. Normative References..........................................32
12. Acknowledgments...............................................33 11. Informative References........................................33
13. Appendix A Example Implementations in C (Informative).........33 12. Acknowledgments...............................................35
14. Appendix B Fragment Order Evaluation (Informative)............35 13. Appendix A Example Implementations in C (Informative).........35
14.1 Metric Name..................................................36 14. Appendix B Fragment Order Evaluation (Informative)............38
14.2 Additional Metric Parameters.................................36 14.1 Metric Name..................................................38
14.3 Definition...................................................36 14.2 Additional Metric Parameters.................................38
14.4 Discussion: Notes on Sample Metrics when Evaluating Fragments38 14.3 Definition...................................................38
15. Author's Addresses............................................38 14.4 Discussion: Notes on Sample Metrics when Evaluating Fragments40
Full Copyright Statement..........................................39 15. Disclaimer and License........................................40
Intellectual Property.............................................39 16. Author's Addresses............................................40
Acknowledgement...................................................39 Full Copyright Statement..........................................41
Intellectual Property.............................................41
Acknowledgement...................................................42
1. Conventions Used in this Document 1. Conventions Used in this Document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119]. Although document are to be interpreted as described in [RFC2119]. Although
RFC 2119 was written with protocols in mind, the key words are used 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 in this document for similar reasons. They are used to ensure the
results of measurements from two different implementations are results of measurements from two different implementations are
comparable, and to note instances when an implementation could comparable, and to note instances when an implementation could
perturb the network. perturb the network.
In this memo, the characters "<=" should be read as "less than or In this memo, the characters "<=" should be read as "less than or
equal to" and ">=" as "greater than or equal to". equal to" and ">=" as "greater than or equal to".
2. Introduction 2. Introduction
Ordered arrival is a property found in packets that transit their Ordered arrival is a property found in packets that transit their
path, where the packet sequence number increases with each new path, where the packet sequence number increases with each new
arrival and there are no backward steps. The Internet Protocol arrival and there are no backward steps. The Internet Protocol
[RFC791] has no mechanisms to assure either packet delivery or [RFC791] [RFC2640] has no mechanisms to assure either packet
sequencing, and higher layer protocols (above IP) should be prepared delivery or sequencing, and higher layer protocols (above IP) should
to deal with both loss and reordering. This memo defines reordering be prepared to deal with both loss and reordering. This memo defines
metrics. reordering metrics.
A unique sequence identifier carried in each packet, such as an A unique sequence identifier carried in each packet, such as an
incrementing consecutive integer message number, establishes the incrementing consecutive integer message number, establishes the
Source Sequence. Source Sequence.
The detection of reordering at the Destination is based on packet The detection of reordering at the Destination is based on packet
arrival order in comparison with a non-reversing reference value. arrival order in comparison with a non-reversing reference value
[Cia03].
This metric is consistent with [RFC2330], and classifies arriving This metric is consistent with [RFC2330], and classifies arriving
packets with sequence numbers smaller than their predecessors as packets with sequence numbers smaller than their predecessors as
out-of-order, or reordered. For example, if sequentially numbered out-of-order, or reordered. For example, if sequentially numbered
packets arrive 1,2,4,5,3, then packet 3 is reordered. This is packets arrive 1,2,4,5,3, then packet 3 is reordered. This is
equivalent to Paxon's reordering definition in [Pax98], where "late" equivalent to Paxon's reordering definition in [Pax98], where "late"
packets were declared reordered. The alternative is to emphasize packets were declared reordered. The alternative is to emphasize
"premature" packets instead (4 and 5 in the example), but only the "premature" packets instead (4 and 5 in the example), but only the
arrival of packet 3 distinguishes this circumstance from packet arrival of packet 3 distinguishes this circumstance from packet
loss. Focusing attention on late packets allows us to maintain loss. Focusing attention on late packets allows us to maintain
skipping to change at line 308 skipping to change at line 312
samples, and statistics. For easy reference: samples, and statistics. For easy reference:
By a 'singleton' metric, we refer to metrics that are, By a 'singleton' metric, we refer to metrics that are,
in a sense, atomic. For example, a single instance of "bulk in a sense, atomic. For example, a single instance of "bulk
throughput capacity" from one host to another might be defined throughput capacity" from one host to another might be defined
as a singleton metric, even though the instance involves as a singleton metric, even though the instance involves
measuring the timing of a number of Internet packets. measuring the timing of a number of Internet packets.
The evaluation of packet order requires several supporting concepts. The evaluation of packet order requires several supporting concepts.
The first is an algorithm (function) that produces a series of The first is an algorithm (function) that produces a series of
monotonically increasing identifiers applied to packets at the strictly monotonically increasing identifiers applied to packets at
source to uniquely establish the order of packet transmission. The the source to uniquely establish the order of packet transmission
unique sequence identifier may simply be an incrementing consecutive (where a function, g(x), is strictly monotonically increasing if for
integer message number, or sequence number as used below. The any x>y, g(x)>g(y) ). The unique sequence identifier may simply be
prospect of sequence number roll-over is discussed in Section 6. an incrementing consecutive integer message number, or sequence
number as used below. The prospect of sequence number roll-over is
discussed in Section 6.
The second supporting concept is a stored value which is the "next The second supporting concept is a stored value which is the "next
expected" packet number. Under normal conditions, the value of Next expected" packet number. Under normal conditions, the value of Next
Expected (NextExp) is the sequence number of the previous packet Expected (NextExp) is the sequence number of the previous packet
plus 1 for message numbering (in general, the receiver reproduces plus 1 for message numbering (in general, the receiver reproduces
the sender's algorithm and the sequence of identifiers so that the the sender's algorithm and the sequence of identifiers so that the
"next expected" can be determined). "next expected" can be determined).
Each packet within a packet stream can be evaluated with this order Each packet within a packet stream can be evaluated with this order
singleton metric. singleton metric.
skipping to change at line 430 skipping to change at line 437
It is possible to use alternate dimensions of time or payload 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 to test for reordering in the definition of section 3.3, as long as
the SrcTimes and SrcBytes are unique and reliable. Sequence the SrcTimes and SrcBytes are unique and reliable. Sequence
Discontinuities are easily defined and detected with message Discontinuities are easily defined and detected with message
numbering, however, this is not so simple in the dimensions of time numbering, however, this is not so simple in the dimensions of time
or bytes. This is a detractor for the alternate dimensions because or bytes. This is a detractor for the alternate dimensions because
the Sequence Discontinuity definition plays a key role in the sample the Sequence Discontinuity definition plays a key role in the sample
metrics that follow. metrics that follow.
It is possible to detect Sequence Discontinuities with payload byte It is possible to detect Sequence Discontinuities with payload byte
numbering, but only when the complete pattern of payload sizes is numbering, but only when the test device knows exactly what value to
stored at the Destination, or when payload size is constant and then assign as NextExp in response to any packet arrival. This is
the byte numbering adds needless complexity over message numbering. 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 It may be possible to detect Sequence Discontinuities with Periodic
Streams and Source Time numbering, but there are practical pitfalls Streams and Source Time numbering, but there are practical pitfalls
with sending exactly on-schedule and with clock reliability. with sending exactly on-schedule and with clock reliability.
The dimensions of time and bytes remain an important basis for The dimensions of time and bytes remain an important basis for
characterizing the extent of reordering, as described in sections characterizing the extent of reordering, as described in sections
4.3 and 4.4. 4.3 and 4.4.
3.6 Discussion 3.6 Discussion
skipping to change at line 462 skipping to change at line 473
evaluation. In principle, it is possible to use the Type-P-Reordered evaluation. In principle, it is possible to use the Type-P-Reordered
metric to evaluate reordering among packet fragments, but each metric to evaluate reordering among packet fragments, but each
fragment must contain source sequence information. fragment must contain source sequence information.
See the Appendix on fragment order evaluation for more detail. See the Appendix on fragment order evaluation for more detail.
If duplicate packets (multiple non-corrupt copies) arrive at the If duplicate packets (multiple non-corrupt copies) arrive at the
destination, they MUST be noted and only the first to arrive is destination, they MUST be noted and only the first to arrive is
considered for further analysis (copies would be declared reordered considered for further analysis (copies would be declared reordered
according to the definition above). This requirement has the same according to the definition above). This requirement has the same
storage implications as earlier IPPM metrics, and follows the storage implications as earlier IPPM metrics, and follows the
precedent of RFC 2679. We provide a suggestion to minimize storage precedent of [RFC2679]. We provide a suggestion to minimize storage
size needed in Section 6 on Measurement and Implementation Issues. size needed in Section 6 on Measurement and Implementation Issues.
4. Sample Metrics 4. Sample Metrics
In this section, we define metrics applicable to a sample of packets In this section, we define metrics applicable to a sample of packets
from a single Source sequence number system. When reordering occurs, from a single Source sequence number system. When reordering occurs,
it is highly desirable to assert the degree to which a packet is it is highly desirable to assert the degree to which a packet is
out-of-order, or reordered with respect other packets. This section out-of-order, or reordered with respect other packets. This section
defines several metrics that quantify the extent of reordering in defines several metrics that quantify the extent of reordering in
various units of measure. Each metric highlights a relevant use. various units of measure. Each metric highlights a relevant use.
skipping to change at line 496 skipping to change at line 507
The parameter set includes Type-P-Reordered singleton parameters, The parameter set includes Type-P-Reordered singleton parameters,
the parameters unique to Poisson Streams (as in [RFC2330], Periodic the parameters unique to Poisson Streams (as in [RFC2330], Periodic
Streams (as in [RFC3432]), or TCP-like Streams (as in [RFC3148]), Streams (as in [RFC3432]), or TCP-like Streams (as in [RFC3148]),
packet size or size patterns, and the following: packet size or size patterns, and the following:
+ T0, a start time + T0, a start time
+ Tf, an end time + Tf, an end time
+ dT, a waiting time for each packet to arrive + dT, a waiting time for each packet to arrive, in seconds
+ K, the total number of packets in the stream sent from Source to + K, the total number of packets in the stream sent from Source to
Destination Destination
+ L, the total number of packets received (arriving between T0 and + L, the total number of packets received (arriving between T0 and
Tf+dT) out of the K packets sent. Recall that identical copies Tf+dT) out of the K packets sent. Recall that identical copies
(duplicates) have been removed, so L <= K. (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.3 Definition 4.1.3 Definition
Given a stream of packets sent from a Source to a Destination, the Given a stream of packets sent from a Source to a Destination, the
ratio of reordered packets in the sample is ratio of reordered packets in the sample is
(Count of packets with Type-P-Reordered=TRUE) / ( L ) R = (Count of packets with Type-P-Reordered=TRUE) / ( L )
This fraction may be expressed as a percentage (multiply by 100). This fraction may be expressed as a percentage (multiply by 100).
Note that in the case of duplicate packets, only the first copy is Note that in the case of duplicate packets, only the first copy is
used. used.
4.1.4 Discussion 4.1.4 Discussion
When the Type-P-Reordered-Ratio-Stream is zero, no further When the Type-P-Reordered-Ratio-Stream is zero, no further
reordering metrics need be examined for that sample. Therefore, the reordering metrics need be examined for that sample. Therefore, the
value of this metric is its simple ability to summarize the results value of this metric is its simple ability to summarize the results
skipping to change at line 562 skipping to change at line 582
The new parameters are: The new parameters are:
+ i, the index for arrival position, where i-1 represents an + i, the index for arrival position, where i-1 represents an
arrival earlier than i. arrival earlier than i.
+ j, a set of one or more arrival indexes, where 1 <= j < 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. + s[i], the original sequence numbers, s, in order of arrival.
+ e, the Reordering Extent, defined below. + e, the Reordering Extent, in units of packets, defined below.
4.2.3 Definition 4.2.3 Definition
The reordering extent, e, of packet s[i] is defined to be i-j for 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]. the smallest value of j where s[j] > s[i].
Informally, the reordering extent is the maximum distance, in Informally, the reordering extent is the maximum distance, in
packets, from a reordered packet to the earliest packet received packets, from a reordered packet to the earliest packet received
that has a larger sequence number. If a packet is in-order, its that has a larger sequence number. If a packet is in-order, its
reordering extent is undefined. The first packet to arrive is in- reordering extent is undefined. The first packet to arrive is in-
skipping to change at line 601 skipping to change at line 620
larger stream, but L is still the total number of packets received larger stream, but L is still the total number of packets received
out of the K packets sent in that subset. out of the K packets sent in that subset.
If a receiver intends to restore order, then its buffer capacity If a receiver intends to restore order, then its buffer capacity
determines its ability to handle packets that are reordered. For determines its ability to handle packets that are reordered. For
cases with single reordered packets, the extent e gives the number cases with single reordered packets, the extent e gives the number
of packets that must be held in the receiver's buffer while waiting of packets that must be held in the receiver's buffer while waiting
for the reordered packet to complete the sequence. For more complex for the reordered packet to complete the sequence. For more complex
scenarios, the extent may be an overestimate of required storage scenarios, the extent may be an overestimate of required storage
(see section 4.4 on Reordering Byte Offset and the Examples (see section 4.4 on Reordering Byte Offset and the Examples
section). section). 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 Although reordering extent primarily quantifies the offset in terms
of arrival position, it may also be useful for determining the of arrival position, it may also be useful for determining the
portion of reordered packets that can or cannot be restored to order portion of reordered packets that can or cannot be restored to order
in a typical receiver buffer based on their arrival order alone (and in a typical receiver buffer based on their arrival order alone (and
without the aid of retransmission). without the aid of retransmission).
A sample's reordering extents may be expressed as a histogram, to A sample's reordering extents may be expressed as a histogram, to
easily summarize the frequency of various extents. easily summarize the frequency of various extents.
skipping to change at line 632 skipping to change at line 653
Type-P-Packet-Late-Time-Stream Type-P-Packet-Late-Time-Stream
4.3.2 Metric Parameters 4.3.2 Metric Parameters
In addition to the parameters defined for Type-P-Reordered-Ratio- In addition to the parameters defined for Type-P-Reordered-Ratio-
Stream, we specify: Stream, we specify:
+ DstTime, the time that each packet in the stream arrives at the + DstTime, the time that each packet in the stream arrives at the
destination, and may be associated with index i, or packet s[i] destination, and may be associated with index i, or packet s[i]
+ LateTime(s[i]), the offset of packet s[i] in time, defined below + LateTime(s[i]), the offset of packet s[i] in units of seconds,
defined below
4.3.3 Definition 4.3.3 Definition
Lateness in time is calculated using destination times. When Lateness in time is calculated using destination times. When
received packet s[i] is reordered, and has a reordering extent e, received packet s[i] is reordered, and has a reordering extent e,
then: then:
LateTime(s[i]) = DstTime(i)-DstTime(i-e) LateTime(s[i]) = DstTime(i)-DstTime(i-e)
Alternatively, using similar notation to that of section 4.2, an Alternatively, using similar notation to that of section 4.2, an
skipping to change at line 752 skipping to change at line 774
can store. can store.
A sample's ByteOffset results may be expressed as a histogram, to A sample's ByteOffset results may be expressed as a histogram, to
summarize the frequency of buffer lengths needed to accommodate summarize the frequency of buffer lengths needed to accommodate
reordered packets and permit buffer tuning on that basis. A CDF with reordered packets and permit buffer tuning on that basis. A CDF with
buffer size vs. percent of reordered packets accommodated may be buffer size vs. percent of reordered packets accommodated may be
informative. informative.
4.5 Gaps between multiple Reordering Discontinuities 4.5 Gaps between multiple Reordering Discontinuities
4.5.1 Metric Name 4.5.1 Metric Names
Type-P-Packet-Reordering-Gap-Stream Type-P-Packet-Reordering-Gap-Stream
Type-P-Packet-Reordering-GapTime-Stream
4.5.2 Parameters 4.5.2 Parameters
We use the same parameters defined earlier, but add the convention We use the same parameters defined earlier, but add the convention
that index i' is greater than i, likewise j' > j, and define: 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 + Gap(s[j']), the Reordering Gap of packet s[j'] in units of
integer messages integer messages
and the OPTIONAL parameter:
+ GapTime(s[j']), the Reordering Gap of packet s[j'] in units of + GapTime(s[j']), the Reordering Gap of packet s[j'] in units of
time seconds
4.5.3 Definition of Reordering Discontinuity 4.5.3 Definition of Reordering Discontinuity
All reordered packets are associated with a packet at a reordering All reordered packets are associated with a packet at a reordering
discontinuity, defined as the in-order packet s[j] that arrived at 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]. 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 Note that s[j] will have been found to cause a sequence
discontinuity, where s > NextExp when evaluated with the reordered discontinuity, where s > NextExp when evaluated with the reordered
singleton metric as described in section 3.4. singleton metric as described in section 3.4.
skipping to change at line 782 skipping to change at line 807
Note that s[j] will have been found to cause a sequence Note that s[j] will have been found to cause a sequence
discontinuity, where s > NextExp when evaluated with the reordered discontinuity, where s > NextExp when evaluated with the reordered
singleton metric as described in section 3.4. singleton metric as described in section 3.4.
Recall that i - e = min(j). Subsequent reordered packets may be Recall that i - e = min(j). Subsequent reordered packets may be
associated with the same s[j], or with a different discontinuity. associated with the same s[j], or with a different discontinuity.
This fact is used in the definition of the Reordering Gap, below. This fact is used in the definition of the Reordering Gap, below.
4.5.4 Definition of Reordering Gap 4.5.4 Definition of Reordering Gap
A reordering gap is the distance between successive reordering A reordering gap is the distance between successive reordering
discontinuities. Type-P-packet-Reordering-Gap-Stream assigns a value discontinuities. The Type-P-Packet-Reordering-Gap-Stream metric
to (all) packets in a stream. assigns a value for Gap(s[j']) to (all) packets in a stream (and a
value for GapTime(s[j']), when reported).
If: If:
The packet s[j'] is found to be a reordering discontinuity, based The packet s[j'] is found to be a reordering discontinuity, based
on the arrival of reordered packet s[i'] with extent e', and on the arrival of reordered packet s[i'] with extent e', and
an earlier reordering discontinuity s[j], based on the arrival of an earlier reordering discontinuity s[j], based on the arrival of
reordered packet s[i] with extent e was already detected, and reordered packet s[i] with extent e was already detected, and
i' > i, and i' > i, and
there are no reordering discontinuities between j and j', there are no reordering discontinuities between j and j',
then the Reordering Gap for packet s[j'] is the difference between then the Reordering Gap for packet s[j'] is the difference between
the arrival positions the reordering discontinuities, as shown the arrival positions the reordering discontinuities, as shown
below: below:
Gap(s[j']) = (j') - (j) Gap(s[j']) = (j') - (j)
Otherwise: Gaps MAY also be expressed in time:
The Type-P-packet-Reordering-Gap-Stream for the packet is 0. GapTime(s[j']) = DstTime(j') - DstTime(j)
Gaps may also be expressed in time: Otherwise:
GapTime(s[j']) = DstTime(j') - DstTime(j) Gap(s[jí]) (and GapTime(s[j']) ) for packet s[jí] is 0.
4.5.5 Discussion 4.5.5 Discussion
When separate reordering discontinuities can be distinguished, then When separate reordering discontinuities can be distinguished, then
a count may also be reported (along with the discontinuity a count may also be reported (along with the discontinuity
description, such as the number of reordered packets associated with description, such as the number of reordered packets associated with
that discontinuity and their extents and offsets). The Gaps between that discontinuity and their extents and offsets). The Gaps between
a sample's reordering discontinuities may be expressed as a a sample's reordering discontinuities may be expressed as a
histogram, to easily summarize the frequency of various gaps. histogram, to easily summarize the frequency of various gaps.
Reporting the mode, average, range, etc. may also summarize the Reporting the mode, average, range, etc. may also summarize the
skipping to change at line 832 skipping to change at line 857
distributions. distributions.
The Gap metric may help to correlate the frequency of reordering The Gap metric may help to correlate the frequency of reordering
discontinuities with their cause. Gap lengths are also informative discontinuities with their cause. Gap lengths are also informative
to receiver designers, revealing the period of reordering to receiver designers, revealing the period of reordering
discontinuities. The combination of reordering gaps and extent discontinuities. The combination of reordering gaps and extent
reveals whether receivers will be required to handle cases of reveals whether receivers will be required to handle cases of
overlapping reordered packets. overlapping reordered packets.
4.6 Reordering-free Runs 4.6 Reordering-free Runs
This section defines a metric based on a count of consecutive in- This section defines a metric based on a count of consecutive in-
order packets between reordered packets. order packets between reordered packets.
4.6.1 Metric Name 4.6.1 Metric Names
Type-P-Packet-Reordering-Free-Run-Stream 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 4.6.2 Parameters
We use the same parameters defined earlier, and define the We use the same parameters defined earlier, and define the
following: following:
+ r, the run counter + r, the run counter
+ x, the number of runs, also the number of reordered packets + x, the number of runs, also the number of reordered packets
skipping to change at line 1084 skipping to change at line 1109
of parallel processing (they may cause steady state reordering). For of parallel processing (they may cause steady state reordering). For
example, a line-speed burst of the longest (MTU-length) packets example, a line-speed burst of the longest (MTU-length) packets
followed by a burst of the shortest possible packets may be an followed by a burst of the shortest possible packets may be an
effective detecting pattern. Other size patterns are possible. effective detecting pattern. Other size patterns are possible.
The non-reversing order criterion and all metrics described above The non-reversing order criterion and all metrics described above
remain valid and useful when a stream of packets experiences packet remain valid and useful when a stream of packets experiences packet
loss, or both loss and reordering. In other words, losses alone do loss, or both loss and reordering. In other words, losses alone do
not cause subsequent packets to be declared reordered. not cause subsequent packets to be declared reordered.
Assuming that the necessary sequence information (message number) is
included in the packet payload (possibly in application headers such
as RTP), reordering metrics may be evaluated in a passive
measurement arrangement. Also, it is possible to evaluate order at
any point along a Source-Destination path, recognizing that
intermediate measurements may differ from those made at the
Destination (where 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 to avoid this
ambiguity, or the optional TCP timestamp field [RFC1323].
Since this metric definition may use sequence numbers with finite Since this metric definition may use sequence numbers with finite
range, it is possible that the sequence numbers could reach end-of- range, it is possible that the sequence numbers could reach end-of-
range and roll over to zero during a measurement. By definition, range and roll over to zero during a measurement. By definition,
the Next Expected value cannot decrease, and all packets received the Next Expected value cannot decrease, and all packets received
after a roll-over would be declared reordered. Sequence number after a roll-over would be declared reordered. Sequence number
roll-over can be avoided by using combinations of counter size and roll-over can be avoided by using combinations of counter size and
test duration where roll-over is impossible (and sequence is reset test duration where roll-over is impossible (and sequence is reset
to zero at the start). Also, message-based numbering results in to zero at the start). Also, message-based numbering results in
slower sequence consumption. There may still be cases where slower sequence consumption. There may still be cases where
methodological mitigation of this problem is desirable (e.g., long- methodological mitigation of this problem is desirable (e.g., long-
skipping to change at line 1166 skipping to change at line 1174
sample, K, when the sending time for K packets is small with respect sample, K, when the sending time for K packets is small with respect
to the network's largest possible transfer time. Another possible to the network's largest possible transfer time. Another possible
limitation on storage is the maximum length of the sequence number limitation on storage is the maximum length of the sequence number
field, assuming that most test streams do not exhaust this length in field, assuming that most test streams do not exhaust this length in
practice. practice.
Last, we note that determining reordering extents and gaps is tricky Last, we note that determining reordering extents and gaps is tricky
when there are overlapped or nested events. Test instrument when there are overlapped or nested events. Test instrument
complexity and reordering complexity are directly correlated. complexity and reordering complexity are directly correlated.
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 to avoid this
ambiguity in active measurement, or the optional TCP timestamp field
[RFC1323] in passive measurement.
7. Examples of Arrival Order Evaluation 7. Examples of Arrival Order Evaluation
This section provides some examples to illustrate how the non- This section provides some examples to illustrate how the non-
reversing order criterion works, how n-reordering works in reversing order criterion works, how n-reordering works in
comparison, and the value of quantifying reordering in all the comparison, and the value of quantifying reordering in all the
dimensions of time, bytes, and position. dimensions of time, bytes, and position.
Throughout this section, we will refer to packets by their source Throughout this section, we will refer to packets by their source
sequence number, except where noted. So "Packet 4" refers to the sequence number, except where noted. So "Packet 4" refers to the
packet with source sequence number 4, and the reader should refer to packet with source sequence number 4, and the reader should refer to
skipping to change at line 1433 skipping to change at line 1464
8.3 Interference with the Metric 8.3 Interference with the Metric
It may be possible to identify that a certain packet or stream of 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 packets is part of a sample. With that knowledge at the destination
and/or the intervening networks, it is possible to change the and/or the intervening networks, it is possible to change the
processing of the packets (e.g. increasing or decreasing delay) that processing of the packets (e.g. increasing or decreasing delay) that
may distort the measured performance. It may also be possible to may distort the measured performance. It may also be possible to
generate additional packets that appear to be part of the sample generate additional packets that appear to be part of the sample
metric. These additional packets are likely to perturb the results metric. These additional packets are likely to perturb the results
of the sample measurement. 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.
To discourage the kind of interference mentioned above, packet The requirements for data collection resistance to interference by
interference checks, such as cryptographic hash, may be used. 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]. The security considerations sections of the two OWAMP
documents are extensive and should be consulted for additional
details.
9. IANA Considerations 9. IANA Considerations
Metrics defined in this memo SHOULD be registered in the IANA IPPM Metrics defined in this memo are designed to be registered in the
METRICS REGISTRY as described in initial version of the registry IANA IPPM METRICS REGISTRY as described in initial version of the
[RFC4148]. registry [RFC4148].
IANA is asked to register the following metrics in the IANA-IPPM- IANA is asked to register the following metrics in the IANA-IPPM-
METRICS-REGISTRY-MIB (where RFC xxxx is replaced with the number of METRICS-REGISTRY-MIB (where RFC xxxx is replaced with the number of
this memo): this memo):
ietfReorderedSingleton OBJECT-IDENTITY ietfReorderedSingleton OBJECT-IDENTITY
STATUS current STATUS current
DESCRIPTION DESCRIPTION
"Type-P-Reordered" "Type-P-Reordered"
REFERENCE REFERENCE
skipping to change at line 1496 skipping to change at line 1537
::= { ianaIppmMetrics nn } -- IANA assigns nn ::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfReorderingGap OBJECT-IDENTITY ietfReorderingGap OBJECT-IDENTITY
STATUS current STATUS current
DESCRIPTION DESCRIPTION
"Type-P-Packet-Reordering-Gap-Stream" "Type-P-Packet-Reordering-Gap-Stream"
REFERENCE REFERENCE
"Reference RFC xxxx, section 4.5" "Reference RFC xxxx, section 4.5"
::= { ianaIppmMetrics nn } -- IANA assigns nn ::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfReorderingFreeRun OBJECT-IDENTITY ietfReorderingGapTime OBJECT-IDENTITY
STATUS current STATUS current
DESCRIPTION DESCRIPTION
"Type-P-Packet-Reordering-Free-Run-Stream" "Type-P-Packet-Reordering-GapTime-Stream"
REFERENCE
"Reference RFC xxxx, section 4.5"
::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfReorderingFreeRunx OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Free-Run-x-numruns-Stream"
REFERENCE
"Reference RFC xxxx, section 4.6"
::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfReorderingFreeRunq OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Free-Run-q-squruns-Stream"
REFERENCE
"Reference RFC xxxx, section 4.6"
::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfReorderingFreeRunp OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Free-Run-p-numpkts-Stream"
REFERENCE
"Reference RFC xxxx, section 4.6"
::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfReorderingFreeRuna OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Free-Run-a-accpkts-Stream"
REFERENCE REFERENCE
"Reference RFC xxxx, section 4.6" "Reference RFC xxxx, section 4.6"
::= { ianaIppmMetrics nn } -- IANA assigns nn ::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfnReordering OBJECT-IDENTITY ietfnReordering OBJECT-IDENTITY
STATUS current STATUS current
DESCRIPTION DESCRIPTION
"Type-P-Packet-n-Reordering-Stream" "Type-P-Packet-n-Reordering-Stream"
REFERENCE REFERENCE
"Reference RFC xxxx, section 5" "Reference RFC xxxx, section 5"
skipping to change at line 1521 skipping to change at line 1594
10. Normative References 10. Normative References
[RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791, [RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791,
September 1981. September 1981.
Obtain via: http://www.rfc-editor.org/rfc/rfc791.txt Obtain via: http://www.rfc-editor.org/rfc/rfc791.txt
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119, March 1997. Requirement Levels", RFC 2119, March 1997.
Obtain via: http://www.rfc-editor.org/rfc/rfc2119.txt Obtain via: http://www.rfc-editor.org/rfc/rfc2119.txt
[RFC2330] Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., [RFC2330] Paxson, V., Almes, G., Mahdavi, J., and Mathis, M.,
"Framework for IP Performance Metrics", RFC 2330, May "Framework for IP Performance Metrics", RFC 2330, May
1998. 1998.
Obtain via: http://www.rfc-editor.org/rfc/rfc2330.txt Obtain via: http://www.rfc-editor.org/rfc/rfc2330.txt
[RFC2460] Deering, S. and Hinden, R., "Internet Protocol Version 6
(IPv6) Specification", RFC 2460, December 1998.
Obtain via: http://www.rfc-editor.org/rfc/rfc2460.txt
[RFC3148] Mathis, M. and Allman, M., "A Framework for Defining [RFC3148] Mathis, M. and Allman, M., "A Framework for Defining
Empirical Bulk Transfer Capacity Metrics", RFC 3148, July Empirical Bulk Transfer Capacity Metrics", RFC 3148, July
2001. 2001.
Obtain via: http://www.rfc-editor.org/rfc/rfc3148.txt Obtain via: http://www.rfc-editor.org/rfc/rfc3148.txt
[RFC3432] Raisanen, V., Grotefeld, G., and Morton, A., "Network [RFC3432] Raisanen, V., Grotefeld, G., and Morton, A., "Network
performance measurement with periodic streams", RFC 3432, performance measurement with periodic streams", RFC 3432,
November 2002. November 2002.
Obtain via: http://www.rfc-editor.org/rfc/rfc3432.txt Obtain via: http://www.rfc-editor.org/rfc/rfc3432.txt
[RFC3763] Shalunov, S. and 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 [RFC4148] Stephan, E., "IP Performance Metrics (IPPM) Metrics
Registry", RFC 4148, August 2005. Registry", RFC 4148, BCP 108, August 2005.
Obtain via: http://www.rfc-editor.org/rfc/rfc4148.txt Obtain via: http://www.rfc-editor.org/rfc/rfc4148.txt
[RFCyyyy] Shalunov, S., Teitelbaum, B., Karp, A., Boote, J., and
Zeckauskas, M., "One-way Active Measurement Protocol
(OWAMP) Requirements", RFC yyyy, 2006.
Obtain via: http://www.rfc-editor.org/rfc/rfcyyyy.txt
11. Informative References 11. Informative References
[Bel02] J.Bellardo and S.Savage, "Measuring Packet Reordering," [Bel02] J.Bellardo and S.Savage, "Measuring Packet Reordering,"
Proceedings of the ACM SIGCOMM Internet Measurement Proceedings of the ACM SIGCOMM Internet Measurement
Workshop 2002, November 6-8, Marseille, France. Workshop 2002, November 6-8, Marseille, France.
[Ben99] J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet [Ben99] J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet
Reordering is Not Pathological Network Behavior," Reordering is Not Pathological Network Behavior,"
IEEE/ACM Transactions on Networking, vol.7, no.6, pp.789- IEEE/ACM Transactions on Networking, vol.7, no.6, pp.789-
798, December 1999. 798, December 1999.
skipping to change at line 1593 skipping to change at line 1678
[RFC793] Postel, J., "Transmission Control Protocol", STD 7, RFC [RFC793] Postel, J., "Transmission Control Protocol", STD 7, RFC
793, September 1981. 793, September 1981.
Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt
[RFC1323] Jacobson, V., Braden, R., and Borman, D., "TCP Extensions [RFC1323] Jacobson, V., Braden, R., and Borman, D., "TCP Extensions
for High Performance", RFC 1323, May 1992. for High Performance", RFC 1323, May 1992.
[RFC2581] Allman, M., Paxson, V., and Stevens, W., "TCP Congestion [RFC2581] Allman, M., Paxson, V., and Stevens, W., "TCP Congestion
Control", RFC 2581, April 1999. Control", RFC 2581, April 1999.
[RFC2679] Almes, G., Kalidindi, S., and 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 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., "Stream Control Transmission [RFC2960] Stewart, R., et al., "Stream Control Transmission
Protocol", RFC 2960, October 2000. Protocol", RFC 2960, October 2000.
[RFC3393] Demichelis, C., and Chimento, P., "IP Packet Delay [RFC3393] Demichelis, C., and Chimento, P., "IP Packet Delay
Variation Metric for IP Performance Metrics (IPPM)", RFC Variation Metric for IP Performance Metrics (IPPM)", RFC
3393, November 2002. 3393, November 2002.
[RFC4340] Kohler, E., Handley, M. and Floyd, S., "Datagram [RFC4340] Kohler, E., Handley, M. and Floyd, S., "Datagram
Congestion Control Protocol (DCCP)", RFC 4340, March Congestion Control Protocol (DCCP)", RFC 4340, March
2006. 2006.
skipping to change at line 1877 skipping to change at line 1970
14.4 Discussion: Notes on Sample Metrics when Evaluating Fragments 14.4 Discussion: Notes on Sample Metrics when Evaluating Fragments
All fragments with the same Source Sequence Number are assigned the All fragments with the same Source Sequence Number are assigned the
same Source Time. same Source Time.
Evaluation with byte stream numbering may be simplified if the Evaluation with byte stream numbering may be simplified if the
fragment offset is simply added to the SourceByte of the first fragment offset is simply added to the SourceByte of the first
packet (with fragment offset = 0), keeping the 8 octet units of the packet (with fragment offset = 0), keeping the 8 octet units of the
offset in mind. offset in mind.
15. Author's Addresses 15. 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's Addresses
Al Morton Al Morton
AT&T Labs AT&T Labs
Room D3 - 3C06 Room D3 - 3C06
200 Laurel Ave. South 200 Laurel Ave. South
Middletown, NJ 07748 USA Middletown, NJ 07748 USA
Phone +1 732 420 1571 Phone +1 732 420 1571
EMail: <acmorton@att.com> EMail: <acmorton@att.com>
Len Ciavattone Len Ciavattone
 End of changes. 47 change blocks. 
103 lines changed or deleted 210 lines changed or added

This html diff was produced by rfcdiff 1.29, available from http://www.levkowetz.com/ietf/tools/rfcdiff/