Internet DRAFT - draft-critchley-mlas-reordering
draft-critchley-mlas-reordering
Network Working Group D. Pullin
Internet Draft California Institute of Technology
Expiration Date: August 2002 A. Corlett
B. Mandeville
CQOS, Inc.
S. Critchley
Worldcom, Inc.
Packet Reordering: The Minimal Longest Ascending Subsequence Metric
<draft-critchley-mlas-reordering-00.txt>
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026 [1].
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/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
This draft describes a metric, based on the minimal longest ascending
subsequence (MLAS), which can be used to measure the level of
reorderedness of a given single sequence of packets transmitted by one
host and received by a second. This metric enables reordering between
similar packet flows to be compared across differing network
topologies. The draft goes on to provide a set of recommended
parameters which can be used when attempting to consistently compare
reordering, and highlights potential issues which should be taken into
account during measurement.
1. Introduction
Traditionally, the effect of network conditions upon applications
transmitting packets from one host to another has been measured
according to the parameters generally accepted to have the most effect
on the performance of the applications sending and receiving those
packets. The following are usually measured - loss, delay (both
one-way and two-way), and jitter. However, certain IP-based
applications, such as voice, video, and encapsulated Layer 2 services,
also rely to some extent on packets sent being received in the same
order in which they were transmitted. These applications are affected
to different extents by the level of reordering experienced.
Reordering can be said to have occurred if packets are received in
anything other than exactly the same order in which they are
transmitted. However, should reordering occur, there is currently no
standard metric in place with which to define the degree to which a
sequence of packets received is out of order in relation to the
sequence in which it was transmitted [2]. This document sets out to
define such a metric, and provide a set of recommendations in order to
assist in measurement.
2. An MLAS-based Packet Reordering Metric.
2.1 Metric considerations
When transmitting, receiving, and sampling a sequence of packets in
order to determine the level of reorderedness of that sequence, it is
necessary to take into account the following:
- Transmission and receipt devices.
The sampled sequence of packets is always transmitted from one device,
known as the source, and received at another device, known as the
destination. In that way, a level of reordering can be given for
packets passing in one direction across a network.
- Sampling device.
The device performing calculations on the packet sequence in order to
derive a level of reorderedness may or may not be the same device as
the destination device.
- Length of Sequence
The transmission device is capable of transmitting a defined number of
packets in a sample sequence. The sampling device is aware of the
number of packets defined in the sample sequence. Whether the
transmission device labels each packet in a sample sequence with the
length of that sequence is optional.
- Transmission Interval
The transmission device is capable of transmitting sample packets with
a given interval between transmission. This interval is generally
stated as the number of packets sent per second for any given
sequence. The device sampling the given sequence of packets for
reorderedness is aware of the interval between transmission of packets
by the source. Whether the transmission device labels each packet
transmitted in the sample sequence with the transmission interval of
packets in that sequence is optional.
- Overall Transmission Envelope
It is assumed that 100% of packets in the sample sequence sent by the
transmission device are received, and that they are received within a
given time following transmission of the initial packet in the
sequence, stated in seconds. Packets received after the end of this
transmission envelope are discounted.Whether the transmission device
labels each packet in the sequence with the overall envelope of the
sequence is optional.
- Packet Size
The tranmission device is capable of transmitting sample packets in a
given sequence with a standard packet size. This packet size is
generally stated as a number of bytes. The sampling device is capable
of aware of the packet size of each packet in the sample flow. Whether
the transmission device labels each packet transmitted in the sample
sequence with the given standard packet size for that sequence is
optional. All packets in a given sequence should be of the same size.
- Sequence Numbers
All packets transmitted in a sample flow or sequence are given a
transmission sequence number by the source device, and are given a
receipt sequence number by the destination device.
- Sequence awareness
The device sampling the sequence of packets for reorderedness is
capable of reading both the transmission and receipt sequence numbers,
and of performing the calculation necessary to derive the degree of
reorderedness of the sequence.
It can therefore be stated that a sample packet sequence has the
following stated properties:
- Sequence Length, in number of packets.
- Transmission Interval, in packets per second.
- Overall Transmission Envelope, in seconds.
- Packet Size, in bytes, for each packet.
- Unique Sequence Numbers, both transmission and receipt, for each packet.
2.2 Definition of the MLAS-based Packet Ordering Metric.
Suppose that we a set of integers {X} with elements
x(i),i=1,....,N. These integers may represent the send order of a
sequence of packets. For the purposes of this discussion the elements
x(i) may be any integer, negative, zero or positive. Any number of
repeated elements are allowed. In practice these integers may
represent the send order of a sequence of packets, and so will be
positive integers. An example with N=10 is
{X} : {3,2,4,6,5,9,7,1,10,8}
An ascending subsequence of X, denoted by {S} of length m, is defined
as any subsequence of {X} which has the properties that
(i) it contains m elements,
(ii) the elements appear in {S} in the same order as they appear in{X}
(iii) the elements of {S} are in ascending order.
In the above example, there are countably many ascending subsequences of
the given sequence. For example, ascending subsequences of length m=3 of
the sequence of {X} given above include
{S_1} : {2,4,6 }
{S_2} : {4,7,10}
{S_3} : {5,9,10}
These are not exhaustive.
2.1.1 The Minimal Longest Ascending Subsequence (MLAS)
For a given {X}, there exists some m=m_{max} such that no ascending
subsequence is of length greater than m=m_{max}. For our example
m_{max}=5 and
{S_1} : {2,4,5,9,10}
{S_2} : {2,4,5,7,10}
{S_3} : {2,4,5,7,8}
are all ascending subsequences of length m=5. We call these the
longest ascending subsequences of {X}. The three shown above are not
the complete set of ascending subsequences of length m=5 of our
original sequence. We can rank ascending subsequences of the same
length by comparing their terminal elements, and then, if necessary,
the subsequent elements, working backwards. Thus for the three
subsequences of length m=5 we give the ranking
{S_3}< {S_2} <{S_1}
because 8<10 and 7<9. The member belonging to the set of the longest
ascending subsequences that has lowest rank is referred to as the
Minimal Longest Ascending Subsequence (MLAS) of the sequence {X}. For
any given {X} the MLAS is unique. For {X} given above, the MLAS is
{S_3}.
It is proposed that, for a given sequence of length N the elements of
which are the packet send order, the packets that are `in order' be
defined to be the MLAS for the sequence. Those packets not belonging
to the MLAS are considered to be out of order. With this definition
there are exactly m_{max} packets that are in order and N- m_{max}
packets that are out of order.
2.1.2 The MLAS algorithm
There exist well known algorithms for determining the MLAS of any
given sequence. The one used presently was obtained from the website
http://www.tiac.net/users/cri/mlas.html
which also contains a description of the algorithm, and relevant
pseudocode. The following brief description of the MLAS algorithm is
derived from the above web site. [3]
Suppose that we already have the MLAS for a sequence with elements
x(i), i =1,...,K-1. This is always known for the first element of the
sequence, for which m_{max}=1, and the MLAS consists simply of x(1) We
use this, together with x(K), to obtain the MLAS for the extended
sequence with elements x(i), i =1,...,K. Let t_m be the index of the
terminal element of the minimal ascending of length m in the sequence
x(i), i =1,...,K-1. Then the terminal element of this ascending
subsequence is x(t_m). These terminal elements are ordered, so that
x(t_1) <x(t_2).....< x(t_{m_{max}}). Now extend x(i), i =1,...,K-1 to
x(i), i =1,...,K by adding x(K). Search the terminals for a j such
that
x(t_j) < x(K) < x(t_{j+1})
If x(K)< x(t_1), then set t_1=K, else if x(K) > x(t_{m_{max}}), then
increment m_{max} by 1 and add a new ascending subsequence with
t_{max}=K, else set t_{j+1}=K. Perform this procedure for
K=1,...,N. In order to keep track of the MLAS, backpointers are
used. Let b_l be the index of the predecessor of x(l). Each x(i)
either has no predecessor (if it is a minimal ascending subsequence of
length 1), in which case set b_i = -1, or it has just one
predecessor. Backpointers are assigned when the algorithm passes
through K=i. The output of the algorithm is m_{max} and the arrays
t_m, m=1,....,m_{max} and b_q, q=1,....,N$. The reconstruction of the
MLAS can be done after the basic algorithm has executed by first
starting from x(t_{m_{max}}), and then following the predecessors
backwards. It should be emphasized that this step is not necessary if
only m_{max} is required. In addition, each minimal ascending
subsequence with $m=1,..,m_{max}$ can also be found if required by the
same procedure, starting from x(t_{m}).
2.1.3 Calculation of the reordering metric.
The MLAS algorithm provides an approach to both the definition and
solution of the packet ordering problem. For a given sequence it
provides the length m_{max} of the minimal longest ascending
subsequence in CPU cost order N*log(N), and with memory requirements
order (N). The number of `packet moves' required to re-order the
sequence is then simply N-m_{max}. This suggests that an ordering
metric be defined as
Q = m_{max}/N
If the elements of a sequence {X} are in ascending order (all packets
received in the order sent), then m_max = N and so Q = 1. If the
elements of {X} are in perfect descending order (packets received in
reverse order), then m_{max} = 1, and so Q = 1/N. Hence Q is bounded
above by unity and below by 1/N. An alternative dedinition could be
Q = log(m_{max}/N} -1
In this case perfect ascending order corresponds to Q = 0 and perfect
descending order gives Q = log(1/N) -1.
3. Sampling Techniques
In order to provide a consistent metric value when comparing differing
levels of reordering across multiple networks, it is necessary to take
certain considerations into account. These are provided below:
3.1 Sampling Parameters and Recommendations
In this section, this draft provides recommendations for the following
parameters:
- Sequence Length.
- Transmission Interval.
- Packet Size.
- Unique Sequence Numbers.
- Overall Transmission Envelope.
- Packet Protocol
3.1.1 Sequence Length
It should be noted that it is possible to derive a degree of
reordering in a sample sequence of any number of packets, as long as
that number is greater than 0. However, the meaningfulness of the
degree of reordering derived increases with the length of the sequence
upon which the calculation is made. With this in mind, this draft
recommends sampling as much as possible using longer packet sequences,
and chooses to select a sequence length of 50 packets. Whether
incremental sampling is performed, based on continual flow
transmission, is optional and does not affect sequence
length. However, when stating a degree of reordering it is considered
to be necessary to state the sequence length of the sample
sequence(s).
3.1.2 Transmission Interval
Take a sequence of packets, X, transmitted by source A, in the
following order:
{X_A} : {1,2,3,4,5,6,7,8,9,10}
The interval between transmission of each packet in {X_A} is 125 ms.
After passing across a network, P, this sequence is received by
destination B in the following order:
{X_B} : {3,4,5,1,7,8,2,6,9,10}
According to the metric defined in this draft, the sequence {X_A} has
experienced a certain level of reordering, R.
At the same time, another sequence of packets, Y, is transmitted by
source A, in the same order:
{Y_A} : {1,2,3,4,5,6,7,8,9,10}
The interval between transmission of each packet in {Y_A} is 2 seconds.
After passing across network P, this sequence is received by
destination B in the following order:
{Y_B} : {1,2,3,4,5,6,7,8,9,10}
In this case, the sequence {Y_A} has experienced no reordering.
Therefore, unless a transmission interval is stated it is impossible
to assign a network-causal effect to reodering in given sequences of
packets, and it is anticipated that this makes comparison of
reordering across varying network topologies meaningless.
Therefore, this draft recommends implementation of a limited set of
example sequences, each of which contains a specific, stated,
transmission interval in seconds. Each of this limited set of example
sequences is designed to emulate the packet behaviour of a common IP
application. Adherence to the recommended transmission intervals when
sampling is not compulsory. However, when stating a degree of
reordering it is considered necessary to state the transmission
interval of the packets in the sampled sequence(s).
3.1.3 Packet Size
Due to interface queuing, and other network parameters beyond the
influence of the transmission devices, sequences of different packet
size can experience reordering of differing magnitudes, even if all
other factors are the same. With this in mind, this draft recommends
implementation of a limited set of example sequences, each of which
contains a specific, stated, packet size in bytes. Each of this
limited set of example sequences is designed to emulate the packet
behaviour of a common IP application. Adherence to the recommended
packet sizes is not compulsory. However, when stating a degree of
reordering of a given sequence it is considered necessary to state the
packet size of the packets in the sample sequence.
3.1.4 Unique Sequence Numbers
This draft recommends that unique sequence numbers are used for each
packet in a sample sequence, in order that overall simplicity is
maintained and that it is impossible that packets belonging to one
sequence are transmitted with the same sequence as packets belonging
to another sequence during two overlapping overall transmission
intervals.
3.1.5 Overall Transmission Envelope
In order for consistency to be achieved, this draft recommends that
the value of the overall transmission envelope be not more than two
seconds greater than the time taken to transmit the entire sequence
according to its stated transmission interval value and its sequence
length value. Adherence to the recommended overall transmission
envelope is not compulsory. However, when stating a degree of
reordering of a given sequence it is considered necessary to state the
overall transmission envelope value, in seconds.
3.1.6 Packet Protocol
This draft makes no recommendations on the protocol type used for the
packets in a sample sequence as this is not perceived to have any
effect on the reordering of any given packet sequence. However, this
draft does recommend that, when sampling packet reordering, protocol
of the sample packets used is stated in order to provide clarity and
ease of comparison.
3.2 Recommended sample set.
With the details and recommendations provided in section 3.1 above,
this draft sets out the following flows which those carrying out
sampling may or may not wish to apply in their sampling technique, and
state when providing sampling results.
Set Sequence Transmission Packet Overall
Length Interval Size Transmission
(packets) (pps) (Bytes) Envelope (s)
1 50 50 200 3.000
2 50 50 40 3.000
3 50 7 1500 8.143
4. 50 11 1500 6.545
5. 50 86 1500 3.724
6. 50 6 1500 10.333
7. 50 30 1500 3.667
8. 50 83 1500 2.602
These sample figures are intended to approximate to the following streams:
1 = G.711 VoIP
2 = G.729 VoIP
3 = appx 80Kbps streamed audio
4 = appx 128Kbps streamed video
5 = appx 1Mbps streamed video
6 = appx 9KBps TCP transfer
7 = appx 45KBps TCP transfer
8 = appx 125KBps TCP transfer
4. References
[1] Bradner, S., "The Internet Standards Process -- Revision 3", RFC 2026,
Internet Engineering Task Force, October 1996.
[2] "On the packet ordering problem", D. Pullin, A. Corlett and
R. Mandeville, CQOS Internal Document, April 2001.
[3] Harter, R., "The minimal longest ascending subsequence algorithm",
http://www.tiac.net/users/cri/mlas.html, and other references.
5. Authors' Addresses
Sam Critchley
Worldcom EMEA Network Service
Joan Muyskenweg 22
1096 CJ Amsterdam
The Netherlands
Phone: +31 20 711 6082
Email: Sam.Critchley@wcom.com
Dale Pullin
Mailstop 105-50
California Institute of Technology
1200 East California Blvd.
Pasadena CA 91125
Andrew Corlett
CQOS Inc.,
7 Technology Dr.
Irvine, CA 92618
R. Mandeville
CQOS Inc.,
7 Technology Dr.
Irvine, CA 92618
Expiration date: August, 2002
