[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02

Transport Area Working Group                                    K. Nichols
Internet-Draft                                               Pollere, Inc.
Intended status: Informational                                 V. Jacobson
Expires: August 24, 2013                                      Google, Inc.
                                                         February 24, 2013

                 Controlled Delay Active Queue Management
                       draft-nichols-tsvwg-codel-01


Abstract

   The "persistently full buffer" problem has been discussed in the
   IETF community since the early 80's [RFC896]. The IRTF's End-to-End
   Working Group called for the deployment of active queue management
   to solve the problem in 1998 [RFC2309]. Despite the awareness and
   recommendations, the "full buffer" problem has not gone away, but on
   the contrary has become worse as buffers have grown in size and
   proliferated and today's networks proved intractable for available
   AQM approaches. The overall problem is presently known as
   "bufferbloat"[TSVBB2011, BB2011] and has become increasingly
   important, particularly at the consumer edge.
   This document describes a recently developed AQM, Controlled Delay
   (CoDel) algorithm, which was designed to work in modern networking
   environments and can be deployed as a major part of the solution to
   bufferbloat [CODEL2012]. The goal of the CoDel work is to provide a
   solution with cost-effective implementation that is particularly
   well-suited to the consumer edge.

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), its areas, and its working groups. Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   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

   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 August 24, 2013.


Nichols & Jacobson     Expires August 24, 2013                    [Page 1]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

Copyright Notice
   Copyright (c) 2013 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 the
   license as included with the code in Section 4.

Table of Contents

  1. Introduction .....................................................3
  2. Conventions used in this document ................................4
  3. The Controlled Delay (CoDel) Approach ............................4
     3.1. Overview of CoDel's Algorithm ...............................5
     3.2. About the interval ..........................................6
     3.3. About the target ............................................6
     3.4. Non-starvation ..............................................7
     3.5. Target and Interval in Bursty MACs ..........................8
     3.6. Use with multiple queues ....................................8
     3.7. Use of stochastic bins or sub-queues to improve performance .8
  4. Annotated Pseudo-code for CoDel ..................................9
     4.1. Data Types .................................................11
     4.2. Per-queue state (codel_queue_t instance variables) .........11
     4.3. Constants ..................................................11
     4.4. Enque routine ..............................................11
     4.5. Deque routine ..............................................12
     4.6. Helper routines ............................................13
     4.7. Implementation considerations ..............................14
  5. CoDel for specialized networks ..................................15
  6. Resources and Additional Information ............................15
  7. Security Considerations .........................................16
  8. IANA Considerations .............................................16
  9. Conclusions .....................................................16
  10.References ......................................................16
     10.1.Normative References .......................................16
     10.2.Informative References .....................................16
  11.Acknowledgments .................................................18




Nichols & Jacobson     Expires August 24, 2013                 [Page 2]

Internet-Draft  Controlled Delay Active Queue Management   February 2013


1. Introduction

   The need for queue management has been evident for decades.
   Unfortunately, the development and deployment of effective active
   queue management has been hampered by persistent misconceptions
   about the cause and meaning of queues. Network buffers exist to
   absorb the packet bursts that occur naturally in statistically
   multiplexed networks. Short-term mismatches in traffic arrival and
   departure rates that arise from upstream resource contention,
   transport conversation startup transients and/or changes in the
   number of conversations sharing a link create queues in the buffers.
   Unfortunately, other network behavior can cause queues to fill and
   their effects aren't nearly as benign. Discussion of these issues
   and why the solution isn't just smaller buffers can be found in
   [RFC2309],[VANQ2006],[REDL1998] and [CODEL2012]. It is critical to
   understand the difference between the necessary and useful "good"
   queue and the counterproductive "bad" queue.
   Recent papers [CMNTS] question how widespread bufferbloat actually
   is. It is certainly difficult to measure that and those papers do
   not claim to do so. Certainly, there are places, particularly at the
   network edge, where bufferbloat occurs and impacts performance. The
   correct solution is a cost-effective AQM that "does no harm" if its
   subject buffer is not bloated. We believe this is an appropriate
   response to the problem where dramatic protocol changes are the
   wrong response.

   Many approaches to active queue management (AQM) have been developed
   over the past two decades, but none has been widely deployed due to
   performance problems. When designed with the wrong conceptual model
   for queues, AQMs have limited operational range, require a lot of
   configuration tweaking, and frequently impair rather than improve
   performance. Today, the demands on an effective AQM are even
   greater: many network devices must work across a range of
   bandwidths, either due to link variations or due to the mobility of
   the device. CoDel has been designed to meet the following goals:

   o is parameterless - has no knobs for operators, users, or
      implementers to adjust

   o treats "good queue" and "bad queue" differently, that is, keeps
      delay low while permitting necessary bursts of traffic

   o controls delay while insensitive (or nearly so) to round trip
      delays, link rates and traffic loads; this goal is to "do no
      harm" to network traffic while controlling delay

   o adapts to dynamically changing link rates with no negative impact
      on utilization

