RFC 8289

Controlled Delay Active Queue Management

📅 published January 2018, from ietf

🎀 RFC 8289: Controlled Delay Active Queue Management 🎀

okay bestie, this one is the CoDel spec and it is SO iconic 💅✨ Honestly the title block is the first thing you need to clock:

  • Who wrote it: K. Nichols (Pollere, Inc.), V. Jacobson, and A. McGregor and J. Iyengar (both listed as Ed., aka editors, at Google) 🫶
  • Category: Experimental 🧪 so it's not an Internet Standards Track spec, it's published for people to examine, try out, and evaluate 👀
  • Stream/ISSN: ISSN: 2070-1721
  • Date: January 2018 📅
  • Obsoletes/Updates: this document doesn't say it obsoletes or updates anything, so there's nothing to report on that front 🌸

Okay so, the Abstract says CoDel is a general framework that controls bufferbloat-generated excess delay in modern networking environments 💖 It has three parts: an estimator, a setpoint, and a control loop 🔥 And the best part? It requires no configuration in normal Internet deployments 😭 no knobs, no fuss, we love a parameterless queen 👑

Status of This Memo ✨

Not a standards track spec, so it's Experimental 🧪 It is an IETF product though, and it's had public review and IESG approval. Not every IESG-approved doc is on the path to becoming an Internet Standard, so see Section 2 of RFC 7841 if you're curious 🦋

The current status, errata, and feedback info lives at https://www.rfc-editor.org/info/rfc8289 🌈

Copyright (c) 2018 IETF Trust and the document authors. All rights reserved 🔒 This doc is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) as of the publication date, so read those carefully about your rights 🫶 Any Code Components pulled out of this doc must include Simplified BSD License text (Section 4.e of the Trust Legal Provisions) and come with no warranty, as the Simplified BSD License describes 💜

Table of Contents

1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
2.  Conventions and Terms Used in This Document . . . . . . . . .   4
3.  Understanding the Building Blocks of Queue Management . . . .   5
  3.1.  Estimator . . . . . . . . . . . . . . . . . . . . . . . .   6
  3.2.  Target Setpoint . . . . . . . . . . . . . . . . . . . . .   8
  3.3.  Control Loop  . . . . . . . . . . . . . . . . . . . . . .  10
4.  Overview of the CoDel AQM . . . . . . . . . . . . . . . . . .  13
  4.1.  Non-starvation  . . . . . . . . . . . . . . . . . . . . .  14
  4.2.  Setting INTERVAL  . . . . . . . . . . . . . . . . . . . .  14
  4.3.  Setting TARGET  . . . . . . . . . . . . . . . . . . . . .  14
  4.4.  Use with Multiple Queues  . . . . . . . . . . . . . . . .  15
  4.5.  Setting Up CoDel  . . . . . . . . . . . . . . . . . . . .  16
5.  Annotated Pseudocode for CoDel AQM  . . . . . . . . . . . . .  16
  5.1.  Data Types  . . . . . . . . . . . . . . . . . . . . . . .  17
  5.2.  Per-Queue State (codel_queue_t Instance Variables)  . . .  17
  5.3.  Constants . . . . . . . . . . . . . . . . . . . . . . . .  17
  5.4.  Enqueue Routine . . . . . . . . . . . . . . . . . . . . .  18
  5.5.  Dequeue Routine . . . . . . . . . . . . . . . . . . . . .  18
  5.6.  Helper Routines . . . . . . . . . . . . . . . . . . . . .  19
  5.7.  Implementation Considerations . . . . . . . . . . . . . .  21
6.  Further Experimentation . . . . . . . . . . . . . . . . . . .  21
7.  Security Considerations . . . . . . . . . . . . . . . . . . .  21
8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  21
9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  22
  9.1.  Normative References  . . . . . . . . . . . . . . . . . .  22
  9.2.  Informative References  . . . . . . . . . . . . . . . . .  22
Appendix A.  Applying CoDel in the Data Center  . . . . . . . . .  24
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  25
Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  25

1. Introduction 🌸

Okay so the "persistently full buffer" problem has been around since the early 80s 😭 [RFC896] The IRTF's End-to-End Research Group called for AQM deployment to fix it in 1998 [RFC2309] and yet, the problem has only gotten worse 💀 Moore's Law kept packing more memory density in, and buffer pools grew exponentially. Deploying AQM has been a struggle because it's hard to configure and it can hurt network utilization. This "bufferbloat" problem [BLOAT] is a big deal across the whole Internet, but it's especially bad at the consumer edge, since people are now mixing huge video streams with time-critical VoIP and gaming on the same connection 🎮📞

An effective AQM fixes bufferbloat at a bottleneck while "doing no harm" at hops where the buffers aren't bloated 🫶 The thing is, people often get the cause of packet queues wrong. Buffers exist to absorb the packet bursts that naturally happen in statistically multiplexed networks ✨ They soak up queues from perfectly reasonable behavior, like short-term mismatches between traffic arrival and departure rates caused by upstream resource contention, transport startup transients, or changes in how many conversations share a link. Other, less useful network behaviors can also fill queues, though, and those effects are not benign 🙈 For the discussion of why the fix isn't just "smaller buffers," check out [RFC2309], [VANQ2006], [REDL1998], and [CODEL2012]. Basically, to understand queue management you have to know the difference between the necessary, useful "good" queue and the counterproductive "bad" queue 💅

