On Queuing, Marking, and Dropping
RFC 7806

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

• Versions
• 00
• 01
• 02
• 03
• 04
• 05

Internet Engineering Task Force (IETF)                          F. Baker
Request for Comments: 7806                                        R. Pan
Category: Informational                                    Cisco Systems
ISSN: 2070-1721                                               April 2016

                   On Queuing, Marking, and Dropping

Abstract

   This note discusses queuing and marking/dropping algorithms.  While
   these algorithms may be implemented in a coupled manner, this note
   argues that specifications, measurements, and comparisons should
   decouple the different algorithms and their contributions to system
   behavior.

Status of This Memo

   This document is not an Internet Standards Track specification; it is
   published for informational purposes.

   This document is a product of the Internet Engineering Task Force
   (IETF).  It represents the consensus of the IETF community.  It has
   received public review and has been approved for publication by the
   Internet Engineering Steering Group (IESG).  Not all documents
   approved by the IESG are a candidate for any level of Internet
   Standard; see Section 2 of RFC 5741.

   Information about the current status of this document, any errata,
   and how to provide feedback on it may be obtained at
   http://www.rfc-editor.org/info/rfc7806.

Copyright Notice

   Copyright (c) 2016 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Baker & Pan                   Informational                     [Page 1]
RFC 7806            On Queuing, Marking, and Dropping         April 2016

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Fair Queuing: Algorithms and History  . . . . . . . . . . . .   3
     2.1.  Generalized Processor Sharing . . . . . . . . . . . . . .   3
       2.1.1.  GPS Comparisons: Transmission Quanta  . . . . . . . .   4
       2.1.2.  GPS Comparisons: Flow Definition  . . . . . . . . . .   4
       2.1.3.  GPS Comparisons: Unit of Measurement  . . . . . . . .   5
     2.2.  GPS Approximations  . . . . . . . . . . . . . . . . . . .   5
       2.2.1.  Definition of a Queuing Algorithm . . . . . . . . . .   5
       2.2.2.  Round-Robin Models  . . . . . . . . . . . . . . . . .   6
       2.2.3.  Calendar Queue Models . . . . . . . . . . . . . . . .   7
       2.2.4.  Work-Conserving Models and Stochastic Fairness
               Queuing . . . . . . . . . . . . . . . . . . . . . . .   9
       2.2.5.  Non-Work-Conserving Models and Virtual Clock  . . . .   9
   3.  Queuing, Marking, and Dropping  . . . . . . . . . . . . . . .  10
     3.1.  Queuing with Tail Mark/Drop . . . . . . . . . . . . . . .  11
     3.2.  Queuing with CoDel Mark/Drop  . . . . . . . . . . . . . .  11
     3.3.  Queuing with RED or PIE Mark/Drop . . . . . . . . . . . .  11
   4.  Conclusion  . . . . . . . . . . . . . . . . . . . . . . . . .  12
   5.  Security Considerations . . . . . . . . . . . . . . . . . . .  13
   6.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  13
     6.1.  Normative References  . . . . . . . . . . . . . . . . . .  13
     6.2.  Informative References  . . . . . . . . . . . . . . . . .  13
   Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . .  15
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  16

1.  Introduction

   In the discussion of Active Queue Management (AQM), there has been
   discussion of the coupling of queue management algorithms such as
   Stochastic Fairness Queuing [SFQ], Virtual Clock [VirtualClock], or
   Deficit Round Robin [DRR] with mark/drop algorithms such as
   Controlled Delay (CoDel) [DELAY-AQM] or Proportional Integral
   controller Enhanced (PIE) [AQM-PIE].  In the interest of clarifying
   the discussion, we document possible implementation approaches to
   that and analyze the possible effects and side effects.  The language
   and model derive from the Architecture for Differentiated Services
   [RFC2475].

   This note is informational and is intended to describe reasonable
   possibilities without constraining outcomes.  This is not so much
   about "right" or "wrong" as it is "what might be reasonable" and
   discusses several possible implementation strategies.  Also, while
   queuing might be implemented in almost any layer, the note
   specifically addresses queues that might be used in the