Nichols & Jacobson     Expires August 24, 2013                  [Page 3]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

   o is simple and efficient (can easily span the spectrum from low-
      end, linux-based access points and home routers up to high-end
      commercial router silicon)

   With no changes to parameters, we have found CoDel to work across a
   wide range of conditions, with varying links and the full range of
   terrestrial round trip times. CoDel has been implemented in Linux
   very efficiently and should lend itself to silicon implementation.
   Further, CoDel is well-adapted for use in multiple queued devices
   due to its use of sojourn time.

   Since CoDel was published (4/2012), a number of talented and
   enthusiastic implementers and experimenters have been working with
   CoDel with promising results. CoDel has been implemented along with
   stochastic flow queuing for better traffic management. CoDel has
   also been applied successfully in data center networks which have
   different properties than the consumer edge. Much of this work can
   be located starting from: http://www.bufferbloat.net/projects/codel.

2. Conventions used in this document

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC-2119 [RFC2119].

   In this document, these words will appear with that interpretation
   only when in ALL CAPS. Lower case uses of these words are not to be
   interpreted as carrying RFC-2119 significance.
   In this document, the characters ">>" preceding an indented line(s)
   indicates a compliance requirement statement using the key words
   listed above. This convention aids reviewers in quickly identifying
   or finding the explicit compliance requirements of this RFC.

3. The Controlled Delay (CoDel) Approach

   CoDel has three major innovations that distinguish it from prior
   AQMs: use of local queue minimum to track congestion ("bad queue"),
   use of an efficient single state variable representation of that
   tracked statistic, and the use of packet sojourn time time as the
   observed datum, rather than packets, bytes, or rates. The local
   minimum queue provides an accurate and robust measure of standing
   queue and has an efficient implementation since it is sufficient to
   keep a single state variable of how long the minimum has been above
   or below a target value rather than retaining all the local values
   to compute the minimum. By tracking the packet sojourn time in the
   buffer, CoDel is using the actual delay experienced by each packet,
   which is independent of link rate, gives superior performance to use
   of buffer size, and is directly related to the user-visible
   performance.

Nichols & Jacobson     Expires August 24, 2013                 [Page 4]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

   In addition to lending itself to an efficient single state variable
   implementation, use of the minimum value has important advantages in
   implementation. The minimum packet sojourn can only be decreased
   when a packet is dequeued which means that all the work of CoDel can
   take place when packets are dequeued for transmission and that no
   locks are needed in the implementation. The minimum is the only
   statistic with this property. The only addition to code at packet
   arrival is creation of a timestamp of packet arrival time. If the
   buffer is full when a packet arrives, the packet is dropped as
   usual.

3.1. Overview of CoDel's Algorithm

   To ensure that link utilization is not adversely affected, CoDel's
   design assumes that a small "target" standing queue delay (discussed
   in more detail below) is acceptable and that it is unacceptable to
   drop packets when the drop would leave the queue empty or there are
   fewer than a maximum transmission unit (MTU) worth of bytes in the
   buffer. A persistent delay above the target indicates a standing
   queue. The standing queue can be detected by tracking the (local)
   minimum queue delay packets experience. To ensure that this minimum
   value does not become stale, it has to have been experienced
   recently, which is can be determined by using an appropriate
   interval of time (discussed further below). When the queue delay
   has exceeded the target for at least an interval, a packet is
   dropped and a control law used to set the next drop time. The next
   drop time is decreased in inverse proportion to the square root of
   the number of drops since the dropping state was entered, using the
   well-known relationship of drop rate to throughput to get a linear
   change in throughput. [REDL1998, MACTCP1997] When the queue delay
   goes below target, the controller stops dropping. No drops are
   carried out if the buffer contains fewer than an MTU worth of bytes.
   Additional logic prevents re-entering the dropping state too soon
   after exiting it and resumes the dropping state at a recent control
   level, if one exists. Target and interval are constants with
   straightforward interpretations described below.

   CoDel only enters its dropping state when the local minimum sojourn
   delay has exceeded an acceptable value for standing queue for an
   "interval" long enough to for normal bursts to dissipate. This
   ensures that a burst of packets will not be dropped as long as the
   burst can be cleared from the queue within a reasonable interval.

   CoDel's efficient implementation and lack of configuration are
   unique features and make it suitable to manage modern packet
   buffers. The three innovations: minimum statistic, simplified single
   state variable tracking of minimum, and use of queue sojourn time
   lead directly to these unique features. For more background and
   results on CoDel, see [CODEL2012], available on-line at
   queue.acm.org.