Several AQM approaches have come and gone over the past two decades, but none got widely deployed because of performance problems 😩 If you design around the wrong model of queues, AQMs end up with limited operational range, need tons of configuration tweaking, and often make performance worse instead of better. So learning from that history, CoDel is designed to hit these goals:

  • Make AQM parameterless for normal operation, with no knobs for operators, users, or implementers to adjust 🎀
  • Tell "good" queue apart from "bad" queue and treat them differently, so delay stays low while still allowing necessary bursts of traffic 🦋
  • Control delay while being insensitive (or nearly so) to round-trip delays, link rates, and traffic loads. This is the "do no harm" goal 🌈
  • Adapt to dynamically changing link rates with no negative impact on utilization ⭐
  • Allow simple and efficient implementation, from low-end access points and home routers all the way up to high-end router hardware 🧚

CoDel differs from prior AQMs in five major ways: it uses the local queue minimum to track congestion ("bad" queue), it uses one efficient state variable to represent that tracked statistic, it uses packet sojourn time as the observed datum (instead of packets, bytes, or rates), it uses a mathematically determined setpoint derived from maximizing network power [KLEIN81], and it uses a modern state-space controller 🔥

CoDel configures itself from a round-trip time metric that can be set to 100 ms for the normal terrestrial Internet 🍓 With no parameter changes, CoDel is expected to work across a wide range of conditions, with varying links and the full range of terrestrial round-trip times 🌸

CoDel adapts easily to multiple-queue systems, as shown by [RFC8290] 💖 Implementers and users SHOULD use the fq_codel multiple-queue approach, since it handles a bunch of problems that are beyond the reach of an AQM on a single queue 😭

CoDel was first published in [CODEL2012] and has been implemented in the Linux kernel 🐧

Heads up: while this document talks about dropping packets when CoDel indicates it, it may be reasonable to ECN-mark packets instead 🙈

2. Conventions and Terms Used in This Document 🧠

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here 💅

Terms used in this document, defined as follows:

  • sojourn time: the amount of time a packet has spent in a particular buffer, i.e., the time a packet departs the buffer minus the time the packet arrived at the buffer. A packet can depart a buffer via transmission or drop 🦋
  • standing queue: a queue (in packets, bytes, or time delay) in a buffer that persists for a "long" time, where "long" is on the order of the longer round-trip times through the buffer, as discussed in Section 4.2. A standing queue occurs when the minimum queue over the "long" time is non-zero and is usually tolerable and even desirable as long as it does not exceed some target delay 🌈
  • bottleneck bandwidth: the limiting bandwidth along a network path ✨

Part 1 of 6. Keep going, bestie, more coming soon 🫶💖

3. Understanding the Building Blocks of Queue Management ✨

okay bestie, this is the heart of the whole thing 🫶 Queue management is all about spotting the "bad" queue (which only adds delay 😤) and getting rid of it, while keeping the "good" queue (which keeps utilization high 💖). This section walks through queueing, good and bad, plus the CoDel building blocks you can use to manage packet buffers so their queues stay in the "good" range 🦋

Packet queues form in buffers facing bottleneck links, i.e., where the line rate goes from high to low or where many links converge 🚦 The well-known bandwidth-delay product (sometimes called "pipe size") is the bottleneck's bandwidth multiplied by the sender-receiver-sender round-trip delay. It's the amount of data that has to be in transit between two hosts to run the bottleneck link at 100% utilization 💅 To see how queues can form, picture a long-lived TCP connection with a 25-packet window sending through a connection with a bandwidth-delay product of 20 packets. After an initial burst of packets, the connection settles into a 5-packet (+/-1) standing queue. This standing queue size is determined by the mismatch between the window size and the pipe size, and it's unrelated to the connection's sending rate 🤯 The connection has 25 packets in flight at all times, but only 20 packets arrive at the destination over a round-trip time. If the TCP connection has a 30-packet window, the queue will be 10 packets with no change in sending rate. Similarly, if the window is 20 packets, there's no queue, but the sending rate is the same. So nothing can be inferred about the sending rate from the queue size, and any queue other than transient bursts only creates delays in the network. The sender needs to reduce the number of packets in flight rather than the sending rate 🧚

In the above example, the 5-packet standing queue contributes nothing but delay to the connection, so it's clearly "bad" queue 💀 Now say there's a single bottleneck link that's much slower than the link feeding it (like a high-speed Ethernet link into a limited DSL uplink). Then a 20-packet buffer at the bottleneck might be necessary to temporarily hold the 20 packets in flight, so the bottleneck link's utilization stays high 🌈 That burst of packets should drain completely (to 0 or 1 packets) within a round-trip time, and this transient queue is "good" queue because it lets the connection keep its 20 packets in flight while the bottleneck stays fully utilized. In terms of delay, the "good" queue goes away in about a round-trip time, while "bad" queue hangs around for longer and causes delays 😭

Effective queue management detects "bad" queue while ignoring "good" queue, then takes action to get rid of the "bad" queue once it's detected ✨ The goal is a queue controller that pulls this off. To control a queue, we need three basic components:

  • Estimator - To figure out what we've got.
  • Target setpoint - To know what we want.
  • Control loop - If what we've got isn't what we want, we need a way to move it there.

3.1. Estimator

The estimator is the part that observes the queue and detects when "good" queue turns into "bad" queue, and vice versa 👀 CoDel has two parts to its estimator: what gets observed as an indicator of queue, and how those observations are used to detect "good"/"bad" queue.

Queue length has been widely used as an observed indicator of congestion, and it's frequently mixed up with sending rate 🙈 Using queue length as a metric is sensitive to how and when the length is observed. A high-speed arrival link feeding a buffer that's serviced at a much lower rate can quickly build up a queue that might disperse completely, or drop down to a single packet, before a round-trip time has passed. If the queue length is monitored at packet arrival (as in original Random Early Detection (RED)) or at departure time, every packet will see a queue with one possible exception. If the queue length itself is time sampled (as recommended in [REDL1998]), you can get a truer picture of the queue's occupancy, but at the expense of considerable implementation complexity 🥴

