draft-ietf-ippm-reordering-00.txt   draft-ietf-ippm-reordering-01.txt 
IP Performance Metrics Working Group A.Morton IP Performance Metrics Working Group A.Morton
Internet Draft L.Ciavattone Internet Draft L.Ciavattone
Document: <draft-ietf-ippm-reordering-00.txt> G.Ramachandran Document: <draft-ietf-ippm-reordering-01.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
Reordering Metric for IPPM Packet Reordering Metric for IPPM
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026 [1]. all provisions of Section 10 of RFC2026 [1].
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Internet-Drafts are draft documents valid for a maximum of Drafts. Internet-Drafts are draft documents valid for a maximum of
skipping to change at line 65 skipping to change at line 65
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 the sending time of each packet
or an incrementing message number carried in each packet establishes or an incrementing message number carried in each packet establishes
the Source Sequence. the 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 classifies arriving packets with sequence numbers This metric is consistent with RFC 2330 [3], and classifies arriving
smaller than their predecessors as out-of-order, or reordered. For packets with sequence numbers smaller than their predecessors as
example, if arriving packets are numbered 1,2,4,5,3, then packet 3 out-of-order, or reordered. For example, if arriving packets are
is reordered. This is equivalent to Paxon's reordering definition in numbered 1,2,4,5,3, then packet 3 is reordered. This is equivalent
[3], where "late" packets were declared reordered. The alternative to Paxon's reordering definition in [4], where "late" packets were
is to emphasize "premature" packets instead (4 and 5 in the declared reordered. The alternative is to emphasize "premature"
example). The metric's construction is very similar to the sequence packets instead (4 and 5 in the example). The metric's construction
space validation for received segments in RFC793 [4]. Earlier work is very similar to the sequence space validation for received
to define ordered delivery includes [5], and more ???. segments in RFC793 [5]. Earlier work to define ordered delivery
includes [6], [7] and more ???.
3.1 Motivation 3.1 Motivation
A reordering metric is relevant for most applications, especially A reordering metric is relevant for most applications, especially
when assessing network support for Real-Time media streams. The when assessing network support for Real-Time media streams. The
extent of reordering may be sufficient to cause a received packet to extent of reordering may be sufficient to cause a received packet to
be discarded by functions above the IP layer. be discarded by functions above the IP layer.
Packet order is not expected to change during transfer, but several Packet order is not expected to change during transfer, but several
specific path characteristics can cause their order to change. specific path characteristics can cause their order to change.
skipping to change at line 136 skipping to change at line 137
+ 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 4. 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 an incrementing sequence number applied to packets at The first is a sequence number applied to packets at the source to
the source (decrementing sequences can be accommodated, and sequence uniquely identify the order of packet transmission. The sequence
roll-over is treated later). The source order may established by a number may be established by a simple message number, a byte stream
simple message number, a byte stream number, or it may be the actual number, or it may be the actual time when each packet departs from
time when each packet departs from the Src. the Src.
The second supporting concept is a stored value which is the "next The second supporting concept is a stored value which is the "next
expected" packet number. Under normal conditions, the value of Next expected" packet number. Under normal conditions, the value of Next
Expected (NextExp) is the sequence number of the previous packet Expected (NextExp) is the sequence number of the previous packet
(plus 1 for message numbering). In byte stream numbering, NextExp (plus 1 for message numbering). In byte stream numbering, NextExp
is a value 1 byte greater than the last in-order packet sequence is a value 1 byte greater than the last in-order packet sequence
number + payload. If Src time is used as the sequence number, number + payload. If 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.
skipping to change at line 164 skipping to change at line 165
4.1 Metric Name: 4.1 Metric Name:
Type-P-Non-Reversing-Order Type-P-Non-Reversing-Order
4.2 Metric Parameters: 4.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 + SrcTime, the time of packet emission from the Src (or wire time)
+ SrcNum, the packet sequence number applied at the Src, in units + SrcNum, the packet sequence number applied at the Src, in units
of messages or bytes. of messages or 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 SrcNum sequence is based on byte
transfer. transfer.
skipping to change at line 214 skipping to change at line 214
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 5. Sample Metrics
It is highly desirable to assert the degree to which a packet is It is highly desirable to assert the degree to which a packet is
out-of-order with respect to a sample of packets. This section out-of-order, or reordered with respect to a sample of packets. This
defines several metrics that quantify the extent of reordering in section defines several metrics that quantify the extent of
various units of measure. Each metric highlights a relevant reordering in various units of measure. Each metric highlights a
application. relevant application.
5.1 N-Reordering 5.1 n-Reordering
[Note: This is a modified definition of N-Reordering.] [Note: This is the 10/2002 definition of n-Reordering. This
definition focuses on TCP sender and receiver behavior, and in
particular, New Reno TCP behavior when n=3.]
Metric Name: Type-P-packet-N-reordering-Poisson/Periodic-Stream Metric Name: Type-P-packet-n-reordering-Poisson/Periodic-Stream
Parameter Notation: Let N be a positive integer (a parameter). Let Parameter Notation: Let n be a positive integer (a parameter). Let
K be a positive integer (sample size, the number of packets sent). k be a positive integer (sample size, the number of packets sent).
Let L be a non-negative integer representing the number of packets Let l be a non-negative integer representing the number of packets
that were received out of the K packets sent. Assign each sent that were received out of the k packets sent. (Note that there is
packet a sequence number, 1 to K. Let <S_1, ..., S_L> be the no relationship between k and l: on one hand, losses can make l less
original sequence numbers of the received packets, in the order of than k; on the other hand, duplicates can make l greater than k.)
arrival (duplicates are possible). 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 Definition 1: Received packet number i (n < i <= l) is called n-
N-reordered IFF for all J such that I-N <= J < I we have S_J > S_I. reordered if and only if for all j such that i-n <= j < i we have
s[j] > s[i].
Let M be the number of N-reordered packets in the sample. Note: This definition is illustrated by C code in Appendix A. It
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).
Definition 2: The degree of N-reordering of the sample is M/(K-N). Claim: If a packet is n-reordered and 0 < n' < n, then the packet is
also n'-reordered.
Let m be the number of n-reordered packets in the sample.
Definition 2: The degree of n-reordering of the sample is m/(l-n).
Definition 3: The degree of reordering of the sample is its degree Definition 3: The degree of reordering of the sample is its degree
of 1-reordering. 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
on "proportion of reordered packets in the sample".
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 reordering is 0. of reordering is 0.
Discussion: 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.
N-reordering is particularly useful for determining the portion of For a given sample, the number of n-reordered packets is the number
of packets that would be considered as good as lost by a receiver
that uses a buffer of n packets to correct reordering.
Important special cases are n=1 and n=3:
- For n=1, absence of 1-reordering means the sequence numbers that
the receiver sees are monotonically increasing with respect to the
previous arriving packet.
- For n=3, a NewReno TCP sender would retransmit 3-reordered packets
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
reordered packets which can or cannot be restored to order in a reordered packets which can or cannot be restored to order in a
typical TCP receiver buffer based on their arrival order alone (and typical TCP receiver buffer based on their arrival order alone (and
without the aid of retransmission). without the aid of retransmission).
[need more on this].
5.2 Reordering Offset 5.2 Reordering Offset
Any packet whose sequence number causes the Next Expected value to Any packet whose sequence number causes the Next Expected value to
increment by more than the usual increment indicates a discontinuity increment by more than the usual increment indicates a discontinuity
in the sequence. From this point on, any packets with sequence in the sequence. From this point on, any packets with sequence
number less than the Next Expected value can be assigned Offset number less than the Next Expected value can be assigned Offset
values indicating their position (in packets or bytes) and lateness values indicating their position (in packets or bytes) and lateness
in terms of time of arrival with respect to a sequence in terms of time of arrival with respect to a sequence
discontinuity. The various Offset metrics are calculated only on discontinuity. The various Offset metrics are calculated only on
reordered packets, as defined in section 4. reordered packets, as defined in section 4.
skipping to change at line 288 skipping to change at line 325
Definition: Reordered packets are associated with a specific Definition: Reordered packets are associated with a specific
sequence discontinuity by determining which earlier packet's sequence discontinuity by determining which earlier packet's
sequence number skipped over them. We calculate all expressions of sequence number skipped over them. We calculate all expressions of
Offset with respect to that packet. Position Offset is calculated Offset with respect to that packet. Position Offset is calculated
from a Dst Order number assigned to each packet on arrival: from a Dst Order number assigned to each packet on arrival:
Position Offset = Position Offset =
DstOrder(reordered packet)-DstOrder(packet at discontinuity) DstOrder(reordered packet)-DstOrder(packet at discontinuity)
Using the notation of Section 5.1, an equivalent definition is: Using the notation of Section 5.1, an equivalent definition is:
The Position Offset of Reordered Packet I is M = I-J, for The Position Offset of Reordered Packet i is m = i-j, for
min{J|1<=J<I} that satisfies S_J > S_I. min{j|1<=j<i} that satisfies s[j]> s[i].
A sample's position offset may be expressed as a histogram, to
easily summarize the extent and frequency of various offsets.
5.2.2 Metric Name: Type-P-packet-Late-Time-Poisson/Periodic-Stream 5.2.2 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.
Late Time = Late Time =
DstTime(reordered packet)-DstTime(packet at discontinuity) DstTime(reordered packet)-DstTime(packet at discontinuity)
Using similar notation to that of Section 5.1, an equivalent Using similar notation to that of Section 5.1, an equivalent
definition is: definition is:
The Late Time of Reordered Packet I is T = DstTime_I-DstTime_J, The Late Time of Reordered Packet i is t = DstTime[i]-DstTime[j],
for min{J|1<=J<I} that satisfies S_J > S_I, or SrcTime_J>SrcTime_I. for min{j|1<=j<i} that satisfies s[j]>s[i], or
SrcTime[j]>SrcTime[i].
5.2.3 Metric Name: Type-P-packet-Byte-Offset-Poisson/Periodic-Stream 5.2.3 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 can be determined from the payload Definition: Byte stream offset is the sum of the payload sizes of
sizes of intervening packets. all intervening packets between the reordered packet and the
discontinuity (including the packet at the discontinuity).
Byte Offset = When reordered packet has DstOrder=m
PayloadNum(reordered packet, DstOrder=m) Byte Offset = Sum[PayloadSize(packet, DstOrder=m-1),
- Sum[PayloadSize(packet, DstOrder=m-1),
PayloadSize(packet, DstOrder=m-2), ... PayloadSize(packet, DstOrder=m-2), ...
PayloadSize(packet at discontinuity)] PayloadSize(packet at discontinuity)]
5.2.4 Discussion 5.2.4 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, limited receiver buffer system. The limit may useful in a general, but limited receiver buffer system. The limit
be the number of bytes or packets the buffer can store, or the time may be the number of bytes or packets the buffer can store, or the
of storage prior to a cyclic play-out instant (as with de-jitter time of storage prior to a cyclic play-out instant (as with de-
buffers). jitter buffers).
Note that the One-way IPDV [6] gives the delay variation for a Note that the One-way IPDV [8] 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 more buffer delay to accommodate similar events in the future - with additional buffer delay to accommodate similar events in the
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 For a sample of packets in a stream, results may be reported as a
ratio of reordered packets to total packets sent by the source ratio of reordered packets to total packets sent by the source
during the test. If separate reordering events can be distinguished, during the test. If separate reordering events can be distinguished,
then an event count may also be reported (along with the event then an event count may also be reported (along with the event
description, such as the number of reordered packets and their description, such as the number of reordered packets and their
offsets). The distribution of various Offset metrics may also be offsets). The distribution of various Offset metrics may also be
reported and summarized as average, range, etc. reported and summarized as average, range, etc.
6. Measurement Issues 6. Measurement Issues
The results of sequence tests will be dependent on the time interval The results of tests will be dependent on the time interval between
between measurement packets (both at the Src, and during transport measurement packets (both at the Src, and during transport where
where spacing may change). Clearly, packets launched infrequently spacing may change). Clearly, packets launched infrequently (e.g.,
(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
known temporal bias is maintained, also bringing simplified results
analysis [Ref to npmps]. In this case, the periodic sending interval
should be chosen to reproduce the closest Src packet spacing
expected.
<<<<Ed.Note: Need to expand this further, it is a very important
consideration.
The Non-reversing order criterion remains valid and useful when a The Non-reversing order criterion remains valid and useful when a
stream of packets experiences packet loss, or both loss and stream of packets experiences packet loss, or both loss and
reordering. In other words, losses alone do not cause subsequent reordering. In other words, losses alone do not cause subsequent
packets to be declared reordered. 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
skipping to change at line 457 skipping to change at line 506
reordered. Further, we can compute the Offset of packet 4 in terms reordered. Further, we can compute the Offset of packet 4 in terms
of position (8-4=4 using DstOrder) and Late Time (210-148=62ms using 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 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, 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 packet 4 may be useful. Note that 1-way delay and IPDV also indicate
unusual behavior for packet 4. unusual behavior for packet 4.
If all packets contained 100 byte payloads, then Byte Offset is If all packets contained 100 byte payloads, then Byte Offset is
equal to 500 bytes. equal to 500 bytes.
In the notation of N-reordering, <S_1, ..., S_I, ..., S_L> the In the notation of n-reordering, <s[1], ..., s[i], ..., s[l]> the
received packets are represented as: received packets are represented as:
1_1, 2_2, 3_3, 5_4, 6_5, 7_6, 8_7, 4_8, 9_9, 10_10 \/
s = 1, 2, 3, 5, 6, 7, 8, 4, 9, 10
when N=1, 7<=J<8, and 8_7 > 4_8, so packet I=8 is 1-reordered. i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
/\
when N=2, 6<=J<8, and 7_6 > 4_8, so packet I=8 is 2-reordered. when n=1, 7<=J<8, and 8 > 4, so the packet at i=8 is 1-reordered.
when N=3, 5<=J<8, and 6_5 > 4_8, so packet I=8 is 3-reordered. when n=2, 6<=J<8, and 7 > 4, so the packet at i=8 is 2-reordered.
when N=4, 4<=J<8, and 5_4 > 4_8, so packet I=8 is 4-reordered. when n=3, 5<=J<8, and 6 > 4, so the packet at i=8 is 3-reordered.
when n=4, 4<=J<8, and 5 > 4, so the packet at i=8 is 4-reordered.
when n=5, 3<=J<8, but 3 < 4, no more reordering.
We note that the Position Offset is equal to the Max(N) with N- We note that the Position Offset is equal to the Max(n) with n-
reordering. reordering.
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(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10
SrcNum Src Dst Dst Posit. Late SrcNum Src Dst Dst Posit. 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 1 1
6 8 100 190 90 -19 7 2 2 6 8 100 190 90 -19 7 2 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
[ Remaining examples need to have N-reordering added ]
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 declared out-of-order. Their positional
offsets (6-5=1 and 7-5=2, using DstOrder again) and Late times (189- offsets (6-5=1 and 7-5=2, using DstOrder again) and Late times (189-
188=1, 190-188=2) are small. 188=1, 190-188=2) are small.
In the notation of n-reordering, the received packets are
represented as:
\/ \/
s = 1, 2, 3, 4, 7, 5, 6, 8, 9, 10
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
/\ /\
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=2, 4<=J<6, but 4 < 5, same for all earlier packets.
Considering packet 6[7] next:
when n=1, 6<=J<7, and 5 < 6, so the packet at I=7 is not n-reordered
for any n, even though:
when N=2, 5<=J<7, and 7 > 6,
because n-reordering requires s[j]>s[i]
for all j such that i-n <= j < i (see Definition 1 in section 5.1).
A hypothetical sender/receiver pair may retransmit packet 5[8]
unnecessarily, since it is 1-reordered (in agreement with the
singleton metric). However, the receiver cannot advance packet 7[5]
to the higher layers until after packet 6[7] arrives. Therefore, the
singleton metric correctly determined that 6[7] is reordered, and
the n-reordering metric indicates that the hypothetical receiver can
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(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10,11
SrcNum Src Dst Dst Posit. Late SrcNum Src Dst Dst Posit. 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 4 62
5 11 80 252 172 -18 9 5 64 5 11 80 252 172 -18 9 5 64
6 11 100 256 156 -16 10 6 68 6 11 100 256 156 -16 10 6 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. Delay, Late time, and Offset capture this very well, transit times (packets with SrcNum 4,5,and 6). Delay, Late time, and
and indicate variation in reordering extent, while IPDV indicates Position Offset capture this very well, and indicate variation in
that the spacing between packets 4,5,and 6 has changed. reordering extent, while IPDV indicates that the spacing between
packets 4,5,and 6 has changed.
The histogram of Position Offsets would be:
Bin 1 2 3 4 5 6 7
Frequency 0 0 0 1 1 1 0
In the notation of n-reordering, the received packets are
represented as:
s = 1, 2, 3, 7, 8, 9,10, 4, 5, 6, 11
i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11
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=2, 6<=J<8, and 9 > 4, so the packet at i=8 is 2-reordered.
when n=3, 5<=J<8, and 8 > 4, so the packet at i=8 is 3-reordered.
when n=4, 4<=J<8, and 7 > 4, so the packet at i=8 is 4-reordered.
when n=5, 3<=J<8, but 3 < 4, same for all earlier packets.
Considering packet 5[9] next:
when n=1, 8<=J<9, and 4 < 5, so the packet at I=9 is not n-reordered
This example shows again that the n-reordering definition identifies
a single packet (SrcNum=4) with a sufficient degree of reordering to
result in one unnecessary packet retransmission by the New Reno TCP
sender. Also, the delayed arrival of SrcNum=5 and SrcNum=6 will
allow the receiver process to pass Src packets 7 through 10 up the
protocol stack (the singleton metric indicates 5 and 6 are
reordered).
8. Security Considerations [mostly borrowed from npmps] 8. Security Considerations [mostly borrowed from npmps]
8.1 Denial of Service Attacks 8.1 Denial of Service Attacks
This metric requires a stream of packets sent from one host (Src) to This metric requires a stream of packets sent from one host (Src) to
another host (Dst) through intervening networks. This method could another host (Dst) through intervening networks. This method could
be abused for denial of service attacks directed at Dst and/or the be abused for denial of service attacks directed at Dst and/or the
intervening network(s). intervening network(s).
skipping to change at line 566 skipping to change at line 671
there are no IANA considerations in this memo. there are no IANA considerations in this memo.
10. References 10. References
1 Bradner, S., "The Internet Standards Process -- Revision 3", BCP 1 Bradner, S., "The Internet Standards Process -- Revision 3", BCP
9, RFC 2026, October 1996. 9, RFC 2026, October 1996.
2 Bradner, S., "Key words for use in RFCs to Indicate Requirement 2 Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", RFC 2119, March 1997. Levels", RFC 2119, March 1997.
3 V.Paxson, "Measurements and Analysis of End-to-End Internet 3 Paxson, V., Almes, G., Mahdavi, J., and Mathis, M., "Framework
for IP Performance Metrics", RFC 2330, May 1998.
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.
4 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
5 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
6 Demichelis, C., and Chimento, P., "IP Packet Delay Variation 7 J.C.R.Bennett, C.Partridge, and N.Shectman, "Packet Reordering is
Not Pathological Network Behavior," IEEE/ACM Transactions on
Neteworking, vol.7, no.6, pp.789-798, December 1999.
8 Demichelis, C., and Chimento, P., "IP Packet Delay Variation
Metric for IPPM", work in progress. Metric for IPPM", work in progress.
11. Acknowledgments 11. Acknowledgments
The authors would like to acknowledge the helpful discussions with The authors would like to acknowledge the helpful discussions with
Matt Mathis, and . We gratefully acknowledge the foundation laid by Matt Mathis and Jon Bennett. We gratefully acknowledge the
the authors of the IP performance Framework [3]. foundation laid by the authors of the IP performance Framework [3].
11. Author's Addresses 12. Appendix A (informative)
Two example c-code implementations of reordering definitions follow:
Example 1 n-reordering ============================================
#include <stdio.h>
#define MAX_N 100
#define min(a, b) ((a) < (b)? (a): (b))
#define loop(x) ((x) >= 0? x: x + MAX_N)
/*
* Read new sequence number and return it. Return a sentinel value
of EOF
* (at least once) when there are no more sequence numbers. In this
example,
* the sequence numbers come from stdin; in an actual test, they
would come
* from the network.
*/
int
read_sequence_number()
{
int res, rc;
rc = scanf("%d\n", &res);
if (rc == 1) return res;
else return EOF;
}
int
main()
{
int m[MAX_N]; /* We have m[j-1] == number
of
* j-reordered packets. */
int ring[MAX_N]; /* Last sequence numbers
seen. */
int r = 0; /* Ring pointer for next
write. */
int l = 0; /* Number of sequence
numbers read. */
int s; /* Last sequence number
read. */
int j;
for (j = 0; j < MAX_N; j++) m[j] = 0;
for (; (s = read_sequence_number()) != EOF; l++, r = (r+1) %
MAX_N) {
for (j=0; j<min(l, MAX_N) && s<ring[loop(r-j-1)];
j++) m[j]++;
ring[r] = s;
}
for (j = 0; j < MAX_N && m[j]; j++)
printf("%d-reordering = %f%%\n", j+1, 100.0*m[j]/(l-
j-1));
if (j == 0) printf("no reordering\n");
else if (j < MAX_N) printf("no %d-reordering\n", j+1);
else printf("only up to %d-reordering is handled\n", MAX_N);
exit(0);
}
Example 2 singleton and n-reordering comparison =================
#include <stdio.h>
#define MAX_N 100
#define min(a, b) ((a) < (b)? (a): (b))
#define loop(x) ((x) >= 0? x: x + MAX_N)
/* Global counters */
int receive_packets=0; /* number of recieved */
int reorder_packets=0; /* number of reordered packets */
/* function to test if current packet has been reordered
* returns 0 = not reordered
* 1 = reordered
*/
int testorder1(int seqnum) // Al
{
static int NextExp = 1;
int iReturn = 0;
if (seqnum >= NextExp) {
NextExp = seqnum+1;
} else {
iReturn = 1;
}
return iReturn;
}
int testorder2(int seqnum) // Stanislav
{
static int ring[MAX_N]; /* Last sequence numbers
seen. */
static int r = 0; /* Ring pointer for next write.
*/
int l = 0; /* Number of sequence
numbers read. */
int j;
int iReturn = 0;
l++;
r = (r+1) % MAX_N;
for (j=0; j<min(l, MAX_N) && seqnum<ring[loop(r-j-1)]; j++)
iReturn = 1;
ring[r] = seqnum;
return iReturn;
}
int main(int argc, char *argv[])
{
int i, packet;
for (i=1; i< argc; i++) {
receive_packets++;
packet = atoi(argv[i]);
reorder_packets += testorder2(packet);
}
printf("Received packets = %d, Reordered packets = %d\n",
receive_packets, reorder_packets);
exit(0);
}
13. Author's Addresses
Al Morton Al Morton
AT&T Labs AT&T Labs
Room D3 - 3C06 Room D3 - 3C06
200 Laurel Ave. South 200 Laurel Ave. South
Middletown, NJ 07748 USA Middletown, NJ 07748 USA
Phone +1 732 420 1571 Fax +1 732 368 1192 Phone +1 732 420 1571 Fax +1 732 368 1192
<acmorton@att.com> <acmorton@att.com>
Len Ciavattone Len Ciavattone
skipping to change at line 614 skipping to change at line 848
Gomathi Ramachandran Gomathi Ramachandran
AT&T Labs AT&T Labs
Room C4 - 3D22 Room C4 - 3D22
200 Laurel Ave. South 200 Laurel Ave. South
Middletown, NJ 07748 USA Middletown, NJ 07748 USA
Phone +1 732 420 2353 Phone +1 732 420 2353
<gomathi@att.com> <gomathi@att.com>
Stanislav Shalunov Stanislav Shalunov
University Corporation for Advanced Internet Development Internet2
200 Business Park Drive, Suite 307 200 Business Park Drive, Suite 307
Armonk, NY 10504 Armonk, NY 10504
Phone: + 1 914 765 1182 Phone: + 1 914 765 1182
EMail: <shalunov@internet2.edu> EMail: <shalunov@internet2.edu>
Jerry Perser Jerry Perser
Spirent Communications Spirent Communications
26750 Agoura Road 26750 Agoura Road
Calabasas, CA 91302 USA Calabasas, CA 91302 USA
Phone: + 1 818 676 2300 Phone: + 1 818 676 2300
 End of changes. 

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