Nichols & Jacobson     Expires August 24, 2013                 [Page 5]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

3.2. About the interval

   The interval constant is chosen to give endpoints time to react to a
   drop without being so long that response times suffer. As such, it
   is clearly related to RTT. Since RTTs vary across connections and
   are not known apriori, the best policy is to use a value on the
   order of or slightly larger than the RTT seen by most of the
   connections using a link. It's fortunate that CoDel is fairly
   insensitive to interval since it's difficult to give a definitive
   histogram of RTTs seen on the normal consumer edge link.

   A setting of 100ms works well across a range of RTTs from 10ms to 1
   second (excellent performance is achieved in the range from 10 ms to
   300ms). For devices intended for the normal, terrestrial internet
   interval SHOULD have the value of 100ms. Smaller values are likely
   to cause CoDel to over drop packets since insufficient time is given
   to senders to react and this will most adversely affect a long-lived
   TCP with an RTT long compared to interval.
   A CoDel control law more independent of interval is future work.

3.3. About the target

   The target value constant is the maximum acceptable standing queue
   delay above which CoDel is dropping or preparing to drop and below
   which CoDel will not drop. Our initial focus with CoDel is on
   devices for the open internet, in particular the consumer edge,
   where bottleneck standing queues of a few milliseconds are
   acceptable for ordinary internet traffic.

   The target value derives from an analytically derived range which
   was further studied with many simulations. Analysis centers on a
   single TCP connection since this is easiest to analyze and is more
   difficult to keep utilization high than with more connections. With
   a sufficiently large buffer, the link utilization for the single TCP
   flow can reach 100% but the delay will increase. If no queue is
   permitted, A Reno TCP will only get 75% utilization. We want a value
   for the target, the maximum acceptable standing queue, that gets a
   good utilization for the long-lived TCP flow while holding down the
   delay. Conceptually, if this TCP connection were sharing the link
   with other short-lived flows, it would be able to achieve an
   excellent utilization while presenting a short delay to these other,
   possibly interactive, flows. Fortunately, analysis shows that a very
   small standing queue gives close to 100% utilization and this holds
   for Reno, Cubic, and Westwood. Pictures of this can be seen at
   [TSV84]. The analysis was done by normalizing the queue size to a
   percentage of RTT and using the average "power" (throughput over
   delay) performance metric. The ideal range for the permitted
   standing queue is between 5 and 10% of the RTT of the TCP
   connection.

Nichols & Jacobson        Expires August 24, 2013              [Page 6]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

   We expected additional impact when TCPs are mixed with other traffic
   and experiencing a number of different RTTs. Accordingly, we
   experimented with values between 1 and 20 milliseconds for RTTs from
   30 to 500ms and link bandwidths of 64Kbps to 100Mbps to determine a
   target that gives consistently high utilization while controlling
   delay across a range of bandwidths, RTTs, and traffic loads. Below a
   target of 5ms, utilization suffers for some conditions and traffic
   loads, above 5ms we saw very little or no improvement in
   utilization. Thus target SHOULD be set to 5ms.
   If a CoDel link has only or primarily long-lived TCP flows sharing a
   link to congestion but not overload, the median delay through the
   link will tend to the target value. For bursty traffic loads and for
   overloaded conditions (where it is difficult or impossible for all
   the arriving flows to be accommodated, the median queues will be
   longer than target).

   By inhibiting drops when there is less than an (outbound link) MTU
   worth of bytes in the buffer, CoDel adapts to very low bandwidth
   links. This is shown in [CODEL2012] and interested parties should
   see the discussion of results there. Unpublished studies were
   carried out down to 64Kbps. The drop inhibit condition can be
   expanded to include a test to retain sufficient bytes or packets to
   fill an allocation in a request-and-grant MAC.
   CoDel has to see sojourn times that remain above target for an
   entire interval in order to enter the drop state. Any packet with a
   sojourn time less than target will reset the time that the queue was
   last below the target. Since internet traffic has very dynamic
   characteristics, the actual sojourn delays experienced by packets
   varies greatly and is often less than the target unless the overload
   is excessive. When a link is not overloaded, it is not a bottleneck
   and packet sojourn times will be small or nonexistent. In the usual
   case, there are only one or two places along a path where packets
   will encounter a bottleneck (usually at the edge), so the amount of
   queuing delay experienced by a packet should be less than 10 ms even
   under extremely congested conditions. Contrast this to the queuing
   delays that grow to orders of seconds that have led to the
   "bufferbloat" term [NETAL2010, CHARRB2007].