Using queue length gets even more complicated in networks that are subject to both short- and long-term changes in available link rate (as in WiFi 📶). Link rate drops can cause a spike in queue length that should be ignored unless it persists. It's not the queue length that should be controlled, but the amount of excess delay packets experience due to a persistent or standing queue. That means the packet sojourn time in the buffer is exactly what we want to track 🎯 Tracking packet sojourn times observes the actual delay each packet experiences. Sojourn time lets queue management be independent of link rate, gives superior performance compared to using buffer size, and is directly related to user-visible performance 👑 It works regardless of line rate changes or link sharing by multiple queues (which the individual queues may experience as changing rates).

Let's look at a link shared by two queues with different priorities. Packets that arrive at the high-priority queue are sent as soon as the link is available, while packets in the other queue have to wait until the high-priority queue is empty (i.e., a strict priority scheduler). The high-priority queue might hold a lot of packets, but it empties quickly, so the time each packet spends enqueued (the sojourn time) isn't large. The other queue might hold fewer packets, but its sojourn times include the waiting time for the high-priority packets to be sent. This makes sojourn time a good sample of the congestion each separate queue is experiencing 🍓 The example also shows that the sojourn time metric is independent of the number of queues or the service discipline used, and is instead indicative of the congestion seen by each individual queue.

So how can observed sojourn time be used to separate "good" queue from "bad" queue? Averages, especially of queue length, have previously been widely used as an indicator of "bad" queue, but their efficacy is questionable 🤔 Consider the burst that disperses every round-trip time. The average queue will be one-half the burst size, though this might vary depending on when the average is computed and the timing of arrivals. The average queue sojourn time would be one-half the time it takes to clear the burst. So the average would indicate a persistent queue where there isn't one 🙅‍♀️ Instead of averages, we recommend tracking the minimum sojourn time. Then, if there's one packet with a zero sojourn time, there is no persistent queue 💜

A persistent queue can be detected by tracking the (local) minimum queue delay packets experience. To make sure this minimum value doesn't go stale, it has to have been experienced recently, i.e., during an appropriate past time interval ⏰ This interval is the maximum amount of time a minimum value is considered to be in effect, and it's related to the amount of time it takes for the largest expected burst to drain. Conservatively, this interval SHOULD be at least a round-trip time, so we don't falsely detect a persistent queue, and not a lot more than a round-trip time, so we don't delay detecting the persistent queue. This suggests that the appropriate interval value is the maximum round-trip time of all the connections sharing the buffer 🦋

Here's the key insight that makes computing the local minimum efficient 🧠 It's enough to keep a single state variable that indicates how long the minimum has been above or below the target value, rather than retaining all the local values to compute the minimum. That means big storage and computational savings. We use this insight in the pseudocode for CoDel later in the document 💅

These two parts, using sojourn time as the observed value and the local minimum as the statistic to monitor queue congestion, are the key to CoDel's estimator building block 🏆 The local minimum sojourn time gives an accurate and robust measure of standing queue and has an efficient implementation. The minimum sojourn time also has important implementation advantages. The minimum packet sojourn can only decrease when a packet is dequeued, which means all of CoDel's work can happen when packets are dequeued for transmission, and no locks are needed in the implementation 🔥 The minimum is the only statistic with this property.

A more detailed explanation with many pictures can be found in [TSV84] 📚🌸

3.2. Target Setpoint ✨

Okay so now that we have a robust way of detecting standing queue 🕵️, we need a target setpoint that tells us when to act. If the controller acts the second the estimator shows anything non-zero, the average drop rate gets maxed out and TCP goodput takes a hit [MACTCP1997] 💀. And this policy leaves zero backlog over time (no persistent queue), which totally wastes the whole point of having a buffer, because it lets the bottleneck link lose bandwidth to normal stochastic variation in packet interarrival time 😭. We want a target that maximizes utilization while minimizing delay, bestie 🎀. Way back in the early days of packet networking, Kleinrock built the analytic machinery to do exactly this, using a quantity he called "power", which is the ratio of a normalized throughput to a normalized delay [KLEIN81] 👑.

It's straightforward to derive an analytic expression for the average goodput of a TCP conversation at a given round-trip time r and target f (where f is expressed as a fraction of r). Reno TCP, for example, yields:

goodput = r (3 + 6f - f^2) / (4 (1+f))

Since the peak queue delay is simply the product of f and r, power is solely a function of f since the r's in the numerator and denominator cancel:

power is proportional to (1 + 2f - 1/3 f^2) / (1 + f)^2

As Kleinrock observed, the best operating point (in terms of bandwidth/delay trade-off) is the peak power point, since points off the peak represent a higher cost (in delay) per unit of bandwidth 🦋. The power vs. f curve for any Additive Increase Multiplicative Decrease (AIMD) TCP is monotone decreasing. But the curve is very flat for f < 0.1, then gets increasing curvature with a knee around f = 0.2, and then does a steep, almost linear fall off [TSV84] 📉. Since the previous equation showed that goodput is monotone increasing with f, the best operating point is near the right edge of the flat top, since that gives the highest goodput achievable for a negligible increase in delay ✨. However, since the r in the model is a conservative upper bound, a target of 0.1r runs the risk of pushing shorter RTT connections over the knee and giving them higher delay for no significant goodput increase 🙈. Generally, a more conservative target of 0.05r offers a good utilization vs. delay trade-off while giving enough headroom to work well with a large variation in real RTT 🌸.

As the above analysis shows, a very small standing queue gives close to 100% utilization of the bottleneck link 🔥. While this result was for Reno TCP, the derivation only uses properties that must hold for any "TCP friendly" transport. We have verified by both analysis and simulation that this result holds for Reno, Cubic, and Westwood [TSV84] 💅. This results in a particularly simple form for the target: the ideal range for the permitted standing queue, or the target setpoint, is between 5% and 10% of the TCP connection's RTT 🍓.

