On Queuing, Marking, and Dropping
RFC 7806
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
Show full document text