3.4. Non-starvation

   CoDel's goals are to control delay with little or no impact on link
   utilization and to be deployed on a wide range of link bandwidth,
   including varying rate links, without reconfiguration. To keep from
   making drops when it would starve the output link, CoDel makes
   another check before dropping to see if at least an MTU worth of
   bytes remains in the buffer. If not, the packet SHOULD NOT be


Nichols & Jacobson     Expires August 24, 2013                 [Page 7]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

   dropped and, currently, CoDel exits the drop state. The MTU size can
   be set to the largest packet seen so far or read from the driver.

3.5. Target and Interval in Bursty MACs

   Regrettably, there seems to be some confusion about the role of
   target and interval. In particular, many experimenters believe the
   value of target needs to be increased when the lower layers have a
   bursty nature where packets are transmitted for short periods
   interspersed with idle periods where the link is waiting for
   permission to send. CoDel will "see" the effective transmission rate
   over an interval and increasing target will just lead to longer
   queue delays. On the other hand, if an additional delay is added to
   the round trip time of most or all packets due to the waiting time
   for a transmission, it may be necessary to increase interval by that
   extra delay. That is, target SHOULD NOT be adjusted but interval MAY
   need to be adjusted. For more on this (and pictures) see
   pollere.net/

3.6. Use with multiple queues

   Unlike other AQMs, CoDel is easily adapted to multiple queue
   systems. With other approaches there is always a question of how to
   account for the fact that each queue receives less than the full
   link rate over time and usually sees a varying rate over time. This
   is exactly what CoDel excels at: using a packet's sojourn time in
   the buffer completely bypasses this problem. A separate CoDel
   algorithm can run on each queue, but each CoDel uses the packet
   sojourn time the same way a single queue CoDel does. Just as a
   single queue CoDel adapts to changing link bandwidths[CODEL2012], so
   do the multiple queue CoDels. When testing for queue occupancy
   before dropping, the total occupancy of all bins should be used.

