draft-ietf-ippm-reordering-03.txt | draft-ietf-ippm-reordering-04.txt | |||
---|---|---|---|---|
Network Working Group A.Morton | Network Working Group A.Morton | |||
Internet Draft L.Ciavattone | Internet Draft L.Ciavattone | |||
Document: <draft-ietf-ippm-reordering-03.txt> G.Ramachandran | Document: <draft-ietf-ippm-reordering-04.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 34 | skipping to change at line 34 | |||
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. | |||
Abstract | Abstract | |||
This memo defines a simple metric to determine if a network has | This memo defines metrics to evaluate if a network has maintained | |||
maintained packet order. It provides motivations for the new metric, | packet order on a packet-by-packet basis. It provides motivations | |||
gives the metric definition, and discusses the issues associated | for the new metrics and discusses the measurement issues. The memo | |||
with its measurement. The memo defines additional sample metrics to | first defines a reordered singleton, and then uses it as the basis | |||
quantify the extent of reordering in several useful dimensions. Some | for sample metrics to quantify the extent of reordering in several | |||
useful dimensions. Additional metrics quantify the frequency of | ||||
reordering and the distance between separate occurrences. We then | ||||
define metrics with a receiver analysis orientation. Several | ||||
examples of evaluation using the various sample metrics are | examples of evaluation using the various sample metrics are | |||
included. | 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 | |||
Packet Reordering Metric for IPPM October 2003 | ||||
ensure the results of measurements from two different | ensure the results of measurements from two different | |||
implementations are comparable, and to note instances when an | implementations are comparable, and to note instances when an | |||
implementation could perturb the network. | implementation could perturb the network. | |||
2. Introduction | 2. Introduction | |||
Ordered delivery is a property of successful packet transfer | Ordered delivery is a property of successful packet transfer | |||
attempts, where the packet sequence ascends for each arriving packet | attempts, where the packet sequence ascends for each arriving packet | |||
and there are no backward steps. | and there are no backward steps. | |||
An explicit sequence number, such as an incrementing message number | An explicit sequence number, such as an incrementing message number | |||
or the packet sending time carried in each packet, establishes the | or the packet sending time carried in each packet, establishes the | |||
Source Sequence. | Source Sequence. | |||
The presence of reordering at the Destination is based on arrival | The detection of reordering at the Destination is based on packet | |||
order. | arrival order in comparison with a non-reversing reference value. | |||
This metric is consistent with RFC 2330 [3], and classifies arriving | This metric is consistent with RFC 2330 [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 sequentially numbered | |||
numbered 1,2,4,5,3, then packet 3 is reordered. This is equivalent | packets arrive 1,2,4,5,3, then packet 3 is reordered. This is | |||
to Paxon's reordering definition in [4], where "late" packets were | equivalent to Paxon's reordering definition in [4], where "late" | |||
declared reordered. The alternative is to emphasize "premature" | packets were declared reordered. The alternative is to emphasize | |||
packets instead (4 and 5 in the example), but only the arrival of | "premature" packets instead (4 and 5 in the example), but only the | |||
packet 3 distinguishes this circumstance from packet loss. Focusing | arrival of packet 3 distinguishes this circumstance from packet | |||
attention on late packets allows us to maintain orthogonality with | loss. Focusing attention on late packets allows us to maintain | |||
the packet loss metric. The metric's construction is very similar to | orthogonality with the packet loss metric. The metric's construction | |||
the sequence space validation for received segments in RFC793 [5]. | is very similar to the sequence space validation for received | |||
Earlier work to define ordered delivery includes [6], [7], [8], [9], | segments in RFC793 [5]. Earlier work to define ordered delivery | |||
[10] and more ???. | includes [6], [7], [8], [9], [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 order to change. | |||
Examples are: | Examples are: | |||
* When two paths, one with slightly longer transfer time, support a | * When two paths, one with slightly longer transfer time, support a | |||
single packet stream or flow, then packets traversing the longer | single packet stream or flow, then packets traversing the longer | |||
path may arrive out-of-order. Multiple paths may be used to | path may arrive out-of-order. Multiple paths may be used to | |||
achieve load balancing, or may arise from route instability. | achieve load balancing, or may arise from route instability. | |||
* To increase capacity, a network device designed with multiple | * To increase capacity, a network device designed with multiple | |||
processors serving a single port may reorder as a byproduct. | processors serving a single port may reorder as a byproduct. | |||
* A layer 2 retransmission protocol that compensates for an error- | * A layer 2 retransmission protocol that compensates for an error- | |||
prone link may cause packet reordering. | prone link may cause packet reordering. | |||
Packet Reordering Metric for IPPM October 2003 | ||||
* If for any reason, the packets in a buffer are not serviced in the | * If for any reason, the packets in a buffer are not serviced in the | |||
order of their arrival, their order will change. | order of their arrival, their order will change. | |||
* If packets in a flow are assigned to multiple buffers (following | * If packets in a flow are assigned to multiple buffers (following | |||
evaluation of traffic characteristics, for example), and the | evaluation of traffic characteristics, for example), and the | |||
buffers have different occupations and/or service rates, then | buffers have different occupations and/or service rates, then | |||
order will likely change. | order will likely change. | |||
When one or more of the above path characteristics are present | ||||
continuously, then reordering may be present on a steady-state | ||||
basis. Measurements most easily detect this form of reordering when | ||||
the spacing between packets is minimized. Transient reordering may | ||||
occur in response to network instability; temporary routing loops | ||||
can cause periods of extreme reordering. | ||||
The ability to restore order at the destination will likely have | The ability to restore order at the destination will likely have | |||
finite limits. Practical hosts have receiver buffers with finite | finite limits. Practical hosts have receiver buffers with finite | |||
size in terms of packets, bytes, or time (such as de-jitter | size in terms of packets, bytes, or time (such as de-jitter | |||
buffers). Once the initial determination of reordering is made, it | buffers). Once the initial determination of reordering is made, it | |||
is useful to quantify the extent of reordering, or lateness, in all | is useful to quantify the extent of reordering, or lateness, in all | |||
meaningful dimensions. | meaningful dimensions. | |||
2.2 Goals and Objectives | 2.2 Goals and Objectives | |||
The definitions below intend to satisfy the goals of: | The definitions below intend to satisfy the goals of: | |||
skipping to change at line 135 | skipping to change at line 151 | |||
+ 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 | |||
3. An Ordered Arrival Singleton Metric | 3. A Reordered Packet Singleton Metric | |||
The IPPM framework RFC 2330 [3] describes the notions of singletons, | The IPPM framework RFC 2330 [3] describes the notions of singletons, | |||
samples, and statistics. For easy reference: | samples, and statistics. For easy reference: | |||
By a 'singleton' metric, we refer to metrics that are, | By a 'singleton' metric, we refer to metrics that are, | |||
in a sense, atomic. For example, a single instance of "bulk | in a sense, atomic. For example, a single instance of "bulk | |||
throughput capacity" from one host to another might be defined | throughput capacity" from one host to another might be defined | |||
Packet Reordering Metric for IPPM October 2003 | ||||
as a singleton metric, even though the instance involves | as a singleton metric, even though the instance involves | |||
measuring the timing of a number of Internet packets. | measuring the timing of a number of Internet packets. | |||
The evaluation of packet order requires several supporting concepts. | The evaluation of packet order requires several supporting concepts. | |||
The first is a sequence number applied to packets at the source to | The first is a sequence number applied to packets at the source to | |||
uniquely identify the order of packet transmission. The sequence | uniquely identify the order of packet transmission. The sequence | |||
number may be established by a simple message number, a byte stream | number may be established by a simple message number, a byte stream | |||
number, or it may be the actual time when each packet departs from | number, or it may be the actual time when each packet departs from | |||
the Source. | the Source. | |||
The second supporting concept is a stored value which is the "next | The second supporting concept is a stored value which is the "next | |||
expected" packet number. Under normal conditions, the value of Next | expected" packet number. Under normal conditions, the value of Next | |||
Expected (NextExp) is the sequence number of the previous packet | Expected (NextExp) is the sequence number of the previous packet | |||
(plus 1 for message numbering). In byte stream numbering, NextExp | (plus 1 for message numbering). | |||
is a value 1 byte greater than the last in-order packet sequence | ||||
number + payload. If Source time is used as the sequence number, | ||||
NextExp is the Src time from the last in-order packet + 1 clock | ||||
tick. | ||||
Each packet within a packet stream can be evaluated for its order | Each packet within a packet stream can be evaluated with this order | |||
singleton metric. | singleton metric. | |||
3.1 Metric Name: | 3.1 Metric Name: | |||
Type-P-Non-Reversing-Order | Type-P-Reordered | |||
3.2 Metric Parameters: | 3.2 Metric Parameters: | |||
+ Src, the IP address of a host | + Src, the IP address of a host | |||
+ Dst, the IP address of a host | + Dst, the IP address of a host | |||
+ SrcTime, the time of packet emission from the Source (or wire | + SrcTime, the time of packet emission from the Source (or wire | |||
time) | time) | |||
skipping to change at line 193 | skipping to change at line 208 | |||
+ NextExp, the Next Expected Sequence number at the Destination, in | + NextExp, the Next Expected Sequence number at the Destination, in | |||
units of messages, time, or bytes. | units of messages, time, or bytes. | |||
+ PayloadSize, the number of bytes contained in the information | + PayloadSize, the number of bytes contained in the information | |||
field and referred to when the SrcByte sequence is based on byte | field and referred to when the SrcByte sequence is based on byte | |||
transfer. | transfer. | |||
3.3 Definition: | 3.3 Definition: | |||
The Type-P-Non-Reversing-Order of a packet is defined as true if | The value of Type-P-Reordered is defined as false if s >= NextExp | |||
s >= NextExp (the packet is in-order). In this case, NextExp is set | (the packet is in-order). In this case, NextExp is set to s+1. | |||
to s+1. | ||||
The Type-P-Non-Reversing-Order of a packet is defined as false if | The value of Type-P-Reordered is defined as true if s < NextExp (the | |||
s < NextExp (the packet is reordered). In this case, NextExp value | packet is reordered). In this case, NextExp value does not change. | |||
does not change. | ||||
Since the Next Expected value cannot decrease, it represents a non- | Packet Reordering Metric for IPPM October 2003 | |||
reversing order that is the basis to identify reordered packets. | ||||
For the alternate sequence dimensions, in-order packets have byte | Since the Next Expected value cannot decrease, it provides a non- | |||
stream numbers or Source times greater than or equal to the value of | reversing order criterion to identify reordered packets. | |||
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 true, in-order */ | if s >= NextExp, /* s is in-order */ | |||
then | then | |||
NextExp = s + PayloadSize + 1; | NextExp = s + 1; | |||
Type-P-Reordered = False; | ||||
else /* when s < NextExp */ | else /* when s < NextExp */ | |||
/* packet s is false, reordered */ | Type-P-Reordered = True | |||
The sequence number s may be replaced by SrcTime or SrcByte. When | We note that when s = NextExp, the original sequence has been | |||
using s (message-based sequence numbering) or Source time, | maintained, and there is no discontinuity present. | |||
PayloadSize=0. | ||||
3.4 Discussion | 3.4 Evaluation in Time or Byte Order | |||
For the alternate sequence dimensions, in-order packets have byte | ||||
stream numbers or Source times greater than or equal to the value of | ||||
NextExp. Each new in-order packet will increase the NextExp SrcTime | ||||
plus 1 clock tick when using Source times, or to SrcByte plus the | ||||
payload size plus 1 for byte numbering. In the pseudo-code above, | ||||
SrcByte (or SrcTime) replaces the sequence number s, and we have: | ||||
if SrcByte >= NextExp, /* packet is in-order */ | ||||
then | ||||
NextExp = SrcByte + PayloadSize + 1; | ||||
When using Source time, PayloadSize=0 (or a fixed time increment, if | ||||
using a reliable periodic packet source). | ||||
3.5 Discussion | ||||
Any arriving packet bearing a sequence number from the sequence that | Any arriving packet bearing a sequence number from the sequence that | |||
establishes the Next Expected value can be evaluated to determine | establishes the Next Expected value can be evaluated to determine | |||
whether it is in-order or reordered, based on a previous packet's | whether it is in-order or reordered, based on a previous packet's | |||
arrival. In the case where Next Expected is Undefined (because the | arrival. In the case where Next Expected is Undefined (because the | |||
arriving packet is the first successful transfer), the packet is | arriving packet is the first successful transfer), the packet is | |||
designated in-order. | designated in-order. | |||
This metric assumes re-assembly of packet fragments before | This metric assumes re-assembly of packet fragments before | |||
evaluation. | evaluation. In principle, it is possible to use the Type-P-Reordered | |||
metric to evaluate reordering among packet fragments, but each | ||||
fragment must contain source sequence information. | ||||
<<<<<<<< Note: Additional considerations will be needed here. | ||||
If duplicate packets (multiple non-corrupt copies) arrive at the | If duplicate packets (multiple non-corrupt copies) arrive at the | |||
destination, they MUST be noted and only the first to arrive is | destination, they MUST be noted and only the first to arrive is | |||
considered for further analysis (copies would be declared reordered | considered for further analysis (copies would be declared reordered | |||
according to the definition above). This requirement has the same | according to the definition above). This requirement has the same | |||
storage requirements as earlier IPPM metrics, and follows the | ||||
Packet Reordering Metric for IPPM October 2003 | ||||
storage implications as earlier IPPM metrics, and follows 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 defined as a reordering discontinuity | sequence discontinuity to be defined as a reordering discontinuity | |||
(see 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 retransmissions are distinguished), and may be | constant (and retransmissions are distinguished), and may be | |||
possible with Periodic Streams and Source Time 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 Source 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 other | |||
sample of packets. This section defines several metrics that | packets. This section defines several metrics that quantify the | |||
quantify the extent of reordering in various units of measure. Each | extent of reordering in various units of measure. Each "extent" | |||
"extent" metric highlights a relevant use. | metric highlights a relevant use. | |||
The metrics in the sub-sections below have a network | The metrics in the sub-sections below have a network | |||
characterization orientation, but also have relevance to receiver | characterization orientation, but also have relevance to receiver | |||
design. | design. | |||
4.1 Reordered Packet Ratio | 4.1 Reordered Packet Ratio | |||
4.1.1 Metric Name: | 4.1.1 Metric Name: | |||
Type-P-Reordered-Ratio-Stream | Type-P-Reordered-Ratio-Stream | |||
4.1.2 Metric Parameters: | 4.1.2 Metric Parameters: | |||
The parameter set includes Type-P-Non-Reversing-Order singleton | The parameter set includes Type-P-Reordered singleton parameters, | |||
parameters, the parameters unique to Poisson or Periodic Streams (as | the parameters unique to Poisson or Periodic Streams (as in RFC 2330 | |||
in RFC 2330 and RFC3432), plus the following: | 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: | |||
Packet Reordering Metric for IPPM October 2003 | ||||
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 Extent | 4.2 Reordering Extent | |||
skipping to change at line 340 | skipping to change at line 374 | |||
Informally, the reordering extent is the maximum distance, in | Informally, the reordering extent is the maximum distance, in | |||
packets, from a reordered packet to the earliest packet received | packets, from a reordered packet to the earliest packet received | |||
that has a larger sequence number. If a packet is in-order, it's | 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- | reordering extent is undefined. The first packet to arrive is in- | |||
order by definition, and has undefined reordering extent. | order by definition, and has undefined reordering extent. | |||
>>>>>>> Comment on this definition of extent: For some arrival | >>>>>>> Comment on this definition of extent: For some arrival | |||
orders, the assignment of a simple position/distance as the | orders, the assignment of a simple position/distance as the | |||
reordering extent tends to overestimate the receiver storage needed | reordering extent tends to overestimate the receiver storage needed | |||
Packet Reordering Metric for IPPM October 2003 | ||||
to restore order. We need to weigh the value of adding more | to restore order. We need to weigh the value of adding more | |||
complexity in this definition against the accuracy it would provide. | complexity in this definition against the accuracy it would provide. | |||
A more accurate and complex procedure to calculate packet storage | A more accurate and complex procedure to calculate packet storage | |||
would be to subtract any earlier reordered packets that the receiver | would be to subtract any earlier reordered packets that the receiver | |||
could pass on to the upper layers. | could pass on to the upper layers. | |||
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. | |||
4.2.4 Discussion: | 4.2.4 Discussion: | |||
skipping to change at line 385 | skipping to change at line 422 | |||
Any reordered packets can be assigned offset values indicating the | Any reordered packets can be assigned offset values indicating the | |||
storage in bytes and lateness in terms of buffer time that a | storage in bytes and lateness in terms of buffer time that a | |||
receiver must possess to accommodate them. The various offset | receiver must possess to accommodate them. The various offset | |||
metrics are calculated only on reordered packets, as identified by | metrics are calculated only on reordered packets, as identified by | |||
the ordered arrival singleton in section 3. | the ordered arrival singleton in section 3. | |||
4.3.1 Metric Name: Type-P-packet-Late-Time-Stream | 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: | Reordered, 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 | |||
received packet i is reordered, and has a reordering extent e, then: | received packet i is reordered, and has a reordering extent e, then: | |||
Packet Reordering Metric for IPPM October 2003 | ||||
LateTime(i) = DstTime(i)-DstTime(i-e) | LateTime(i) = DstTime(i)-DstTime(i-e) | |||
Alternatively, using similar notation to that of section 4.2, an | Alternatively, using similar notation to that of section 4.2, an | |||
equivalent definition is: | equivalent definition is: | |||
LateTime(i) = DstTime(i)-DstTime(j), for min{j|1<=j<i} that | LateTime(i) = DstTime(i)-DstTime(j), for min{j|1<=j<i} that | |||
satisfies s[j]>s[i], or SrcTime[j]>SrcTime[i]. | satisfies s[j]>s[i], or SrcTime[j]>SrcTime[i]. | |||
4.3.2 Metric Name: Type-P-packet-Byte-Offset-Stream | 4.3.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. | |||
skipping to change at line 441 | skipping to change at line 480 | |||
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). | |||
Packet Reordering Metric for IPPM October 2003 | ||||
4.4 Gaps between multiple Reordering Discontinuities | 4.4 Gaps between multiple Reordering Discontinuities | |||
4.4.1 Metric Name: | 4.4.1 Metric Name: | |||
Type-P-packet-Reordering-Gap-Stream | Type-P-packet-Reordering-Gap-Stream | |||
4.4.2 Parameters: | 4.4.2 Parameters: | |||
No new parameters. | No new parameters. | |||
skipping to change at line 474 | skipping to change at line 515 | |||
A reordering gap is the distance between successive reordering | A reordering gap is the distance between successive reordering | |||
discontinuities. Type-P-packet-Reordering-Gap-Stream assigns a value | discontinuities. Type-P-packet-Reordering-Gap-Stream assigns a value | |||
to (all) packets in a stream. | to (all) packets in a stream. | |||
If: | If: | |||
The packet s[j'] is found to be a reordering discontinuity, based | The packet s[j'] is found to be a reordering discontinuity, based | |||
on the arrival of reordered packet s[i'] with extent e', and | on the arrival of reordered packet s[i'] with extent e', and | |||
an earlier reordering discontinuity s[j], based on the arrival of | an earlier reordering discontinuity s[j], based on the arrival of | |||
reordered packet s[i] with extent e is detected, and | reordered packet s[i] with extent e was already detected, and | |||
i' > i, and | i' > i, and | |||
there are no reordering discontinuities between j and j', | there are no reordering discontinuities between j and j', | |||
then the Reordering Gap for packet s[j'] is the difference between | then the Reordering Gap for packet s[j'] is the difference between | |||
the arrival positions the reordering discontinuities, as shown | the arrival positions the reordering discontinuities, as shown | |||
below: | below: | |||
Gap(j') = (j') - (j) | Gap(j') = (j') - (j) | |||
Otherwise: | Otherwise: | |||
The Type-P-packet-Reordering-Gap-Stream for the packet is 0. | The Type-P-packet-Reordering-Gap-Stream for the packet is 0. | |||
Gaps may also be expressed in time: | Gaps may also be expressed in time: | |||
Packet Reordering Metric for IPPM October 2003 | ||||
GapTime(j') = DstTime(j') - DstTime(j) | GapTime(j') = DstTime(j') - DstTime(j) | |||
4.4.5 Discussion | 4.4.5 Discussion | |||
When separate reordering discontinuities can be distinguished, then | When separate reordering discontinuities can be distinguished, then | |||
a count may also be reported (along with the discontinuity | a count may also be reported (along with the discontinuity | |||
description, such as the number of reordered packets associated with | description, such as the number of reordered packets associated with | |||
that discontinuity and their extents and offsets). The Gaps between | that discontinuity and their extents and offsets). The Gaps between | |||
a sample's reordering discontinuities may be expressed as a | a sample's reordering discontinuities may be expressed as a | |||
histogram, to easily summarize the frequency of various gaps. | histogram, to easily summarize the frequency of various gaps. | |||
Reporting the mode, average, range, etc. may also summarize the | Reporting the mode, average, range, etc. may also summarize the | |||
distributions. | distributions. | |||
The Gap metric may help to correlate the frequency of reordering | The Gap metric may help to correlate the frequency of reordering | |||
discontinuities with their cause. | discontinuities with their cause. | |||
4.5 Reordering-free Runs | 4.5 Reordering-free Runs | |||
This section defines a metric based on a count of consecutive in- | This section defines a metric based on a count of consecutive | |||
order packet arrivals. | packets between reordered packets. | |||
4.5.1 Metric Name: | 4.5.1 Metric Name: | |||
Type-P-packet-Reordering-Free-Run-Stream | Type-P-packet-Reordering-Free-Run-Stream | |||
4.5.2 Parameters: | 4.5.2 Parameters: | |||
No new parameters. | No new parameters. | |||
4.5.3 Definition: | 4.5.3 Definition: | |||
As packets in a sample arrive at Dst, the count of packets to the | As packets in a sample arrive at the Destination, the count of | |||
next reordered packet is a Reordering-Free run. Note that the | packets to the next reordered packet is a Reordering-Free run. Note | |||
minimum run-length is one according to this definition. A pseudo | that the minimum run-length is one according to this definition. A | |||
code example follows: | pseudo code example follows: | |||
r = 0; /* r is the run counter */ | r = 0; /* r is the run counter */ | |||
z = 1; /* z is the index for storing different runs */ | n = 0; /* n is the number of runs */ | |||
Run[*]; /* a vector of run-lengths */ | a = 0; /* a is the accumulator of in order packets */ | |||
p = 0; /* p is the number of packets */ | ||||
q = 0; /* q is the squared sum of the run counters */ | ||||
while(packets arrive with sequence number s) | while(packets arrive with sequence number s) | |||
{ | { | |||
P++; | ||||
if (s >= NextExp) /* s is in-order */ | if (s >= NextExp) /* s is in-order */ | |||
then r++; | then r++; | |||
a++; | ||||
else /* s is reordered */ | else /* s is reordered */ | |||
Run[z]=r; | q+= r*r; | |||
r = 1; | r = 1; | |||
z++; | ||||
Packet Reordering Metric for IPPM October 2003 | ||||
n++; | ||||
} | } | |||
4.5.4 Discussion: | 4.5.4 Discussion: | |||
Each arrival of a reordered packet yields a new count in the Run | Each arrival of a reordered packet yields a new count in the Run | |||
vector. Long runs accompany periods where order was maintained, | vector. Long runs accompany periods where order was maintained, | |||
while short runs indicate frequent, or multi-packet reordering. | while short runs indicate frequent, or multi-packet reordering. | |||
5. Metric Related to Receiver Assessment | 5. Metric Related to Receiver Assessment | |||
skipping to change at line 593 | skipping to change at line 642 | |||
probably report it for several values of n, such as 1, 2, 3, 4 -- | probably report it for several values of n, such as 1, 2, 3, 4 -- | |||
and maybe a few more consecutive values). | and maybe a few more consecutive values). | |||
This definition does not assign an n to all reordered packets as | This definition does not assign an n to all reordered packets as | |||
defined by the singleton metric, in particular when blocks of | defined by the singleton metric, in particular when blocks of | |||
successive packets are reordered. (In the arrival sequence | successive packets are reordered. (In the arrival sequence | |||
s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only 4 | s={1,2,3,7,8,9,4,5,6}, packets 4, 5, and 6 are reordered, but only 4 | |||
is n-reordered, with n=3.) | is n-reordered, with n=3.) | |||
Definition 2: The degree of n-reordering of the sample is m/l. | Definition 2: The degree of n-reordering of the sample is m/l. | |||
Packet Reordering Metric for IPPM October 2003 | ||||
Definition 3: The degree of "monotonic reordering" of the sample is | Definition 3: The degree of "monotonic reordering" of the sample is | |||
its degree of 1-reordering. | its degree of 1-reordering. | |||
Definition 4: A sample is said to have no reordering if its degree | Definition 4: A sample is said to have no reordering if its degree | |||
of n-reordering is 0. | of n-reordering is 0. | |||
5.1.4 Discussion: | 5.1.4 Discussion: | |||
The degree of n-reordering may be expressed as a percentage, in | The degree of n-reordering may be expressed as a percentage, in | |||
which case the number from definition 2 is multiplied by 100. | which case the number from definition 2 is multiplied by 100. | |||
skipping to change at line 622 | skipping to change at line 673 | |||
the receiver sees are monotonically increasing with respect to the | the receiver sees are monotonically increasing with respect to the | |||
previous arriving packet. | previous arriving packet. | |||
- For n=3, a NewReno TCP sender would retransmit 1 packet in | - For n=3, a NewReno TCP sender would retransmit 1 packet in | |||
response to an instance of 3-reordering and therefore consider this | response to an instance of 3-reordering and therefore consider this | |||
packet lost for the purposes of congestion control (the sender will | packet lost for the purposes of congestion control (the sender will | |||
half its congestion window). Detecting instances of 3-reordering is | half its congestion window). Detecting instances of 3-reordering is | |||
useful for determining the portion of reordered packets that are in | useful for determining the portion of reordered packets that are in | |||
fact as good as lost. | fact as good as lost. | |||
A sample's n-reordering may be expressed as a histogram, to | ||||
summarize the frequency for each value of n. | ||||
We note that the definition of n-reordering cannot predict the exact | We note that the definition of n-reordering cannot predict the exact | |||
number of packets unnecessarily retransmitted by a TCP sender under | number of packets unnecessarily retransmitted by a TCP sender under | |||
some circumstances, such as cases with closely-spaced reordered | some circumstances, such as cases with closely-spaced reordered | |||
singletons. The definition is less complicated than a TCP | singletons. The definition is less complicated than a TCP | |||
implementation where both time and position influence the sender's | implementation where both time and position influence the sender's | |||
behavior. | behavior. | |||
A sample's n-reordering may be expressed as a histogram, to | A packet's n-reordering is sometimes equal to it's reordering | |||
summarize the frequency for each value of n. | extent, e. n-reordering is different in the following ways: | |||
1. n is a count of *adjacent* early packets. | ||||
2. Some reordered packets may not be n-reordered, but will have e | ||||
(see the examples). | ||||
6. Measurement Issues | 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 | |||
Packet Reordering Metric for IPPM October 2003 | ||||
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 [12]). 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. Of course, packet spacing is likely to vary | packet spacing expected. Of course, packet spacing is likely to vary | |||
as the stream traverses the test path. | as the stream traverses the test path. | |||
<<<<Ed.Note: Is this sufficient? It is a very important | <<<<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 | |||
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 | |||
skipping to change at line 688 | skipping to change at line 750 | |||
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. | |||
Packet Reordering Metric for IPPM October 2003 | ||||
3. Reordered packets coincident with sequence numbers reaching end- | 3. Reordered packets coincident with sequence numbers reaching end- | |||
of-range must also be detected for proper application of correction | of-range must also be detected for proper application of correction | |||
factor. | factor. | |||
In practice, there may be limited ability to determine reordering | In practice, there may be limited ability to determine reordering | |||
extent, because the storage for previous packets may be limited. | extent, because the storage for previous packets may be limited. | |||
Saving only packets that indicate discontinuities (and their arrival | Saving only packets that indicate discontinuities (and their arrival | |||
positions) will reduce storage volume. When discarding all stream | positions) will reduce storage volume. When discarding all stream | |||
information beyond a threshold packet count, the reordering extent | information beyond a threshold packet count, the reordering extent | |||
or degree of n-reordering may need to be expressed as greater than | or degree of n-reordering may need to be expressed as greater than | |||
skipping to change at line 739 | skipping to change at line 803 | |||
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: | |||
Packet Reordering Metric for IPPM October 2003 | ||||
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. | |||
skipping to change at line 791 | skipping to change at line 856 | |||
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 | |||
Packet Reordering Metric for IPPM October 2003 | ||||
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 | |||
skipping to change at line 841 | skipping to change at line 909 | |||
Table 3 Example with Packets 4, 5, and 6 reordered | Table 3 Example with Packets 4, 5, and 6 reordered | |||
Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11 | Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11 | |||
s Src Dst Dst Byte Late | s Src Dst Dst Byte Late | |||
@Dst NextExp Time Time Delay IPDV Order Offset Time | @Dst NextExp Time Time Delay IPDV Order Offset Time | |||
1 1 0 68 68 1 | 1 1 0 68 68 1 | |||
2 2 20 88 68 0 2 | 2 2 20 88 68 0 2 | |||
3 3 40 108 68 0 3 | 3 3 40 108 68 0 3 | |||
7 4 120 188 68 -88 4 | 7 4 120 188 68 -88 4 | |||
8 8 140 208 68 0 5 | 8 8 140 208 68 0 5 | |||
Packet Reordering Metric for IPPM October 2003 | ||||
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 | |||
skipping to change at line 894 | skipping to change at line 964 | |||
a single Packet (4) with a sufficient degree of reordering to result | a single Packet (4) with a sufficient degree of reordering to result | |||
in one unnecessary packet retransmission by the New Reno TCP sender. | in one unnecessary packet retransmission by the New Reno TCP sender. | |||
Also, the reordered arrival of Packets 5 and 6 will allow the | Also, the reordered arrival of Packets 5 and 6 will allow the | |||
receiver process to pass Packets 7 through 10 up the protocol stack | receiver process to pass Packets 7 through 10 up the protocol stack | |||
(the singleton metric indicates 5 and 6 are reordered, and they are | (the singleton metric indicates 5 and 6 are reordered, and they are | |||
all associated with a single reordering discontinuity). | all associated with a single reordering discontinuity). | |||
Table 4 Example with Packets Multiple Reordering Discontinuities | 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 | Sending order(s @Src): 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 | |||
Packet Reordering Metric for IPPM October 2003 | ||||
Discontinuity Discontinuity | Discontinuity Discontinuity | |||
|---------Gap---------| | |---------Gap---------| | |||
s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16 | s = 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 12, 13, 11, 14, 15, 16 | |||
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 | i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 | |||
r = 1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, ... | r = 1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, ... | |||
Run[] counts = 5 1 6 | n = 1 2 3 | |||
end r counts = 5 1 6 | ||||
Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has | Packet 4 has extent e=2, Packet 5 has extent e=3, and Packet 11 has | |||
e=2. There are two different reordering discontinuities at Packet 6 | e=2. There are two different reordering discontinuities, one at | |||
(where j=4) and Packet 12 (where j=11). | Packet 6 (where j=4) and one at Packet 12 (where j'=11). | |||
According to the definition of Reordering Gap | According to the definition of Reordering Gap | |||
Gap(j') = (j') - (j) | Gap(j') = (j') - (j) | |||
Gap(11) = (11) - (4) = 7 | Gap(11) = (11) - (4) = 7 | |||
We also have three reordering-free runs of lengths 5, 1, and 6. | We also have three reordering-free runs of lengths 5, 1, and 6. | |||
The differences between these two multiple-event metrics are evident | The differences between these two multiple-event metrics are evident | |||
here. Gaps are the distance between sequence discontinuities that | here. Gaps are the distance between sequence discontinuities that | |||
are subsequently defined as reordering discontinuities, while | are subsequently defined as reordering discontinuities, while | |||
skipping to change at line 943 | skipping to change at line 1016 | |||
8.2 User data confidentiality | 8.2 User data confidentiality | |||
Active use of this method generates packets for a sample, rather | Active use of this method generates packets for a sample, rather | |||
than taking samples based on user data, and does not threaten user | than taking samples based on user data, and does not threaten user | |||
data confidentiality. Passive measurement must restrict attention to | data confidentiality. Passive measurement must restrict attention to | |||
the headers of interest. Since user payloads may be temporarily | the headers of interest. Since user payloads may be temporarily | |||
stored for length analysis, suitable precautions MUST be taken to | stored for length analysis, suitable precautions MUST be taken to | |||
keep this information safe and confidential. | keep this information safe and confidential. | |||
Packet Reordering Metric for IPPM October 2003 | ||||
8.3 Interference with the metric | 8.3 Interference with the metric | |||
It may be possible to identify that a certain packet or stream of | It may be possible to identify that a certain packet or stream of | |||
packets is part of a sample. With that knowledge at Dst and/or the | packets is part of a sample. With that knowledge at 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. | |||
skipping to change at line 994 | skipping to change at line 1069 | |||
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. | |||
Packet Reordering Metric for IPPM October 2003 | ||||
9 J.Bellardo and S.Savage, "Measuring Packet Reordering," | 9 J.Bellardo and S.Savage, "Measuring Packet Reordering," | |||
Proceedings of the ACM SIGCOMM Internet Measurement Workshop | Proceedings of the ACM SIGCOMM Internet Measurement Workshop | |||
2002, November 6-8, Marseille, France. | 2002, November 6-8, Marseille, France. | |||
10 S.Jaiswal et al., "Measurement and Classification of Out-of- | 10 S.Jaiswal et al., "Measurement and Classification of Out-of- | |||
Sequence Packets in a Tier-1 IP Backbone," Proceedings of the ACM | Sequence Packets in a Tier-1 IP Backbone," Proceedings of the ACM | |||
SIGCOMM Internet Measurement Workshop 2002, November 6-8, | SIGCOMM Internet Measurement Workshop 2002, November 6-8, | |||
Marseille, France. | Marseille, France. | |||
11 Demichelis, C., and Chimento, P., "IP Packet Delay Variation | 11 Demichelis, C., and Chimento, P., "IP Packet Delay Variation | |||
skipping to change at line 1045 | skipping to change at line 1122 | |||
* the sequence numbers come from stdin; in an actual test, they | * the sequence numbers come from stdin; in an actual test, they | |||
would come | would come | |||
* from the network. | * from the network. | |||
*/ | */ | |||
int | int | |||
read_sequence_number() | read_sequence_number() | |||
{ | { | |||
int res, rc; | int res, rc; | |||
rc = scanf("%d\n", &res); | rc = scanf("%d\n", &res); | |||
if (rc == 1) return res; | if (rc == 1) return res; | |||
Packet Reordering Metric for IPPM October 2003 | ||||
else return EOF; | else return EOF; | |||
} | } | |||
int | int | |||
main() | main() | |||
{ | { | |||
int m[MAX_N]; /* We have m[j-1] == number | int m[MAX_N]; /* We have m[j-1] == number | |||
of | of | |||
* j-reordered packets. */ | * j-reordered packets. */ | |||
int ring[MAX_N]; /* Last sequence numbers | int ring[MAX_N]; /* Last sequence numbers | |||
skipping to change at line 1095 | skipping to change at line 1175 | |||
#define min(a, b) ((a) < (b)? (a): (b)) | #define min(a, b) ((a) < (b)? (a): (b)) | |||
#define loop(x) ((x) >= 0? x: x + MAX_N) | #define loop(x) ((x) >= 0? x: x + MAX_N) | |||
/* Global counters */ | /* Global counters */ | |||
int receive_packets=0; /* number of recieved */ | int receive_packets=0; /* number of recieved */ | |||
int reorder_packets=0; /* number of reordered packets */ | int reorder_packets=0; /* number of reordered packets */ | |||
/* function to test if current packet has been reordered | /* function to test if current packet has been reordered | |||
* returns 0 = not reordered | * returns 0 = not reordered | |||
* 1 = reordered | * 1 = reordered | |||
Packet Reordering Metric for IPPM October 2003 | ||||
*/ | */ | |||
int testorder1(int seqnum) // Al | int testorder1(int seqnum) // Al | |||
{ | { | |||
static int NextExp = 1; | static int NextExp = 1; | |||
int iReturn = 0; | int iReturn = 0; | |||
if (seqnum >= NextExp) { | if (seqnum >= NextExp) { | |||
NextExp = seqnum+1; | NextExp = seqnum+1; | |||
} else { | } else { | |||
iReturn = 1; | iReturn = 1; | |||
skipping to change at line 1147 | skipping to change at line 1230 | |||
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 | |||
Packet Reordering Metric for IPPM October 2003 | ||||
Middletown, NJ 07748 USA | Middletown, NJ 07748 USA | |||
Phone +1 732 420 1571 | 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 | |||
skipping to change at line 1196 | skipping to change at line 1283 | |||
and distributed, in whole or in part, without restriction of any | and distributed, in whole or in part, without restriction of any | |||
kind, provided that the above copyright notice and this paragraph | kind, provided that the above copyright notice and this paragraph | |||
are included on all such copies and derivative works. However, this | are included on all such copies and derivative works. However, this | |||
document itself may not be modified in any way, such as by removing | document itself may not be modified in any way, such as by removing | |||
the copyright notice or references to the Internet Society or other | the copyright notice or references to the Internet Society or other | |||
Internet organizations, except as needed for the purpose of | Internet organizations, except as needed for the purpose of | |||
developing Internet standards in which case the procedures for | developing Internet standards in which case the procedures for | |||
copyrights defined in the Internet Standards process must be | copyrights defined in the Internet Standards process must be | |||
followed, or as required to translate it into languages other than | followed, or as required to translate it into languages other than | |||
English. | English. | |||
Packet Reordering Metric for IPPM October 2003 | ||||
The limited permissions granted above are perpetual and will not be | The limited permissions granted above are perpetual and will not be | |||
revoked by the Internet Society or its successors or assigns. | revoked by the Internet Society or its successors or assigns. | |||
This document and the information contained herein is provided on an | This document and the information contained herein is provided on an | |||
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING | "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING | |||
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING | TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING | |||
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION | BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION | |||
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF | HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF | |||
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. | |||
End of changes. | ||||
This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/ |