Lightweight Fair Queueing
draft-morton-tsvwg-lightweight-fair-queueing-00

Document Type Active Internet-Draft (individual)
Last updated 2019-07-02
Stream (None)
Intended RFC status (None)
Formats plain text xml pdf html bibtex
Stream Stream state (No stream defined)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date
Responsible AD (None)
Send notices to (None)
Transport Working Group                                        J. Morton
Internet-Draft                                                  P. Heist
Intended status: Informational                               3 July 2019
Expires: 4 January 2020

                       Lightweight Fair Queueing
            draft-morton-tsvwg-lightweight-fair-queueing-00

Abstract

   This note presents Lightweight Fair Queueing (LFQ), a fair queueing
   algorithm with a small code footprint, low memory requirements, no
   multiply operations, only two physical queues, and only one set of
   AQM state.  LFQ provides throughput fairness, sparse flow
   prioritization and ordering guarantees, making it suitable for a
   mixture of traffic flow types.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

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

   This Internet-Draft will expire on 4 January 2020.

Copyright Notice

   Copyright (c) 2019 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 (https://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.

Morton & Heist           Expires 4 January 2020                 [Page 1]
Internet-Draft                lightweightfq                    July 2019

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Background  . . . . . . . . . . . . . . . . . . . . . . . . .   2
   3.  The Algorithm . . . . . . . . . . . . . . . . . . . . . . . .   3
     3.1.  Overview  . . . . . . . . . . . . . . . . . . . . . . . .   3
     3.2.  Declarations  . . . . . . . . . . . . . . . . . . . . . .   4
     3.3.  Pseudo-code . . . . . . . . . . . . . . . . . . . . . . .   6
     3.4.  Simulator . . . . . . . . . . . . . . . . . . . . . . . .   9
   4.  Security Considerations . . . . . . . . . . . . . . . . . . .   9
   5.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   9
   6.  Informative References  . . . . . . . . . . . . . . . . . . .   9
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  10

1.  Introduction

   Flow isolation is a powerful tool for congestion management in
   today's Internet.  Early implementations, such as SFQ [SFQ], aimed
   simply to have inter-flow induced latency dependent on the number of
   flows, rather than the total length of the queue.  Today, DRR++
   [DRRPP] explicitly shares throughput capacity between flows, and
   prioritises "sparse" flows that use less than their fair share, on
   the grounds that these are probably latency-sensitive traffic.  This
   reduces the inter-flow induced latency to near zero for sparse flows,
   regardless of the number of saturating flows.

   Unfortunately, the relatively complex algorithms and considerable
   dynamic state of a DRR++ queue set with individual AQM (Active Queue
   Management) [RFC7567] instances has proved disheartening to hardware
   implementors, and thus to deployment on high-capacity links.
   Ordinary CPE devices implementing DRR++ in software work well up to
   100Mbps or so.  A scheme involving only a small number of queues and
   AQM instances might be more suitable for the 1Gbps and up category.

   This note therefore presents LFQ, a fair queueing algorithm suitable
   for implementation in hardware, making fair queueing possible on
   high-throughput routers and low-cost middleboxes.

2.  Background

   LFQ is inspired by DRR++'s facility for identifying "sparse" flows
   and giving them strict priority over "saturating" flows.  DRR++ does
   this by maintaining separate lists of queues (each queue containing
   one flow) meeting "sparseness" criteria or not.

   Queues are first placed into the sparse list when they become non-
   empty, then moved to the saturating list when their deficit exceeds a
   threshold called "quantum".  Every queue's deficit is incremented by

Morton & Heist           Expires 4 January 2020                 [Page 2]
Show full document text