We used simulation to explore the impact when TCPs are mixed with other traffic and with connections of different RTTs 🧚. So we experimented extensively with values in the 5-10% of RTT range and, overall, used target values between 1 and 20 milliseconds for RTTs from 30 to 500 ms and link bandwidths of 64 Kbps to 100 Mbps. The goal was to experimentally find a target that gives consistently high utilization while controlling delay across a range of bandwidths, RTTs, and traffic loads 🫶. Our results were notably consistent with the mathematics above, which is so iconic 🌈.

A congested (but not overloaded) CoDel link with traffic composed solely or primarily of long-lived TCP flows will have a median delay through the link that tends to the target 💜. 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 the target 😬.

The non-starvation drop inhibit feature dominates where the link rate becomes very small. 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, as shown in [CODEL2012] ⭐.

3.3. Control Loop 🔥

Section 3.1 describes a simple, reliable way to measure "bad" (persistent) queue 🫧. Section 3.2 shows that TCP congestion control dynamics give rise to a target setpoint for this measure that's a provably good balance between enhancing throughput and minimizing delay 🎀. Section 3.2 also shows that this target is a constant fraction of the same "largest average RTT" interval used to distinguish persistent from transient queue 💖. The only remaining building block needed for a basic AQM is a "control loop" algorithm to effectively drive the queueing system from any "persistent queue above the target" state to a state where the persistent queue is below the target. That's the whole job, bestie 💅.

