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]