Improved Packet Reordering Metrics
RFC 5236

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions
• 08

Network Working Group                                      A. Jayasumana
Request for Comments: 5236                     Colorado State University
Category: Informational                                       N. Piratla
                                                   Deutsche Telekom Labs
                                                                T. Banka
                                               Colorado State University
                                                                 A. Bare
                                                              R. Whitner
                                              Agilent Technologies, Inc.
                                                               June 2008

                   Improved Packet Reordering Metrics

Status of This Memo

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

IESG Note

   The content of this RFC was at one time considered by the IETF, and
   therefore it may resemble a current IETF work in progress or a
   published IETF work.  The IETF standard for reordering metrics is RFC
   4737.  The metrics in this document were not adopted for inclusion in
   RFC 4737.  This RFC is not a candidate for any level of Internet
   Standard.  The IETF disclaims any knowledge of the fitness of this
   RFC for any purpose and in particular notes that the decision to
   publish is not based on IETF review for such things as security,
   congestion control, or inappropriate interaction with deployed
   protocols.  The RFC Editor has chosen to publish this document at its
   discretion.  Readers of this RFC should exercise caution in
   evaluating its value for implementation and deployment.  See RFC 3932
   for more information.

Abstract

   This document presents two improved metrics for packet reordering,
   namely, Reorder Density (RD) and Reorder Buffer-occupancy Density
   (RBD).  A threshold is used to clearly define when a packet is
   considered lost, to 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.

Jayasumana, et al.           Informational                      [Page 1]
RFC 5236           Improved Packet Reordering Metrics          June 2008

   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. Attributes of Packet Reordering Metrics .........................4
   3. Reorder Density and Reorder Buffer-Occupancy Density ............7
      3.1. Receive Index (RI) .........................................8
      3.2. Out-of-Order Packet ........................................9
      3.3. Displacement (D) ...........................................9
      3.4. Displacement Threshold (DT) ................................9
      3.5. Displacement Frequency (FD) ...............................10
      3.6. Reorder Density (RD) ......................................10
      3.7. Expected Packet (E) .......................................10
      3.8. Buffer Occupancy (B) ......................................10
      3.9. Buffer-Occupancy Threshold (BT) ...........................11
      3.10. Buffer-Occupancy Frequency (FB) ..........................11
      3.11. Reorder Buffer-Occupancy Density (RBD) ...................11
   4. Representation of Packet Reordering and Reorder Density ........11
   5. Selection of DT ................................................12
   6. Detection of Lost and Duplicate Packets ........................13
   7. Algorithms to Evaluate RD and RBD ..............................14
      7.1. Algorithm for RD ..........................................14
      7.2. Algorithm for RBD .........................................16
   8. Examples .......................................................17
   9. Characteristics Derivable from RD and RBD ......................21
   10. Comparison with Other Metrics .................................22
   11. Security Considerations .......................................22
   12. References ....................................................22
      12.1. Normative References .....................................22
      12.2. Informative References ...................................22
   13. Contributors ..................................................24

Jayasumana, et al.           Informational                      [Page 2]
RFC 5236           Improved Packet Reordering Metrics          June 2008

1.  Introduction and Motivation