diff options
Diffstat (limited to 'doc/rfc/rfc8289.txt')
| -rw-r--r-- | doc/rfc/rfc8289.txt | 1403 |
1 files changed, 1403 insertions, 0 deletions
diff --git a/doc/rfc/rfc8289.txt b/doc/rfc/rfc8289.txt new file mode 100644 index 0000000..dc58d3e --- /dev/null +++ b/doc/rfc/rfc8289.txt @@ -0,0 +1,1403 @@ + + + + + + +Internet Engineering Task Force (IETF) K. Nichols +Request for Comments: 8289 Pollere, Inc. +Category: Experimental V. Jacobson +ISSN: 2070-1721 A. McGregor, Ed. + J. Iyengar, Ed. + Google + January 2018 + + + Controlled Delay Active Queue Management + +Abstract + + This document describes CoDel (Controlled Delay) -- a general + framework that controls bufferbloat-generated excess delay in modern + networking environments. CoDel consists of an estimator, a setpoint, + and a control loop. It requires no configuration in normal Internet + deployments. + +Status of This Memo + + This document is not an Internet Standards Track specification; it is + published for examination, experimental implementation, and + evaluation. + + This document defines an Experimental Protocol for the Internet + community. This document is a product of the Internet Engineering + Task Force (IETF). It represents the consensus of the IETF + community. It has received public review and has been approved for + publication by the Internet Engineering Steering Group (IESG). Not + all documents approved by the IESG are a candidate for any level of + Internet Standard; see Section 2 of RFC 7841. + + Information about the current status of this document, any errata, + and how to provide feedback on it may be obtained at + https://www.rfc-editor.org/info/rfc8289. + + + + + + + + + + + + + + + +Nichols, et al. Experimental [Page 1] + +RFC 8289 CoDel January 2018 + + +Copyright Notice + + Copyright (c) 2018 IETF Trust and the persons identified as the + document authors. All rights reserved. + + This document is subject to BCP 78 and the IETF Trust's Legal + Provisions Relating to IETF Documents + (https://trustee.ietf.org/license-info) in effect on the date of + publication of this document. Please review these documents + carefully, as they describe your rights and restrictions with respect + to this document. Code Components extracted from this document must + include Simplified BSD License text as described in Section 4.e of + the Trust Legal Provisions and are provided without warranty as + described in the Simplified BSD License. + +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 + + + + + +Nichols, et al. Experimental [Page 2] + +RFC 8289 CoDel January 2018 + + +1. Introduction + + The "persistently full buffer" problem has been discussed in the IETF + community since the early 80s [RFC896]. The IRTF's End-to-End + Research Group called for the deployment of Active Queue Management + (AQM) to solve the problem in 1998 [RFC2309]. Despite this + awareness, the problem has only gotten worse as growth in memory + density per Moore's Law fueled an exponential increase in buffer pool + size. Efforts to deploy AQM have been frustrated by difficult + configuration and negative impact on network utilization. This + "bufferbloat" problem [BLOAT] has become increasingly important + throughout the Internet but particularly at the consumer edge. Queue + management has become more critical due to increased consumer use of + the Internet, mixing large video transactions with time-critical VoIP + and gaming. + + An effective AQM remediates bufferbloat at a bottleneck while "doing + no harm" at hops where buffers are not bloated. However, the + development and deployment of AQM are frequently subject to + misconceptions about the cause of packet queues in network buffers. + Network buffers exist to absorb the packet bursts that occur + naturally in statistically multiplexed networks. Buffers helpfully + absorb the queues created by reasonable packet network behavior such + as 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. Unfortunately, other less useful network behaviors + can cause queues to fill, and their effects are not nearly as benign. + Discussion of these issues and the reason why the solution is not + simply "smaller buffers" can be found in [RFC2309], [VANQ2006], + [REDL1998], and [CODEL2012]. To understand queue management, it is + critical to understand the difference between the necessary, useful + "good" queue and the counterproductive "bad" queue. + + Several approaches to AQM have been developed over the past two + decades, but none have 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. + Learning from this past history, the CoDel approach is designed to + meet the following goals: + + o Make AQM parameterless for normal operation, with no knobs for + operators, users, or implementers to adjust. + + o Be able to distinguish "good" queue from "bad" queue and treat + them differently, that is, keep delay low while permitting + necessary bursts of traffic. + + + +Nichols, et al. Experimental [Page 3] + +RFC 8289 CoDel January 2018 + + + o Control 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 Adapt to dynamically changing link rates with no negative impact + on utilization. + + o Allow simple and efficient implementation (can easily span the + spectrum from low-end access points and home routers up to high- + end router hardware). + + CoDel has five major differences from prior AQMs: use of the local + queue minimum to track congestion ("bad" queue), use of an efficient + single state variable representation of that tracked statistic, use + of packet sojourn time as the observed datum (rather than packets, + bytes, or rates), use of a mathematically determined setpoint derived + from maximizing network power [KLEIN81], and a modern state-space + controller. + + CoDel configures itself based on a round-trip time metric that can be + set to 100 ms for the normal, terrestrial Internet. With no changes + to parameters, CoDel is expected to work across a wide range of + conditions, with varying links and the full range of terrestrial + round-trip times. + + CoDel is easily adapted to multiple queue systems as shown by + [RFC8290]. Implementers and users SHOULD use the fq_codel multiple- + queue approach as it deals with many problems beyond the reach of an + AQM on a single queue. + + CoDel was first published in [CODEL2012] and has been implemented in + the Linux kernel. + + Note that while this document refers to dropping packets when + indicated by CoDel, 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. + + + + + + + + +Nichols, et al. Experimental [Page 4] + +RFC 8289 CoDel January 2018 + + + The following terms are used in this document and are 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. + +3. Understanding the Building Blocks of Queue Management + + At the heart of queue management is the notion of "good" queue and + "bad" queue and the search for ways to get rid of the "bad" queue + (which only adds delay) while preserving the "good" queue (which + provides for good utilization). This section explains queueing, both + good and bad, and covers the CoDel building blocks that can be used + to manage packet buffers to keep their queues 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 is the amount of data that has to be in + transit between two hosts in order to run the bottleneck link at 100% + utilization. To explore how queues can form, consider 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 will settle 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 is 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 will be no queue, but + the sending rate is the same. 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. + + + +Nichols, et al. Experimental [Page 5] + +RFC 8289 CoDel January 2018 + + + In the above example, the 5-packet standing queue can be seen to + contribute nothing but delay to the connection and thus is clearly + "bad" queue. If, in our example, there is a single bottleneck link + and it is much slower than the link that feeds it (say, 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 to keep the bottleneck link's utilization high. The 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 + allows the connection to keep the 20 packets in flight and the + bottleneck link to be fully utilized. In terms of the delay + experienced, the "good" queue goes away in about a round-trip time, + while "bad" queue hangs around for longer, causing delays. + + Effective queue management detects "bad" queue while ignoring "good" + queue and takes action to get rid of the "bad" queue when it is + detected. The goal is a queue controller that accomplishes this + objective. To control a queue, we need three basic components: + + o Estimator - To figure out what we've got. + + o Target setpoint - To know what we want. + + o 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 both observes the queue and detects when "good" queue + turns to "bad" queue and vice versa. CoDel has two parts to its + estimator: what is observed as an indicator of queue and how the + observations are used to detect "good"/"bad" queue. + + Queue length has been widely used as an observed indicator of + congestion and is frequently conflated with sending rate. Use of + queue length as a metric is sensitive to how and when the length is + observed. A high-speed arrival link to a buffer serviced at a much + lower rate can rapidly build up a queue that might disperse + completely or down to a single packet before a round-trip time has + elapsed. If the queue length is monitored at packet arrival (as in + original Random Early Detection (RED)) or departure time, every + packet will see a queue with one possible exception. If the queue + length itself is time sampled (as recommended in [REDL1998]), a truer + picture of the queue's occupancy can be gained at the expense of + considerable implementation complexity. + + + + + + +Nichols, et al. Experimental [Page 6] + +RFC 8289 CoDel January 2018 + + + The use of queue length is further complicated in networks that are + subject to both short- and long-term changes in available link rate + (as in WiFi). Link rate drops can result in a spike in queue length + that should be ignored unless it persists. It is not the queue + length that should be controlled but the amount of excess delay + packets experience due to a persistent or standing queue, which means + that the packet sojourn time in the buffer is exactly what we want to + track. Tracking the packet sojourn times in the buffer observes the + actual delay experienced by each packet. Sojourn time allows queue + management to be independent of link rate, gives superior performance + to use of 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). + + Consider 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 number of packets in the high-priority queue might + be large, but the queue is emptied quickly, and the amount of time + each packet spends enqueued (the sojourn time) is not large. The + other queue might have a smaller number of packets, but packet + sojourn times will include the waiting time for the high-priority + packets to be sent. This makes the sojourn time a good sample of the + congestion that each separate queue is experiencing. This example + also shows how the metric of sojourn time is independent of the + number of queues or the service discipline used and is instead + indicative of congestion seen by the individual queues. + + How can observed sojourn time be used to separate "good" queue from + "bad" queue? Although averages, especially of queue length, have + previously been widely used as an indicator of "bad" queue, 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. The average then would + indicate a persistent queue where there is none. Instead of + averages, we recommend tracking the minimum sojourn time; then, if + there is one packet that has 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 ensure that this minimum value + does not become 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 + + + +Nichols, et al. Experimental [Page 7] + +RFC 8289 CoDel January 2018 + + + and is 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 to avoid falsely detecting a persistent queue + and not a lot more than a round-trip time to avoid delay in detecting + the persistent queue. This suggests that the appropriate interval + value is the maximum round-trip time of all the connections sharing + the buffer. + + Note that the following key insight makes computation of the local + minimum efficient: it is sufficient 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, which leads to both storage and computational savings. + We use this insight in the pseudocode for CoDel later in the + document. + + These two parts, use of sojourn time as the observed value and the + local minimum as the statistic to monitor queue congestion, are key + to CoDel's estimator building block. The local minimum sojourn time + provides an accurate and robust measure of standing queue and has an + efficient implementation. In addition, use of the minimum sojourn + time 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. + + A more detailed explanation with many pictures can be found in + [TSV84]. + +3.2. Target Setpoint + + 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 is set + to take action as soon as the estimator has a non-zero value, the + average drop rate will be maximized, which minimizes TCP goodput + [MACTCP1997]. Also, this policy results in no backlog over time (no + persistent queue), which negates much of the value of having a + buffer, since it maximizes the bottleneck link bandwidth lost due to + normal stochastic variation in packet interarrival time. We want a + target that maximizes utilization while minimizing delay. Early in + the history of packet networking, Kleinrock developed the analytic + machinery to do this using a quantity he called "power", which is the + ratio of a normalized throughput to a normalized delay [KLEIN81]. + + + + + + + +Nichols, et al. Experimental [Page 8] + +RFC 8289 CoDel January 2018 + + + It is 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, followed by an increasing curvature with a knee + around f = 0.2, then 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 represents 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 uses only 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. Accordingly, + 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 to + experimentally explore a value for the target that gives consistently + + + + + +Nichols, et al. Experimental [Page 9] + +RFC 8289 CoDel January 2018 + + + high utilization while controlling delay across a range of + bandwidths, RTTs, and traffic loads. Our results were notably + consistent with the mathematics above. + + 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 will tend 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 gives 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. + + 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. + + + + + +Nichols, et al. Experimental [Page 10] + +RFC 8289 CoDel January 2018 + + + 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, 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 since 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. + + + +Nichols, et al. Experimental [Page 11] + +RFC 8289 CoDel January 2018 + + + 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, using + 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. + + + + + + + + + +Nichols, et al. Experimental [Page 12] + +RFC 8289 CoDel January 2018 + + +4. Overview of the CoDel AQM + + CoDel was initially designed as a bufferbloat solution for the + consumer network edge. The CoDel building blocks are able to adapt + to different or time-varying link rates, be easily used with multiple + queues, have excellent utilization with low delay, and have a simple + and efficient implementation. + + The CoDel algorithm described in the rest of this document uses two + key variables: TARGET, which is the controller's target setpoint + described in Section 3.2, and INTERVAL, which is the estimator's + interval described in Section 3.3. + + The only setting CoDel requires is the INTERVAL value, and as 100 ms + satisfies that definition for normal Internet usage, CoDel can be + parameter-free for consumer use. To ensure that link utilization is + not adversely affected, CoDel's estimator sets TARGET to one that + optimizes power. CoDel's controller does not drop packets when the + drop would leave the queue empty or with fewer than a Maximum + Transmission Unit (MTU) worth of bytes in the buffer. Section 3.2 + shows that an ideal TARGET is 5-10% of the connection round-trip time + (RTT). In the open terrestrial-based Internet, especially at the + consumer edge, we expect most unbloated RTTs to have a ceiling of 100 + ms [CHARB2007]. Using this RTT gives a minimum TARGET of 5 ms and + INTERVAL of 100 ms. In practice, uncongested links will see sojourn + times below TARGET more often than once per RTT, so the estimator is + not overly sensitive to the value of INTERVAL. + + When the estimator finds a persistent delay above TARGET, the + controller enters the drop state where a packet is dropped, and the + next drop time is set. As discussed in Section 3.3, the initial next + drop spacing is intended to be long enough to give the endpoints time + to react to the single drop and therefore 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 value, since an unnecessary drop would occur and lower link + utilization). If the next drop time is reached while the controller + is still in drop state, the packet being dequeued is dropped, and the + next drop time is recalculated. + + Additional logic prevents re-entering the drop state too soon after + exiting it and resumes the drop state at a recent control level, if + one exists. This logic is described more precisely in the pseudocode + below. Additional work is required to determine the frequency and + importance of re-entering the drop state. + + + + + +Nichols, et al. Experimental [Page 13] + +RFC 8289 CoDel January 2018 + + + Note that CoDel AQM only enters its drop state when the local minimum + sojourn delay has exceeded TARGET for a time period long enough for + normal bursts to dissipate, ensuring that a burst of packets that + fits in the pipe will not be dropped. + +4.1. 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 bandwidths, + including variable-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 + dropped; therefore, CoDel exits the drop state. The MTU size can be + set adaptively to the largest packet seen so far or can be read from + the interface driver. + +4.2. Setting INTERVAL + + The INTERVAL value is chosen to give endpoints time to react to a + drop without being so long that response times suffer. CoDel's + estimator, TARGET, and control loop all use INTERVAL. Understanding + their derivation shows that CoDel is the most sensitive to the value + of INTERVAL for single long-lived TCPs with a decreased sensitivity + for traffic mixes. This is fortunate, as RTTs vary across + connections and are not known a priori. The best policy seems to be + to use an INTERVAL value slightly larger than the RTT seen by most of + the connections using a link, a value that can be determined as the + largest RTT seen if the value is not an outlier (use of a 95-99th + percentile value should work). In practice, this value is not known + or measured (however, see Appendix A for an application where + INTERVAL is measured). An INTERVAL setting of 100 ms works well + across a range of RTTs from 10 ms to 1 second (excellent performance + is achieved in the range from 10 ms to 300 ms). For devices intended + for the normal terrestrial Internet, INTERVAL SHOULD have a value of + 100 ms. This will only cause overdropping where a long-lived TCP has + an RTT longer than 100 ms and there is little or no mixing with other + connections through the link. + +4.3. Setting TARGET + + TARGET is the maximum acceptable persistent queue delay above which + CoDel is dropping or preparing to drop and below which CoDel will not + drop. TARGET SHOULD be set to 5 ms for normal Internet traffic. + + The calculations of Section 3.2 show that the best TARGET value is + 5-10% of the RTT, with the low end of 5% preferred. Extensive + simulations exploring the impact of different TARGET values when used + + + +Nichols, et al. Experimental [Page 14] + +RFC 8289 CoDel January 2018 + + + with mixed traffic flows with different RTTs and different bandwidths + show that below a TARGET of 5 ms, utilization suffers for some + conditions and traffic loads; above 5 ms showed very little or no + improvement in utilization. + + Sojourn times must remain above the TARGET for INTERVAL amount of + time 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 TARGET. Since Internet traffic has very dynamic + characteristics, the actual sojourn delay experienced by packets + varies greatly and is often less than 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 total + amount of queueing delay experienced by a packet should be less than + 10 ms even under extremely congested conditions. This net delay is + substantially lower than common current queueing delays on the + Internet that grow to orders of seconds [NETAL2010] [CHARB2007]. + + Regarding the roles of TARGET and the minimum-tracking INTERVAL, note + that TARGET SHOULD NOT be increased in response to lower layers that + 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'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 the waiting time 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 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 what CoDel excels at: + using a packet's sojourn time in the buffer completely circumvents + 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 for queue occupancy before + dropping, the total occupancy of all queues sharing the same output + link SHOULD be used. This property of CoDel has been exploited in + + + +Nichols, et al. Experimental [Page 15] + +RFC 8289 CoDel January 2018 + + + fq_codel [RFC8290], which hashes on the packet header fields to + determine a specific bin, or sub-queue, for the packet 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"). + +4.5. Setting Up CoDel + + CoDel is set for use in devices in 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 the INTERVAL. These settings + have been chosen so that a device, such as a small WiFi router, can + be sold without the need for any values to be made adjustable, + yielding a parameterless implementation. In addition, 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 + <100 us) but bandwidths are high (1-40 Gbps), 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 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 have attempted to highlight just these additions by + presenting CoDel as a sub-class of a basic FIFO queue base class. + The reference code is included to aid implementers who wish to apply + CoDel to queue management as described here or to adapt its + principles to other applications. + + + + + + + +Nichols, et al. Experimental [Page 16] + +RFC 8289 CoDel January 2018 + + + 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 is 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 will be 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 shouldn't require a lock with the enqueue() method. + + flag_t is a Boolean. + +5.2. Per-Queue State (codel_queue_t Instance Variables) + + 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 + + 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) + + + + + + + + + + + +Nichols, et al. Experimental [Page 17] + +RFC 8289 CoDel January 2018 + + +5.4. Enqueue Routine + + All the work of CoDel is done in the dequeue routine. The only CoDel + addition to enqueue is putting the current time in the packet's + tstamp field so that the dequeue routine can compute the packet's + sojourn time. Note that packets arriving at a full buffer will be + dropped, but these drops are not counted towards CoDel's + computations. + + 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. There are two branches based on whether + the controller is in drop state: (i) if the controller is in drop + state (that is, the minimum packet sojourn time is greater than + TARGET), then the controller checks if it is time to leave drop state + or schedules the next drop(s); or (ii) if the controller is not in + drop state, it determines if it should enter drop state and do the + initial 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; + + + +Nichols, et al. Experimental [Page 18] + +RFC 8289 CoDel January 2018 + + + } 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 + + 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. + + time_t codel_queue_t::control_law(time_t t, uint32_t count) + { + return t + INTERVAL / sqrt(count); + } + + + +Nichols, et al. Experimental [Page 19] + +RFC 8289 CoDel January 2018 + + + Next is a helper routine that 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 + amount of time. 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; + } 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; + } + + + +Nichols, et al. Experimental [Page 20] + +RFC 8289 CoDel January 2018 + + +5.7. Implementation Considerations + + 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. + + Since CoDel requires relatively little per-queue state and no direct + communication or state sharing between the enqueue and dequeue + routines, it is relatively simple to add CoDel to almost any packet + processing pipeline, including forwarding engines based on + Application-Specific Integrated Circuits (ASICs) or Network + Processors (NPUs). One issue to consider is dodequeue()'s use of a + 'bytes()' function to determine the current queue size in bytes. + 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 simply + the difference between these two counters (32-bit counters should be + adequate). Enqueue has to update its counter once per packet queued, + but it does not matter when (before, during, or after the packet has + been added to the queue). The worst that can happen is a slight, + transient underestimate of the queue size, which might cause a drop + to be briefly deferred. + +6. Further Experimentation + + We encourage experimentation with the recommended values of TARGET + and INTERVAL for Internet settings. CoDel provides general, + efficient, parameterless building blocks for queue management that + can be applied to single or multiple queues in a variety of data + networking scenarios. CoDel's settings may be modified for other + special-purpose networking applications. + +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. + + + +Nichols, et al. Experimental [Page 21] + +RFC 8289 CoDel January 2018 + + +9. References + +9.1. Normative References + + [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate + Requirement Levels", BCP 14, RFC 2119, + DOI 10.17487/RFC2119, March 1997, + <https://www.rfc-editor.org/info/rfc2119>. + + [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC + 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, + May 2017, <https://www.rfc-editor.org/info/rfc8174>. + +9.2. Informative References + + [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. + + + + +Nichols, et al. Experimental [Page 22] + +RFC 8289 CoDel January 2018 + + + [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>. + + [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>. + + + + + + + + + + + + + + + + +Nichols, et al. Experimental [Page 23] + +RFC 8289 CoDel January 2018 + + +Appendix A. Applying CoDel in the Data Center + + Nandita Dukkipati and her group at Google realized that the CoDel + building blocks could be applied to bufferbloat problems in data- + center servers, not just to Internet routers. The Linux CoDel + queueing discipline (qdisc) was adapted in three ways to tackle this + bufferbloat problem. + + 1. The default CoDel action was modified to be a direct feedback + from qdisc to the TCP layer at dequeue. The direct feedback + simply reduces TCP's congestion window just as congestion control + would do in the event of drop. The scheme falls back to ECN + marking or packet drop if the TCP socket lock could not be + acquired at dequeue. + + 2. Being located in the server makes it possible to monitor the + actual RTT to use as CoDel's interval rather than making a "best + guess" of RTT. The CoDel interval is dynamically adjusted by + using the maximum TCP round-trip time (RTT) of those connections + sharing the same qdisc/bucket. In particular, there is a history + entry of the maximum RTT experienced over the last second. As a + packet is dequeued, the RTT estimate is accessed from its TCP + socket. If the estimate is larger than the current CoDel + interval, the CoDel interval is immediately refreshed to the new + value. If the CoDel interval is not refreshed for over a second, + it is decreased to the history entry, and the process is + repeated. The use of the dynamic TCP RTT estimate allows the + interval to adapt to the actual maximum value currently seen and + thus lets the controller space 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, as these are typically small and + sometimes critical control packets. Being located on the server, + there is no concern with misbehaving users as there would be on the + public Internet. + + In several data-center workload benchmarks, which are typically + bursty, CoDel reduced the queueing latencies at the qdisc and thereby + improved the mean and 99th-percentile latencies from several tens of + milliseconds to less than one millisecond. The minimum tracking part + of the CoDel framework proved useful in disambiguating "good" queue + versus "bad" queue, which is particularly helpful in controlling + qdisc buffers that are inherently bursty because of TCP Segmentation + Offload (TSO). + + + + + +Nichols, et al. Experimental [Page 24] + +RFC 8289 CoDel January 2018 + + +Acknowledgments + + The authors thank Jim Gettys for the constructive nagging that made + us get the work "out there" before we thought it was ready. We thank + Dave Taht, Eric Dumazet, and the open source community for showing + the value of getting it "out there" and for making it real. We thank + Nandita Dukkipati for contributions to Section 6 and for comments + that helped to substantially improve this document. We 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. + +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 + + + + + + + + + + + + +Nichols, et al. Experimental [Page 25] + |