draft-ietf-ippm-reordering-11.txt   draft-ietf-ippm-reordering-12.txt 
Network Working Group A.Morton Network Working Group A.Morton
Internet Draft L.Ciavattone Internet Draft L.Ciavattone
Document: <draft-ietf-ippm-reordering-11.txt> G.Ramachandran Document: <draft-ietf-ippm-reordering-12.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 Veriwave
Packet Reordering Metric for IPPM Packet Reordering Metric for IPPM
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79. aware will be disclosed, in accordance with Section 6 of BCP 79.
skipping to change at line 41 skipping to change at line 41
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 (2005). Copyright (C) The Internet Society (2006).
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, including for the new metrics and discusses the measurement issues, including
the context information required for all metrics. The memo first the context information required for all metrics. The memo first
defines a reordered singleton, and then uses it as the basis for defines a reordered singleton, and then uses it as the basis for
sample metrics to quantify the extent of reordering in several 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 distance between separate occurrences. We then define a metric
oriented toward assessing reordering affects on TCP. Several oriented toward assessing reordering effects on TCP. Several
examples of evaluation using the various sample metrics are examples of evaluation using the various sample metrics are
included. An Appendix gives extended definitions for evaluating included. An Appendix gives extended definitions for evaluating
order with packet fragmentation. 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....................................................4 2. Introduction....................................................4
2.1 Motivation.....................................................4 2.1 Motivation.....................................................4
2.2 Goals and Objectives...........................................5 2.2 Goals and Objectives...........................................5
2.3 Required Context for All Reordering Metrics....................6 2.3 Required Context for All Reordering Metrics....................6
3. A Reordered Packet Singleton Metric.............................6 3. A Reordered Packet Singleton Metric.............................6
3.1 Metric Name:...................................................7 3.1 Metric Name....................................................7
3.2 Metric Parameters:.............................................7 3.2 Metric Parameters..............................................7
3.3 Definition:....................................................7 3.3 Definition.....................................................7
3.4 Sequence Discontinuity Definition..............................8 3.4 Sequence Discontinuity Definition..............................8
3.5 Evaluation of Reordering in Dimensions of Time or Bytes........9 3.5 Evaluation of Reordering in Dimensions of Time or Bytes........9
3.6 Discussion.....................................................9 3.6 Discussion.....................................................9
4. Sample Metrics.................................................10 4. Sample Metrics.................................................10
4.1 Reordered Packet Ratio........................................10 4.1 Reordered Packet Ratio........................................10
4.1.1 Metric Name:................................................10 4.1.1 Metric Name.................................................10
4.1.2 Metric Parameters:..........................................10 4.1.2 Metric Parameters...........................................10
4.1.3 Definition:.................................................10 4.1.3 Definition..................................................10
4.1.4 Discussion..................................................11 4.1.4 Discussion..................................................11
4.2 Reordering Extent.............................................11 4.2 Reordering Extent.............................................11
4.2.1 Metric Name:................................................11 4.2.1 Metric Name.................................................11
4.2.2 Notation and Metric Parameters:.............................11 4.2.2 Notation and Metric Parameters..............................11
4.2.3 Definition:.................................................12 4.2.3 Definition..................................................12
4.2.4 Discussion:.................................................12 4.2.4 Discussion..................................................12
4.3 Reordering Late Time Offset...................................13 4.3 Reordering Late Time Offset...................................13
4.3.1 Metric Name:................................................13 4.3.1 Metric Name.................................................13
4.3.2 Metric Parameters:..........................................13 4.3.2 Metric Parameters...........................................13
4.3.3 Definition:.................................................13 4.3.3 Definition..................................................13
4.3.4 Discussion..................................................13 4.3.4 Discussion..................................................13
4.4 Reordering Byte Offset........................................14 4.4 Reordering Byte Offset........................................14
4.4.1 Metric Name:................................................14 4.4.1 Metric Name.................................................14
4.4.2 Metric Parameters:..........................................14 4.4.2 Metric Parameters...........................................14
4.4.3 Definition:.................................................14 4.4.3 Definition..................................................14
4.4.4 Discussion..................................................15 4.4.4 Discussion..................................................15
4.5 Gaps between multiple Reordering Discontinuities..............15 4.5 Gaps between multiple Reordering Discontinuities..............15
4.5.1 Metric Name:................................................15 4.5.1 Metric Name.................................................15
4.5.2 Parameters:.................................................15 4.5.2 Parameters..................................................15
4.5.3 Definition of Reordering Discontinuity:.....................16 4.5.3 Definition of Reordering Discontinuity......................16
4.5.4 Definition of Reordering Gap:...............................16 4.5.4 Definition of Reordering Gap................................16
4.5.5 Discussion..................................................16 4.5.5 Discussion..................................................17
4.6 Reordering-free Runs..........................................17 4.6 Reordering-free Runs..........................................17
4.6.1 Metric Name:................................................17 4.6.1 Metric Name.................................................17
4.6.2 Parameters:.................................................17 4.6.2 Parameters..................................................17
4.6.3 Definition:.................................................17 4.6.3 Definition..................................................17
4.6.4 Discussion and Illustration:................................18 4.6.4 Discussion and Illustration.................................18
5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..19 5. Metrics Focused on Receiver Assessment: A TCP-Relevant Metric..19
5.1 Metric Name:..................................................19 5.1 Metric Name...................................................19
5.2 Parameter Notation:...........................................19 5.2 Parameter Notation............................................19
5.3 Definitions...................................................19 5.3 Definitions...................................................19
5.4 Discussion:...................................................20 5.4 Discussion....................................................20
6. Measurement and Implementation Issues..........................21 6. Measurement and Implementation Issues..........................21
7. Examples of Arrival Order Evaluation...........................24 7. Examples of Arrival Order Evaluation...........................24
7.1 Example with a single packet reordered........................24 7.1 Example with a Single Packet Reordered........................24
7.2 Example with two packets reordered............................25 7.2 Example with Two Packets Reordered............................25
7.3 Example with three packets reordered..........................27 7.3 Example with Three Packets Reordered..........................27
7.4 Example with Multiple Packet Reordering Discontinuities.......28 7.4 Example with Multiple Packet Reordering Discontinuities.......28
8. Security Considerations........................................28 8. Security Considerations........................................28
8.1 Denial of Service Attacks.....................................28 8.1 Denial of Service Attacks.....................................28
8.2 User data confidentiality.....................................29 8.2 User Data Confidentiality.....................................29
8.3 Interference with the metric..................................29 8.3 Interference with the Metric..................................29
9. IANA Considerations............................................29 9. IANA Considerations............................................29
10. Normative References..........................................29 10. Normative References..........................................31
11. Informative References........................................30 11. Informative References........................................31
12. Acknowledgments...............................................31 12. Acknowledgments...............................................33
13. Appendix A Example Implementations in C (Informative).........31 13. Appendix A Example Implementations in C (Informative).........33
14. Appendix B Fragment Order Evaluation (Informative)............34 14. Appendix B Fragment Order Evaluation (Informative)............35
14.1 Metric Name:.................................................34 14.1 Metric Name..................................................36
14.2 Additional Metric Parameters:................................34 14.2 Additional Metric Parameters.................................36
14.3 Definition:..................................................35 14.3 Definition...................................................36
14.4 Discussion: Notes on Sample Metrics when evaluating Fragments36 14.4 Discussion: Notes on Sample Metrics when Evaluating Fragments38
15. Author's Addresses............................................36 15. Author's Addresses............................................38
Full Copyright Statement..........................................37 Full Copyright Statement..........................................39
Intellectual Property.............................................37 Intellectual Property.............................................39
Acknowledgement...................................................38 Acknowledgement...................................................39
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 [RFC2119]. Although
Although RFC 2119 was written with protocols in mind, the key words RFC 2119 was written with protocols in mind, the key words are used
are used in this document for similar reasons. They are used to in this document for similar reasons. They are used to ensure the
ensure the results of measurements from two different results of measurements from two different implementations are
implementations are comparable, and to note instances when an comparable, and to note instances when an implementation could
implementation could perturb the network. perturb the network.
In this memo, the characters "<=" should be read as "less than or In this memo, the characters "<=" should be read as "less than or
equal to" and ">=" as "greater than or equal to". equal to" and ">=" as "greater than or equal to".
2. Introduction 2. Introduction
Ordered arrival is a property found in packets that transit their Ordered arrival is a property found in packets that transit their
path, where the packet sequence number increases with each new path, where the packet sequence number increases with each new
arrival and there are no backward steps. The Internet Protocol arrival and there are no backward steps. The Internet Protocol
[RFC791] has no mechanisms to assure either packet delivery or [RFC791] has no mechanisms to assure either packet delivery or
sequencing, and higher layer protocols (above IP) should be prepared sequencing, and higher layer protocols (above IP) should be prepared
to deal with both loss and reordering. This memo defines reordering to deal with both loss and reordering. This memo defines reordering
metrics. metrics.
A unique sequence number, such as an incrementing message number A unique sequence identifier carried in each packet, such as an
carried in each packet, establishes the Source Sequence. incrementing consecutive integer message number, 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 [RFC2330], and classifies arriving
arriving packets with sequence numbers smaller than their packets with sequence numbers smaller than their predecessors as
predecessors as out-of-order, or reordered. For example, if out-of-order, or reordered. For example, if sequentially numbered
sequentially numbered packets arrive 1,2,4,5,3, then packet 3 is packets arrive 1,2,4,5,3, then packet 3 is reordered. This is
reordered. This is equivalent to Paxon's reordering definition in equivalent to Paxon's reordering definition in [Pax98], where "late"
[Pax98], where "late" packets were declared reordered. The packets were declared reordered. The alternative is to emphasize
alternative is to emphasize "premature" packets instead (4 and 5 in "premature" packets instead (4 and 5 in the example), but only the
the example), but only the arrival of packet 3 distinguishes this arrival of packet 3 distinguishes this circumstance from packet
circumstance from packet loss. Focusing attention on late packets loss. Focusing attention on late packets allows us to maintain
allows us to maintain orthogonality with the packet loss metric. The orthogonality with the packet loss metric. The metric's construction
metric's construction is very similar to the sequence space is very similar to the sequence space validation for received
validation for received segments in RFC 793 [RFC793]. Earlier work segments in [RFC793]. Earlier work to define ordered delivery
to define ordered delivery includes [Cia00], [Ben99], [Lou01], includes [Cia00], [Ben99], [Lou01], [Bel02], [Jai02] and [Cia03].
[Bel02], [Jai02] and [Cia03].
2.1 Motivation 2.1 Motivation
A reordering metric is relevant for most applications, especially A reordering metric is relevant for most applications, especially
when assessing network support for Real-Time media streams. The when assessing network support for Real-Time media streams. The
extent of reordering may be sufficient to cause a received packet to extent of reordering may be sufficient to cause a received packet to
be discarded by functions above the IP layer. be discarded by functions above the IP layer.
Packet order 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.
skipping to change at line 241 skipping to change at line 241
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. (We define a number of 2. Quantifying the degree of reordering. (We define a number of
metrics to meet this goal, because receiving procedures differ metrics to meet this goal, because receiving procedures differ
by protocol or application. Since the affects of packet by protocol or application. Since the effects of packet
reordering vary with these procedures, a metric that quantifies reordering vary with these procedures, a metric that quantifies
a key aspect of one receiver's behavior could be irrelevant to a key aspect of one receiver's behavior could be irrelevant to
a different receiver. If all the metrics defined below are a different receiver. If all the metrics defined below are
reported, they give a wide-ranging view of reordering reported, they give a wide-ranging view of reordering
conditions.) conditions.)
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 view of the
group's view. interested community.
+ 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:
+ ability to concatenate results for segments measured separately + ability to concatenate results for segments measured separately
to estimate the reordering of an entire path to estimate the reordering of an entire path
+ simplicity for easy consumption and understanding + simplicity for easy consumption and understanding
+ relevance to TCP design + 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 meets 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 measurements of path segments exhibit no reordering, and one
segment concatenation would also exhibit this desirable outcome). may estimate that the complete path composed of these segments would
However, satisfying these goals restricts the set of metrics to also exhibit no reordering). However, satisfying these goals
those that provide some clear insight into network characterization restricts the set of metrics to those that provide some clear
or receiver design. They are not likely to be exhaustive in their insight into network characterization or receiver design. They are
coverage of reordering effects on applications, and additional not likely to be exhaustive in their coverage of reordering effects
measurements may be possible. on applications, and additional measurements may be possible.
2.3 Required Context for All Reordering Metrics 2.3 Required Context for All Reordering Metrics
A critical aspect of all reordering metrics is their inseparable A critical aspect of all reordering metrics is their inseparable
bond with the measurement conditions. Packet reordering is not well bond with the measurement conditions. Packet reordering is not well
defined unless the full measurement context is reported. Therefore, defined unless the full measurement context is reported. Therefore,
all reordering metric definitions include the following parameters: all reordering metric definitions include the following parameters:
1. The "Packet of Type-P" [RFC2330] identifiers for the packet 1. The "Packet of Type-P" [RFC2330] identifiers for the packet
stream, including the transport addresses for source and stream, including the transport addresses for source and
destination, and any other information which may result in different destination, and any other information which may result in different
packet treatments. packet treatments.
2. The stream parameter set for the sending discipline, such as the 2. The stream parameter set for the sending discipline, such as the
parameters unique to Periodic Streams (as in RFC 3432 [RFC3432]), parameters unique to Periodic Streams (as in [RFC3432]), TCP-like
TCP-like Streams (as in RFC 3148 [RFC3148]), or Poisson Streams (as Streams (as in [RFC3148]), or Poisson Streams (as in [RFC2330]). The
in RFC 2330 [RFC2330]. The stream parameters include the packet stream parameters include the packet size, either specified as a
size, either specified as a fixed value or as a pattern of sizes (as fixed value or as a pattern of sizes (as applicable).
applicable).
Whenever a metric is reported, it MUST include a description of Whenever a metric is reported, it MUST include a description of
these parameters to provide a context for the results. 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 [RFC2330] describes the notions of singletons,
singletons, samples, and statistics. For easy reference: samples, and statistics. For easy reference:
By a 'singleton' metric, we refer to metrics that are, By a 'singleton' metric, we refer to metrics that are,
in a sense, atomic. For example, a single instance of "bulk in a sense, atomic. For example, a single instance of "bulk
throughput capacity" from one host to another might be defined throughput capacity" from one host to another might be defined
as a singleton metric, even though the instance involves as a singleton metric, even though the instance involves
measuring the timing of a number of Internet packets. measuring the timing of a number of Internet packets.
The evaluation of packet order requires several supporting concepts. The evaluation of packet order requires several supporting concepts.
The first is an algorithm (function) that produces a series of The first is an algorithm (function) that produces a series of
monotonically increasing identifiers applied to packets at the monotonically increasing identifiers applied to packets at the
source to uniquely establish the order of packet transmission. The source to uniquely establish the order of packet transmission. The
unique sequence identifier may simply be an incrementing integer unique sequence identifier may simply be an incrementing consecutive
message number, as used below. integer message number, or sequence number as used below. The
prospect of sequence number roll-over is discussed in Section 6.
The second supporting concept is a stored value which is the "next The second supporting concept is a stored value which is the "next
expected" packet number. Under normal conditions, the value of Next expected" packet number. Under normal conditions, the value of Next
Expected (NextExp) is the sequence number of the previous packet Expected (NextExp) is the sequence number of the previous packet
plus 1 for message numbering (in general, the receiver reproduces plus 1 for message numbering (in general, the receiver reproduces
the sender's algorithm and the sequence of identifiers so that the the sender's algorithm and the sequence of identifiers so that the
"next expected" can be determined). "next expected" can be determined).
Each packet within a packet stream can be evaluated with this order Each packet within a packet stream can be evaluated with this order
singleton metric. singleton metric.
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.
skipping to change at line 353 skipping to change at line 353
And optionally: 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 bytes field and referred to when the SrcByte sequence is based on bytes
transfered. transfered.
+ SrcByte, the packet sequence number applied at the Source, in + SrcByte, the packet sequence number applied at the Source, in
units of payload bytes. units of payload bytes.
3.3 Definition: 3.3 Definition
If a packet s, (sent at time, SrcTime) is found to be reordered by If a packet s, (sent at time, SrcTime) is found to be reordered by
comparison with the Next Expected value, its Type-P-Reordered = comparison with the Next Expected value, its Type-P-Reordered =
TRUE; otherwise Type-P-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, the NextExp value does not packet is reordered). In this case, the NextExp value does not
change. 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 for (the packet is in-order). In this case, NextExp is set to s+1 for
skipping to change at line 413 skipping to change at line 412
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;
Whether there are any Sequence Discontinuities and their size is Whether any Sequence Discontinuities occur (and their size) is
determined by the conditions causing loss and/or reordering along determined by the conditions causing loss and/or reordering along
the measurement path. Note that a packet could be reordered at one the measurement path. Note that a packet could be reordered at one
point, and subsequently lost elsewhere on the path, but this cannot point, and subsequently lost elsewhere on the path, but this cannot
be known from observations at the Destination. be known from observations at the Destination.
3.5 Evaluation of Reordering in Dimensions of Time or Bytes 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
skipping to change at line 440 skipping to change at line 439
It is possible to detect Sequence Discontinuities with payload byte It is possible to detect Sequence Discontinuities with payload byte
numbering, but only when the complete pattern of payload sizes is numbering, but only when the complete pattern of payload sizes is
stored at the Destination, or when payload size is constant and then stored at the Destination, or when payload size is constant and then
the byte numbering adds needless complexity over message numbering. 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 in sections
4.3 and 4.4.
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 (Type-P-Reordered=FALSE). designated in-order (Type-P-Reordered=FALSE).
skipping to change at line 463 skipping to change at line 463
metric to evaluate reordering among packet fragments, but each metric to evaluate reordering among packet fragments, but each
fragment must contain source sequence information. fragment must contain source sequence information.
See the Appendix on fragment order evaluation for more detail. See the Appendix on fragment order evaluation for more detail.
If duplicate packets (multiple non-corrupt copies) arrive at the If duplicate packets (multiple non-corrupt copies) arrive at the
destination, they MUST be noted and only the first to arrive is destination, they MUST be noted and only the first to arrive is
considered for further analysis (copies would be declared reordered considered for further analysis (copies would be declared reordered
according to the definition above). This requirement has the same according to the definition above). This requirement has the same
storage implications as earlier IPPM metrics, and follows the storage implications as earlier IPPM metrics, and follows the
precedent of RFC 2679. We provide a suggestion to minimize storage precedent of RFC 2679. We provide a suggestion to minimize storage
size needed in the section on Measurement and Implementation Issues. size needed in Section 6 on Measurement and Implementation Issues.
4. Sample Metrics 4. Sample Metrics
In this section, we define metrics applicable to a sample of packets In this section, we define metrics applicable to a sample of packets
from a single Source sequence number system. When reordering occurs, from a single Source sequence number system. When reordering occurs,
it is highly desirable to assert the degree to which a packet is it is highly desirable to assert the degree to which a packet is
out-of-order, or reordered with respect other packets. This section out-of-order, or reordered with respect other packets. This section
defines several metrics that quantify the extent of reordering in defines several metrics that quantify the extent of reordering in
various units of measure. Each metric highlights a relevant use. various units of measure. Each metric highlights a relevant use.
The metrics in the sub-sections below have a network The metrics in the sub-sections below have a network
characterization orientation, but also have relevance to receiver characterization orientation, but also have relevance to receiver
design where reordering compensation is of interest. We begin with a design where reordering compensation is of interest. We begin with a
simple ratio metric indicating the reordered portion of the sample. simple ratio metric indicating the reordered portion of the sample.
4.1 Reordered Packet Ratio 4.1 Reordered Packet Ratio
4.1.1 Metric Name: 4.1.1 Metric Name
Type-P-Reordered-Ratio-Stream Type-P-Reordered-Ratio-Stream
4.1.2 Metric Parameters: 4.1.2 Metric Parameters
The parameter set includes Type-P-Reordered singleton parameters, The parameter set includes Type-P-Reordered singleton parameters,
the parameters unique to Poisson Streams (as in RFC 2330 [RFC2330], the parameters unique to Poisson Streams (as in [RFC2330], Periodic
Periodic Streams (as in RFC 3432 [RFC3432]), or TCP-like Streams (as Streams (as in [RFC3432]), or TCP-like Streams (as in [RFC3148]),
in RFC 3148 [RFC3148]), packet size or size patterns, and the packet size or size patterns, and the following:
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 + K, the total number of packets in the stream sent from Source to
Destination Destination
+ L, the total number of packets received (arriving between T0 and + L, the total number of packets received (arriving between T0 and
Tf+dT) out of the K packets sent. Recall that identical copies Tf+dT) out of the K packets sent. Recall that identical copies
(duplicates) have been removed, so L <= K. (duplicates) have been removed, so L <= K.
4.1.3 Definition: 4.1.3 Definition
Given a stream of packets sent from a Source to a Destination, the Given a stream of packets sent from a Source to a Destination, the
ratio of reordered packets in the sample is ratio of reordered packets in the sample is
(Count of packets with Type-P-Reordered=TRUE) / ( L ) (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
skipping to change at line 529 skipping to change at line 528
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 Notation and Metric Parameters: 4.2.2 Notation and Metric Parameters
Recall that K is the number of packets in the stream at the Source Recall that K is the number of packets in the stream at the Source
and L is the number of packets received at the Destination. and L is the number of packets received at the Destination.
Each packet has been assigned a sequence number, s, a consecutive Each packet has been assigned a sequence number, s, a consecutive
integer from 1 to K in the order of packet transmission (at the integer from 1 to K in the order of packet transmission (at the
source). 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.
skipping to change at line 565 skipping to change at line 564
+ i, the index for arrival position, where i-1 represents an + i, the index for arrival position, where i-1 represents an
arrival earlier than i. arrival earlier than i.
+ j, a set of one or more arrival indexes, where 1 <= j < i. + j, a set of one or more arrival indexes, where 1 <= j < i.
+ s[i], the original sequence numbers, s, in order of arrival. + s[i], the original sequence numbers, s, in order of arrival.
+ e, the Reordering Extent, defined below. + e, the Reordering Extent, defined below.
4.2.3 Definition: 4.2.3 Definition
The reordering extent, e, of packet s[i] is defined to be i-j for The reordering extent, e, of packet s[i] is defined to be i-j for
the smallest value of j where s[j] > s[i]. the smallest value of j where s[j] > s[i].
Informally, the reordering extent is the maximum distance, in Informally, the reordering extent is the maximum distance, in
packets, from a reordered packet to the earliest packet received packets, from a reordered packet to the earliest packet received
that has a larger sequence number. If a packet is in-order, its that has a larger sequence number. If a packet is in-order, its
reordering extent is undefined. The first packet to arrive is in- reordering extent is undefined. The first packet to arrive is in-
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 (see the Byte Offset metric). With could pass on to the upper layers (see the Byte Offset metric). With
the bias understood, this definition is deemed sufficient, the bias understood, this definition is deemed sufficient,
especially for those who demand "on the fly" calculations. especially for those who demand "on 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 s at 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.
If a receiver intends to restore order, then its buffer capacity If a receiver intends to restore order, then its buffer capacity
skipping to change at line 621 skipping to change at line 620
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
lateness in terms of buffer time that a receiver must possess to lateness in terms of buffer time that a receiver must possess to
accommodate them. Offset metrics are calculated only on reordered accommodate them. Offset metrics are calculated only on reordered
packets, as identified by the reordered packet singleton metric in packets, as identified by the reordered packet singleton metric in
Section 3. Section 3.
4.3.1 Metric Name: 4.3.1 Metric Name
Type-P-packet-Late-Time-Stream Type-P-Packet-Late-Time-Stream
4.3.2 Metric Parameters: 4.3.2 Metric Parameters
In addition to the parameters defined for Type-P-Reordered-Ratio- In addition to the parameters defined for Type-P-Reordered-Ratio-
Stream, we specify: Stream, we specify:
+ DstTime, the time that each packet in the stream arrives at the + DstTime, the time that each packet in the stream arrives at the
destination, and may be associated with index i, or packet s[i] destination, and may be associated with index i, or packet s[i]
+ LateTime(s[i]), the offset of packet s[i] in time, defined below + LateTime(s[i]), the offset of packet s[i] in 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 s[i] is reordered, and has a reordering extent e, received packet s[i] is reordered, and has a reordering extent e,
then: then:
LateTime(s[i]) = DstTime(i)-DstTime(i-e) LateTime(s[i]) = DstTime(i)-DstTime(i-e)
Alternatively, using similar notation to that of section 4.2, an Alternatively, using similar notation to that of section 4.2, an
equivalent definition is: equivalent definition is:
skipping to change at line 697 skipping to change at line 696
buffer time vs. percent of reordered packets accommodated may be buffer time vs. percent of reordered packets accommodated may be
informative. informative.
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.
Offset metrics are calculated only on reordered packets, as Offset metrics are calculated only on reordered packets, as
identified by the reordered packet singleton metric in Section 3. 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, including the optional We use the same parameters defined earlier, including the optional
parameters of SrcByte and PayloadSize, and define: parameters of SrcByte and PayloadSize, and define:
+ ByteOffset(s[i]), the offset of packet s[i] in bytes + ByteOffset(s[i]), the offset of packet s[i] in bytes
4.4.3 Definition: 4.4.3 Definition
The Byte stream offset for reordered packet s[i] is the sum of the The Byte stream offset for reordered packet s[i] is the sum of the
payload sizes of packets qualified by the following criteria: payload sizes of packets qualified by the following criteria:
* Arrival prior to the reordered packet, s[i], and * Arrival prior to the reordered packet, s[i], and
* The send sequence number, s, is greater than s[i]. * The send sequence number, s, is greater than s[i].
Packets that meet both these criteria are normally buffered until Packets that meet both these criteria are normally buffered until
the sequence beneath them is complete. Note that these criteria the sequence beneath them is complete. Note that these criteria
apply to both in-order and reordered packets. apply to both in-order and reordered packets.
For reordered packet s[i] with a reordering extent e: For reordered packet s[i] with a reordering extent e:
ByteOffset(s[i]) = Sum[qualified packets] ByteOffset(s[i]) = Sum[qualified packets]
= Sum[PayloadSize(packet at i-1 if qualified), = Sum[PayloadSize(packet at i-1 if qualified),
PayloadSize(packet at i-2 if qualified), ... PayloadSize(packet at i-2 if qualified), ...
skipping to change at line 732 skipping to change at line 732
= Sum[PayloadSize(packet at i-1 if qualified), = Sum[PayloadSize(packet at i-1 if qualified),
PayloadSize(packet at i-2 if qualified), ... PayloadSize(packet at i-2 if qualified), ...
PayloadSize(packet at i-e always qualified)] PayloadSize(packet at i-e always qualified)]
Using our earlier notation: Using our earlier notation:
ByteOffset(s[i]) = ByteOffset(s[i]) =
Sum[payloads of s[j] where s[j]>s[i] and i > j >= i-e] Sum[payloads of s[j] where s[j]>s[i] and i > j >= i-e]
4.4.4 Discussion 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
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. In packets and their size, especially when packet size is variable. In
these and other circumstances, it may be most useful to characterize these and other circumstances, it may be most useful to characterize
offset in terms of the payload size(s) of stored packets, using the offset in terms of the payload size(s) of stored packets, using the
Type-P-packet-Byte-Offset-Stream metric. 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.
A sample's ByteOffset results may be expressed as a histogram, to A sample's ByteOffset results may be expressed as a histogram, to
summarize the frequency of buffer lengths needed to accommodate summarize the frequency of buffer lengths needed to accommodate
reordered packets and permit buffer tuning on that basis. A CDF with reordered packets and permit buffer tuning on that basis. A CDF with
buffer size vs. percent of reordered packets accommodated may be buffer size vs. percent of reordered packets accommodated may be
informative. informative.
4.5 Gaps between multiple Reordering Discontinuities 4.5 Gaps between multiple Reordering Discontinuities
4.5.1 Metric Name: 4.5.1 Metric 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, but add the convention We use the same parameters defined earlier, but add the convention
that index i' is greater than i, likewise j' > j, and define: that index i' is greater than i, likewise j' > j, and define:
+ Gap(s[j']), the Reordering Gap of packet s[j'] in units of + Gap(s[j']), the Reordering Gap of packet s[j'] in units of
integer messages integer messages
+ GapTime(s[j']), the Reordering Gap of packet s[j'] in units of + GapTime(s[j']), the Reordering Gap of packet s[j'] in units of
time 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 fact is used in the definition of the Reordering Gap, below. This fact is used in the definition of the Reordering Gap, below.
4.5.4 Definition of Reordering Gap: 4.5.4 Definition of Reordering Gap
A reordering gap is the distance between successive reordering A reordering gap is the distance between successive reordering
discontinuities. Type-P-packet-Reordering-Gap-Stream assigns a value discontinuities. Type-P-packet-Reordering-Gap-Stream assigns a value
to (all) packets in a stream. to (all) packets in a stream.
If: If:
The packet s[j'] is found to be a reordering discontinuity, based The packet s[j'] is found to be a reordering discontinuity, based
on the arrival of reordered packet s[i'] with extent e', and on the arrival of reordered packet s[i'] with extent e', and
skipping to change at line 834 skipping to change at line 836
to receiver designers, revealing the period of reordering to receiver designers, revealing the period of reordering
discontinuities. The combination of reordering gaps and extent discontinuities. The combination of reordering gaps and extent
reveals whether receivers will be required to handle cases of reveals whether receivers will be required to handle cases of
overlapping reordered packets. overlapping reordered packets.
4.6 Reordering-free Runs 4.6 Reordering-free Runs
This section defines a metric based on a count of consecutive in- This section defines a metric based on a count of consecutive in-
order packets between reordered packets. order packets between reordered packets.
4.6.1 Metric Name: 4.6.1 Metric 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, and define the We use the same parameters defined earlier, and define the
following: following:
+ r, the run counter + r, the run counter
+ x, the number of runs, also the number of reordered packets + x, the number of runs, also the number of reordered packets
+ a, the accumulator of in-order packets + a, the accumulator of in-order packets
+ p, the number of packets (when the stream is complete, p=(x+a)=L) + p, the number of packets (when the stream is complete, p=(x+a)=L)
+ q, the sum of the squares of the runs counted + 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 in- As packets in a sample arrive at the Destination, the count of in-
order packets between reordered packets is a Reordering-Free run. order packets between reordered packets is a Reordering-Free run.
Note that the minimum run-length is zero according to this Note that the minimum run-length is zero according to this
definition. A pseudo code example follows: definition. A pseudo code example follows:
r = 0; /* r is the run counter */ r = 0; /* r is the run counter */
x = 0; /* x 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 sum of the squares of the runs counted */ 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 = 0; r = 0;
x++; 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 sum of the squared lengths. after adding it to the sum of the squared lengths.
Each arrival of a reordered packet yields a new run count. Long Each arrival of a reordered packet yields a new run count. Long
runs accompany periods where order was maintained, while short runs runs accompany periods where order was maintained, 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/x 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/x ((q/a)/(a/x)) Free runs from the average by comparing q/a to a/x ((q/a)/(a/x))
4.6.4 Discussion and Illustration: 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 36 packets with 3 runs of 11 in-order packets we have: For 36 packets with 3 runs of 11 in-order packets we have:
p = 36 p = 36
x = 3 x = 3
skipping to change at line 927 skipping to change at line 929
(q/a)/(a/x) = 2.65 (q/a)/(a/x) = 2.65
The variability in run length is prominent in the difference between The variability in run length is prominent in the difference between
the q values (sum of the squared run lengths) and comparing average 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 run length to the (q/a)/(a/x) ratios (equals 1 when all runs are the
same length). 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 effect 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. [RFC3148] lists the
the specific aspects of congestion control algorithms that must be 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 estimate whether reordering might cause the DUP-ACK threshold to to estimate whether reordering might cause the DUP-ACK threshold to
be exceeded causing the Fast Retransmit algorithm to be invoked. be exceeded causing the Fast Retransmit algorithm to be invoked.
Additional TCP Kernel Instruments are 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
received out of the k packets sent. (Note that there is no received out of the k packets sent. (Note that there is no
relationship between k and l: on one hand, losses can make l less relationship between k and l: on one hand, losses can make l less
than k; on the other hand, duplicates can make l greater than k.) than k; on the other hand, duplicates can make l greater than k.)
Assign each sent packet a sequence number, 1 to k, in order of Assign each sent packet a sequence number, 1 to k, in order of
packet emission. packet emission.
skipping to change at line 988 skipping to change at line 990
Definition 2: The degree of n-reordering of the sample is m/l, where Definition 2: The degree of n-reordering of the sample is m/l, where
m is the number of n-reordered packets in the sample. m is the number of n-reordered packets in the sample.
Definition 3: The degree of "monotonic reordering" of the sample is Definition 3: The degree of "monotonic reordering" of the sample is
its degree of 1-reordering. its degree of 1-reordering.
Definition 4: A sample is said to have no reordering if its degree Definition 4: A sample is said to have no reordering if its degree
of n-reordering is 0. of n-reordering is 0.
5.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.
The n-reordering metric is helpful for matching the duplicate ACK The n-reordering metric is helpful for matching the duplicate ACK
threshold setting to a given path. For example, if a path exhibits threshold setting to a given path. For example, if a path exhibits
no more than 5-reordering, a DUP-ACK threshold of 6 may avoid no more than 5-reordering, a DUP-ACK threshold of 6 may avoid
unnecessary retransmissions. 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, see [RFC2581]). 3 is default threshold halve its congestion window, see [RFC2581]). Three is default
for SCTP [RFC2960], and the future Datagram Congestion Control threshold for Stream Control Transport Protocol (SCTP) [RFC2960],
Protocol (DCCP). and the Datagram Congestion Control Protocol (DCCP) [RFC4340] when
used with Congestion Control ID 2: TCP-like Congestion Control
[RFC4341].
A sample's n-reordering may be expressed as a histogram, to 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. Both time and position influence the sender's behavior. singletons. 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
skipping to change at line 1086 skipping to change at line 1090
remain valid and useful when a stream of packets experiences packet remain valid and useful when a stream of packets experiences packet
loss, or both loss and reordering. In other words, losses alone do loss, or both loss and reordering. In other words, losses alone do
not cause subsequent packets to be declared reordered. not cause subsequent packets to be declared reordered.
Assuming that the necessary sequence information (message number) is Assuming that the necessary sequence information (message number) is
included in the packet payload (possibly in application headers such included in the packet payload (possibly in application headers such
as RTP), reordering metrics may be evaluated in a passive as RTP), reordering metrics may be evaluated in a passive
measurement arrangement. Also, it is possible to evaluate order at measurement arrangement. Also, it is possible to evaluate order at
any point along a Source-Destination path, recognizing that any point along a Source-Destination path, recognizing that
intermediate measurements may differ from those made at the intermediate measurements may differ from those made at the
Destination (where the reordering affect on applications can be Destination (where the reordering effect on applications can be
inferred). 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 s or SrcTime helps to avoid this additional sequence reference of s or SrcTime helps to avoid this
ambiguity, or the optional TCP timestamp field [RFC1323]. ambiguity, or the optional TCP timestamp field [RFC1323].
skipping to change at line 1133 skipping to change at line 1137
Ideally, the test instrument would have the ability to use all Ideally, the test instrument would have the ability to use all
earlier packets at any point in the test stream. In practice there earlier packets at any point in the test stream. In practice there
will be limited ability to determine reordering extent, due to the will be limited ability to determine reordering extent, due to the
storage requirements for previous packets. Saving only packets that storage requirements for previous packets. Saving only packets that
indicate discontinuities (and their arrival positions) will reduce indicate discontinuities (and their arrival positions) will reduce
storage volume. storage volume.
Another solution is to use a sliding history window of packets, Another solution is to use a sliding history window of packets,
where the window size would be determined by an upper bound on the where the window size would be determined by an upper bound on the
useful reordering extent. This bound could be several packets or useful reordering extent. This bound could be several packets or
several seconds-worth of packets, depending on the intended several seconds worth of packets, depending on the intended
analysis. When discarding all stream information beyond the window, analysis. When discarding all stream information beyond the window,
the reordering extent or degree of n-reordering may need to be the reordering extent or degree of n-reordering may need to be
expressed as greater than the window length if the reordering expressed as greater than the window length if the reordering
discontinuity information has been discarded, and Gap calculations discontinuity information has been discarded, and Gap calculations
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).
It is important to note that practical IP networks also have limited It is important to note that practical IP networks also have limited
ability to "store" packets, even when routing loops appear ability to "store" packets, even when routing loops appear
temporarily. Therefore, the storage for reordering metrics (and temporarily. Therefore, the maximum storage for reordering metrics
their complexity) would only approach the number packets in the (and their complexity) would only approach the number packets in the
sample, K, when the sending time for K packets is small with respect sample, K, when the sending time for K packets is small with respect
to the network's largest possible transfer time. to the network's largest possible transfer time. Another possible
limitation on storage is the maximum length of the sequence number
field, assuming that most test streams do not exhaust this length in
practice.
Last, we note that determining reordering extents and gaps is tricky 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 quantifying reordering in all the comparison, and the value of quantifying reordering in all the
dimensions of time, bytes, and position. dimensions of time, bytes, and position.
Throughout this section, we will refer to packets by their source Throughout this section, we will refer to packets by their source
sequence number, except where noted. So "Packet 4" refers to the sequence number, except where noted. So "Packet 4" refers to the
packet with source sequence number 4, and the reader should refer to packet with source sequence number 4, and the reader should refer to
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. All packets contain PayloadSize=100 and message numbering is used. All packets contain PayloadSize=100
bytes, with SrcByte=(s x 100)-99 for s=1,2,3,4,... bytes, with SrcByte=(s x 100)-99 for s=1,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
skipping to change at line 1240 skipping to change at line 1247
Packet 4 may be useful. Note that 1-way delay and IPDV indicate Packet 4 may be useful. Note that 1-way delay and IPDV indicate
unusual behavior for Packet 4. Also, if Packet 4 had arrived at unusual behavior for Packet 4. Also, if Packet 4 had arrived at
least 62ms earlier, it would have been in-order in this example. least 62ms earlier, it would have been in-order in this example.
If all packets contained 100 byte payloads, then Byte Offset is If all packets contained 100 byte payloads, then Byte Offset is
equal to 400 bytes. equal to 400 bytes.
Following the definitions of section 5.1, Packet 4 is designated 4- Following the definitions of section 5.1, Packet 4 is designated 4-
reordered. reordered.
7.2 Example with two packets reordered 7.2 Example with Two Packets Reordered
Table 2 Example with Packets 5 and 6 Reordered, Table 2 Example with Packets 5 and 6 Reordered,
Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10
s Src Dst Dst Byte Late s Src Dst Dst Byte Late
@Dst NextExp Time Time Delay IPDV Order Offset Time @Dst NextExp Time Time Delay IPDV Order Offset Time
1 1 0 68 68 1 1 1 0 68 68 1
2 2 20 88 68 0 2 2 2 20 88 68 0 2
3 3 40 108 68 0 3 3 3 40 108 68 0 3
4 4 60 128 68 0 4 4 4 60 128 68 0 4
7 5 120 188 68 -22 5 7 5 120 188 68 -22 5
skipping to change at line 1298 skipping to change at line 1305
Following the definitions of section 5, Packet 5 is designated 1- Following the definitions of section 5, Packet 5 is designated 1-
reordered, but Packet 6 is not designated n-reordered. reordered, but Packet 6 is not designated n-reordered.
A hypothetical sender/receiver pair may retransmit Packet 5 A hypothetical sender/receiver pair may retransmit Packet 5
unnecessarily, since it is 1-reordered (in agreement with the unnecessarily, since it is 1-reordered (in agreement with the
singleton metric). Though Packet 6 may not be unnecessarily singleton metric). Though Packet 6 may not be unnecessarily
retransmitted, the receiver cannot advance Packet 7 to the higher retransmitted, the receiver cannot advance Packet 7 to the higher
layers until after Packet 6 arrives. Therefore, the singleton metric layers until after Packet 6 arrives. Therefore, the singleton metric
correctly determined that Packet 6 is reordered. correctly determined that Packet 6 is reordered.
7.3 Example with three packets reordered 7.3 Example with Three Packets Reordered
Table 3 Example with Packets 4, 5, and 6 reordered Table 3 Example with Packets 4, 5, and 6 reordered
Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11
s Src Dst Dst Byte Late s Src Dst Dst Byte Late
@Dst NextExp Time Time Delay IPDV Order Offset Time @Dst NextExp Time Time Delay IPDV Order Offset Time
1 1 0 68 68 1 1 1 0 68 68 1
2 2 20 88 68 0 2 2 2 20 88 68 0 2
3 3 40 108 68 0 3 3 3 40 108 68 0 3
7 4 120 188 68 -88 4 7 4 120 188 68 -88 4
8 8 140 208 68 0 5 8 8 140 208 68 0 5
skipping to change at line 1406 skipping to change at line 1413
destination and/or the intervening network(s). destination and/or the intervening network(s).
Administrators of source, destination, and the intervening Administrators of source, destination, and the intervening
network(s) should establish bilateral or multi-lateral agreements network(s) should establish bilateral or multi-lateral agreements
regarding the timing, size, and frequency of collection of sample regarding the timing, size, and frequency of collection of sample
metrics. Use of this method in excess of the terms agreed between metrics. Use of this method in excess of the terms agreed between
the participants may be cause for immediate rejection or discard of the participants may be cause for immediate rejection or discard of
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. In most cases, a keep this information safe and confidential. In most cases, a
hashing function will produce a value suitable for payload hashing function will produce a value suitable for payload
comparisons. 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
of the sample measurement. of the sample measurement.
To discourage the kind of interference mentioned above, packet To discourage the kind of interference mentioned above, packet
interference checks, such as cryptographic hash, may be used. interference checks, such as cryptographic hash, may be used.
9. IANA Considerations 9. IANA Considerations
Since this metric does not define a protocol or well-known values, Metrics defined in this memo SHOULD be registered in the IANA IPPM
there are no IANA considerations in this memo. METRICS REGISTRY as described in initial version of the registry
[RFC4148].
IANA is asked to register the following metrics in the IANA-IPPM-
METRICS-REGISTRY-MIB (where RFC xxxx is replaced with the number of
this memo):
ietfReorderedSingleton OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Reordered"
REFERENCE
"Reference RFC xxxx, section 3"
::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfReorderedPacketRatio OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Reordered-Ratio-Stream"
REFERENCE
"Reference RFC xxxx, section 4.1"
::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfReorderingExtent OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Extent-Stream"
REFERENCE
"Reference RFC xxxx, section 4.2"
::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfReorderingLateTimeOffset OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Late-Time-Stream"
REFERENCE
"Reference RFC xxxx, section 4.3"
::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfReorderingByteOffset OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Byte-Offset-Stream"
REFERENCE
"Reference RFC xxxx, section 4.4"
::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfReorderingGap OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Gap-Stream"
REFERENCE
"Reference RFC xxxx, section 4.5"
::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfReorderingFreeRun OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-Reordering-Free-Run-Stream"
REFERENCE
"Reference RFC xxxx, section 4.6"
::= { ianaIppmMetrics nn } -- IANA assigns nn
ietfnReordering OBJECT-IDENTITY
STATUS current
DESCRIPTION
"Type-P-Packet-n-Reordering-Stream"
REFERENCE
"Reference RFC xxxx, section 5"
::= { ianaIppmMetrics nn } -- IANA assigns nn
10. Normative References 10. Normative References
[RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791, [RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791,
September 1981. September 1981.
Obtain via: http://www.rfc-editor.org/rfc/rfc791.txt Obtain via: http://www.rfc-editor.org/rfc/rfc791.txt
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119, March 1997. Requirement Levels", RFC 2119, March 1997.
Obtain via: http://www.rfc-editor.org/rfc/rfc2119.txt Obtain via: http://www.rfc-editor.org/rfc/rfc2119.txt
skipping to change at line 1450 skipping to change at line 1526
Obtain via: http://www.rfc-editor.org/rfc/rfc791.txt Obtain via: http://www.rfc-editor.org/rfc/rfc791.txt
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119, March 1997. Requirement Levels", RFC 2119, March 1997.
Obtain via: http://www.rfc-editor.org/rfc/rfc2119.txt Obtain via: http://www.rfc-editor.org/rfc/rfc2119.txt
[RFC2330] Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., [RFC2330] Paxson, V., Almes, G., Mahdavi, J., and Mathis, M.,
"Framework for IP Performance Metrics", RFC 2330, May "Framework for IP Performance Metrics", RFC 2330, May
1998. 1998.
Obtain via: http://www.rfc-editor.org/rfc/rfc2330.txt Obtain via: http://www.rfc-editor.org/rfc/rfc2330.txt
[RFC3148] Mathis, M. and Allman, M., "A Framework for Defining [RFC3148] Mathis, M. and Allman, M., "A Framework for Defining
Empirical Bulk Transfer Capacity Metrics", RFC 3148, July Empirical Bulk Transfer Capacity Metrics", RFC 3148, July
2001. 2001.
Obtain via: http://www.rfc-editor.org/rfc/rfc3148.txt Obtain via: http://www.rfc-editor.org/rfc/rfc3148.txt
[RFC3432] Raisanen, V., Grotefeld, G., and Morton, A., "Network [RFC3432] Raisanen, V., Grotefeld, G., and Morton, A., "Network
performance measurement with periodic streams", RFC 3432, performance measurement with periodic streams", RFC 3432,
November 2002. November 2002.
Obtain via: http://www.rfc-editor.org/rfc/rfc3432.txt
[RFC4148] Stephan, E., "IP Performance Metrics (IPPM) Metrics
Registry", RFC 4148, August 2005.
Obtain via: http://www.rfc-editor.org/rfc/rfc4148.txt
11. Informative References 11. Informative References
[Bel02] J.Bellardo and S.Savage, "Measuring Packet Reordering," [Bel02] J.Bellardo and S.Savage, "Measuring Packet Reordering,"
Proceedings of the ACM SIGCOMM Internet Measurement Proceedings of the ACM SIGCOMM Internet Measurement
Workshop 2002, November 6-8, Marseille, France. Workshop 2002, November 6-8, Marseille, France.
[Ben99] J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet [Ben99] J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet
Reordering is Not Pathological Network Behavior," Reordering is Not Pathological Network Behavior,"
IEEE/ACM Transactions on Networking, vol.7, no.6, pp.789- IEEE/ACM Transactions on Networking, vol.7, no.6, pp.789-
skipping to change at line 1518 skipping to change at line 1600
[RFC2581] Allman, M., Paxson, V., and Stevens, W., "TCP Congestion [RFC2581] Allman, M., Paxson, V., and Stevens, W., "TCP Congestion
Control", RFC 2581, April 1999. Control", RFC 2581, April 1999.
[RFC2960] Stewart, R., et al., "Stream Control Transmission [RFC2960] Stewart, R., et al., "Stream Control Transmission
Protocol", RFC 2960, October 2000. Protocol", RFC 2960, October 2000.
[RFC3393] Demichelis, C., and Chimento, P., "IP Packet Delay [RFC3393] Demichelis, C., and Chimento, P., "IP Packet Delay
Variation Metric for IP Performance Metrics (IPPM)", RFC Variation Metric for IP Performance Metrics (IPPM)", RFC
3393, November 2002. 3393, November 2002.
[RFC4340] Kohler, E., Handley, M. and Floyd, S., "Datagram
Congestion Control Protocol (DCCP)", RFC 4340, March
2006.
[RFC4341] Floyd, S. and Kohler, E., "Profile for Datagram
Congestion Control Protocol (DCCP) Congestion Control ID
2: TCP-like Congestion Control", RFC 4341, March 2006.
[TBABAJ02] T. Banka, A. A. Bare, A. P. Jayasumana, "Metrics for [TBABAJ02] T. Banka, A. A. Bare, A. P. Jayasumana, "Metrics for
Degree of Reordering in Packet Sequences", Proc. 27th Degree of Reordering in Packet Sequences", Proc. 27th
IEEE Conference on Local Computer Networks, Tampa, FL, IEEE Conference on Local Computer Networks, Tampa, FL,
Nov. 2002. Nov. 2002.
[Y.1540] ITU-T Recommendation Y.1540, "Internet protocol data [Y.1540] ITU-T Recommendation Y.1540, "Internet protocol data
communication service - IP packet transfer and communication service - IP packet transfer and
availability performance parameters", December 2002. availability performance parameters", December 2002.
12. Acknowledgments 12. Acknowledgments
skipping to change at line 1672 skipping to change at line 1763
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
evaluation, but that similar procedures could be applied prior to evaluation, but that similar procedures could be applied prior to
re-assembly. This appendix gives definitions and procedures to re-assembly. This appendix gives definitions and procedures to
identify reordering in a packet stream that includes fragmentation. identify reordering in a packet stream that includes fragmentation.
14.1 Metric Name: 14.1 Metric Name
The Metric retains the same name, Type-P-Reordered, but additional The Metric retains the same name, Type-P-Reordered, but additional
parameters are required. parameters are required.
This Appendix assumes that the device that divides a packet into This Appendix assumes that the device that divides a packet into
fragments send them according to ascending fragment offset. Early fragments send them according to ascending fragment offset. Early
Linux OS sent fragments in reverse order, so this possibility is Linux OS sent fragments in reverse order, so this possibility is
worth checking. worth checking.
14.2 Additional Metric Parameters: 14.2 Additional Metric Parameters
+ MoreFrag, the state of the More Fragments Flag in the IP header + MoreFrag, the state of the More Fragments Flag in the IP header
+ FragOffset, the offset from the beginning of a fragmented packet, + FragOffset, the offset from the beginning of a fragmented packet,
in 8 octet units (also from the IP header). in 8 octet units (also from the IP header).
+ FragSeq#, the sequence number from the IP header of a fragmented + FragSeq#, the sequence number from the IP header of a fragmented
packet currently under evaluation for reordering. When set to packet currently under evaluation for reordering. When set to
zero, fragment evaluation is not in progress. zero, fragment evaluation is not in progress.
skipping to change at line 1706 skipping to change at line 1797
The packet sequence number, s, is assumed to be the same as the IP The packet sequence number, s, is assumed to be the same as the IP
header sequence number. Also, the value of NextExp does not change header sequence number. Also, the value of NextExp does not change
with the in-order arrival of fragments. NextExp is only updated when with the in-order arrival of fragments. NextExp is only updated when
a last fragment or a complete packet arrives. a last fragment or a complete packet arrives.
Note that packets with missing fragments MUST be declared lost, and Note that packets with missing fragments MUST be declared lost, and
the Reordering status of any fragments that do arrive MUST be the Reordering status of any fragments that do arrive MUST be
excluded from sample metrics. excluded from sample metrics.
14.3 Definition: 14.3 Definition
The value of Type-P-Reordered is typically false (the packet is in- The value of Type-P-Reordered is typically false (the packet is in-
order) when order) when
* the sequence number s >= NextExp, * the sequence number s >= NextExp,
* AND the fragment offset FragOffset >= NextExpFrag * AND the fragment offset FragOffset >= NextExpFrag
However, it more efficient to define reordered conditions exactly, However, it more efficient to define reordered conditions exactly,
and designate Type-P-Reordered as False otherwise. and designate Type-P-Reordered as False otherwise.
skipping to change at line 1773 skipping to change at line 1863
} }
if (s>=NextExp AND MoreFrag==1 AND s < FragSeq#){ if (s>=NextExp AND MoreFrag==1 AND s < FragSeq#){
/* case where a late fragment arrived, /* case where a late fragment arrived,
for illustration only, redundant with else below */ for illustration only, redundant with else below */
Reordering = True; Reordering = True;
} }
else { /* when s < NextExp, or MoreFrag==0 AND s < FragSeq# */ else { /* when s < NextExp, or MoreFrag==0 AND s < FragSeq# */
Reordering = True; Reordering = True;
} }
} }
A working version of the code would include a check to ensure that A working version of the code would include a check to ensure that
all fragments of a packet arrive before using the Reordered status all fragments of a packet arrive before using the Reordered status
further, such as in sample metrics. further, such as in sample metrics.
14.4 Discussion: Notes on Sample Metrics when evaluating Fragments 14.4 Discussion: Notes on Sample Metrics when Evaluating Fragments
All fragments with the same Source Sequence Number are assigned the All fragments with the same Source Sequence Number are assigned the
same Source Time. same Source Time.
Evaluation with byte stream numbering may be simplified if the Evaluation with byte stream numbering may be simplified if the
fragment offset is simply added to the SourceByte of the first fragment offset is simply added to the SourceByte of the first
packet (with fragment offset = 0), keeping the 8 octet units of the packet (with fragment offset = 0), keeping the 8 octet units of the
offset in mind. offset in mind.
15. Author's Addresses 15. Author's Addresses
skipping to change at line 1822 skipping to change at line 1911
EMail: <gomathi@att.com> EMail: <gomathi@att.com>
Stanislav Shalunov Stanislav Shalunov
Internet2 Internet2
1000 Oakbrook DR STE 300 1000 Oakbrook DR STE 300
Ann Arbor, MI 48104 Ann Arbor, MI 48104
+1 734 995 7060 +1 734 995 7060
EMail: <shalunov@internet2.edu> EMail: <shalunov@internet2.edu>
Jerry Perser Jerry Perser
Consultant Veriwave
Calabasas, CA 91302 USA USA
Phone: + 1 Phone:
EMail: <jerry@perser.org>
EMail: <jperser@veriwave.com>
Full Copyright Statement Full Copyright Statement
Copyright (C) The Internet Society (2005). Copyright (C) The Internet Society (2006).
This document is subject to the rights, licenses and restrictions This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors contained in BCP 78, and except as set forth therein, the authors
retain all their rights. 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
 End of changes. 94 change blocks. 
167 lines changed or deleted 256 lines changed or added

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