3.7. Use of stochastic bins or sub-queues to improve performance

   Shortly after the release of the CoDel pseudocode, Eric Dumazet
   created fq_codel, applying CoDel to each bin, or queue, used in an
   SFQ (stochastic fair queuing) approach. (To understand further, see
   [SFQ1990] or the linux sfq at http://linux.die.net/man/8/tc-sfq.)
   Fq_codel hashes on the packet header fields to determine a specific
   bin, or sub-queue, for each five-tuple flow, and runs CoDel on each
   bin or sub-queue thus creating a well-mixed output flow and
   obviating issues of reverse path flows (including "ack
   compression"). Dumazet's code is part of the CeroWrt project code at
   the bufferbloat.net's web site.

   Inspired by Dumazet's work, we've experimented with an ns-2
   simulator version with excellent results thus far: median queues
   remain small across a range of traffic patterns that includes
   bidirectional file transfers (that is, the same traffic sent in both

Nichols & Jacobson     Expires August 24, 2013                 [Page 8]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

   directions on a link), constant bit-rate VoIP-like flows, and
   emulated web traffic and utilizations are consistently better than
   single queue CoDel, generally very close to 100%. Our original
   version differed slightly from Dumazet's by using a packet-based
   round robin of the bins rather than byte-based DRR and by doing a
   simple drop tail when bins are full and there may be other minor
   differences in implementation. There are some experimental additions
   that permit head or tail drop from fullest bin and a quantum-based
   rounding. Andrew McGregor has an ns-3 version of fq_codel and we
   have heard good reports of his results.

   This approach is to provide a better traffic mixing on the wire and
   to tend to isolate a larger flow or flows. For real priority
   treatment, use of DiffServ isolation is encouraged. We've
   experimented with creating a queue that gets all the UDP traffic in
   the simulation (which is all simulated VoiP and low bandwidth) but
   this approach has to be applied with caution in the real world. Some
   experimenters are trying rounding with a small quantum (on the order
   of a voice packet size) but this also needs thorough study.

   There are a number of open issues that should be studied. In
   particular, if the number of different queues or bins is too large,
   the scheduling will be the dominant factor, not the AQM; it is NOT
   the case that more bins are always better. In our simulations, we
   have found good behavior across mixed traffic types with smaller
   numbers of queues, 8-16 for a 5Mbps link. This configuration seemed
   to give the best behavior for voice, web browsing and file transfers
   where increased numbers of bins seemed to favor file transfers at
   the expense of the other traffic. Our work has been very preliminary
   and we encourage others to take this up and to explore analytic
   modeling. It would be good to see the effects of different numbers
   of bins on a range of traffic models, something like an updated
   version of [BMPFQ].

   Implementers should consider using this type of approach if possible
   as it deals with many problems beyond the reach of an AQM alone. As
   more experiments are completed, future versions of this draft may be
   able to include particular pseudocode for a recommended approach.

4. Annotated Pseudo-code for CoDel

   What follows is the CoDel algorithm in C++-like pseudo-code. Since
   CoDel adds relatively little new code to a basic tail-drop fifo-
   queue, we've tried to highlight just these additions by presenting
   CoDel as a sub-class of a basic fifo-queue base class. There have
   been a number of minor variants in the code and our reference
   pseudo-code has not yet been completely updated.




Nichols & Jacobson     Expires August 24, 2013                 [Page 9]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

   Implementors are strongly encouraged to also look at Eric Dumazet's
   Linux kernel version of CoDel - a well-written, well tested, real-
   world, C-based implementation. As of this writing, it is at:
   http://git.kernel.org/?p=linux/kernel/git/torvalds/
   linux.git;a=blob_plain;f=net/sched/sch_codel.c;hb=HEAD

   This code is open-source with a dual BSD/GPL license:

     Codel - The Controlled-Delay Active Queue Management algorithm

     Copyright (C) 2011-2012 Kathleen Nichols <nichols@pollere.com>

     Redistribution and use in source and binary forms, with or
     without modification, are permitted provided that the following
     conditions are met:

        *   Redistributions of source code must retain the above
            copyright notice, this list of conditions, and the following
            disclaimer, without modification.

        *   Redistributions in binary form must reproduce the above
            copyright notice, this list of conditions and the following
            disclaimer in the documentation and/or other materials
            provided with the distribution.

        *   The names of the authors may not be used to endorse or
            promote products derived from this software without specific
            prior written permission.

      Alternatively, provided that this notice is retained in full,
     this software may be distributed under the terms of the GNU
     General Public License ("GPL") version 2, in which case the
     provisions of the GPL apply INSTEAD OF those given above.

      THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
     CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
     INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
     MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
     BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
     EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
     TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
     ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
     TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
     THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     SUCH DAMAGE.



Nichols & Jacobson      Expires August 24, 2013                  [Page 10]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

4.1. Data Types

   time_t is an integer time value in units convenient for the system.
          Resolution to at least a millisecond is required and better
          resolution is useful up to the minimum possible packet time
          on the output link; 64- or 32-bit widths are acceptable but
          with 32 bits the resolution should be no finer than 2^{-16}
          to leave enough dynamic range to represent a wide range of
          queue waiting times. Narrower widths also have implementation
          issues due to overflow (wrapping) and underflow (limit cycles
          because of truncation to zero) that are not addressed in this
          pseudocode. The code presented here uses 0 as a flag value to
          indicate "no time set."

   packet_t* is a pointer to a packet descriptor. We assume it has a
          tstamp field capable of holding a time_t and that field is
          available for use by CoDel (it will be set by the enque
          routine and used by the deque routine).

   queue_t is a base class for queue objects (the parent class for
          codel_queue_t objects). We assume it has enque() and deque()
          methods that can be implemented in child classes. We assume
          it has a bytes() method that returns the current queue size
          in bytes. This can be an approximate value. The method is
          invoked in the deque() method but shouldn't require a lock
          with the enque() method.

   flag_t is a Boolean.

4.2. Per-queue state (codel_queue_t instance variables)

   time_t first_above_time; // Time when we'll declare we're above
                            // target (0 if below)
   time_t drop_next;     // Time to drop next packet
   uint32_t count;      // Packets dropped since entering drop state
   flag_t dropping;      // Equal to 1 if in drop state

4.3. Constants

   time_t target = MS2TIME(5); // Target queue delay (5 ms)
   time_t interval = MS2TIME(100); // Sliding-minimum window (100ms)
   u_int maxpacket = 512; // Maximum packet size in bytes
                          // (should use interface MTU)

4.4. Enque routine

   All the work of CoDel is done in the deque routine. The only CoDel
   addition to enque is putting the current time in the packet's tstamp
   field so that the deque routine can compute the packet's sojourn
   time.

Nichols & Jacobson        Expires August 24, 2013             [Page 11]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

   void codel_queue_t::enque(packet_t* pkt)
   {
       pkt->timestamp() = clock();
       queue_t::enque(pkt);
   }

4.5. Deque routine

   This is the heart of CoDel. There are two branches: In packet-
   dropping state (meaning that the queue-sojourn time has gone above
   target and hasn't come down yet), then we need to check if it's time
   to leave or if it's time for the next drop(s); if we're not in
   dropping state, then we need to decide if it's time to enter and do
   the initial drop.

   Packet* CoDelQueue::deque()
   {
       double now = clock();;
       dodequeResult r = dodeque(now);

         if (dropping_) {
             if (  r.ok_to_drop) {
                 // sojourn time below target - leave dropping state
                 dropping_ = 0;
             }
             // Time for the next drop. Drop current packet and dequeue
             // next. If the dequeue doesn't take us out of dropping
             // state, schedule the next drop. A large backlog might
             // result in drop rates so high that the next drop should
             // happen now, hence the 'while' loop. Increment count_
             // outside of the loop.
             while (now >= drop_next_ && dropping_) {
                 drop(r.p);
                 r = dodeque(now);
                 if (  r.ok_to_drop) {
                     // leave dropping state
                     dropping_ = 0;
                 } else {
                     ++count_;
                     // schedule the next drop.
                     drop_next_ = control_law(drop_next_);
                 }
             }
        // If we get here we're not in dropping state. The 'ok_to_drop'
        // return from dodeque means that the sojourn time has been
        // above 'target' for 'interval' so enter dropping state.
        } else if (r.ok_to_drop) {
            drop(r.p);
            r = dodeque(now);

Nichols & Jacobson      Expires August 24, 2013                 [Page 12]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

           dropping_ = 1;
           // If min went above target close to when it last went
           // below, assume that the drop rate that controlled the
           // queue on the last cycle is a good starting point to
           // control it now. ('drop_next' will be at most 'interval'
           // later than the time of the last drop so 'now - drop_next'
           // is a good approximation of the time from the last drop
           // until now.)
           count_ = (count_ > 2 && now - drop_next_ < 8*interval_)?
                       count_ - 2 : 1;
           drop_next_ = control_law(now);
       }
       return (r.p);
   }

4.6. Helper routines

   Since the degree of multiplexing and nature of the traffic sources
   is unknown, CoDel acts as a closed-loop servo system that gradually
   increases the frequency of dropping until the queue is controlled
   (sojourn time goes below target). This is the control law that
   governs the servo. It has this form because of the sqrt(p)
   dependence of TCP throughput on drop probability. Note that for
   embedded systems or kernel implementation, the inverse sqrt can be
   computed efficiently using only integer multiplication. See Eric
   Dumazet's excellent Linux CoDel implementation for example code (in
   file net/sched/sch_codel.c of the kernel source for 3.5 or newer
   kernels).

   time_t codel_queue_t::control_law(time_t t)
   {
       return t + interval / sqrt(count);
   }
   Next is a helper routine the does the actual packet dequeue and
   tracks whether the sojourn time is above or below target and, if
   above, if it has remained above continuously for at least interval.
   It returns two values, a Boolean indicating if it is OK to drop
   (sojourn time above target for at least interval) and the packet
   dequeued.

   typedef struct {
         packet_t* p;
         flag_t ok_to_drop;
   } dodeque_result;

   dodeque_result codel_queue_t::dodeque(time_t now)
   {
       dodequeResult r = { NULL, queue_t::deque() };

Nichols & Jacobson     Expires August 24, 2013                [Page 13]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

       if (r.p == NULL) {
           // queue is empty - we can't be above target
           first_above_time_ = 0;
           return r;
       }

       // To span a large range of bandwidths, CoDel runs two
       // different AQMs in parallel. One is sojourn-time-based
       // and takes effect when the time to send an MTU-sized
       // packet is less than target. The 1st term of the "if"
       // below does this. The other is backlog-based and takes
       // effect when the time to send an MTU-sized packet is >=
       // target. The goal here is to keep the output link
       // utilization high by never allowing the queue to get
       // smaller than the amount that arrives in a typical
       // interarrival time (MTU-sized packets arriving spaced
       // by the amount of time it takes to send such a packet on
       // the bottleneck). The 2nd term of the "if" does this.
       time_t sojourn_time = now - r.p->tstamp;
       if (sojourn_time_ < target_ || bytes() <= maxpacket_) {
           // went below - stay below for at least interval
           first_above_time_ = 0;
       } else {
           if (first_above_time_ == 0) {
                // just went above from below. if still above at
                // first_above_time, will say it's ok to drop.
                first_above_time_ = now + interval_;
           } else if (now >= first_above_time_) {
                r.ok_to_drop = 1;
           }
       }
       return r;
   }

4.7. Implementation considerations

   Since CoDel requires relatively little per-queue state and no direct
   communication or state sharing between the enqueue and dequeue
   routines, it's relatively simple to add it to almost any packet
   processing pipeline, including ASIC- or NPU-based forwarding
   engines. One issue to think about is dodeque's use of a 'bytes()'
   function to find out about how many bytes are currently in the
   queue. This value does not need to be exact. If the enqueue part of
   the pipeline keeps a running count of the total number of bytes it
   has put into the queue and the dequeue routine keeps a running count
   of the total bytes it has removed from the queue, 'bytes()' is just
   the difference between these two counters. 32 bit counters are more
   than adequate. Enqueue has to update its counter once per packet
   queued but it doesn't matter when (before, during or after the
   packet has been added to the queue). The worst that can happen is a

Nichols & Jacobson     Expires August 24, 2013                [Page 14]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

   slight, transient, underestimate of the queue size which might cause
   a drop to be briefly deferred.

5. CoDel for specialized networks

   CoDel's constants are set for use in devices in the open Internet.
   They have been chosen so that a device, such as a small WiFi router,
   can be sold without the need for those values to be made adjustable,
   a "parameterless" implementation. CoDel is useful in environments
   with significantly different characteristics from the normal
   internet, for example, in switches used as a cluster interconnect
   within a data center. Since cluster traffic is entirely internal to
   the data center, round trip latencies are low (typically <100us) but
   bandwidths are high (1-40Gbps) so it's relatively easy for the
   aggregation phase of a distributed computation (e.g., the Reduce
   part of a Map/Reduce) to persistently fill then overflow the modest
   per-port buffering available in most high speed switches. A CoDel
   configured for this environment (target and interval in the
   microsecond rather than millisecond range) can minimize drops (or
   ECN marks) while keeping throughput high and latency low.
   Devices destined for these environments MAY have different
   constants, ones that are suitable for those environments. But these
   settings will cause problems such as over dropping and low
   throughput if used on the open Internet so devices that allow the
   CoDel constants to be configured MUST default to Internet
   appropriate values given in this document.

6. Resources and Additional Information

   CoDel is being implemented and tested in a range of environments.
   Dave Taht has been instrumental in the integration and distribution
   of bufferbloat solutions, including CoDel, and has set up a website
   for CeroWRT implementers. This is an active area of work and an
   excellent place to track developments. Eric Dumazet has put CoDel
   into the Linux distribution. Andrew McGregor has an ns-3
   implementation of both CoDel and FQ_CoDel and we have made our ns-2
   implementation public. Dave Taht set up a web site and mailing list
   for implementers and Eric Dumazet put CoDel into the Linux
   distribution. An experiment by Stanford graduate students
   successfully duplicated our published work using the linux code
   which can be found at: http://
   reproducingnetworkresearch.wordpress.com/2012/06/06/solving-
   bufferbloat-the-codel-way/.

   Cable Labs is actively experimenting with CoDel, fq_codel, and
   sfqcodel for cable modem simulation models.

   Our ns-2 simulations are available at http://pollere.net/CoDel.html.
   We continue to do some small experiments and are periodically

Nichols & Jacobson     Expires August 24, 2013                [Page 15]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

   updating the code. Cable Labs has funded some additions to the
   simulator sfqcodel code which should be made public in the future.
   The basic algorithm of CoDel remains unchanged, but we continue to
   experiment with drop interval setting when resuming the drop state,
   whether to "clear out" extremely aged packets from the queue, and
   other minor details. Our approach to changes is to only make them if
   we are both convinced they do more good than harm, both
   operationally and in the implementation. With this in mind, some of
   these issues won't be settled until we can get more experimental
   deployment. Our ns-2 version of stochastic flow binning is also
   available at our site.

7. Security Considerations

   This document describes an active queue management algorithm for
   implementation in networked devices. There are no specific security
   exposures associated with CoDel.

8. IANA Considerations

   This document does not require actions by IANA.

9. Conclusions

   CoDel is a very general,   efficient, parameterless active queue
   management approach that   can be applied to single or multiple
   queues. It is a critical   tool in solving bufferbloat. CoDel's
   settings MAY be modified   for other special-purpose networking
   applications.

   On-going projects are creating a deployable CoDel in Linux routers
   and experimenting with applying CoDel to stochastic queuing with
   very promising results.

10.References

10.1. Normative References

   [RFC896] Nagle, J., "Congestion Control in IP/TCP Internetworks",
             RFC 896, January 1984.
   [RFC2309] Braden, R. et al., "Recommendations on Queue Management
             and Congestion Avoidance in the Internet", RFC 2309, April
             1998.

10.2. Informative References




Nichols & Jacobson       Expires August 24, 2013                [Page 16]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

   [TSV2011] Gettys, J., "Bufferbloat: Dark Buffers in the Internet",
             presentation to Transport Area Open Meeting, http://
             www.ietf.org/proceedings/80/tsvarea.html, IETF 80, March,
             2011.
   [BB2011] Gettys, J. and K. Nichols, "Bufferbloat: Dark Buffers in
             the Internet", Communications of the ACM 9(11) pp. 57-65.

   [BMPFQ] Suter, B., et. al., "Buffer Management Schemes for
             Supporting TCP in Gigabit Routers with Per-flow Queueing",
             IEEE Journal on Selected Areas in Communications Vol. 17
             Issue 6, June, 1999, pp. 1159-1169.
   [CMNTS] Allman, M., "Comments on Bufferbloat", Computer
             Communication Review Vol. 43 No. 1, January, 2013, pp.
             31-37.

   [CODEL2012] Nichols, K. and V. Jacobson, "Controlling Queue Delay",
             Communications of the ACM Vol. 55 No. 11, July, 2012, pp.
             42-50.
   [VANQ2006] Jacobson, V., "A Rant on Queues", talk at MIT Lincoln
             Labs, Lexington, MA, July, 2006, http://www.pollere.net/
             Pdfdocs/QrantJul06.pdf
   [REDL1998] Jacobson, V., K. Nichols and K. Poduri, "RED in a
             Different Light",September, 1999, http://
             www.cnaf.infn.it/~ferrari/papers/ispn/red_light_9_30.pdf

   [NETAL2010] Kreibich, C., et. al., "Netalyzr: Illuminating the Edge
             Network", Proceedings of the Internet Measurement
             Conference, Melbourne, Australia, 2010.

   [TSV84] Jacobson, V., slides and talk at TSV meeting IETF 84,
             http://www.ietf.org/proceedings/84/slides/slides-84-
             tsvarea-4.pdf and http://recordings.conf.meetecho.com/
             Recordings/watch.jsp?
             recording=IETF84_TSVAREA&chapter=part_3

   [CHARB2007] Dischinger, M., et. al, "Characterizing Residential
             Broadband Networks", Proceedings of the Internet
             Measurement Conference, San Diego, CA, 2007.
   [MACTCP1997] Mathis, M., J. Semke, J. Mahdavi, "The Macroscopic
             Behavior of the TCP Congestion Avoidance Algorithm", ACM
             SIGCOMM Computer Communications Review, Vol. 27 no. 1,
             Jan. 2007.

   [SFQ1990] McKenney, P., "Stochastic Fairness Queuing", Proceedings
             of IEEE INFOCOMM'90, San Francisco, 1990.

Nichols & Jacobson     Expires August 24, 2013                [Page 17]

Internet-Draft  Controlled Delay Active Queue Management   February 2013

11. Acknowledgments

   The authors wish to thank Jim Gettys for constructive nagging, Dave
   Taht and Eric Dumazet for "getting it" and making it real, Andrew
   McGregor for his ns-3 simulation and all those who have expressed
   interest in CoDel.

Authors' Addresses
   Kathleen Nichols
   Pollere, Inc.
   325M Sharon Park Drive #214
   Menlo Park, CA 94025

   Email: nichols@pollere.com


   Van Jacobson
   Google, Inc.
   1600 Amphitheatre Pkwy
   Mountain View, CA 94043

   Email: vanj@google.com




Nichols & Jacobson     Expires August 24, 2013                [Page 18]


Html markup produced by rfcmarkup 1.107, available from http://tools.ietf.org/tools/rfcmarkup/