draft-ietf-ippm-reordering-02.txt   draft-ietf-ippm-reordering-03.txt 
Network Working Group A.Morton Network Working Group A.Morton
Internet Draft L.Ciavattone Internet Draft L.Ciavattone
Document: <draft-ietf-ippm-reordering-02.txt> G.Ramachandran Document: <draft-ietf-ippm-reordering-03.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
Spirent Spirent
Packet Reordering Metric for IPPM Packet Reordering Metric for IPPM
Status of this Memo Status of this Memo
skipping to change at line 36 skipping to change at line 36
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.
Abstract Abstract
This memo defines a simple metric to determine if a network has This memo defines a simple metric to determine if a network has
maintained packet order. It provides motivations for the new metric, maintained packet order. It provides motivations for the new metric,
suggests a metric definition, and discusses the issues associated gives the metric definition, and discusses the issues associated
with measurement. The memo includes sample metrics to quantify the with its measurement. The memo defines additional sample metrics to
extent of reordering in several useful dimensions. Some examples of quantify the extent of reordering in several useful dimensions. Some
evaluation using the various sample metrics are included. examples of evaluation using the various sample metrics are
included.
1. Conventions used in this document 1. Conventions used in this document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [2]. document are to be interpreted as described in RFC 2119 [2].
Although RFC 2119 was written with protocols in mind, the key words Although RFC 2119 was written with protocols in mind, the key words
are used in this document for similar reasons. They are used to are used in this document for similar reasons. They are used to
ensure the results of measurements from two different ensure the results of measurements from two different
implementations are comparable, and to note instances when an implementations are comparable, and to note instances when an
skipping to change at line 76 skipping to change at line 77
packets with sequence numbers smaller than their predecessors as packets with sequence numbers smaller than their predecessors as
out-of-order, or reordered. For example, if arriving packets are out-of-order, or reordered. For example, if arriving packets are
numbered 1,2,4,5,3, then packet 3 is reordered. This is equivalent numbered 1,2,4,5,3, then packet 3 is reordered. This is equivalent
to Paxon's reordering definition in [4], where "late" packets were to Paxon's reordering definition in [4], where "late" packets were
declared reordered. The alternative is to emphasize "premature" declared reordered. The alternative is to emphasize "premature"
packets instead (4 and 5 in the example), but only the arrival of packets instead (4 and 5 in the example), but only the arrival of
packet 3 distinguishes this circumstance from packet loss. Focusing packet 3 distinguishes this circumstance from packet loss. Focusing
attention on late packets allows us to maintain orthogonality with attention on late packets allows us to maintain orthogonality with
the packet loss metric. The metric's construction is very similar to the packet loss metric. The metric's construction is very similar to
the sequence space validation for received segments in RFC793 [5]. the sequence space validation for received segments in RFC793 [5].
Earlier work to define ordered delivery includes [6], [7], [8 and Earlier work to define ordered delivery includes [6], [7], [8], [9],
more ???. [10] and more ???.
2.1 Motivation 2.1 Motivation
A reordering metric is relevant for most applications, especially A reordering metric is relevant for most applications, especially
when assessing network support for Real-Time media streams. The when assessing network support for Real-Time media streams. The
extent of reordering may be sufficient to cause a received packet to extent of reordering may be sufficient to cause a received packet to
be discarded by functions above the IP layer. be discarded by functions above the IP layer.
Packet order is not expected to change during transfer, but several Packet order is not expected to change during transfer, but several
specific path characteristics can cause their order to change. specific path characteristics can cause their order to change.
skipping to change at line 136 skipping to change at line 137
Reordering Metrics SHOULD: Reordering Metrics SHOULD:
+ have concatenating results for segments measured separately + have concatenating results for segments measured separately
+ have simplicity for easy consumption and understanding + have simplicity for easy consumption and understanding
+ have relevance to TCP performance + have relevance to TCP performance
+ have relevance to Real-time application performance + have relevance to Real-time application performance
3. An Ordered Arrival Singleton Metric 3. An Ordered Arrival Singleton Metric
The IPPM framework RFC 2330 [3] gives the definitions of singletons, The IPPM framework RFC 2330 [3] describes the notions of singletons,
samples, and statistics. samples, and statistics. For easy reference:
By a 'singleton' metric, we refer to metrics that are,
in a sense, atomic. For example, a single instance of "bulk
throughput capacity" from one host to another might be defined
as a singleton metric, even though the instance involves
measuring the timing of a number of Internet packets.
The evaluation of packet order requires several supporting concepts. The evaluation of packet order requires several supporting concepts.
The first is a sequence number applied to packets at the source to The first is a sequence number applied to packets at the source to
uniquely identify the order of packet transmission. The sequence uniquely identify the order of packet transmission. The sequence
number may be established by a simple message number, a byte stream number may be established by a simple message number, a byte stream
number, or it may be the actual time when each packet departs from number, or it may be the actual time when each packet departs from
the Src. the Source.
The second supporting concept is a stored value which is the "next The second supporting concept is a stored value which is the "next
expected" packet number. Under normal conditions, the value of Next expected" packet number. Under normal conditions, the value of Next
Expected (NextExp) is the sequence number of the previous packet Expected (NextExp) is the sequence number of the previous packet
(plus 1 for message numbering). In byte stream numbering, NextExp (plus 1 for message numbering). In byte stream numbering, NextExp
is a value 1 byte greater than the last in-order packet sequence is a value 1 byte greater than the last in-order packet sequence
number + payload. If Src time is used as the sequence number, number + payload. If Source time is used as the sequence number,
NextExp is the Src time from the last in-order packet + 1 clock NextExp is the Src time from the last in-order packet + 1 clock
tick. tick.
Each packet within a packet stream can be evaluated for its order Each packet within a packet stream can be evaluated for its order
singleton metric. singleton metric.
3.1 Metric Name: 3.1 Metric Name:
Type-P-Non-Reversing-Order Type-P-Non-Reversing-Order
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 Src (or wire time) + SrcTime, the time of packet emission from the Source (or wire
time)
+ s, the packet sequence number applied at the Src, in units of + s, the packet sequence number applied at the Source, in units of
messages. messages.
+ SrcByte, the packet sequence number applied at the Src, in units + SrcByte, the packet sequence number applied at the Source, in
of payload bytes. units of payload bytes.
+ NextExp, the Next Expected Sequence number at the Dst, in units + NextExp, the Next Expected Sequence number at the Destination, in
of messages, time, or bytes. units of messages, time, or bytes.
+ PayloadSize, the number of bytes contained in the information + PayloadSize, the number of bytes contained in the information
field and referred to when the SrcByte sequence is based on byte field and referred to when the SrcByte sequence is based on byte
transfer. transfer.
3.3 Definition: 3.3 Definition:
In-order packets have sequence numbers (or Src times) greater than The Type-P-Non-Reversing-Order of a packet is defined as true if
or equal to the value of Next Expected. Each new in-order packet s >= NextExp (the packet is in-order). In this case, NextExp is set
will increase the Next Expected (typically by 1 for message to s+1.
numbering, or the payload size plus 1 for byte numbering). The Next
Expected value cannot decrease, thereby specifying non-reversing
order as the basis to identify reordered packets.
A reordered packet outcome occurs when a single IP packet at the Dst The Type-P-Non-Reversing-Order of a packet is defined as false if
Measurement Point results in the following: s < NextExp (the packet is reordered). In this case, NextExp value
The packet has a Src sequence number lower than the Next Expected does not change.
(NextExp), and therefore the packet is reordered. The Next Expected
value does not change on the arrival of this packet. Since the Next Expected value cannot decrease, it represents a non-
reversing order that is the basis to identify reordered packets.
For the alternate sequence dimensions, in-order packets have byte
stream numbers or Source times greater than or equal to the value of
Next Expected. Each new in-order packet will increase the Next
Expected by 1 clock tick for Source times, or the payload size plus
1 for byte numbering.
This definition can also be specified in pseudo-code. This definition can also be specified in pseudo-code.
On successful arrival of a packet with sequence number s: On successful arrival of a packet with sequence number s:
if s >= NextExp, /* s is in-order */ if s >= NextExp, /* s is true, in-order */
then then
NextExp = s + PayloadSize + 1; NextExp = s + PayloadSize + 1;
else /* when s < NextExp */ else /* when s < NextExp */
designate packet s as reordered; /* packet s is false, reordered */
The sequence number s may be replaced by SrcTime or SrcByte. When The sequence number s may be replaced by SrcTime or SrcByte. When
using s (message-based sequence numbering) or Src time, using s (message-based sequence numbering) or Source time,
PayloadSize=0. PayloadSize=0.
3.4 Discussion 3.4 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 if establishes the Next Expected value can be evaluated to determine
it is in-order, or reordered, based on a previous packet's arrival. whether it is in-order or reordered, based on a previous packet's
In the case where Next Expected is Undefined (because the arriving arrival. In the case where Next Expected is Undefined (because the
packet is the first successful transfer), the packet is designated arriving packet is the first successful transfer), the packet is
in-order. designated in-order.
This metric assumes re-assembly of packet fragments before
evaluation.
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 (additional copies would be declared considered for further analysis (copies would be declared reordered
reordered according to the definition above). This requirement has according to the definition above). This requirement has the same
the same storage requirements as earlier IPPM metrics, and follows storage requirements as earlier IPPM metrics, and follows the
the precedent of RFC 2679. precedent of RFC 2679.
Packets with s > NextExp are a special case of in-order delivery. Packets with s > NextExp are a special case of in-order delivery.
This condition indicates a sequence discontinuity, either because of This condition indicates a sequence discontinuity, either because of
packet loss or reordering. Reordered packets must arrive for the packet loss or reordering. Reordered packets must arrive for the
sequence discontinuity to be part of a reordering event (defined in sequence discontinuity to be defined as a reordering discontinuity
the next section). Discontinuities are easiest to detect with (see next section). Discontinuities are easiest to detect with
message numbering or payload byte numbering where payload size is message numbering or payload byte numbering where payload size is
constant, and may be possible with Periodic Streams and Src Time constant (and retransmissions are distinguished), and may be
numbering. possible with Periodic Streams and Source Time numbering.
4. Sample Metrics 4. Sample Metrics
In this section, we define metrics applicable to a sample of packets In this section, we define metrics applicable to a sample of packets
from a single Src sequence number system. We begin with a simple from a single Source sequence number system. We begin with a simple
ratio metric indicating the reordered portion of the sample. When ratio metric indicating the reordered portion of the sample. When
this ratio is zero, no further reordering metrics are needed for this ratio is zero, no further reordering metrics are needed for
that sample. that sample.
When reordering occurs, it is highly desirable to assert the degree When reordering occurs, it is highly desirable to assert the degree
to which a packet is out-of-order, or reordered with respect to a to which a packet is out-of-order, or reordered with respect to a
sample of packets. This section defines several metrics that sample of packets. This section defines several metrics that
quantify the extent of reordering in various units of measure. Each quantify the extent of reordering in various units of measure. Each
"extent" metric highlights a relevant application. "extent" metric highlights a relevant use.
The metrics in the sub-sections below have a network
characterization orientation, but also have relevance to receiver
design.
4.1 Reordered Packet Ratio 4.1 Reordered Packet Ratio
4.1.1 Metric Name: 4.1.1 Metric Name:
Type-P-Reordered-Ratio-Poisson/Periodic-Stream Type-P-Reordered-Ratio-Stream
4.1.2 Metric Parameters: 4.1.2 Metric Parameters:
The parameter set includes Type-P-Non-Reversing-Order singleton The parameter set includes Type-P-Non-Reversing-Order singleton
parameters, the parameters unique to Poisson or Periodic Streams, parameters, the parameters unique to Poisson or Periodic Streams (as
plus the following: in RFC 2330 and RFC3432), plus the following:
+ T0, a start time + T0, a start time
+ Tf, an end time + Tf, an end time
+ dT, a waiting time for each packet to arrive + dT, a waiting time for each packet to arrive
4.1.3 Definition: 4.1.3 Definition:
For the packets arriving successfully between T0 and Tf+dT, the For the packets arriving successfully between T0 and Tf+dT, the
ratio of reordered packets in the sample is ratio of reordered packets in the sample is
(Total of Reordered packets) / (Total packets received) (Total of Reordered packets) / (Total packets received)
This fraction may be expressed as a percentage (multiply by 100%). This fraction may be expressed as a percentage (multiply by 100%).
Note that in the case of duplicate packets, only the first copy is Note that in the case of duplicate packets, only the first copy is
used. used.
4.2 Reordering Events and their Extent 4.2 Reordering Extent
Note: This section is expected to evolve further as we integrate the
various metrics of reordering extent (n-reordering and other This section defines the extent to which packets are reordered, and
distance metrics used in earlier drafts). The co-authors are not yet associates a specific sequence discontinuity with each reordered
satisfied with all aspects of this section, and comments are packet.
welcome.
4.2.1 Metric Name: 4.2.1 Metric Name:
Type-P-packet-n-Reordering-Event-Poisson/Periodic-Stream Type-P-packet-Reordering-Extent-Stream
4.2.2 Parameter Notation: 4.2.2 Parameter Notation:
Let n be a positive integer (a parameter). Let k be a positive Given a stream of packets sent from a source to a destination, let K
integer (sample size, the number of packets sent). Let l be a non- be the total number of packets in that stream.
negative integer representing the number of packets that were
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
than k; on the other hand, duplicates can make l greater than k.)
Assign each sent packet a sequence number, 1 to k.
Let s[1], s[2], ..., s[l] be the original sequence numbers of the
received packets, in the order of arrival.
4.2.3 Definition 1:
Received packet number i (n < i <= l), with Src sequence number s
(s[i]), is reordered to the extent n if and only if for all j such
that i-n <= j < i we have s[j] > s[i].
Claim: If by this definition, the extent of a packet's reordering is
n and 0 < n' < n, then the packet is also reordered to the n'
extent.
Note: This definition is illustrated by C code in Appendix A. It
determines the presence of n-reordering events for a particular
value of n (when actually writing applications that would report the
metric, one would probably report it for several values of n, such
as 1, 2, 3, 4 -- and maybe a few more consecutive values).
Also, this definition does not assign an extent to all reordered
packets as defined by the singleton metric, in particular when
blocks of successive packets are reordered. (In the arrival sequence
s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only 4
is assigned a reordering extent according to Definition 1.) All
reordered packets are assigned a reordering extent by associating
them with a specific reordering event, as defined below.
4.2.4 Definition 2:
Note: The intent of this section is to assign a reordering extent to
all reordered packets, not just the ones identified by Definition 1.
This definition is new in this version and needs more study.
A packet s[i] that satisfies Definition 1 constitutes an n- Assign each packet a sequence number, a consecutive integer from 1
Reordering Event with the following characteristics: to K in the order of packet emission.
1. The maximum value of n that satisfies Definition 1 is the extent Let L be the total number of packets received out of the K packets
of the reordering event. (Extent n is assigned to all packets sent. Recall that identical copies (duplicates) have been removed,
associated with this event in part 3 below.) so L<=K.
2. The in-order packet arrival defined as beginning the event Let s[1], s[2], ..., s[L], represent the original sequence numbers
(having indicated a sequence discontinuity) is s[j] for j that associated with the packets in order of arrival.
satisfies the following:
min{j|1<=j<i} for which s[j]> s[i] Consider a reordered packet (as identified in section 3) with
arrival index i and source sequence number s[i]. There exists a set
of indexes j (1<=j<i) such that s[j] > s[i].
Typically i-n=j. This aspect of a reordering event is used later in 4.2.3 Definition:
the definition of the gap between successive events.
3. The arrival of any subsequent reordered packets with sequence The reordering extent, e, of packet s[i] is defined to be
number s meeting the following condition: i-j for the smallest value of j.
s[j] > s[*] > s[i], or Informally, the reordering extent is the maximum distance, in
(s at beginning of event) > s > (lowest s in the reordering event) packets, from a reordered packet to the earliest packet received
that has a larger sequence number. If a packet is in-order, it's
reordering extent is undefined. The first packet to arrive is in-
order by definition, and has undefined reordering extent.
are associated with the reordering event first identified by s[i], >>>>>>> Comment on this definition of extent: For some arrival
the sequence discontinuity that starts the event at s[j], and are orders, the assignment of a simple position/distance as the
assigned the same reordering extent, n. reordering extent tends to overestimate the receiver storage needed
>>> to restore order. We need to weigh the value of adding more
Comment on Part 3.: For some arrival orders, the assignment of the complexity in this definition against the accuracy it would provide.
same extent to all packets in a reordering event will tend to A more accurate and complex procedure to calculate packet storage
underestimate their true extent. However, a pure position/distance would be to subtract any earlier reordered packets that the receiver
metric (as appeared in earlier versions of this draft) would tend to could pass on to the upper layers.
overestimate the receiver storage needed. We need to weigh the value
of adding more complexity in this definition against the accuracy it
would provide.
A more accurate and complex procedure would be to count any
additional in-order packets that arrive after a reordering event is
identified, and add them to the extent of the first reordered packet
(up to some counter limit of interest) for packets in the interval
s[i] < s[*] < s[j].
Those who desire "on-the-fly" calculation must assess whether such a Those who desire "on-the-fly" calculation must assess whether such a
procedure is feasible. procedure is feasible.
Discussion: 4.2.4 Discussion:
A receiver must perform some amount of "work" to restore order to The packet with index j (s[j], identified in the Definition above)
all packets that are part of an n-reordering event. The extent n is the reordering discontinuity associated with packet with index i
(s[i]). This definition is formalized below.
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
out of the K packets sent in that subset.
A receiver must possess storage to restore order to packets that are
reordered. For cases with single reordered packets, the extent e
gives the number of packets that must be held in the receiver's gives the number of packets that must be held in the receiver's
buffer while waiting for the reordered packets in the sequence. As buffer while waiting for the reordered packet to complete the
reordered packets arrive, the amount of work stays the same if they sequence. For more complex scenarios, the extent may be an
are all part of the same reordering event. If new reordering events overestimate of required storage. See Examples section (specific
occur, the work in terms of buffer size can increase. See Examples example to be provided).
section (specific example to be provided).
Knowledge of the reordering extent n is particularly useful for Knowledge of the reordering extent e is particularly useful for
determining the portion of reordered packets that can or cannot be determining the portion of reordered packets that can or cannot be
restored to order in a typical TCP receiver buffer based on their restored to order in a typical receiver buffer based on their
arrival order alone (and without the aid of retransmission). arrival order alone (and without the aid of retransmission).
Important special cases are n=1 and n=3:
- For n=1, absence of 1-reordering events means the sequence numbers
that the receiver sees are monotonically increasing with respect to
the previous arriving packet.
- For n=3, a NewReno TCP sender would retransmit 1 packet in
response to a 3-reordering event and therefore consider this a loss
event for the purposes of congestion control (the sender will half
its congestion window). Detecting 3-reordering events is useful for
determining the portion of reordered packets that are in fact as
good as lost.
We note that the definition of n-reordering events cannot predict
the exact number of packets unnecessarily retransmitted by a TCP
sender under some circumstances, such as closely-spaced reordering
events. The definition is less complicated than a TCP implementation
where both time and position influence the sender's behavior.
A sample's reordering extents may be expressed as a histogram, to A sample's reordering extents may be expressed as a histogram, to
easily summarize the frequency of various extents. easily summarize the frequency of various extents.
4.3 Reordering Offset 4.3 Reordering Offset
Any packet whose sequence number causes the Next Expected value to
increment by more than the usual increment indicates a discontinuity
in the sequence. From this point on, any reordered packets can be
assigned Offset values indicating the storage in bytes and lateness
in terms of buffer time that a receiver must possess to accommodate
them. The various Offset metrics are calculated only on reordered
packets, as identified by the ordered arrival singleton in section
3.
4.3.1 Metric Name: Type-P-packet-Late-Time-Poisson/Periodic-Stream Any reordered packets can be assigned offset values indicating the
storage in bytes and lateness in terms of buffer time that a
receiver must possess to accommodate them. The various offset
metrics are calculated only on reordered packets, as identified by
the ordered arrival singleton in section 3.
4.3.1 Metric Name: Type-P-packet-Late-Time-Stream
Metric Parameters: In addition to the parameters defined for Type-P- Metric Parameters: In addition to the parameters defined for Type-P-
Non-Reversing-Order, we specify: Non-Reversing-Order, we specify:
+ DstTime, the time that each packet in the stream arrives at Dst + DstTime, the time that each packet in the stream arrives at Dst
Definition: Lateness in time is calculated using Dst times. When Definition: Lateness in time is calculated using Dst times. When
packet i is reordered, and part of a reordering event with n extent received packet i is reordered, and has a reordering extent e, then:
(assuming j=i-n):
LateTime(i) = DstTime(i)-DstTime(i-n) LateTime(i) = DstTime(i)-DstTime(i-e)
Alternatively, using similar notation to that of section 4.2, an Alternatively, using similar notation to that of section 4.2, an
equivalent definition is: equivalent definition is:
LateTime(i) = DstTime[i]-DstTime[j], for min{j|1<=j<i} that LateTime(i) = DstTime(i)-DstTime(j), for min{j|1<=j<i} that
satisfies s[j]>s[i], or SrcTime[j]>SrcTime[i]. satisfies s[j]>s[i], or SrcTime[j]>SrcTime[i].
4.3.2 Metric Name: Type-P-packet-Byte-Offset-Poisson/Periodic-Stream 4.3.2 Metric Name: Type-P-packet-Byte-Offset-Stream
Metric Parameters: We use the same parameters defined above. Metric Parameters: We use the same parameters defined above.
Definition: Byte stream offset is the sum of the payload sizes of Definition: Byte stream offset is the sum of the payload sizes of
all intervening packets between the reordered packet and the intervening in-order packets between the reordered packet and the
discontinuity (including the packet at the discontinuity). discontinuity (including the packet at the discontinuity).
For reordered packet i For reordered packet i with a reordering extent e:
ByteOffset(i) = Sum[in-order packets to start of the reordering ByteOffset(i) = Sum[in-order packets back to reordering discon.]
event] = Sum[PayloadSize(packet at i-1 if in-order),
= Sum[PayloadSize(packet at i-1), PayloadSize(packet at i-2 if in-order), ...
PayloadSize(packet at i-2), ... PayloadSize(packet at i-e if in-order)]
PayloadSize(packet at i-n)]
Alternatively, if all payload sizes are equal:
ByteOffset(i) = n * PayloadSize where n is the reordering extent.
>>>>Comment: Previous comments on the accuracy of extent n apply
here as well.
4.3.3 Discussion 4.3.3 Discussion
The Offset metrics can predict whether reordered packets will be The offset metrics can help predict whether reordered packets will
useful in a general receiver buffer system with finite limits. The be useful in a general receiver buffer system with finite limits.
limit may be the number of bytes or packets the buffer can store, or The limit may be the number of bytes or packets the buffer can
the time of storage prior to a cyclic play-out instant (as with de- store, or the time of storage prior to a cyclic play-out instant (as
jitter buffers). with de-jitter buffers).
Note that the One-way IPDV [9] gives the delay variation for a Note that the One-way IPDV [11] gives the delay variation for a
packet w.r.t. the preceding packet in the source sequence. Lateness packet w.r.t. the preceding packet in the source sequence. Lateness
and IPDV give an indication of whether a buffer at Dst has and IPDV give an indication of whether a buffer at Dst has
sufficient storage to accommodate the network's behavior and restore sufficient storage to accommodate the network's behavior and restore
order. When an earlier packet in the Src sequence is lost, IPDV will order. When an earlier packet in the Src sequence is lost, IPDV will
necessarily be undefined for adjacent packets, and Late Time may necessarily be undefined for adjacent packets, and Late Time may
provide the only way to evaluate the usefulness of a packet. provide the only way to evaluate the usefulness of a packet.
In the case of de-jitter buffers, there are circumstances where the In the case of de-jitter buffers, there are circumstances where the
receiver employs loss concealment at the intended play-out time of a receiver employs loss concealment at the intended play-out time of a
late packet. However, if this packet arrives out of order, the Late late packet. However, if this packet arrives out of order, the Late
Time determines whether the packet is still useful. IPDV no longer Time determines whether the packet is still useful. IPDV no longer
applies, because the receiver establishes a new play-out schedule applies, because the receiver establishes a new play-out schedule
with additional buffer delay to accommodate similar events in the with additional buffer delay to accommodate similar events in the
future - this requires very minimal processing. future - this requires very minimal processing.
When packets in the stream have variable sizes, it may be most When packets in the stream have variable sizes, it may be most
useful to characterize Offset in terms of the payload size(s) of useful to characterize Offset in terms of the payload size(s) of
stored packets (using byte stream numbering). stored packets (using byte stream numbering).
4.4 Gaps between multiple Reordering Events 4.4 Gaps between multiple Reordering Discontinuities
4.4.1 Metric Name: 4.4.1 Metric Name:
Type-P-packet-Reordering-Event-Gap-Poisson/Periodic-Stream Type-P-packet-Reordering-Gap-Stream
4.4.2 Parameters: 4.4.2 Parameters:
No new parameters. No new parameters.
4.4.3 Definition: 4.4.3 Definition of Reordering Discontinuity:
A reordering event with extent n is detected according to section All reordered packets are associated with a packet at a reordering
4.2 with the arrival of packet s[i]. The next reordering event with discontinuity, defined as the in-order packet arrival s[j] at the
extent n' is detected at packet i', and there are no reordering minimum value of j (1<=j<i) for which s[j]> s[i].
events between i and i'.
The Reordering Event Gap is the difference between the arrival Recall that i - e = min(j). Subsequent reordered packets may be
positions the packets, as shown below (assuming j=i-n): associated with the same s[j], or with a different discontinuity.
This definition is used in the definition of the Reordering Gap,
below.
Gap(i) = (i'-n') - (i-n) 4.4.4 Definition of Reordering Gap:
A reordering gap is the distance between successive reordering
discontinuities. Type-P-packet-Reordering-Gap-Stream assigns a value
to (all) packets in a stream.
If:
The packet s[j'] is found to be a reordering discontinuity, based
on the arrival of reordered packet s[i'] with extent e', and
an earlier reordering discontinuity s[j], based on the arrival of
reordered packet s[i] with extent e is detected, and
i' > i, and
there are no reordering discontinuities between j and j',
then the Reordering Gap for packet s[j'] is the difference between
the arrival positions the reordering discontinuities, as shown
below:
Gap(j') = (j') - (j)
Otherwise:
The Type-P-packet-Reordering-Gap-Stream for the packet is 0.
Gaps may also be expressed in time: Gaps may also be expressed in time:
GapTime(i) = DstTime(i'-n') - DstTime(i-n) GapTime(j') = DstTime(j') - DstTime(j)
The Gaps between a sample's reordering events may be expressed as a
histogram, to easily summarize the frequency of various extents.
4.4.4 Discussion 4.4.5 Discussion
When separate reordering events can be distinguished, then an event When separate reordering discontinuities can be distinguished, then
count may also be reported (along with the event description, such a count may also be reported (along with the discontinuity
as the number of reordered packets and their extents or offsets). description, such as the number of reordered packets associated with
The distribution of various metrics may also be reported and that discontinuity and their extents and offsets). The Gaps between
summarized by the mode, average, range, histogram, etc. a sample's reordering discontinuities may be expressed as a
histogram, to easily summarize the frequency of various gaps.
Reporting the mode, average, range, etc. may also summarize the
distributions.
The Gap metric may help to correlate the frequency of reordering The Gap metric may help to correlate the frequency of reordering
events with their cause. discontinuities with their cause.
5. Measurement Issues 4.5 Reordering-free Runs
This section defines a metric based on a count of consecutive in-
order packet arrivals.
4.5.1 Metric Name:
Type-P-packet-Reordering-Free-Run-Stream
4.5.2 Parameters:
No new parameters.
4.5.3 Definition:
As packets in a sample arrive at Dst, the count of packets to the
next reordered packet is a Reordering-Free run. Note that the
minimum run-length is one according to this definition. A pseudo
code example follows:
r = 0; /* r is the run counter */
z = 1; /* z is the index for storing different runs */
Run[*]; /* a vector of run-lengths */
while(packets arrive with sequence number s)
{
if (s >= NextExp) /* s is in-order */
then r++;
else /* s is reordered */
Run[z]=r;
r = 1;
z++;
}
4.5.4 Discussion:
Each arrival of a reordered packet yields a new count in the Run
vector. Long runs accompany periods where order was maintained,
while short runs indicate frequent, or multi-packet reordering.
5. Metric Related to Receiver Assessment
5.1 A TCP-Relevant Metric
5.1.1 Metric Name:
Type-P-packet-n-Reordering-Stream
5.1.2 Parameter Notation:
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
a non-negative integer representing the number of packets that were
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
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
packet emission.
Let s[1], s[2], ..., s[l] be the original sequence numbers of the
received packets, in the order of arrival.
5.1.3 Definitions
Definition 1: Received packet number i (n < i <= l), with source
sequence number s[i], is n-reordered if and only if for all j such
that i-n <= j < i, s[j] > s[i].
Claim: If by this definition, a packet's reordering is n and 0 < n'
< n, then the packet is also reordered to the n' extent.
Note: This definition is illustrated by C code in Appendix A. It
determines the n-reordering for a value of n=3 (when actually
writing applications that would report the metric, one would
probably report it for several values of n, such as 1, 2, 3, 4 --
and maybe a few more consecutive values).
This definition does not assign an n to all reordered packets as
defined by the singleton metric, in particular when blocks of
successive packets are reordered. (In the arrival sequence
s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only 4
is n-reordered, with n=3.)
Definition 2: The degree of n-reordering of the sample is m/l.
Definition 3: The degree of "monotonic reordering" of the sample is
its degree of 1-reordering.
Definition 4: A sample is said to have no reordering if its degree
of n-reordering is 0.
5.1.4 Discussion:
The degree of n-reordering may be expressed as a percentage, in
which case the number from definition 2 is multiplied by 100.
Knowledge of n-reordering is particularly useful for determining the
portion of reordered packets that can or cannot be restored to order
in a typical TCP receiver buffer based on their arrival order alone
(and without the aid of retransmission).
Important special cases are n=1 and n=3:
- For n=1, absence of 1-reordering means the sequence numbers that
the receiver sees are monotonically increasing with respect to the
previous arriving packet.
- For n=3, a NewReno TCP sender would retransmit 1 packet in
response to an instance of 3-reordering and therefore consider this
packet lost for the purposes of congestion control (the sender will
half its congestion window). Detecting instances of 3-reordering is
useful for determining the portion of reordered packets that are in
fact as good as lost.
We note that the definition of n-reordering cannot predict the exact
number of packets unnecessarily retransmitted by a TCP sender under
some circumstances, such as cases with closely-spaced reordered
singletons. The definition is less complicated than a TCP
implementation where both time and position influence the sender's
behavior.
A sample's n-reordering may be expressed as a histogram, to
summarize the frequency for each value of n.
6. Measurement Issues
The results of tests will be dependent on the time interval between The results of tests will be dependent on the time interval between
measurement packets (both at the Src, and during transport where measurement packets (both at the Src, and during transport where
spacing may change). Clearly, packets launched infrequently (e.g., spacing may change). Clearly, packets launched infrequently (e.g.,
1 per 10 seconds) are unlikely to be reordered. 1 per 10 seconds) are unlikely to be reordered.
Test streams may prefer to use a periodic sending interval so that a Test streams may prefer to use a periodic sending interval so that a
known temporal bias is maintained, also bringing simplified results known temporal bias is maintained, also bringing simplified results
analysis (as described in RFC 3432 [10]). In this case, the periodic analysis (as described in RFC 3432 [12]). In this case, the periodic
sending interval should be chosen to reproduce the closest Src sending interval should be chosen to reproduce the closest Src
packet spacing expected. packet spacing expected. Of course, packet spacing is likely to vary
<<<<Ed.Note: Need to expand this further, it is a very important as the stream traverses the test path.
<<<<Ed.Note: Is this sufficient? It is a very important
consideration. consideration.
The Non-reversing order criterion and all metrics described above The Non-reversing order criterion and all metrics described above
remain valid and useful when a stream of packets experiences packet remain valid and useful when a stream of packets experiences packet
loss, or both loss and reordering. In other words, losses alone do loss, or both loss and reordering. In other words, losses alone do
not cause subsequent packets to be declared reordered. not cause subsequent packets to be declared reordered.
Assuming that the necessary sequence information (sequence number Assuming that the necessary sequence information (sequence number
and/or source time stamp) is included in the packet payload and/or source time stamp) is included in the packet payload
(possibly in application headers such as RTP), packet sequence may (possibly in application headers such as RTP), packet sequence may
skipping to change at line 583 skipping to change at line 692
2. All sequence numbers used in computations are represented in a 2. All sequence numbers used in computations are represented in a
sufficiently large precision. The numbers have a correction applied sufficiently large precision. The numbers have a correction applied
(equivalent to adding a significant digit) whenever roll-over is (equivalent to adding a significant digit) whenever roll-over is
detected. detected.
3. Reordered packets coincident with sequence numbers reaching end- 3. Reordered packets coincident with sequence numbers reaching end-
of-range must also be detected for proper application of correction of-range must also be detected for proper application of correction
factor. factor.
6. Examples of Arrival Order Evaluation In practice, there may be limited ability to determine reordering
extent, because the storage for previous packets may be limited.
Saving only packets that indicate discontinuities (and their arrival
positions) will reduce storage volume. When discarding all stream
information beyond a threshold packet count, the reordering extent
or degree of n-reordering may need to be expressed as greater than
the threshold value, and Gap calculations would not be possible.
The requirement to ignore duplicate packets also requires storage.
Here, tracking the sequence numbers of missing packets may minimize
storage. Missing packets may eventually be declared lost, or
reordered if they arrive. The missing packet list and the largest
sequence number received thus far are sufficient information to
determine if a packet is a duplicate.
7. Examples of Arrival Order Evaluation
This section provides some examples to illustrate how the non- This section provides some examples to illustrate how the non-
reversing order criterion works, and the value of viewing reordering reversing order criterion works, and the value of viewing reordering
in both the dimensions of time and position. in both the dimensions of time and position.
Throughout this section, we will refer to packets by their source
sequence number, except where noted. So "Packet 4" refers to the
packet with source sequence number 4, and the reader should refer to
the tables in each example to determine packet 4's arrival index
number, if needed.
Table 1 gives a simple case of reordering, where one packet (the Table 1 gives a simple case of reordering, where one packet is
packet with s=4) arrives out-of-order. Packets are arranged reordered, Packet 4. Packets are listed according to their arrival,
according to their arrival, and message numbering is used. and message numbering is used.
Table 1 Example with Packet 4 Reordered, Table 1 Example with Packet 4 Reordered,
Sending order(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10 Sending order(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10
s Src Dst Dst Byte Late s Src Dst Dst Byte Late
@Dst NextExp Time Time Delay IPDV Order Offset Time @Dst NextExp Time Time Delay IPDV Order Offset Time
1 1 0 68 68 1 1 1 0 68 68 1
2 2 20 88 68 0 2 2 2 20 88 68 0 2
3 3 40 108 68 0 3 3 3 40 108 68 0 3
5 4 80 148 68 -82 4 5 4 80 148 68 -82 4
6 6 100 168 68 0 5 6 6 100 168 68 0 5
7 7 120 188 68 0 6 7 7 120 188 68 0 6
8 8 140 208 68 0 7 8 8 140 208 68 0 7
4 9 60 210 150 82 8 400 62 4 9 60 210 150 82 8 400 62
9 9 160 228 68 0 9 9 9 160 228 68 0 9
10 10 180 248 68 0 10 10 10 180 248 68 0 10
Each column gives the following information: Each column gives the following information:
S Packet sequence number at the Source. s Packet sequence number at the Source.
NextExp The value of NextExp when the packet arrived(before NextExp The value of NextExp when the packet arrived(before
update). update).
SrcTime Packet time stamp at the Source, ms. SrcTime Packet time stamp at the Source, ms.
DstTime Packet time stamp at the Destination, ms. DstTime Packet time stamp at the Destination, ms.
Delay 1-way delay of the packet, ms. Delay 1-way delay of the packet, ms.
IPDV IP Packet Delay Variation, ms IPDV IP Packet Delay Variation, ms
IPDV = Delay(SrcNum)-Delay(SrcNum-1) IPDV = Delay(SrcNum)-Delay(SrcNum-1)
DstOrder Order in which the packet arrived at the Destination. DstOrder Order in which the packet arrived at the Destination.
Byte Offset The Byte Offset of a reordered packet, in bytes. Byte Offset The Byte Offset of a reordered packet, in bytes.
LateTime The lateness of a reordered packet, in ms. LateTime The lateness of a reordered packet, in ms.
We can see that when packet 4 arrives, NextExp=9, and it is declared We can see that when Packet 4 arrives, NextExp=9, and it is declared
reordered. We compute the extent of the reordering event as follows: reordered. We compute the extent of reordering as follows:
Using the notation <s[1], ..., s[i], ..., s[l]>, the received Using the notation <s[1], ..., s[i], ..., s[L]>, the received
packets are represented as: packets are represented as:
\/ \/
s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10 s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
/\ /\
when n=1, 7<=J<8, and 8 > 4, so the reordering extent is 1 or more. when j=7, 8 > 4, so the reordering extent is 1 or more.
when n=2, 6<=J<8, and 7 > 4, so the reordering extent is 2 or more. when j=6, 7 > 4, so the reordering extent is 2 or more.
when n=3, 5<=J<8, and 6 > 4, so the reordering extent is 3 or more. when j=5, 6 > 4, so the reordering extent is 3 or more.
when n=4, 4<=J<8, and 5 > 4, so the reordering extent is 4 or more. when j=4, 5 > 4, so the reordering extent is 4 or more.
when n=5, 3<=J<8, but 3 < 4, and 4 is the maximum extent.
when j=3, but 3 < 4, and 4 is the maximum extent, e=4 (assuming
there are no earlier sequence discontinuities, as in this example).
Further, we can compute the Late Time (210-148=62ms using DstTime) Further, we can compute the Late Time (210-148=62ms using DstTime)
compared to packet 5's arrival. If Dst has a de-jitter buffer that compared to Packet 5's arrival. If the receiver has a de-jitter
holds more than 4 packets, or at least 62 ms storage, packet 4 may buffer that holds more than 4 packets, or at least 62 ms storage,
be useful. Note that 1-way delay and IPDV also indicate unusual Packet 4 may be useful. Note that 1-way delay and IPDV also indicate
behavior for packet 4. unusual behavior for Packet 4.
If all packets contained 100 byte payloads, then Byte Offset is If all packets contained 100 byte payloads, then Byte Offset is
equal to 400 bytes. equal to 400 bytes.
Following the definitions of section 5.1, Packet 4 is defined to be
4-reordered.
Table 2 Example with Packets 5 and 6 Reordered, Table 2 Example with Packets 5 and 6 Reordered,
Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10 Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10
s Src Dst Dst Byte Late s Src Dst Dst Byte Late
@Dst NextExp Time Time Delay IPDV Order Offset Time @Dst NextExp Time Time Delay IPDV Order Offset Time
1 1 0 68 68 1 1 1 0 68 68 1
2 2 20 88 68 0 2 2 2 20 88 68 0 2
3 3 40 108 68 0 3 3 3 40 108 68 0 3
4 4 60 128 68 0 4 4 4 60 128 68 0 4
7 5 120 188 68 -22 5 7 5 120 188 68 -22 5
5 8 80 189 109 41 6 100 1 5 8 80 189 109 41 6 100 1
6 8 100 190 90 -19 7 100 2 6 8 100 190 90 -19 7 100 2
8 8 140 208 68 0 8 8 8 140 208 68 0 8
9 9 160 228 68 0 9 9 9 160 228 68 0 9
10 10 180 248 68 0 10 10 10 180 248 68 0 10
Table 2 shows a case where packets 5 and 6 arrive just behind packet
Table 2 shows a case where Packets 5 and 6 arrive just behind Packet
7, so both 5 and 6 are reordered. The Late times (189-188=1, 190- 7, so both 5 and 6 are reordered. The Late times (189-188=1, 190-
188=2) are small. 188=2) are small.
Using the notation <s[1], ..., s[i], ..., s[l]>, the received Using the notation <s[1], ..., s[i], ..., s[l]>, the received
packets are represented as: packets are represented as:
\/ \/ \/ \/
s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10 s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
/\ /\ /\ /\
Considering packet 5[6] first: Considering Packet 5 first:
when n=1, 5<=J<6, and 7 > 5, so the reordering extent is 1 or more. when j=5, 7 > 5, so the reordering extent is 1 or more.
when n=2, 4<=J<6, but 4 < 5, and 1 is the maximum extent. when j=4, but 4 < 5, so 1 is its maximum extent, and e=1.
Considering packet 6[7] next: Considering Packet 6 next:
when n=1, 6<=J<7, and 5 < 6, so the packet at i=7 does not have its when j=6, 5 < 6, the extent is not yet defined.
own reordering extent, and must be part of the same reordering event when j=5, 7 > 6, so the reordering extent is i-j=2 or more.
as packet 5[6]. Using the test of Section 4.2.4, Definition 2, we when j=4, 4 < 6, and we find 2 is its maximum extent, and e=2.
find that the condition is met for packet 6[7]:
s[i] < s < s[i-n] We can also associate each of these reordered packets with a
5[6] < 6[7] < 7[5] reordering discontinuity. We find the minimum j=5 (for both packets)
according to Section 4.2.4. So Packet 6 is associated with the same
reordering discontinuity as Packet 5, at Packet 7.
A hypothetical sender/receiver pair may retransmit packet 5[8] Following the definitions of section 5.1, Packet 5 is defined to be
unnecessarily, since it is reordered with extent n=1(in agreement 1-reordered, but Packet 6 is not qualified n-reordered.
with the singleton metric). However, the receiver cannot advance
packet 7[5] to the higher layers until after packet 6[7] arrives. A hypothetical sender/receiver pair may retransmit Packet 5
Therefore, the singleton metric correctly determined that 6[7] is unnecessarily, since it is 1-reordered (in agreement with the
reordered, and both packets are part of a 1-reordering event. singleton metric). Though Packet 6 may not be unnecessarily
retransmitted, the receiver cannot advance Packet 7 to the higher
layers until after Packet 6 arrives. Therefore, the singleton metric
correctly determined that Packet 6 is 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 -68 4 7 4 120 188 68 -88 4
8 8 140 208 68 0 5 8 8 140 208 68 0 5
9 9 160 228 68 0 6 9 9 160 228 68 0 6
10 10 180 248 68 0 7 10 10 180 248 68 0 7
4 11 60 250 190 122 8 400 62 4 11 60 250 190 122 8 400 62
5 11 80 252 172 -18 9 400 64 5 11 80 252 172 -18 9 400 64
6 11 100 256 156 -16 10 400 68 6 11 100 256 156 -16 10 400 68
11 11 200 268 68 0 11 11 11 200 268 68 0 11
The case in Table 3 is where three packets in sequence have long The case in Table 3 is where three packets in sequence have long
transit times (packets with s = 4,5,and 6). Delay, Late time, and transit times (Packets with s = 4,5,and 6). Delay, Late time, and
Byte Offset capture this very well, and indicate variation in Byte Offset capture this very well, and indicate variation in
reordering extent, while IPDV indicates that the spacing between reordering extent, while IPDV indicates that the spacing between
packets 4,5,and 6 has changed. packets 4,5,and 6 has changed.
The histogram of Reordering extents (n) would be: The histogram of Reordering extents (e) would be:
Bin 1 2 3 4 5 6 7 Bin 1 2 3 4 5 6 7
Frequency 0 0 0 3 0 0 0 Frequency 0 0 0 1 1 1 0
Using the notation <s[1], ..., s[i], ..., s[l]>, the received Using the notation <s[1], ..., s[i], ..., s[l]>, the received
packets are represented as: packets are represented as:
s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11 s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11 i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11
Considering packet 4[8] first: We first calculate the n-reordering. Considering Packet 4 first:
when n=1, 7<=J<8, and 10> 4, so the reordering extent is 1 or more. when n=1, 7<=j<8, and 10> 4, so the packet is 1-reordered.
when n=2, 6<=J<8, and 9 > 4, so the reordering extent is 2 or more.
when n=3, 5<=J<8, and 8 > 4, so the reordering extent is 3 or more. when n=2, 6<=j<8, and 9 > 4, so the packet is 2-reordered.
when n=4, 4<=J<8, and 7 > 4, so the reordering extent is 4 or more. when n=3, 5<=j<8, and 8 > 4, so the packet is 3-reordered.
when n=5, 3<=J<8, but 3 < 4, and 4 is the maximum extent. when n=4, 4<=j<8, and 7 > 4, so the packet is 4-reordered.
when n=5, 3<=j<8, but 3 < 4, and 4 is the maximum n-reordering.
Considering packet 5[9] next: Considering packet 5[9] next:
when n=1, 8<=J<9, but 4 < 5, so the packet at i=9 does not have its when n=1, 8<=j<9, but 4 < 5, so the packet at i=9 is not qualified
own reordering extent, and must be part of the same reordering event as n-reordered. We find the same to for Packet 6.
as packet 4[8]. Using the test of Section 4.2.4, Definition 2, we
find that the condition is met for both packets 5[9] and 6[10]:
s[i] < s < s[i-n] We now consider whether reordered Packets 5 and 6 are associated
4[8] < 5[9] < 7[4] with the same reordering discontinuity as Packet 4. Using the test
4[8] < 6[10]< 7[4] of Section 4.2.4, Definition 2, we find that the minimum j=4 for all
three packets. They are all associated with the reordering
discontinuity at Packet 7.
This example shows again that the n-reordering event definition This example shows again that the n-reordering definition identifies
identifies a single event (s=4) with a sufficient degree of a single Packet (4) with a sufficient degree of reordering to result
reordering to result in one unnecessary packet retransmission by the in one unnecessary packet retransmission by the New Reno TCP sender.
New Reno TCP sender. Also, the reordered arrival of packets s=5 and Also, the reordered arrival of Packets 5 and 6 will allow the
s=6 will allow the receiver process to pass packets 7 through 10 up receiver process to pass Packets 7 through 10 up the protocol stack
the protocol stack (the singleton metric indicates 5 and 6 are (the singleton metric indicates 5 and 6 are reordered, and they are
reordered, and they are all part of one reordering event). all associated with a single reordering discontinuity).
7. Security Considerations Table 4 Example with Packets Multiple Reordering Discontinuities
Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
7.1 Denial of Service Attacks Discontinuity Discontinuity
|---------Gap---------|
s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
r = 1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, ...
Run[] counts = 5 1 6
Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has
e=2. There are two different reordering discontinuities at Packet 6
(where j=4) and Packet 12 (where j=11).
According to the definition of Reordering Gap
Gap(j') = (j') - (j)
Gap(11) = (11) - (4) = 7
We also have three reordering-free runs of lengths 5, 1, and 6.
The differences between these two multiple-event metrics are evident
here. Gaps are the distance between sequence discontinuities that
are subsequently defined as reordering discontinuities, while
reordering-free runs are capture the distance between reordered
packets.
8. Security Considerations
8.1 Denial of Service Attacks
This metric requires a stream of packets sent from one host (Src) to This metric requires a stream of packets sent from one host (Src) to
another host (Dst) through intervening networks. This method could another host (Dst) through intervening networks. This method could
be abused for denial of service attacks directed at Dst and/or the be abused for denial of service attacks directed at Dst and/or the
intervening network(s). intervening network(s).
Administrators of Src, Dst, and the intervening network(s) should Administrators of Src, Dst, and the intervening network(s) should
establish bilateral or multi-lateral agreements regarding the establish bilateral or multi-lateral agreements regarding the
timing, size, and frequency of collection of sample metrics. Use of timing, size, and frequency of collection of sample metrics. Use of
this method in excess of the terms agreed between the participants this method in excess of the terms agreed between the participants
may be cause for immediate rejection or discard of packets or other may be cause for immediate rejection or discard of packets or other
escalation procedures defined between the affected parties. escalation procedures defined between the affected parties.
7.2 User data confidentiality 8.2 User data confidentiality
Active use of this method generates packets for a sample, rather Active use of this method generates packets for a sample, rather
than taking samples based on user data, and does not threaten user than taking samples based on user data, and does not threaten user
data confidentiality. Passive measurement must restrict attention to data confidentiality. Passive measurement must restrict attention to
the headers of interest. Since user payloads may be temporarily the headers of interest. Since user payloads may be temporarily
stored for length analysis, suitable precautions MUST be taken to stored for length analysis, suitable precautions MUST be taken to
keep this information safe and confidential. keep this information safe and confidential.
7.3 Interference with the metric 8.3 Interference with the metric
It may be possible to identify that a certain packet or stream of It may be possible to identify that a certain packet or stream of
packets is part of a sample. With that knowledge at Dst and/or the packets is part of a sample. With that knowledge at Dst and/or the
intervening networks, it is possible to change the processing of the intervening networks, it is possible to change the processing of the
packets (e.g. increasing or decreasing delay) that may distort the packets (e.g. increasing or decreasing delay) that may distort the
measured performance. It may also be possible to generate measured performance. It may also be possible to generate
additional packets that appear to be part of the sample metric. additional packets that appear to be part of the sample metric.
These additional packets are likely to perturb the results of the These additional packets are likely to perturb the results of the
sample measurement. 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.
8. IANA Considerations 9. IANA Considerations
Since this metric does not define a protocol or well-known values, Since this metric does not define a protocol or well-known values,
there are no IANA considerations in this memo. there are no IANA considerations in this memo.
9. References 10. References
1 Bradner, S., "The Internet Standards Process -- Revision 3", BCP 1 Bradner, S., "The Internet Standards Process -- Revision 3", BCP
9, RFC 2026, October 1996. 9, RFC 2026, October 1996.
2 Bradner, S., "Key words for use in RFCs to Indicate Requirement 2 Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", RFC 2119, March 1997. Levels", RFC 2119, March 1997.
3 Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., "Framework 3 Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., "Framework
for IP Performance Metrics", RFC 2330, May 1998. for IP Performance Metrics", RFC 2330, May 1998.
skipping to change at line 814 skipping to change at line 980
3 Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., "Framework 3 Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., "Framework
for IP Performance Metrics", RFC 2330, May 1998. for IP Performance Metrics", RFC 2330, May 1998.
4 V.Paxson, "Measurements and Analysis of End-to-End Internet 4 V.Paxson, "Measurements and Analysis of End-to-End Internet
Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997, Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997,
ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz. ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz.
5 Postel, J., "Transmission Control Protocol", STD 7, RFC 793, 5 Postel, J., "Transmission Control Protocol", STD 7, RFC 793,
September 1981. September 1981.
Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt Obtain via: http://www.rfc-editor.org/rfc/rfc793.txt
6 L.Ciavattone and A.Morton, "Out-of-Sequence Packet Parameter 6 L.Ciavattone and A.Morton, "Out-of-Sequence Packet Parameter
Definition (for Y.1540)", Contribution number T1A1.3/2000-047, Definition (for Y.1540)", Contribution number T1A1.3/2000-047,
October 30, 2000. ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc October 30, 2000. ftp://ftp.t1.org/pub/t1a1/2000-A13/0a130470.doc
7 J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet Reordering is 7 J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet Reordering is
Not Pathological Network Behavior," IEEE/ACM Transactions on Not Pathological Network Behavior," IEEE/ACM Transactions on
Neteworking, vol.7, no.6, pp.789-798, December 1999. Neteworking, vol.7, no.6, pp.789-798, December 1999.
8 D.Loguinov and H.Radha, "Measurement Study of Low-bitrate 8 D.Loguinov and H.Radha, "Measurement Study of Low-bitrate
Internet Video Streaming"' Proceedings of the ACM SIGCOMM Internet Video Streaming", Proceedings of the ACM SIGCOMM
Internet Measurement Workshop 2001 November 1-2, 2001, San Internet Measurement Workshop 2001 November 1-2, 2001, San
Francisco, USA. Francisco, USA.
9 Demichelis, C., and Chimento, P., "IP Packet Delay Variation 9 J.Bellardo and S.Savage, "Measuring Packet Reordering,"
Proceedings of the ACM SIGCOMM Internet Measurement Workshop
2002, November 6-8, Marseille, France.
10 S.Jaiswal et al., "Measurement and Classification of Out-of-
Sequence Packets in a Tier-1 IP Backbone," Proceedings of the ACM
SIGCOMM Internet Measurement Workshop 2002, November 6-8,
Marseille, France.
11 Demichelis, C., and Chimento, P., "IP Packet Delay Variation
Metric for IP Performance Metrics (IPPM)", RFC 3393, November Metric for IP Performance Metrics (IPPM)", RFC 3393, November
2002. 2002.
10 Raisanen, V., Grotefeld, G., and Morton, A., "Network performance 12 Raisanen, V., Grotefeld, G., and Morton, A., "Network performance
measurement with periodic streams", RFC 3432, November 2002. measurement with periodic streams", RFC 3432, November 2002.
11. Acknowledgments 12. Acknowledgments
The authors would like to acknowledge many helpful discussions with The authors would like to acknowledge many helpful discussions with
Matt Mathis and Jon Bennett. We gratefully acknowledge the Matt Mathis, Jon Bennett, and Matt Zekauskas. We gratefully
foundation laid by the authors of the IP performance Framework [3]. acknowledge the foundation laid by the authors of the IP performance
Framework [3].
12. Appendix A (informative) 13. Appendix A (informative)
Two example c-code implementations of reordering definitions follow: Two example c-code implementations of reordering definitions follow:
Example 1 n-reordering ============================================ Example 1 n-reordering ============================================
#include <stdio.h> #include <stdio.h>
#define MAX_N 100 #define MAX_N 100
#define min(a, b) ((a) < (b)? (a): (b)) #define min(a, b) ((a) < (b)? (a): (b))
skipping to change at line 964 skipping to change at line 1142
receive_packets++; receive_packets++;
packet = atoi(argv[i]); packet = atoi(argv[i]);
reorder_packets += testorder2(packet); reorder_packets += testorder2(packet);
} }
printf("Received packets = %d, Reordered packets = %d\n", printf("Received packets = %d, Reordered packets = %d\n",
receive_packets, reorder_packets); receive_packets, reorder_packets);
exit(0); exit(0);
} }
13. Author's Addresses 13. Author's Addresses
Al Morton Al Morton
AT&T Labs AT&T Labs
Room D3 - 3C06 Room D3 - 3C06
200 Laurel Ave. South 200 Laurel Ave. South
Middletown, NJ 07748 USA Middletown, NJ 07748 USA
Phone +1 732 420 1571 Fax +1 732 368 1192 Phone +1 732 420 1571
<acmorton@att.com> <acmorton@att.com>
Len Ciavattone Len Ciavattone
AT&T Labs AT&T Labs
Room C4 - 2B29 Room C4 - 2B29
200 Laurel Ave. South 200 Laurel Ave. South
Middletown, NJ 07748 USA Middletown, NJ 07748 USA
Phone +1 732 420 1239 Phone +1 732 420 1239
<lencia@att.com> <lencia@att.com>
 End of changes. 

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