draft-ietf-ippm-reordering-05.txt   draft-ietf-ippm-reordering-06.txt 
Network Working Group A.Morton Network Working Group A.Morton
Internet Draft L.Ciavattone Internet Draft L.Ciavattone
Document: <draft-ietf-ippm-reordering-05.txt> G.Ramachandran Document: <draft-ietf-ippm-reordering-06.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
This document is an Internet-Draft and is in full conformance with By submitting this Internet-Draft, each author represents that any
all provisions of Section 10 of RFC2026 [1]. applicable patent or other IPR claims of which he or she is aware
have been disclosed, and any of which he or she becomes aware will
be disclosed, in accordance with RFC 3668.
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. Internet-Drafts are draft documents valid for a maximum of Drafts.
six months and may be updated, replaced, or made obsolete by other
documents at any time. It is inappropriate to use Internet-Drafts as Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as "work in progress." reference material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
Copyright Notice
Copyright (C) The Internet Society (2004).
Abstract Abstract
This memo defines metrics to evaluate if a network has maintained This memo defines metrics to evaluate if a network has maintained
packet order on a packet-by-packet basis. It provides motivations packet order on a packet-by-packet basis. It provides motivations
for the new metrics and discusses the measurement issues. The memo for the new metrics and discusses the measurement issues. The memo
first defines a reordered singleton, and then uses it as the basis first defines a reordered singleton, and then uses it as the basis
for sample metrics to quantify the extent of reordering in several for sample metrics to quantify the extent of reordering in several
useful dimensions. Additional metrics quantify the frequency of useful dimensions for network characterization or receiver design.
reordering and the distance between separate occurrences. We then Additional metrics quantify the frequency of reordering and the
define metrics with a receiver analysis orientation. Several distance between separate occurrences. We then define a metric with
examples of evaluation using the various sample metrics are purely receiver analysis orientation. Several examples of evaluation
included. An Appendix gives extended definitions for evaluating using the various sample metrics are included. An Appendix gives
order with packet fragmentation. extended definitions for evaluating order with packet fragmentation.
Contents
Status of this Memo................................................1
Copyright Notice...................................................1
Abstract...........................................................1
1. Conventions used in this document...............................3
2. Introduction....................................................3
2.1 Motivation.....................................................4
2.2 Goals and Objectives...........................................5
3. A Reordered Packet Singleton Metric.............................5
3.1 Metric Name:...................................................6
3.2 Metric Parameters:.............................................6
3.3 Definition:....................................................6
3.4 Sequence Discontinuity Definition..............................7
3.5 Evaluation in Time or Byte Order...............................7
3.6 Discussion.....................................................8
4. Sample Metrics..................................................8
4.1 Reordered Packet Ratio.........................................8
4.1.1 Metric Name:.................................................9
4.1.2 Metric Parameters:...........................................9
4.1.3 Definition:..................................................9
4.1.4 Discussion...................................................9
4.2 Reordering Extent..............................................9
4.2.1 Metric Name:.................................................9
4.2.2 Parameter Notation:..........................................9
4.2.3 Definition:.................................................10
4.2.4 Discussion:.................................................10
4.3 Reordering Late Time Offset...................................11
4.3.1 Metric Name:................................................11
4.3.2 Metric Parameters:..........................................11
4.3.3 Definition:.................................................11
4.3.4 Discussion..................................................11
4.4 Reordering Byte Offset........................................12
4.4.1 Metric Name:................................................12
4.4.2 Metric Parameters:..........................................12
4.4.3 Definition:.................................................12
4.4.4 Discussion..................................................12
4.5 Gaps between multiple Reordering Discontinuities..............13
4.5.1 Metric Name:................................................13
4.5.2 Parameters:.................................................13
4.5.3 Definition of Reordering Discontinuity:.....................13
4.5.4 Definition of Reordering Gap:...............................13
4.5.5 Discussion..................................................14
4.6 Reordering-free Runs..........................................14
4.6.1 Metric Name:................................................14
4.6.2 Parameters:.................................................14
4.6.3 Definition:.................................................14
4.6.4 Discussion:.................................................15
5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..16
5.1 Metric Name:..................................................16
5.2 Parameter Notation:...........................................16
5.3 Definitions...................................................16
5.4 Discussion:...................................................17
6. Measurement and Implementation Issues..........................17
7. Examples of Arrival Order Evaluation...........................20
7.1 Example with a single packet reordered........................20
7.2 Example with two packets reordered............................21
7.3 Example with three packets reordered..........................22
7.4 Example with Multiple Packet Reordering Discontinuities.......23
8. Security Considerations........................................24
8.1 Denial of Service Attacks.....................................24
8.2 User data confidentiality.....................................24
8.3 Interference with the metric..................................24
9. IANA Considerations............................................25
10. Normative References..........................................25
11. Informative References........................................25
12. Acknowledgments...............................................26
13. Appendix A Example Implementations in C (Informative).........26
14. Appendix B Fragment Order Evaluation (Informative)............28
14.1 Metric Name:.................................................29
14.2 Additional Metric Parameters:................................29
14.3 Definition:..................................................29
14.4 Discussion: Notes on Sample Metrics when evaluating Fragments31
15. Author's Addresses............................................31
Full Copyright Statement..........................................32
Intellectual Property.............................................32
Acknowledgement...................................................32
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 [2]. document are to be interpreted as described in RFC 2119 [1].
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 delivery is a property of successful packet transfer
attempts, where the packet sequence ascends for each arriving packet attempts, where the packet sequence ascends for each arriving packet
and there are no backward steps. and there are no backward steps.
An explicit sequence number, such as an incrementing message number An explicit sequence number, such as an incrementing message number
or the packet sending time carried in each packet, establishes the or the packet sending time 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 [3], and classifies arriving This metric is consistent with RFC 2330 [2], 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 [4], where "late" equivalent to Paxon's reordering definition in [3], 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
orthogonality with the packet loss metric. The metric's construction orthogonality with the packet loss metric. The metric's construction
is very similar to the sequence space validation for received is very similar to the sequence space validation for received
segments in RFC793 [5]. Earlier work to define ordered delivery segments in RFC793 [4]. Earlier work to define ordered delivery
includes [6], [7], [8], [9], [10] and [11. includes [5], [6], [7], [8], [9] and [10].
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 is not expected to change during transfer, but several
specific path characteristics can cause order to change. specific path characteristics can cause order to change.
skipping to change at line 103 skipping to change at line 189
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.
* If for any reason, the packets in a buffer are not serviced in the * If for any reason, the packets in a buffer are not serviced in the
order of their arrival, their order will change. order of their arrival, their order will change.
* If packets in a flow are assigned to multiple buffers (following * If packets in a flow are assigned to multiple buffers (following
evaluation of traffic characteristics, for example), and the evaluation of traffic characteristics, for example), and the
buffers have different occupations and/or service rates, then buffers have different occupations and/or service rates, then
order will likely change. order will likely change.
When one or more of the above path characteristics are present When one or more of the above path characteristics are present
continuously, then reordering may be present on a steady-state continuously, then reordering may be present on a steady-state
basis. Measurements most easily detect this form of reordering when basis. The steady-state reordering condition typically causes an
the spacing between packets is minimized. Transient reordering may appreciable fraction of packets to be reordered. This form of
occur in response to network instability; temporary routing loops reordering is most easily detected by minimizing the spacing between
can cause periods of extreme reordering. test packets. Transient reordering may occur in response to network
instability; temporary routing loops can cause periods of extreme
reordering. This condition is characterized by long in-order streams
with occasional instances of reordering, sometimes with extreme
correlation. However, we do not expect packet delivery in a
completely random order, where for example, the last packet or the
first packet in a sample is equally likely to arrive at the
destination first. Thus we expect at least a minimal degree of order
in the packet arrivals, as exhibited in real networks.
The ability to restore order at the destination will likely have 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 order is maintained. 1. Determining whether or not packet reordering has occurred.
2. Quantifying the extent (achieving this second goal requires 2. Quantifying the degree of reordering (achieving this second
assumptions of upper layer functions and capabilities to goal requires assumptions of upper layer functions and
restore order, and therefore several solutions). capabilities to restore order, and therefore several
solutions).
Reordering Metrics MUST: Reordering Metrics MUST:
+ be relevant to one or more known applications + have one or more relevant applications, such as receiver design
or network characterization.
+ be computable "on the fly" + be computable "on the fly"
+ work with Poisson and Periodic test streams + 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
Reordering Metrics SHOULD: It is desirable for Reordering Metrics to have one or more of the
following attributes:
+ have concatenating results for segments measured separately + have concatenating results for segments measured separately
+ have simplicity for easy consumption and understanding + have simplicity for easy consumption and understanding
+ have relevance to TCP performance + have relevance to TCP performance
+ have relevance to Real-time application performance + have relevance to Real-time application performance
3. A Reordered Packet Singleton Metric 3. A Reordered Packet Singleton Metric
The IPPM framework RFC 2330 [3] describes the notions of singletons, The IPPM framework RFC 2330 [2] describes the notions of singletons,
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 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 sequence
number may be established by a simple message number, a byte stream number may be established by a simple message number, a byte stream
number, or it may be the actual time when each packet departs from number, or it may be the actual time when each packet departs from
the Source. 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:
Type-P-Reordered Type-P-Reordered
3.2 Metric Parameters: 3.2 Metric Parameters:
skipping to change at line 201 skipping to change at line 297
+ 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.
3.3 Definition: 3.3 Definition:
The value of Type-P-Reordered is defined as false if s >= NextExp If a packet is found to be reordered by comparison with the Next
(the packet is in-order). In this case, NextExp is set to s+1. Expected value, its Type-P-Reordered = TRUE; otherwise Type-P-
Reordered = FALSE, as defined below:
The value of Type-P-Reordered is defined as true if s < NextExp (the The value of Type-P-Reordered is defined as TRUE if s < NextExp (the
packet is reordered). In this case, NextExp value does not change. packet is reordered). In this case, NextExp value does not change.
The value of Type-P-Reordered is defined as FALSE if s >= NextExp
(the packet is in-order). In this case, NextExp is set to s+1.
Since the Next Expected value cannot decrease, it provides a non- Since the Next Expected value cannot decrease, it provides a non-
reversing order criterion to identify reordered packets. reversing order criterion to identify reordered packets.
This definition can also be specified in pseudo-code. This definition can also be specified in pseudo-code.
On successful arrival of a packet with sequence number s: On successful arrival of a packet with sequence number s:
if s >= NextExp, /* s is in-order */ if s >= NextExp then /* s is in-order */
then
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
We note that when s = NextExp, the original sequence has been 3.4 Sequence Discontinuity Definition
maintained, and there is no discontinuity present.
3.4 Evaluation in Time or Byte Order Packets with s > NextExp are a special case of in-order delivery.
This condition indicates a sequence discontinuity, either because of
packet loss or reordering. Reordered packets must arrive for the
sequence discontinuity to be defined as a reordering discontinuity
(see section 4).
We define two different states for in-order packets.
When s = NextExp, the original sequence has been maintained, and
there is no discontinuity present.
When s > NextExp, some packets in the original sequence have not yet
arrived, and there is a sequence discontinuity associated with
packet s. The size of the discontinuity is s - NextExp, equal to
the number of packets presently missing, either reordered or lost.
In pseudo-code:
On successful arrival of a packet with sequence number s:
if s >= NextExp, then /* s is in-order */
if s > NextExp then
SequenceDiscontinuty = True;
SeqDiscontinutySize = s - NextExp;
else
SequenceDiscontinuty = False;
NextExp = s + 1;
Type-P-Reordered = False;
else /* when s < NextExp */
Type-P-Reordered = True;
SequenceDiscontinuty = False;
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
For the alternate sequence dimensions, in-order packets have byte For the alternate sequence dimensions, in-order packets have byte
stream numbers or Source times greater than or equal to the value of stream numbers or Source times greater than or equal to the value of
NextExp. Each new in-order packet will increase the NextExp SrcTime NextExp. Each new in-order packet will increase the NextExp to
plus 1 clock tick when using Source times, or to SrcByte plus the SrcTime plus 1 clock tick when using Source times, or to SrcByte
payload size plus 1 for byte numbering. In the pseudo-code above, plus the payload size plus 1 for byte numbering. In the pseudo-code
SrcByte (or SrcTime) replaces the sequence number s, and we have: of section 3.3, SrcByte (or SrcTime) replaces the sequence number s,
and we have:
if SrcByte >= NextExp, /* packet is in-order */ if SrcByte >= NextExp then /* packet is in-order */
then
NextExp = SrcByte + PayloadSize + 1; NextExp = SrcByte + PayloadSize + 1;
Type-P-Reordered = False;
When using Source time, PayloadSize=0 (or a fixed time increment, if When using Source time, PayloadSize=0 (or a fixed time increment, if
using a reliable periodic packet source). using a reliable periodic packet source).
3.5 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.
This metric assumes re-assembly of packet fragments before This metric assumes re-assembly of packet fragments before
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. precedent of RFC 2679. We provide a suggestion to minimize storage
size needed in the section on Measurement and Implementation Issues.
Packets with s > NextExp are a special case of in-order delivery.
This condition indicates a sequence discontinuity, either because of
packet loss or reordering. Reordered packets must arrive for the
sequence discontinuity to be defined as a reordering discontinuity
(see next section). 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.
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. We begin with a simple from a single Source sequence number system. When reordering occurs,
ratio metric indicating the reordered portion of the sample. When it is highly desirable to assert the degree to which a packet is
this ratio is zero, no further reordering metrics are needed for out-of-order, or reordered with respect other packets. This section
that sample. defines several metrics that quantify the extent of reordering in
various units of measure. Each metric highlights a relevant use.
When reordering occurs, it is highly desirable to assert the degree
to which a packet is out-of-order, or reordered with respect other
packets. This section defines several metrics that quantify the
extent of reordering in various units of measure. Each "extent"
metric highlights a relevant use.
The metrics in the sub-sections below have a network The metrics in the sub-sections below have a network
characterization orientation, but also have relevance to receiver characterization orientation, but also have relevance to receiver
design. design where reordering compensation is of interest. We begin with a
simple ratio metric indicating the reordered portion of the sample.
4.1 Reordered Packet Ratio 4.1 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,
skipping to change at line 317 skipping to change at line 441
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
When the Type-P-Reordered-Ratio-Stream is zero, no further
reordering metrics need be examined for that sample. Therefore, the
value of this metric is its simple ability to summarize the results
for a reordering-free sample.
4.2 Reordering Extent 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.
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.
Assign each packet a sequence number, a consecutive integer from 1 Assign each packet a sequence number, a consecutive integer from 1
to K in the order of packet emission. to K in the order of packet transmission (at the source).
Let L be the total number of packets received out of the K packets Let L be the total number of packets received out of the K packets
sent. Recall that identical copies (duplicates) have been removed, sent. Recall that identical copies (duplicates) have been removed,
so L<=K. so L<=K.
Let s[1], s[2], ..., s[L], represent the original sequence numbers Let s[1], s[2], ..., s[L], represent the original sequence numbers
associated with the packets in order of arrival. associated with the packets in order of arrival.
Consider a reordered packet (as identified in section 3) with Consider a reordered packet (as identified in section 3) with
arrival index i and source sequence number s[i]. There exists a set arrival index i and source sequence number s[i]. There exists a set
of indexes j (1<=j<i) such that s[j] > s[i]. of indexes j (1<=j<i) such that s[j] > s[i].
4.2.3 Definition: 4.2.3 Definition:
The reordering extent, e, of packet s[i] is defined to be The reordering extent, e, of packet s[i] is defined to be
i-j for the smallest value of j. i-j for the smallest value of j when 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-
order by definition, and has undefined reordering extent. order by definition, and has undefined reordering extent.
>>>>>>> Comment on this definition of extent: For some arrival Comment on the definition of extent: For some arrival orders, the
orders, the assignment of a simple position/distance as the assignment of a simple position/distance as the reordering extent
reordering extent tends to overestimate the receiver storage needed tends to overestimate the receiver storage needed to restore order.
to restore order. We need to weigh the value of adding more
complexity in this definition against the accuracy it would provide.
A more accurate and complex procedure to calculate packet storage A more accurate and complex procedure to calculate packet storage
would be to subtract any earlier reordered packets that the receiver would be to subtract any earlier reordered packets that the receiver
could pass on to the upper layers. could pass on to the upper layers. With the bias understood, this
Those who desire "on-the-fly" calculation must assess whether such a definition is deemed sufficient, especially for those who demand "on
procedure is feasible. the fly" calculations.
4.2.4 Discussion: 4.2.4 Discussion:
The packet with index j (s[j], identified in the Definition above) The packet with index j (s[j], identified in the Definition above)
is the reordering discontinuity associated with packet with index i is the reordering discontinuity associated with packet with index i
(s[i]). This definition is formalized below. (s[i]). This definition is formalized below.
Note that the K packets in the stream could be some subset of a Note that the K packets in the stream could be some subset of a
larger stream, but L is still the total number of packets received 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.
A receiver must possess storage to restore order to packets that are A receiver must possess storage to restore order to packets that are
reordered. For cases with single reordered packets, the extent e reordered. For cases with single reordered packets, the extent e
gives the number of packets that must be held in the receiver's gives the number of packets that must be held in the receiver's
buffer while waiting for the reordered packet to complete the buffer while waiting for the reordered packet to complete the
sequence. For more complex scenarios, the extent may be an sequence. For more complex scenarios, the extent may be an
overestimate of required storage. See Examples section (specific overestimate of required storage (see the Examples section).
example to be provided).
Knowledge of the reordering extent e is particularly useful for Knowledge of the reordering extent e is particularly useful for
determining the portion of reordered packets that can or cannot be determining the portion of reordered packets that can or cannot be
restored to order in a typical receiver buffer based on their restored to order in a typical receiver buffer based on their
arrival order alone (and without the aid of retransmission). arrival order alone (and 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.
4.3 Reordering Offset 4.3 Reordering Late Time Offset
Any reordered packets can be assigned offset values indicating the Reordered packets can be assigned offset values indicating their
storage in bytes and lateness in terms of buffer time that a lateness in terms of buffer time that a receiver must possess to
receiver must possess to accommodate them. The various offset accommodate them. Offset metrics are calculated only on reordered
metrics are calculated only on reordered packets, as identified by packets, as identified by the reordered packet singleton metric in
the ordered arrival singleton in section 3. Section 3.
4.3.1 Metric Name: Type-P-packet-Late-Time-Stream 4.3.1 Metric Name:
Metric Parameters: In addition to the parameters defined for Type-P- Type-P-packet-Late-Time-Stream
Reordered, we specify:
+ DstTime, the time that each packet in the stream arrives at Dst 4.3.2 Metric Parameters:
Definition: Lateness in time is calculated using Dst times. When In addition to the parameters defined for Type-P-Reordered, we
specify:
+ DstTime, the time that each packet in the stream arrives at the
destination
4.3.3 Definition:
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], or SrcTime[j]>SrcTime[i].
4.3.2 Metric Name: Type-P-packet-Byte-Offset-Stream 4.3.4 Discussion
Metric Parameters: We use the same parameters defined above.
Definition: Byte stream offset is the sum of the payload sizes of
intervening in-order packets between the reordered packet and the
discontinuity (including the packet at the discontinuity).
For reordered packet i with a reordering extent e:
ByteOffset(i) = Sum[in-order packets back to reordering discon.]
= Sum[PayloadSize(packet at i-1 if in-order),
PayloadSize(packet at i-2 if in-order), ...
PayloadSize(packet at i-e if in-order)]
4.3.3 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 number of bytes or packets the buffer can The limit may be the time of storage prior to a cyclic play-out
store, or the time of storage prior to a cyclic play-out instant (as instant (as with de-jitter buffers).
with de-jitter buffers).
Note that the One-way IPDV [12] gives the delay variation for a Note that the One-way IPDV [11] 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 Dst has and IPDV give an indication of whether a buffer at the destination
sufficient storage to accommodate the network's behavior and restore has sufficient storage to accommodate the network's behavior and
order. When an earlier packet in the Src sequence is lost, IPDV will restore order. When an earlier packet in the Source sequence is
necessarily be undefined for adjacent packets, and Late Time may lost, IPDV will necessarily be undefined for adjacent packets, and
provide the only way to evaluate the usefulness of a packet. Late Time may provide the only way to evaluate the usefulness of a
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
late packet. However, if this packet arrives out of order, the Late late packet. However, if this packet arrives out of order, the Late
Time determines whether the packet is still useful. IPDV no longer Time determines whether the packet is still useful. IPDV no longer
applies, because the receiver establishes a new play-out schedule applies, because the receiver establishes a new play-out schedule
with additional buffer delay to accommodate similar events in the with additional buffer delay to accommodate similar events in the
future - this requires very minimal processing. future (this requires very minimal processing).
When packets in the stream have variable sizes, it may be most 4.4 Reordering Byte Offset
useful to characterize Offset in terms of the payload size(s) of
stored packets (using byte stream numbering).
4.4 Gaps between multiple Reordering Discontinuities Reordered packets can be assigned offset values indicating the
storage in bytes that a receiver must possess to accommodate them.
The various offset metrics are calculated only on reordered packets,
as identified by the reordered packet singleton metric in Section 3.
4.4.1 Metric Name: 4.4.1 Metric Name:
Type-P-packet-Byte-Offset-Stream
4.4.2 Metric Parameters:
We use the same parameters defined earlier.
4.4.3 Definition:
Byte stream offset is the sum of the payload sizes of intervening
in-order packets between the reordered packet and the discontinuity
(including the packet at the discontinuity).
For reordered packet i with a reordering extent e:
ByteOffset(i) = Sum[in-order packets back to reordering discon.]
= Sum[PayloadSize(packet at i-1 if in-order),
PayloadSize(packet at i-2 if in-order), ...
PayloadSize(packet at i-e if in-order)]
4.4.4 Discussion
The byte offset metric can help predict whether reordered packets
will be useful in a general receiver buffer system with finite
limits. The limit is expressed as the number of bytes the buffer
can store.
When packets in the stream have variable sizes, it may be most
useful to characterize offset in terms of the payload size(s) of
stored packets, using the Type-P-packet-Byte-Offset-Stream metric
and byte stream numbering.
4.5 Gaps between multiple Reordering Discontinuities
4.5.1 Metric Name:
Type-P-packet-Reordering-Gap-Stream Type-P-packet-Reordering-Gap-Stream
4.4.2 Parameters: 4.5.2 Parameters:
No new parameters. No new parameters.
4.4.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 arrival s[j] at the discontinuity, defined as the in-order packet s[j] that arrived at
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
discontinuity, where s > NextExp when evaluated with the reordered
singleton metric as described in section 3.4.
Recall that i - e = min(j). Subsequent reordered packets may be 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 definition is used in the definition of the Reordering Gap, This definition is used in the definition of the Reordering Gap,
below. below.
4.4.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. Type-P-packet-Reordering-Gap-Stream assigns a value
to (all) packets in a stream. to (all) packets in a stream.
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
skipping to change at line 514 skipping to change at line 674
Gap(j') = (j') - (j) Gap(j') = (j') - (j)
Otherwise: Otherwise:
The Type-P-packet-Reordering-Gap-Stream for the packet is 0. The Type-P-packet-Reordering-Gap-Stream for the packet is 0.
Gaps may also be expressed in time: Gaps may also be expressed in time:
GapTime(j') = DstTime(j') - DstTime(j) GapTime(j') = DstTime(j') - DstTime(j)
4.4.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
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. discontinuities with their cause. Gap lengths are also informative
to receiver designers, revealing the period of reordering
discontinuities. The combination of reordering gaps and extent
reveals whether receivers will be required to handle cases of
overlapping reordered packets.
4.5 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.5.1 Metric Name: 4.6.1 Metric Name:
Type-P-packet-Reordering-Free-Run-Stream Type-P-packet-Reordering-Free-Run-Stream
4.5.2 Parameters: 4.6.2 Parameters:
No new parameters. r, the run counter
n, the number of runs
a, the accumulator of in-order packets
p, the number of packets
q, the squared sum of the run counters
4.5.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
that the minimum run-length is one according to this definition. A that the minimum run-length is one according to this definition. A
pseudo code example follows: pseudo code example follows:
r = 0; /* r is the run counter */ r = 0; /* r is the run counter */
n = 0; /* n is the number of runs */ n = 0; /* n is the number of runs */
a = 0; /* a is the accumulator of in order packets */ a = 0; /* a is the accumulator of in order packets */
p = 0; /* p is the number of packets */ p = 0; /* p is the number of packets */
q = 0; /* q is the squared sum of the run counters */ q = 0; /* q is the squared sum of the run counters */
while(packets arrive with sequence number s) while(packets arrive with sequence number s)
{ {
P++; p++;
if (s >= NextExp) /* s is in-order */ if (s >= NextExp) /* s is in-order */
then r++; then r++;
a++; a++;
else /* s is reordered */ else /* s is reordered */
q+= r*r; q+= r*r;
r = 1; r = 1;
n++; n++;
} }
Each in-order arrival increments the run counter and the accumulator
of in order packets, each reordered packet resets the run counter
after adding it to the accumulator.
Each arrival of a reordered packet yields a new count in the Run Each arrival of a reordered packet yields a new count in the Run
vector. Long runs accompany periods where order was maintained, vector. Long runs accompany periods where order was maintained,
while short runs indicate frequent, or multi-packet reordering. while short runs indicate frequent, or multi-packet reordering.
4.5.4 Discussion: The percent of packets in-order is 100*a/p
Each in-order arrival increments the run counter and the accumulator The average Reordering-Free run length is a/n
of in order packets, each reordered packet resets the run counter
after adding it to the accumulator.
The percent of packets in order is 100*a/p The q counter gives an indication of variation of the Reordering-
Free runs from the average by comparing q/a to a/n ((q/a)/(a/n))
The average in order run length is a/n 4.6.4 Discussion:
The q counter gives an indication of variation of the in order runs Type-P-packet-Reordering-Free-Run-Stream parameters give a brief
from the average by comparing q/a to a/n ((q/a)/(a/n)) summary of the stream's reordering characteristics including the
average reordering-free run length, and the variation of run
lengths, therefore a key application of this metric is network
evaluation.
For example for 36 packets with 3 runs of 11 in-order packets we For example for 36 packets with 3 runs of 11 in-order packets we
have: have:
p = 36 p = 36
n = 3 n = 3
a = 33 a = 33
q = 3 * (11*11) = 363 q = 3 * (11*11) = 363
ave io = 11 ave reordering-free run = 11
q/a = 11 q/a = 11
(q/a)/ave = 1.0 (q/a)/ave = 1.0
For 36 packets with 3 runs, 2 of length 1 and one of length 31 For 36 packets with 3 runs, 2 of length 1 and one of length 31
p = 36 p = 36
n = 3 n = 3
a = 33 a = 33
q = 1 + 1 + 961 = 963 q = 1 + 1 + 961 = 963
ave io = 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. Metric Related to Receiver Assessment 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric
5.1 A TCP-Relevant Metric
5.1.1 Metric Name: 5.1 Metric Name:
Type-P-packet-n-Reordering-Stream Type-P-packet-n-Reordering-Stream
5.1.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
relationship between k and l: on one hand, losses can make l less relationship between k and l: on one hand, losses can make l less
than k; on the other hand, duplicates can make l greater than k.) than k; on the other hand, duplicates can make l greater than k.)
Assign each sent packet a sequence number, 1 to k, in order of Assign each sent packet a sequence number, 1 to k, in order of
packet emission. packet emission.
Let s[1], s[2], ..., s[l] be the original sequence numbers of the Let s[1], s[2], ..., s[l] be the original sequence numbers of the
received packets, in the order of arrival. received packets, in the order of arrival.
5.1.3 Definitions 5.3 Definitions
Definition 1: Received packet number i (n < i <= l), with source Definition 1: Received packet number i (n < i <= l), with source
sequence number s[i], is n-reordered if and only if for all j such sequence number s[i], is n-reordered if and only if for all j such
that i-n <= j < i, s[j] > s[i]. that i-n <= j < i, s[j] > s[i].
Claim: If by this definition, a packet's reordering is n and 0 < n' Claim: If by this definition, a packet's reordering is n and 0 < n'
< n, then the packet is also reordered to the n' extent. < n, then the packet is also reordered to the n' extent.
Note: This definition is illustrated by C code in Appendix A. It Note: This definition is illustrated by C code in Appendix A. It
determines the n-reordering for a value of n=3 (when actually determines the n-reordering for a value of n=3 (when actually
skipping to change at line 638 skipping to change at line 810
that i-n <= j < i, s[j] > s[i]. that i-n <= j < i, s[j] > s[i].
Claim: If by this definition, a packet's reordering is n and 0 < n' Claim: If by this definition, a packet's reordering is n and 0 < n'
< n, then the packet is also reordered to the n' extent. < n, then the packet is also reordered to the n' extent.
Note: This definition is illustrated by C code in Appendix A. It Note: This definition is illustrated by C code in Appendix A. It
determines the n-reordering for a value of n=3 (when actually determines the n-reordering for a value of n=3 (when actually
writing applications that would report the metric, one would writing applications that would report the metric, one would
probably report it for several values of n, such as 1, 2, 3, 4 -- probably report it for several values of n, such as 1, 2, 3, 4 --
and maybe a few more consecutive values). and maybe a few more consecutive values).
This definition does not assign an n to all reordered packets as This definition does not assign an n to all reordered packets as
defined by the singleton metric, in particular when blocks of defined by the singleton metric, in particular when blocks of
successive packets are reordered. (In the arrival sequence successive packets are reordered. (In the arrival sequence
s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only 4 s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only
is n-reordered, with n=3.) packet 4 is n-reordered, with n=3.)
Definition 2: The degree of n-reordering of the sample is m/l. Definition 2: The degree of n-reordering of the sample is m/l, where
m is the number of n-reordered packets in the sample.
Definition 3: The degree of "monotonic reordering" of the sample is Definition 3: The degree of "monotonic reordering" of the sample is
its degree of 1-reordering. its degree of 1-reordering.
Definition 4: A sample is said to have no reordering if its degree Definition 4: A sample is said to have no reordering if its degree
of n-reordering is 0. of n-reordering is 0.
5.1.4 Discussion: 5.4 Discussion:
The degree of n-reordering may be expressed as a percentage, in The degree of n-reordering may be expressed as a percentage, in
which case the number from definition 2 is multiplied by 100. which case the number from Definition 2 is multiplied by 100%.
Knowledge of n-reordering is particularly useful for determining the Knowledge of n-reordering is particularly 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 TCP receiver buffer based on their arrival order alone in a typical TCP receiver buffer based on their arrival order alone
(and without the aid of retransmission). (and without the aid of retransmission).
Important special cases are n=1 and n=3: Important special cases are n=1 and n=3:
- For n=1, absence of 1-reordering means the sequence numbers that - For n=1, absence of 1-reordering means the sequence numbers that
the receiver sees are monotonically increasing with respect to the the receiver sees are monotonically increasing with respect to the
skipping to change at line 688 skipping to change at line 862
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 is sometimes equal to its reordering extent,
e. n-reordering is different in the following ways: e. n-reordering is different in the following ways:
1. n is a count of *adjacent* early packets. 1. n is a count of early packets with consecutive arrival positions
at the receiver.
2. Some reordered packets may not be n-reordered, but will have e 2. Reordered packets may not be n-reordered, but will have an
(see the examples). extent, e (see the examples).
6. Measurement 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 Src, 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 streams may prefer to use a periodic sending interval so that a Test stream designers may prefer to use a periodic sending interval
known temporal bias is maintained, also bringing simplified results so that a known temporal bias is maintained, also bringing
analysis (as described in RFC 3432 [13]). In this case, the periodic simplified results analysis (as described in RFC 3432 [12]). In this
sending interval should be chosen to reproduce the closest Src case, the periodic sending interval should be chosen to reproduce
packet spacing expected. Of course, packet spacing is likely to vary the closest Source packet spacing expected (down to the link speed
as the stream traverses the test path. serialization time limit). Use of the closest possible spacing
<<<<Ed.Note: Is this sufficient? It is a very important should reveal the greatest extent of steady-state reordering on the
consideration. path. Of course, packet spacing is likely to vary as the stream
traverses the test path.
Packet lengths might also be varied to attempt to detect instances
of parallel processing (they may cause steady state reordering). For
example, a line-speed burst of the longest (MTU-length) packets
followed by a burst of the shortest possible packets may be an
effective detecting pattern. Other size patterns are possible.
The non-reversing order criterion and all metrics described above 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
skipping to change at line 753 skipping to change at line 935
2. All sequence numbers used in computations are represented in a 2. All sequence numbers used in computations are represented in a
sufficiently large precision. The numbers have a correction applied sufficiently large precision. The numbers have a correction applied
(equivalent to adding a significant digit) whenever roll-over is (equivalent to adding a significant digit) whenever roll-over is
detected. detected.
3. Reordered packets coincident with sequence numbers reaching end- 3. Reordered packets coincident with sequence numbers reaching end-
of-range must also be detected for proper application of correction of-range must also be detected for proper application of correction
factor. factor.
In practice, there may be limited ability to determine reordering Ideally, the test instrument would have the ability to use all
extent, because the storage for previous packets may be limited. earlier packets at any point in the test stream. In practice, there
Saving only packets that indicate discontinuities (and their arrival will be limited ability to determine reordering extent, due to the
positions) will reduce storage volume. When discarding all stream storage requirements for previous packets. Saving only packets that
information beyond a threshold packet count, the reordering extent indicate discontinuities (and their arrival positions) will reduce
or degree of n-reordering may need to be expressed as greater than storage volume.
the threshold value, and Gap calculations would not be possible.
The requirement to ignore duplicate packets also requires storage. Another solution is to use a sliding history window of packets,
where the window size would be determined by an upper bound on the
useful reordering extent. This bound could be several packets or
several seconds-worth of packets, depending on the intended
analysis. When discarding all stream information beyond the window,
the reordering extent or degree of n-reordering may need to be
expressed as greater than the window length if the reordering
discontinuity information has been discarded, and Gap calculations
would not be possible.
The requirement to ignore duplicate packets also mandates storage.
Here, tracking the sequence numbers of missing packets may minimize Here, tracking the sequence numbers of missing packets may minimize
storage. Missing packets may eventually be declared lost, or storage size. Missing packets may eventually be declared lost, or
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 are sufficient information to sequence number received thus far (NextExp - 1) are sufficient
determine if a packet is a duplicate. information to determine if a packet is a duplicate (assuming a
manageable storage size for packets that are missing due to loss).
Some in-order packet arrivals may not be useful to TCP receivers,
due to the receiver window. Sequence Discontinuities and their size
are defined in section 3.4, and this information may be useful to
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
when there are overlapped or nested events. Test instrument
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, and the value of viewing reordering reversing order criterion works, how n-reordering works in
in both the dimensions of time and position. comparison, and the value of viewing reordering in all the
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
the tables in each example to determine packet 4's arrival index the tables in each example to determine packet 4's arrival index
number, if needed. number, if needed.
7.1 Example with a single packet reordered
Table 1 gives a simple case of reordering, where one packet is Table 1 gives a simple case of reordering, where one packet is
reordered, Packet 4. Packets are listed according to their arrival, reordered, Packet 4. Packets are listed according to their arrival,
and message numbering is used. and message numbering is used.
Table 1 Example with Packet 4 Reordered, Table 1 Example with Packet 4 Reordered,
Sending order(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10 Sending order(SrcNum@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
skipping to change at line 833 skipping to change at line 1048
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 also indicate
unusual behavior for Packet 4. unusual behavior for Packet 4. Also, if Packet 4 had arrived at
least 62ms earlier, it would have been in-order in this example.
If all packets contained 100 byte payloads, then Byte Offset is 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 defined to be
4-reordered. 4-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
4 4 60 128 68 0 4 4 4 60 128 68 0 4
7 5 120 188 68 -22 5 7 5 120 188 68 -22 5
5 8 80 189 109 41 6 100 1 5 8 80 189 109 41 6 100 1
skipping to change at line 880 skipping to change at line 1097
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, but 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.4. 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, at Packet 7.
Following the definitions of section 5.1, Packet 5 is defined to be This is a case where reordering extent e would over-estimate the
1-reordered, but Packet 6 is not qualified n-reordered. packet storage required to restore order. Only one packet storage is
required (to hold Packet 7), but e=2 for Packet 6.
Following the definitions of section 5, Packet 5 is defined to be 1-
reordered, but Packet 6 is not qualified 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
Table 3 Example with Packets 4, 5, and 6 reordered Table 3 Example with Packets 4, 5, and 6 reordered
Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11
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
7 4 120 188 68 -88 4 7 4 120 188 68 -88 4
8 8 140 208 68 0 5 8 8 140 208 68 0 5
9 9 160 228 68 0 6 9 9 160 228 68 0 6
skipping to change at line 938 skipping to change at line 1161
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 qualified 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.4, Definition 2, we find that the minimum j=4 for all of Section 4.2.3, we find that the minimum j=4 for all three
three packets. They are all associated with the reordering packets. They are all associated with the reordering discontinuity
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 metric indicates 5 and 6 are reordered, and they are
all associated with a single reordering discontinuity). all associated with a single reordering discontinuity).
Table 4 Example with Packets Multiple Reordering Discontinuities 7.4 Example with Multiple Packet Reordering Discontinuities
Table 4 Example with Multiple Packet Reordering Discontinuities
Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 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 n = 1 2 3
end r counts = 5 1 6 end r counts = 5 1 6
skipping to change at line 969 skipping to change at line 1194
n = 1 2 3 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
We also have three reordering-free runs of lengths 5, 1, and 6. We also have three reordering-free runs of lengths 5, 1, and 6.
The differences between these two multiple-event metrics are evident The differences between these two multiple-event metrics are evident
here. Gaps are the distance between sequence discontinuities that here. Gaps are the distance between sequence discontinuities that
are subsequently defined as reordering discontinuities, while are subsequently defined as reordering discontinuities, while
reordering-free runs are capture the distance between reordered reordering-free runs capture the distance between reordered packets.
packets.
8. Security Considerations 8. Security Considerations
8.1 Denial of Service Attacks 8.1 Denial of Service Attacks
This metric requires a stream of packets sent from one host (Src) to This metric requires a stream of packets sent from one host (source)
another host (Dst) through intervening networks. This method could to another host (destination) through intervening networks. This
be abused for denial of service attacks directed at Dst and/or the method could be abused for denial of service attacks directed at
intervening network(s). destination and/or the intervening network(s).
Administrators of Src, Dst, and the intervening network(s) should Administrators of source, destination, and the intervening
establish bilateral or multi-lateral agreements regarding the network(s) should establish bilateral or multi-lateral agreements
timing, size, and frequency of collection of sample metrics. Use of regarding the timing, size, and frequency of collection of sample
this method in excess of the terms agreed between the participants metrics. Use of this method in excess of the terms agreed between
may be cause for immediate rejection or discard of packets or other the participants may be cause for immediate rejection or discard of
escalation procedures defined between the affected parties. packets or other escalation procedures defined between the affected
parties.
8.2 User data confidentiality 8.2 User data confidentiality
Active use of this method generates packets for a sample, rather Active use of this method generates packets for a sample, rather
than taking samples based on user data, and does not threaten user than taking samples based on user data, and does not threaten user
data confidentiality. Passive measurement must restrict attention to data confidentiality. Passive measurement must restrict attention to
the headers of interest. Since user payloads may be temporarily the headers of interest. Since user payloads may be temporarily
stored for length analysis, suitable precautions MUST be taken to stored for length analysis, suitable precautions MUST be taken to
keep this information safe and confidential. keep this information safe and confidential.
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 Dst and/or the packets is part of a sample. With that knowledge at the destination
intervening networks, it is possible to change the processing of the and/or the intervening networks, it is possible to change the
packets (e.g. increasing or decreasing delay) that may distort the processing of the packets (e.g. increasing or decreasing delay) that
measured performance. It may also be possible to generate may distort the measured performance. It may also be possible to
additional packets that appear to be part of the sample metric. generate additional packets that appear to be part of the sample
These additional packets are likely to perturb the results of the metric. These additional packets are likely to perturb the results
sample measurement. of the sample measurement.
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. References 10. Normative References
1 Bradner, S., "The Internet Standards Process -- Revision 3", BCP
9, RFC 2026, October 1996.
2 Bradner, S., "Key words for use in RFCs to Indicate Requirement 1 Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", RFC 2119, March 1997. Levels", RFC 2119, March 1997.
3 Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., "Framework 2 Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., "Framework
for IP Performance Metrics", RFC 2330, May 1998. for IP Performance Metrics", RFC 2330, May 1998.
4 V.Paxson, "Measurements and Analysis of End-to-End Internet 11. Informative References
3 V.Paxson, "Measurements and Analysis of End-to-End Internet
Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997, Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997,
ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz. ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz.
5 Postel, J., "Transmission Control Protocol", STD 7, RFC 793, 4 Postel, J., "Transmission Control Protocol", STD 7, RFC 793,
September 1981. September 1981.
Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt
6 L.Ciavattone and A.Morton, "Out-of-Sequence Packet Parameter 5 L.Ciavattone and A.Morton, "Out-of-Sequence Packet Parameter
Definition (for Y.1540)", Contribution number T1A1.3/2000-047, Definition (for Y.1540)", Contribution number T1A1.3/2000-047,
October 30, 2000. ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc October 30, 2000. ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc
7 J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet Reordering is 6 J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet Reordering is
Not Pathological Network Behavior," IEEE/ACM Transactions on Not Pathological Network Behavior," IEEE/ACM Transactions on
Networking, vol.7, no.6, pp.789-798, December 1999. Networking, vol.7, no.6, pp.789-798, December 1999.
8 D.Loguinov and H.Radha, "Measurement Study of Low-bitrate 7 D.Loguinov and H.Radha, "Measurement Study of Low-bitrate
Internet Video Streaming", Proceedings of the ACM SIGCOMM Internet Video Streaming", Proceedings of the ACM SIGCOMM
Internet Measurement Workshop 2001 November 1-2, 2001, San Internet Measurement Workshop 2001 November 1-2, 2001, San
Francisco, USA. Francisco, USA.
9 J.Bellardo and S.Savage, "Measuring Packet Reordering," 8 J.Bellardo and S.Savage, "Measuring Packet Reordering,"
Proceedings of the ACM SIGCOMM Internet Measurement Workshop Proceedings of the ACM SIGCOMM Internet Measurement Workshop
2002, November 6-8, Marseille, France. 2002, November 6-8, Marseille, France.
10 S.Jaiswal et al., "Measurement and Classification of Out-of- 9 S.Jaiswal et al., "Measurement and Classification of Out-of-
Sequence Packets in a Tier-1 IP Backbone," Proceedings of the ACM Sequence Packets in a Tier-1 IP Backbone," Proceedings of the ACM
SIGCOMM Internet Measurement Workshop 2002, November 6-8, SIGCOMM Internet Measurement Workshop 2002, November 6-8,
Marseille, France. Marseille, France.
11 L.Ciavattone, A.Morton, and G.Ramachandran, "Standardized Active 10 L.Ciavattone, A.Morton, and G.Ramachandran, "Standardized Active
Measurements on a Tier 1 IP Backbone," IEEE Communications Mag., Measurements on a Tier 1 IP Backbone," IEEE Communications Mag.,
pp 90-97, June 2003. pp 90-97, June 2003.
12 Demichelis, C., and Chimento, P., "IP Packet Delay Variation
11 Demichelis, C., and Chimento, P., "IP Packet Delay Variation
Metric for IP Performance Metrics (IPPM)", RFC 3393, November Metric for IP Performance Metrics (IPPM)", RFC 3393, November
2002. 2002.
13 Raisanen, V., Grotefeld, G., and Morton, A., "Network performance 12 Raisanen, V., Grotefeld, G., and Morton, A., "Network performance
measurement with periodic streams", RFC 3432, November 2002. measurement with periodic streams", RFC 3432, 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 Mathis, Jon Bennett, and Matt Zekauskas. We gratefully Matt Zekauskas, Jon Bennett (who authored the sections on
acknowledge the foundation laid by the authors of the IP performance Reordering-Free Runs), and Matt Mathis. We thank David Newman and
Framework [3]. Henk Uijterwall for their reviews and suggestions, and Michal
Przybylski for sharing implementation experiences with us on the
ippm-list. We gratefully acknowledge the foundation laid by the
authors of the IP performance Framework [2].
13. Appendix A (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 MAX_N 100 #define MAXN 100
#define min(a, b) ((a) < (b)? (a): (b)) #define min(a, b) ((a) < (b)? (a): (b))
#define loop(x) ((x) >= 0? x: x + MAX_N) #define loop(x) ((x) >= 0? x: x + MAXN)
/* /*
* Read new sequence number and return it. Return a sentinel value * Read new sequence number and return it. Return a sentinel value
of EOF * of EOF (at least once) when there are no more sequence numbers.
* (at least once) when there are no more sequence numbers. In this * In this example, the sequence numbers come from stdin;
example, * in an actual test, they would come from the network.
* the sequence numbers come from stdin; in an actual test, they *
would come
* from the network.
*/ */
int int
read_sequence_number() read_sequence_number()
{ {
int res, rc; int res, rc;
rc = scanf("%d\n", &res); rc = scanf("%d\n", &res);
if (rc == 1) return res; if (rc == 1) return res;
else return EOF; else return EOF;
} }
int int
main() main()
{ {
int m[MAX_N]; /* We have m[j-1] == number int m[MAXN]; /* We have m[j-1] == number of
of
* j-reordered packets. */ * j-reordered packets. */
int ring[MAX_N]; /* Last sequence numbers int ring[MAXN]; /* Last sequence numbers seen. */
seen. */ int r = 0; /* Ring pointer for next write. */
int r = 0; /* Ring pointer for next int l = 0; /* Number of sequence numbers read. */
write. */ int s; /* Last sequence number read. */
int l = 0; /* Number of sequence
numbers read. */
int s; /* Last sequence number
read. */
int j; int j;
for (j = 0; j < MAX_N; j++) m[j] = 0; for (j = 0; j < MAXN; j++) m[j] = 0;
for (; (s = read_sequence_number()) != EOF; l++, r = (r+1) % for (;(s = read_sequence_number())!= EOF;l++,r=(r+1)%MAXN) {
MAX_N) { for (j=0; j<min(l, MAXN)&&s<ring[loop(r-j-1)];j++) m[j]++;
for (j=0; j<min(l, MAX_N) && s<ring[loop(r-j-1)];
j++) m[j]++;
ring[r] = s; ring[r] = s;
} }
for (j = 0; j < MAX_N && m[j]; j++) for (j = 0; j < MAXN && m[j]; j++)
printf("%d-reordering = %f%%\n", j+1, 100.0*m[j]/(l- printf("%d-reordering = %f%%\n", j+1, 100.0*m[j]/(l-j-1));
j-1));
if (j == 0) printf("no reordering\n"); if (j == 0) printf("no reordering\n");
else if (j < MAX_N) printf("no %d-reordering\n", j+1); else if (j < MAXN) printf("no %d-reordering\n", j+1);
else printf("only up to %d-reordering is handled\n", MAX_N); else printf("only up to %d-reordering is handled\n", MAXN);
exit(0); exit(0);
} }
Example 2 singleton and n-reordering comparison ================= Example 2 singleton and n-reordering comparison =================
#include <stdio.h> #include <stdio.h>
#define MAX_N 100 #define MAXN 100
#define min(a, b) ((a) < (b)? (a): (b)) #define min(a, b) ((a) < (b)? (a): (b))
#define loop(x) ((x) >= 0? x: x + MAX_N) #define loop(x) ((x) >= 0? x: x + MAXN)
/* Global counters */ /* Global counters */
int receive_packets=0; /* number of recieved */ int receive_packets=0; /* number of recieved */
int reorder_packets=0; /* number of reordered packets */ int reorder_packets=0; /* number of reordered packets */
/* function to test if current packet has been reordered /* function to test if current packet has been reordered
* returns 0 = not reordered * returns 0 = not reordered
* 1 = reordered * 1 = reordered
*/ */
int testorder1(int seqnum) // Al int testorder1(int seqnum) // Al
skipping to change at line 1173 skipping to change at line 1392
if (seqnum >= NextExp) { if (seqnum >= NextExp) {
NextExp = seqnum+1; NextExp = seqnum+1;
} else { } else {
iReturn = 1; iReturn = 1;
} }
return iReturn; return iReturn;
} }
int testorder2(int seqnum) // Stanislav int testorder2(int seqnum) // Stanislav
{ {
static int ring[MAX_N]; /* Last sequence numbers static int ring[MAXN]; /* Last sequence numbers seen. */
seen. */ static int r = 0; /* Ring pointer for next write */
static int r = 0; /* Ring pointer for next write. int l = 0; /* Number of sequence numbers read. */
*/
int l = 0; /* Number of sequence
numbers read. */
int j; int j;
int iReturn = 0; int iReturn = 0;
l++; l++;
r = (r+1) % MAX_N; r = (r+1) % MAXN;
for (j=0; j<min(l, MAX_N) && seqnum<ring[loop(r-j-1)]; j++) for (j=0; j<min(l, MAXN) && seqnum<ring[loop(r-j-1)]; j++)
iReturn = 1; iReturn = 1;
ring[r] = seqnum; ring[r] = seqnum;
return iReturn; return iReturn;
} }
int main(int argc, char *argv[]) int main(int argc, char *argv[])
{ {
int i, packet; int i, packet;
for (i=1; i< argc; i++) { for (i=1; i< argc; i++) {
receive_packets++; receive_packets++;
packet = atoi(argv[i]); packet = atoi(argv[i]);
reorder_packets += testorder2(packet); reorder_packets += testorder2(packet);
} }
printf("Received packets = %d, Reordered packets = %d\n", printf("Received packets = %d, Reordered packets = %d\n",
receive_packets, reorder_packets); receive_packets, reorder_packets);
exit(0); exit(0);
} }
13. Appendix on fragment order evaluation Reference
ISO/IEC 9899:1999 (E), as amended by ISO/IEC 9899:1999/Cor.1:2001
(E). Also published as:
The C Standard: Incorporating Technical Corrigendum 1, British
Standards Institute, ISBN: 0-470-84573-2, Hardcover, 558 pages,
September 2003.
14. Appendix B Fragment Order Evaluation (Informative)
Section 3 stated that fragment re-assembly is assumed prior to order Section 3 stated that fragment re-assembly is assumed prior to order
evaluation, but that similar procedures could be applied prior to evaluation, but that similar procedures could be applied prior to
re-assembly. This appendix gives definitions and procedures to re-assembly. This appendix gives definitions and procedures to
identify reordering in a packet stream that includes fragmentation. identify reordering in a packet stream that includes fragmentation.
14.1 Metric Name:
The Metric retains the same name, Type-P-Reordered, but additional The Metric retains the same name, Type-P-Reordered, but additional
parameters are required. parameters are required.
This Appendix assumes that the device that divides a packet into This Appendix assumes that the device that divides a packet into
fragments send them according to ascending fragment offset. Early fragments send them according to ascending fragment offset. Early
Linux OS sent fragments in reverse order, so this possibility is Linux OS sent fragments in reverse order, so this possibility is
worth checking. worth checking.
13.1 Additional Metric Parameters: 14.2 Additional Metric Parameters:
+ MoreFrag, the state of the More Fragments Flag in the IP header + MoreFrag, the state of the More Fragments Flag in the IP header
+ FragOffset, the offset from the beginning of a fragmented packet, + FragOffset, the offset from the beginning of a fragmented packet,
in 8 octet units (also from the IP header). in 8 octet units (also from the IP header).
+ FragSeq#, the sequence number from the IP header of a fragmented + FragSeq#, the sequence number from the IP header of a fragmented
packet currently under evaluation for reordering. When set to packet currently under evaluation for reordering. When set to
zero, fragment evaluation is not in progress. zero, fragment evaluation is not in progress.
skipping to change at line 1242 skipping to change at line 1469
The packet sequence number, s, is assumed to be the same as the IP The packet sequence number, s, is assumed to be the same as the IP
header sequence number. Also, the value of NextExp does not change header sequence number. Also, the value of NextExp does not change
with the in-order arrival of fragments. NextExp is only updated when with the in-order arrival of fragments. NextExp is only updated when
a last fragment or a complete packet arrives. a last fragment or a complete packet arrives.
Note that packets with missing fragments MUST be declared lost, and Note that packets with missing fragments MUST be declared lost, and
the Reordering status of any fragments that do arrive MUST be the Reordering status of any fragments that do arrive MUST be
excluded from sample metrics. excluded from sample metrics.
13.2 Definition: 14.3 Definition:
The value of Type-P-Reordered is typically false (the packet is in- The value of Type-P-Reordered is typically false (the packet is in-
order) when order) when
* the sequence number s >= NextExp, * the sequence number s >= NextExp,
* AND the fragment offset FragOffset >= NextExpFrag * AND the fragment offset FragOffset >= NextExpFrag
However, it more efficient to define reordered conditions exactly, However, it more efficient to define reordered conditions exactly,
and designate Type-P-Reordered as False otherwise. and designate Type-P-Reordered as False otherwise.
skipping to change at line 1301 skipping to change at line 1527
/* a fragment of the "current packet s" arrived */ /* a fragment of the "current packet s" arrived */
if (FragOffset >= NextExpFrag){ if (FragOffset >= NextExpFrag){
NextExpFrag = FragOffset+1; NextExpFrag = FragOffset+1;
Reordering = False; Reordering = False;
} }
else{ else{
Reordering = True; /* fragment reordered */ Reordering = True; /* fragment reordered */
} }
} }
if (s>=NextExp AND MoreFrag==1 AND s < FragSeq#){ if (s>=NextExp AND MoreFrag==1 AND s < FragSeq#){
/* case where a late fragment arrived */ /* case where a late fragment arrived,
for illustration only, redundant with else below*/
Reordering = True; Reordering = True;
} }
else { /* when s < NextExp, or MoreFrag==0 AND s < FragSeq# */ else { /* when s < NextExp, or MoreFrag==0 AND s < FragSeq# */
Reordering = True; Reordering = True;
} }
} }
A working version of the code would include a check to ensure that A working version of the code would include a check to ensure that
all fragments of a packet arrive before using the Reordered status all fragments of a packet arrive before using the Reordered status
further, such as in sample metrics. further, such as in sample metrics.
13.3 Notes on Sample Metrics 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.
14. Author's Addresses 15. 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
skipping to change at line 1364 skipping to change at line 1590
EMail: <shalunov@internet2.edu> EMail: <shalunov@internet2.edu>
Jerry Perser Jerry Perser
Consultant Consultant
Calabasas, CA 91302 USA Calabasas, CA 91302 USA
Phone: + 1 Phone: + 1
EMail: <jerry@perser.org> EMail: <jerry@perser.org>
Full Copyright Statement Full Copyright Statement
"Copyright (C) The Internet Society (date). All Rights Reserved. Copyright (C) The Internet Society (2004). This document is subject
This document and translations of it may be copied and furnished to to the rights, licenses and restrictions contained in BCP 78 and
others, and derivative works that comment on or otherwise explain it except as set forth therein, the authors retain all their rights.
or assist in its implmentation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph
are included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be This document and the information contained herein are provided on
revoked by the Internet Society or its successors or assigns. an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE
INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
This document and the information contained herein is provided on an Intellectual Property
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING The IETF takes no position regarding the validity or scope of any
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION Intellectual Property Rights or other rights that might be claimed
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF to pertain to the implementation or use of the technology described
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. in this document or the extent to which any license under such
rights might or might not be available; nor does it represent that
it has made any independent effort to identify any such rights.
Information on the procedures with respect to rights in RFC
documents can be found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use
of such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository
at http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at ietf-
ipr@ietf.org.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
 End of changes. 

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