Internet Engineering Task Force Anura P. Jayasumana
INTERNET-DRAFT Nischal M. Piratla
draft-jayasumana-reorder-density-03.txt Abhijit A. Bare
Tarun Banka
Colorado State University
Rick Whitner
Jerry McCollom
Agilent Technologies
July 2004
Expires: January 2005
Reorder Density and Reorder Buffer-occupancy Density - Metrics for
Packet Reordering Measurements
Status of this memo
By submitting this Internet-Draft, we certify that any applicable
patent or other IPR claims of which we are aware have been disclosed,
and any of which we become aware will be disclosed, in accordance
with RFC 3668.
This document may not be modified, and derivative works of it may not
be created, except to publish it as an RFC and to translate it into
languages other than English.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or made obsolete by other documents at
any time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/1id-abstracts.html.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Copyright Notice
Copyright (C), 2004, The Internet Society. All Rights Reserved.
Abstract
Out of order arrival of packets is a common occurrence on Internet,
and it will be more widespread as the link speeds increase.
Percentage packet reordering is vague and unclear. A good reorder
metric will capture the occurrence and characteristics of reordering
Anura Jayasumana [Page 1]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
comprehensively, and have broader utility than merely distinguishing
among different reordered sequences. Two metrics for packet
reordering are presented, namely, Reorder Density (RD) and Reorder
Buffer-occupancy Density (RBD). A threshold is used to clearly define
when a packet is considered lost, to upper bound computational
complexity at O(N), and to keep the memory requirement for evaluation
independent of N, where N is the length of the packet sequence. RD is
a comprehensive metric that captures the characteristics of
reordering, while RBD evaluates the sequences from the point of view
of recovery from reordering. These metrics are simple to compute yet
comprehensive in their characterization of packet reordering. The
measures are robust, and orthogonal to packet loss and duplication.
Table of Contents
1. Introduction and Motivation . . . . . . . . . . . . . . . . . 3
2. Definitions of the terms used . . . . . . . . . . . . . . . . 5
2.1 Receive_index (RI) . . . . . . . . . . . . . . . . . . . . 5
2.2 Out-of-order Packet . . . . . . . . . . . . . . . . . . . . 6
2.3 Early-packet and Late-packet . . . . . . . . . . . . . . . 6
2.4 Displacement (D) . . . . . . . . . . . . . . . . . . . . . 6
2.5 Displacement Threshold (DT) . . . . . . . . . . . . . . . . 7
2.6 Lateness/Earliness Frequency (FLE) . . . . . . . . . . . . 7
2.7 Reorder Density (RD) . . . . . . . . . . . . . . . . . . . 7
2.8 Expected Packet (E) . . . . . . . . . . . . . . . . . . . . 7
2.9 Buffer Occupancy (B) . . . . . . . . . . . . . . . . . . . 8
2.10 Buffer Occupancy Threshold (BT) . . . . . . . . . . . . . . 8
2.11 Buffer Occupancy Frequency (FB) . . . . . . . . . . . . . . 8
2.12 Reorder Buffer-occupancy Density (RBD) . . . . . . . . . . 8
3. Representation of packet reordering and Reorder Density . . . 8
4. Selection of DT . . . . . . . . . . . . . . . . . . . . . . . 9
5. Detection of Lost and Duplicate Packets . . . . . . . . . . . 10
6. Algorithms to compute RD and RBD . . . . . . . . . . . . . . . 10
5.1 RD Algorithm . . . . . . . . . . . . . . . . . . . . . . . 11
5.2 RBD Algorithm . . . . . . . . . . . . . . . . . . . . . . . 12
7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8. Comparison with Other Metrics . . . . . . . . . . . . . . . . 18
9. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
10. Security Considerations . . . . . . . . . . . . . . . . . . . 20
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
12. Normative References . . . . . . . . . . . . . . . . . . . . . 20
13. Author's Address . . . . . . . . . . . . . . . . . . . . . . . 21
14. Revision History . . . . . . . . . . . . . . . . . . . . . . . 22
Full Copyright Statement . . . . . . . . . . . . . . . . . . . . . 22
Intellectual Property . . . . . . . . . . . . . . . . . . . . . . 22
Appendix A . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Appendix B . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Anura Jayasumana [Page 2]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
1. Introduction and Motivation
The increase in link speeds, increased parallelism within routers and
switches, QoS support and load balancing among links, all point to
future networks with increased packet reordering. Major causes for
reordering of packets include but are not limited to packet stripping
at layers 2 and 3 [1,2], priority scheduling (ex.diffserv), and route
fluttering [3,4,5]. Reordering leads to degradation of the
performance of many applications [1,6,7]. For example, perceived
quality of voice degrades if a VoIP application receives packets
out-of-order. Once the reordering in arriving packet streams is
measured and/or quantified, it may be possible to predict the effects
of reordering on applications that are sensitive to reordering, and
perhaps even compensate for reordering. A metric for reordered
packets may also help evaluate network protocols and implementations
with respect to their impact on packet reordering.
The percentage of out-of-order packets is often used as a metric for
characterizing reordering. However, this metric is vague and lacks
in detail. There is no uniform definition of the degree of reordering
of an arrived packet [8,9]. For example, consider two packet
sequences (1, 3, 4, 2, 5) and (1, 4, 3, 2, 5). It is possible to
interpret the reordering of packets differently in this case, for
example,
(i) Packets 2, 3 and 4 are out-of-order in both cases.
(ii) Only packet 2 is out-of-order in the first sequence, while
packets 2 and 3 are out-of-order in the second.
(iii) Packets 3 and 4 are out-of-order in both the sequences.
(iv) Packets 2, 3 and 4 are out-of-order in the first sequence, while
packets 4 and 2 are out-of-order in the second sequence.
In essence, the percentage of out-of-order packets is subject to
interpretation and it cannot capture the reordering unambiguously
and, hence, accurately.
Other metrics attempt to overcome this ambiguity by defining only the
late packets or only the early packets to be reordered. However,
measuring reordering based on only late packets or early packets is
not always effective. Consider a metric that measures packet
reordering based on lateness only. For example, consider a sequence
of packets with the only anomaly being packet 20 delivered after
packet 1: (1, 20, 2, 3,..,19, 21, 22, ...). A metric based only on
lateness will indicate a high degree of reordering, whereas it is
caused by one packet arriving ahead of others. Similarly, a metric
based only on earliness does not capture reordering caused by a late
packet accurately. Thus, a complete reorder metric should account for
both earliness and lateness and be able to differentiate them.
Anura Jayasumana [Page 3]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
With the two packet sequences (1, 3, 4, 2, 5) and (1, 4, 3, 2, 5),
for example if buffers are available to store the packets 3 and 4
while waiting for the packet 2, it is possible to recover from the
reordering. However, there may be cases where the application
requirement is such that arrival of packet 2 after this delay renders
it useless. While one can argue that a good packet reordering
measurement scheme should capture such effects, a counter argument
can also be made that packet reordering should be measured strictly
with respect to the order of delivery and should be application
independent.
The desirable attributes of a packet reorder metric include:
1) Simplicity: The measure should be simple, yet contain sufficient
information to be useful.
2) Orthogonality: Metric, to the extent possible, should be
independent of or orthogonal to other phenomena that affect the
packet streams, e.g., packet loss and duplication.
3) Usefulness: Rather than being a mere representation of the amount
of reordering in a packet stream, reorder metric should be useful
to the application and/or resource management schemes. For
example, it may allow one to determine the size of buffer that is
required to recover from reordering.
4) Differentiability: Metric should provide insight into the nature
of reordering, and perhaps even into possible causes.
5) Evaluation complexity: The metric should be computable in
real-time. In evaluating reordering in an arbitrarily long
sequence, one should be able to keep a running measurement,
without having to wait till all the packets have arrived. The
memory requirement, i.e. the amount of state information, should
not grow with the length of the sequence (N), and the computation
time should be O(N).
6) Robustness: The metric should be self-correcting against events
such as bursty losses, and sequence number wraparound. It should
also have a sense of proportionality, i.e. the measure should not
change significantly due to a peculiar behavior of a very small
number of packets. For example, consider a TCP sequence number
rollover scenario with packet 2000 from the previous cycle
appearing in initial part of the current cycle which starts from
sequence number 1,2,.. This will cause a large change in a
late-packet reorder metric.
7) Broader Applicability: A good metric should have applicability
beyond just characterizing the nature of reordering in a given
sequence of packets. For example, a good metric may allow one
to combine the reorder characteristics of individual networks to
predict the reorder behavior of the network formed by
concatenation of these networks.
Anura Jayasumana [Page 4]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
In this memo, we define two density functions, Reorder Density (RD)
and Reorder Buffer-occupancy Density (RBD), that capture the nature
of reordering in a packet stream. These two metrics may be used
individually or collectively to characterize the reordering in a
packet stream.
Reorder density is the normalized distribution of the displacement of
a packet from its original position. Lost and duplicate packets are
accounted for in evaluating the displacement. The nature of
reordering introduced by a network with stationary statistical
characteristics can be captured using this metric in the form of a
reorder response [9,10]. For reordering introduced by such a system,
or for a statistically significant sequence of packets, RD is the
probability density of the packet displacement.
RBD is the normalized histogram of the occupancy of a hypothetical
buffer that would allow the recovery from out-of-order delivery of
packets. If an arriving packet is early, it is added to a
hypothetical buffer until it can be released in order. The occupancy
of this buffer after each arrival is used as the measure of
reordering. However, the arrival of a packet may be regarded useless
different constraints, such as due to the application, e.g.,
the packet may be too late for a real-time application. To
accommodate such constraints, we define a threshold on the
hypothetical buffer size, as explained in section 2.10. In [8], this
metric is called RD and buffer occupancy is known as displacement.
RD and RBD are simple, orthogonal to loss and duplication, useful to
improve/evaluate the application performance, robust against
peculiarities and have a computation complexity of O(N), where the
received sequence size is N. Also, RD of a cascade of a network
formed by two subnets is the convolution of RDs of individual
subnets.
2. Definitions of terms used
Some important terms are defined, which will help us describe the
Reorder Density, the Reorder Buffer-occupancy Density and the
measurement algorithm.
We do not explicitly address wraparound of sequence numbers in this
document, but with the use of modulo-N arithmetic, all the claims
here remain valid, in the presence of wraparound.
2.1 Receive_index (RI):
Without loss of generality, consider a sequence of packets (1, 2,..N)
transmitted over a network. A receive_index RI, (1, 2,..) is assigned
to each packet as it arrives at the destination. A receive_index is
not assigned to a duplicate, and the receive_index skips the number
corresponding to a lost packet. The detection of loss and duplication
Anura Jayasumana [Page 5]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
for this purpose is described later (section 5). RI is used to
compute earliness and lateness of an arriving packet. Below are two
examples of received sequences with receive_index values for a
sequence of 5 packets (1, 2, 3, 4, 5), arriving out of order:
Example 1:
Arrived sequence: 2 1 4 5 3
Receive_index: 1 2 3 4 5
Example 2:
Arrived sequence: 1 4 3 5 3
Receive_index: 1 3 4 5 -
In example 1, there is no loss or duplication. In example 2, the
packet with sequence number 2 is lost, and thus 2 is not assigned as
a RI; packet 3 is duplicated, thus the second copy is not assigned an
RI.
2.2 Out-of-order Packet:
When the sequence number of a packet is not equal to the RI assigned
to it, it is considered as an out-of-order packet. Duplicates, for
which RI is not defined, are ignored.
2.3 Early-packet and Late-packet:
An arriving packet i is early if its sequence number is greater than
its RI and it is late if its sequence number is less
than its RI. Let the receive_index of packet 'i' be RI[i]. If
i > RI[i] the packet is early, and i < RI[i] the packet is late.
2.4 Displacement (D):
Displacement of a packet is defined as the difference between RI and
the sequence number of the packet, i.e., the displacement of packet
i is RI[i] - i. Thus, a negative displacement refers to the earliness
of a packet and a positive displacement to the lateness. In example 3
below, an arrived sequence with displacements of each packet are
illustrated.
Example 3:
Arrived sequence: 1 4 3 5 3 8 7 6
Receive_index: 1 3 4 5 - 6 7 8
Displacement: 0 -1 1 0 - -2 0 2
Anura Jayasumana [Page 6]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
2.5 Displacement Threshold (DT):
This parameter is a threshold on the displacement of a packet that
allows the metric to classify a packet as lost or duplicate. It is
arguable as to when a packet can be classified as lost. One could
wait till the end of sequence and if a packet does not arrive, it
may be labeled as lost. But, the packet may still arrive after a
long delay. Thus, there is no point in time that a packet can
theoretically be classified as lost. From a practical point of view
however, a packet may be classified as lost if it hasnËt arrived
within a certain displacement threshold, DT. If DT is selected too
small, reordered packets may be classified as lost. A large DT will
increase the size of memory to keep track of sequence numbers as well
as computation time to evaluate the metric. Similarly, to identify
whether a packet is a duplicate, theoretically it is necessary to
keep track of all the arrived (or missing) packets so far. But from a
practical point of view, missing packets within a certain window of
sequence numbers suffice. We use DT for declaring a packet as lost,
or as a duplicate. It is indeed possible to use two different
thresholds for the two cases. The selection of DT is further
discussed in section 4.
DT makes the metric more robust and keeps the computation complexity
for long sequences within O(N), and storage requirement independent
of N.
2.6 Lateness/Earliness Frequency (FLE)
Lateness/Earliness frequency FLE[k] is the number of arrived packets
having a displacement of k. Due to the use of DT, k takes the value
from -DT to DT.
2.7 Reorder Density (RD)
RD is defined as the distribution of all Lateness/Earliness
frequencies FLE[k] normalized with respect to total number of
non-duplicate packets received (N'), where N' is the length of the
received sequence ignoring lost and duplicate packets. N' is also the
sum(FLE[k]) for all k such that k belongs to [-DT, DT].
2.8 Expected Packet(E):
A packet with sequence number 'E' is expected, if E is the largest
number such that all the packets with sequence number less than E
have already arrived or have been detected to be lost.
Anura Jayasumana [Page 7]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
2.9 Buffer Occupancy (B):
An arrived packet with a sequence number greater than that of
expected packet is considered to be stored in a hypothetical buffer
long enough to recover from reordering. At any packet arrival, the
buffer occupancy is equal to the number of such out-of-order packets
in the buffer including the arrived packet (assuming one buffer for
each packet). For example, for the sequence of packets (1, 2, 4,
5, 3), the expected order is (1, 2, 3, 4, 5) and buffer occupancy
value, when the packet with the sequence number 4 arrives is 1
because it arrived early. Similarly, the buffer occupancy becomes 2,
when the packet with the sequence number 5 arrives. When the packet
with sequence number 3 arrives, we recover from reordering and the
buffer occupancy changes to zero.
2.10 Buffer Occupancy Threshold (BT)
Buffer occupancy threshold BT, is a parameter that places a threshold
on the maximum size of the hypothetical buffer that is used for
recovery from reordering. As in the case of DT, it is used for loss
and duplication classification for RBD computation. It also provides
robustness in addition to limiting the computation complexity of RBD.
2.11 Buffer Occupancy Frequency (FB)
At the arrival of each packet the buffer occupancy may take any value
'k' ranging from 0 to BT. The buffer occupancy frequency FB[k] is the
number of times the occupancy takes the value of 'k'.
2.12 Reorder Buffer-occupancy Density (RBD)
Buffer occupancy frequencies are normalized against the total number
of non-duplicate packets received to compute Reorder Buffer-occupancy
density, i.e. RBD[k] = FB[k]/N' where N' is the length of the
received sequence ignoring lost and duplicate packets. N' is also the
sum(FB[k]) for all k such that k belongs to [0, BT].
3. Representation of packet reordering and Reorder Density
Without loss of generality, consider a sequence of packets
(1, 2,...N) transmitted over a network. An index, (1, 2,...), denoted
by receive_index, is assigned to each packet as it arrives at the
destination. A receive_index is not assigned to lost and duplicate
packets. In the absence of reordering the sequence number of the
packet and the receive_index are same for each packet. Let the
receive_index assigned to packet m be (m + dm ). This event is
represented by r(m, dm). When dm is not equal to zero, we say that a
reorder event has occurred. A packet is late if this offset dm > 0,
and early if dm < 0. Thus, packet reordering of a sequence of packets
is completely represented by the union of reorder events, R, referred
to as the reorder set:
Anura Jayasumana [Page 8]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
R = {r(m,dm)| dm not equal to 0 for all m}
If there is no reordering in a packet sequence then R is the null
set.
Examples 4 and 5 illustrate the reorder set:
Example 4. No losses or duplicates
Arrived Sequence 1 2 3 5 4 6
Receive_index 1 2 3 4 5 6
Displacement 0 0 0 -1 1 0
R = {(4,1), (5,-1)}
Example 5. Packet 4 is lost and 2 is duplicated
Arrived Sequence 1 2 5 3 6 2
Receive_index 1 2 3 5 6 -
Displacement 0 0 -2 2 0 -
R = {(3, 2), (5, -2)}
RD is defined as the discrete density of the frequency of packets
with respect to their displacements, i.e., the lateness and earliness
from the original position. Let S[k] denote the set of reorder events
in R with displacement equal to k , i.e.,
S[k]= {r(m, dm)| dm = k}
Let |S[k]| be the cardinality of set S[k] . Thus, RD[k] is defined as
|S[k]| normalized with respect to the total number of received
packets (N'). Note that N' does not include duplicates or lost
packets.
RD[k] = |S[k]|/ N' for k not equal to zero.
RD [0] corresponds to the packets for which receive_index is
the same as the sequence number. Thus
RD[0] = 1 - sum(|S[k]| / N ')
Thus, defined FLE[k] is the measure that keeps track of |S[k]|.
4. Selection of DT
While the selection of the value of DT, for the purpose of defining
lost and duplicate packets and to keep computation/storage complexity
within bounds, appears to introduce an error, this need not be the
case in practice. Application, transport layer protocol or the
network characteristics often define a value, above which DT does not
have an impact on the measurement. In case of a VoIP application, for
example, with a bit-rate of 128kbps and packet size of 200 bytes, DT
value can be determined as follows. Assume that the application can
Anura Jayasumana [Page 9]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
wait maximum 50 ms for an expected packet, and that the packets
arrive at constant rate. That means within 50 ms, the application
can receive (128*1000*0.05)/(200*8) i.e. 4 packets. Since the packet
arriving after this duration is as good as lost, the DT value could
be kept at 4. If application is such that a DT can be defined then
the use of DT does not cause any limitation, i.e., increasing DT
does not provide any benefit. In case of TCP, the transmit and
receive windows impose a natural limit on the useful value of DT.
If there is no limitation defined on DT imposed by factors just
described, or if one is purely interested in a more complete picture
of reordering, then DT can be made as large as required. In the worst
case, DT is equal to the length of the packet sequence, we get a
complete picture of reordering. This will not be a problem, if the
length of the packet sequence is known before the computation, or if
DT is allowed to grow without a limit.
5. Detection of Lost and Duplicate Packets
As RD and RBD use thresholds, all the previous packet arrivals need
not be buffered to compare with current/future arrivals. In both RD
and RBD, the sequence number of the arrival is compared to the early
arrivals. However, the size of buffer is limited by the thresholds
DT and BT respectively. A non-duplicate packet does not have a copy
in this buffer. At the same time, it cannot be earlier than those in
buffer either. Thus, we can compare the sequence number against the
expected sequence number and the buffer to identify a duplicate.
Since a packet is not considered lost until it is late beyond DT, the
question arises as to how a RI can be assigned to packets with later
packet numbers. This can be handled in one of two ways:
a) Go-back Method: RD and RBD are computed as the packets arrive, and
when a packet is deemed lost, go back and correct receive_index
values and expected sequence numbers respectively, and recompute
displacements and buffer-occupancies.
b) Stay-back Method: RD and RBD evaluation lags the arriving packets
so that it can assign the correct receive_index and expected packet
to each packet as it arrives. This way, RI and expected are assigned
to packet once and they are correct values. In the worst case, the
computations are delayed by DT and BT packets respectively. Stay-back
method needs to stay back only when a packet is missing.
6. Algorithms to compute RD and RBD
Below, we present the algorithms to compute RD and RBD. Only
Stay-back method is presented here, i.e., RD and RBD values lag by DT
and BT respectively, to detect lost packets. Both Stay-back and
Go-back methods are described elsewhere [9]. Perl scripts for these
algorithms are posted in [11].
Anura Jayasumana [Page 10]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
To keep the explanation simple, we assume without loss of generality,
that the sequence numbers start from 1 and continue with increments
of 1.
6.1 RD Algorithm
Variables used:
RI: receive_index.
S: Arrival under consideration for lateness/earliness computation.
D: Lateness or earliness of the packet being processed.
FLE[ -DT..DT]: Frequency of lateness and earliness.
window[1..DT+1]: List of incoming sequence numbers.
buffer[1..DT]: Array to hold sequence numbers of early arrivals.
window[] and buffer[] are empty at the beginning.
Step 1. Initialize:
Store first unique DT+1 sequence numbers in arriving order into
window;
RI = 1;
Step 2. Repeat:
If (window or buffer contains sequence number RI)
{
Copy first sequence number in window to S;
Delete first sequence number from window;
D = RI - S; # compute displacement
If (absolute(D) <= DT) # Apply threshold
{
FLE[D]++; # Update frequency
If (buffer contains sequence number RI)
Delete RI from buffer;
If (D < 0) # Early Arrival
add S to empty slot in buffer;
RI++; # Update RI value
}
Else # Displacement beyond threshold.
{
Discard S;
}
Anura Jayasumana [Page 11]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
# Get next incoming non-duplicate sequence number, if any.
newS = get_next_arrival(); # subroutine called*
if (newS != null)
{
add newS to window;
}
if (window is empty) go to step 3;
}
Else # RI not found. Get next RI value.
{
# Next RI is the minimum among window and buffer contents.
m = minimum (minimum (window), minimum (buffer));
If (RI < m)
RI = m;
Else
RI++;
}
Step 3. Normalize FLE to get RD;
* Get a new sequence number from packet stream, if any
subroutine get_next_arrival()
{
do # get non-duplicate next arrival
{
newS = new sequence from arriving stream;
if (newS == null) # End of packet stream
return null;
} while (newS < RI or newS in buffer or newS in window);
return newS;
}
6.2 RBD Algorithm
Variables used:
BT: Buffer Occupancy Threshold.
E: Currently expected sequence number.
S: Arrival under consideration.
B: Number of sequence numbers present in buffer.
newS: Next arriving sequence number.
window[1..BT+1]: List of incoming sequence numbers.
buffer[1..BT]: Array to hold sequence numbers of early arrivals.
TW[1..BT+1]: List of sequence numbers within threshold that are
searched to detect losses.
EW[1..BT+1]: List to retain expected sequence numbers of late
arrivals in threshold.
FB[0..BT]: Frequency of buffer-occupancy.
Anura Jayasumana [Page 12]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
Step 1. Initialize.
Store first unique BT+1 sequence numbers in arriving order into
window;
Copy all elements in window to TW;
Step 2. Repeat.
# Next expected sequence number, newE, is the smallest element
# in TW. Thus, lost packets are neglected.
newE = smallest sequence number in TW;
Delete newE from TW; # Update TW
Add newE to EW; # Update EW
# Following is regular RBD processing.
S = first sequence number in window;
Delete first sequence number from window;
E = first sequence number in EW;
If (S == E) # Next expected packet arrived
{
Delete E from EW; # Sequence number is not expected anymore
k = first sequence number in EW; # k is a temporary variable.
While (buffer contains sequence number k)
{
Delete k from both EW and buffer;
k = first sequence number in EW;
}
}
Else # S is an early arrival. Add it to the buffer.
Add S to buffer;
B = number of occupied slots in buffer;
FB[B]++; # Increment frequency of current buffer occupancy
# Get next incoming non-duplicate sequence number, if any.
newS = get_next_arrival(); # subroutine called*
if (newS != null) # subroutine called*
{
Add newS to window;
Add newS to TW;
}
if (window is empty) go to step 3;
Step 3. Normalize FB to get RBD;
Anura Jayasumana [Page 13]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
* Get a new sequence number from packet stream, if any
subroutine get_next_arrival()
{
do # get non-duplicate next arrival
{
newS = new sequence from arriving stream;
if (newS == null) # End of packet stream
return null;
} while (newS <= newE or newS in TW);
return newS;
}
7. Examples
We consider a few different sequences to exemplify the above
algorithm.
a. Case with no packet loss:
Consider a sequence of 5 packets (1, 4, 2, 5, 3, 6, 7, 8) with
DT = BT = 4.
Tables 1 and 2 show the computation steps when RD algorithm is
applied to the above sequence.
------------------------------------------------------
Table 1: Late/Early-packet Frequency computation steps
------------------------------------------------------
S 1 4 2 5 3 6 7 8
RI 1 2 3 4 5 6 7 8
D 0 -2 1 -1 2 0 0 0
FLE[D] 1 1 1 1 1 2 3 4
------------------------------------------------------
(S, RI,D,FLE[D] as described in section 6)
------------------------------------------------------
The last row (FLE[D]) represents the current frequency of occurrence
of the displacement D, e.g., column 3 indicates FLE[1] = 1 while
column 4 indicates FLE[-1] = 1.The final set of values for RD are
shown in table 2.
-------------------------------------------------
Table 2: Reorder Density (RD)
-------------------------------------------------
D -2 -1 0 1 2
FLE[D] 1 1 4 1 1
RD[D] 0.125 0.125 0.5 0.125 0.125
-------------------------------------------------
(D,FLE[D],RD[D] as described in section 6)
-------------------------------------------------
Anura Jayasumana [Page 14]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
Tables 3 and 4 illustrate the computation steps for RBD for the same
example
--------------------------------------------------------
Table 3: Buffer Occupancy Frequency computation steps
--------------------------------------------------------
S 1 4 2 5 3 6 7 8
E 1 2 2 3 3 6 7 8
B 0 1 1 2 0 0 0 0
FB[B] 1 1 2 1 2 3 4 5
--------------------------------------------------------
(E,S,B,FB[B] as described in section 6)
--------------------------------------------------------
-------------------------------------------------
Table 4: Reorder Buffer-occupancy Density (RBD)
-------------------------------------------------
B 0 1 2
FB[B] 5 2 1
RBD[B] 0.625 0.25 0.125
-------------------------------------------------
(B,FB[B],RBD[B] as described in section 6)
-------------------------------------------------
Graphical representations of the densities are as follows:
^ ^
| |
| _
^ 0.5 _ ^ 0.625 | |
| | | | | |
| | | |
RD[D] | | RBD[B] | | - o.25
_ _ | | _ _ 0.125 | || | - 0.125
| || || || || | | || || |
--+--+--+--+--+--+--> ---+--+--+--
-2 -1 0 1 2 0 1 2
D --> B -->
b. Case with packet loss:
Consider a sequence of 6 packets (1, 2, 4, 5, 6, 7) with DT = BT = 3.
Table 5 shows the computation steps, when the RD algorithm is
applied to the above sequence.
Anura Jayasumana [Page 15]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
------------------------------------------------------
Table 5: Late/Early-packet Frequency computation steps
------------------------------------------------------
S 1 2 4 5 6 7
RI 1 2 4 5 6 7
D 0 0 0 0 0 0
FLE[D] 1 2 3 4 5 6
------------------------------------------------------
(S, RI,D,FLE[D] as described in section 6)
------------------------------------------------------
Table 6 illustrates the RBD for the above arrival sequence.
-------------------------------------------------
Table 6: Buffer Occupancy Frequency computation steps
-------------------------------------------------
S 1 2 4 5 6 7
E 1 2 4 5 6 7
B 0 0 0 0 0 0
FB[D] 1 2 3 4 5 6
-------------------------------------------------
(E,S,B,FB[B] as described in section 6)
-------------------------------------------------
Graphical representations of above RD and ED are as follows.
^ ^
| |
1.0 _ 1.0 _
^ | | ^ | |
| | | | | |
| | | |
RD[D] | | RBD[B] | |
| | | |
--+--+--+--> --+--+-->
-1 0 1 0 1
D --> B -->
c. Case of duplicate packets:
Consider a sequence of 6 packets (1, 3, 2, 3 , 4, 5) with DT = 2.
Tables 7 and 8 show the computation steps when the RD algorithm is
applied to the above sequence.
Anura Jayasumana [Page 16]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
------------------------------------------------------
Table 7: Late/Early-packet Frequency computation steps
------------------------------------------------------
S 1 3 2 3 4 5
RI 1 2 3 - 4 5
D 0 -1 1 - 0 0
FLE[D] 1 1 1 - 2 3
------------------------------------------------------
(S, RI,D,FLE[D] as described in section 6)
------------------------------------------------------
--------------------------------------------
Table 8: Reorder Density (RD)
--------------------------------------------
D -1 0 1
FLE[D] 1 3 1
RD[D] 0.2 0.6 0.2
--------------------------------------------
(D,FLE[D],RD[D] as described in section 6)
--------------------------------------------
Table 9 and 10 illustrates the RBD for the above arrival sequence.
------------------------------------------------------
Table 9: Buffer Occupancy Frequency computation steps
------------------------------------------------------
S 1 3 2 3 4 5
E 1 2 2 - 4 5
B 0 1 0 - 0 0
FB[B] 1 1 2 - 3 4
------------------------------------------------------
(E,S,B,FB[B] as described in section 6)
------------------------------------------------------
-------------------------------------------------
Table 10: Reorder Buffer-occupancy Density (RBD)
-------------------------------------------------
B 0 1
FB[B] 4 1
RD[B] 0.8 0.2
-------------------------------------------------
(B,FB[B],RBD[B] as described in section 6)
-------------------------------------------------
Anura Jayasumana [Page 17]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
Graphical Representation of RD, ED and LD is as follows:
^ ^
| |
^ | ^ 0.8 _
| 0.6 _ | | |
| | | |
RD[D] | | RBD[B] | |
0.2 _ | | _ 0.2 | | _ 0.2
| || || | | || |
--+--+--+--+--+--+--> ---+--+--+--
-2 -1 0 1 2 0 1 2
D --> B -->
8. Comparison with Other Metrics
Percentage of out-of-order packets is commonly used as a packet
reordering metric. As shown in section 1, this metric has many
disadvantages.
Reordering offset [12] is a metric to measure reordering. In this
metric a packet is not considered reordered until it arrives. It
uses the definition of late arrival as in [3]. However, a duplicate
packet is considered as a reordered packet. Unlike RD and RBD, this
metric is not orthogonal to duplication of packets. Appendix B uses a
few example sequences to compare Reordering offset, RD and RBD.
N-reordering [12] is a metric where an expected packet is
1-reordered, 2-reordered and so on till it arrives. If a packet
arrives after 40 positions from its expected position then it is
40-reordered. Two examples are listed in Appendix A to show the
difference between RD and RBD, and N-reordering. These examples show
that N-reordering is much more susceptible to delayed packets as it
cannot treat them as lost when their useful life is over, whereas
with RD this is taken care of using threshold. One may argue that
since N-reordering does not use a threshold, there is no possibility
of characterizing a reordered packet (late by more than DT) as lost.
This comes however at a heavy cost, especially with respect to long
sequences, which are likely to be the cases in many measurement
scenarios, both in terms of computation complexity and memory. If
such complexity is acceptable, DT can be set to N in the calculation
of RD and RBD to overcome this concern, while preserving its all
other advantages over N-reordering. Another option is to include a
threshold for loss detection in computing N-reordering as well.
Anura Jayasumana [Page 18]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
However, RD is a more comprehensive measure that captures both
earliness and lateness. It can be shown that information contained in
N-reordering in this case is a subset of that contained in RD. From
RD measure, we can derive measures similar to N-reordering and
Reordering offset that are orthogonal to loss and duplication. For
example, consider a RD measure given as RD[-1]= 0.3, RD[0] = 0.5,
RD[1] = 0.1, RD[2] = 0.1. The measure similar to N-reordering will
have reorder measure as: 10% 2-reordering and 20% 1-reordering.
reorder offset will have 10% packets by offset two and 10% by offset
one.
9. Summary
Two metrics for packet reordering, Reorder Density (RD) and Reorder
Buffer-occupancy Density (RBD) were presented, and some of their
salient features are listed below:
RD captures the reorder characteristics of a packet stream in a
comprehensive manner. When used with a packet sequence of sufficient
length, it approaches the probability density of displacement of
packets in a stream. Thus parameters such as the mean and variance of
lateness of late packets, and fraction of packets arriving earlier by
more than m packets, can easily be obtained. It does not assume that
only two possibilities exists for a packet: ex. in lateness based
metrics, a packet is either in order, or is late, but can never be
early. As it considers both earliness and lateness simultaneously, it
contains information that would be captured by an earliness based
metric as well as a lateness based metric.
RBD evaluates reordering from the perspective of recovery from
reordering. Thus it provides information such as the size of buffers
required for an application to recover from reordering.
Both RD and RBD use thresholds to clearly define when a packet is
considered lost. They also use these thresholds to overcome having to
maintain a long list (of all received packets or all missing packets)
to identify duplicates. As a result they can accommodate anomalies
such as burst losses and multiple duplicates in a robust manner. The
threshold values can be selected to achieve the required degree of
accuracy. The time complexity of evaluating RD and RBD for a stream
of packets is O(N), while the amount of memory needed is
proportional to the threshold (DT or BT). Both RD and RBD are
orthogonal to loss and duplication. In comparison, N-reordering
and reordering offset are not.
Information provided by RD may be used to change the number of
duplicate ACKs a TCP implementation could wait before opting for
fast retransmits [13]. RBD is useful for evaluating the impact of
reordering on the performance of an application relying on a buffer
for recovery, and conversely to estimate the storage requirements or
other parameters to achieve required quality of service.
Anura Jayasumana [Page 19]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
RD, a density function of displacement of packets, can help
significantly in modeling theoretical analysis of reordering. In
fact, for a network with stationary statistical characteristics,
and a given interpacket gap distribution of a input packet stream,
the reordering of the network may be characterized using a Reorder
Response, the RD observed at the output. In [10], we prove that the
reorder response of two concatenated subnets is equal to the
convolution of the reorder responses of the two subnets. Algorithms
for generating sequences of packets for a given RD, and RBD are
described in [14]. Such algorithms are useful for simulation of
networks to understand the interaction of reordering produced by
complex networks of subnets.
10. Security Considerations
This document does not define any protocol. The metric definition per
se is believed to have no security implications.
11. IANA Considerations
This document requires nothing from the IANA.
12. References
[1] J. C. R. Bennett, C. Partridge and N. Shectman, "Packet
Reordering is Not Pathological Network Behavior," Trans. on
Networking IEEE/ACM, Dec. 1999, pp.789-798.
[2] S. Jaiswal, G. Iannaccone, C. Diot, J. Kurose and D. Towsley,
"Measurement and Classification of Out-of-sequence Packets in
Tier-1 IP Backbone," Proc. IEEE INFOCOM, Mar. 2003, pp. 1199-
1209.
[3] V.Paxson, "Measurements and Analysis of End-to-End Internet
Dynamics," Ph.D. dissertation, U.C. Berkeley, 1997,
ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz.
[4] S. Bohacek, J. Hespanha, J. Lee, C. Lim and K.Obraczka, "TCP-PR:
TCP for Persistent Packet Reordering," In Proc. of the IEEE 23rd
ICDCS, May 2003, pp.222-231.
[5] G. Iannaccone, S. Jaiswal and C. Diot, "Packet Reordering Inside
the Sprint Backbone," Tech.Report, TR01-ATL-062917, Sprint ATL,
Jun. 2001.
[6] E. Blanton and M. Allman, "On Making TCP More Robust to Packet
Reordering," ACM Computer Comm. Review, 32(1), Jan. 2002, pp.20-
30.
Anura Jayasumana [Page 20]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
[7] M. Laor and L. Gendel, "The Effect of Packet Reordering in a
Backbone Link on Application Throughput," IEEE Network,
Sep./Oct. 2002, pp.28-36.
[8] T. Banka, A. A. Bare, A. P. Jayasumana, "Metrics for Degree of
Reordering in Packet Sequences", Proc. 27th IEEE Conference on
Local Computer Networks, Tampa, FL, Nov. 2002.
[9] N. M. Piratla, "Metrics, measurements and techniques
to characterize Internet," Ph.D. Dissertation, Department of
Electrical and Computer Engineering, Colorado State University,
Fort Collins, CO. (in progress)
[10] N. M. Piratla, A. P. Jayasumana and A. A. Bare, " RD: A
Formal, Comprehensive Metric for Packet Reordering," (under
review for publication).
[11] Perl Scripts for RLED and RBD,
http://www.cnrl.colostate.edu/Reorder_Density.html,
Last modified on Jul. 18, 2004.
[12] A. Morton, L. Ciavattone, G. Ramachandran, S.Shalunov and
J.Perser, "Packet Reordering Metric for IPPM", Internet Draft,
<draft-ietf-ippm-reordering-05.txt>, August 2004.
[13] M. Zhang, B. Karp, S. Floyd and L. Peterson, "RR-TCP: A
Reordering-Robust TCP with DSACK," Proc. The Eleventh IEEE
International Conference on Networking Protocols (ICNP 2003),
Atlanta, GA, Nov. 2003, pp. 95-106.
[14] A. A. Bare, "Measurement and Analysis of Packet Reordering Using
Reorder Density," Masters Thesis, Department of Computer
Science, Colorado State University, Fort Collins, Colorado, Fall
2004.
13. Authors' Addresses
Anura P. Jayasumana <Anura.Jayasumana@colostate.edu>
Nischal M. Piratla <Nischal.Piratla@colostate.edu>
Abhijit A. Bare <Abhijit.Bare@colostate.edu>
Tarun Banka <Tarun.Banka@colostate.edu>
Computer Networking Research Laboratory,
Department of Electrical and Computer Engineering,
1373 Colorado State University,
Fort Collins, CO 80523.
Rick Whitner <rick_whitner@agilent.com>
Jerry McCollom <jerry_mccollom@agilent.com>
Agilent Technologies, 4380 Ziegler Rd.,
Fort Collins, CO, USA
Expiration Date: January 2005
Anura Jayasumana [Page 21]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
14. Revision History
This is a third version of this draft. The following changes have
been made when compared to the previous drafts:
1) ED (Early Density) and LD (Late Density) in the previous draft
have been replaced by a new Reorder Density function, that
captures the information in ED, LD, and more, in a single,
comprehensive metric. Reorder Density function is orthogonal to
losses and duplicates, and capture both lateness and earliness.
The new reorder density function addresses all the concerns
expressed at the IETF meeting, Fall 2003.
2) The Reorder Density function defined in the previous draft is
renamed Reorder Buffer-occupancy Density (RBD), reflecting its
properties more accurately. It has also been modified to address
the comments from ippm, including orthogonality to packet loss.
3) As suggested by the RFC reviewers, the formal definitions for RBD
and RD are included.
Full Copyright Statement
Copyright (C) The Internet Society (2004). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTORS, THE ORGANIZATIONS THEY REPRESENT
OR ARE SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
intellectual property or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; neither does it represent that it
has made any effort to identify any such rights. Information on the
IETF's procedures with respect to rights in standards-track and
standards-related documentation can be found in BCP-11.
Copies of IPR disclosures made to the IETF secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line repository at
http://www.ietf.org/ipr. The IETF invites any interested party to
bring to its attention any copyrights, patents or patent
Anura Jayasumana [Page 22]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
applications, or other proprietary rights, which may cover technology
that may be required to practice this standard. Please address the
information to the IETF at ietf-ipr@ietf.org.
Appendix A
Example 1:For the sequence <1,2,3,4,5,2,1>
RD output:
---------------------
Reorder Density
---------------------
D 0
FLE[D] 5
RD[D] 1.00
---------------------
RBD output:
-----------------------------------
Reorder Buffer-occupancy Density
-----------------------------------
B 0
FB[B] 5
RBD[B] 1.00
-----------------------------------
N-reordering output:
1-reordering = 33.333333%
2-reordering = 40.000000%
3-reordering = 50.000000%
4-reordering = 33.333333%
5-reordering = 50.000000%
no 6-reordering
1-reordering = 2
2-reordering = 2
3-reordering = 2
4-reordering = 1
5-reordering = 1
no 6-reordering
In this example, the N-reordering algorithm shows that there is
5-reordering. If you look at the sequence there are two duplicate
packets namely, sequence numbers 2 & 1. In RD and RBD, these packets
are discarded. As obvious, the sequence has no reordering.
Anura Jayasumana [Page 23]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
Example 2: For Sequence:
<1,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,
27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,2>
RD output with DT = 5:
------------------
Reorder Density
------------------
D 0
FLE[D] 40
RD[D] 1.00
------------------
RBD output with BT = 5:
-----------------------------------
Reorder Buffer-occupancy Density
-----------------------------------
B 0
FB[B] 40
RBD[B] 1.00
-----------------------------------
Since packet 2 is assumed to be lost, there are no late packets,
which leads to no reordering.
N-reordering output:
1-reordering = 2.500000%
2-reordering = 2.564103%
3-reordering = 2.631579%
4-reordering = 2.702703%
5-reordering = 2.777778%
6-reordering = 2.857143%
7-reordering = 2.941176%
8-reordering = 3.030303%
9-reordering = 3.125000%
10-reordering = 3.225806%
11-reordering = 3.333333%
12-reordering = 3.448276%
13-reordering = 3.571429%
14-reordering = 3.703704%
15-reordering = 3.846154%
16-reordering = 4.000000%
17-reordering = 4.166667%
18-reordering = 4.347826%
19-reordering = 4.545455%
20-reordering = 4.761905%
21-reordering = 5.000000%
22-reordering = 5.263158%
Anura Jayasumana [Page 24]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
23-reordering = 5.555556%
24-reordering = 5.882353%
25-reordering = 6.250000%
26-reordering = 6.666667%
27-reordering = 7.142857%
28-reordering = 7.692308%
29-reordering = 8.333333%
30-reordering = 9.090909%
31-reordering = 10.000000%
32-reordering = 11.111111%
33-reordering = 12.500000%
34-reordering = 14.285714%
35-reordering = 16.666667%
36-reordering = 20.000000%
37-reordering = 25.000000%
38-reordering = 33.333333%
39-reordering = 50.000000%
no 40-reordering
This example clearly shows that N-reordering is much more susceptible
to delayed packets as it cannot treat them as lost when their useful
life is over, whereas RD and RBD are most robust metrics.
Appendix B
From <draft-ietf-ippm-reordering-05.txt>
"...Table 1 Example with Packet 4 Reordered,
Sending order(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10
SrcNum Src Dst Dst Posit. Late
@Dst NextExp Time Time Delay IPDV Order Offset Time
1 1 0 68 68 1
2 2 20 88 68 0 2
3 3 40 108 68 0 3
5 4 80 148 68 -82 4
6 6 100 168 68 0 5
7 7 120 188 68 0 6
8 8 140 208 68 0 7
4 9 60 210 150 82 8 4 62
9 9 160 228 68 0 9
10 10 180 248 68 0 10
Each column gives the following information:
Anura Jayasumana [Page 25]
Internet Draft <draft-jayasumana-reorder-density-03.txt> July 2004
SrcNum Packet sequence number at the Source.
NextExp The value of NextExp when the packet arrived(before
update).
SrcTime Packet time stamp at the Source, ms.
DstTime Packet time stamp at the Destination, ms.
Delay 1-way delay of the packet, ms.
IPDV IP Packet Delay Variation, ms
IPDV = Delay(SrcNum)-Delay(SrcNum-1)..."
Reorder Buffer Density (BT =5) for the above example:
SrcNum
@Dst NextExp Buffer occupancy Frequency
1 1 0 FB[0] = 1
2 2 0 FB[0]++
3 3 0 FB[0]++
5 4 1 FB[1] = 1
6 4 2 FB[2] = 1
7 4 3 FB[3] = 1
8 4 4 FB[4] = 1
4 4 0 FB[0]++
9 9 0 FB[0]++
10 10 0 FB[0]++
Normalized FB[i] for all i: FB[0] = 0.6, FB[1] = 0.1, FB[2] = 0.1,
FB[3] = 0.1, FB[4] = 0.1
In this case, if we can set DT = 3 to get something equivalent to
IPDV must be less than 80 time units, then the table will look like
this:
SrcNum
@Dst Expected Buffer occupancy Frequency
1 1 0 FB[0] = 1
2 2 0 FB[0]++
3 3 0 FB[0]++
5 4 1 FB[0]++
6 4 2 FB[0]++
7 4 3 FB[0]++
8 4 0 FB[0]++ {after the current packet's
arrival, packet '4' is
rendered useless!}
4 9 0 - {discarded pkt.}
9 9 0 FB[0]++
10 10 0 FB[0]++
Normalized FB[i] for all i: FB[0] = 9/9 = 1.
Anura Jayasumana [Page 26]