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

Versions: 00 01 02 draft-ietf-aqm-codel

Transport Area Working Group                                  K. Nichols
Internet-Draft                                             Pollere, Inc.
Intended status: Informational                               V. Jacobson
Expires: January 10, 2013                                     PARC, Inc.
                                                            July 9, 2012


                Controlled Delay Active Queue Management
                     draft-nichols-tsvwg-codel-00.txt

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

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 January 9, 2013.

Copyright Notice


Nichols & Jacobson          Expires: January, 2013          [page  1 ]

INTERNET DRAFT       draft-nichols-tsvwg-codel-00.txt    July, 2012


   Copyright (c) 2012 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 target value................................5
      3.3 About the interval....................................6
      3.4 Use with multiple queues..............................6
      3.5 Use of stochastic bins or sub-queues to improve
               performance......................................6
   4. Annotated Pseudo-code for CoDel...........................7
      4.1 Data Types............................................8
      4.2 Per-queue state (codel_queue_t instance variables)....9
      4.3 Constants.............................................9
      4.4 Enque routine.........................................9
      4.5 Deque routine.........................................9
      4.6 Helper routines......................................11
      4.7 Implementation considerations........................12
   5. CoDel for specialized networks...........................12
   6. Resources and Additional Information.....................13
   7. Security Considerations..................................13
   8. IANA Considerations......................................13
   9. Conclusions..............................................14
   10. References..............................................14
      10.1 Normative References................................14
      10.2 Informative References..............................14
   11. Acknowledgments.........................................15

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

Nichols & Jacobson          Expires: January, 2013          [page  2 ]

INTERNET DRAFT       draft-nichols-tsvwg-codel-00.txt    July, 2012


   why the solution isn't just smaller buffers can be found in [RFC2309,
   VANQ2006, REDL1998, CODEL2012]. It is critical to understand the
   difference between the necessary and useful 'good' queue and the
   counterproductive 'bad' queue.

   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
   o is simple and efficient (easily spans 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, in late April of this year, a number of
   talented and enthusiastic implementers and experimenters have been
   working with CoDel with promising results. 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

Nichols & Jacobson          Expires: January, 2013          [page  3 ]

INTERNET DRAFT       draft-nichols-tsvwg-codel-00.txt    July, 2012


   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.

   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

Nichols & Jacobson          Expires: January, 2013          [page  4 ]

INTERNET DRAFT       draft-nichols-tsvwg-codel-00.txt    July, 2012


   interpretations described below.

   CoDel only enters its dropping state when the local minimum sojourn
   delay has exceeded an acceptable value for standing queue for a time
   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.

3.2. About the target value

   The target value constant is the maximum acceptable standing queue
   delay under a prolonged overload. Our initial focus with CoDel was on
   devices for the ordinary open internet where bottleneck standing
   queues of a few milliseconds are acceptable for ordinary internet
   traffic. We experimented with values between 1 and 20 milliseconds to
   determine a target that gives a 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.

   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.3. About the interval

   The interval constant is loosely related to RTT since it is chosen to
   give endpoints time to react without being so long that response
   times suffer.  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.

Nichols & Jacobson          Expires: January, 2013          [page  5 ]

INTERNET DRAFT       draft-nichols-tsvwg-codel-00.txt    July, 2012



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

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

   We've experimented with an ns-2 simulator version inspired by
   Dumazet's approach with excellent results thus far: median queues
   remain small across a range of traffic patterns than includes
   bidirectional file transfers (that is, the same traffic sent in both
   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 version differs
   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. There may be other minor differences in
   implementation. Andrew McGregor has an ns-3 version of fq_codel and
   we have heard good reports of his results. Implementers should
   consider using this approach if possible. As more experiments are
   completed, future versions of this draft should 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.

   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:


Nichols & Jacobson          Expires: January, 2013          [page  6 ]

INTERNET DRAFT       draft-nichols-tsvwg-codel-00.txt    July, 2012


   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.

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

Nichols & Jacobson          Expires: January, 2013          [page  7 ]

INTERNET DRAFT       draft-nichols-tsvwg-codel-00.txt    July, 2012


   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.

   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);

Nichols & Jacobson          Expires: January, 2013          [page  8 ]

INTERNET DRAFT       draft-nichols-tsvwg-codel-00.txt    July, 2012



       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.  while (now >= drop_next_
        && dropping_) {
            drop(r.p); ++count_; r = dodeque(now); if (!
            r.ok_to_drop) {
                // leave dropping state dropping_ = 0;
            } else {
                // 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); 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_ < 16*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);
   }

Nichols & Jacobson          Expires: January, 2013          [page  9 ]

INTERNET DRAFT       draft-nichols-tsvwg-codel-00.txt    July, 2012



   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() }; 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

Nichols & Jacobson          Expires: January, 2013          [page  10 ]

INTERNET DRAFT       draft-nichols-tsvwg-codel-00.txt    July, 2012


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

   Our ns-2 simulations are available at http://pollere.net/CoDel.html.

Nichols & Jacobson          Expires: January, 2013          [page  11 ]

INTERNET DRAFT       draft-nichols-tsvwg-codel-00.txt    July, 2012


   We continue to do some small experiments and are periodically
   updating the code. 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 the stochastic flow
   binning adapted from Dumazet's fq_codel should be released before the
   Vancouver IETF meeting.

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

   [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.
   [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", MIT Lincoln Labs talk,

Nichols & Jacobson          Expires: January, 2013          [page  12 ]

INTERNET DRAFT       draft-nichols-tsvwg-codel-00.txt    July, 2012


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

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 PARC, Inc.  3333 Coyote Hill Road Palo Alto, CA 94304

   Email: van@parc.com


Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/