idnits 2.17.1 draft-ietf-aqm-codel-10.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 13, 2017) is 2381 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 1073 == Unused Reference: 'BMPFQ' is defined on line 998, but no explicit reference was found in the text == Unused Reference: 'SFQ1990' is defined on line 1054, but no explicit reference was found in the text -- Obsolete informational reference (is this intentional?): RFC 2309 (Obsoleted by RFC 7567) -- Obsolete informational reference (is this intentional?): RFC 2581 (Obsoleted by RFC 5681) -- Obsolete informational reference (is this intentional?): RFC 896 (Obsoleted by RFC 7805) Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 AQM K. Nichols 3 Internet-Draft Pollere, Inc. 4 Intended status: Experimental V. Jacobson 5 Expires: April 16, 2018 A. McGregor, ed. 6 J. Iyengar, ed. 7 Google 8 October 13, 2017 10 Controlled Delay Active Queue Management 11 draft-ietf-aqm-codel-10 13 Abstract 15 This document describes a general framework called CoDel (Controlled 16 Delay) that controls bufferbloat-generated excess delay in modern 17 networking environments. CoDel consists of an estimator, a setpoint, 18 and a control loop. It requires no configuration in normal Internet 19 deployments. 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at https://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on April 16, 2018. 38 Copyright Notice 40 Copyright (c) 2017 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (https://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 56 2. Conventions and terms used in this document . . . . . . . . . 4 57 3. Understanding the Building Blocks of Queue Management . . . . 5 58 3.1. Estimator . . . . . . . . . . . . . . . . . . . . . . . . 6 59 3.2. Target Setpoint . . . . . . . . . . . . . . . . . . . . . 8 60 3.3. Control Loop . . . . . . . . . . . . . . . . . . . . . . 10 61 4. Overview of the Codel AQM . . . . . . . . . . . . . . . . . . 12 62 4.1. Non-starvation . . . . . . . . . . . . . . . . . . . . . 13 63 4.2. Setting INTERVAL . . . . . . . . . . . . . . . . . . . . 13 64 4.3. Setting TARGET . . . . . . . . . . . . . . . . . . . . . 14 65 4.4. Use with multiple queues . . . . . . . . . . . . . . . . 15 66 4.5. Setting up CoDel . . . . . . . . . . . . . . . . . . . . 15 67 5. Annotated Pseudo-code for CoDel AQM . . . . . . . . . . . . . 16 68 5.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 16 69 5.2. Per-queue state (codel_queue_t instance variables) . . . 17 70 5.3. Constants . . . . . . . . . . . . . . . . . . . . . . . . 17 71 5.4. Enqueue routine . . . . . . . . . . . . . . . . . . . . . 17 72 5.5. Dequeue routine . . . . . . . . . . . . . . . . . . . . . 17 73 5.6. Helper routines . . . . . . . . . . . . . . . . . . . . . 19 74 5.7. Implementation considerations . . . . . . . . . . . . . . 20 75 6. Further Experimentation . . . . . . . . . . . . . . . . . . . 21 76 7. Security Considerations . . . . . . . . . . . . . . . . . . . 21 77 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 78 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21 79 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 80 10.1. Normative References . . . . . . . . . . . . . . . . . . 22 81 10.2. Informative References . . . . . . . . . . . . . . . . . 22 82 10.3. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 23 83 Appendix A. Applying CoDel in the datacenter . . . . . . . . . . 24 84 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 25 86 1. Introduction 88 The "persistently full buffer" problem has been discussed in the IETF 89 community since the early 80's [RFC896]. The IRTF's End-to-End 90 Research Group called for the deployment of active queue management 91 (AQM) to solve the problem in 1998 [RFC2309]. Despite this 92 awareness, the problem has only gotten worse as Moore's Law growth in 93 memory density fueled an exponential increase in buffer pool size. 94 Efforts to deploy AQM have been frustrated by difficult configuration 95 and negative impact on network utilization. This "bufferbloat" 96 problem [TSV2011] [BB2011] has become increasingly important 97 throughout the Internet but particularly at the consumer edge. Queue 98 management has become more critical due to increased consumer use of 99 the Internet, mixing large video transactions with time-critical VoIP 100 and gaming. 102 An effective AQM remediates bufferbloat at a bottleneck while "doing 103 no harm" at hops where buffers are not bloated. The development and 104 deployment of AQM however is frequently subject to misconceptions 105 about the cause of packet queues in network buffers. Network buffers 106 exist to absorb the packet bursts that occur naturally in 107 statistically multiplexed networks. Buffers helpfully absorb the 108 queues created by such reasonable packet network behavior as short- 109 term mismatches in traffic arrival and departure rates that arise 110 from upstream resource contention, transport conversation startup 111 transients and/or changes in the number of conversations sharing a 112 link. Unfortunately, other less useful network behaviors can cause 113 queues to fill and their effects are not nearly as benign. 114 Discussion of these issues and the reason why the solution is not 115 simply smaller buffers can be found in [RFC2309], [VANQ2006], 116 [REDL1998], and [CODEL2012]. To understand queue management, it is 117 critical to understand the difference between the necessary, useful 118 "good" queue, and the counterproductive "bad" queue. 120 Several approaches to AQM have been developed over the past two 121 decades but none has been widely deployed due to performance 122 problems. When designed with the wrong conceptual model for queues, 123 AQMs have limited operational range, require a lot of configuration 124 tweaking, and frequently impair rather than improve performance. 125 Learning from this past history, the CoDel approach is designed to 126 meet the following goals: 128 o Making it parameterless for normal operation, with no knobs for 129 operators, users, or implementers to adjust. 131 o Being able to distinguish "good queue" from bad queue and treat 132 them differently, that is, keep delay low while permitting 133 necessary bursts of traffic. 135 o Controlling delay while insensitive (or nearly so) to round trip 136 delays, link rates and traffic loads; this goal is to "do no harm" 137 to network traffic while controlling delay. 139 o Adapting to dynamically changing link rates with no negative 140 impact on utilization. 142 o Allowing simple and efficient implementation (can easily span the 143 spectrum from low-end access points and home routers up to high- 144 end router silicon). 146 CoDel has five major differences from prior AQMs: use of local queue 147 minimum to track congestion ("bad queue"), use of an efficient single 148 state variable representation of that tracked statistic, use of 149 packet sojourn time as the observed datum, rather than packets, 150 bytes, or rates, use of mathematically determined setpoint derived 151 from maximizing network power [KLEIN81], and a modern state space 152 controller. 154 CoDel configures itself based on a round-trip time metric which can 155 be set to 100ms for the normal, terrestrial Internet. With no 156 changes to parameters, CoDel is expected to work across a wide range 157 of conditions, with varying links and the full range of terrestrial 158 round trip times. 160 CoDel is easily adapted to multiple queue systems as shown by [FQ- 161 CODEL-ID]. Implementers and users SHOULD use the fq_codel multiple- 162 queue approach as it deals with many problems beyond the reach of an 163 AQM on a single queue. 165 CoDel was first published in [CODEL2012] and has been implemented in 166 the Linux kernel. 168 Note that while this document refers to dropping packets when 169 indicated by CoDel, it is reasonable to ECN-mark packets instead as 170 well. 172 2. Conventions and terms used in this document 174 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 175 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 176 document are to be interpreted as described in [RFC2119]. 178 In this document, these words will appear with that interpretation 179 only when in ALL CAPS. Lower case uses of these words are not to be 180 interpreted as carrying [RFC2119] significance. 182 The following terms are defined as used in this document: 184 sojourn time: the amount of time a packet has spent in a particular 185 buffer, i.e. the time a packet departs the buffer minus the time the 186 packet arrived at the buffer. A packet can depart a buffer via 187 transmission or drop. 189 standing queue: a queue (in packets, bytes, or time delay) in a 190 buffer that persists for a "long" time where "long" is on the order 191 of the longer round trip times through the buffer as discussed in 192 section 4.2. A standing queue occurs when the minimum queue over the 193 "long" time is nonzero and is usually tolerable and even desirable as 194 long as it does not exceed some target delay. 196 bottleneck bandwidth: the limiting bandwidth along a network path. 198 3. Understanding the Building Blocks of Queue Management 200 At the heart of queue management is the notion of "good queue" and 201 "bad queue" and the search for ways to get rid of the bad queue 202 (which only adds delay) while preserving the good queue (which 203 provides for good utilization). This section explains queueing, both 204 good and bad, and covers the CoDel building blocks that can be used 205 to manage packet buffers to keep their queues in the "good" range. 207 Packet queues form in buffers facing bottleneck links, i.e., where 208 the line rate goes from high to low or where many links converge. 209 The well-known bandwidth-delay product (sometimes called "pipe size") 210 is the bottleneck's bandwidth multiplied by the sender-receiver- 211 sender round-trip delay, and is the amount of data that has to be in 212 transit between two hosts in order to run the bottleneck link at 100% 213 utilization. To explore how queues can form, consider a long-lived 214 TCP connection with a 25 packet window sending through a connection 215 with a bandwidth-delay product of 20 packets. After an initial burst 216 of packets the connection will settle into a five packet (+/-1) 217 standing queue; this standing queue size is determined by the 218 mismatch between the window size and the pipe size, and is unrelated 219 to the connection's sending rate. The connection has 25 packets in 220 flight at all times, but only 20 packets arrive at the destination 221 over a round trip time. If the TCP connection has a 30 packet 222 window, the queue will be ten packets with no change in sending rate. 223 Similarly, if the window is 20 packets, there will be no queue but 224 the sending rate is the same. Nothing can be inferred about the 225 sending rate from the queue size, and any queue other than transient 226 bursts only creates delays in the network. The sender needs to 227 reduce the number of packets in flight rather than sending rate. 229 In the above example, the five packet standing queue can be seen to 230 contribute nothing but delay to the connection, and thus is clearly 231 "bad queue". If, in our example, there is a single bottleneck link 232 and it is much slower than the link that feeds it (say, a high-speed 233 ethernet link into a limited DSL uplink) a 20 packet buffer at the 234 bottleneck might be necessary to temporarily hold the 20 packets in 235 flight to keep the bottleneck link's utilization high. The burst of 236 packets should drain completely (to 0 or 1 packets) within a round 237 trip time and this transient queue is "good queue" because it allows 238 the connection to keep the 20 packets in flight and for the 239 bottleneck link to be fully utilized. In terms of the delay 240 experienced, the "good queue" goes away in about a round trip time, 241 while "bad queue" hangs around for longer, causing delays. 243 Effective queue management detects "bad queue" while ignoring "good 244 queue" and takes action to get rid of the bad queue when it is 245 detected. The goal is a queue controller that accomplishes this 246 objective. To control a queue, we need three basic components 248 o Estimator - figure out what we've got. 250 o Target setpoint - know what we want. 252 o Control loop - if what we've got isn't what we want, we need a way 253 to move it there. 255 3.1. Estimator 257 The estimator both observes the queue and detects when good queue 258 turns to bad queue and vice versa. CoDel has two parts to its 259 estimator: what is observed as an indicator of queue and how the 260 observations are used to detect good/bad queue. 262 Queue length has been widely used as an observed indicator of 263 congestion and is frequently conflated with sending rate. Use of 264 queue length as a metric is sensitive to how and when the length is 265 observed. A high speed arrival link to a buffer serviced at a much 266 lower rate can rapidly build up a queue that might disperse 267 completely or down to a single packet before a round trip time has 268 elapsed. If the queue length is monitored at packet arrival (as in 269 original RED) or departure time, every packet will see a queue with 270 one possible exception. If the queue length itself is time sampled 271 (as recommended in [REDL1998], a truer picture of the queue's 272 occupancy can be gained at the expense of considerable implementation 273 complexity. 275 The use of queue length is further complicated in networks that are 276 subject to both short and long term changes in available link rate 277 (as in WiFi). Link rate drops can result in a spike in queue length 278 that should be ignored unless it persists. It is not the queue 279 length that should be controlled but the amount of excess delay 280 packets experience due to a persistent or standing queue, which means 281 that the packet sojourn time in the buffer is exactly what we want to 282 track. Tracking the packet sojourn times in the buffer observes the 283 actual delay experienced by each packet. Sojourn time allows queue 284 management to be independent of link rate, gives superior performance 285 to use of buffer size, and is directly related to user-visible 286 performance. It works regardless of line rate changes or link 287 sharing by multiple queues (which the individual queues may 288 experience as changing rates). 290 Consider a link shared by two queues with different priorities. 291 Packets that arrive at the high priority queue are sent as soon as 292 the link is available while packets in the other queue have to wait 293 until the high priority queue is empty (i.e., a strict priority 294 scheduler). The number of packets in the high priority queue might 295 be large but the queue is emptied quickly and the amount of time each 296 packet spends enqueued (the sojourn time) is not large. The other 297 queue might have a smaller number of packets, but packet sojourn 298 times will include the waiting time for the high priority packets to 299 be sent. This makes the sojourn time a good sample of the congestion 300 that each separate queue is experiencing. This example also shows 301 how the metric of sojourn time is independent of the number of queues 302 or the service discipline used, and is instead indicative of 303 congestion seen by the individual queues. 305 How can observed sojourn time be used to separate good queue from bad 306 queue? Although averages, especially of queue length, have 307 previously been widely used as an indicator of bad queue, their 308 efficacy is questionable. Consider the burst that disperses every 309 round trip time. The average queue will be one-half the burst size, 310 though this might vary depending on when the average is computed and 311 the timing of arrivals. The average queue sojourn time would be one- 312 half the time it takes to clear the burst. The average then would 313 indicate a persistent queue where there is none. Instead of averages 314 we recommend tracking the minimum sojourn time, then, if there is one 315 packet that has a zero sojourn time then there is no persistent 316 queue. 318 A persistent queue can be detected by tracking the (local) minimum 319 queue delay packets experience. To ensure that this minimum value 320 does not become stale, it has to have been experienced recently, i.e. 321 during an appropriate past time interval. This interval is the 322 maximum amount of time a minimum value is considered to be in effect, 323 and is related to the amount of time it takes for the largest 324 expected burst to drain. Conservatively, this interval SHOULD be at 325 least a round trip time to avoid falsely detecting a persistent queue 326 and not a lot more than a round trip time to avoid delay in detecting 327 the persistent queue. This suggests that the appropriate interval 328 value is the maximum round-trip time of all the connections sharing 329 the buffer. 331 (The following key insight makes computation of the local minimum 332 efficient: It is sufficient to keep a single state variable of how 333 long the minimum has been above or below the target value rather than 334 retaining all the local values to compute the minimum, leading to 335 both storage and computational savings. We use this insight in the 336 pseudo-code for CoDel later in the document.) 338 These two parts, use of sojourn time as observed values and the local 339 minimum as the statistic to monitor queue congestion are key to 340 CoDel's estimator building block. The local minimum sojourn time 341 provides an accurate and robust measure of standing queue and has an 342 efficient implementation. In addition, use of the minimum sojourn 343 time has important advantages in implementation. The minimum packet 344 sojourn can only be decreased when a packet is dequeued which means 345 that all the work of CoDel can take place when packets are dequeued 346 for transmission and that no locks are needed in the implementation. 347 The minimum is the only statistic with this property. 349 A more detailed explanation with many pictures can be found in 350 http://www.ietf.org/proceedings/84/slides/slides-84-tsvarea-4.pdf 351 [1]. 353 3.2. Target Setpoint 355 Now that we have a robust way of detecting standing queue, we need a 356 target setpoint that tells us when to act. If the controller is set 357 to take action as soon as the estimator has a non-zero value, the 358 average drop rate will be maximized, which minimizes TCP goodput 359 [MACTCP1997]. Also, this policy results in no backlog over time (no 360 persistent queue), which negates much of the value of having a 361 buffer, since it maximizes the bottleneck link bandwidth lost due to 362 normal stochastic variation in packet interarrival time. We want a 363 target that maximizes utilization while minimizing delay. Early in 364 the history of packet networking, Kleinrock developed the analytic 365 machinery to do this using a quantity he called 'power', which is the 366 ratio of a normalized throughput to a normalized delay [KLEIN81]. 368 It is straightforward to derive an analytic expression for the 369 average goodput of a TCP conversation at a given round-trip time r 370 and target f (where f is expressed as a fraction of r). Reno TCP, 371 for example, yields: 373 goodput = r (3 + 6f - f^2) / (4 (1+f)) 375 Since the peak queue delay is simply the product of f and r, power is 376 solely a function of f since the r's in the numerator and denominator 377 cancel: 379 power is proportional to (1 + 2f - 1/3 f^2) / (1 + f)^2 381 As Kleinrock observed, the best operating point, in terms of 382 bandwidth / delay tradeoff, is the peak power point, since points off 383 the peak represent a higher cost (in delay) per unit of bandwidth. 384 The power vs. f curve for any Additive Increase Multiplicative 385 Decrease (AIMD) TCP is monotone decreasing. But the curve is very 386 flat for f < 0.1 followed by a increasing curvature with a knee 387 around f = 0.2, then a steep, almost linear fall off [TSV84]. Since 388 the previous equation showed that goodput is monotone increasing with 389 f, the best operating point is near the right edge of the flat top 390 since that represents the highest goodput achievable for a negligible 391 increase in delay. However, since the r in the model is a 392 conservative upper bound, a target of 0.1r runs the risk of pushing 393 shorter RTT connections over the knee and giving them higher delay 394 for no significant goodput increase. Generally, a more conservative 395 target of 0.05r offers a good utilization vs. delay tradeoff while 396 giving enough headroom to work well with a large variation in real 397 RTT. 399 As the above analysis shows, a very small standing queue gives close 400 to 100% utilization of the bottleneck link. While this result was 401 for Reno TCP, the derivation uses only properties that must hold for 402 any 'TCP friendly' transport. We have verified by both analysis and 403 simulation that this result holds for Reno, Cubic, and Westwood 404 [TSV84]. This results in a particularly simple form for the target: 405 the ideal range for the permitted standing queue, or the target 406 setpoint, is between 5% and 10% of the TCP connection's RTT. 408 We used simulation to explore the impact when TCPs are mixed with 409 other traffic and with connections of different RTTs. Accordingly, 410 we experimented extensively with values in the 5-10% of RTT range 411 and, overall, used target values between 1 and 20 milliseconds for 412 RTTs from 30 to 500ms and link bandwidths of 64Kbps to 100Mbps to 413 experimentally explore a value for the target that gives consistently 414 high utilization while controlling delay across a range of 415 bandwidths, RTTs, and traffic loads. Our results were notably 416 consistent with the mathematics above. 418 A congested (but not overloaded) CoDel link with traffic composed 419 solely or primarily of long-lived TCP flows will have a median delay 420 through the link will tend to the target. For bursty traffic loads 421 and for overloaded conditions (where it is difficult or impossible 422 for all the arriving flows to be accommodated) the median queues will 423 be longer than the target. 425 The non-starvation drop inhibit feature dominates where the link rate 426 becomes very small. By inhibiting drops when there is less than an 427 (outbound link) MTU worth of bytes in the buffer, CoDel adapts to 428 very low bandwidth links, as shown in [CODEL2012]. 430 3.3. Control Loop 432 Section 3.1 describes a simple, reliable way to measure bad 433 (persistent) queue. Section 3.2 shows that TCP congestion control 434 dynamics gives rise to a target setpoint for this measure that's a 435 provably good balance between enhancing throughput and minimizing 436 delay, and that this target is a constant fraction of the same 437 'largest average RTT' interval used to distinguish persistent from 438 transient queue. The only remaining building block needed for a 439 basic AQM is a 'control loop' algorithm to effectively drive the 440 queueing system from any 'persistent queue above the target' state to 441 a state where the persistent queue is below the target. 443 Control theory provides a wealth of approaches to the design of 444 control loops. Most of classical control theory deals with the 445 control of linear, time-invariant, single-input-single-output (SISO) 446 systems. Control loops for these systems generally come from a (well 447 understood) class known as Proportional-Integral-Derivative (PID) 448 controllers. Unfortunately, a queue is not a linear system and an 449 AQM operates at the point of maximum non-linearity (where the output 450 link bandwidth saturates so increased demand creates delay rather 451 than higher utilization). Output queues are also not time-invariant 452 since traffic is generally a mix of connections which start and stop 453 at arbitrary times and which can have radically different behaviors 454 ranging from "open loop" UDP audio/video to "closed-loop" congestion- 455 avoiding TCP. Finally, the constantly changing mix of connections 456 (which can't be converted to a single 'lumped parameter' model 457 because of their transfer function differences) makes the system 458 multi-input-multi-output (MIMO), not SISO. 460 Since queueing systems match none of the prerequisites for a 461 classical controller, a modern state-space controller is a better 462 approach with states 'no persistent queue' and 'has persistent 463 queue'. Since Internet traffic mixtures change rapidly and 464 unpredictably, a noise and error tolerant adaptation algorithm like 465 Stochastic Gradient is a good choice. Since there's essentially no 466 information in the amount of persistent queue [TSV84], the adaptation 467 should be driven by how long it has persisted. 469 Consider the two extremes of traffic behavior, a single open-loop UDP 470 video stream and a single, long-lived TCP bulk data transfer. If the 471 average bandwidth of the UDP video stream is greater that the 472 bottleneck link rate, the link's queue will grow and the controller 473 will eventually enter 'has persistent queue' state and start dropping 474 packets. Since the video stream is open loop, its arrival rate is 475 unaffected by drops so the queue will persist until the average drop 476 rate is greater than the output bandwidth deficit (= average arrival 477 rate - average departure rate) so the job of the adaptation algorithm 478 is to discover this rate. For this example, the adaptation could 479 consist of simply estimating the arrival and departure rates then 480 dropping at a rate slightly greater than their difference. But this 481 class of algorithm won't work at all for the bulk data TCP stream. 482 TCP runs in closed-loop flow balance [TSV84] so its arrival rate is 483 almost always exactly equal to the departure rate - the queue isn't 484 the result of a rate imbalance but rather a mismatch between the TCP 485 sender's window and the source-destination-source round-trip path 486 capacity (i.e., the connection's bandwidth-delay product). The 487 sender's TCP congestion avoidance algorithm will slowly increase the 488 send window (one packet per round-trip-time) [RFC2581] which will 489 eventually cause the bottleneck to enter 'has persistent queue' 490 state. But, since the average input rate is the same as the average 491 output rate, the rate deficit estimation that gave the correct drop 492 rate for the video stream would compute a drop rate of zero for the 493 TCP stream. However, if the output link drops one packet as it 494 enters 'has persistent queue' state, when the sender discovers this 495 (via TCP's normal packet loss repair mechanisms) it will reduce its 496 window by a factor of two [RFC2581] so, one round-trip-time after the 497 drop, the persistent queue will go away. 499 If there were N TCP conversations sharing the bottleneck, the 500 controller would have to drop O(N) packets, one from each 501 conversation, to make all the conversations reduce their window to 502 get rid of the persistent queue. If the traffic mix consists of 503 short (<= bandwidth-delay product) conversations, the aggregate 504 behavior becomes more like the open-loop video example since each 505 conversation is likely to have already sent all its packets by the 506 time it learns about a drop so each drop has negligible effect on 507 subsequent traffic. 509 The controller does not know the number, duration, or kind of 510 conversations creating its queue, so it has to learn the appropriate 511 response. Since single drops can have a large effect if the degree 512 of multiplexing (the number of active conversations) is small, 513 dropping at too high a rate is likely to have a catastrophic effect 514 on throughput. Dropping at a low rate (< 1 packet per round-trip- 515 time) then increasing the drop rate slowly until the persistent queue 516 goes below the target is unlikely to overdrop and is guaranteed to 517 eventually dissipate the persistent queue. This stochastic gradient 518 learning procedure is the core of CoDel's control loop (the gradient 519 exists because a drop always reduces the (instantaneous) queue so an 520 increasing drop rate always moves the system "down" toward no 521 persistent queue, regardless of traffic mix). 523 The "next drop time" is decreased in inverse proportion to the square 524 root of the number of drops since the drop state was entered, using 525 the well-known nonlinear relationship of drop rate to throughput to 526 get a linear change in throughput [REDL1998], [MACTCP1997]. 528 Since the best rate to start dropping is at slightly more than one 529 packet per RTT, the controller's initial drop rate can be directly 530 derived from the estimator's interval. When the minimum sojourn time 531 first crosses the target and CoDel drops a packet, the earliest the 532 controller could see the effect of the drop is the round trip time 533 (interval) + the local queue wait time (the target). If the next 534 drop happens any earlier than this time (interval + target), CoDel 535 will overdrop. In practice, the local queue waiting time tends to 536 vary, so making the initial drop spacing (i.e., the time to the 537 second drop) be exactly the minimum possible also leads to 538 overdropping. Analysis of simulation and real-world measured data 539 shows that the 75th percentile magnitude of this variation is less 540 than the target, and so the initial drop spacing SHOULD be set to the 541 estimator's interval (i.e., initial drop spacing = interval) to 542 ensure that the controller has accounted for acceptable congestion 543 delays. 545 Use of the minimum statistic lets the controller be placed in the 546 dequeue routine with the estimator. This means that the control 547 signal (the drop) can be sent at the first sign of bad queue (as 548 indicated by the sojourn time) and that the controller can stop 549 acting as soon as the sojourn time falls below the target. Dropping 550 at dequeue has both implementation and control advantages. 552 4. Overview of the Codel AQM 554 CoDel was initially designed as a bufferbloat solution for the 555 consumer network edge. The CoDel building blocks are able to adapt 556 to different or time-varying link rates, to be easily used with 557 multiple queues, to have excellent utilization with low delay, and to 558 have a simple and efficient implementation. 560 The CoDel algorithm described in the rest of this document uses two 561 key variables: TARGET, which is the controller's target setpoint 562 described in Section 3.2 and INTERVAL, which is the estimator's 563 interval described in Section 3.3. 565 The only setting CoDel requires is the INTERVAL value, and as 100ms 566 satisfies that definition for normal Internet usage, CoDel can be 567 parameter-free for consumer use. To ensure that link utilization is 568 not adversely affected, CoDel's estimator sets TARGET to one that 569 optimizes power. CoDel's controller does not drop packets when the 570 drop would leave the queue empty or with fewer than a maximum 571 transmission unit (MTU) worth of bytes in the buffer. Section 3.2 572 shows that an ideal TARGET is 5-10% of the connection round trip time 573 (RTT). In the open terrestrial-based Internet, especially at the 574 consumer edge, we expect most unbloated RTTs to have a ceiling of 575 100ms [CHARB2007]. Using this RTT gives a minimum TARGET of 5ms and 576 INTERVAL of 100ms. In practice, uncongested links will see sojourn 577 times below TARGET more often than once per RTT, so the estimator is 578 not overly sensitive to the value of INTERVAL. 580 When the estimator finds a persistent delay above TARGET, the 581 controller enters the drop state where a packet is dropped and the 582 next drop time is set. As discussed in section 3.3, the initial next 583 drop spacing is intended to be long enough to give the endpoints time 584 to react to the single drop so SHOULD be set to a value equal to 585 INTERVAL. If the estimator's output falls below TARGET, the 586 controller cancels the next drop and exits the drop state. (The 587 controller is more sensitive than the estimator to an overly short 588 INTERVAL value, since an unnecessary drop would occur and lower link 589 utilization.) If next drop time is reached while the controller is 590 still in drop state, the packet being dequeued is dropped and the 591 next drop time is recalculated. 593 Additional logic prevents re-entering the drop state too soon after 594 exiting it and resumes the drop state at a recent control level, if 595 one exists. This logic is described more precisely in the pseudo- 596 code below. Additional work is required to determine the frequency 597 and importance of re-entering the drop state. 599 Note that CoDel AQM only enters its drop state when the local minimum 600 sojourn delay has exceeded TARGET for a time period long enough for 601 normal bursts to dissipate, ensuring that a burst of packets that 602 fits in the pipe will not be dropped. 604 4.1. Non-starvation 606 CoDel's goals are to control delay with little or no impact on link 607 utilization and to be deployed on a wide range of link bandwidths, 608 including variable-rate links, without reconfiguration. To keep from 609 making drops when it would starve the output link, CoDel makes 610 another check before dropping to see if at least an MTU worth of 611 bytes remains in the buffer. If not, the packet SHOULD NOT be 612 dropped and, therefore, CoDel exits the drop state. The MTU size can 613 be set adaptively to the largest packet seen so far or can be read 614 from the interface driver. 616 4.2. Setting INTERVAL 618 The INTERVAL value is chosen to give endpoints time to react to a 619 drop without being so long that response times suffer. CoDel's 620 estimator, TARGET, and control loop all use INTERVAL. Understanding 621 their derivation shows that CoDel is the most sensitive to the value 622 of INTERVAL for single long-lived TCPs with a decreased sensitivity 623 for traffic mixes. This is fortunate as RTTs vary across connections 624 and are not known a priori. The best policy seems to be to use an 625 INTERVAL value slightly larger than the RTT seen by most of the 626 connections using a link, a value that can be determined as the 627 largest RTT seen if the value is not an outlier (use of a 95-99th 628 percentile value should work). In practice, this value is not known 629 or measured (though see section 6.2 for an application where INTERVAL 630 is measured). An INTERVAL setting of 100ms works well across a range 631 of RTTs from 10ms to 1 second (excellent performance is achieved in 632 the range from 10 ms to 300ms). For devices intended for the normal 633 terrestrial Internet, INTERVAL SHOULD have a value of 100ms. This 634 will only cause overdropping where a long-lived TCP has an RTT longer 635 than 100ms and there is little or no mixing with other connections 636 through the link. 638 4.3. Setting TARGET 640 TARGET is the maximum acceptable persistent queue delay above which 641 CoDel is dropping or preparing to drop and below which CoDel will not 642 drop. TARGET SHOULD be set to 5ms for normal Internet traffic. 644 The calculations of section 3.2 show that the best TARGET value is 645 5-10% of the RTT, with the low end of 5% preferred. Extensive 646 simulations exploring the impact of different TARGET values when used 647 with mixed traffic flows with different RTTs and different bandwidths 648 show that below a TARGET of 5ms, utilization suffers for some 649 conditions and traffic loads, and above 5ms showed very little or no 650 improvement in utilization. 652 Sojourn times must remain above the TARGET for INTERVAL amount of 653 time in order to enter the drop state. Any packet with a sojourn 654 time less than TARGET will reset the time that the queue was last 655 below TARGET. Since Internet traffic has very dynamic 656 characteristics, the actual sojourn delay experienced by packets 657 varies greatly and is often less than TARGET unless the overload is 658 excessive. When a link is not overloaded, it is not a bottleneck and 659 packet sojourn times will be small or nonexistent. In the usual 660 case, there are only one or two places along a path where packets 661 will encounter a bottleneck (usually at the edge), so the total 662 amount of queueing delay experienced by a packet should be less than 663 10ms even under extremely congested conditions. This net delay is 664 substantially lower than common current queueing delays on the 665 Internet that grow to orders of seconds [NETAL2010, CHARB2007]. 667 A note on the roles of TARGET and the minimum-tracking INTERVAL. 668 TARGET SHOULD NOT be increased in response to lower layers that have 669 a bursty nature, where packets are transmitted for short periods 670 interspersed with idle periods where the link is waiting for 671 permission to send. CoDel's estimator will "see" the effective 672 transmission rate over an INTERVAL amount of time, and increasing 673 TARGET only leads to longer queue delays. On the other hand, where a 674 significant additional delay is added to the intrinsic RTT of most or 675 all packets due to the waiting time for a transmission, it is 676 necessary to increase INTERVAL by that extra delay. TARGET SHOULD 677 NOT be adjusted for such short-term bursts, but INTERVAL MAY need to 678 be adjusted if the path's intrinsic RTT changes. 680 4.4. Use with multiple queues 682 CoDel is easily adapted to multiple queue systems. With other 683 approaches there is always a question of how to account for the fact 684 that each queue receives less than the full link rate over time and 685 usually sees a varying rate over time. This is what CoDel excels at: 686 using a packet's sojourn time in the buffer completely circumvents 687 this problem. In a multiple-queue setting, a separate CoDel 688 algorithm runs on each queue, but each CoDel instance uses the packet 689 sojourn time the same way a single-queue CoDel does. Just as a 690 single-queue CoDel adapts to changing link bandwidths [CODEL2012], so 691 does a multiple-queue CoDel system. As an optimization to avoid 692 queueing more than necessary, when testing for queue occupancy before 693 dropping, the total occupancy of all queues sharing the same output 694 link SHOULD be used. This property of CoDel has been exploited in 695 fq_codel [FQ-CODEL-ID], which hashes on the packet header fields to 696 determine a specific bin, or sub-queue, for the packet, and runs 697 CoDel on each bin or sub-queue thus creating a well-mixed output flow 698 and obviating issues of reverse path flows (including "ack 699 compression"). 701 4.5. Setting up CoDel 703 CoDel is set for use in devices in the open Internet. An INTERVAL 704 setting of 100ms is used, TARGET is set to 5% of INTERVAL, and the 705 initial drop spacing is also set to the INTERVAL. These settings 706 have been chosen so that a device, such as a small WiFi router, can 707 be sold without the need for any values to be made adjustable, 708 yielding a parameterless implementation. In addition, CoDel is 709 useful in environments with significantly different characteristics 710 from the normal Internet, for example, in switches used as a cluster 711 interconnect within a data center. Since cluster traffic is entirely 712 internal to the data center, round trip latencies are low (typically 713 <100us) but bandwidths are high (1-40Gbps) so it's relatively easy 714 for the aggregation phase of a distributed computation (e.g., the 715 Reduce part of a Map/Reduce) to persistently fill then overflow the 716 modest per-port buffering available in most high speed switches. A 717 CoDel configured for this environment (TARGET and INTERVAL in the 718 microsecond rather than millisecond range) can minimize drops or ECN 719 marks while keeping throughput high and latency low. 721 Devices destined for these environments MAY use a different value for 722 INTERVAL, where suitable. If appropriate analysis indicates, the 723 TARGET MAY be set to some other value in the 5-10% of INTERVAL and 724 the initial drop spacing MAY be set to a value of 1.0 to 1.2 times 725 INTERVAL. But these settings will cause problems such as 726 overdropping and low throughput if used on the open Internet, so 727 devices that allow CoDel to be configured SHOULD default to Internet- 728 appropriate values given in this document. 730 5. Annotated Pseudo-code for CoDel AQM 732 What follows is the CoDel algorithm in C++-like pseudo-code. Since 733 CoDel adds relatively little new code to a basic tail-drop fifo- 734 queue, we have attempted to highlight just these additions by 735 presenting CoDel as a sub-class of a basic fifo-queue base class. 736 The reference code is included to aid implementers who wish to apply 737 CoDel to queue management as described here or to adapt its 738 principles to other applications. 740 Implementors are strongly encouraged to also look at the Linux kernel 741 version of CoDel - a well-written, well tested, real-world, C-based 742 implementation. As of this writing, it is available at 743 https://github.com/torvalds/linux/blob/master/net/sched/sch_codel.c. 745 5.1. Data Types 747 time_t is an integer time value in units convenient for the system. 748 The code presented here uses 0 as a flag value to indicate "no time 749 set." 751 packet_t* is a pointer to a packet descriptor. We assume it has a 752 tstamp field capable of holding a time_t and that field is available 753 for use by CoDel (it will be set by the enqueue routine and used by 754 the dequeue routine). 756 queue_t is a base class for queue objects (the parent class for 757 codel_queue_t objects). We assume it has enqueue() and dequeue() 758 methods that can be implemented in child classes. We assume it has a 759 bytes() method that returns the current queue size in bytes. This 760 can be an approximate value. The method is invoked in the dequeue() 761 method but shouldn't require a lock with the enqueue() method. 763 flag_t is a Boolean. 765 5.2. Per-queue state (codel_queue_t instance variables) 767 time_t first_above_time_ = 0; // Time to declare sojourn time above 768 // TARGET 769 time_t drop_next_ = 0; // Time to drop next packet 770 uint32_t count_ = 0; // Packets dropped in drop state 771 uint32_t lastcount_ = 0; // Count from previous iteration 772 flag_t dropping_ = false; // Set to true if in drop state 774 5.3. Constants 776 time_t TARGET = MS2TIME(5); // 5ms TARGET queue delay 777 time_t INTERVAL = MS2TIME(100); // 100ms sliding-minimum window 778 u_int maxpacket = 512; // Maximum packet size in bytes 779 // (SHOULD use interface MTU) 781 5.4. Enqueue routine 783 All the work of CoDel is done in the dequeue routine. The only CoDel 784 addition to enqueue is putting the current time in the packet's 785 tstamp field so that the dequeue routine can compute the packet's 786 sojourn time. Note that packets arriving at a full buffer will be 787 dropped, but these drops are not counted towards CoDel's 788 computations. 790 void codel_queue_t::enqueue(packet_t* pkt) 791 { 792 pkt->timestamp() = clock(); 793 queue_t::enqueue(pkt); 794 } 796 5.5. Dequeue routine 798 This is the heart of CoDel. There are two branches based on whether 799 the controller is in drop state: (i) if the controller is in drop 800 state (that is, the minimum packet sojourn time is greater than 801 TARGET) then the controller checks if it is time to leave drop state 802 or schedules the next drop(s); or (ii) if the controller is not in 803 drop state, it determines if it should enter drop state and do the 804 initial drop. 806 packet_t* CoDelQueue::dequeue() 807 { 808 time_t now = clock(); 809 dodequeue_result r = dodequeue(now); 810 uint32_t delta; 812 if (dropping_) { 813 if (! r.ok_to_drop) { 814 // sojourn time below TARGET - leave drop state 815 dropping_ = false; 816 } 817 // Time for the next drop. Drop current packet and dequeue 818 // next. If the dequeue doesn't take us out of dropping 819 // state, schedule the next drop. A large backlog might 820 // result in drop rates so high that the next drop should 821 // happen now, hence the 'while' loop. 822 while (now >= drop_next_ && dropping_) { 823 drop(r.p); 824 ++count_; 825 r = dodequeue(now); 826 if (! r.ok_to_drop) { 827 // leave drop state 828 dropping_ = false; 829 } else { 830 // schedule the next drop. 831 drop_next_ = control_law(drop_next_, count_); 832 } 833 } 834 // If we get here we're not in drop state. The 'ok_to_drop' 835 // return from dodequeue means that the sojourn time has been 836 // above 'TARGET' for 'INTERVAL' so enter drop state. 837 } else if (r.ok_to_drop) { 838 drop(r.p); 839 r = dodequeue(now); 840 dropping_ = true; 842 // If min went above TARGET close to when it last went 843 // below, assume that the drop rate that controlled the 844 // queue on the last cycle is a good starting point to 845 // control it now. ('drop_next' will be at most 'INTERVAL' 846 // later than the time of the last drop so 'now - drop_next' 847 // is a good approximation of the time from the last drop 848 // until now.) Implementations vary slightly here; this is 849 // the Linux version, which is more widely deployed and 850 // tested. 851 delta = count_ - lastcount_; 852 count_ = 1; 853 if ((delta > 1) && (now - drop_next_ < 16*INTERVAL)) 854 count_ = delta; 856 drop_next_ = control_law(now, count_); 857 lastcount_ = count_; 858 } 859 return (r.p); 860 } 862 5.6. Helper routines 864 Since the degree of multiplexing and nature of the traffic sources is 865 unknown, CoDel acts as a closed-loop servo system that gradually 866 increases the frequency of dropping until the queue is controlled 867 (sojourn time goes below TARGET). This is the control law that 868 governs the servo. It has this form because of the sqrt(p) 869 dependence of TCP throughput on drop probability. Note that for 870 embedded systems or kernel implementation, the inverse sqrt can be 871 computed efficiently using only integer multiplication. 873 time_t codel_queue_t::control_law(time_t t, uint32_t count) 874 { 875 return t + INTERVAL / sqrt(count); 876 } 878 Next is a helper routine the does the actual packet dequeue and 879 tracks whether the sojourn time is above or below TARGET and, if 880 above, if it has remained above continuously for at least INTERVAL 881 amount of time. It returns two values: a Boolean indicating if it is 882 OK to drop (sojourn time above TARGET for at least INTERVAL), and the 883 packet dequeued. 885 typedef struct { 886 packet_t* p; 887 flag_t ok_to_drop; 888 } dodequeue_result; 890 dodequeue_result codel_queue_t::dodequeue(time_t now) 891 { 892 dodequeue_result r = { queue_t::dequeue(), false }; 893 if (r.p == NULL) { 894 // queue is empty - we can't be above TARGET 895 first_above_time_ = 0; 896 return r; 897 } 899 // To span a large range of bandwidths, CoDel runs two 900 // different AQMs in parallel. One is sojourn-time-based 901 // and takes effect when the time to send an MTU-sized 902 // packet is less than TARGET. The 1st term of the "if" 903 // below does this. The other is backlog-based and takes 904 // effect when the time to send an MTU-sized packet is >= 905 // TARGET. The goal here is to keep the output link 906 // utilization high by never allowing the queue to get 907 // smaller than the amount that arrives in a typical 908 // interarrival time (MTU-sized packets arriving spaced 909 // by the amount of time it takes to send such a packet on 910 // the bottleneck). The 2nd term of the "if" does this. 911 time_t sojourn_time = now - r.p->tstamp; 912 if (sojourn_time_ < TARGET || bytes() <= maxpacket_) { 913 // went below - stay below for at least INTERVAL 914 first_above_time_ = 0; 915 } else { 916 if (first_above_time_ == 0) { 917 // just went above from below. if still above at 918 // first_above_time, will say it's ok to drop. 919 first_above_time_ = now + INTERVAL; 920 } else if (now >= first_above_time_) { 921 r.ok_to_drop = true; 922 } 923 } 924 return r; 925 } 927 5.7. Implementation considerations 929 time_t is an integer time value in units convenient for the system. 930 Resolution to at least a millisecond is required and better 931 resolution is useful up to the minimum possible packet time on the 932 output link; 64- or 32-bit widths are acceptable but with 32 bits the 933 resolution should be no finer than 2^{-16} to leave enough dynamic 934 range to represent a wide range of queue waiting times. Narrower 935 widths also have implementation issues due to overflow (wrapping) and 936 underflow (limit cycles because of truncation to zero) that are not 937 addressed in this pseudocode. 939 Since CoDel requires relatively little per-queue state and no direct 940 communication or state sharing between the enqueue and dequeue 941 routines, it is relatively simple to add CoDel to almost any packet 942 processing pipeline, including ASIC- or NPU-based forwarding engines. 943 One issue to consider is dodequeue()'s use of a 'bytes()' function to 944 determine the current queue size in bytes. This value does not need 945 to be exact. If the enqueue part of the pipeline keeps a running 946 count of the total number of bytes it has put into the queue and the 947 dequeue routine keeps a running count of the total bytes it has 948 removed from the queue, 'bytes()' is simply the difference between 949 these two counters (32-bit counters should be adequate.) Enqueue has 950 to update its counter once per packet queued but it does not matter 951 when (before, during or after the packet has been added to the 952 queue). The worst that can happen is a slight, transient, 953 underestimate of the queue size which might cause a drop to be 954 briefly deferred. 956 6. Further Experimentation 958 We encourage experimentation with the recommended values of TARGET 959 and INTERVAL for Internet settings. CoDel provides general, 960 efficient, parameterless building blocks for queue management that 961 can be applied to single or multiple queues in a variety of data 962 networking scenarios. CoDel's settings may be modified for other 963 special-purpose networking applications. 965 7. Security Considerations 967 This document describes an active queue management algorithm for 968 implementation in networked devices. There are no known security 969 exposures associated with CoDel at this time. 971 8. IANA Considerations 973 This document does not require actions by IANA. 975 9. Acknowledgments 977 The authors thank Jim Gettys for the constructive nagging that made 978 us get the work "out there" before we thought it was ready. We thank 979 Dave Taht, Eric Dumazet, and the open source community for showing 980 the value of getting it "out there" and for making it real. We thank 981 Nandita Dukkipati for contributions to section 6 and for comments 982 which helped to substantially improve this draft. We thank the AQM 983 working group and the Transport Area shepherd, Wes Eddy, for 984 patiently prodding this draft all the way to a standard. 986 10. References 988 10.1. Normative References 990 [RFC2119] Bradner, S., "Key Words for use in RFCs to Indicate 991 Requirement Levels", March 1997. 993 10.2. Informative References 995 [BB2011] Gettys, J. and K. Nichols, "Bufferbloat: Dark Buffers in 996 the Internet", Communications of the ACM 9(11) pp. 57-65. 998 [BMPFQ] Suter, B., "Buffer Management Schemes for Supporting TCP 999 in Gigabit Routers with Per-flow Queueing", IEEE Journal 1000 on Selected Areas in Communications Vol. 17 Issue 6, June, 1001 1999, pp. 1159-1169. 1003 [CHARB2007] 1004 Dischinger, M., "Characterizing Residential Broadband 1005 Networks", Proceedings of the Internet Measurement 1006 Conference San Diego, CA, 2007. 1008 [CODEL2012] 1009 Nichols, K. and V. Jacobson, "Controlling Queue Delay", 1010 Communications of the ACM Vol. 55 No. 11, July, 2012, pp. 1011 42-50. 1013 [FQ-CODEL-ID] 1014 Hoeiland-Joergensen, T., McKenney, P., 1015 dave.taht@gmail.com, d., Gettys, J., and E. Dumazet, 1016 "FlowQueue-Codel", draft-ietf-aqm-fq-codel-06 (work in 1017 progress), March 2017. 1019 [KLEIN81] Kleinrock, L. and R. Gail, "An Invariant Property of 1020 Computer Network Power", International Conference on 1021 Communications June, 1981, 1022 . 1024 [MACTCP1997] 1025 Mathis, M., Semke, J., and J. Mahdavi, "The Macroscopic 1026 Behavior of the TCP Congestion Avoidance Algorithm", ACM 1027 SIGCOMM Computer Communications Review Vol. 27 no. 1, Jan. 1028 2007. 1030 [NETAL2010] 1031 Kreibich, C., "Netalyzr: Illuminating the Edge Network", 1032 Proceedings of the Internet Measurement 1033 Conference Melbourne, Australia, 2010. 1035 [REDL1998] 1036 Nichols, K., Jacobson, V., and K. Poduri, "RED in a 1037 Different Light", Tech report, September, 1999, 1038 . 1041 [RFC2309] Braden, B., Clark, D., Crowcroft, J., Davie, B., Deering, 1042 S., Estrin, D., Floyd, S., Jacobson, V., Minshall, G., 1043 Partridge, C., Peterson, L., Ramakrishnan, K., Shenker, 1044 S., Wroclawski, J., and L. Zhang, "Recommendations on 1045 Queue Management and Congestion Avoidance in the 1046 Internet", RFC 2309, April 1998. 1048 [RFC2581] Allman, M., Paxson, V., and W. Stevens, "TCP Congestion 1049 Control", RFC 2581, April 1999. 1051 [RFC896] Nagle, J., "Congestion control in IP/TCP internetworks", 1052 RFC 896, January 1984. 1054 [SFQ1990] McKenney, P., "Stochastic Fairness Queuing", Proceedings 1055 of IEEE INFOCOMM 90 San Francisco, 1990. 1057 [TSV2011] Gettys, J., "Bufferbloat: Dark Buffers in the Internet", 1058 IETF 80 presentation to Transport Area Open Meeting, 1059 March, 2011, 1060 . 1062 [TSV84] Jacobson, V., "CoDel talk at TSV meeting IETF 84", 1063 . 1066 [VANQ2006] 1067 Jacobson, V., "A Rant on Queues", talk at MIT Lincoln 1068 Labs, Lexington, MA July, 2006, 1069 . 1071 10.3. URIs 1073 [1] http://www.ietf.org/proceedings/84/slides/slides-84-tsvarea-4.pdf 1075 Appendix A. Applying CoDel in the datacenter 1077 Nandita Dukkipati and her group at Google realized that the CoDel 1078 building blocks could be applied to bufferbloat problems in 1079 datacenter servers, not just to Internet routers. The Linux CoDel 1080 queueing discipline (qdisc) was adapted in three ways to tackle this 1081 bufferbloat problem. 1083 1. The default CoDel action was modified to be a direct feedback 1084 from qdisc to the TCP layer at dequeue. The direct feedback 1085 simply reduces TCP's congestion window just as congestion control 1086 would do in the event of drop. The scheme falls back to ECN 1087 marking or packet drop if the TCP socket lock could not be 1088 acquired at dequeue. 1090 2. Being located in the server makes it possible to monitor the 1091 actual RTT to use as CoDel's interval rather than making a "best 1092 guess" of RTT. The CoDel interval is dynamically adjusted by 1093 using the maximum TCP round-trip time (RTT) of those connections 1094 sharing the same Qdisc/bucket. In particular, there is a history 1095 entry of the maximum RTT experienced over the last second. As a 1096 packet is dequeued, the RTT estimate is accessed from its TCP 1097 socket. If the estimate is larger than the current CoDel 1098 interval, the CoDel interval is immediately refreshed to the new 1099 value. If the CoDel interval is not refreshed for over a second, 1100 it is decreased it to the history entry and the process is 1101 repeated. The use of the dynamic TCP RTT estimate lets interval 1102 adapt to the actual maximum value currently seen and thus lets 1103 the controller space its drop intervals appropriately. 1105 3. Since the mathematics of computing the setpoint are invariant, a 1106 target of 5% of the RTT or CoDel interval was used here. 1108 Non-data packets were not dropped as these are typically small and 1109 sometimes critical control packets. Being located on the server, 1110 there is no concern with misbehaving users as there would be on the 1111 public Internet. 1113 In several data center workload benchmarks, which are typically 1114 bursty, CoDel reduced the queueing latencies at the qdisc, and 1115 thereby improved the mean and 99th-percentile latencies from several 1116 tens of milliseconds to less than one millisecond. The minimum 1117 tracking part of the CoDel framework proved useful in disambiguating 1118 "good" queue versus "bad" queue, particularly helpful in controlling 1119 qdisc buffers that are inherently bursty because of TCP Segmentation 1120 Offload (TSO). 1122 Authors' Addresses 1124 Kathleen Nichols 1125 Pollere, Inc. 1126 PO Box 370201 1127 Montara, CA 94037 1128 USA 1130 Email: nichols@pollere.com 1132 Van Jacobson 1133 Google 1135 Email: vanj@google.com 1137 Andrew McGregor 1138 Google 1140 Email: andrewmcgr@google.com 1142 Janardhan Iyengar 1143 Google 1145 Email: jri@google.com