[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04 05 06 07 08 RFC 5236

Internet Engineering Task Force
INTERNET-DRAFT                                          Anura Jayasumana
draft-jayasumana-reorder-density-02.txt               Nischal M. Piratla
                                                         Abhijit A. Bare
                                                             Tarun Banka
                                               Colorado State University
                                                            Rick Whitner
                                                          Jerry McCollom
                                                    Agilent Technologies
                                                           December 2003
                                                      Expires: June 2004

 Reorder Density Function - A Metric for packet reordering measurement


Status of this memo

   This document is an Internet-Draft and is subject to all provisions
   of Section 10 of RFC2026.

   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 obsoleted 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

   This memo provides information for the Internet community.  This memo
   does not specify an Internet standard of any kind.  Distribution of
   this memo is unlimited.

Abstract

   Out of order arrival of packets can significantly degrade the
   performance of many TCP-based, VoIP-based and video-based
   applications. There is a need for a metric that can meaningfully,
   accurately and unambiguously characterize reordering. This memo
   proposes a new metric called Reorder Density (RD), which can
   give an in-depth view of the reordering present in any packet
   sequence. This well-defined metric can also be used to evaluate
   effects of protocol and hardware implementations on packet
   reordering. We define two additional density functions Late-packet
   Density (LD) and Early-packet Density (ED) that characterize the


Anura Jayasumana                                                [Page 1]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


   lateness and the earliness of packets in a sequence as well. The memo
   also provides an algorithm to compute these density functions
   followed by some illustrative examples.

1. Introduction and Motivation

   Out of order arrival of packets is a common phenomenon on the
   Internet. A major cause of reordering of packets is the local
   parallelism present in network routers and switches. This parallelism
   is caused by different load balancing algorithms used in routers
   and switches. Packets can also be reordered due to different queuing
   schemes within the networking equipment itself. The reordering leads
   to degradation of the performance of the applications. For example,
   perceived quality of voice degrades if a VoIP application receives
   packets out-of-order. Once we quantify the degree of
   reordering in arriving packet streams, it may be possible to predict
   the effects of reordering on applications that are sensitive to
   reordering, and perhaps even compensate for reordering. This can
   further help us in evaluating network protocols with respect to
   packet reordering.

   The percentage of out-of-order packets is often being 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. 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. Thus, the current definition is not a
   sufficient metric and there is a need for a more precise and complete
   metric.

   Taking any of the above sequences, 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 the 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.


Anura Jayasumana                                                [Page 2]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


   In this memo, we define three density functions Reorder Density (RD),
   Late-packet Density(LD) and Early-packet Density (ED) that captures
   the nature of reordering in a packet stream. These three functions
   may be used individually or collectively to characterize the
   reordering in the packet stream.

   RD is the normalized form of a 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 out-of-order, it is
   added to a hypothetical buffer. The occupancy density of this buffer
   after each arrival is the measure of reordering. However, the arrival
   of a packet may be regarded useless due to application constraints,
   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.4.

   The Late-packet Density (LD) and the Early-packet Density (ED)
   characterize the packet stream with respect to the displacement of
   the packet (late or early) compared to the expected place of the
   packet (as explained in 2.2).

2. Definitions of terms used

   Some important terms are defined, which will help us describe the
   Reorder Density, Early-packet Density and Late-packet Density
   algorithm.

2.1 Out-of-order packet:

   When a packet other than the expected packet arrives, it is
   considered as an out-of-order packet, provided it is not a duplicate
   of an already received packet.

2.2 Early-packet and late-packet:

   An arriving non-duplicate packet is defined to be early if it arrives
   before its expected place in the sequence. It is considered to be
   late if it arrives after its expected place in the sequence. For
   example, for an arrived sequence (1,3,4,2,5), the packets 3 and 4
   arrived before their expected place in the sequence by 1 (i.e. 3 has
   arrived at place 2 and four at place 3) and packet 2 arrived 2
   places after its expected place (that was place 2). A packet at its
   expected place (e.g. 1 and 5 in this sequence) is neither early nor
   late. Earliness and lateness of 0 places is not defined to emphasize
   only the packets, which are really early or late.





Anura Jayasumana                                                [Page 3]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


   Place label is defined as the indicator of the place of an arriving
   packet in the arriving sequence. Place label is incremented by 1
   after each arrival of packet unless one or more packets are lost.
   Place label is used to find earliness and lateness of an arriving
   packet. Before the computation, place label is initialized to the
   first expected sequence number. For the above example (1,3,4,2,5)
   the place labels are [1,2,3,4,5]. However, this place label is not
   same as the packet counter, as explained later.

2.3 Buffer Occupancy (D):

   An arrived packet with a sequence number greater than the expected
   may be considered to be stored in a hypothetical buffer to recover
   from reordering. At any packet arrival, the buffer occupancy is equal
   to the number of such out-of-order packets including the arrived
   packet (assuming one buffer for each packet). For example, for the
   sequence of packets (1,2,4,5,3), the buffer occupancy value, when the
   packet with the sequence number 4 arrives is 1 because it arrived
   when 3 was expected. Similarly, the buffer occupancy becomes 2, when
   the packet with the sequence number 5 arrives. This term was
   previously called displacement [1].

2.4 Occupancy Threshold (DT):

   This parameter defines the tolerance of the application to the
   maximum allowed hypothetical buffer size. If an out-of-order packet
   needs to be stored in the hypothetical buffer already filled to the
   value of occupancy threshold, the currently expected packet is
   considered to be delayed more than the tolerance and hence, is
   assumed to be lost. The threshold is chosen such that even if the
   packet ultimately arrives after the threshold, it is of no use to the
   application. Many factors influence the selection of the occupancy
   threshold value, for example, the transport layer protocol (UDP or
   TCP), the amount of redundant information sent to recover from
   losses, and whether the sequence of packets belong to a
   time-sensitive application or not.

   In case of a VoIP application, for example, with  a bit-rate of 128
   kbps and packet size of 200 bytes, DT value can be determined as
   follows. Assume that the application can 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. Therefore, the occupancy
   threshold should 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. If there are no such limitations defined by the


Anura Jayasumana                                                [Page 4]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


   application, or one is purely interested in a more complete picture
   of reordering, then DT can be made as large as required. However, DT
   corresponds to the maximum allowed occupancy of the hypothetical
   buffer. If 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. However, the computation
   complexity increases with DT.

   DT can be given in time units too. In this case, the metric remains
   the same except the packet and the hypothetical buffer are now in
   time units. In this memo, we explain the spatial analysis.

   In case of TCP, a lost or delayed packet will be retransmitted and
   will reach the destination. So the value of the DT should be kept at
   least equal to the size of the receiving window on the receiver side.

   Since a packet reordered beyond DT places is assumed to be lost, it
   cannot be early or late. Therefore, earliness and lateness of a
   packet are bounded by DT. Also, in the situation of loss of one or
   more packets, the place label is advanced to the next expected
   sequence number after the buffer is flushed (partially or completely)
   , so as to avoid any false indication of earliness or lateness of the
   next arriving packets.

2.5 Buffer Occupancy Frequency (FB)

   At the arrival of each packet the buffer occupancy may take any value
   'i' ranging from 0 to DT. The buffer occupancy frequency FB[i] is the
   number of times the occupancy takes the value of 'i'.

2.6 Early-packet and Late-packet Frequency (FE and FL)

   Early frequency FE[i] is the number of packets that arrived 'i'
   places early. Similarly, late frequency FL[i] is the number of
   packets that arrived 'i' places late. Also as described above, 'i'
   can take values only between 1 and DT, both inclusive.

2.7 Reorder Density (RD)

   RD is defined as the distribution of all buffer occupancy frequencies
   FB[i] normalized with respect to the total number of occurrence
   sum(FB[i]) for all i's such that 'i' belongs to [0, DT].

2.8 Early-packet Density (ED) and Late-packet Density (LD)

   In the same way as buffer occupancy frequency, early-packet and
   late-packet frequencies are normalized against the total number of
   packets received to get early-packet density (ED) and late-packet
   density (LD) respectively.


Anura Jayasumana                                                [Page 5]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


3. Algorithm to compute RD, ED and LD

   This section describes an algorithm to compute the RD, ED and LD.
   Without loss of generality, the description assumes that the sequence
   numbers start at 1 and increment by 1 for each packet.

   ---------------------------------------------------------------------
   # E : Next expected sequence number.
   # S : Sequence number of the packet just arrived.
   # PL : Place label.
   # D : Current buffer occupancy.
   # DT : Occupancy threshold.
   # FB[i]: Frequency of buffer occupancy i  (0 <= i <= DT).
   # FE[i]: Frequency of packets that are early by i  (1 <= i <= DT).
   # FL[i]: Frequency of packets that are late by i  (1 <= i <= DT).
   # in_buffer(N) : True if the packet with sequence number N is
     already stored in the buffer.
   =====================================================================

   1.  Initialize E = 1,PL = 0,D = 0 and FB[i] = FE[i] = FL[i] = 0 for
       all values of i.

   2.  Do the following for each arrived packet.

          If (in_buffer(S) || S < E) /*Do nothing*/;
          /* Case a: S is a duplicate or delayed packet. Discard the
             packet.*/
          Else
          {
             PL = PL + 1;
             If (S == E)
             /* Case b: Expected packet has arrived.*/
             {
                E = E + 1;
                While (in_buffer(E))
                {
                   D = D - 1; /* Free buffer occupied by E.*/
                   E = E + 1; /* Expect next packet.*/
                }
                FB[D] = FB[D] + 1; /*Update frequency for buffer
                occupancy D.*/
             } /* End of ElseIf (S == E)*/








Anura Jayasumana                                                [Page 6]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


             ElseIf (S > E)
             /* Case c: Arrived packet has a sequence number higher
                than expected.*/
             {
                If (D < DT)
                /* Store the arrived packet in a buffer.*/
                   D = D + 1;
                Else
                /* Expected packet is delayed beyond the DT. Treat it as
                   lost.*/
                {
                   Repeat
                   {
                      E = E + 1;
                   }
                   Until (in_buffer(E) || E == S);

                   While (in_buffer(E) || E == S)
                   {
                      if (E != S) D = D - 1;
                      E = E + 1;
                   }
                   PL = E - 1;
                 }
                 FB[D] = FB[D] + 1; /*Update frequency for buffer
                 occupancy D.*/
             } /* End of ElseIf (S > E)*/

             /* Compute lateness/earliness of the packet and update */
             delta = S - PL;
             abs_delta = abs(delta);
             if (abs_delta > DT) abs_delta = DT;
             /* Earliness and lateness bounded by DT. */
             if (delta < 0) FL[abs_delta]++;
             else if (delta > 0) FE[abs_delta]++;
          }

   3. Normalize FB[i], FE[i] and FL[i] to get RD[i], ED[i] and LD[i] for
      all values of i using
                            FB[i]
      RD[i] = ----------------------------------
                  Sum(FB[j] for 0 <= j <= DT)

      /* Note that the normalization is done with same number of packets
         in all three cases*/
                            FE[i]
      ED[i] = ----------------------------------
                  Sum(FB[j] for 0 <= j <= DT)





Anura Jayasumana                                                [Page 7]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


                            FL[i]
      LD[i] = ----------------------------------
                  Sum(FB[j] for 0 <= j <= DT)

      respectively.

   ---------------------------------------------------------------------

   The algorithm starts with the initialization of D to 0 and E to 1.
   Let S be the sequence number of an arrived packet.

   If S has been received previously or delayed subject to the
   occupancy threshold condition (case a), it is discarded.

   If S is the expected packet (case b), E is incremented by 1 (i.e. the
   next packet in the sequence is now expected). If the packet with new
   E, i.e., the next packet in the sequence has already arrived, it need
   not be held in the buffer any more (it can be used by the
   application). So the buffer occupancy value is reduced by 1 and E is
   incremented by 1. This is repeated till all the in-sequence waiting
   packets are removed. It can be observed that case a and case b have
   no impact on early-packet measurement or late-packet measurement.
   However, case b accounts for no buffer occupancy case in RD
   computation.

   If the received packet with the sequence number S is not the expected
   packet, two cases are possible. First case is when S is higher than E
   (case c), i.e., received packet is an out-of-order packet. If the
   buffer occupancy is less than the occupancy threshold, the packet
   with the sequence number E can still be expected. The value of the
   buffer occupancy is incremented, because the newly arrived packet
   needs to be stored in the hypothetical buffer. This arrival is early
   or late based on the difference in the placeholder and arrived
   packet. The difference between these values is the number that shows
   how early or late the packet is. On the other hand, if the buffer
   occupancy is equal to the occupancy threshold, the currently expected
   packet E is assumed to be lost and E is incremented repeatedly till E
   reaches the sequence number of a packet that has been already
   received. This packet can now be removed from the hypothetical buffer
   giving space to the newly arrived packet. E is incremented further to
   check if there are any packets with higher sequence numbers already
   arrived and waiting, similar to what is done in the S=E case (in case
   b).

   The frequency value for the new value of the buffer occupancy,
   earliness and lateness are incremented as shown in the algorithm.

   Once the algorithm deals with all the packets and the frequences
   FB[D] is computed, for all the values of D, the F[D] values are
   normalized to get the density with respect to D. This function is
   called the Reorder Density function.


Anura Jayasumana                                                [Page 8]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


4. Examples

   We consider a few different sequences to exemplify the above
   algorithm.

   a. Case of no packet loss:

   Consider a sequence of 5 packets (1,4,2,5,3) with DT = 10.

   Table 1 to 6 show the computation steps when RD algorithm is applied
   to above sequence.

   -------------------------------------------------
   Table 1: Buffer Occupancy Frequency computation steps
   -------------------------------------------------
   E     1     2     2     3     3
   S     1     4     2     5     3
   D     0     1     1     2     0
   FB[D] 1     1     2     1     2
   -------------------------------------------------
   (E,S,D,FB[D] as described in section 3)
   -------------------------------------------------

   The last row (FB[D]) represents the current frequency of occurrence
   of the buffer occupancy D. The final set of values for FB[D] are
   shown in table 2.

   When the first packet with the sequence number S=1 arrives, it is
   same as the expected sequence number E=1, resulting in the
   buffer occupancy D=0. Next, when the packet S=4 arrives instead of
   the expected packet E=2, the buffer occupancy D becomes 1. After
   receiving the packet with the sequence number 2, the buffer occupancy
   D is still 1, since the packet 3 that is expected now is not yet
   received. Packet 4 continues to occupy a buffer. Only one buffer is
   needed and hence D = 1. On receiving the packet with the sequence
   number 5, the buffer occupancy D becomes 2. Finally, when we receive
   the packet with sequence number 3, all the packets up to the sequence
   number 5 have been received. Thus the buffers can be released and
   hence the buffer occupancy D becomes 0. The reorder density function
   (RD) is derived by normalizing FB[D] in Table 1 as
   follows:

   -------------------------------------------------
   Table 2: Reorder Density (RD)
   -------------------------------------------------
   D          0     1     2
   FB[D]      2     2     1
   RD[D]      0.4   0.4   0.2
   -------------------------------------------------
   (D,FB[D],RD[D] as described in section 3)
   -------------------------------------------------


Anura Jayasumana                                                [Page 9]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


   Table 3 and 4 show the computation steps of early-packet and
   late-packet densities. Let N represents the earliness or lateness of
   a packet where N represents as to how late or early a packet is for
   the respective computation.

   -------------------------------------------------
   Table 3: Early-packet Frequency computation steps
   -------------------------------------------------
   S     1     4     2     5     3
   PL    1     2     3     4     5
   N     -     2     -     1     -
   FE[N] -     1     -     1     -
   -------------------------------------------------
   (PL,S,FE[N] as described in section 3)
   -------------------------------------------------

   -------------------------------------------------
   Table 4: Late-packet Frequency computation steps
   -------------------------------------------------
   S     1     4     2     5     3
   PL    1     2     3     4     5
   N     -     -     1     -     2
   FL[N] -     -     1     -     1
   -------------------------------------------------
   (PL,S,FL[N] as described in section 3)
   -------------------------------------------------

   FE and FL are normalized to get early-packet and late-packet
   densities, ED and LD respectively.

   -------------------------------------------------
   Table 5: Early-packet Density (ED)
   -------------------------------------------------
   N          1     2
   FE[N]      1     1
   ED[N]      0.2   0.2
   -------------------------------------------------
   (FE[N],ED[N] as described in section 3)
   -------------------------------------------------

   -------------------------------------------------
   Table 6: Late-packet Density (LD)
   -------------------------------------------------
   N          1     2
   FL[N]      1     1
   LD[N]      0.2   0.2
   -------------------------------------------------
   (FL[N],LD[N] as described in section 3)
   -------------------------------------------------



Anura Jayasumana                                               [Page 10]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


   Graphical representations of the densities are as follows:

           ^                      ^                 ^
           |                  0.5 |             0.5 |
           |                      |                 |
       0.4 |_____                 |                 |
    ^      |  |  |          ^     |             ^   |
    |      |  |  |          |     |             |   |
       0.2 |  |  |__              |__ __            |__ __
  RD[D]    |  |  |  |      ED[N]  |  |  |     LD[N] |  |  |
           |  |  |  |             |  |  |           |  |  |
         0 +--+--+--+--->       0 +--+--+--->     0 +--+--+--->
             0  1  2                1  2              1  2
             D  -->                 N  -->            N  -->

   b. Case of packet loss:

   Consider a sequence of 6 packets (1,2,4,5,6,7) with DT = 3.

   Tables 7 to 11 show the computation steps, when the RD algorithm is
   applied to the above sequence.

   -------------------------------------------------
   Table 7: Buffer Occupancy Frequency computation steps
   -------------------------------------------------
   E     1     2     3     3     3     3
   S     1     2     4     5     6     7
   D     0     0     1     2     3     0
   FB[D] 1     2     1     1     1     3
   -------------------------------------------------
   (E,S,D,FB[D] as described in section 3)
   -------------------------------------------------

   When a packet with the sequence number 4 is received, the expected
   packet E is 3. So the buffer occupancy D increases by 1. When the
   packets with the sequence numbers 5 and 6 arrive, D increases to 2
   and then to 3 respectively. The buffer occupancy is now equal to the
   occupancy threshold DT=3. Therefore, when the packet 7 is received,
   we no longer expect the packet with the sequence number 3 to arrive
   and assume that it is lost. We can now use all the waiting packets
   (4,5,6 and 7), reducing the buffer occupancy to 0. The reorder
   density function (RD) is derived by normalizing FB[D]
   in Table 3 as follows:

   -------------------------------------------------
   Table 8: Reorder Density (RD)
   -------------------------------------------------
   D          0     1     2     3
   FB[D]      3     1     1     1
   RD[D]      0.5   0.17  0.17  0.17
   -------------------------------------------------
   (D,FB[D],RD[D] as described in section 3)
   -------------------------------------------------

Anura Jayasumana                                               [Page 11]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003

   Table 9 and 10 show the computation steps of early-packet and
   late-packet densities. Again, N represents the earliness or lateness
   of a packet.

   -------------------------------------------------
   Table 9: Early-packet Frequency computation steps
   -------------------------------------------------
   E     1     2     3     3     3     3
   S     1     2     4     5     6     7
   PL    1     2     3     4     5     7
   N     -     -     1     1     1     -
   FE[N] -     -     1     2     3     -
   -------------------------------------------------
   (PL,S,FE[N] as described in section 3)
   -------------------------------------------------

   -------------------------------------------------
   Table 10: Late-packet Frequency computation steps
   -------------------------------------------------
   E     1     2     3     3     3     3
   S     1     2     4     5     6     7
   PL    1     2     3     4     5     7
   N     -     -     -     -     -     -
   FL[N] -     -     -     -     -     -
   -------------------------------------------------
   (PL,S,FL[N] as described in section 3)
   -------------------------------------------------

   FE is normalized to get early-packet density ED. Since no packet in
   the sequence has arrived late, the late-packet density is undefined.

   -------------------------------------------------
   Table 11: Early-packet Density (ED)
   -------------------------------------------------
   N          1
   FE[N]      3
   ED[N]      0.5
   -------------------------------------------------
   (FE[N],ED[N] as described in section 3)
   -------------------------------------------------

   Graphical representations of above RD and ED are as follows.

                                    ^
           ^                        |
       0.5 |__                 0.5  |__
   ^       |  |                ^    |  |
   |       |  |                |    |  |
           |  |                     |  |
 RD[D] 0.17|  |________      ED[N]  |  |
           |  |  |  |  |            |  |
         0 +--+--+--+--+---->     0 +--+----->
             0  1  2  3               1
             D  -->                   N  -->

Anura Jayasumana                                               [Page 12]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003



   c.  Case of Duplicate packets:

   Consider a sequence of 6 packets (1,3,2,3,4,5) with DT = 5.

   Tables 11 to 16 show the computation steps when the RD algorithm is
   applied to the above sequence.

   -------------------------------------------------
   Table 11: Buffer Occupancy Frequency computation steps
   -------------------------------------------------
   E     1     2     2     4     4     5
   S     1     3     2     3     4     5
   D     0     1     0     -     0     0
   FB[D] 1     1     2     -     3     4
   -------------------------------------------------
   (D,FB[D],RD[D] as described in section 3)
   -------------------------------------------------

   In the above sequence, duplicate packets are received by the
   destination. The RD algorithm ignores the arrivals of the duplicate
   packets.

   -------------------------------------------------
   Table 12: Reorder Density (RD)
   -------------------------------------------------
   D          0     1
   FB[D]      4     1
   RD[D]      0.8   0.2
   -------------------------------------------------
   (D,FB[D],RD[D] as described in section 3)
   -------------------------------------------------

   -------------------------------------------------
   Table 13: Early-packet Frequency computation steps
   -------------------------------------------------
   E     1     2     2     4     4     5
   S     1     3     2     3     4     5
   PL    1     2     3     3     4     5
   N     -     1     -     -     -     -
   FE[N] -     1     -     -     -     -
   -------------------------------------------------
   (PL,S,FE[N] as described in section 3)
   -------------------------------------------------







Anura Jayasumana                                               [Page 13]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


   -------------------------------------------------
   Table 14: Late-packet Frequency computation steps
   -------------------------------------------------
   E     1     2     2     4     4     5
   S     1     3     2     3     4     5
   PL    1     2     3     3     4     5
   N     -     -     1     -     -     -
   FL[N] -     -     1     -     -     -
   -------------------------------------------------
   (PL,S,FL[N] as described in section 3)
   -------------------------------------------------

   FE and FL are normalized to get early-packet and late-packet
   densities, ED and LD respectively.

   -------------------------------------------------
   Table 15: Early-packet Density (ED)
   -------------------------------------------------
   N          1
   FE[N]      1
   ED[N]      0.2
   -------------------------------------------------
   (FE[N],ED[N] as described in section 3)
   -------------------------------------------------

   -------------------------------------------------
   Table 16: Late-packet Density (LD)
   -------------------------------------------------
   N          1
   FL[N]      1
   LD[N]      0.2
   -------------------------------------------------
   (FL[N],LD[N] as described in section 3)
   -------------------------------------------------

   Graphical Representation of RD, ED and LD is as follows:

                 ^
                 |
            0.80 |__
                 |  |
                 |  |
         ^       |  |                   ^
         |       |  |      LD[N]&ED[N]  |
                 |  |                   |
       RD[D] 0.20|  |__             0.20|__
                 |  |  |                |  |
               0 +--+--+----->        0 +--+--+----->
                   0  1                  1
                     D  --->              N  --->



Anura Jayasumana                                               [Page 14]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


5. Other schemes for measuring reordering

   Currently, the percentage of  out-of-order packets is the most
   commonly used packet reordering metric. With the percentage reorder
   metric, the information provided by the metric is purely for
   information only. For example, consider two sequences at the receiver
   end (2,3,4,5,1) and (2,1,3,4,5). Taking the definition of late
   arrival as reordered packet [2], in both the cases the percentage
   reordering is 20. However, it is obvious that the reordering in the
   second sequence is more acceptable than the first one as the recovery
   from the packet reordering is much easier in the former case. This
   metric is a significant simplification and is not useful in the
   recovery from reordering.

   N-reordering [3] 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
   reorder density and N-reordering. These examples how 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.

   Reordering offset[4] is another metric to measure reordering. In this
   metric the packet is not considered reordered until it arrives.
   However, a duplicate packet is considered as a reordered packet.
   Unlike RD, ED and LD, this metric is not orthogonal to duplication of
   packets. Appendix B uses a few example sequences to compare
   Reordering offset and RD.

   The table 17 below summarizes the loss and duplication
   orthogonalities of the current metrics:

    ---------------------------------------------------
   |Name of the metric | Orthogonal to | Orthogonal to |
   |                   | Duplication   |     Loss      |
   |---------------------------------------------------|
   |     RD            |    Yes        |      No       |
   |     ED            |    Yes        |      No       |
   |     LD            |    Yes        |      Yes      |
   |---------------------------------------------------|
   | N-reordering      |    No         |      Yes      |
   |---------------------------------------------------|
   | Reordering offset |    No         |      Yes      |
    ---------------------------------------------------


6. Security Considerations

   This document does not define any protocol.  The metric definition
   per se is believed to have no security implications.


Anura Jayasumana                                               [Page 15]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


7. IANA Considerations

   This document requires nothing from the IANA.


8. References

   1    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.

   2    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.

   3    S. Shalunov, "Definition of IP Packet Reordering Metric",
   Internet Draft, <draft-shalunov-reordering-definition-02.txt>,
   September 2003.

   4    A. Morton, L. Ciavattone, G. Ramachandran, S.Shalunov and
   J.Perser, "Packet Reordering Metric for IPPM", Internet Draft,
   <draft-ietf-ippm-reordering-03.txt>, December 2003.


9. Authors' Addresses

   Anura Jayasumana <anura@engr.colostate.edu>
   Nischal M. Piratla <nischal@engr.colostate.edu>
   Abhijit A. Bare <abhijit@cs.colostate.edu>
   Tarun Banka <tarunb@cs.colostate.edu>

   Computer Networking Research Laboratory,
   Department of Electrical and Computer Engineering,
   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: June 2004









Anura Jayasumana                                               [Page 16]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


10. Appendix A


   Example 1:For the sequence <1,2,3,4,5,2,1>

   RD output:
   -----------------------------------------
   Reorder Density
   -----------------------------------------
   D          0     1     2     3
   FB[D]      5     0     0     0
   RD[D]      1.00  0.00  0.00  0.00
   -----------------------------------------

   The early-packet (ED) and late-packet (LD) densities are undefined.

   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, the FB[D] does not
   exist for D > 0 i.e., there is no reordering. As one can see, the
   sequence has no reordering.

   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      1      2      3      4      5
   FB[D]      35     1      1      1      1      1
   RD[D]      0.875  0.025  0.025  0.025  0.025  0.025
   ---------------------------------------------------



Anura Jayasumana                                               [Page 17]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


   ---------------------------------------------------
   Early-packet Density
   ---------------------------------------------------
   D          1      2      3      4      5
   FE[D]      5      0      0      0      0
   ED[D]      0.125  0      0      0      0
   ---------------------------------------------------

   Since packet 2 is assumed to be lost, there are no late packets,
   which leads to an undefined late-packet density (LD).

   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%
   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

Anura Jayasumana                                               [Page 18]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


   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 with RD this is taken care of.


11. Appendix B

   From <draft-ietf-ippm-reordering-01.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:

   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 Density for the above example:

   SrcNum
   @Dst NextExp  Buffer occupancy  Frequency
    1     1          0              F[0] = 1
    2     2          0              F[0]++
    3     3          0              F[0]++
    5     4          1              F[1] = 1
    6     4          2              F[2] = 1
    7     4          3              F[3] = 1
    8     4          4              F[4] = 1
    4     4          0              F[0]++
    9     9          0              F[0]++
   10    10          0              F[0]++


Anura Jayasumana                                               [Page 19]

Internet Draft  <draft-jayasumana-reorder-density-02.txt>  December 2003


   Normalized F[i] for all i: F[0] = 0.6, F[1] = 0.1, F[2] = 0.1, F[3] =
   0.1,
   F[4] = 0.1

   In this case, if we can set DT = 3, then the table will look like
   this:

   SrcNum
   @Dst Expected  Buffer occupancy Frequency
   1     1          0              F[0] = 1
   2     2          0              F[0]++
   3     3          0              F[0]++
   5     4          1              F[1] = 1
   6     4          2              F[2] = 1
   7     4          3              F[3] = 1
   8     4          0              F[0]++    {after the current packet's
                                              arrival, packet '4' is
                                              rendered useless!}
   4     9          0              -         {discarded pkt.}
   9     9          0              F[0]++
   10    10         0              F[0]++

   Normalized F[i] for all i: F[0] = 5/9, F[1] = 1/9, F[2] = 1/9, F[3] =
   1/9


   Other examples in current metrics are almost similar. However, there
   are no examples with packet duplication. Here is one for the metric
   proposed. (Note: Packet '5' is duplicated.)

   SrcNum
   @Dst NextExp  Buffer Occupancy  Frequency
   1     1          0              F[0] = 1
   2     2          0              F[0]++
   3     3          0              F[0]++
   5     4          1              F[1] = 1
   6     4          2              F[2] = 1
   7     4          3              F[3] = 1
   8     4          4              F[4] = 1
   4     4          0              F[0]++
   5     9          0              -   {duplicate packet}
   9     9          0              F[0]++


   Normalized F[i] for all i: F[0] = 5/9, F[1] = 1/9, F[2] = 1/9, F[3] =
   1/9, F[4] = 1/9.

   At the arrival of a duplicate packet the buffer occupancy is held the
   same as the duplicate packet will be discarded and the contents of
   the buffer remain the same.


Anura Jayasumana                                               [Page 20]


Html markup produced by rfcmarkup 1.109, available from https://tools.ietf.org/tools/rfcmarkup/