Control theory provides a wealth of approaches to the design of control loops 📚. Most of classical control theory deals with the control of linear, time-invariant, Single-Input-Single-Output (SISO) systems. Control loops for these systems generally come from a well-understood class known as Proportional-Integral-Derivative (PID) controllers. Unfortunately, a queue is not a linear system, and an AQM operates at the point of maximum non-linearity (where the output link bandwidth saturates, so increased demand creates delay rather than higher utilization) 😵‍💫. Output queues are also not time invariant, since traffic is generally a mix of connections that start and stop at arbitrary times and that can have radically different behaviors, ranging from "open-loop" UDP audio/video to "closed-loop" congestion-avoiding TCP 🎥. Finally, the constantly changing mix of connections (which can't be converted to a single "lumped parameter" model because of their transfer function differences) makes the system Multi-Input-Multi-Output (MIMO), not SISO. Literally a chaotic group chat 💀.

Since queueing systems match none of the prerequisites for a classical controller, a better approach is a modern state-space controller with "no persistent queue" and "has persistent queue" states 🦋. Since Internet traffic mixtures change rapidly and unpredictably, a noise- and error-tolerant adaptation algorithm like stochastic gradient is a good choice 🌸. Since there's essentially no information in the amount of persistent queue [TSV84], the adaptation should be driven by how long it has persisted ⏳.

Consider the two extremes of traffic behavior: a single, open-loop UDP video stream and a single, long-lived TCP bulk data transfer 🎬. If the average bandwidth of the UDP video stream is greater than the bottleneck link rate, the link's queue will grow, and the controller will eventually enter "has persistent queue" state and start dropping packets. Since the video stream is open loop, its arrival rate is unaffected by drops, so the queue will persist until the average drop rate is greater than the output bandwidth deficit (= average arrival rate - average departure rate). The job of the adaptation algorithm is to discover this rate 🔍. For this example, the adaptation could consist of simply estimating the arrival and departure rates and then dropping at a rate slightly greater than their difference, but this class of algorithm won't work at all for the bulk data TCP stream 🙅‍♀️. TCP runs in closed-loop flow balance [TSV84], so its arrival rate is almost always exactly equal to the departure rate. The queue isn't the result of a rate imbalance, but rather a mismatch between the TCP sender's window and the source-destination-source round-trip path capacity (i.e., the connection's bandwidth-delay product) 🧠. The sender's TCP congestion avoidance algorithm will slowly increase the send window (one packet per round-trip time) [RFC5681], which will eventually cause the bottleneck to enter "has persistent queue" state 📈. But, since the average input rate is the same as the average output rate, the rate deficit estimation that gave the correct drop rate for the video stream would compute a drop rate of zero for the TCP stream 😳. However, if the output link drops one packet as it enters "has persistent queue" state, then when the sender discovers this (via TCP's normal packet loss repair mechanisms), it will reduce its window by a factor of two [RFC5681]. So, one round-trip time after the drop, the persistent queue will go away 🥹✨.

If there were N TCP conversations sharing the bottleneck, the controller would have to drop O(N) packets (one from each conversation) to make all the conversations reduce their window to get rid of the persistent queue 🫠. If the traffic mix consists of short (<= bandwidth-delay product) conversations, the aggregate behavior becomes more like the open-loop video example. That's because each conversation is likely to have already sent all its packets by the time it learns about a drop, so each drop has negligible effect on subsequent traffic 🌷.

The controller does not know the number, duration, or kind of conversations creating its queue, so it has to learn the appropriate response 🧩. Since single drops can have a large effect if the degree of multiplexing (the number of active conversations) is small, dropping at too high a rate is likely to have a catastrophic effect on throughput 💥. Dropping at a low rate (< 1 packet per round-trip time) and then increasing the drop rate slowly until the persistent queue goes below the target is unlikely to overdrop, and is guaranteed to eventually dissipate the persistent queue 🌊. This stochastic gradient learning procedure is the core of CoDel's control loop. The gradient exists because a drop always reduces the (instantaneous) queue, so an increasing drop rate always moves the system "down" toward no persistent queue, regardless of traffic mix 🎯.

The "next drop time" is decreased in inverse proportion to the square root of the number of drops since the drop state was entered. This uses the well-known non-linear relationship of drop rate to throughput to get a linear change in throughput [REDL1998][MACTCP1997] 📐.

Since the best rate to start dropping is at slightly more than one packet per RTT, the controller's initial drop rate can be directly derived from the estimator's interval 🍭. When the minimum sojourn time first crosses the target and CoDel drops a packet, the earliest the controller could see the effect of the drop is the round-trip time (interval) + the local queue wait time (the target). If the next drop happens any earlier than this time (interval + target), CoDel will overdrop 🚫. In practice, the local queue waiting time tends to vary, so making the initial drop spacing (i.e., the time to the second drop) be exactly the minimum possible also leads to overdropping. Analysis of simulation and real-world measured data shows that the 75th percentile magnitude of this variation is less than the target. So the initial drop spacing SHOULD be set to the estimator's interval (i.e., initial drop spacing = interval) to ensure that the controller has accounted for acceptable congestion delays 🫶.

Use of the minimum statistic lets the controller be placed in the dequeue routine with the estimator. This means that the control signal (the drop) can be sent at the first sign of "bad" queue (as indicated by the sojourn time), and that the controller can stop acting as soon as the sojourn time falls below the target 🎉. Dropping at dequeue has both implementation and control advantages, and honestly that's so clean 👑.

4. Overview of the CoDel AQM ✨

Okay bestie, so CoDel was originally built as a bufferbloat fix for the consumer network edge 🏠💖. Its building blocks can adapt to different or time-varying link rates, work with multiple queues, keep utilization excellent with low delay, and stay simple and efficient to implement. Slay 💅.

The CoDel algorithm in the rest of this document runs on two key variables: TARGET, the controller's target setpoint from Section 3.2, and INTERVAL, the estimator's interval from Section 3.3 🎯.

The only setting CoDel needs is INTERVAL, and since 100 ms fits that definition for normal Internet usage, CoDel can be parameter-free for consumers 🎀. To keep link utilization from taking a hit, CoDel's estimator sets TARGET to whatever value optimizes power ⚡. CoDel's controller won't drop a packet if the drop would leave the queue empty or with less than one Maximum Transmission Unit (MTU) worth of bytes in the buffer 🙅. Section 3.2 shows the ideal TARGET is 5-10% of the connection round-trip time (RTT). On the open terrestrial Internet, especially at the consumer edge, we expect most unbloated RTTs to top out at 100 ms [CHARB2007]. Using that RTT gives a minimum TARGET of 5 ms and an INTERVAL of 100 ms. In practice, uncongested links see sojourn times below TARGET more often than once per RTT, so the estimator isn't overly sensitive to the value of INTERVAL 🦋.

When the estimator finds a persistent delay above TARGET, the controller enters the drop state, drops a packet, and sets the next drop time 💥. As covered in Section 3.3, the initial next drop spacing is meant to be long enough for endpoints to react to that single drop, so it SHOULD be set to a value equal to INTERVAL. If the estimator's output falls below TARGET, the controller cancels the next drop and exits the drop state. (The controller is more sensitive than the estimator to an overly short INTERVAL, since an unnecessary drop would happen and lower link utilization 📉.) If the next drop time arrives while the controller is still in the drop state, the packet being dequeued gets dropped and the next drop time gets recalculated ⏭️.

There's extra logic that stops CoDel from re-entering the drop state too soon after leaving it, and that lets it pick up the drop state at a recent control level if one exists 🔄. This logic is described more precisely in the pseudocode below. Figuring out how often and how much re-entering the drop state matters still needs more work 🤔.

Also, CoDel AQM only enters its drop state once the local minimum sojourn delay has stayed above TARGET long enough for normal bursts to clear out 🌊. That way, a burst of packets that fits in the pipe won't get dropped. Main character restraint 👑.

4.1. Non-starvation

CoDel's goals are to control delay with little or no impact on link utilization, and to work on a wide range of link bandwidths, including variable-rate links, without any reconfiguration 🎯. To avoid drops that would starve the output link, CoDel does one more check before dropping: is at least an MTU worth of bytes still left in the buffer? If not, the packet SHOULD NOT be dropped, so CoDel exits the drop state 🙅‍♀️. The MTU size can be set adaptively to the largest packet seen so far, or read from the interface driver 📦.

4.2. Setting INTERVAL

INTERVAL is picked to give endpoints time to react to a drop without making response times suffer ⏰. CoDel's estimator, TARGET, and control loop all use INTERVAL. Checking how it's derived shows that CoDel is most sensitive to INTERVAL for a single long-lived TCP, and less sensitive for traffic mixes. That's lucky, because RTTs vary across connections and aren't known a priori 🙌.

The best policy seems to be an INTERVAL slightly larger than the RTT seen by most connections using a link. That value can be found as the largest RTT seen, as long as it isn't an outlier (a 95-99th percentile value should work) 🔍. In practice, this value isn't known or measured (but see Appendix A for an application where INTERVAL is measured). An INTERVAL of 100 ms works well across RTTs from 10 ms to 1 second, and excellent performance happens between 10 ms and 300 ms 🌈.

For devices intended for the normal terrestrial Internet, INTERVAL SHOULD have a value of 100 ms. This only causes overdropping when a long-lived TCP has an RTT longer than 100 ms and there's little or no mixing with other connections through the link 💅.

4.3. Setting TARGET

TARGET is the maximum acceptable persistent queue delay. Above it, CoDel is dropping or getting ready to drop, and below it, CoDel won't drop 🎀. TARGET SHOULD be set to 5 ms for normal Internet traffic.

The calculations in Section 3.2 show the best TARGET is 5-10% of the RTT, with the low end of 5% preferred 📐. Extensive simulations of different TARGET values with mixed traffic flows (different RTTs and different bandwidths) showed that below a TARGET of 5 ms, utilization suffers for some conditions and traffic loads. Above 5 ms, there was very little or no improvement in utilization 📊.

Sojourn times must stay above TARGET for INTERVAL amount of time before CoDel enters the drop state. Any packet with a sojourn time less than TARGET resets the time the queue was last below TARGET 🔁. Internet traffic is super dynamic, so the actual sojourn delay packets experience varies a lot and is often less than TARGET, unless the overload is excessive. When a link isn't overloaded, it isn't a bottleneck, and packet sojourn times are small or nonexistent 😌.

In the usual case, only one or two places along a path are bottlenecks (usually at the edge), so the total amount of queueing delay a packet experiences should be less than 10 ms, even under extremely congested conditions. This net delay is substantially lower than the common queueing delays on the Internet today, which grow to orders of seconds [NETAL2010] [CHARB2007] 🤯.

Regarding the roles of TARGET and the minimum-tracking INTERVAL: TARGET SHOULD NOT be increased in response to lower layers with a bursty nature, where packets are transmitted for short periods, interspersed with idle periods where the link is waiting for permission to send 🚦. CoDel's estimator will "see" the effective transmission rate over an INTERVAL amount of time, and increasing TARGET only leads to longer queue delays 😬.

On the other hand, where a significant additional delay is added to the intrinsic RTT of most or all packets due to waiting for a transmission, it is necessary to increase INTERVAL by that extra delay. TARGET SHOULD NOT be adjusted for such short-term bursts, but INTERVAL MAY need to be adjusted if the path's intrinsic RTT changes 🧠.

4.4. Use with Multiple Queues

CoDel adapts easily to multiple-queue systems 🧩. With other approaches, there's always the question of how to account for the fact that each queue gets less than the full link rate over time, and usually sees a varying rate over time. This is what CoDel excels at: using a packet's sojourn time in the buffer completely sidesteps this problem ✨.

In a multiple-queue setting, a separate CoDel algorithm runs on each queue, but each CoDel instance 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 does a multiple-queue CoDel system 🎢. As an optimization to avoid queueing more than necessary, when testing queue occupancy before dropping, the total occupancy of all queues sharing the same output link SHOULD be used.

This property has been exploited in fq_codel [RFC8290], which hashes on packet header fields to determine a specific bin, or sub-queue, for each packet. It runs CoDel on each bin or sub-queue, which creates a well-mixed output flow and gets rid of issues with reverse path flows (including "ack compression") 🫶.

4.5. Setting Up CoDel

CoDel is set up for devices on the open Internet 🌐. An INTERVAL setting of 100 ms is used, TARGET is set to 5% of INTERVAL, and the initial drop spacing is also set to INTERVAL. These settings were chosen so that a device, such as a small WiFi router, can be sold without any values needing to be adjustable, which gives a parameterless implementation 🛜.

CoDel is also useful in environments with significantly different characteristics from the normal Internet, for example 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 <100 us) but bandwidths are high (1-40 Gbps). That makes it relatively easy for the aggregation phase of a distributed computation (e.g., the Reduce part of a Map/Reduce) to persistently fill, and 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 Explicit Congestion Notification (ECN) marks while keeping throughput high and latency low ⚡.

Devices destined for these environments MAY use a different value for INTERVAL, where suitable. If appropriate analysis indicates, the TARGET MAY be set to some other value in the 5-10% of INTERVAL, and the initial drop spacing MAY be set to a value of 1.0 to 1.2 times INTERVAL. But these settings will cause problems, such as overdropping and low throughput, if used on the open Internet. So devices that allow CoDel to be configured SHOULD default to the Internet-appropriate values given in this document 🙏.

5. Annotated Pseudocode for CoDel AQM 🧁

What follows is the CoDel algorithm in C++-like pseudocode. Since CoDel adds relatively little new code to a basic tail-drop FIFO queue, we've highlighted just these additions by presenting CoDel as a sub-class of a basic FIFO queue base class 🍓. The reference code is included to help implementers who want to apply CoDel to queue management as described here, or to adapt its principles to other applications.

Implementors are strongly encouraged to also look at the Linux kernel version of CoDel, a well-written, well-tested, real-world, C-based implementation 🐧. As of this writing, it's available at https://github.com/torvalds/linux/blob/master/net/sched/sch_codel.c.

5.1. Data Types

time_t is an integer time value in units convenient for the system 🕰️. 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 the field is available for use by CoDel. It gets set by the enqueue routine and used by the dequeue routine 📦.

queue_t is a base class for queue objects (the parent class for codel_queue_t objects). We assume it has enqueue() and dequeue() 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 dequeue() method, but it shouldn't require a lock with the enqueue() method 🔐.

flag_t is a Boolean 💜.

5.2. Per-Queue State 📓

Okay so this is CoDel's little notebook 📓 for each queue. It keeps track of when things first went above the limit, when the next drop is due, and how many drops have happened so far. Literally the whole memory of the algorithm, and it's surprisingly small 🥹

time_t first_above_time_ = 0; // Time to declare sojourn time above
                              // TARGET
time_t drop_next_ = 0;        // Time to drop next packet
uint32_t count_ = 0;          // Packets dropped in drop state
uint32_t lastcount_ = 0;      // Count from previous iteration
flag_t dropping_ = false;     // Set to true if in drop state

5.3. Constants 🎀

These are the main numbers, and they're the ones the whole thing is built around 💅 TARGET is the 5 ms queue delay CoDel is aiming for, and INTERVAL is the 100 ms sliding-minimum window. There's also a maxpacket value that comes with a little reminder about the interface MTU.

time_t TARGET = MS2TIME(5);     // 5 ms TARGET queue delay
time_t INTERVAL = MS2TIME(100); // 100 ms sliding-minimum window
u_int maxpacket = 512;          // Maximum packet size in bytes
                                // (SHOULD use interface MTU)

5.4. Enqueue Routine 🧚

Bestie, the enqueue side is so chill 🫶 All the real work happens in the dequeue routine. CoDel's only addition to enqueue is stamping the current time onto the packet's tstamp field, so dequeue can figure out the packet's sojourn time later.

Also, packets that show up when the buffer is already full get dropped, but those drops don't count toward CoDel's computations. That's giving "not my problem" energy 💅

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

5.5. Dequeue Routine 💖

This is the heart of CoDel and I'm obsessed 😭 There are two branches, and which one runs depends on whether the controller is already in drop state. If it is, the minimum sojourn time is above TARGET, so the controller either checks whether it's time to leave drop state or schedules the next drop(s). If it isn't, the controller decides whether to enter drop state and do the first drop.

packet_t* CoDelQueue::dequeue()
{
    time_t now = clock();
    dodequeue_result r = dodequeue(now);
    uint32_t delta;

    if (dropping_) {
        if (! r.ok_to_drop) {
            // sojourn time below TARGET - leave drop state
            dropping_ = false;
        }
        // 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 = dodequeue(now);
            if (! r.ok_to_drop) {
                // leave drop state
                dropping_ = false;

            } else {
                // schedule the next drop.
                drop_next_ = control_law(drop_next_, count_);
            }
        }
    // If we get here, we're not in drop state.  The 'ok_to_drop'
    // return from dodequeue means that the sojourn time has been
    // above 'TARGET' for 'INTERVAL', so enter drop state.
    } else if (r.ok_to_drop) {
        drop(r.p);
        r = dodequeue(now);
        dropping_ = true;

        // 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.) Implementations vary slightly here; this is
        // the Linux version, which is more widely deployed and
        // tested.
        delta = count_ - lastcount_;
        count_ = 1;
        if ((delta > 1) && (now - drop_next_ < 16*INTERVAL))
            count_ = delta;

        drop_next_ = control_law(now, count_);
        lastcount_ = count_;
    }
    return (r.p);
}

5.6. Helper Routines 🦋

So here's the vibe. CoDel doesn't know how many flows are multiplexed or what the traffic looks like, so it acts like a closed-loop servo 🧚 It keeps increasing how often it drops until the queue is under control, meaning sojourn time goes back below TARGET. The control law is what runs that servo, and it has this shape because of the sqrt(p) dependence of TCP throughput on drop probability. Iconic math behavior 🔥 For embedded systems or kernel implementations, the inverse sqrt can be computed efficiently using only integer multiplication, which is very slay for tiny devices.

time_t codel_queue_t::control_law(time_t t, uint32_t count)
{
    return t + INTERVAL / sqrt(count);
}

Next up is the helper that does the actual packet dequeue. It keeps track of whether sojourn time is above or below TARGET and, if it's above, whether it has stayed above continuously for at least INTERVAL. It returns two things: a Boolean saying whether it's OK to drop (sojourn time above TARGET for at least INTERVAL), and the packet that was dequeued.

typedef struct {
    packet_t* p;
    flag_t ok_to_drop;
} dodequeue_result;
dodequeue_result codel_queue_t::dodequeue(time_t now)
{
    dodequeue_result r = { queue_t::dequeue(), false };
    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 based on sojourn time
    // 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 based on backlog 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 = true;
        }
    }
    return r;
}

