idnits 2.17.1 draft-white-aqm-docsis-pie-02.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 : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 12, 2015) is 3384 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-10) exists of draft-ietf-aqm-pie-00 Summary: 3 errors (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Active Queue Management and Packet Scheduling (aqm) G. White 3 Internet-Draft CableLabs 4 Intended status: Informational R. Pan 5 Expires: July 16, 2015 Cisco Systems 6 January 12, 2015 8 A PIE-Based AQM for DOCSIS Cable Modems 9 draft-white-aqm-docsis-pie-02 11 Abstract 13 DOCSIS cable modems provide broadband Internet access to over one 14 hundred million users worldwide. They are commonly positioned at the 15 head of the bottleneck link for traffic in the upstream direction 16 (from the customer), and as a result, the impact of buffering and 17 bufferbloat in the cable modem can have a significant effect on user 18 experience. The CableLabs DOCSIS 3.1 specification includes 19 requirements for cable modems to support an Active Queue Management 20 (AQM) algorithm that is intended to alleviate the impact that 21 buffering has on latency sensitive traffic, while preserving bulk 22 throughput performance. In addition, the CableLabs DOCSIS 3.0 23 specifications have also been amended to contain similar 24 requirements. 26 Status of This Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at http://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on July 16, 2015. 43 Copyright Notice 45 Copyright (c) 2015 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents 50 (http://trustee.ietf.org/license-info) in effect on the date of 51 publication of this document. Please review these documents 52 carefully, as they describe your rights and restrictions with respect 53 to this document. Code Components extracted from this document must 54 include Simplified BSD License text as described in Section 4.e of 55 the Trust Legal Provisions and are provided without warranty as 56 described in the Simplified BSD License. 58 Table of Contents 60 1. Overview of DOCSIS AQM Requirements . . . . . . . . . . . . . 2 61 2. The DOCSIS MAC Layer and Service Flows . . . . . . . . . . . 3 62 3. DOCSIS-PIE vs. PIE . . . . . . . . . . . . . . . . . . . . . 4 63 3.1. Latency Target . . . . . . . . . . . . . . . . . . . . . 4 64 3.2. Departure rate estimation . . . . . . . . . . . . . . . . 5 65 3.3. Expanded auto-tuning range . . . . . . . . . . . . . . . 6 66 3.4. Trigger for exponential decay . . . . . . . . . . . . . . 6 67 4. Implementation Guidance . . . . . . . . . . . . . . . . . . . 6 68 5. References . . . . . . . . . . . . . . . . . . . . . . . . . 7 69 Appendix A. DOCSIS-PIE Algorithm definition . . . . . . . . . . 7 70 A.1. DOCSIS-PIE AQM Constants and Variables . . . . . . . . . 7 71 A.1.1. Configuration parameters . . . . . . . . . . . . . . 7 72 A.1.2. Constant values . . . . . . . . . . . . . . . . . . . 8 73 A.1.3. Variables . . . . . . . . . . . . . . . . . . . . . . 8 74 A.1.4. Public/system functions: . . . . . . . . . . . . . . 9 75 A.2. DOCSIS-PIE AQM Control Path . . . . . . . . . . . . . . . 9 76 A.3. DOCSIS-PIE AQM Data Path . . . . . . . . . . . . . . . . 11 77 Appendix B. Change Log . . . . . . . . . . . . . . . . . . . . . 13 78 B.1. Since draft-white-aqm-docsis-pie-01 . . . . . . . . . . . 13 79 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 81 1. Overview of DOCSIS AQM Requirements 83 CableLabs' DOCSIS 3.1 specification [DOCSIS_3.1] mandates that cable 84 modems implement a specific variant of the Proportional Integral 85 controller Enhanced (PIE) [I-D.ietf-aqm-pie] active queue management 86 algorithm. This specific variant is provided for reference in 87 Appendix A. CableLabs' DOCSIS 3.0 specification [DOCSIS_3.0] has 88 been amended to recommend that cable modems implement the same 89 algorithm. Both specifications allow that cable modems can 90 optionally implement additional algorithms, that can then be selected 91 for use by the operator via the modem's configuration file. 93 These requirements on the cable modem apply to upstream 94 transmissions. 96 Both specifications also include requirements (mandatory in DOCSIS 97 3.1 and recommended in DOCSIS 3.0) that the Cable Modem Termination 98 System (CMTS) implement active queue management for downstream 99 traffic, however no specific algorithm is defined for downstream use. 101 2. The DOCSIS MAC Layer and Service Flows 103 The DOCSIS Media Access Control (sub-)layer provides tools for 104 configuring differentiated Quality of Service for different 105 applications by the use of Packet Classifiers and Service Flows. 107 Each cable modem can be configured with multiple Packet Classifiers 108 and Service Flows. The maximum number of such entities that a cable 109 modem supports is an implementation decision for the manufacturer, 110 but modems typically support 16 or 32 Service Flows and at least that 111 many Packet Classifiers. 113 Each Service Flow has an associated Quality of Service (QoS) 114 parameter set that defines the treatment of the packets that traverse 115 the Service Flow. These parameters include (for example) Minimum 116 Reserved Traffic Rate, Maximum Sustained Traffic Rate, Peak Traffic 117 Rate, Maximum Traffic Burst, Traffic Priority. Each upstream Service 118 Flow corresponds to a queue in the cable modem, and each downstream 119 Service Flow corresponds to a queue in the CMTS. The DOCSIS AQM 120 requirements mandate that the CM and CMTS implement the AQM algorithm 121 (and allow it to be disabled if need be) on each Service Flow queue 122 independently. 124 Packet Classifiers can match packets based upon several fields in the 125 packet/frame headers including the Ethernet header, IP header, and 126 TCP/UDP header. Matched packets are then queued in the associated 127 Service Flow queue. 129 It is typical that upstream and downstream Service Flows used for 130 broadband Internet access are configured with a Maximum Sustained 131 Traffic Rate. This QoS parameter rate-shapes the traffic onto the 132 DOCSIS link, and is the main parameter that defines the service 133 offering. Additionally, it is common that upstream and downstream 134 Service Flows are configured with a Maximum Traffic Burst and a Peak 135 Traffic Rate. These parameters allow the service to burst at a 136 higher (sometimes significantly higher) rate than is defined in the 137 Maximum Sustained Traffic Rate for the amount of bytes configured in 138 Maximum Traffic Burst, as long as the long-term average data rate 139 remains at or below the Maximum Sustained Traffic Rate. 141 Mathematically, what is enforced is that the traffic placed on the 142 DOCSIS link in the time interval (t1,t2) complies with the following 143 rate shaping equations: 145 TxBytes(t1,t2) <= (t2-t1)*R/8 + B 147 TxBytes(t1,t2) <= (t2-t1)*P/8 + 1522 149 for all values t2>t1, where: 151 R = Maximum Sustained Traffic Rate (bps) 153 P = Peak Traffic Rate (bps) 155 B = Maximum Traffic Burst (bytes) 157 The result of this configuration is that the link rate available to 158 the Service Flow varies based on the pattern of load. If the load 159 that the Service Flow places on the link is less than the Maximum 160 Sustained Traffic Rate, the Service Flow "earns" credit that it can 161 then use (should the load increase) to burst at the Peak Traffic 162 Rate. This dynamic is important since these rate changes 163 (particularly the decrease in data rate once the traffic burst credit 164 is exhausted) can induce a step increase in buffering latency. 166 3. DOCSIS-PIE vs. PIE 168 There are a number of differences between the version of the PIE 169 algorithm that is mandated for cable modems in the DOCSIS 170 specifications and the version described in [I-D.ietf-aqm-pie]. 172 o 10 ms default latency target, configurable per service flow 174 o departure rate estimation 176 o expanded auto-tuning range 178 o trigger for exponential decay 180 3.1. Latency Target 182 The latency target (aka delay reference) is a key parameter that 183 affects, among other things, the tradeoff in performance between 184 latency-sensitive applications and bulk TCP applications. Via 185 simulation studies, a value of 10ms was identified as providing a 186 good balance of performance. However, it is recognized that there 187 may be service offerings for which this value doesn't provide the 188 best performance balance. As a result, this is provided as a 189 configuration parameter that the operator can set independently on 190 each upstream service flow. If not explicitly set by the operator, 191 the modem will use 10 ms as the default value. 193 3.2. Departure rate estimation 195 The PIE algorithm utilizes a departure rate estimator to track 196 fluctuations in the egress rate for the queue and to generate a 197 smoothed estimate of this rate for use in the drop probability 198 calculation. This estimator may be well suited to many link 199 technologies, but is not ideal for DOCSIS upstream links for a number 200 of reasons. 202 First, the bursty nature of the upstream transmissions, in which the 203 queue drains at line rate (up to ~100 Mbps for DOCSIS 3.0 and ~1 Gbps 204 for DOCSIS 3.1) and then is blocked until the next transmit 205 opportunity, results in the potential for inaccuracy in measurement, 206 given that the PIE departure rate estimator starts each measurement 207 during a transmission burst and ends each measurement during a 208 (possibly different) transmission burst. For example, in the case 209 where the start and end of measurement occur within a single burst, 210 the PIE estimator will calculate the egress rate to be equal to the 211 line rate, rather than the average rate available to the modem. 213 Second, the latency introduced by the DOCSIS request-grant mechanism 214 can result in some further inaccuracy. In typical conditions, the 215 request-grant mechanism can add between ~4 ms and ~8 ms of latency to 216 the forwarding of upstream traffic. Within that range, the amount of 217 additional latency that affects any individual data burst is 218 effectively random, being influenced by the arrival time of the burst 219 relative to the next request transmit opportunity, among other 220 factors. 222 Third, in the significant majority of cases, the departure rate, 223 while variable, is controlled by the modem itself via the pair of 224 token bucket rate shaping equations described in Section 2. 225 Together, these two equations enforce a maximum sustained traffic 226 rate, a peak traffic rate, and a maximum traffic burst size for the 227 modem's requested bandwidth. The implication of this is that the 228 modem, in the significant majority of cases, will know precisely what 229 the departure rate will be, and can predict exactly when transitions 230 between peak rate and maximum sustained traffic rate will occur. 231 Compare this to the PIE estimator, which would be simply reacting to 232 (and smoothing its estimate of) those rate transitions after the 233 fact. 235 Finally, since the modem is already implementing the dual token 236 bucket traffic shaper, it contains enough internal state to calculate 237 predicted queuing delay with a minimum of computations. Furthermore, 238 these computations only need to be run every drop probability update 239 interval, as opposed to the PIE estimator, which runs a similar 240 number of computations on each packet dequeue event. 242 For these reasons, the DOCSIS-PIE algorithm utilizes the 243 configuration and state of the dual token bucket traffic shaper to 244 translate queue depth into predicted queuing delay, rather than 245 implementing the departure rate estimator defined in PIE. 247 3.3. Expanded auto-tuning range 249 The PIE algorithm scales the PI coefficients based on the current 250 drop probability. The DOCSIS-PIE algorithm extends this scaling to 251 drop probabilities below 1e-4. 253 3.4. Trigger for exponential decay 255 The PIE algorithm includes a mechanism by which the drop probability 256 is allowed to decay exponentially (rather than linearly) when it is 257 detected that the buffer is empty. In the DOCSIS case, recently 258 arrived packets may reside in buffer due to the request-grant latency 259 even if the link is effectively idle. As a result, the buffer may 260 not be identically empty in the situations for which the exponential 261 decay is intended. To compensate for this, we trigger exponential 262 decay when the buffer occupancy is less than 5ms * Peak Traffic Rate. 264 4. Implementation Guidance 266 The AQM space is an evolving one, and it is expected that continued 267 research in this field may in the future result in improved 268 algorithms. 270 As part of defining the DOCSIS-PIE algorithm, we split the pseudocode 271 definition into two components, a "data path" component and a 272 "control path" component. The control path component contains the 273 packet drop probability update functionality, whereas the data path 274 component contains the per-packet operations, including the drop 275 decision logic. 277 It is understood that some aspects of the cable modem implementation 278 may be done in hardware, particularly functions that handle packet- 279 processing. 281 While the DOCSIS specifications don't mandate the internal 282 implementation details of the cable modem, modem implementers are 283 strongly advised against implementing the control path functionality 284 in hardware. The intent of this advice is to retain the possibility 285 that future improvements in AQM algorithms can be accommodated via 286 software updates to deployed devices. 288 5. References 290 [DOCSIS_3.0] 291 CableLabs, "DOCSIS 3.0 MAC and Upper Layer Protocols 292 Specification", November 2013, . 296 [DOCSIS_3.1] 297 CableLabs, "DOCSIS 3.1 MAC and Upper Layer Protocols 298 Specification", October 2013, . 302 [I-D.ietf-aqm-pie] 303 Pan, R., Natarajan, P., Baker, F., and G. White, "PIE: A 304 Lightweight Control Scheme To Address the Bufferbloat 305 Problem", draft-ietf-aqm-pie-00 (work in progress), 306 October 2014. 308 Appendix A. DOCSIS-PIE Algorithm definition 310 PIE defines two functions organized here into two design blocks: 312 1. Control path block, a periodically running algorithm that 313 calculates a drop probability based on the estimated queuing 314 latency and queuing latency trend. 316 2. Data path block, a function that occurs on each packet enqueue: 317 per-packet drop decision based on the drop probability. 319 It is desired to have the ability to update the Control path block 320 based on operational experience with PIE deployments. 322 A.1. DOCSIS-PIE AQM Constants and Variables 324 A.1.1. Configuration parameters 326 o LATENCY_TARGET. AQM Latency Target for this Service Flow 328 o PEAK_RATE. Service Flow configured Peak Traffic Rate, expressed 329 in Bytes/sec. 331 o MSR. Service Flow configured Max. Sustained Traffic Rate, 332 expressed in Bytes/sec. 334 o BUFFER_SIZE. The size (in bytes) of the buffer for this Service 335 Flow. 337 A.1.2. Constant values 339 o A=0.25, B=2.5. Weights in the drop probability calculation 341 o INTERVAL=16 ms. Update interval for drop probability. 343 o DELAY_HIGH=200 ms. 345 o BURST_RESET_TIMEOUT = 1 s. 347 o MAX_BURST = 142 ms (150 ms-8 ms(update error)) 349 o MEAN_PKTSIZE = 1024 bytes 351 o MIN_PKTSIZE = 64 bytes 353 o PROB_LOW = 0.85 355 o PROB_HIGH = 8.5 357 o LATENCY_LOW = 5 ms 359 A.1.3. Variables 361 o drop_prob_. The current packet drop probability. 363 o accu_prob_. accumulated drop prob. since last drop 365 o qdelay_old_. The previous queue delay estimate. 367 o burst_allowance_. Countdown for burst protection, initialize to 0 369 o burst_reset_. counter to reset burst 371 o burst_state_. Burst protection state encoding 3 states: 373 NOBURST - no burst yet 375 FIRST_BURST - first burst detected, no protection yet 377 PROTECT_BURST - first burst detected, protecting burst if 378 burst_allowance_ > 0 380 o queue_. Holds the pending packets. 382 A.1.4. Public/system functions: 384 o drop(packet). Drops/discards a packet 386 o random(). Returns a uniform r.v. in the range 0 ~ 1 388 o queue_.is_full(). Returns true if queue_ is full 390 o queue_.byte_length(). Returns current queue_ length in bytes, 391 including all MAC PDU bytes without DOCSIS MAC overhead 393 o queue_.enque(packet). Adds packet to tail of queue_ 395 o msrtokens(). Returns current token credits (in bytes) from the 396 Max Sust. Traffic Rate token bucket 398 o packet.size(). Returns size of packet 400 A.2. DOCSIS-PIE AQM Control Path 402 The DOCSIS-PIE control path performs the following: 404 o Calls control_path_init() at service flow creation 406 o Calls calculate_drop_prob() at a regular INTERVAL (16ms) 408 ================ 409 // Initialization function 410 control_path_init() { 411 drop_prob_ = 0; 412 qdelay_old_ = 0; 413 burst_reset_ = 0; 414 burst_state_ = NOBURST; 415 } 417 // Background update, occurs every INTERVAL 418 calculate_drop_prob() { 420 if (queue_.byte_length() <= msrtokens()) { 421 qdelay = queue_.byte_length() / PEAK_RATE; 422 } else { 423 qdelay = ((queue_.byte_length() - msrtokens()) / MSR \ 424 + msrtokens() / PEAK_RATE); 425 } 427 if (burst_allowance_ > 0) { 428 drop_prob_ = 0; 429 } else { 430 p = A * (qdelay - LATENCY_TARGET) + \ 431 B * (qdelay - qdelay_old_); 432 // Since A=0.25 & B=2.5, can be implemented 433 // with shift and add 435 if (drop_prob_ < 0.000001) { 436 p /= 2048; 437 } else if (drop_prob_ < 0.00001) { 438 p /= 512; 439 } else if (drop_prob_ < 0.0001) { 440 p /= 128; 441 } else if (drop_prob_ < 0.001) { 442 p /= 32; 443 } else if (drop_prob_ < 0.01) { 444 p /= 8; 445 } else if (drop_prob_ < 0.1) { 446 p /= 2; 447 } else if (drop_prob_ < 1) { 448 p /= 0.5; 449 } else if (drop_prob_ < 10) { 450 p /= 0.125; 451 } else { 452 p /= 0.03125; 453 } 455 if ((drop_prob_ >= 0.1) && (p > 0.02)) { 456 p = 0.02; 457 } 458 drop_prob_ += p; 460 /* for non-linear drop in prob */ 461 if (qdelay < LATENCY_LOW && qdelay_old_ < LATENCY_LOW) { 462 drop_prob_ *= 0.98; // (1-1/64) is sufficient 463 } else if (qdelay > DELAY_HIGH) { 464 drop_prob_ += 0.02; 465 } 467 drop_prob_ = max(0, drop_prob_); 468 drop_prob_ = min(drop_prob_, \ 469 PROB_LOW * MEAN_PKTSIZE/MIN_PKTSIZE); 470 } 472 if (burst_allowance_ < INTERVAL) 473 burst_allowance_ = 0; 474 else 475 burst_allowance_ = burst_allowance_ - INTERVAL; 477 // both old and new qdelay is well better than the 478 // target and drop_prob_ == 0, time to clear burst tolerance 479 if ((qdelay < 0.5 * LATENCY_TARGET) 480 && (qdelay_old_ < 0.5 * LATENCY_TARGET) 481 && (drop_prob_ == 0) 482 && (burst_allowance_ == 0)){ 484 if (burst_state_ == PROTECT_BURST) { 485 burst_state_ = FIRST_BURST; 486 burst_reset_ = 0; 488 } else if (burst_state_ == FIRST_BURST) { 489 burst_reset_ += INTERVAL ; 490 if (burst_reset_ > BURST_RESET_TIMEOUT) { 491 burst_reset_ = 0; 492 burst_state_ = NOBURST; 493 } 494 } 495 } else if (burst_state_ == FIRST_BURST) { 496 burst_reset_ = 0; 497 } 499 qdelay_old_ = qdelay; 501 } 503 A.3. DOCSIS-PIE AQM Data Path 505 The DOCSIS-PIE data path performs the following: 507 o Calls enque() in response to an incoming packet from the CMCI 509 ================ 510 enque(packet) { 512 if (queue_.is_full()) { 513 drop(packet); 514 accu_prob_ = 0; 515 } else if (drop_early(packet, queue_.byte_length())) { 516 drop(packet); 517 } else { 518 queue_.enque(packet); 519 } 520 } 522 //////////////// 523 drop_early(packet, queue_length) { 524 if (burst_allowance_ > 0) { 525 return FALSE; 527 } 529 if (drop_prob_ == 0) { 530 accu_prob_ = 0; 531 } 533 if (burst_state_ == NOBURST) { //first burst? 534 if (queue_.byte_length() < BUFFER_SIZE/3) { 535 return FALSE; 536 } else { 537 burst_state_ = FIRST_BURST; //burst detected 538 } 539 } 541 //The CM can quantize packet.size to 64, 128, 256, 512, 768, 542 // 1024, 1280, 1536, 2048 in the calculation below 543 p1 = drop_prob_ * packet.size() / MEAN_PKTSIZE; 544 p1 = min(p1, PROB_LOW); 546 accu_prob_ += p1; 548 // If latency is low, don't drop packets 549 if ( (qdelay_old_ < 0.5 * LATENCY_TARGET && drop_prob_ < 0.2) 550 || (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) { 551 return FALSE; 552 } 554 drop = TRUE; 555 if (accu_prob_ < PROB_LOW) { // avoid dropping too fast due 556 drop = FALSE; // to bad luck of coin tosses... 557 } else if (accu_prob_ >= PROB_HIGH) { // ...and avoid droppping 558 drop = TRUE; // too slowly 559 } else { //Random drop 560 double u = random(); // 0 ~ 1 561 if (u > p1) { 562 drop = FALSE; 563 } 564 } 566 if (drop == FALSE) return FALSE; 568 // In case of packet drop: 569 accu_prob_ = 0; 571 // Not protecting burst yet? Start protecting burst. 572 // This will set the burst_allowance_ value, and 573 // calculate_drop_prob() will decrement it. 574 // Could implement this as a 150ms timer instead. 576 if (burst_state_ == FIRST_BURST) { 577 burst_state_ = PROTECT_BURST; 578 burst_allowance_ = MAX_BURST; 579 } 580 return TRUE; 581 } 583 Appendix B. Change Log 585 B.1. Since draft-white-aqm-docsis-pie-01 587 Added Change Log. 589 Removed discussion of Packet drop de-randomization, Enhanced burst 590 protection, and 16ms update interval, as these are now included in 591 [I-D.ietf-aqm-pie]. 593 Authors' Addresses 595 Greg White 596 CableLabs 597 858 Coal Creek Circle 598 Louisville, CO 80027-9750 599 USA 601 Email: g.white@cablelabs.com 603 Rong Pan 604 Cisco Systems 605 510 McCarthy Blvd 606 Milpitas, CA 95134 607 USA 609 Email: ropan@cisco.com