draft-ietf-ippm-reordering-07.txt   draft-ietf-ippm-reordering-08.txt 
Network Working Group A.Morton Network Working Group A.Morton
Internet Draft L.Ciavattone Internet Draft L.Ciavattone
Document: <draft-ietf-ippm-reordering-07.txt> G.Ramachandran Document: <draft-ietf-ippm-reordering-08.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
Consultant Consultant
Packet Reordering Metric for IPPM Packet Reordering Metric for IPPM
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any This document is an Internet-Draft and is subject to all provisions
applicable patent or other IPR claims of which he or she is aware of section 3 of RFC 3667. By submitting this Internet-Draft, each
have been disclosed, and any of which he or she becomes aware will author represents that any applicable patent or other IPR claims of
be disclosed, in accordance with RFC 3668. which he or she is aware have been disclosed, and any of which he or
she becomes aware will be disclosed, in accordance with RFC 3668.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as "work in progress." reference material or to cite them other than as "work in progress."
skipping to change at line 63 skipping to change at line 63
Contents Contents
Status of this Memo................................................1 Status of this Memo................................................1
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....................................................3 2. Introduction....................................................3
2.1 Motivation.....................................................4 2.1 Motivation.....................................................4
2.2 Goals and Objectives...........................................5 2.2 Goals and Objectives...........................................5
3. A Reordered Packet Singleton Metric.............................5 3. A Reordered Packet Singleton Metric.............................6
3.1 Metric Name:...................................................6 3.1 Metric Name:...................................................6
3.2 Metric Parameters:.............................................6 3.2 Metric Parameters:.............................................6
3.3 Definition:....................................................6 3.3 Definition:....................................................7
3.4 Sequence Discontinuity Definition..............................7 3.4 Sequence Discontinuity Definition..............................7
3.5 Evaluation in Time or Byte Order...............................8 3.5 Evaluation of Reordering in Dimensions of Time or Bytes........8
3.6 Discussion.....................................................8 3.6 Discussion.....................................................8
4. Sample Metrics..................................................8 4. Sample Metrics..................................................9
4.1 Reordered Packet Ratio.........................................9 4.1 Reordered Packet Ratio.........................................9
4.1.1 Metric Name:.................................................9 4.1.1 Metric Name:.................................................9
4.1.2 Metric Parameters:...........................................9 4.1.2 Metric Parameters:...........................................9
4.1.3 Definition:..................................................9 4.1.3 Definition:..................................................9
4.1.4 Discussion...................................................9 4.1.4 Discussion...................................................9
4.2 Reordering Extent..............................................9 4.2 Reordering Extent.............................................10
4.2.1 Metric Name:................................................10 4.2.1 Metric Name:................................................10
4.2.2 Parameter Notation:.........................................10 4.2.2 Parameter Notation:.........................................10
4.2.3 Definition:.................................................10 4.2.3 Definition:.................................................10
4.2.4 Discussion:.................................................10 4.2.4 Discussion:.................................................11
4.3 Reordering Late Time Offset...................................11 4.3 Reordering Late Time Offset...................................11
4.3.1 Metric Name:................................................11 4.3.1 Metric Name:................................................11
4.3.2 Metric Parameters:..........................................11 4.3.2 Metric Parameters:..........................................11
4.3.3 Definition:.................................................11 4.3.3 Definition:.................................................11
4.3.4 Discussion..................................................12 4.3.4 Discussion..................................................12
4.4 Reordering Byte Offset........................................12 4.4 Reordering Byte Offset........................................12
4.4.1 Metric Name:................................................12 4.4.1 Metric Name:................................................12
4.4.2 Metric Parameters:..........................................12 4.4.2 Metric Parameters:..........................................12
4.4.3 Definition:.................................................12 4.4.3 Definition:.................................................12
4.4.4 Discussion..................................................13 4.4.4 Discussion..................................................13
4.5 Gaps between multiple Reordering Discontinuities..............13 4.5 Gaps between multiple Reordering Discontinuities..............13
4.5.1 Metric Name:................................................13 4.5.1 Metric Name:................................................13
4.5.2 Parameters:.................................................13 4.5.2 Parameters:.................................................13
4.5.3 Definition of Reordering Discontinuity:.....................13 4.5.3 Definition of Reordering Discontinuity:.....................13
4.5.4 Definition of Reordering Gap:...............................13 4.5.4 Definition of Reordering Gap:...............................14
4.5.5 Discussion..................................................14 4.5.5 Discussion..................................................14
4.6 Reordering-free Runs..........................................14 4.6 Reordering-free Runs..........................................14
4.6.1 Metric Name:................................................14 4.6.1 Metric Name:................................................15
4.6.2 Parameters:.................................................14 4.6.2 Parameters:.................................................15
4.6.3 Definition:.................................................15 4.6.3 Definition:.................................................15
4.6.4 Discussion:.................................................15 4.6.4 Discussion:.................................................16
5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..16 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..16
5.1 Metric Name:..................................................16 5.1 Metric Name:..................................................16
5.2 Parameter Notation:...........................................16 5.2 Parameter Notation:...........................................17
5.3 Definitions...................................................16 5.3 Definitions...................................................17
5.4 Discussion:...................................................17 5.4 Discussion:...................................................17
6. Measurement and Implementation Issues..........................18 6. Measurement and Implementation Issues..........................18
7. Examples of Arrival Order Evaluation...........................20 7. Examples of Arrival Order Evaluation...........................20
7.1 Example with a single packet reordered........................20 7.1 Example with a single packet reordered........................21
7.2 Example with two packets reordered............................22 7.2 Example with two packets reordered............................22
7.3 Example with three packets reordered..........................23 7.3 Example with three packets reordered..........................23
7.4 Example with Multiple Packet Reordering Discontinuities.......24 7.4 Example with Multiple Packet Reordering Discontinuities.......25
8. Security Considerations........................................24 8. Security Considerations........................................25
8.1 Denial of Service Attacks.....................................24 8.1 Denial of Service Attacks.....................................25
8.2 User data confidentiality.....................................25 8.2 User data confidentiality.....................................25
8.3 Interference with the metric..................................25 8.3 Interference with the metric..................................26
9. IANA Considerations............................................25 9. IANA Considerations............................................26
10. Normative References..........................................25 10. Normative References..........................................26
11. Informative References........................................25 11. Informative References........................................26
12. Acknowledgments...............................................26 12. Acknowledgments...............................................27
13. Appendix A Example Implementations in C (Informative).........27 13. Appendix A Example Implementations in C (Informative).........28
14. Appendix B Fragment Order Evaluation (Informative)............29 14. Appendix B Fragment Order Evaluation (Informative)............30
14.1 Metric Name:.................................................29 14.1 Metric Name:.................................................30
14.2 Additional Metric Parameters:................................29 14.2 Additional Metric Parameters:................................30
14.3 Definition:..................................................30 14.3 Definition:..................................................31
14.4 Discussion: Notes on Sample Metrics when evaluating Fragments31 14.4 Discussion: Notes on Sample Metrics when evaluating Fragments32
15. Author's Addresses............................................31 15. Author's Addresses............................................32
Full Copyright Statement..........................................32 Full Copyright Statement..........................................33
Intellectual Property.............................................32 Intellectual Property.............................................33
Acknowledgement...................................................33 Acknowledgement...................................................34
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 RFC 2119 [1]. document are to be interpreted as described in RFC 2119 [RFC2119].
Although RFC 2119 was written with protocols in mind, the key words Although RFC 2119 was written with protocols in mind, the key words
are used in this document for similar reasons. They are used to are used in this document for similar reasons. They are used to
ensure the results of measurements from two different ensure the results of measurements from two different
implementations are comparable, and to note instances when an implementations are comparable, and to note instances when an
implementation could perturb the network. implementation could perturb the network.
2. Introduction 2. Introduction
Ordered delivery is a property of successful packet transfer Ordered arrival is a property found in packets that successfully
attempts, where the packet sequence ascends for each arriving packet transit their path, where the packet sequence number increases with
and there are no backward steps. each new arrival and there are no backward steps. Internet Protocol
[RFC791] has no mechanisms to assure either packet delivery or
sequencing, and other protocols should be prepared to deal with both
loss and reordering. This memo defines reordering metrics.
An explicit sequence number, such as an incrementing message number A unique sequence number, such as an incrementing message number
or the packet sending time carried in each packet, establishes the carried in each packet, 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.
This metric is consistent with RFC 2330 [2], and classifies arriving This metric is consistent with RFC 2330 [RFC2330], and classifies
packets with sequence numbers smaller than their predecessors as arriving packets with sequence numbers smaller than their
out-of-order, or reordered. For example, if sequentially numbered predecessors as out-of-order, or reordered. For example, if
packets arrive 1,2,4,5,3, then packet 3 is reordered. This is sequentially numbered packets arrive 1,2,4,5,3, then packet 3 is
equivalent to Paxon's reordering definition in [3], where "late" reordered. This is equivalent to Paxon's reordering definition in
packets were declared reordered. The alternative is to emphasize [Pax98], where "late" packets were declared reordered. The
"premature" packets instead (4 and 5 in the example), but only the alternative is to emphasize "premature" packets instead (4 and 5 in
arrival of packet 3 distinguishes this circumstance from packet the example), but only the arrival of packet 3 distinguishes this
loss. Focusing attention on late packets allows us to maintain circumstance from packet loss. Focusing attention on late packets
orthogonality with the packet loss metric. The metric's construction allows us to maintain orthogonality with the packet loss metric. The
is very similar to the sequence space validation for received metric's construction is very similar to the sequence space
segments in RFC793 [4]. Earlier work to define ordered delivery validation for received segments in RFC 793 [RFC793]. Earlier work
includes [5], [6], [7], [8], [9] and [10]. to define ordered delivery includes [Cia00], [Ben99], [Lou01],
[Bel02], [Jai02] and [Cia03].
2.1 Motivation 2.1 Motivation
A reordering metric is relevant for most applications, especially A reordering metric is relevant for most applications, especially
when assessing network support for Real-Time media streams. The when assessing network support for Real-Time media streams. The
extent of reordering may be sufficient to cause a received packet to extent of reordering may be sufficient to cause a received packet to
be discarded by functions above the IP layer. be discarded by functions above the IP layer.
Packet order is not expected to change during transfer, but several Packet order may change during transfer, and several specific path
specific path characteristics can cause order to change. characteristics can make reordering more likely.
Examples are: Examples are:
* When two paths, one with slightly longer transfer time, support a * When two paths, one with slightly longer transfer time, support a
single packet stream or flow, then packets traversing the longer single packet stream or flow, then packets traversing the longer
path may arrive out-of-order. Multiple paths may be used to path may arrive out-of-order. Multiple paths may be used to
achieve load balancing, or may arise from route instability. achieve load balancing, or may arise from route instability.
* To increase capacity, a network device designed with multiple * To increase capacity, a network device designed with multiple
processors serving a single port may reorder as a byproduct. processors serving a single port may reorder as a byproduct.
* A layer 2 retransmission protocol that compensates for an error- * A layer 2 retransmission protocol that compensates for an error-
prone link may cause packet reordering. prone link may cause packet reordering.
skipping to change at line 207 skipping to change at line 210
continuously, then reordering may be present on a steady-state continuously, then reordering may be present on a steady-state
basis. The steady-state reordering condition typically causes an basis. The steady-state reordering condition typically causes an
appreciable fraction of packets to be reordered. This form of appreciable fraction of packets to be reordered. This form of
reordering is most easily detected by minimizing the spacing between reordering is most easily detected by minimizing the spacing between
test packets. Transient reordering may occur in response to network test packets. Transient reordering may occur in response to network
instability; temporary routing loops can cause periods of extreme instability; temporary routing loops can cause periods of extreme
reordering. This condition is characterized by long in-order streams reordering. This condition is characterized by long in-order streams
with occasional instances of reordering, sometimes with extreme with occasional instances of reordering, sometimes with extreme
correlation. However, we do not expect packet delivery in a correlation. However, we do not expect packet delivery in a
completely random order, where for example, the last packet or the completely random order, where for example, the last packet or the
first packet in a sample is equally likely to arrive at the first packet in a sample is equally likely to arrive first at the
destination first. Thus we expect at least a minimal degree of order destination. Thus we expect at least a minimal degree of order in
in the packet arrivals, as exhibited in real networks. the packet arrivals, as exhibited in real networks.
The ability to restore order at the destination will likely have The ability to restore order at the destination will likely have
finite limits. Practical hosts have receiver buffers with finite finite limits. Practical hosts have receiver buffers with finite
size in terms of packets, bytes, or time (such as de-jitter size in terms of packets, bytes, or time (such as de-jitter
buffers). Once the initial determination of reordering is made, it buffers). Once the initial determination of reordering is made, it
is useful to quantify the extent of reordering, or lateness, in all is useful to quantify the extent of reordering, or lateness, in all
meaningful dimensions. meaningful dimensions.
2.2 Goals and Objectives 2.2 Goals and Objectives
The definitions below intend to satisfy the goals of: The definitions below intend to satisfy the goals of:
1. Determining whether or not packet reordering has occurred. 1. Determining whether or not packet reordering has occurred.
2. Quantifying the degree of reordering (achieving this second 2. Quantifying the degree of reordering (achieving this second
goal requires assumptions of upper layer functions and goal requires assumptions of upper layer functions and
capabilities to restore order, and therefore several capabilities to restore order, and therefore several
solutions). solutions).
Reordering Metrics MUST: Reordering Metrics MUST:
+ have one or more relevant applications, such as receiver design + have one or more applications, such as receiver design or network
or network characterization. characterization, and a compelling relevance in the working
group's view.
+ be computable "on the fly" + be computable "on the fly"
+ work with Poisson and Periodic test streams
+ work even if the stream has duplicate or lost packets + work even if the stream has duplicate or lost packets
It is desirable for Reordering Metrics to have one or more of the It is desirable for Reordering Metrics to have one or more of the
following attributes: following attributes:
+ have concatenating results for segments measured separately + concatenating results for segments measured separately
+ have simplicity for easy consumption and understanding + simplicity for easy consumption and understanding
+ have relevance to TCP performance + relevance to TCP performance
+ have relevance to Real-time application performance + relevance to Real-time application performance
The current set of metrics meet all the requirements above, and The current set of metrics meet all the requirements above, and
provides all but the concatenation attribute (except in the case provides all but the concatenation attribute (except in the case
where segments exhibit no reordering, and one may estimate that the where segments exhibit no reordering, and one may estimate that the
segment concatenation would also exhibit this desirable outcome). segment concatenation would also exhibit this desirable outcome).
However, satisfying these goals limits the set of metrics to those However, satisfying these goals limits the set of metrics to those
that provide some clear insight into network characterization or that provide some clear insight into network characterization or
receiver design, and they are not likely to be exhaustive in their receiver design, and they are not likely to be exhaustive in their
coverage of the applications with respect to packet reordering coverage of the applications with respect to packet reordering
effects. Likewise, additional measurements may be possible. effects. Likewise, additional measurements may be possible.
3. A Reordered Packet Singleton Metric 3. A Reordered Packet Singleton Metric
The IPPM framework RFC 2330 [2] describes the notions of singletons, The IPPM framework RFC 2330 [RFC2330] describes the notions of
samples, and statistics. For easy reference: singletons, 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 a sequence number applied to packets at the source to The first is a sequence number applied to packets at the source to
uniquely identify the order of packet transmission. The sequence uniquely identify the order of packet transmission. The unique
number may be established by a simple message number, a byte stream sequence number may be a simple message number.
number, or it may be the actual time when each packet departs from
the Source.
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). plus 1 (for message numbering).
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.
3.1 Metric Name: 3.1 Metric Name:
skipping to change at line 293 skipping to change at line 294
3.2 Metric Parameters: 3.2 Metric Parameters:
+ Src, the IP address of a host + Src, the IP address of a host
+ Dst, the IP address of a host + Dst, the IP address of a host
+ SrcTime, the time of packet emission from the Source (or wire + SrcTime, the time of packet emission from the Source (or wire
time) time)
+ s, the packet sequence number applied at the Source, in units of + s, the unique packet sequence number applied at the Source, in
messages. units of messages.
+ SrcByte, the packet sequence number applied at the Source, in + SrcByte, the packet sequence number applied at the Source, in
units of payload bytes. units of payload bytes.
+ NextExp, the Next Expected Sequence number at the Destination, in + NextExp, the Next Expected Sequence number at the Destination, in
units of messages, time, or bytes. units of messages, time, or bytes.
+ PayloadSize, the number of bytes contained in the information + PayloadSize, the number of bytes contained in the information
field and referred to when the SrcByte sequence is based on byte field and referred to when the SrcByte sequence is based on byte
transfer. transfer.
skipping to change at line 363 skipping to change at line 364
SequenceDiscontinuty = True; SequenceDiscontinuty = True;
SeqDiscontinutySize = s - NextExp; SeqDiscontinutySize = s - NextExp;
else else
SequenceDiscontinuty = False; SequenceDiscontinuty = False;
NextExp = s + 1; NextExp = s + 1;
Type-P-Reordered = False; Type-P-Reordered = False;
else /* when s < NextExp */ else /* when s < NextExp */
Type-P-Reordered = True; Type-P-Reordered = True;
SequenceDiscontinuty = False; SequenceDiscontinuty = False;
Discontinuities are easiest to detect with message numbering or
payload byte numbering where payload size is constant (and
retransmissions are distinguished), and may be possible with
Periodic Streams and Source Time numbering.
3.5 Evaluation in Time or Byte Order 3.5 Evaluation of Reordering in Dimensions of Time or Bytes
For the alternate sequence dimensions, in-order packets have byte It is possible to use alternate dimensions of time or payload bytes
stream numbers or Source times greater than or equal to the value of to test for reordering in the definition of section 3.3, as long as
NextExp. Each new in-order packet will increase the NextExp to the SrcTimes and SrcBytes are unique and reliable. Sequence
SrcTime plus 1 clock tick when using Source times, or to SrcByte Discontinuities are easily defined and detected with message
plus the payload size plus 1 for byte numbering. In the pseudo-code numbering, however, this is not so in the dimensions of time or
of section 3.3, SrcByte (or SrcTime) replaces the sequence number s, bytes. This is a detractor for the alternate dimensions because the
and we have: Sequence Discontinuity definition plays a key role in the sample
metrics that follow.
if SrcByte >= NextExp then /* packet is in-order */ It is possible to detect Sequence Discontinuities with payload byte
NextExp = SrcByte + PayloadSize + 1; numbering, but only when payload size is constant, and then the byte
Type-P-Reordered = False; numbering adds needless complexity over message numbering.
When using Source time, PayloadSize=0 (or a fixed time increment, if It may be possible to detect Sequence Discontinuities with Periodic
using a reliable periodic packet source). 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 later.
3.6 Discussion 3.6 Discussion
Any arriving packet bearing a sequence number from the sequence that Any arriving packet bearing a sequence number from the sequence that
establishes the Next Expected value can be evaluated to determine establishes the Next Expected value can be evaluated to determine
whether it is in-order or reordered, based on a previous packet's whether it is in-order or reordered, based on a previous packet's
arrival. In the case where Next Expected is Undefined (because the arrival. In the case where Next Expected is Undefined (because the
arriving packet is the first successful transfer), the packet is arriving packet is the first successful transfer), the packet is
designated in-order. designated in-order.
skipping to change at line 431 skipping to change at line 433
4.1 Reordered Packet Ratio 4.1 Reordered Packet Ratio
4.1.1 Metric Name: 4.1.1 Metric Name:
Type-P-Reordered-Ratio-Stream Type-P-Reordered-Ratio-Stream
4.1.2 Metric Parameters: 4.1.2 Metric Parameters:
The parameter set includes Type-P-Reordered singleton parameters, The parameter set includes Type-P-Reordered singleton parameters,
the parameters unique to Poisson or Periodic Streams (as in RFC 2330 the parameters unique to Poisson Streams (as in RFC 2330 [RFC2330],
and RFC3432), plus the following: Periodic Streams (as in RFC 3432 [RFC3432]), or TCP-like Streams (as
in RFC 3148 [RFC3148]), plus 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
4.1.3 Definition: 4.1.3 Definition:
For the packets arriving successfully between T0 and Tf+dT, the For the packets arriving successfully between T0 and Tf+dT, the
skipping to change at line 452 skipping to change at line 455
For the packets arriving successfully between T0 and Tf+dT, the For the packets arriving successfully between T0 and Tf+dT, the
ratio of reordered packets in the sample is ratio of reordered packets in the sample is
(Total of Reordered packets) / (Total packets received) (Total of Reordered packets) / (Total packets received)
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
for a reordering-free sample. for a reordering-free sample.
4.2 Reordering Extent 4.2 Reordering Extent
This section defines the extent to which packets are reordered, and This section defines the extent to which packets are reordered, and
associates a specific sequence discontinuity with each reordered associates a specific sequence discontinuity with each reordered
packet. packet. This section inherits the Parameters defined above.
4.2.1 Metric Name: 4.2.1 Metric Name:
Type-P-packet-Reordering-Extent-Stream Type-P-packet-Reordering-Extent-Stream
4.2.2 Parameter Notation: 4.2.2 Parameter Notation:
Given a stream of packets sent from a source to a destination, let K Given a stream of packets sent from a source to a destination, let K
be the total number of packets in that stream. be the total number of packets in that stream.
skipping to change at line 546 skipping to change at line 548
accommodate them. Offset metrics are calculated only on reordered accommodate them. Offset metrics are calculated only on reordered
packets, as identified by the reordered packet singleton metric in packets, as identified by the reordered packet singleton metric in
Section 3. Section 3.
4.3.1 Metric Name: 4.3.1 Metric Name:
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, we In addition to the parameters defined for Type-P-Reordered-Ratio-
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 destination
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 i is reordered, and has a reordering extent e, then: received packet i is reordered, and has a reordering extent e, then:
LateTime(i) = DstTime(i)-DstTime(i-e) LateTime(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
equivalent definition is: equivalent definition is:
LateTime(i) = DstTime(i)-DstTime(j), for min{j|1<=j<i} that LateTime(i) = DstTime(i)-DstTime(j), for min{j|1<=j<i} that
satisfies s[j]>s[i], or SrcTime[j]>SrcTime[i]. satisfies s[j]>s[i].
4.3.4 Discussion 4.3.4 Discussion
The offset metrics can help predict whether reordered packets will The offset metrics can help predict whether reordered packets will
be useful in a general receiver buffer system with finite limits. 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 The limit may be the time of storage prior to a cyclic play-out
instant (as with de-jitter buffers). instant (as with de-jitter buffers).
Note that the One-way IPDV [11] gives the delay variation for a Note that the One-way IPDV [RFC3393] gives the delay variation for a
packet w.r.t. the preceding packet in the source sequence. Lateness packet w.r.t. the preceding packet in the source sequence. Lateness
and IPDV give an indication of whether a buffer at the destination and IPDV give an indication of whether a buffer at the destination
has sufficient storage to accommodate the network's behavior and has sufficient storage to accommodate the network's behavior and
restore order. When an earlier packet in the Source sequence is restore order. When an earlier packet in the Source sequence is
lost, IPDV will necessarily be undefined for adjacent packets, and lost, IPDV will necessarily be undefined for adjacent packets, and
Late Time may provide the only way to evaluate the usefulness of a Late Time may provide the only way to evaluate the usefulness of a
packet. packet.
In the case of de-jitter buffers, there are circumstances where the In the case of de-jitter buffers, there are circumstances where the
receiver employs loss concealment at the intended play-out time of a receiver employs loss concealment at the intended play-out time of a
skipping to change at line 617 skipping to change at line 619
(including the packet at the discontinuity). (including the packet at the discontinuity).
For reordered packet i with a reordering extent e: For reordered packet i with a reordering extent e:
ByteOffset(i) = Sum[in-order packets back to reordering discon.] ByteOffset(i) = Sum[in-order packets back to reordering discon.]
= Sum[PayloadSize(packet at i-1 if in-order), = Sum[PayloadSize(packet at i-1 if in-order),
PayloadSize(packet at i-2 if in-order), ... PayloadSize(packet at i-2 if in-order), ...
PayloadSize(packet at i-e if in-order)] PayloadSize(packet at i-e if in-order)]
4.4.4 Discussion 4.4.4 Discussion
We note that estimates of buffer size due to reordering depend on
greatly on the test stream, in terms of the spacing between test
packets and their size, especially when packet size is variable.
The byte offset metric can help predict whether reordered packets The byte offset metric can help predict whether reordered packets
will be useful in a general receiver buffer system with finite will be useful in a general receiver buffer system with finite
limits. The limit is expressed as the number of bytes the buffer limits. The limit is expressed as the number of bytes the buffer
can store. can store.
When packets in the stream have variable sizes, it may be most When packets in the stream have variable sizes, it may be most
useful to characterize offset in terms of the payload size(s) of useful to characterize offset in terms of the payload size(s) of
stored packets, using the Type-P-packet-Byte-Offset-Stream metric stored packets, using the Type-P-packet-Byte-Offset-Stream metric.
and byte stream numbering.
4.5 Gaps between multiple Reordering Discontinuities 4.5 Gaps between multiple Reordering Discontinuities
4.5.1 Metric Name: 4.5.1 Metric Name:
Type-P-packet-Reordering-Gap-Stream Type-P-packet-Reordering-Gap-Stream
4.5.2 Parameters: 4.5.2 Parameters:
No new parameters. We use the same parameters defined earlier.
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 702 skipping to change at line 708
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 This section defines a metric based on a count of consecutive
packets between reordered packets. packets between reordered packets.
4.6.1 Metric Name: 4.6.1 Metric Name:
Type-P-packet-Reordering-Free-Run-Stream Type-P-packet-Reordering-Free-Run-Stream
4.6.2 Parameters: 4.6.2 Parameters:
We use the same parameters defined earlier, plus the following:
r, the run counter r, the run counter
n, the number of runs n, the number of runs
a, the accumulator of in-order packets a, the accumulator of in-order packets
p, the number of packets p, the number of packets
q, the squared sum of the run counters q, the squared sum of the run counters
4.6.3 Definition: 4.6.3 Definition:
As packets in a sample arrive at the Destination, the count of As packets in a sample arrive at the Destination, the count of
packets to the next reordered packet is a Reordering-Free run. Note packets to the next reordered packet is a Reordering-Free run. Note
skipping to change at line 788 skipping to change at line 792
p = 36 p = 36
n = 3 n = 3
a = 33 a = 33
q = 1 + 1 + 961 = 963 q = 1 + 1 + 961 = 963
ave reordering-free run = 11 ave reordering-free run = 11
q/a = 29.18 q/a = 29.18
(q/a)/ave = 2.65 (q/a)/ave = 2.65
5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric
This section describes a metric that conveys information associated
with the affect 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. RFC 3148 [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 distinguish the case where the Fast Retransmit algorithm is
invoked due to reordering. Additional TCP Kernel Instruments are
summarized in [Mat03].
5.1 Metric Name: 5.1 Metric Name:
Type-P-packet-n-Reordering-Stream Type-P-packet-n-Reordering-Stream
5.2 Parameter Notation: 5.2 Parameter Notation:
Let n be a positive integer (a parameter). Let k be a positive 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 integer equal to the number of packets sent (sample size). Let l be
a non-negative integer representing the number of packets that were a non-negative integer representing the number of packets that were
received out of the k packets sent. (Note that there is no received out of the k packets sent. (Note that there is no
skipping to change at line 869 skipping to change at line 887
A sample's n-reordering may be expressed as a histogram, to A sample's n-reordering may be expressed as a histogram, to
summarize the frequency for each value of n. summarize the frequency for each value of n.
We note that the definition of n-reordering cannot predict the exact We note that the definition of n-reordering cannot predict the exact
number of packets unnecessarily retransmitted by a TCP sender under number of packets unnecessarily retransmitted by a TCP sender under
some circumstances, such as cases with closely-spaced reordered some circumstances, such as cases with closely-spaced reordered
singletons. The definition is less complicated than a TCP singletons. The definition is less complicated than a TCP
implementation where both time and position influence the sender's implementation where both time and position influence the sender's
behavior. behavior.
A packet's n-reordering is sometimes equal to its reordering extent, A packet's n-reordering designation is sometimes equal to its
e. n-reordering is different in the following ways: reordering extent, e. n-reordering is different in the following
ways:
1. n is a count of early packets with consecutive arrival positions 1. n is a count of early packets with consecutive arrival positions
at the receiver. at the receiver.
2. Reordered packets may not be n-reordered, but will have an 2. Reordered packets (Type-P-Reordered=TRUE) may not be n-reordered,
extent, e (see the examples). but will have an extent, e (see the examples).
6. Measurement and Implementation Issues 6. Measurement and Implementation Issues
The results of tests will be dependent on the time interval between The results of tests will be dependent on the time interval between
measurement packets (both at the Source, and during transport where measurement packets (both at the Source, and during transport where
spacing may change). Clearly, packets launched infrequently (e.g., spacing may change). Clearly, packets launched infrequently (e.g.,
1 per 10 seconds) are unlikely to be reordered. 1 per 10 seconds) are unlikely to be reordered.
Test stream designers may prefer to use a periodic sending interval Test stream designers may prefer to use a periodic sending interval
so that a known temporal bias is maintained, also bringing so that a known temporal bias is maintained, also bringing
simplified results analysis (as described in RFC 3432 [12]). In this simplified results analysis (as described in [RFC3432]). In this
case, the periodic sending interval should be chosen to reproduce case, it is RECOMMENDED that the periodic sending interval should be
the closest Source packet spacing expected (down to the link speed chosen to reproduce the closest Source packet spacing expected (down
serialization time limit). Use of the closest possible spacing to the link speed serialization time limit). Use of the closest
should reveal the greatest extent of steady-state reordering on the possible spacing should reveal the greatest extent of steady-state
path. Of course, packet spacing is likely to vary as the stream reordering on the path. Of course, packet spacing is likely to vary
traverses the test path. as the stream traverses the test path. In any case, the exact method
of packet generation MUST be reported with measurement results,
including all stream parameters.
When intending to compare or concatenate 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 Packet lengths might also be varied to attempt to detect instances
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 (sequence number Assuming that the necessary sequence information (sequence number
and/or source time stamp) is included in the packet payload and/or source time stamp) is included in the packet payload
(possibly in application headers such as RTP), packet sequence may (possibly in application headers such as RTP), packet sequence may
be evaluated in a passive measurement arrangement. Also, it is be evaluated in a passive measurement arrangement. Also, it is
possible to evaluate sequence at a single point along a path, since possible to evaluate order at a single point along a path, since the
the usual need for synchronized Src and Dst Clocks may be relaxed to usual need for synchronized Src and Dst Clocks may be relaxed to
some extent. some extent.
When the Src sequence is based on byte stream, or payload numbering, It is possible to apply these metrics to evaluate reordering in a
care must be taken to avoid declaring retransmitted packets TCP sender's stream. In this case, the Source sequence numbers would
reordered. The additional reference of Src Time is one way to avoid 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 either s or SrcTime help to avoid
this ambiguity. this ambiguity.
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
skipping to change at line 975 skipping to change at line 1003
reordered if they arrive. The missing packet list and the largest reordered if they arrive. The missing packet list and the largest
sequence number received thus far (NextExp - 1) are sufficient sequence number received thus far (NextExp - 1) are sufficient
information to determine if a packet is a duplicate (assuming a information to determine if a packet is a duplicate (assuming a
manageable storage size for packets that are missing due to loss). manageable storage size for packets that are missing due to loss).
Some in-order packet arrivals may not be useful to TCP receivers, Some in-order packet arrivals may not be useful to TCP receivers,
due to the receiver window. Sequence Discontinuities and their size due to the receiver window. Sequence Discontinuities and their size
are defined in section 3.4, and this information may be useful to are defined in section 3.4, and this information may be useful to
determine whether a packet is useful or not. determine whether a packet is useful or not.
When in-order packet s arrives and represents a Sequence
Discontinuity,
If
SeqDiscontinutySize >= (number of packets needed to exceed TCP
Receive window)
then s will not be acknowledged until the TCP window fills and
slides over. If s is sufficiently beyond the window and the path is
congested such that intermediate packets never arrive, s will be
discarded and the TCP connection may drop.
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.
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 viewing reordering in all the comparison, and the value of viewing reordering in all the
dimensions of time, bytes, and position. dimensions of time, bytes, and position.
skipping to change at line 1047 skipping to change at line 1065
We can see that when Packet 4 arrives, NextExp=9, and it is declared We can see that when Packet 4 arrives, NextExp=9, and it is declared
reordered. We compute the extent of reordering as follows: reordered. We compute the extent of reordering as follows:
Using the notation <s[1], ..., s[i], ..., s[L]>, the received Using the notation <s[1], ..., s[i], ..., s[L]>, the received
packets are represented as: packets are represented as:
\/ \/
s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10 s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10
i = 1, 2, 3, 4, 5, 6, 7, 8, 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=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=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=5, 6 > 4, so the reordering extent is 3 or more.
when j=4, 5 > 4, so the reordering extent is 4 or more. when j=4, 5 > 4, so the reordering extent is 4 or more.
when j=3, but 3 < 4, and 4 is the maximum extent, e=4 (assuming 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). there are no earlier sequence discontinuities, as in this example).
Further, we can compute the Late Time (210-148=62ms using DstTime) 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 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, 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 also indicate 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 unusual behavior for Packet 4. Also, if Packet 4 had arrived at
least 62ms earlier, it would have been in-order in this example. least 62ms earlier, it would have been in-order in this example.
If all packets contained 100 byte payloads, then Byte Offset is If all packets contained 100 byte payloads, then Byte Offset is
equal to 400 bytes. equal to 400 bytes.
Following the definitions of section 5.1, Packet 4 is defined to be Following the definitions of section 5.1, Packet 4 is designated 4-
4-reordered. reordered.
7.2 Example with two packets reordered 7.2 Example with two packets reordered
Table 2 Example with Packets 5 and 6 Reordered, Table 2 Example with Packets 5 and 6 Reordered,
Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10
s Src Dst Dst Byte Late s Src Dst Dst Byte Late
@Dst NextExp Time Time Delay IPDV Order Offset Time @Dst NextExp Time Time Delay IPDV Order Offset Time
1 1 0 68 68 1 1 1 0 68 68 1
2 2 20 88 68 0 2 2 2 20 88 68 0 2
3 3 40 108 68 0 3 3 3 40 108 68 0 3
skipping to change at line 1095 skipping to change at line 1114
7, so both 5 and 6 are reordered. The Late times (189-188=1, 190- 7, so both 5 and 6 are reordered. The Late times (189-188=1, 190-
188=2) are small. 188=2) are small.
Using the notation <s[1], ..., s[i], ..., s[l]>, the received Using the notation <s[1], ..., s[i], ..., s[l]>, the received
packets are represented as: packets are represented as:
\/ \/ \/ \/
s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10 s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
/\ /\ /\ /\
Considering Packet 5 first: Considering Packet 5 first:
when j=5, 7 > 5, so the reordering extent is 1 or more. when j=5, 7 > 5, so the reordering extent is 1 or more.
when j=4, but 4 < 5, so 1 is its maximum extent, and e=1. when j=4, we have 4 < 5, so 1 is its maximum extent, and e=1.
Considering Packet 6 next: Considering Packet 6 next:
when j=6, 5 < 6, the extent is not yet defined. 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=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. 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 We can also associate each of these reordered packets with a
reordering discontinuity. We find the minimum j=5 (for both packets) 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 according to Section 4.2.3. So Packet 6 is associated with the same
reordering discontinuity as Packet 5, at Packet 7. reordering discontinuity as Packet 5, the Reordering Discontinuity
at Packet 7.
This is a case where reordering extent e would over-estimate the This is a case where reordering extent e would over-estimate the
packet storage required to restore order. Only one packet storage is packet storage required to restore order. Only one packet storage is
required (to hold Packet 7), but e=2 for Packet 6. required (to hold Packet 7), but e=2 for Packet 6.
Following the definitions of section 5, Packet 5 is defined to be 1- Following the definitions of section 5, Packet 5 is designated 1-
reordered, but Packet 6 is not qualified n-reordered. reordered, but Packet 6 is not designated n-reordered.
A hypothetical sender/receiver pair may retransmit Packet 5 A hypothetical sender/receiver pair may retransmit Packet 5
unnecessarily, since it is 1-reordered (in agreement with the unnecessarily, since it is 1-reordered (in agreement with the
singleton metric). Though Packet 6 may not be unnecessarily singleton metric). Though Packet 6 may not be unnecessarily
retransmitted, the receiver cannot advance Packet 7 to the higher retransmitted, the receiver cannot advance Packet 7 to the higher
layers until after Packet 6 arrives. Therefore, the singleton metric layers until after Packet 6 arrives. Therefore, the singleton metric
correctly determined that Packet 6 is reordered. correctly determined that Packet 6 is reordered.
7.3 Example with three packets reordered 7.3 Example with three packets reordered
skipping to change at line 1167 skipping to change at line 1186
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11
We first calculate the n-reordering. Considering Packet 4 first: 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=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=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=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=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. when n=5, 3<=j<8, but 3 < 4, and 4 is the maximum n-reordering.
Considering packet 5[9] next: Considering packet 5[9] next:
when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not designated
when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not qualified
as n-reordered. We find the same to for Packet 6. as n-reordered. We find the same to for Packet 6.
We now consider whether reordered Packets 5 and 6 are associated We now consider whether reordered Packets 5 and 6 are associated
with the same reordering discontinuity as Packet 4. Using the test 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 of Section 4.2.3, we find that the minimum j=4 for all three
packets. They are all associated with the reordering discontinuity packets. They are all associated with the reordering discontinuity
at Packet 7. at Packet 7.
This example shows again that the n-reordering definition identifies This example shows again that the n-reordering definition identifies
a single Packet (4) with a sufficient degree of reordering to result a single Packet (4) with a sufficient degree of reordering to result
in one unnecessary packet retransmission by the New Reno TCP sender. in one unnecessary packet retransmission by the New Reno TCP sender.
Also, the reordered arrival of Packets 5 and 6 will allow the Also, the reordered arrival of Packets 5 and 6 will allow the
receiver process to pass Packets 7 through 10 up the protocol stack receiver process to pass Packets 7 through 10 up the protocol stack
(the singleton metric indicates 5 and 6 are reordered, and they are (the singleton Type-P-Reordered = TRUE for Packets 5 and 6, and they
all associated with a single reordering discontinuity). are all associated with a single reordering discontinuity).
7.4 Example with Multiple Packet Reordering Discontinuities 7.4 Example with Multiple Packet Reordering Discontinuities
Table 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 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
Discontinuity Discontinuity Discontinuity Discontinuity
|---------Gap---------| |---------Gap---------|
s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16 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 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
r = 1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, ... r = 1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, ...
n = 1 2 3 number of runs,n = 1 2 3
end r counts = 5 1 6 end r counts = 5 1 6
Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has 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 e=2. There are two different reordering discontinuities, one at
Packet 6 (where j=4) and one at Packet 12 (where j'=11). Packet 6 (where j=4) and one at Packet 12 (where j'=11).
According to the definition of Reordering Gap According to the definition of Reordering Gap
Gap(j') = (j') - (j) Gap(j') = (j') - (j)
Gap(11) = (11) - (4) = 7 Gap(11) = (11) - (4) = 7
skipping to change at line 1260 skipping to change at line 1279
To discourage the kind of interference mentioned above, packet To discourage the kind of interference mentioned above, packet
interference checks, such as cryptographic hash, may be used. interference checks, such as cryptographic hash, may be used.
9. IANA Considerations 9. IANA Considerations
Since this metric does not define a protocol or well-known values, Since this metric does not define a protocol or well-known values,
there are no IANA considerations in this memo. there are no IANA considerations in this memo.
10. Normative References 10. Normative References
1 Bradner, S., "Key words for use in RFCs to Indicate Requirement [RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791,
Levels", RFC 2119, March 1997. September 1981.
Obtain via: http://www.rfc-editor.org/rfc/rfc791.txt
2 Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., "Framework [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
for IP Performance Metrics", RFC 2330, May 1998. Requirement Levels", RFC 2119, March 1997.
Obtain via: http://www.rfc-editor.org/rfc/rfc2119.txt
[RFC2330] Paxson, V., Almes, G., Mahdavi, J., and Mathis, M.,
"Framework for IP Performance Metrics", RFC 2330, May
1998.
Obtain via: http://www.rfc-editor.org/rfc/rfc2330.txt
[RFC3148] Mathis, M. and Allman, M., "A Framework for Defining
Empirical Bulk Transfer Capacity Metrics", RFC 3148, July
2001.
Obtain via: http://www.rfc-editor.org/rfc/rfc3148.txt
[RFC3432] Raisanen, V., Grotefeld, G., and Morton, A., "Network
performance measurement with periodic streams", RFC 3432,
November 2002.
11. Informative References 11. Informative References
3 V.Paxson, "Measurements and Analysis of End-to-End Internet [Bel02] J.Bellardo and S.Savage, "Measuring Packet Reordering,"
Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997, Proceedings of the ACM SIGCOMM Internet Measurement
ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz. Workshop 2002, November 6-8, Marseille, France.
4 Postel, J., "Transmission Control Protocol", STD 7, RFC 793, [Ben99] J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet
September 1981. Reordering is Not Pathological Network Behavior,"
Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt IEEE/ACM Transactions on Networking, vol.7, no.6, pp.789-
798, December 1999.
5 L.Ciavattone and A.Morton, "Out-of-Sequence Packet Parameter [Cia00] L.Ciavattone and A.Morton, "Out-of-Sequence Packet
Definition (for Y.1540)", Contribution number T1A1.3/2000-047, Parameter Definition (for Y.1540)", Contribution number
October 30, 2000. ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc T1A1.3/2000-047, October 30, 2000.
ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc
6 J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet Reordering is [Cia03] L.Ciavattone, A.Morton, and G.Ramachandran, "Standardized
Not Pathological Network Behavior," IEEE/ACM Transactions on Active Measurements on a Tier 1 IP Backbone," IEEE
Networking, vol.7, no.6, pp.789-798, December 1999. Communications Mag., pp 90-97, June 2003.
7 D.Loguinov and H.Radha, "Measurement Study of Low-bitrate [Jai02] S.Jaiswal et al., "Measurement and Classification of Out-
Internet Video Streaming", Proceedings of the ACM SIGCOMM of-Sequence Packets in a Tier-1 IP Backbone," Proceedings
Internet Measurement Workshop 2001 November 1-2, 2001, San of the ACM SIGCOMM Internet Measurement Workshop 2002,
Francisco, USA. November 6-8, Marseille, France.
8 J.Bellardo and S.Savage, "Measuring Packet Reordering," [Lou01] D.Loguinov and H.Radha, "Measurement Study of Low-bitrate
Proceedings of the ACM SIGCOMM Internet Measurement Workshop Internet Video Streaming", Proceedings of the ACM SIGCOMM
2002, November 6-8, Marseille, France. Internet Measurement Workshop 2001 November 1-2, 2001,
San Francisco, USA.
9 S.Jaiswal et al., "Measurement and Classification of Out-of- [Mat03] M. Mathis, J Heffner and R Reddy, "Web100: Extended TCP
Sequence Packets in a Tier-1 IP Backbone," Proceedings of the ACM Instrumentation for Research, Education and Diagnosis",
SIGCOMM Internet Measurement Workshop 2002, November 6-8, ACM Computer Communications Review, Vol 33, Num 3, July
Marseille, France. 2003. http://www.web100.org/docs/mathis03web100.pdf
10 L.Ciavattone, A.Morton, and G.Ramachandran, "Standardized Active [Pax98] V.Paxson, "Measurements and Analysis of End-to-End
Measurements on a Tier 1 IP Backbone," IEEE Communications Mag., Internet Dynamics," Ph.D. dissertation, U.C. Berkeley,
pp 90-97, June 2003. 1997, ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz.
11 Demichelis, C., and Chimento, P., "IP Packet Delay Variation [RFC793] Postel, J., "Transmission Control Protocol", STD 7, RFC
Metric for IP Performance Metrics (IPPM)", RFC 3393, November 793, September 1981.
2002. Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt
12 Raisanen, V., Grotefeld, G., and Morton, A., "Network performance [RFC3393] Demichelis, C., and Chimento, P., "IP Packet Delay
measurement with periodic streams", RFC 3432, November 2002. Variation Metric for IP Performance Metrics (IPPM)", RFC
3393, November 2002.
12. Acknowledgments 12. Acknowledgments
The authors would like to acknowledge many helpful discussions with The authors would like to acknowledge many helpful discussions with
Matt Zekauskas, Jon Bennett (who authored the sections on Matt Zekauskas, Jon Bennett (who authored the sections on
Reordering-Free Runs), and Matt Mathis. We thank David Newman and Reordering-Free Runs), and Matt Mathis. We thank David Newman, Henk
Henk Uijterwall for their reviews and suggestions, and Michal Uijterwall, and Mark Allman for their reviews and suggestions, and
Przybylski for sharing implementation experiences with us on the Michal Przybylski for sharing implementation experiences with us on
ippm-list. We gratefully acknowledge the foundation laid by the the ippm-list. We gratefully acknowledge the foundation laid by the
authors of the IP performance Framework [2]. authors of the IP performance Framework [RFC2330].
13. Appendix A Example Implementations in C (Informative) 13. Appendix A Example Implementations in C (Informative)
Two example c-code implementations of reordering definitions follow: Two example c-code implementations of reordering definitions follow:
Example 1 n-reordering ============================================ Example 1 n-reordering ============================================
#include <stdio.h> #include <stdio.h>
#define MAXN 100 #define MAXN 100
 End of changes. 

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