draft-ietf-ippm-reordering-01.txt | draft-ietf-ippm-reordering-02.txt | |||
---|---|---|---|---|
IP Performance Metrics Working Group A.Morton | Network Working Group A.Morton | |||
Internet Draft L.Ciavattone | Internet Draft L.Ciavattone | |||
Document: <draft-ietf-ippm-reordering-01.txt> G.Ramachandran | Document: <draft-ietf-ippm-reordering-02.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 32 | skipping to change at line 32 | |||
six months and may be updated, replaced, or made obsolete by other | six months and may be updated, replaced, or made obsolete by other | |||
documents at any time. It is inappropriate to use Internet-Drafts as | documents at any time. It is inappropriate to use Internet-Drafts as | |||
reference material or to cite them other than as "work in progress." | reference material or to cite them other than as "work in progress." | |||
The list of current Internet-Drafts can be accessed at | The list of current Internet-Drafts can be accessed at | |||
http://www.ietf.org/ietf/1id-abstracts.txt | http://www.ietf.org/ietf/1id-abstracts.txt | |||
The list of Internet-Draft Shadow Directories can be accessed at | The list of Internet-Draft Shadow Directories can be accessed at | |||
http://www.ietf.org/shadow.html. | http://www.ietf.org/shadow.html. | |||
1. 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 | suggests a metric definition, and discusses the issues associated | |||
with measurement. The memo includes sample metrics to quantify the | with measurement. The memo includes sample metrics to quantify the | |||
extent of reordering in several useful dimensions. Some examples of | extent of reordering in several useful dimensions. Some examples of | |||
evaluation using the various sample metrics are included. | evaluation using the various sample metrics are included. | |||
2. 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 | |||
implementation could perturb the network. | implementation could perturb the network. | |||
3. Introduction | 2. Introduction | |||
Ordered delivery is a property of successful packet transfer | Ordered delivery is a property of successful packet transfer | |||
attempts, where the packet sequence ascends for each arriving packet | attempts, where the packet sequence ascends for each arriving packet | |||
and there are no backward steps. | and there are no backward steps. | |||
An explicit sequence number, such as the sending time of each packet | An explicit sequence number, such as an incrementing message number | |||
or an incrementing message number carried in each packet establishes | or the packet sending time carried in each packet, establishes the | |||
the Source Sequence. | Source Sequence. | |||
The presence of reordering at the Destination is based on arrival | The presence of reordering at the Destination is based on arrival | |||
order. | order. | |||
This metric is consistent with RFC 2330 [3], and classifies arriving | This metric is consistent with RFC 2330 [3], and classifies arriving | |||
packets with sequence numbers smaller than their predecessors as | packets with sequence numbers smaller than their predecessors as | |||
out-of-order, or reordered. For example, if 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). The metric's construction | packets instead (4 and 5 in the example), but only the arrival of | |||
is very similar to the sequence space validation for received | packet 3 distinguishes this circumstance from packet loss. Focusing | |||
segments in RFC793 [5]. Earlier work to define ordered delivery | attention on late packets allows us to maintain orthogonality with | |||
includes [6], [7] and more ???. | the packet loss metric. The metric's construction is very similar to | |||
the sequence space validation for received segments in RFC793 [5]. | ||||
Earlier work to define ordered delivery includes [6], [7], [8 and | ||||
more ???. | ||||
3.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. | |||
Examples are: | Examples are: | |||
skipping to change at line 109 | skipping to change at line 112 | |||
buffers have different occupations and/or service rates, then | buffers have different occupations and/or service rates, then | |||
order will likely change. | order will likely change. | |||
The ability to restore order at the destination will likely have | The ability to restore order at the destination will likely have | |||
finite limits. Practical hosts have receiver buffers with finite | finite limits. Practical hosts have receiver buffers with finite | |||
size in terms of packets, bytes, or time (such as de-jitter | size in terms of packets, bytes, or time (such as de-jitter | |||
buffers). Once the initial determination of reordering is made, it | buffers). Once the initial determination of reordering is made, it | |||
is useful to quantify the extent of reordering, or lateness, in all | is useful to quantify the extent of reordering, or lateness, in all | |||
meaningful dimensions. | meaningful dimensions. | |||
3.2 Goals and Objectives | 2.2 Goals and Objectives | |||
The definitions below intend to satisfy the goals of: | The definitions below intend to satisfy the goals of: | |||
1. Determining whether or not packet order is maintained. | 1. Determining whether or not packet order is maintained. | |||
2. Quantifying the extent (achieving this second goal requires | 2. Quantifying the extent (achieving this second goal requires | |||
assumptions of upper layer functions and capabilities to | assumptions of upper layer functions and capabilities to | |||
restore order, and therefore several solutions). | restore order, and therefore several solutions). | |||
Reordering Metrics MUST: | Reordering Metrics MUST: | |||
+ be relevant to one or more known applications | + be relevant to one or more known applications | |||
skipping to change at line 131 | skipping to change at line 134 | |||
+ work with Poisson and Periodic test streams | + work with Poisson and Periodic test streams | |||
+ work even if the stream has duplicate or lost packets | + work even if the stream has duplicate or lost packets | |||
Reordering Metrics SHOULD: | 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 | |||
4. 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] gives the definitions of singletons, | |||
samples, and statistics. | samples, and statistics. | |||
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 Src. | |||
skipping to change at line 155 | skipping to change at line 158 | |||
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 Src 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. | |||
4.1 Metric Name: | 3.1 Metric Name: | |||
Type-P-Non-Reversing-Order | Type-P-Non-Reversing-Order | |||
4.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 Src (or wire time) | |||
+ SrcNum, the packet sequence number applied at the Src, in units | + s, the packet sequence number applied at the Src, in units of | |||
of messages or bytes. | messages. | |||
+ SrcByte, the packet sequence number applied at the Src, in units | ||||
of payload bytes. | ||||
+ NextExp, the Next Expected Sequence number at the Dst, in units | + NextExp, the Next Expected Sequence number at the Dst, in units | |||
of messages, time, or bytes. | 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 SrcNum sequence is based on byte | field and referred to when the SrcByte sequence is based on byte | |||
transfer. | transfer. | |||
4.3 Definition: | 3.3 Definition: | |||
In-order packets have sequence numbers (or Src times) greater than | In-order packets have sequence numbers (or Src times) greater than | |||
or equal to the value of Next Expected. Each new in-order packet | or equal to the value of Next Expected. Each new in-order packet | |||
will increase the Next Expected (typically by 1 for message | will increase the Next Expected (typically by 1 for message | |||
numbering, or the payload size plus 1 for byte numbering). The Next | numbering, or the payload size plus 1 for byte numbering). The Next | |||
Expected value cannot decrease, thereby specifying non-reversing | Expected value cannot decrease, thereby specifying non-reversing | |||
order as the basis to identify reordered packets. | order as the basis to identify reordered packets. | |||
A reordered packet outcome occurs when a single IP packet at the Dst | A reordered packet outcome occurs when a single IP packet at the Dst | |||
Measurement Point results in the following: | Measurement Point results in the following: | |||
The packet has a Src sequence number lower than the Next Expected | The packet has a Src sequence number lower than the Next Expected | |||
(NextExp), and therefore the packet is reordered. The Next Expected | (NextExp), and therefore the packet is reordered. The Next Expected | |||
value does not change on the arrival of this packet. | value does not change on the arrival of this packet. | |||
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 n: | On successful arrival of a packet with sequence number s: | |||
if n >= NextExp, /* n is in-order */ | if s >= NextExp, /* s is in-order */ | |||
then | then | |||
NextExp = n + PayloadSize + 1; | NextExp = s + PayloadSize + 1; | |||
else /* when n < NextExp */ | else /* when s < NextExp */ | |||
designate packet n as reordered; | designate packet s as reordered; | |||
When using message-based sequence numbering or Src time, | The sequence number s may be replaced by SrcTime or SrcByte. When | |||
using s (message-based sequence numbering) or Src time, | ||||
PayloadSize=0. | PayloadSize=0. | |||
4.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 if | |||
it is in-order, or reordered, based on a previous packet's arrival. | it is in-order, or reordered, based on a previous packet's arrival. | |||
In the case where Next Expected is Undefined (because the arriving | In the case where Next Expected is Undefined (because the arriving | |||
packet is the first successful transfer), the packet is designated | packet is the first successful transfer), the packet is designated | |||
in-order. | in-order. | |||
5. Sample Metrics | If duplicate packets (multiple non-corrupt copies) arrive at the | |||
destination, they MUST be noted and only the first to arrive is | ||||
considered for further analysis (additional copies would be declared | ||||
reordered according to the definition above). This requirement has | ||||
the same storage requirements as earlier IPPM metrics, and follows | ||||
the precedent of RFC 2679. | ||||
It is highly desirable to assert the degree to which a packet is | Packets with s > NextExp are a special case of in-order delivery. | |||
out-of-order, or reordered with respect to a sample of packets. This | This condition indicates a sequence discontinuity, either because of | |||
section defines several metrics that quantify the extent of | packet loss or reordering. Reordered packets must arrive for the | |||
reordering in various units of measure. Each metric highlights a | sequence discontinuity to be part of a reordering event (defined in | |||
relevant application. | the next section). Discontinuities are easiest to detect with | |||
message numbering or payload byte numbering where payload size is | ||||
constant, and may be possible with Periodic Streams and Src Time | ||||
numbering. | ||||
5.1 n-Reordering | 4. Sample Metrics | |||
[Note: This is the 10/2002 definition of n-Reordering. This | In this section, we define metrics applicable to a sample of packets | |||
definition focuses on TCP sender and receiver behavior, and in | from a single Src sequence number system. We begin with a simple | |||
particular, New Reno TCP behavior when n=3.] | ratio metric indicating the reordered portion of the sample. When | |||
this ratio is zero, no further reordering metrics are needed for | ||||
that sample. | ||||
Metric Name: Type-P-packet-n-reordering-Poisson/Periodic-Stream | 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 | ||||
sample of packets. This section defines several metrics that | ||||
quantify the extent of reordering in various units of measure. Each | ||||
"extent" metric highlights a relevant application. | ||||
Parameter Notation: Let n be a positive integer (a parameter). Let | 4.1 Reordered Packet Ratio | |||
k be a positive integer (sample size, the number of packets sent). | ||||
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. Let s[1], ..., | ||||
s[l] be the original sequence numbers of the received packets, in | ||||
the order of arrival (duplicates are possible). | ||||
Definition 1: Received packet number i (n < i <= l) is called n- | 4.1.1 Metric Name: | |||
reordered if and only if for all j such that i-n <= j < i we have | ||||
s[j] > s[i]. | ||||
Note: This definition is illustrated by C code in Appendix A. It | Type-P-Reordered-Ratio-Poisson/Periodic-Stream | |||
computes n-reordering 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). | ||||
Claim: If a packet is n-reordered and 0 < n' < n, then the packet is | 4.1.2 Metric Parameters: | |||
also n'-reordered. | ||||
Let m be the number of n-reordered packets in the sample. | The parameter set includes Type-P-Non-Reversing-Order singleton | |||
parameters, the parameters unique to Poisson or Periodic Streams, | ||||
plus the following: | ||||
Definition 2: The degree of n-reordering of the sample is m/(l-n). | + T0, a start time | |||
Definition 3: The degree of reordering of the sample is its degree | + Tf, an end time | |||
of 1-reordering. | ||||
<<<<Ed.Note - Def. 3 is no longer true using Definition 1. Blocks of | ||||
reordered packets are not classified in/out-of order equivalently by | ||||
singleton metric in section 4. See the examples in Table 2 and 3 in | ||||
section 7. It appears that packets with 1-reordering and higher may | ||||
be a subset of the reordered packets as designated by the singleton, | ||||
and this is TBD. | ||||
<<<<Ed.Note - Need to add a short subsection to define the metrics | + dT, a waiting time for each packet to arrive | |||
on "proportion of reordered packets in the sample". | ||||
Definition 4: A sample is said to have no reordering if its degree | 4.1.3 Definition: | |||
of reordering is 0. | ||||
Discussion: | For the packets arriving successfully between T0 and Tf+dT, the | |||
ratio of reordered packets in the sample is | ||||
The degree of n-reordering may be expressed as a percentage, in | (Total of Reordered packets) / (Total packets received) | |||
which case the number from definition 2 is multiplied by 100. | ||||
For a given sample, the number of n-reordered packets is the number | This fraction may be expressed as a percentage (multiply by 100%). | |||
of packets that would be considered as good as lost by a receiver | Note that in the case of duplicate packets, only the first copy is | |||
that uses a buffer of n packets to correct reordering. | used. | |||
Important special cases are n=1 and n=3: | 4.2 Reordering Events and their Extent | |||
Note: This section is expected to evolve further as we integrate the | ||||
various metrics of reordering extent (n-reordering and other | ||||
distance metrics used in earlier drafts). The co-authors are not yet | ||||
satisfied with all aspects of this section, and comments are | ||||
welcome. | ||||
- For n=1, absence of 1-reordering means the sequence numbers that | 4.2.1 Metric Name: | |||
the receiver sees are monotonically increasing with respect to the | ||||
previous arriving packet. | ||||
- For n=3, a NewReno TCP sender would retransmit 3-reordered packets | Type-P-packet-n-Reordering-Event-Poisson/Periodic-Stream | |||
and therefore consider 3-reordering a loss event for the purposes of | ||||
congestion control (the sender will half its congestion window). 3- | ||||
reordering is useful for determining the portion of reordered | ||||
packets that are in fact as good as lost. | ||||
n-reordering is particularly useful for determining the portion of | 4.2.2 Parameter Notation: | |||
reordered packets which 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). | ||||
5.2 Reordering Offset | Let n be a positive integer (a parameter). Let k be a positive | |||
integer (sample size, the number of packets sent). 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. | ||||
Any packet whose sequence number causes the Next Expected value to | Let s[1], s[2], ..., s[l] be the original sequence numbers of the | |||
increment by more than the usual increment indicates a discontinuity | received packets, in the order of arrival. | |||
in the sequence. From this point on, any packets with sequence | ||||
number less than the Next Expected value can be assigned Offset | ||||
values indicating their position (in packets or bytes) and lateness | ||||
in terms of time of arrival with respect to a sequence | ||||
discontinuity. The various Offset metrics are calculated only on | ||||
reordered packets, as defined in section 4. | ||||
5.2.1 Metric Name: Type-P-packet-Position-Offset-Poisson/Periodic- | 4.2.3 Definition 1: | |||
Stream | ||||
Metric Parameters: In addition to the parameters defined for Type-P- | Received packet number i (n < i <= l), with Src sequence number s | |||
Non-Reversing-Order, we specify: | (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]. | ||||
+ DstOrder, numerical order in which each packet in the stream | Claim: If by this definition, the extent of a packet's reordering is | |||
arrives at Dst | n and 0 < n' < n, then the packet is also reordered to the n' | |||
extent. | ||||
Definition: Reordered packets are associated with a specific | Note: This definition is illustrated by C code in Appendix A. It | |||
sequence discontinuity by determining which earlier packet's | determines the presence of n-reordering events for a particular | |||
sequence number skipped over them. We calculate all expressions of | value of n (when actually writing applications that would report the | |||
Offset with respect to that packet. Position Offset is calculated | metric, one would probably report it for several values of n, such | |||
from a Dst Order number assigned to each packet on arrival: | 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. | ||||
Position Offset = | 4.2.4 Definition 2: | |||
DstOrder(reordered packet)-DstOrder(packet at discontinuity) | 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. | ||||
Using the notation of Section 5.1, an equivalent definition is: | A packet s[i] that satisfies Definition 1 constitutes an n- | |||
The Position Offset of Reordered Packet i is m = i-j, for | Reordering Event with the following characteristics: | |||
min{j|1<=j<i} that satisfies s[j]> s[i]. | ||||
A sample's position offset may be expressed as a histogram, to | 1. The maximum value of n that satisfies Definition 1 is the extent | |||
easily summarize the extent and frequency of various offsets. | of the reordering event. (Extent n is assigned to all packets | |||
associated with this event in part 3 below.) | ||||
5.2.2 Metric Name: Type-P-packet-Late-Time-Poisson/Periodic-Stream | 2. The in-order packet arrival defined as beginning the event | |||
(having indicated a sequence discontinuity) is s[j] for j that | ||||
satisfies the following: | ||||
min{j|1<=j<i} for which s[j]> s[i] | ||||
Typically i-n=j. This aspect of a reordering event is used later in | ||||
the definition of the gap between successive events. | ||||
3. The arrival of any subsequent reordered packets with sequence | ||||
number s meeting the following condition: | ||||
s[j] > s[*] > s[i], or | ||||
(s at beginning of event) > s > (lowest s in the reordering event) | ||||
are associated with the reordering event first identified by s[i], | ||||
the sequence discontinuity that starts the event at s[j], and are | ||||
assigned the same reordering extent, n. | ||||
>>> | ||||
Comment on Part 3.: For some arrival orders, the assignment of the | ||||
same extent to all packets in a reordering event will tend to | ||||
underestimate their true extent. However, a pure position/distance | ||||
metric (as appeared in earlier versions of this draft) would tend to | ||||
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 | ||||
procedure is feasible. | ||||
Discussion: | ||||
A receiver must perform some amount of "work" to restore order to | ||||
all packets that are part of an n-reordering event. The extent n | ||||
gives the number of packets that must be held in the receiver's | ||||
buffer while waiting for the reordered packets in the sequence. As | ||||
reordered packets arrive, the amount of work stays the same if they | ||||
are all part of the same reordering event. If new reordering events | ||||
occur, the work in terms of buffer size can increase. See Examples | ||||
section (specific example to be provided). | ||||
Knowledge of the reordering extent n 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 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 | ||||
easily summarize the frequency of various extents. | ||||
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 | ||||
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. | Definition: Lateness in time is calculated using Dst times. When | |||
packet i is reordered, and part of a reordering event with n extent | ||||
(assuming j=i-n): | ||||
Late Time = | LateTime(i) = DstTime(i)-DstTime(i-n) | |||
DstTime(reordered packet)-DstTime(packet at discontinuity) | ||||
Using similar notation to that of Section 5.1, an equivalent | Alternatively, using similar notation to that of section 4.2, an | |||
definition is: | equivalent definition is: | |||
The Late Time of Reordered Packet i is t = DstTime[i]-DstTime[j], | LateTime(i) = DstTime[i]-DstTime[j], for min{j|1<=j<i} that | |||
for min{j|1<=j<i} that satisfies s[j]>s[i], or | satisfies s[j]>s[i], or SrcTime[j]>SrcTime[i]. | |||
SrcTime[j]>SrcTime[i]. | ||||
5.2.3 Metric Name: Type-P-packet-Byte-Offset-Poisson/Periodic-Stream | 4.3.2 Metric Name: Type-P-packet-Byte-Offset-Poisson/Periodic-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 | all intervening packets between the reordered packet and the | |||
discontinuity (including the packet at the discontinuity). | discontinuity (including the packet at the discontinuity). | |||
When reordered packet has DstOrder=m | For reordered packet i | |||
Byte Offset = Sum[PayloadSize(packet, DstOrder=m-1), | ByteOffset(i) = Sum[in-order packets to start of the reordering | |||
PayloadSize(packet, DstOrder=m-2), ... | event] | |||
PayloadSize(packet at discontinuity)] | = Sum[PayloadSize(packet at i-1), | |||
PayloadSize(packet at i-2), ... | ||||
PayloadSize(packet at i-n)] | ||||
5.2.4 Discussion | 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 | ||||
The Offset metrics can predict whether reordered packets will be | The Offset metrics can predict whether reordered packets will be | |||
useful in a general, but limited receiver buffer system. The limit | useful in a general receiver buffer system with finite limits. The | |||
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 store, or | |||
time of storage prior to a cyclic play-out instant (as with de- | the time of storage prior to a cyclic play-out instant (as with de- | |||
jitter buffers). | jitter buffers). | |||
Note that the One-way IPDV [8] gives the delay variation for a | Note that the One-way IPDV [9] 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). | |||
For a sample of packets in a stream, results may be reported as a | 4.4 Gaps between multiple Reordering Events | |||
ratio of reordered packets to total packets sent by the source | ||||
during the test. If separate reordering events can be distinguished, | ||||
then an event count may also be reported (along with the event | ||||
description, such as the number of reordered packets and their | ||||
offsets). The distribution of various Offset metrics may also be | ||||
reported and summarized as average, range, etc. | ||||
6. Measurement Issues | 4.4.1 Metric Name: | |||
Type-P-packet-Reordering-Event-Gap-Poisson/Periodic-Stream | ||||
4.4.2 Parameters: | ||||
No new parameters. | ||||
4.4.3 Definition: | ||||
A reordering event with extent n is detected according to section | ||||
4.2 with the arrival of packet s[i]. The next reordering event with | ||||
extent n' is detected at packet i', and there are no reordering | ||||
events between i and i'. | ||||
The Reordering Event Gap is the difference between the arrival | ||||
positions the packets, as shown below (assuming j=i-n): | ||||
Gap(i) = (i'-n') - (i-n) | ||||
Gaps may also be expressed in time: | ||||
GapTime(i) = DstTime(i'-n') - DstTime(i-n) | ||||
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 | ||||
When separate reordering events can be distinguished, then an event | ||||
count may also be reported (along with the event description, such | ||||
as the number of reordered packets and their extents or offsets). | ||||
The distribution of various metrics may also be reported and | ||||
summarized by the mode, average, range, histogram, etc. | ||||
The Gap metric may help to correlate the frequency of reordering | ||||
events with their cause. | ||||
5. 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 [Ref to npmps]. In this case, the periodic sending interval | analysis (as described in RFC 3432 [10]). In this case, the periodic | |||
should be chosen to reproduce the closest Src packet spacing | sending interval should be chosen to reproduce the closest Src | |||
expected. | packet spacing expected. | |||
<<<<Ed.Note: Need to expand this further, it is a very important | <<<<Ed.Note: Need to expand this further, it is a very important | |||
consideration. | consideration. | |||
The Non-reversing order criterion remains valid and useful when a | The Non-reversing order criterion and all metrics described above | |||
stream of packets experiences packet loss, or both loss and | remain valid and useful when a stream of packets experiences packet | |||
reordering. In other words, losses alone do not cause subsequent | loss, or both loss and reordering. In other words, losses alone do | |||
packets to be declared reordered. | not cause subsequent packets to be declared reordered. | |||
Assuming that the necessary sequence information (sequence number | Assuming that the necessary sequence information (sequence number | |||
and/or source time stamp) is included in the packet payload | and/or source time stamp) is included in the packet payload | |||
(possibly in application headers such as RTP), packet sequence may | (possibly in application headers such as RTP), packet sequence may | |||
be evaluated in a passive measurement arrangement. Also, it is | be evaluated in a passive measurement arrangement. Also, it is | |||
possible to evaluate sequence at a single point along a path, since | possible to evaluate sequence at a single point along a path, since | |||
the usual need for synchronized Src and Dst Clocks may be relaxed to | the usual need for synchronized Src and Dst Clocks may be relaxed to | |||
some extent. | some extent. | |||
When the Src sequence is based on byte stream, or payload numbering, | When the Src sequence is based on byte stream, or payload numbering, | |||
care must be taken to avoid declaring retransmitted packets out-of- | care must be taken to avoid declaring retransmitted packets | |||
sequence. The additional reference of Src Time is one way to avoid | reordered. The additional reference of Src Time is one way to avoid | |||
this ambiguity. | this ambiguity. | |||
Since this metric definition may use sequence numbers with finite | Since this metric definition may use sequence numbers with finite | |||
range, it is possible that the sequence numbers could reach end-of- | range, it is possible that the sequence numbers could reach end-of- | |||
range and roll over to zero during a measurement. By definition, | range and roll over to zero during a measurement. By definition, | |||
the Next Expected value cannot decrease, and all packets received | the Next Expected value cannot decrease, and all packets received | |||
after a roll-over would be declared out-of-sequence. Sequence | after a roll-over would be declared reordered. Sequence number | |||
number roll-over can be avoided by using combinations of counter | roll-over can be avoided by using combinations of counter size and | |||
size and test duration where roll-over is impossible (and sequence | test duration where roll-over is impossible (and sequence is reset | |||
is reset to zero at the start). Also, message-based numbering | to zero at the start). Also, message-based numbering results in | |||
results in slower sequence consumption. There may still be cases | slower sequence consumption. There may still be cases where | |||
where methodological mitigation of this problem is desirable (e.g., | methodological mitigation of this problem is desirable (e.g., long- | |||
long-term testing). The elements of mitigation are: | term testing). The elements of mitigation are: | |||
1. There must be a test to detect if a roll-over has occurred. It | 1. There must be a test to detect if a roll-over has occurred. It | |||
would be nearly impossible for the sequence numbers of successive | would be nearly impossible for the sequence numbers of successive | |||
packets to jump by more than half the total range, so these large | packets to jump by more than half the total range, so these large | |||
discontinuities are designated as roll-over. | discontinuities are designated as roll-over. | |||
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. Out-of-order packets coincident with sequence numbers reaching | 3. Reordered packets coincident with sequence numbers reaching end- | |||
end-of-range must also be detected for proper application of | of-range must also be detected for proper application of correction | |||
correction factor. | factor. | |||
6. Examples of Arrival Order Evaluation | ||||
7. Examples of 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. | |||
Table 1 gives a simple case of reordering, where one packet (the | Table 1 gives a simple case of reordering, where one packet (the | |||
packet with SrcNum=4) arrives out-of-order. Packets are arranged | packet with s=4) arrives out-of-order. Packets are arranged | |||
according to their arrival, and message numbering is used. | according to their arrival, 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 | |||
SrcNum Src Dst Dst Posit. 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 4 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: | |||
SrcNum 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. | |||
Posit.Offset The Position Offset of an out-of-order packet. | Byte Offset The Byte Offset of a reordered packet, in bytes. | |||
LateTime The lateness of an out-of-order packet, 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. Further, we can compute the Offset of packet 4 in terms | reordered. We compute the extent of the reordering event as follows: | |||
of position (8-4=4 using DstOrder) and Late Time (210-148=62ms using | ||||
DstTime) compared to packet 5's arrival. If Dst has a de-jitter | ||||
buffer that holds more than 4 packets, or at least 62 ms storage, | ||||
packet 4 may be useful. Note that 1-way delay and IPDV also indicate | ||||
unusual behavior for packet 4. | ||||
If all packets contained 100 byte payloads, then Byte Offset is | ||||
equal to 500 bytes. | ||||
In the notation of n-reordering, <s[1], ..., s[i], ..., s[l]> the | Using the notation <s[1], ..., s[i], ..., s[l]>, the received | |||
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 packet at i=8 is 1-reordered. | when n=1, 7<=J<8, and 8 > 4, so the reordering extent is 1 or more. | |||
when n=2, 6<=J<8, and 7 > 4, so the packet at i=8 is 2-reordered. | when n=2, 6<=J<8, and 7 > 4, so the reordering extent is 2 or more. | |||
when n=3, 5<=J<8, and 6 > 4, so the packet at i=8 is 3-reordered. | when n=3, 5<=J<8, and 6 > 4, so the reordering extent is 3 or more. | |||
when n=4, 4<=J<8, and 5 > 4, so the packet at i=8 is 4-reordered. | when n=4, 4<=J<8, and 5 > 4, so the reordering extent is 4 or more. | |||
when n=5, 3<=J<8, but 3 < 4, no more reordering. | when n=5, 3<=J<8, but 3 < 4, and 4 is the maximum extent. | |||
We note that the Position Offset is equal to the Max(n) with n- | Further, we can compute the Late Time (210-148=62ms using DstTime) | |||
reordering. | compared to packet 5's arrival. If Dst has a de-jitter buffer that | |||
holds more than 4 packets, or at least 62 ms storage, packet 4 may | ||||
be useful. Note that 1-way delay and IPDV also indicate unusual | ||||
behavior for packet 4. | ||||
If all packets contained 100 byte payloads, then Byte Offset is | ||||
equal to 400 bytes. | ||||
Table 2 Example with Packets 5 and 6 Reordered, | Table 2 Example with Packets 5 and 6 Reordered, | |||
Sending order(SrcNum@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 | |||
SrcNum Src Dst Dst Posit. 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 1 1 | 5 8 80 189 109 41 6 100 1 | |||
6 8 100 190 90 -19 7 2 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 declared out-of-order. Their positional | 7, so both 5 and 6 are reordered. The Late times (189-188=1, 190- | |||
offsets (6-5=1 and 7-5=2, using DstOrder again) and Late times (189- | 188=2) are small. | |||
188=1, 190-188=2) are small. | ||||
Using the notation <s[1], ..., s[i], ..., s[l]>, the received | ||||
packets are represented as: | ||||
In the notation of n-reordering, the received 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[6] first: | |||
when n=1, 5<=J<6, and 7 > 5, so the packet at i=6 is 1-reordered. | when n=1, 5<=J<6, and 7 > 5, so the reordering extent is 1 or more. | |||
when n=2, 4<=J<6, but 4 < 5, same for all earlier packets. | when n=2, 4<=J<6, but 4 < 5, and 1 is the maximum extent. | |||
Considering packet 6[7] next: | Considering packet 6[7] next: | |||
when n=1, 6<=J<7, and 5 < 6, so the packet at I=7 is not n-reordered | when n=1, 6<=J<7, and 5 < 6, so the packet at i=7 does not have its | |||
for any n, even though: | own reordering extent, and must be part of the same reordering event | |||
when N=2, 5<=J<7, and 7 > 6, | as packet 5[6]. Using the test of Section 4.2.4, Definition 2, we | |||
because n-reordering requires s[j]>s[i] | find that the condition is met for packet 6[7]: | |||
for all j such that i-n <= j < i (see Definition 1 in section 5.1). | ||||
s[i] < s < s[i-n] | ||||
5[6] < 6[7] < 7[5] | ||||
A hypothetical sender/receiver pair may retransmit packet 5[8] | A hypothetical sender/receiver pair may retransmit packet 5[8] | |||
unnecessarily, since it is 1-reordered (in agreement with the | unnecessarily, since it is reordered with extent n=1(in agreement | |||
singleton metric). However, the receiver cannot advance packet 7[5] | with the singleton metric). However, the receiver cannot advance | |||
to the higher layers until after packet 6[7] arrives. Therefore, the | packet 7[5] to the higher layers until after packet 6[7] arrives. | |||
singleton metric correctly determined that 6[7] is reordered, and | Therefore, the singleton metric correctly determined that 6[7] is | |||
the n-reordering metric indicates that the hypothetical receiver can | reordered, and both packets are part of a 1-reordering event. | |||
deal with its arrival efficiently (no unnecessary retransmission). | ||||
Table 3 Example with Packets 4, 5, and 6 reordered | Table 3 Example with Packets 4, 5, and 6 reordered | |||
Sending order(SrcNum@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 | |||
SrcNum Src Dst Dst Posit. 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 -68 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 4 62 | 4 11 60 250 190 122 8 400 62 | |||
5 11 80 252 172 -18 9 5 64 | 5 11 80 252 172 -18 9 400 64 | |||
6 11 100 256 156 -16 10 6 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 SrcNum 4,5,and 6). Delay, Late time, and | transit times (packets with s = 4,5,and 6). Delay, Late time, and | |||
Position 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 Position Offsets would be: | The histogram of Reordering extents (n) would be: | |||
Bin 1 2 3 4 5 6 7 | Bin 1 2 3 4 5 6 7 | |||
Frequency 0 0 0 1 1 1 0 | Frequency 0 0 0 3 0 0 0 | |||
In the notation of n-reordering, the received packets are | Using the notation <s[1], ..., s[i], ..., s[l]>, the received | |||
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: | Considering packet 4[8] first: | |||
when n=1, 7<=J<8, and 10> 4, so the packet at i=8 is 1-reordered. | when n=1, 7<=J<8, and 10> 4, so the reordering extent is 1 or more. | |||
when n=2, 6<=J<8, and 9 > 4, so the packet at i=8 is 2-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 packet at i=8 is 3-reordered. | when n=3, 5<=J<8, and 8 > 4, so the reordering extent is 3 or more. | |||
when n=4, 4<=J<8, and 7 > 4, so the packet at i=8 is 4-reordered. | when n=4, 4<=J<8, and 7 > 4, so the reordering extent is 4 or more. | |||
when n=5, 3<=J<8, but 3 < 4, same for all earlier packets. | when n=5, 3<=J<8, but 3 < 4, and 4 is the maximum extent. | |||
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 | ||||
own reordering extent, and must be part of the same reordering event | ||||
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]: | ||||
when n=1, 8<=J<9, and 4 < 5, so the packet at I=9 is not n-reordered | s[i] < s < s[i-n] | |||
4[8] < 5[9] < 7[4] | ||||
4[8] < 6[10]< 7[4] | ||||
This example shows again that the n-reordering definition identifies | This example shows again that the n-reordering event definition | |||
a single packet (SrcNum=4) with a sufficient degree of reordering to | identifies a single event (s=4) with a sufficient degree of | |||
result in one unnecessary packet retransmission by the New Reno TCP | reordering to result in one unnecessary packet retransmission by the | |||
sender. Also, the delayed arrival of SrcNum=5 and SrcNum=6 will | New Reno TCP sender. Also, the reordered arrival of packets s=5 and | |||
allow the receiver process to pass Src packets 7 through 10 up the | s=6 will allow the receiver process to pass packets 7 through 10 up | |||
protocol stack (the singleton metric indicates 5 and 6 are | the protocol stack (the singleton metric indicates 5 and 6 are | |||
reordered). | reordered, and they are all part of one reordering event). | |||
8. Security Considerations [mostly borrowed from npmps] | 7. Security Considerations | |||
8.1 Denial of Service Attacks | 7.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. | |||
8.2 User data confidentiality | 7.2 User data confidentiality | |||
Active use of this method generates packets for a sample, rather | Active use of this method generates packets for a sample, rather | |||
than taking samples based on user data, and does not threaten user | than taking samples based on user data, and does not threaten user | |||
data confidentiality. Passive measurement must restrict attention to | data confidentiality. Passive measurement must restrict attention to | |||
the headers of interest. Since user payloads may be temporarily | the headers of interest. Since user payloads may be temporarily | |||
stored for length analysis, suitable precautions MUST be taken to | stored for length analysis, suitable precautions MUST be taken to | |||
keep this information safe and confidential. | keep this information safe and confidential. | |||
8.3 Interference with the metric | 7.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. | |||
9. IANA Considerations | 8. IANA Considerations | |||
Since this metric does not define a protocol or well-known values, | Since this metric does not define a protocol or well-known values, | |||
there are no IANA considerations in this memo. | there are no IANA considerations in this memo. | |||
10. References | 9. 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 681 | skipping to change at line 814 | |||
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 Demichelis, C., and Chimento, P., "IP Packet Delay Variation | 8 D.Loguinov and H.Radha, "Measurement Study of Low-bitrate | |||
Metric for IPPM", work in progress. | Internet Video Streaming"' Proceedings of the ACM SIGCOMM | |||
Internet Measurement Workshop 2001 November 1-2, 2001, San | ||||
Francisco, USA. | ||||
9 Demichelis, C., and Chimento, P., "IP Packet Delay Variation | ||||
Metric for IP Performance Metrics (IPPM)", RFC 3393, November | ||||
2002. | ||||
10 Raisanen, V., Grotefeld, G., and Morton, A., "Network performance | ||||
measurement with periodic streams", RFC 3432, November 2002. | ||||
11. Acknowledgments | 11. Acknowledgments | |||
The authors would like to acknowledge the helpful discussions with | The authors would like to acknowledge many helpful discussions with | |||
Matt Mathis and Jon Bennett. We gratefully acknowledge the | Matt Mathis and Jon Bennett. We gratefully acknowledge the | |||
foundation laid by the authors of the IP performance Framework [3]. | foundation laid by the authors of the IP performance Framework [3]. | |||
12. Appendix A (informative) | 12. 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> | |||
End of changes. | ||||
This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/ |