draft-ietf-ippm-reordering-08.txt   draft-ietf-ippm-reordering-09.txt 
Network Working Group A.Morton Network Working Group A.Morton
Internet Draft L.Ciavattone Internet Draft L.Ciavattone
Document: <draft-ietf-ippm-reordering-08.txt> G.Ramachandran Document: <draft-ietf-ippm-reordering-09.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
skipping to change at line 38 skipping to change at line 39
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 Notice
Copyright (C) The Internet Society (2004). Copyright (C) The Internet Society (2005).
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, including
first defines a reordered singleton, and then uses it as the basis the context information required for all metrics. The memo first
for sample metrics to quantify the extent of reordering in several defines a reordered singleton, and then uses it as the basis for
sample metrics to quantify the extent of reordering in several
useful dimensions for network characterization or receiver design. useful dimensions for network characterization or receiver design.
Additional metrics quantify the frequency of reordering and the Additional metrics quantify the frequency of reordering and the
distance between separate occurrences. We then define a metric with distance between separate occurrences. We then define a metric
purely receiver analysis orientation. Several examples of evaluation oriented toward reordering affects on TCP. Several examples of
using the various sample metrics are included. An Appendix gives evaluation using the various sample metrics are included. An
extended definitions for evaluating order with packet fragmentation. Appendix gives extended definitions for evaluating order with packet
fragmentation.
Contents Contents
Status of this Memo................................................1 Status of this Memo................................................1
Copyright Notice...................................................1 Copyright Notice...................................................1
Abstract...........................................................1 Abstract...........................................................1
1. Conventions used in this document...............................3 1. Conventions used in this document...............................3
2. Introduction....................................................3 2. Introduction....................................................3
2.1 Motivation.....................................................4 2.1 Motivation.....................................................4
2.2 Goals and Objectives...........................................5 2.2 Goals and Objectives...........................................5
3. A Reordered Packet Singleton Metric.............................6 3. A Reordered Packet Singleton Metric.............................6
3.1 Metric Name:...................................................6 3.1 Metric Name:...................................................7
3.2 Metric Parameters:.............................................6 3.2 Metric Parameters:.............................................7
3.3 Definition:....................................................7 3.3 Definition:....................................................7
3.4 Sequence Discontinuity Definition..............................7 3.4 Sequence Discontinuity Definition..............................8
3.5 Evaluation of Reordering in Dimensions of Time or Bytes........8 3.5 Evaluation of Reordering in Dimensions of Time or Bytes........8
3.6 Discussion.....................................................8 3.6 Discussion.....................................................9
4. Sample Metrics..................................................9 4. Sample Metrics..................................................9
4.1 Reordered Packet Ratio.........................................9 4.1 Reordered Packet Ratio........................................10
4.1.1 Metric Name:.................................................9 4.1.1 Metric Name:................................................10
4.1.2 Metric Parameters:...........................................9 4.1.2 Metric Parameters:..........................................10
4.1.3 Definition:..................................................9 4.1.3 Definition:.................................................10
4.1.4 Discussion...................................................9 4.1.4 Discussion..................................................10
4.2 Reordering Extent.............................................10 4.2 Reordering Extent.............................................11
4.2.1 Metric Name:................................................10 4.2.1 Metric Name:................................................11
4.2.2 Parameter Notation:.........................................10 4.2.2 Parameter Notation:.........................................11
4.2.3 Definition:.................................................10 4.2.3 Definition:.................................................11
4.2.4 Discussion:.................................................11 4.2.4 Discussion:.................................................12
4.3 Reordering Late Time Offset...................................11 4.3 Reordering Late Time Offset...................................12
4.3.1 Metric Name:................................................11 4.3.1 Metric Name:................................................12
4.3.2 Metric Parameters:..........................................11 4.3.2 Metric Parameters:..........................................13
4.3.3 Definition:.................................................11 4.3.3 Definition:.................................................13
4.3.4 Discussion..................................................12 4.3.4 Discussion..................................................13
4.4 Reordering Byte Offset........................................12 4.4 Reordering Byte Offset........................................14
4.4.1 Metric Name:................................................12 4.4.1 Metric Name:................................................14
4.4.2 Metric Parameters:..........................................12 4.4.2 Metric Parameters:..........................................14
4.4.3 Definition:.................................................12 4.4.3 Definition:.................................................14
4.4.4 Discussion..................................................13 4.4.4 Discussion..................................................14
4.5 Gaps between multiple Reordering Discontinuities..............13 4.5 Gaps between multiple Reordering Discontinuities..............15
4.5.1 Metric Name:................................................13 4.5.1 Metric Name:................................................15
4.5.2 Parameters:.................................................13 4.5.2 Parameters:.................................................15
4.5.3 Definition of Reordering Discontinuity:.....................13 4.5.3 Definition of Reordering Discontinuity:.....................15
4.5.4 Definition of Reordering Gap:...............................14 4.5.4 Definition of Reordering Gap:...............................15
4.5.5 Discussion..................................................14 4.5.5 Discussion..................................................16
4.6 Reordering-free Runs..........................................14 4.6 Reordering-free Runs..........................................16
4.6.1 Metric Name:................................................15 4.6.1 Metric Name:................................................16
4.6.2 Parameters:.................................................15 4.6.2 Parameters:.................................................17
4.6.3 Definition:.................................................15 4.6.3 Definition:.................................................17
4.6.4 Discussion:.................................................16 4.6.4 Discussion:.................................................18
5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..16 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..18
5.1 Metric Name:..................................................16 5.1 Metric Name:..................................................18
5.2 Parameter Notation:...........................................17 5.2 Parameter Notation:...........................................19
5.3 Definitions...................................................17 5.3 Definitions...................................................19
5.4 Discussion:...................................................17 5.4 Discussion:...................................................19
6. Measurement and Implementation Issues..........................18 6. Measurement and Implementation Issues..........................20
7. Examples of Arrival Order Evaluation...........................20 7. Examples of Arrival Order Evaluation...........................24
7.1 Example with a single packet reordered........................21 7.1 Example with a single packet reordered........................24
7.2 Example with two packets reordered............................22 7.2 Example with two packets reordered............................25
7.3 Example with three packets reordered..........................23 7.3 Example with three packets reordered..........................27
7.4 Example with Multiple Packet Reordering Discontinuities.......25 7.4 Example with Multiple Packet Reordering Discontinuities.......28
8. Security Considerations........................................25 8. Security Considerations........................................28
8.1 Denial of Service Attacks.....................................25 8.1 Denial of Service Attacks.....................................28
8.2 User data confidentiality.....................................25 8.2 User data confidentiality.....................................29
8.3 Interference with the metric..................................26 8.3 Interference with the metric..................................29
9. IANA Considerations............................................26 9. IANA Considerations............................................29
10. Normative References..........................................26 10. Normative References..........................................29
11. Informative References........................................26 11. Informative References........................................30
12. Acknowledgments...............................................27 12. Acknowledgments...............................................31
13. Appendix A Example Implementations in C (Informative).........28 13. Appendix A Example Implementations in C (Informative).........31
14. Appendix B Fragment Order Evaluation (Informative)............30 14. Appendix B Fragment Order Evaluation (Informative)............34
14.1 Metric Name:.................................................30 14.1 Metric Name:.................................................34
14.2 Additional Metric Parameters:................................30 14.2 Additional Metric Parameters:................................34
14.3 Definition:..................................................31 14.3 Definition:..................................................34
14.4 Discussion: Notes on Sample Metrics when evaluating Fragments32 14.4 Discussion: Notes on Sample Metrics when evaluating Fragments36
15. Author's Addresses............................................32 15. Author's Addresses............................................36
Full Copyright Statement..........................................33 Full Copyright Statement..........................................37
Intellectual Property.............................................33 Intellectual Property.............................................37
Acknowledgement...................................................34 Acknowledgement...................................................38
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 [RFC2119]. document are to be interpreted as described in RFC 2119 [RFC2119].
Although RFC 2119 was written with protocols in mind, the key words Although RFC 2119 was written with protocols in mind, the key words
are used in this document for similar reasons. They are used to are used in this document for similar reasons. They are used to
ensure the results of measurements from two different ensure the results of measurements from two different
implementations are comparable, and to note instances when an implementations are comparable, and to note instances when an
implementation could perturb the network. implementation could perturb the network.
In this memo, the characters "<=" should be read as "less than or
equal to" and ">=" as "greater than or equal to".
2. Introduction 2. Introduction
Ordered arrival is a property found in packets that successfully Ordered arrival is a property found in packets that transit their
transit their path, where the packet sequence number increases with path, where the packet sequence number increases with each new
each new arrival and there are no backward steps. Internet Protocol arrival and there are no backward steps. The Internet Protocol
[RFC791] has no mechanisms to assure either packet delivery or [RFC791] has no mechanisms to assure either packet delivery or
sequencing, and other protocols should be prepared to deal with both sequencing, and higher layer protocols (above IP) should be prepared
loss and reordering. This memo defines reordering metrics. to deal with both loss and reordering. This memo defines reordering
metrics.
A unique sequence number, such as an incrementing message number A unique sequence number, such as an incrementing message number
carried in each packet, establishes the Source Sequence. carried in each packet, establishes the 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 [RFC2330], and classifies This metric is consistent with RFC 2330 [RFC2330], and classifies
arriving packets with sequence numbers smaller than their arriving packets with sequence numbers smaller than their
predecessors as out-of-order, or reordered. For example, if predecessors as out-of-order, or reordered. For example, if
skipping to change at line 184 skipping to change at line 191
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 may change during transfer, and several specific path Packet order may change during transfer, and several specific path
characteristics can make reordering more likely. characteristics can make reordering more likely.
Examples are: Examples are:
* When two paths, one with slightly longer transfer time, support a * When two (or more) paths with slightly differing transfer times
single packet stream or flow, then packets traversing the longer support a single packet stream or flow, then packets traversing
path may arrive out-of-order. Multiple paths may be used to the longer path(s) may arrive out-of-order. Multiple paths may be
achieve load balancing, or may arise from route instability. used to 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 (or parallel links) 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
skipping to change at line 226 skipping to change at line 235
size in terms of packets, bytes, or time (such as de-jitter size in terms of packets, bytes, or time (such as de-jitter
buffers). Once the initial determination of reordering is made, it buffers). Once the initial determination of reordering is made, it
is useful to quantify the extent of reordering, or lateness, in all is useful to quantify the extent of reordering, or lateness, in all
meaningful dimensions. meaningful dimensions.
2.2 Goals and Objectives 2.2 Goals and Objectives
The definitions below intend to satisfy the goals of: The definitions below intend to satisfy the goals of:
1. Determining whether or not packet reordering has occurred. 1. Determining whether or not packet reordering has occurred.
2. Quantifying the degree of reordering (achieving this second 2. Quantifying the degree of reordering. (We define a number of
goal requires assumptions of upper layer functions and metrics to meet this goal, because receiving procedures differ
capabilities to restore order, and therefore several by protocol or application. Since the affects of packet
solutions). reordering vary with these procedures, a metric that quantifies
a key aspect of one receiver's behavior could be irrelevant to
a different receiver.)
Reordering Metrics MUST: Reordering Metrics MUST:
+ have one or more applications, such as receiver design or network + have one or more applications, such as receiver design or network
characterization, and a compelling relevance in the working characterization, and a compelling relevance in the working
group's view. group's view.
+ be computable "on the fly" + be computable "on the fly"
+ work even if the stream has duplicate or lost packets + work even if the stream has duplicate or lost packets
It is desirable for Reordering Metrics to have one or more of the It is desirable for Reordering Metrics to have one or more of the
following attributes: following attributes:
+ concatenating results for segments measured separately + ability to concatenate results for segments measured separately
to estimate the reordering of an entire path
+ simplicity for easy consumption and understanding + simplicity for easy consumption and understanding
+ relevance to TCP performance + relevance to TCP design
+ relevance to Real-time application performance + relevance to Real-time application performance
The current set of metrics meet all the requirements above and
The current set of metrics meet all the requirements above, and
provides all but the concatenation attribute (except in the case provides all but the concatenation attribute (except in the case
where segments exhibit no reordering, and one may estimate that the where segments exhibit no reordering, and one may estimate that the
segment concatenation would also exhibit this desirable outcome). segment concatenation would also exhibit this desirable outcome).
However, satisfying these goals limits the set of metrics to those However, satisfying these goals restricts the set of metrics to
that provide some clear insight into network characterization or those that provide some clear insight into network characterization
receiver design, and they are not likely to be exhaustive in their or receiver design. They are not likely to be exhaustive in their
coverage of the applications with respect to packet reordering coverage of reordering effects on applications, and additional
effects. Likewise, additional measurements may be possible. measurements may be possible.
2.3 Required Context for All Reordering Metrics
A critical aspect of all reordering metrics is their inseparable
bond with the measurement conditions. Packet reordering is not well
defined unless the full measurement context is reported. Therefore,
all reordering metric definitions include the following parameters:
1. The "Packet of Type-P" [RFC2330] identifiers for the packet
stream, including the transport addresses for source and
destination, and any other information which may result in different
packet treatments.
2. The stream parameter set for the sending discipline, such as the
parameters unique to Periodic Streams (as in RFC 3432 [RFC3432]),
TCP-like Streams (as in RFC 3148 [RFC3148]), or Poisson Streams (as
in RFC 2330 [RFC2330]. The stream parameters include the packet
size, either specified as a fixed value or as a pattern of sizes (as
applicable).
Whenever a metric is reported, it MUST include a description of
these parameters to provide a context for the results.
3. A Reordered Packet Singleton Metric 3. A Reordered Packet Singleton Metric
The IPPM framework RFC 2330 [RFC2330] describes the notions of The IPPM framework RFC 2330 [RFC2330] describes the notions of
singletons, samples, and statistics. For easy reference: singletons, samples, and statistics. For easy reference:
By a 'singleton' metric, we refer to metrics that are, By a 'singleton' metric, we refer to metrics that are,
in a sense, atomic. For example, a single instance of "bulk in a sense, atomic. For example, a single instance of "bulk
throughput capacity" from one host to another might be defined throughput capacity" from one host to another might be defined
as a singleton metric, even though the instance involves as a singleton metric, even though the instance involves
measuring the timing of a number of Internet packets. measuring the timing of a number of Internet packets.
The evaluation of packet order requires several supporting concepts. The evaluation of packet order requires several supporting concepts.
The first is a sequence number applied to packets at the source to The first is an algorithm (function) that produces a series of
uniquely identify the order of packet transmission. The unique monotonically increasing identifiers applied to packets at the
sequence number may be a simple message number. source to uniquely establish the order of packet transmission. The
unique sequence identifier may simply be an incrementing integer
message number, as used below.
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 (in general, the receiver reproduces
the sender's algorithm and the sequence of identifiers so that the
"next expected" can be determined).
Each packet within a packet stream can be evaluated with this order 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:
+ Src, the IP address of a host + Src, the IP address of a host
+ Dst, the IP address of a host + Dst, the IP address of a host
+ SrcTime, the time of packet emission from the Source (or wire + SrcTime, the time of packet emission from the Source (or wire
time) time)
+ s, the unique packet sequence number applied at the Source, in + s, the unique packet sequence number applied at the Source, in
units of messages. units of messages.
+ SrcByte, the packet sequence number applied at the Source, in
units of payload bytes.
+ NextExp, the Next Expected Sequence number at the Destination, in + NextExp, the Next Expected Sequence number at the Destination, in
units of messages, time, or bytes. units of messages.
And optionally:
+ 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 bytes
transfer. transfered.
+ SrcByte, the packet sequence number applied at the Source, in
units of payload bytes.
3.3 Definition: 3.3 Definition:
If a packet is found to be reordered by comparison with the Next If a packet s, (sent at time, SrcTime) is found to be reordered by
Expected value, its Type-P-Reordered = TRUE; otherwise Type-P- comparison with the Next Expected value, its Type-P-Reordered =
Reordered = FALSE, as defined below: 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, the NextExp value does not
change.
The value of Type-P-Reordered is defined as FALSE if s >= NextExp 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. (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:
skipping to change at line 365 skipping to change at line 405
SeqDiscontinutySize = s - NextExp; SeqDiscontinutySize = s - NextExp;
else else
SequenceDiscontinuty = False; SequenceDiscontinuty = False;
NextExp = s + 1; NextExp = s + 1;
Type-P-Reordered = False; Type-P-Reordered = False;
else /* when s < NextExp */ else /* when s < NextExp */
Type-P-Reordered = True; Type-P-Reordered = True;
SequenceDiscontinuty = False; SequenceDiscontinuty = False;
3.5 Evaluation of Reordering in Dimensions of Time or Bytes Whether there are any Sequence Discontinuities and their size is
determined by the conditions causing loss and/or reordering along
the measurement path. Note that a packet could be reordered at one
point, and subsequently lost elsewhere on the path, but this cannot
be known from observations at the Destination.
3.5 Evaluation of Reordering in Dimensions of Time or Bytes
It is possible to use alternate dimensions of time or payload bytes It is possible to use alternate dimensions of time or payload bytes
to test for reordering in the definition of section 3.3, as long as to test for reordering in the definition of section 3.3, as long as
the SrcTimes and SrcBytes are unique and reliable. Sequence the SrcTimes and SrcBytes are unique and reliable. Sequence
Discontinuities are easily defined and detected with message Discontinuities are easily defined and detected with message
numbering, however, this is not so in the dimensions of time or numbering, however, this is not so simple in the dimensions of time
bytes. This is a detractor for the alternate dimensions because the or bytes. This is a detractor for the alternate dimensions because
Sequence Discontinuity definition plays a key role in the sample the Sequence Discontinuity definition plays a key role in the sample
metrics that follow. metrics that follow.
It is possible to detect Sequence Discontinuities with payload byte It is possible to detect Sequence Discontinuities with payload byte
numbering, but only when payload size is constant, and then the byte numbering, but only when the complete pattern of payload sizes is
numbering adds needless complexity over message numbering. stored at the Destination, or when payload size is constant and then
the byte numbering adds needless complexity over message numbering.
It may be possible to detect Sequence Discontinuities with Periodic It may be possible to detect Sequence Discontinuities with Periodic
Streams and Source Time numbering, but there are practical pitfalls Streams and Source Time numbering, but there are practical pitfalls
with sending exactly on-schedule and with clock reliability. with sending exactly on-schedule and with clock reliability.
The dimensions of time and bytes remain an important basis for The dimensions of time and bytes remain an important basis for
characterizing the extent of reordering, as described later. characterizing the extent of reordering, as described later.
3.6 Discussion 3.6 Discussion
Any arriving packet bearing a sequence number from the sequence that Any arriving packet bearing a sequence number from the sequence that
establishes the Next Expected value can be evaluated to determine establishes the Next Expected value can be evaluated to determine
whether it is in-order or reordered, based on a previous packet's whether it is in-order or reordered, based on a previous packet's
arrival. In the case where Next Expected is Undefined (because the arrival. In the case where Next Expected is Undefined (because the
arriving packet is the first successful transfer), the packet is arriving packet is the first successful transfer), the packet is
designated in-order. designated in-order (Type-P-Reordered=FALSE).
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
skipping to change at line 435 skipping to change at line 481
4.1.1 Metric Name: 4.1.1 Metric Name:
Type-P-Reordered-Ratio-Stream Type-P-Reordered-Ratio-Stream
4.1.2 Metric Parameters: 4.1.2 Metric Parameters:
The parameter set includes Type-P-Reordered singleton parameters, The parameter set includes Type-P-Reordered singleton parameters,
the parameters unique to Poisson Streams (as in RFC 2330 [RFC2330], the parameters unique to Poisson Streams (as in RFC 2330 [RFC2330],
Periodic Streams (as in RFC 3432 [RFC3432]), or TCP-like Streams (as Periodic Streams (as in RFC 3432 [RFC3432]), or TCP-like Streams (as
in RFC 3148 [RFC3148]), plus the following: in RFC 3148 [RFC3148]), packet size or size patterns, and the
following:
+ T0, a start time + T0, a start time
+ Tf, an end time + Tf, an end time
+ dT, a waiting time for each packet to arrive + dT, a waiting time for each packet to arrive
+ K, the total number of packets in the stream sent from Source to
Destination
+ L, the total number of packets received (arriving between T0 and
Tf+dT) out of the K packets sent. Recall that identical copies
(duplicates) have been removed, so L <= K.
4.1.3 Definition: 4.1.3 Definition:
For the packets arriving successfully between T0 and Tf+dT, the Given a stream of packets sent from a Source to a Destination, the
ratio of reordered packets in the sample is ratio of reordered packets in the sample is
(Total of Reordered packets) / (Total packets received) (Count of packets with Type-P-Reordered=TRUE) / ( L )
This fraction may be expressed as a percentage (multiply by 100%). This fraction may be expressed as a percentage (multiply by 100).
Note that in the case of duplicate packets, only the first copy is Note that in the case of duplicate packets, only the first copy is
used. used.
4.1.4 Discussion 4.1.4 Discussion
When the Type-P-Reordered-Ratio-Stream is zero, no further When the Type-P-Reordered-Ratio-Stream is zero, no further
reordering metrics need be examined for that sample. Therefore, the reordering metrics need be examined for that sample. Therefore, the
value of this metric is its simple ability to summarize the results value of this metric is its simple ability to summarize the results
for a reordering-free sample. for a reordering-free sample.
4.2 Reordering Extent 4.2 Reordering Extent
This section defines the extent to which packets are reordered, and This section defines the extent to which packets are reordered, and
associates a specific sequence discontinuity with each reordered associates a specific Sequence Discontinuity with each reordered
packet. This section inherits the Parameters defined above. packet. This section inherits the Parameters defined above.
4.2.1 Metric Name: 4.2.1 Metric Name:
Type-P-packet-Reordering-Extent-Stream Type-P-packet-Reordering-Extent-Stream
4.2.2 Parameter Notation: 4.2.2 Notation and Metric Parameters:
Given a stream of packets sent from a source to a destination, let K
be the total number of packets in that stream.
Assign each packet a sequence number, a consecutive integer from 1 Recall that K is the number of packets in the stream at the Source
to K in the order of packet transmission (at the source). and L is the number of packets received at the Destination.
Let L be the total number of packets received out of the K packets Each packet has been assigned a sequence number, s, a consecutive
sent. Recall that identical copies (duplicates) have been removed, integer from 1 to K in the order of packet transmission (at the
so L<=K. source).
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 s[i] can be thought of as a vector, where the index i is the arrival
arrival index i and source sequence number s[i]. There exists a set position of the packet with sequence number s. In theory, any
of indexes j (1<=j<i) such that s[j] > s[i]. Source sequence number could appear in any arrival position, but
this is unlikely in reality.
Consider a reordered packet (Type-P-Reordered=TRUE) with arrival
index i and source sequence number s[i]. There exists a set of
indexes j (1 <= j < i) such that s[j] > s[i].
The new parameters are:
+ i, the index for arrival position, where i-1 represents an
arrival earlier than i.
+ j, a set of one or more arrival indexes, where 1 <= j < i.
+ s[i], the original sequence numbers, s, in order of arrival.
+ e, the Reordering Extent, defined below.
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
i-j for the smallest value of j when s[j] > s[i]. the smallest value of j where s[j] > s[i].
Informally, the reordering extent is the maximum distance, in Informally, the reordering extent is the maximum distance, in
packets, from a reordered packet to the earliest packet received packets, from a reordered packet to the earliest packet received
that has a larger sequence number. If a packet is in-order, its that has a larger sequence number. If a packet is in-order, its
reordering extent is undefined. The first packet to arrive is in- reordering extent is undefined. The first packet to arrive is in-
order by definition, and has undefined reordering extent. order by definition, and has undefined reordering extent.
Comment on the definition of extent: For some arrival orders, the Comment on the definition of extent: For some arrival orders, the
assignment of a simple position/distance as the reordering extent assignment of a simple position/distance as the reordering extent
tends to overestimate the receiver storage needed to restore order. tends to overestimate the receiver storage needed to restore order.
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. With the bias understood, this could pass on to the upper layers. With the bias understood, this
definition is deemed sufficient, especially for those who demand "on definition is deemed sufficient, especially for those who demand "on
the fly" calculations. 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 s at 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 If a receiver intends to restore order, then its buffer capacity
reordered. For cases with single reordered packets, the extent e determines its ability to handle packets that are reordered. For
gives the number of packets that must be held in the receiver's cases with single reordered packets, the extent e gives the number
buffer while waiting for the reordered packet to complete the of packets that must be held in the receiver's buffer while waiting
sequence. For more complex scenarios, the extent may be an for the reordered packet to complete the sequence. For more complex
overestimate of required storage (see the Examples section). scenarios, the extent may be an overestimate of required storage
(see the Examples section).
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 Late Time Offset 4.3 Reordering Late Time Offset
Reordered packets can be assigned offset values indicating their Reordered packets can be assigned offset values indicating their
skipping to change at line 552 skipping to change at line 621
4.3.1 Metric Name: 4.3.1 Metric Name:
Type-P-packet-Late-Time-Stream Type-P-packet-Late-Time-Stream
4.3.2 Metric Parameters: 4.3.2 Metric Parameters:
In addition to the parameters defined for Type-P-Reordered-Ratio- In addition to the parameters defined for Type-P-Reordered-Ratio-
Stream, we specify: Stream, we specify:
+ DstTime, the time that each packet in the stream arrives at the + DstTime, the time that each packet in the stream arrives at the
destination destination, and may be associated with index i, or packet s[i]
+ LateTime(s[i]), the offset of packet s[i] in time, defined below
4.3.3 Definition: 4.3.3 Definition:
Lateness in time is calculated using destination times. When Lateness in time is calculated using destination times. When
received packet i is reordered, and has a reordering extent e, then: received packet s[i] is reordered, and has a reordering extent e,
then:
LateTime(i) = DstTime(i)-DstTime(i-e) LateTime(s[i]) = DstTime(i)-DstTime(i-e)
Alternatively, using similar notation to that of section 4.2, an Alternatively, using similar notation to that of section 4.2, an
equivalent definition is: equivalent definition is:
LateTime(i) = DstTime(i)-DstTime(j), for min{j|1<=j<i} that
LateTime(s[i]) = DstTime(i)-DstTime(j), for min{j|1<=j<i} that
satisfies s[j]>s[i]. satisfies s[j]>s[i].
4.3.4 Discussion 4.3.4 Discussion
The offset metrics can help predict whether reordered packets will The offset metrics can help predict whether reordered packets will
be useful in a general receiver buffer system with finite limits. be useful in a general receiver buffer system with finite limits.
The limit may be the time of storage prior to a cyclic play-out The limit may be the time of storage prior to a cyclic play-out
instant (as with de-jitter buffers). instant (as with de-jitter buffers).
Note that the One-way IPDV [RFC3393] gives the delay variation for a Note that the One-way IPDV [RFC3393] gives the delay variation for a
skipping to change at line 590 skipping to change at line 663
packet. packet.
In the case of de-jitter buffers, there are circumstances where the In the case of de-jitter buffers, there are circumstances where the
receiver employs loss concealment at the intended play-out time of a receiver employs loss concealment at the intended play-out time of a
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).
The combination of loss and reordering influences the LateTime
metric. If presented with the arrival sequence 1, 10, 5 (where
packets 2, 3, 4, and 6 through 9 are lost), LateTime would not
indicate exactly how "late" packet 5 is from its intended arrival
position. IPDV [RFC3393] would not capture this either, because of
the lack of adjacent packet pairs. Assuming a Periodic Stream
[RFC3432], an expected arrival time could be defined for all
packets, but this is essentially a single-point delay variation
metric (as defined in ITU-T Recommendations [I.356] and [Y.1540]),
and not a reordering metric.
4.4 Reordering Byte Offset 4.4 Reordering Byte Offset
Reordered packets can be assigned offset values indicating the Reordered packets can be assigned offset values indicating the
storage in bytes that a receiver must possess to accommodate them. storage in bytes that a receiver must possess to accommodate them.
The various offset metrics are calculated only on reordered packets, The various offset metrics are calculated only on reordered packets,
as identified by the reordered packet singleton metric in Section 3. 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 Type-P-packet-Byte-Offset-Stream
4.4.2 Metric Parameters: 4.4.2 Metric Parameters:
We use the same parameters defined earlier. We use the same parameters defined earlier, including the optional
parameters of SrcByte and PayloadSize, and define:
+ ByteOffset(s[i]), the offset of packet s[i] in bytes
4.4.3 Definition: 4.4.3 Definition:
Byte stream offset is the sum of the payload sizes of intervening The Byte stream offset for reordered packet s[i] is the sum of the
in-order packets between the reordered packet and the discontinuity payload sizes of packets qualified by the following criteria:
(including the packet at the discontinuity).
For reordered packet i with a reordering extent e: * Arrival prior to the reordered packet, s[i], and
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 send sequence number, s, is greater than s[i].
Packets that meet both these criteria are normally buffered until
the sequence beneath them is complete. Note that these criteria
apply to both in-order and reordered packets.
For reordered packet s[i] with a reordering extent e:
ByteOffset(s[i]) = Sum[qualified packets]
= Sum[PayloadSize(packet at i-1 if qualified),
PayloadSize(packet at i-2 if qualified), ...
PayloadSize(packet at i-e always qualified)]
Using our earlier notation:
ByteOffset(s[i]) =
Sum[payloads of s[j] where s[j]>s[i] and i > j >= i-e]
4.4.4 Discussion
We note that estimates of buffer size due to reordering depend on We note that estimates of buffer size due to reordering depend on
greatly on the test stream, in terms of the spacing between test greatly on the test stream, in terms of the spacing between test
packets and their size, especially when packet size is variable. packets and their size, especially when packet size is variable. In
these and other circumstances, it may be most useful to characterize
offset in terms of the payload size(s) of stored packets, using the
Type-P-packet-Byte-Offset-Stream metric.
The byte offset metric can help predict whether reordered packets The byte offset metric can help predict whether reordered packets
will be useful in a general receiver buffer system with finite will be useful in a general receiver buffer system with finite
limits. The limit is expressed as the number of bytes the buffer limits. The limit is expressed as the number of bytes the buffer
can store. can store.
When packets in the stream have variable sizes, it may be most
useful to characterize offset in terms of the payload size(s) of
stored packets, using the Type-P-packet-Byte-Offset-Stream metric.
4.5 Gaps between multiple Reordering Discontinuities 4.5 Gaps between multiple Reordering Discontinuities
4.5.1 Metric Name: 4.5.1 Metric Name:
Type-P-packet-Reordering-Gap-Stream Type-P-packet-Reordering-Gap-Stream
4.5.2 Parameters: 4.5.2 Parameters:
We use the same parameters defined earlier. We use the same parameters defined earlier, but add the convention
that index i' is greater than i, likewise j' > j, and define:
+ Gap(s[j']), the Reordering Gap of packet s[j'] in units of
integer messages
+ GapTime(s[j']), the Reordering Gap of packet s[j'] in units of
time
4.5.3 Definition of Reordering Discontinuity: 4.5.3 Definition of Reordering Discontinuity:
All reordered packets are associated with a packet at a reordering All reordered packets are associated with a packet at a reordering
discontinuity, defined as the in-order packet s[j] that arrived at discontinuity, defined as the in-order packet s[j] that arrived at
the minimum value of j (1<=j<i) for which s[j]> s[i]. the minimum value of j (1<=j<i) for which s[j]> s[i].
Note that s[j] will have been found to cause a sequence Note that s[j] will have been found to cause a sequence
discontinuity, where s > NextExp when evaluated with the reordered discontinuity, where s > NextExp when evaluated with the reordered
singleton metric as described in section 3.4. singleton metric as described in section 3.4.
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 fact is used in the definition of the Reordering Gap, below.
below.
4.5.4 Definition of Reordering Gap: 4.5.4 Definition of Reordering Gap:
A reordering gap is the distance between successive reordering A reordering gap is the distance between successive reordering
discontinuities. Type-P-packet-Reordering-Gap-Stream assigns a value discontinuities. 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
skipping to change at line 679 skipping to change at line 781
reordered packet s[i] with extent e was already detected, and reordered packet s[i] with extent e was already detected, and
i' > i, and i' > i, and
there are no reordering discontinuities between j and j', there are no reordering discontinuities between j and j',
then the Reordering Gap for packet s[j'] is the difference between then the Reordering Gap for packet s[j'] is the difference between
the arrival positions the reordering discontinuities, as shown the arrival positions the reordering discontinuities, as shown
below: below:
Gap(j') = (j') - (j) Gap(s[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(s[j']) = DstTime(j') - DstTime(j)
4.5.5 Discussion 4.5.5 Discussion
When separate reordering discontinuities can be distinguished, then When separate reordering discontinuities can be distinguished, then
a count may also be reported (along with the discontinuity a count may also be reported (along with the discontinuity
description, such as the number of reordered packets associated with description, such as the number of reordered packets associated with
that discontinuity and their extents and offsets). The Gaps between that discontinuity and their extents and offsets). The Gaps between
a sample's reordering discontinuities may be expressed as a a sample's reordering discontinuities may be expressed as a
histogram, to easily summarize the frequency of various gaps. histogram, to easily summarize the frequency of various gaps.
Reporting the mode, average, range, etc. may also summarize the Reporting the mode, average, range, etc. may also summarize the
distributions. distributions.
The Gap metric may help to correlate the frequency of reordering The Gap metric may help to correlate the frequency of reordering
discontinuities with their cause. Gap lengths are also informative discontinuities with their cause. Gap lengths are also informative
to receiver designers, revealing the period of reordering to receiver designers, revealing the period of reordering
discontinuities. The combination of reordering gaps and extent discontinuities. The combination of reordering gaps and extent
reveals whether receivers will be required to handle cases of reveals whether receivers will be required to handle cases of
overlapping reordered packets. overlapping reordered packets.
4.6 Reordering-free Runs 4.6 Reordering-free Runs
This section defines a metric based on a count of consecutive
packets between reordered packets. This section defines a metric based on a count of consecutive in-
order packets between reordered packets.
4.6.1 Metric Name: 4.6.1 Metric Name:
Type-P-packet-Reordering-Free-Run-Stream Type-P-packet-Reordering-Free-Run-Stream
4.6.2 Parameters: 4.6.2 Parameters:
We use the same parameters defined earlier, plus the following: We use the same parameters defined earlier, and define the
r, the run counter following:
n, the number of runs
a, the accumulator of in-order packets + r, the run counter
p, the number of packets
q, the squared sum of the run counters + x, the number of runs, also the number of reordered packets
+ a, the accumulator of in-order packets
+ p, the number of packets (when the stream is complete, p=(x+a)=L)
+ q, the sum of the squares of the runs counted
4.6.3 Definition: 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 in-
packets to the next reordered packet is a Reordering-Free run. Note order packets between reordered packets is a Reordering-Free run.
that the minimum run-length is one according to this definition. A Note that the minimum run-length is zero according to this
pseudo code example follows: definition. A 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 */ x = 0; /* x 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 sum of the squares of the runs counted */
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 = 0;
n++; x++;
} }
Each in-order arrival increments the run counter and the accumulator Each in-order arrival increments the run counter and the accumulator
of in order packets, each reordered packet resets the run counter of in order packets, each reordered packet resets the run counter
after adding it to the accumulator. after adding it to the sum of the squared lengths.
Each arrival of a reordered packet yields a new count in the Run Each arrival of a reordered packet yields a new run count. Long
vector. Long runs accompany periods where order was maintained, runs accompany periods where order was maintained, while short runs
while short runs indicate frequent, or multi-packet reordering. indicate frequent, or multi-packet reordering.
The percent of packets in-order is 100*a/p The percent of packets in-order is 100*a/p
The average Reordering-Free run length is a/n
The average Reordering-Free run length is a/x
The q counter gives an indication of variation of the Reordering- 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)) Free runs from the average by comparing q/a to a/x ((q/a)/(a/x))
4.6.4 Discussion: 4.6.4 Discussion and Illustration:
Type-P-packet-Reordering-Free-Run-Stream parameters give a brief Type-P-packet-Reordering-Free-Run-Stream parameters give a brief
summary of the stream's reordering characteristics including the summary of the stream's reordering characteristics including the
average reordering-free run length, and the variation of run average reordering-free run length, and the variation of run
lengths, therefore a key application of this metric is network lengths, therefore a key application of this metric is network
evaluation. evaluation.
For example for 36 packets with 3 runs of 11 in-order packets we For 36 packets with 3 runs of 11 in-order packets we have:
have:
p = 36 p = 36
n = 3 x = 3
a = 33 a = 33
q = 3 * (11*11) = 363 q = 3 * (11*11) = 363
ave reordering-free run = 11 ave reordering-free run = 11
q/a = 11 q/a = 11
(q/a)/ave = 1.0 (q/a)/(a/x) = 1.0
For 36 packets with 3 runs, 2 of length 1 and one of length 31 For 36 packets with 3 runs, 2 runs of length 1 and one of length 31
p = 36 p = 36
n = 3 x = 3
a = 33 a = 33
q = 1 + 1 + 961 = 963 q = 1 + 1 + 961 = 963
ave reordering-free run = 11 ave reordering-free run = 11
q/a = 29.18 q/a = 29.18
(q/a)/ave = 2.65 (q/a)/(a/x) = 2.65
The variability in run length is prominent in the difference between
the q values (sum of the squared run lengths) and comparing average
run length to the (q/a)/(a/x) ratios (equals 1 when all runs are the
same length).
5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric
This section describes a metric that conveys information associated This section describes a metric that conveys information associated
with the affect of reordering on TCP. However, in order to infer with the affect of reordering on TCP. However, in order to infer
anything about TCP performance, the test stream MUST bear a close anything about TCP performance, the test stream MUST bear a close
resemblance to the TCP sender of interest. RFC 3148 [RFC3148] lists resemblance to the TCP sender of interest. RFC 3148 [RFC3148] lists
the specific aspects of congestion control algorithms that must be the specific aspects of congestion control algorithms that must be
specified. Further, RFC 3148 recommends that Bulk Transfer Capacity specified. Further, RFC 3148 recommends that Bulk Transfer Capacity
metrics SHOULD have instruments to distinguish three cases of packet metrics SHOULD have instruments to distinguish three cases of packet
reordering (in section 3.3). The sample metrics defined above reordering (in section 3.3). The sample metrics defined above
satisfy the requirements to classify packets that are slightly or satisfy the requirements to classify packets that are slightly or
grossly out-of-order. The metric in this section adds the capability grossly out-of-order. The metric in this section adds the capability
to distinguish the case where the Fast Retransmit algorithm is to estimate whether reordering might cause the DUP-ACK threshold to
invoked due to reordering. Additional TCP Kernel Instruments are be exceeded causing the Fast Retransmit algorithm to be invoked.
summarized in [Mat03]. Additional TCP Kernel Instruments are summarized in [Mat03].
5.1 Metric Name: 5.1 Metric Name:
Type-P-packet-n-Reordering-Stream Type-P-packet-n-Reordering-Stream
5.2 Parameter Notation: 5.2 Parameter Notation:
Let n be a positive integer (a parameter). Let k be a positive Let n be a positive integer (a parameter). Let k be a positive
integer equal to the number of packets sent (sample size). Let l be integer equal to the number of packets sent (sample size). Let l be
a non-negative integer representing the number of packets that were a non-negative integer representing the number of packets that were
skipping to change at line 857 skipping to change at line 970
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.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 The n-reordering metric is helpful for matching the duplicate ACK
portion of reordered packets that can or cannot be restored to order threshold setting to a given path. For example, if a path exhibits
in a typical TCP receiver buffer based on their arrival order alone no more than 5-reordering, a DUP-ACK threshold of 6 may avoid
(and without the aid of retransmission). unnecessary retransmissions.
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
previous arriving packet. previous arriving packet.
- For n=3, a NewReno TCP sender would retransmit 1 packet in - For n=3, a NewReno TCP sender would retransmit 1 packet in
response to an instance of 3-reordering and therefore consider this response to an instance of 3-reordering and therefore consider this
packet lost for the purposes of congestion control (the sender will packet lost for the purposes of congestion control (the sender will
half its congestion window). Detecting instances of 3-reordering is half its congestion window, see [RFC2581]). 3 is default threshold
useful for determining the portion of reordered packets that are in for SCTP [RFC2960], and the future Datagram Congestion Control
fact as good as lost. Protocol (DCCP).
A sample's n-reordering may be expressed as a histogram, to A sample's n-reordering may be expressed as a histogram, to
summarize the frequency for each value of n. summarize the frequency for each value of n.
We note that the definition of n-reordering cannot predict the exact We note that the definition of n-reordering cannot predict the exact
number of packets unnecessarily retransmitted by a TCP sender under number of packets unnecessarily retransmitted by a TCP sender under
some circumstances, such as cases with closely-spaced reordered some circumstances, such as cases with closely-spaced reordered
singletons. The definition is less complicated than a TCP singletons. Both time and position influence the sender's behavior.
implementation where both time and position influence the sender's
behavior.
A packet's n-reordering designation is sometimes equal to its A packet's n-reordering designation is sometimes equal to its
reordering extent, e. n-reordering is different in the following reordering extent, e. n-reordering is different in the following
ways: ways:
1. n is a count of early packets with consecutive arrival positions 1. n is a count of early packets with consecutive arrival positions
at the receiver. at the receiver.
2. Reordered packets (Type-P-Reordered=TRUE) may not be n-reordered, 2. Reordered packets (Type-P-Reordered=TRUE) may not be n-reordered,
but will have an extent, e (see the examples). but will have an extent, e (see the examples).
6. Measurement and Implementation Issues 6. Measurement and Implementation Issues
The results of tests will be dependent on the time interval between The results of tests will be dependent on the time interval between
measurement packets (both at the Source, and during transport where measurement packets (both at the Source, and during transport where
spacing may change). Clearly, packets launched infrequently (e.g., spacing may change). Clearly, packets launched infrequently (e.g.,
1 per 10 seconds) are unlikely to be reordered. 1 per 10 seconds) are unlikely to be reordered.
In order to gauge the reordering for an application according to the
metrics defined in this memo, it is RECOMMENDED to use the same
sending pattern as the application of interest. In any case, the
exact method of packet generation MUST be reported with the
measurement results, including all stream parameters.
+ To make inferences about applications that use TCP, it is
REQUIRED to use TCP-like Streams as in [RFC3148]
+ For real-time applications, it is RECOMMENDED to use Periodic
Streams as in [RFC3432]
It is acceptable to report the metrics of Sections 3 and 4 with
other IPPM metrics using Poisson Streams [RFC2330]. Poisson streams
represent an "unbiased sample" of network performance for packet
loss and delay metrics. However, it would be incorrect to make
inferences about the application categories above using reordering
metrics measured with Poisson streams.
Test stream designers may prefer to use a periodic sending interval Test stream designers may prefer to use a periodic sending interval
so that a known temporal bias is maintained, also bringing so that a known temporal bias is maintained, also bringing
simplified results analysis (as described in [RFC3432]). In this simplified results analysis (as described in [RFC3432]). In this
case, it is RECOMMENDED that the periodic sending interval should be case, it is RECOMMENDED that the periodic sending interval should be
chosen to reproduce the closest Source packet spacing expected (down chosen to reproduce the closest Source packet spacing expected.
to the link speed serialization time limit). Use of the closest Testers must recognize that streams sent at the link speed
possible spacing should reveal the greatest extent of steady-state serialization limit MUST have limited duration and MUST consider
reordering on the path. Of course, packet spacing is likely to vary packet loss as an indication that the stream has caused congestion,
as the stream traverses the test path. In any case, the exact method and suspend further testing.
of packet generation MUST be reported with measurement results,
including all stream parameters.
When intending to compare or concatenate independent measurements of When intending to compare or concatenate independent measurements of
reordering, it is RECOMMENDED to use the same test stream parameters reordering, it is RECOMMENDED to use the same test stream parameters
in each measurement system. in each measurement system.
Packet lengths might also be varied to attempt to detect instances Packet lengths might also be varied to attempt to detect instances
of parallel processing (they may cause steady state reordering). For of parallel processing (they may cause steady state reordering). For
example, a line-speed burst of the longest (MTU-length) packets example, a line-speed burst of the longest (MTU-length) packets
followed by a burst of the shortest possible packets may be an followed by a burst of the shortest possible packets may be an
effective detecting pattern. Other size patterns are possible. effective detecting pattern. Other size patterns are possible.
The non-reversing order criterion and all metrics described above The non-reversing order criterion and all metrics described above
remain valid and useful when a stream of packets experiences packet remain valid and useful when a stream of packets experiences packet
loss, or both loss and reordering. In other words, losses alone do loss, or both loss and reordering. In other words, losses alone do
not cause subsequent packets to be declared reordered. not cause subsequent packets to be declared reordered.
Assuming that the necessary sequence information (sequence number Assuming that the necessary sequence information (message number) is
and/or source time stamp) is included in the packet payload included in the packet payload (possibly in application headers such
(possibly in application headers such as RTP), packet sequence may as RTP), reordering metrics may be evaluated in a passive
be evaluated in a passive measurement arrangement. Also, it is measurement arrangement. Also, it is possible to evaluate order at
possible to evaluate order at a single point along a path, since the any point along a Source-Destination path, recognizing that
usual need for synchronized Src and Dst Clocks may be relaxed to intermediate measurements may differ from those made at the
some extent. Destination (where reordering's affect on applications can be
inferred).
It is possible to apply these metrics to evaluate reordering in a It is possible to apply these metrics to evaluate reordering in a
TCP sender's stream. In this case, the Source sequence numbers would TCP sender's stream. In this case, the Source sequence numbers would
be based on byte stream, or segment numbering. Since the stream may be based on byte stream, or segment numbering. Since the stream may
include retransmissions due to loss or reordering, care must be include retransmissions due to loss or reordering, care must be
taken to avoid declaring retransmitted packets reordered. The taken to avoid declaring retransmitted packets reordered. The
additional sequence reference of either s or SrcTime help to avoid additional sequence reference of s or SrcTime helps to avoid this
this ambiguity. ambiguity, or the optional TCP timestamp field [RFC1323].
Since this metric definition may use sequence numbers with finite Since this metric definition may use sequence numbers with finite
range, it is possible that the sequence numbers could reach end-of- range, it is possible that the sequence numbers could reach end-of-
range and roll over to zero during a measurement. By definition, range and roll over to zero during a measurement. By definition,
the Next Expected value cannot decrease, and all packets received the Next Expected value cannot decrease, and all packets received
after a roll-over would be declared reordered. Sequence number after a roll-over would be declared reordered. Sequence number
roll-over can be avoided by using combinations of counter size and roll-over can be avoided by using combinations of counter size and
test duration where roll-over is impossible (and sequence is reset test duration where roll-over is impossible (and sequence is reset
to zero at the start). Also, message-based numbering results in to zero at the start). Also, message-based numbering results in
slower sequence consumption. There may still be cases where slower sequence consumption. There may still be cases where
skipping to change at line 998 skipping to change at line 1126
would not be possible. would not be possible.
The requirement to ignore duplicate packets also mandates storage. 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 size. 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 (NextExp - 1) are sufficient sequence number received thus far (NextExp - 1) are sufficient
information to determine if a packet is a duplicate (assuming a information to determine if a packet is a duplicate (assuming a
manageable storage size for packets that are missing due to loss). manageable storage size for packets that are missing due to loss).
Some in-order packet arrivals may not be useful to TCP receivers,
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.
Last, we note that determining reordering extents and gaps is tricky Last, we note that determining reordering extents and gaps is tricky
when there are overlapped or nested events. Test instrument when there are overlapped or nested events. Test instrument
complexity and reordering complexity are directly correlated. complexity and reordering complexity are directly correlated.
7. Examples of Arrival Order Evaluation 7. Examples of Arrival Order Evaluation
This section provides some examples to illustrate how the non- This section provides some examples to illustrate how the non-
reversing order criterion works, how n-reordering works in reversing order criterion works, how n-reordering works in
comparison, and the value of viewing reordering in all the comparison, and the value of quantifying reordering in all the
dimensions of time, bytes, and position. dimensions of time, bytes, and position.
Throughout this section, we will refer to packets by their source Throughout this section, we will refer to packets by their source
sequence number, except where noted. So "Packet 4" refers to the sequence number, except where noted. So "Packet 4" refers to the
packet with source sequence number 4, and the reader should refer to packet with source sequence number 4, and the reader should refer to
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 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. All packets contain 100 bytes,
beginning with s=1 and (s x 100)-99 for s=2,3,4,...
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
3 3 40 108 68 0 3 3 3 40 108 68 0 3
5 4 80 148 68 -82 4 5 4 80 148 68 -82 4
6 6 100 168 68 0 5 6 6 100 168 68 0 5
skipping to change at line 1196 skipping to change at line 1322
when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not designated when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not designated
as n-reordered. We find the same to for Packet 6. as n-reordered. We find the same to for Packet 6.
We now consider whether reordered Packets 5 and 6 are associated We now consider whether reordered Packets 5 and 6 are associated
with the same reordering discontinuity as Packet 4. Using the test with the same reordering discontinuity as Packet 4. Using the test
of Section 4.2.3, we find that the minimum j=4 for all three of Section 4.2.3, we find that the minimum j=4 for all three
packets. They are all associated with the reordering discontinuity packets. They are all associated with the reordering discontinuity
at Packet 7. at Packet 7.
This example shows again that the n-reordering definition identifies This example shows again that the n-reordering definition identifies
a single Packet (4) with a sufficient degree of reordering to result a single Packet (4) with a sufficient degree of n-reordering that
in one unnecessary packet retransmission by the New Reno TCP sender. might cause one unnecessary packet retransmission by the New Reno
Also, the reordered arrival of Packets 5 and 6 will allow the TCP sender (with DUP-ACK threshold=3 or 4). Also, the reordered
receiver process to pass Packets 7 through 10 up the protocol stack arrival of Packets 5 and 6 will allow the receiver process to pass
(the singleton Type-P-Reordered = TRUE for Packets 5 and 6, and they Packets 7 through 10 up the protocol stack (the singleton Type-P-
are all associated with a single reordering discontinuity). Reordered = TRUE for Packets 5 and 6, and they are all associated
with a single reordering discontinuity).
7.4 Example with Multiple Packet Reordering Discontinuities 7.4 Example with Multiple Packet Reordering Discontinuities
Table 4 Example with Multiple Packet Reordering Discontinuities Table 4 Example with Multiple Packet Reordering Discontinuities
Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
Discontinuity Discontinuity Discontinuity Discontinuity
|---------Gap---------| |---------Gap---------|
s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16 s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
r = 1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, ... r = 1, 2, 3, 4, 5, 0, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, ...
number of runs,n = 1 2 3 number of runs,n = 1 2 3
end r counts = 5 1 6 end r counts = 5 0 5
(these values are computed after the packet arrives)
Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has 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(s[j']) = (j') - (j)
Gap(11) = (11) - (4) = 7 Gap(Packet 12) = (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, 0, and 5.
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 capture the distance between reordered packets. reordering-free runs capture the distance between reordered packets.
8. Security Considerations 8. Security Considerations
8.1 Denial of Service Attacks 8.1 Denial of Service Attacks
skipping to change at line 1256 skipping to change at line 1384
packets or other escalation procedures defined between the affected packets or other escalation procedures defined between the affected
parties. 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. In most cases, a
hashing function will produce a value suitable for payload
comparisons.
8.3 Interference with the metric 8.3 Interference with the metric
It may be possible to identify that a certain packet or stream of It may be possible to identify that a certain packet or stream of
packets is part of a sample. With that knowledge at the destination packets is part of a sample. With that knowledge at the destination
and/or the intervening networks, it is possible to change the and/or the intervening networks, it is possible to change the
processing of the packets (e.g. increasing or decreasing delay) that processing of the packets (e.g. increasing or decreasing delay) that
may distort the measured performance. It may also be possible to may distort the measured performance. It may also be possible to
generate additional packets that appear to be part of the sample generate additional packets that appear to be part of the sample
metric. These additional packets are likely to perturb the results metric. These additional packets are likely to perturb the results
skipping to change at line 1320 skipping to change at line 1450
[Cia00] L.Ciavattone and A.Morton, "Out-of-Sequence Packet [Cia00] L.Ciavattone and A.Morton, "Out-of-Sequence Packet
Parameter Definition (for Y.1540)", Contribution number Parameter Definition (for Y.1540)", Contribution number
T1A1.3/2000-047, October 30, 2000. T1A1.3/2000-047, October 30, 2000.
ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc
[Cia03] L.Ciavattone, A.Morton, and G.Ramachandran, "Standardized [Cia03] L.Ciavattone, A.Morton, and G.Ramachandran, "Standardized
Active Measurements on a Tier 1 IP Backbone," IEEE Active Measurements on a Tier 1 IP Backbone," IEEE
Communications Mag., pp 90-97, June 2003. Communications Mag., pp 90-97, June 2003.
[I.356] ITU-T Recommendation I.356, "B-ISDN ATM layer cell
transfer performance", March 2000.
[Jai02] S.Jaiswal et al., "Measurement and Classification of Out- [Jai02] S.Jaiswal et al., "Measurement and Classification of Out-
of-Sequence Packets in a Tier-1 IP Backbone," Proceedings of-Sequence Packets in a Tier-1 IP Backbone," Proceedings
of the ACM SIGCOMM Internet Measurement Workshop 2002, of the ACM SIGCOMM Internet Measurement Workshop 2002,
November 6-8, Marseille, France. November 6-8, Marseille, France.
[Lou01] D.Loguinov and H.Radha, "Measurement Study of Low-bitrate [Lou01] 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, Internet Measurement Workshop 2001 November 1-2, 2001,
San Francisco, USA. San Francisco, USA.
skipping to change at line 1343 skipping to change at line 1476
2003. http://www.web100.org/docs/mathis03web100.pdf 2003. http://www.web100.org/docs/mathis03web100.pdf
[Pax98] V.Paxson, "Measurements and Analysis of End-to-End [Pax98] V.Paxson, "Measurements and Analysis of End-to-End
Internet Dynamics," Ph.D. dissertation, U.C. Berkeley, Internet Dynamics," Ph.D. dissertation, U.C. Berkeley,
1997, ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz. 1997, ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz.
[RFC793] Postel, J., "Transmission Control Protocol", STD 7, RFC [RFC793] Postel, J., "Transmission Control Protocol", STD 7, RFC
793, September 1981. 793, September 1981.
Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt
[RFC1323] Jacobson, V., Braden, R., and Borman, D., "TCP Extensions
for High Performance", RFC 1323, May 1992.
[RFC2581] Allman, M., Paxson, V., and Stevens, W., "TCP Congestion
Control", RFC 2581, April 1999.
[RFC2960] Stewart, R., et al., "Stream Control Transmission
Protocol", RFC 2960, October 2000.
[RFC3393] Demichelis, C., and Chimento, P., "IP Packet Delay [RFC3393] Demichelis, C., and Chimento, P., "IP Packet Delay
Variation Metric for IP Performance Metrics (IPPM)", RFC Variation Metric for IP Performance Metrics (IPPM)", RFC
3393, November 2002. 3393, November 2002.
[Y.1540] ITU-T Recommendation Y.1540, "Internet protocol data
communication service - IP packet transfer and
availability performance parameters", December 2002.
12. Acknowledgments 12. Acknowledgments
The authors would like to acknowledge many helpful discussions with The authors would like to acknowledge many helpful discussions with
Matt Zekauskas, Jon Bennett (who authored the sections on Matt Zekauskas, Jon Bennett (who authored the sections on
Reordering-Free Runs), and Matt Mathis. We thank David Newman, Henk Reordering-Free Runs), and Matt Mathis. We thank David Newman, Henk
Uijterwall, and Mark Allman for their reviews and suggestions, and Uijterwall, Mark Allman, Vern Paxson, and Phil Chimento for their
Michal Przybylski for sharing implementation experiences with us on reviews and suggestions, and Michal Przybylski for sharing
the ippm-list. We gratefully acknowledge the foundation laid by the implementation experiences with us on the ippm-list. We gratefully
authors of the IP performance Framework [RFC2330]. acknowledge the foundation laid by the authors of the IP performance
Framework [RFC2330].
13. Appendix A Example Implementations in C (Informative) 13. Appendix A Example Implementations in C (Informative)
Two example c-code implementations of reordering definitions follow: Two example c-code implementations of reordering definitions follow:
Example 1 n-reordering ============================================ Example 1 n-reordering ============================================
#include <stdio.h> #include <stdio.h>
#define MAXN 100 #define MAXN 100
skipping to change at line 1410 skipping to change at line 1557
ring[r] = s; ring[r] = s;
} }
for (j = 0; j < MAXN && m[j]; j++) for (j = 0; j < MAXN && m[j]; j++)
printf("%d-reordering = %f%%\n", j+1, 100.0*m[j]/(l-j-1)); printf("%d-reordering = %f%%\n", j+1, 100.0*m[j]/(l-j-1));
if (j == 0) printf("no reordering\n"); if (j == 0) printf("no reordering\n");
else if (j < MAXN) 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", MAXN); 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 =======
Author: Jerry Perser 7-2002 (mod by acm 12-2004)
Compile: $ gcc -o jpboth file.c
Usage: $ jpboth 1 2 3 7 8 4 5 6 (pkt sequence given on cmdline)
Note to cut/pasters: line 59 may need repair
*/
#include <stdio.h> #include <stdio.h>
#define MAXN 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 + MAXN) #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 received */
int reorder_packets=0; /* number of reordered packets */ int reorder_packets_Al=0; /* num reordered pkts (singleton) */
int reorder_packets_Stas=0; /* num reordered pkts(n-reordering)*/
/* function to test if current packet has been reordered /* 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
{ {
static int NextExp = 1; static int NextExp = 1;
int iReturn = 0; int iReturn = 0;
skipping to change at line 1460 skipping to change at line 1613
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_Al += testorder1(packet); // singleton
reorder_packets_Stas += testorder2(packet); //n-reord.
} }
printf("Received packets = %d, Reordered packets = %d\n", printf("Received packets = %d, Singleton Reordered = %d, n-
receive_packets, reorder_packets); reordered = %d\n", receive_packets, reorder_packets_Al,
reorder_packets_Stas );
exit(0); exit(0);
} }
Reference Reference
ISO/IEC 9899:1999 (E), as amended by ISO/IEC 9899:1999/Cor.1:2001 ISO/IEC 9899:1999 (E), as amended by ISO/IEC 9899:1999/Cor.1:2001
(E). Also published as: (E). Also published as:
The C Standard: Incorporating Technical Corrigendum 1, British The C Standard: Incorporating Technical Corrigendum 1, British
Standards Institute, ISBN: 0-470-84573-2, Hardcover, 558 pages, Standards Institute, ISBN: 0-470-84573-2, Hardcover, 558 pages,
September 2003. September 2003.
14. Appendix B Fragment Order Evaluation (Informative) 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
skipping to change at line 1611 skipping to change at line 1765
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
AT&T Labs AT&T Labs
Room C4 - 2B29 Room C2 - 3D02
200 Laurel Ave. South 200 Laurel Ave. South
Middletown, NJ 07748 USA Middletown, NJ 07748 USA
Phone +1 732 420 1239 Phone +1 732 420 1239
EMail: <lencia@att.com> EMail: <lencia@att.com>
Gomathi Ramachandran Gomathi Ramachandran
AT&T Labs AT&T Labs
Room C4 - 3D22 Room C4 - 3D22
200 Laurel Ave. South 200 Laurel Ave. South
Middletown, NJ 07748 USA Middletown, NJ 07748 USA
skipping to change at line 1640 skipping to change at line 1794
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 (2004). This document is subject Copyright (C) The Internet Society (2005). This document is subject
to the rights, licenses and restrictions contained in BCP 78 and to the rights, licenses and restrictions contained in BCP 78 and
except as set forth therein, the authors retain all their rights. except as set forth therein, the authors retain all their rights.
This document and the information contained herein are provided on This document and the information contained herein are provided on
an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE
INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
 End of changes. 

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