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