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