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