5.7. Implementation Considerations 🛠️

Quick tea on time_t ☕ It's an integer time value in whatever units are 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}, so there's still enough dynamic range to represent a wide range of queue waiting times. Narrower widths get messy with overflow (wrapping) and underflow (limit cycles because of truncation to zero), and this pseudocode doesn't address those 🙈

The good news is that CoDel needs relatively little per-queue state and no direct communication or state sharing between the enqueue and dequeue routines. That makes it pretty easy to add CoDel to almost any packet processing pipeline, including forwarding engines built on Application-Specific Integrated Circuits (ASICs) or Network Processors (NPUs) 🌈

One thing to think about is dodequeue()'s use of a bytes() function to find the current queue size in bytes. That value doesn't need to be exact. If the enqueue side keeps a running count of the total bytes it has put into the queue, and the dequeue routine keeps a running count of the total bytes it has removed, then bytes() is just the difference between those two counters (32-bit counters should be adequate). Enqueue only has to update its counter once per packet queued, and it doesn't matter when it does it (before, during, or after the packet has been added to the queue). The worst case is a slight, transient underestimate of the queue size, which might cause a drop to be briefly deferred 🫠

6. Further Experimentation 🧪

We really want people to play around with the recommended values of TARGET and INTERVAL for Internet settings 💜 CoDel gives you general, efficient, parameterless building blocks for queue management. They can be applied to single or multiple queues across a bunch of data networking scenarios. And if you're working on a special-purpose networking application, CoDel's settings may be modified for it ✨

7. Security Considerations 🔐

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

8. IANA Considerations 🧚

This document does not require actions by IANA. Nothing for IANA to do here, so it's a chill section 🌸

9. References 📚

9.1. Normative References

9.2. Informative References ✨

Okay bestie, these are the "extra reading" sources 📚🎀 They aren't required to implement this, but they're where the drama and the receipts live, so here's the full list:

  • [BLOAT] Gettys, J. and K. Nichols, "Bufferbloat: Dark Buffers in the Internet", Communications of the ACM, Volume 55, Issue 1, DOI 10.1145/2063176.2063196, January 2012. 🖤
  • [CHARB2007] Dischinger, M., Haeberlen, A., Gummadi, K., and S. Saroiu, "Characterizing Residential Broadband Networks", Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, DOI 10.1145/1298306.1298313, October 2007. 🌐
  • [CODEL2012] Nichols, K. and V. Jacobson, "Controlling Queue Delay", ACM Queue, Volume 10, Issue 5, DOI 10.1145/2208917.2209336, May 2012. 💖
  • [KLEIN81] Kleinrock, L. and R. Gail, "An Invariant Property of Computer Network Power", Proceedings of the International Conference on Communications, June 1981, http://www.lk.cs.ucla.edu/data/files/Gail/power.pdf. 🧚
  • [MACTCP1997] Mathis, M., Semke, J., Mahdavi, J., and T. Ott, "The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm", ACM SIGCOMM Computer Communications Review, Volume 27, Issue 3, pp. 67-82, DOI 10.1145/263932.264023, July 1997. 📈
  • [NETAL2010] Kreibich, C., Weaver, N., Paxson, V., and B. Nechaev, "Netalyzr: Illuminating the Edge Network", Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement, DOI 10.1145/1879141.1879173, November 2010. 🔍
  • [REDL1998] Nichols, K., Jacobson, V., and K. Poduri, "RED in a Different Light", Technical Report, Cisco Systems, September 1999, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.9406. 💜
  • [RFC896] Nagle, J., "Congestion Control in IP/TCP Internetworks", RFC 896, DOI 10.17487/RFC0896, January 1984, https://www.rfc-editor.org/info/rfc896. 👑
  • [RFC2309] Braden, B., Clark, D., Crowcroft, J., Davie, B., Deering, S., Estrin, D., Floyd, S., Jacobson, V., Minshall, G., Partridge, C., Peterson, L., Ramakrishnan, K., Shenker, S., Wroclawski, J., and L. Zhang, "Recommendations on Queue Management and Congestion Avoidance in the Internet", RFC 2309, DOI 10.17487/RFC2309, April 1998, https://www.rfc-editor.org/info/rfc2309. 🌸
  • [RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion Control", RFC 5681, DOI 10.17487/RFC5681, September 2009, https://www.rfc-editor.org/info/rfc5681. ✨
  • [RFC8290] Hoeiland-Joergensen, T., McKenney, P., Taht, D., Gettys, J., and E. Dumazet, "The Flow Queue CoDel Packet Scheduler and Active Queue Management Algorithm", RFC 8290, DOI 10.17487/RFC8290, January 2018, https://www.rfc-editor.org/info/rfc8290. 🦋 This one is the sibling that's giving main character energy with CoDel, so read it next!
  • [TSV84] Jacobson, V., "CoDel", IETF 84, Transport Area Open Meeting, July 2012, http://www.ietf.org/proceedings/84/slides/slides-84-tsvarea-4.pdf. 🎤
  • [VANQ2006] Jacobson, V., "A Rant on Queues", Talk at MIT Lincoln Labs, Lexington, MA, July 2006, http://www.pollere.net/Pdfdocs/QrantJul06.pdf. 🍓 The legendary rant. Iconic.

Appendix A. Applying CoDel in the Data Center 🏢💅

Okay so Nandita Dukkipati and her group at Google realized that the CoDel building blocks weren't just for Internet routers. They could totally slay bufferbloat problems in data-center servers too 🔥 The Linux CoDel queueing discipline (qdisc) got adapted in three ways to tackle this, and honestly the glow-up is real.

  1. The default CoDel action got a makeover: it became direct feedback from qdisc to the TCP layer at dequeue. That feedback just shrinks TCP's congestion window, the same thing congestion control would do after a drop. ✂️ If the TCP socket lock couldn't be grabbed at dequeue, the scheme falls back to ECN marking or packet drop instead.
  2. Being on the server means you can actually monitor the real RTT and use that as CoDel's interval, instead of taking a "best guess" at RTT 🙈 The CoDel interval is adjusted dynamically using the maximum TCP round-trip time (RTT) of the connections sharing the same qdisc/bucket. There's a history entry of the maximum RTT seen over the last second. As each packet is dequeued, its RTT estimate gets read from its TCP socket. If that estimate is bigger than the current CoDel interval, the interval gets refreshed to the new value right away. If the CoDel interval hasn't been refreshed for over a second, it drops down to the history entry, and the whole process repeats. This is why the dynamic TCP RTT estimate is so iconic: the interval adapts to the actual maximum value currently seen, so the controller spaces its drop intervals appropriately. 🧚‍♀️
  3. Since the mathematics of computing the setpoint are invariant, a TARGET of 5% of the RTT or CoDel interval was used here. 🎯

Non-data packets were not dropped, because they're typically small and sometimes critical control packets. Protect the vibes! 🛡️ And since everything lives on the server, there's no concern with misbehaving users like there would be on the public Internet. Safe space 🫶

In several data-center workload benchmarks, which are typically bursty, CoDel reduced queueing latencies at the qdisc and improved the mean and 99th-percentile latencies from several tens of milliseconds to less than one millisecond. Literally from tens of milliseconds down to under one! 😭🔥 The minimum tracking part of the CoDel framework was also useful for telling a "good" queue apart from a "bad" queue, which is especially helpful for controlling qdisc buffers that are inherently bursty because of TCP Segmentation Offload (TSO). 💀

Acknowledgments 🌈

The authors thank Jim Gettys for the constructive nagging that made them get the work "out there" before they thought it was ready. Iconic behavior 🙌 They also thank Dave Taht, Eric Dumazet, and the open source community for showing the value of getting it "out there" and for making it real. ✨ They thank Nandita Dukkipati for contributions to Section 6 and for comments that helped substantially improve this document 💜 And finally, they thank the AQM Working Group and the Transport Area Shepherd, Wes Eddy, for patiently prodding this document all the way to publication as an RFC. Patience is a whole vibe 🦋

Authors' Addresses 📮

Kathleen Nichols Pollere, Inc. PO Box 370201 Montara, CA 94037 United States of America

Email: nichols@pollere.com

Van Jacobson Google

Email: vanj@google.com

Andrew McGregor (editor) Google

Email: andrewmcgr@google.com

Janardhan Iyengar (editor) Google

Email: jri@google.com

📦 where this page comes from