idnits 2.17.1 draft-ietf-tsvwg-aqm-dualq-coupled-23.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: ---------------------------------------------------------------------------- == There are 4 instances of lines with non-ascii characters in the document. 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 (4 May 2022) is 723 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 2681 -- Looks like a reference, but probably isn't: '1' on line 2681 == Outdated reference: A later version (-29) exists of draft-ietf-tsvwg-ecn-l4s-id-25 == Outdated reference: A later version (-07) exists of draft-briscoe-docsis-q-protection-03 == Outdated reference: A later version (-03) exists of draft-briscoe-iccrg-prague-congestion-control-00 == Outdated reference: A later version (-20) exists of draft-ietf-tsvwg-l4s-arch-17 -- Obsolete informational reference (is this intentional?): RFC 2309 (Obsoleted by RFC 7567) -- Obsolete informational reference (is this intentional?): RFC 8312 (Obsoleted by RFC 9438) Summary: 0 errors (**), 0 flaws (~~), 6 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Transport Area working group (tsvwg) K. De Schepper 3 Internet-Draft Nokia Bell Labs 4 Intended status: Experimental B. Briscoe, Ed. 5 Expires: 5 November 2022 Independent 6 G. White 7 CableLabs 8 4 May 2022 10 DualQ Coupled AQMs for Low Latency, Low Loss and Scalable Throughput 11 (L4S) 12 draft-ietf-tsvwg-aqm-dualq-coupled-23 14 Abstract 16 This specification defines a framework for coupling the Active Queue 17 Management (AQM) algorithms in two queues intended for flows with 18 different responses to congestion. This provides a way for the 19 Internet to transition from the scaling problems of standard TCP 20 Reno-friendly ('Classic') congestion controls to the family of 21 'Scalable' congestion controls. These are designed for consistently 22 very Low queuing Latency, very Low congestion Loss and Scaling of 23 per-flow throughput (L4S) by using Explicit Congestion Notification 24 (ECN) in a modified way. Until the Coupled DualQ, these L4S senders 25 could only be deployed where a clean-slate environment could be 26 arranged, such as in private data centres. The coupling acts like a 27 semi-permeable membrane: isolating the sub-millisecond average 28 queuing delay and zero congestion loss of L4S from Classic latency 29 and loss; but pooling the capacity between any combination of 30 Scalable and Classic flows with roughly equivalent throughput per 31 flow. The DualQ achieves this indirectly, without having to inspect 32 transport layer flow identifiers and without compromising the 33 performance of the Classic traffic, relative to a single queue. The 34 DualQ design has low complexity and requires no configuration for the 35 public Internet. 37 Status of This Memo 39 This Internet-Draft is submitted in full conformance with the 40 provisions of BCP 78 and BCP 79. 42 Internet-Drafts are working documents of the Internet Engineering 43 Task Force (IETF). Note that other groups may also distribute 44 working documents as Internet-Drafts. The list of current Internet- 45 Drafts is at https://datatracker.ietf.org/drafts/current/. 47 Internet-Drafts are draft documents valid for a maximum of six months 48 and may be updated, replaced, or obsoleted by other documents at any 49 time. It is inappropriate to use Internet-Drafts as reference 50 material or to cite them other than as "work in progress." 52 This Internet-Draft will expire on 5 November 2022. 54 Copyright Notice 56 Copyright (c) 2022 IETF Trust and the persons identified as the 57 document authors. All rights reserved. 59 This document is subject to BCP 78 and the IETF Trust's Legal 60 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 61 license-info) in effect on the date of publication of this document. 62 Please review these documents carefully, as they describe your rights 63 and restrictions with respect to this document. Code Components 64 extracted from this document must include Revised BSD License text as 65 described in Section 4.e of the Trust Legal Provisions and are 66 provided without warranty as described in the Revised BSD License. 68 Table of Contents 70 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 71 1.1. Outline of the Problem . . . . . . . . . . . . . . . . . 3 72 1.2. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 6 73 1.3. Terminology . . . . . . . . . . . . . . . . . . . . . . . 7 74 1.4. Features . . . . . . . . . . . . . . . . . . . . . . . . 9 75 2. DualQ Coupled AQM . . . . . . . . . . . . . . . . . . . . . . 11 76 2.1. Coupled AQM . . . . . . . . . . . . . . . . . . . . . . . 11 77 2.2. Dual Queue . . . . . . . . . . . . . . . . . . . . . . . 13 78 2.3. Traffic Classification . . . . . . . . . . . . . . . . . 13 79 2.4. Overall DualQ Coupled AQM Structure . . . . . . . . . . . 14 80 2.5. Normative Requirements for a DualQ Coupled AQM . . . . . 17 81 2.5.1. Functional Requirements . . . . . . . . . . . . . . . 17 82 2.5.1.1. Requirements in Unexpected Cases . . . . . . . . 18 83 2.5.2. Management Requirements . . . . . . . . . . . . . . . 19 84 2.5.2.1. Configuration . . . . . . . . . . . . . . . . . . 20 85 2.5.2.2. Monitoring . . . . . . . . . . . . . . . . . . . 21 86 2.5.2.3. Anomaly Detection . . . . . . . . . . . . . . . . 22 87 2.5.2.4. Deployment, Coexistence and Scaling . . . . . . . 22 88 3. IANA Considerations (to be removed by RFC Editor) . . . . . . 22 89 4. Security Considerations . . . . . . . . . . . . . . . . . . . 22 90 4.1. Low Delay without Requiring Per-Flow Processing . . . . . 22 91 4.2. Handling Unresponsive Flows and Overload . . . . . . . . 23 92 4.2.1. Unresponsive Traffic without Overload . . . . . . . . 24 93 4.2.2. Avoiding Short-Term Classic Starvation: Sacrifice L4S 94 Throughput or Delay? . . . . . . . . . . . . . . . . 25 96 4.2.3. L4S ECN Saturation: Introduce Drop or Delay? . . . . 26 97 4.2.3.1. Protecting against Overload by Unresponsive 98 ECN-Capable Traffic . . . . . . . . . . . . . . . . 28 99 5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28 100 6. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 29 101 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 29 102 7.1. Normative References . . . . . . . . . . . . . . . . . . 29 103 7.2. Informative References . . . . . . . . . . . . . . . . . 30 104 Appendix A. Example DualQ Coupled PI2 Algorithm . . . . . . . . 35 105 A.1. Pass #1: Core Concepts . . . . . . . . . . . . . . . . . 36 106 A.2. Pass #2: Edge-Case Details . . . . . . . . . . . . . . . 47 107 Appendix B. Example DualQ Coupled Curvy RED Algorithm . . . . . 51 108 B.1. Curvy RED in Pseudocode . . . . . . . . . . . . . . . . . 51 109 B.2. Efficient Implementation of Curvy RED . . . . . . . . . . 57 110 Appendix C. Choice of Coupling Factor, k . . . . . . . . . . . . 59 111 C.1. RTT-Dependence . . . . . . . . . . . . . . . . . . . . . 59 112 C.2. Guidance on Controlling Throughput Equivalence . . . . . 60 113 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 64 115 1. Introduction 117 This document specifies a framework for DualQ Coupled AQMs, which is 118 the network part of the L4S architecture [I-D.ietf-tsvwg-l4s-arch]. 119 L4S enables both very low queuing latency (sub-millisecond on 120 average) and high throughput at the same time, for ad hoc numbers of 121 capacity-seeking applications all sharing the same capacity. 123 1.1. Outline of the Problem 125 Latency is becoming the critical performance factor for many (most?) 126 applications on the public Internet, e.g. interactive Web, Web 127 services, voice, conversational video, interactive video, interactive 128 remote presence, instant messaging, online gaming, remote desktop, 129 cloud-based applications, and video-assisted remote control of 130 machinery and industrial processes. In the developed world, further 131 increases in access network bit-rate offer diminishing returns, 132 whereas latency is still a multi-faceted problem. In the last decade 133 or so, much has been done to reduce propagation time by placing 134 caches or servers closer to users. However, queuing remains a major 135 intermittent component of latency. 137 Traditionally very low latency has only been available for a few 138 selected low rate applications, that confine their sending rate 139 within a specially carved-off portion of capacity, which is 140 prioritized over other traffic, e.g. Diffserv EF [RFC3246]. Up to 141 now it has not been possible to allow any number of low latency, high 142 throughput applications to seek to fully utilize available capacity, 143 because the capacity-seeking process itself causes too much queuing 144 delay. 146 To reduce this queuing delay caused by the capacity seeking process, 147 changes either to the network alone or to end-systems alone are in 148 progress. L4S involves a recognition that both approaches are 149 yielding diminishing returns: 151 * Recent state-of-the-art active queue management (AQM) in the 152 network, e.g. FQ-CoDel [RFC8290], PIE [RFC8033], Adaptive 153 RED [ARED01] ) has reduced queuing delay for all traffic, not just 154 a select few applications. However, no matter how good the AQM, 155 the capacity-seeking (sawtoothing) rate of TCP-like congestion 156 controls represents a lower limit that will either cause queuing 157 delay to vary or cause the link to be under-utilized. These AQMs 158 are tuned to allow a typical capacity-seeking Reno-friendly flow 159 to induce an average queue that roughly doubles the base RTT, 160 adding 5-15 ms of queuing on average (cf. 500 microseconds with 161 L4S for the same mix of long-running and web traffic). However, 162 for many applications low delay is not useful unless it is 163 consistently low. With these AQMs, 99th percentile queuing delay 164 is 20-30 ms (cf. 2 ms with the same traffic over L4S). 166 * Similarly, recent research into using e2e congestion control 167 without needing an AQM in the network (e.g. BBR 168 [I-D.cardwell-iccrg-bbr-congestion-control]) seems to have hit a 169 similar lower limit to queuing delay of about 20ms on average but 170 there are also regular 25ms delay spikes due to bandwidth probes 171 and 60ms spikes due to flow-starts. 173 L4S learns from the experience of Data Center TCP [RFC8257], which 174 shows the power of complementary changes both in the network and on 175 end-systems. DCTCP teaches us that two small but radical changes to 176 congestion control are needed to cut the two major outstanding causes 177 of queuing delay variability: 179 1. Far smaller rate variations (sawteeth) than Reno-friendly 180 congestion controls; 182 2. A shift of smoothing and hence smoothing delay from network to 183 sender. 185 Without the former, a 'Classic' (e.g. Reno-friendly) flow's round 186 trip time (RTT) varies between roughly 1 and 2 times the base RTT 187 between the machines in question. Without the latter a 'Classic' 188 flow's response to changing events is delayed by a worst-case 189 (transcontinental) RTT, which could be hundreds of times the actual 190 smoothing delay needed for the RTT of typical traffic from localized 191 CDNs. 193 These changes are the two main features of the family of so-called 194 'Scalable' congestion controls (which includes DCTCP, TCP Prague and 195 SCReAM). Both these changes only reduce delay in combination with a 196 complementary change in the network and they are both only feasible 197 with ECN, not drop, for the signalling: 199 1. The smaller sawteeth allow an extremely shallow ECN packet- 200 marking threshold in the queue. 202 2. And no smoothing in the network means that every fluctuation of 203 the queue is signalled immediately. 205 Without ECN, either of these would lead to very high loss levels. 206 But, with ECN, the resulting high marking levels are just signals, 207 not impairments. BBRv2 combines the best of both worlds - it works 208 as a scalable congestion control when ECN is available, but also aims 209 to minimize delay when it isn't. 211 However, until now, Scalable congestion controls (like DCTCP) did not 212 co-exist well in a shared ECN-capable queue with existing ECN-capable 213 TCP Reno [RFC5681] or Cubic [RFC8312] congestion controls -- Scalable 214 controls are so aggressive that these 'Classic' algorithms would 215 drive themselves to a small capacity share. Therefore, until now, 216 L4S controls could only be deployed where a clean-slate environment 217 could be arranged, such as in private data centres (hence the name 218 DCTCP). 220 This document specifies a `DualQ Coupled AQM' extension that solves 221 the problem of coexistence between Scalable and Classic flows, 222 without having to inspect flow identifiers. It is not like flow- 223 queuing approaches [RFC8290] that classify packets by flow identifier 224 into separate queues in order to isolate sparse flows from the higher 225 latency in the queues assigned to heavier flows. If a flow needs 226 both low delay and high throughput, having a queue to itself does not 227 isolate it from the harm it causes to itself. In contrast, DualQ 228 Coupled AQMs address the root cause of the latency problem -- they 229 are an enabler for the smooth low latency scalable behaviour of 230 Scalable congestion controls, so that every packet in every flow can 231 potentially enjoy very low latency, then there would be no need to 232 isolate each flow into a separate queue. 234 1.2. Scope 236 L4S involves complementary changes in the network and on end-systems: 238 Network: A DualQ Coupled AQM (defined in the present document) or a 239 modification to flow-queue AQMs (described in section 4.2.b of the 240 L4S architecture [I-D.ietf-tsvwg-l4s-arch]); 242 End-system: A Scalable congestion control (defined in section 4 of 243 the L4S ECN protocol [I-D.ietf-tsvwg-ecn-l4s-id]). 245 Packet identifier: The network and end-system parts of L4S can be 246 deployed incrementally, because they both identify L4S packets 247 using the experimentally assigned explicit congestion notification 248 (ECN) codepoints in the IP header: ECT(1) and CE [RFC8311] 249 [I-D.ietf-tsvwg-ecn-l4s-id]. 251 Data Center TCP (DCTCP [RFC8257]) is an example of a Scalable 252 congestion control for controlled environments that has been deployed 253 for some time in Linux, Windows and FreeBSD operating systems. 254 During the progress of this document through the IETF a number of 255 other Scalable congestion controls were implemented, e.g. TCP Prague 256 [I-D.briscoe-iccrg-prague-congestion-control] [PragueLinux], BBRv2 257 [BBRv2], [I-D.cardwell-iccrg-bbr-congestion-control], QUIC Prague and 258 the L4S variant of SCREAM for real-time media [RFC8298]. 260 The focus of this specification is to enable deployment of the 261 network part of the L4S service. Then, without any management 262 intervention, applications can exploit this new network capability as 263 their operating systems migrate to Scalable congestion controls, 264 which can then evolve _while_ their benefits are being enjoyed by 265 everyone on the Internet. 267 The DualQ Coupled AQM framework can incorporate any AQM designed for 268 a single queue that generates a statistical or deterministic mark/ 269 drop probability driven by the queue dynamics. Pseudocode examples 270 of two different DualQ Coupled AQMs are given in the appendices. In 271 many cases the framework simplifies the basic control algorithm, and 272 requires little extra processing. Therefore it is believed the 273 Coupled AQM would be applicable and easy to deploy in all types of 274 buffers; buffers in cost-reduced mass-market residential equipment; 275 buffers in end-system stacks; buffers in carrier-scale equipment 276 including remote access servers, routers, firewalls and Ethernet 277 switches; buffers in network interface cards, buffers in virtualized 278 network appliances, hypervisors, and so on. 280 For the public Internet, nearly all the benefit will typically be 281 achieved by deploying the Coupled AQM into either end of the access 282 link between a 'site' and the Internet, which is invariably the 283 bottleneck (see section 6.4 of[I-D.ietf-tsvwg-l4s-arch] about 284 deployment, which also defines the term 'site' to mean a home, an 285 office, a campus or mobile user equipment). 287 Latency is not the only concern of L4S: 289 * The "Low Loss" part of the name denotes that L4S generally 290 achieves zero congestion loss (which would otherwise cause 291 retransmission delays), due to its use of ECN. 293 * The "Scalable throughput" part of the name denotes that the per- 294 flow throughput of Scalable congestion controls should scale 295 indefinitely, avoiding the imminent scaling problems with 'TCP- 296 Friendly' congestion control algorithms [RFC3649]. 298 The former is clearly in scope of this AQM document. However, the 299 latter is an outcome of the end-system behaviour, and therefore 300 outside the scope of this AQM document, even though the AQM is an 301 enabler. 303 The overall L4S architecture [I-D.ietf-tsvwg-l4s-arch] gives more 304 detail, including on wider deployment aspects such as backwards 305 compatibility of Scalable congestion controls in bottlenecks where a 306 DualQ Coupled AQM has not been deployed. The supporting papers 307 [DualPI2Linux], [PI2], [DCttH19] and [PI2param] give the full 308 rationale for the AQM's design, both discursively and in more precise 309 mathematical form, as well as the results of performance evaluations. 310 The main results have been validated independently when using the 311 Prague congestion control [Boru20] (experiments are run using Prague 312 and DCTCP, but only the former are relevant for validation, because 313 Prague fixes a number of problems with the Linux DCTCP code that make 314 it unsuitable for the public Internet). 316 1.3. Terminology 318 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 319 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 320 document are to be interpreted as described in [RFC2119] when, and 321 only when, they appear in all capitals, as shown here. 323 The DualQ Coupled AQM uses two queues for two services. Each of the 324 following terms identifies both the service and the queue that 325 provides the service: 327 Classic service/queue: The Classic service is intended for all the 328 congestion control behaviours that co-exist with Reno [RFC5681] 329 (e.g. Reno itself, Cubic [RFC8312], TFRC [RFC5348]). 331 Low-Latency, Low-Loss Scalable throughput (L4S) service/queue: The 332 'L4S' service is intended for traffic from scalable congestion 333 control algorithms, such as TCP Prague 334 [I-D.briscoe-iccrg-prague-congestion-control], which was derived 335 from Data Center TCP [RFC8257]. The L4S service is for more 336 general traffic than just TCP Prague -- it allows the set of 337 congestion controls with similar scaling properties to Prague to 338 evolve, such as the examples listed earlier (Relentless, SCReAM, 339 etc.). 341 Classic Congestion Control: A congestion control behaviour that can 342 co-exist with standard TCP Reno [RFC5681] without causing 343 significantly negative impact on its flow rate [RFC5033]. With 344 Classic congestion controls, such as Reno or Cubic, because flow 345 rate has scaled since TCP congestion control was first designed in 346 1988, it now takes hundreds of round trips (and growing) to 347 recover after a congestion signal (whether a loss or an ECN mark) 348 as shown in the examples in section 5.1 of the L4S 349 architecture [I-D.ietf-tsvwg-l4s-arch] and in [RFC3649]. 350 Therefore control of queuing and utilization becomes very slack, 351 and the slightest disturbances (e.g. from new flows starting) 352 prevent a high rate from being attained. 354 Scalable Congestion Control: A congestion control where the average 355 time from one congestion signal to the next (the recovery time) 356 remains invariant as the flow rate scales, all other factors being 357 equal. This maintains the same degree of control over queueing 358 and utilization whatever the flow rate, as well as ensuring that 359 high throughput is robust to disturbances. For instance, DCTCP 360 averages 2 congestion signals per round-trip whatever the flow 361 rate, as do other recently developed scalable congestion controls, 362 e.g. Relentless TCP [Mathis09], TCP Prague 363 [I-D.briscoe-iccrg-prague-congestion-control], [PragueLinux], 364 BBRv2 [BBRv2], [I-D.cardwell-iccrg-bbr-congestion-control] and the 365 L4S variant of SCREAM for real-time media [SCReAM], [RFC8298]). 366 For the public Internet a Scalable transport has to comply with 367 the requirements in Section 4 of [I-D.ietf-tsvwg-ecn-l4s-id] 368 (aka. the 'Prague L4S requirements'). 370 C: Abbreviation for Classic, e.g. when used as a subscript. 372 L: Abbreviation for L4S, e.g. when used as a subscript. 374 The terms Classic or L4S can also qualify other nouns, such as 375 'codepoint', 'identifier', 'classification', 'packet', 'flow'. 376 For example: an L4S packet means a packet with an L4S identifier 377 sent from an L4S congestion control. 379 Both Classic and L4S services can cope with a proportion of 380 unresponsive or less-responsive traffic as well, but in the L4S 381 case its rate has to be smooth enough or low enough not to build a 382 queue (e.g. DNS, VoIP, game sync datagrams, etc). The DualQ 383 Coupled AQM behaviour is defined to be similar to a single FIFO 384 queue with respect to unresponsive and overload traffic. 386 Reno-friendly: The subset of Classic traffic that is friendly to the 387 standard Reno congestion control defined for TCP in [RFC5681]. 388 Reno-friendly is used in place of 'TCP-friendly', given the latter 389 has become imprecise, because the TCP protocol is now used with so 390 many different congestion control behaviours, and Reno is used in 391 non-TCP transports such as QUIC. 393 Classic ECN: The original Explicit Congestion Notification (ECN) 394 protocol [RFC3168], which requires ECN signals to be treated the 395 same as drops, both when generated in the network and when 396 responded to by the sender. 398 For L4S, the names used for the four codepoints of the 2-bit IP- 399 ECN field are unchanged from those defined in [RFC3168]: Not ECT, 400 ECT(0), ECT(1) and CE, where ECT stands for ECN-Capable Transport 401 and CE stands for Congestion Experienced. A packet marked with 402 the CE codepoint is termed 'ECN-marked' or sometimes just 'marked' 403 where the context makes ECN obvious. 405 1.4. Features 407 The AQM couples marking and/or dropping from the Classic queue to the 408 L4S queue in such a way that a flow will get roughly the same 409 throughput whichever it uses. Therefore both queues can feed into 410 the full capacity of a link and no rates need to be configured for 411 the queues. The L4S queue enables Scalable congestion controls like 412 DCTCP or TCP Prague to give very low and predictably low latency, 413 without compromising the performance of competing 'Classic' Internet 414 traffic. 416 Thousands of tests have been conducted in a typical fixed residential 417 broadband setting. Experiments used a range of base round trip 418 delays up to 100ms and link rates up to 200 Mb/s between the data 419 centre and home network, with varying amounts of background traffic 420 in both queues. For every L4S packet, the AQM kept the average 421 queuing delay below 1ms (or 2 packets where serialization delay 422 exceeded 1ms on slower links), with 99th percentile no worse than 423 2ms. No losses at all were introduced by the L4S AQM. Details of 424 the extensive experiments are available [DualPI2Linux], [PI2], 425 [DCttH19]. 427 In all these experiments, the host was connected to the home network 428 by fixed Ethernet, in order to quantify the queuing delay that can be 429 achieved by a user who cares about delay. It should be emphasized 430 that L4S support at the bottleneck link cannot 'undelay' bursts 431 introduced by another link on the path, for instance by legacy WiFi 432 equipment. However, if L4S support is added to the queue feeding the 433 _outgoing_ WAN link of a home gateway, it would be counterproductive 434 not to also reduce the burstiness of the _incoming_ WiFi. Also, 435 trials of WiFi equipment with an L4S DualQ Coupled AQM on the 436 _outgoing_ WiFi interface are in progress, and early results of an 437 L4S DualQ Coupled AQM in a 5G radio access network testbed with 438 emulated outdoor cell edge radio fading are given in [L4S_5G]. 440 Subjective testing has also been conducted by multiple people all 441 simultaneously using very demanding high bandwidth low latency 442 applications over a single shared access link [L4Sdemo16]. In one 443 application, each user could use finger gestures to pan or zoom their 444 own high definition (HD) sub-window of a larger video scene generated 445 on the fly in 'the cloud' from a football match. Another user 446 wearing VR goggles was remotely receiving a feed from a 360-degree 447 camera in a racing car, again with the sub-window in their field of 448 vision generated on the fly in 'the cloud' dependent on their head 449 movements. Even though other users were also downloading large 450 amounts of L4S and Classic data, playing a gaming benchmark and 451 watchings videos over the same 40Mb/s downstream broadband link, 452 latency was so low that the football picture appeared to stick to the 453 user's finger on the touch pad and the experience fed from the remote 454 camera did not noticeably lag head movements. All the L4S data (even 455 including the downloads) achieved the same very low latency. With an 456 alternative AQM, the video noticeably lagged behind the finger 457 gestures and head movements. 459 Unlike Diffserv Expedited Forwarding, the L4S queue does not have to 460 be limited to a small proportion of the link capacity in order to 461 achieve low delay. The L4S queue can be filled with a heavy load of 462 capacity-seeking flows (TCP Prague etc.) and still achieve low delay. 463 The L4S queue does not rely on the presence of other traffic in the 464 Classic queue that can be 'overtaken'. It gives low latency to L4S 465 traffic whether or not there is Classic traffic. The tail latency of 466 traffic served by the Classic AQM is sometimes a little better 467 sometimes a little worse, when a proportion of the traffic is L4S. 469 The two queues are only necessary because: 471 * the large variations (sawteeth) of Classic flows need roughly a 472 base RTT of queuing delay to ensure full utilization 474 * Scalable flows do not need a queue to keep utilization high, but 475 they cannot keep latency predictably low if they are mixed with 476 Classic traffic, 478 The L4S queue has latency priority within sub-round trip timescales, 479 but over longer periods the coupling from the Classic to the L4S AQM 480 (explained below) ensures that it does not have bandwidth priority 481 over the Classic queue. 483 2. DualQ Coupled AQM 485 There are two main aspects to the approach: 487 * The Coupled AQM that addresses throughput equivalence between 488 Classic (e.g. Reno, Cubic) flows and L4S flows (that satisfy the 489 Prague L4S requirements). 491 * The Dual Queue structure that provides latency separation for L4S 492 flows to isolate them from the typically large Classic queue. 494 2.1. Coupled AQM 496 In the 1990s, the `TCP formula' was derived for the relationship 497 between the steady-state congestion window, cwnd, and the drop 498 probability, p of standard Reno congestion control [RFC5681]. To a 499 first order approximation, the steady-state cwnd of Reno is inversely 500 proportional to the square root of p. 502 The design focuses on Reno as the worst case, because if it does no 503 harm to Reno, it will not harm Cubic or any traffic designed to be 504 friendly to Reno. TCP Cubic implements a Reno-compatibility mode, 505 which is relevant for typical RTTs under 20ms as long as the 506 throughput of a single flow is less than about 350Mb/s. In such 507 cases it can be assumed that Cubic traffic behaves similarly to Reno. 508 The term 'Classic' will be used for the collection of Reno-friendly 509 traffic including Cubic and potentially other experimental congestion 510 controls intended not to significantly impact the flow rate of Reno. 512 A supporting paper [PI2] includes the derivation of the equivalent 513 rate equation for DCTCP, for which cwnd is inversely proportional to 514 p (not the square root), where in this case p is the ECN marking 515 probability. DCTCP is not the only congestion control that behaves 516 like this, so the term 'Scalable' will be used for all similar 517 congestion control behaviours (see examples in Section 1.2). The 518 term 'L4S' is used for traffic driven by a Scalable congestion 519 control that also complies with the additional 'Prague L4S' 520 requirements [I-D.ietf-tsvwg-ecn-l4s-id]. 522 For safe co-existence, under stationary conditions, a Scalable flow 523 has to run at roughly the same rate as a Reno TCP flow (all other 524 factors being equal). So the drop or marking probability for Classic 525 traffic, p_C has to be distinct from the marking probability for L4S 526 traffic, p_L. The original ECN specification [RFC3168] required 527 these probabilities to be the same, but [RFC8311] updates RFC 3168 to 528 enable experiments in which these probabilities are different. 530 Also, to remain stable, Classic sources need the network to smooth 531 p_C so it changes relatively slowly. It is hard for a network node 532 to know the RTTs of all the flows, so a Classic AQM adds a _worst- 533 case_ RTT of smoothing delay (about 100-200 ms). In contrast, L4S 534 shifts responsibility for smoothing ECN feedback to the sender, which 535 only delays its response by its _own_ RTT, as well as allowing a more 536 immediate response if necessary. 538 The Coupled AQM achieves safe coexistence by making the Classic drop 539 probability p_C proportional to the square of the coupled L4S 540 probability p_CL. p_CL is an input to the instantaneous L4S marking 541 probability p_L but it changes as slowly as p_C. This makes the Reno 542 flow rate roughly equal the DCTCP flow rate, because the squaring of 543 p_CL counterbalances the square root of p_C in the 'TCP formula' of 544 Classic Reno congestion control. 546 Stating this as a formula, the relation between Classic drop 547 probability, p_C, and the coupled L4S probability p_CL needs to take 548 the form: 550 p_C = ( p_CL / k )^2 (1) 552 where k is the constant of proportionality, which is termed the 553 coupling factor. 555 2.2. Dual Queue 557 Classic traffic needs to build a large queue to prevent under- 558 utilization. Therefore a separate queue is provided for L4S traffic, 559 and it is scheduled with priority over the Classic queue. Priority 560 is conditional to prevent starvation of Classic traffic in certain 561 conditions (see Section 2.4). 563 Nonetheless, coupled marking ensures that giving priority to L4S 564 traffic still leaves the right amount of spare scheduling time for 565 Classic flows to each get equivalent throughput to DCTCP flows (all 566 other factors such as RTT being equal). 568 2.3. Traffic Classification 570 Both the Coupled AQM and DualQ mechanisms need an identifier to 571 distinguish L4S (L) and Classic (C) packets. Then the coupling 572 algorithm can achieve coexistence without having to inspect flow 573 identifiers, because it can apply the appropriate marking or dropping 574 probability to all flows of each type. A separate 575 specification [I-D.ietf-tsvwg-ecn-l4s-id] requires the network to 576 treat the ECT(1) and CE codepoints of the ECN field as this 577 identifier. An additional process document has proved necessary to 578 make the ECT(1) codepoint available for experimentation [RFC8311]. 580 For policy reasons, an operator might choose to steer certain packets 581 (e.g. from certain flows or with certain addresses) out of the L 582 queue, even though they identify themselves as L4S by their ECN 583 codepoints. In such cases, the L4S ECN 584 protocol [I-D.ietf-tsvwg-ecn-l4s-id] says that the device "MUST NOT 585 alter the end-to-end L4S ECN identifier", so that it is preserved 586 end-to-end. The aim is that each operator can choose how it treats 587 L4S traffic locally, but an individual operator does not alter the 588 identification of L4S packets, which would prevent other operators 589 downstream from making their own choices on how to treat L4S traffic. 591 In addition, an operator could use other identifiers to classify 592 certain additional packet types into the L queue that it deems will 593 not risk harm to the L4S service. For instance addresses of specific 594 applications or hosts; specific Diffserv codepoints such as EF 595 (Expedited Forwarding), Voice-Admit or the Non-Queue-Building (NQB) 596 per-hop behaviour; or certain protocols (e.g. ARP, DNS) (see 597 Section 5.4.1 of [I-D.ietf-tsvwg-ecn-l4s-id]). Note that the 598 mechanism only reads these identifiers. [I-D.ietf-tsvwg-ecn-l4s-id] 599 says it "MUST NOT alter these non-ECN identifiers". Thus, the L 600 queue is not solely an L4S queue, it can be considered more generally 601 as a low latency queue. 603 2.4. Overall DualQ Coupled AQM Structure 605 Figure 1 shows the overall structure that any DualQ Coupled AQM is 606 likely to have. This schematic is intended to aid understanding of 607 the current designs of DualQ Coupled AQMs. However, it is not 608 intended to preclude other innovative ways of satisfying the 609 normative requirements in Section 2.5 that minimally define a DualQ 610 Coupled AQM. Also, the schematic only illustrates operation under 611 normally expected circumstances; behaviour under overload or with 612 operator-specific classifiers is deferred to Section 2.5.1.1. 614 The classifier on the left separates incoming traffic between the two 615 queues (L and C). Each queue has its own AQM that determines the 616 likelihood of marking or dropping (p_L and p_C). It has been 617 proved [PI2] that it is preferable to control load with a linear 618 controller, then square the output before applying it as a drop 619 probability to Reno-friendly traffic (because Reno congestion control 620 decreases its load proportional to the square-root of the increase in 621 drop). So, the AQM for Classic traffic needs to be implemented in 622 two stages: i) a base stage that outputs an internal probability p' 623 (pronounced p-prime); and ii) a squaring stage that outputs p_C, 624 where 626 p_C = (p')^2. (2) 628 Substituting for p_C in Eqn (1) gives: 630 p' = p_CL / k 632 So the slow-moving input to ECN marking in the L queue (the coupled 633 L4S probability) is: 635 p_CL = k*p'. (3) 637 The actual ECN marking probability p_L that is applied to the L queue 638 needs to track the immediate L queue delay under L-only congestion 639 conditions, as well as track p_CL under coupled congestion 640 conditions. So the L queue uses a native AQM that calculates a 641 probability p'_L as a function of the instantaneous L queue delay. 642 And, given the L queue has conditional priority over the C queue, 643 whenever the L queue grows, the AQM ought to apply marking 644 probability p'_L, but p_L ought not to fall below p_CL. This 645 suggests: 647 p_L = max(p'_L, p_CL), (4) 649 which has also been found to work very well in practice. 651 The two transformations of p' in equations (2) and (3) implement the 652 required coupling given in equation (1) earlier. 654 The constant of proportionality or coupling factor, k, in equation 655 (1) determines the ratio between the congestion probabilities (loss 656 or marking) experienced by L4S and Classic traffic. Thus k 657 indirectly determines the ratio between L4S and Classic flow rates, 658 because flows (assuming they are responsive) adjust their rate in 659 response to congestion probability. Appendix C.2 gives guidance on 660 the choice of k and its effect on relative flow rates. 662 _________ 663 | | ,------. 664 L4S (L) queue | |===>| ECN | 665 ,'| _______|_| |marker|\ 666 <' | | `------'\\ 667 //`' v ^ p_L \\ 668 // ,-------. | \\ 669 // |Native |p'_L | \\,. 670 // | L4S |--->(MAX) < | ___ 671 ,----------.// | AQM | ^ p_CL `\|.'Cond-`. 672 | IP-ECN |/ `-------' | / itional \ 673 ==>|Classifier| ,-------. (k*p') [ priority]==> 674 | |\ | Base | | \scheduler/ 675 `----------'\\ | AQM |---->: ,'|`-.___.-' 676 \\ | |p' | <' | 677 \\ `-------' (p'^2) //`' 678 \\ ^ | // 679 \\,. | v p_C // 680 < | _________ .------.// 681 `\| | | | Drop |/ 682 Classic (C) |queue |===>|/mark | 683 __|______| `------' 685 Figure 1: DualQ Coupled AQM Schematic 687 Legend: ===> traffic flow; ---> control dependency. 689 After the AQMs have applied their dropping or marking, the scheduler 690 forwards their packets to the link. Even though the scheduler gives 691 priority to the L queue, it is not as strong as the coupling from the 692 C queue. This is because, as the C queue grows, the base AQM applies 693 more congestion signals to L traffic (as well as C). As L flows 694 reduce their rate in response, they use less than the scheduling 695 share for L traffic. So, because the scheduler is work preserving, 696 it schedules any C traffic in the gaps. 698 Giving priority to the L queue has the benefit of very low L queue 699 delay, because the L queue is kept empty whenever L traffic is 700 controlled by the coupling. Also there only has to be a coupling in 701 one direction - from Classic to L4S. Priority has to be conditional 702 in some way to prevent the C queue being starved in the short-term 703 (see Section 4.2.2) to give C traffic a means to push in, as 704 explained next. With normal responsive L traffic, the coupled ECN 705 marking gives C traffic the ability to push back against even strict 706 priority, by congestion marking the L traffic to make it yield some 707 space. However, if there is just a small finite set of C packets 708 (e.g. a DNS request or an initial window of data) some Classic AQMs 709 will not induce enough ECN marking in the L queue, no matter how long 710 the small set of C packets waits. Then, if the L queue happens to 711 remain busy, the C traffic would never get a scheduling opportunity 712 from a strict priority scheduler. Ideally the Classic AQM would be 713 designed to increase the coupled marking the longer that C packets 714 have been waiting, but this is not always practical - hence the need 715 for L priority to be conditional. Giving a small weight or limited 716 waiting time for C traffic improves response times for short Classic 717 messages, such as DNS requests, and improves Classic flow startup 718 because immediate capacity is available. 720 Example DualQ Coupled AQM algorithms called DualPI2 and Curvy RED are 721 given in Appendix A and Appendix B. Either example AQM can be used 722 to couple packet marking and dropping across a dual Q. 724 DualPI2 uses a Proportional-Integral (PI) controller as the Base AQM. 725 Indeed, this Base AQM with just the squared output and no L4S queue 726 can be used as a drop-in replacement for PIE [RFC8033], in which case 727 it is just called PI2 [PI2]. PI2 is a principled simplification of 728 PIE that is both more responsive and more stable in the face of 729 dynamically varying load. 731 Curvy RED is derived from RED [RFC2309], except its configuration 732 parameters are delay-based to make them insensitive to link rate and 733 it requires less operations per packet than RED. However, DualPI2 is 734 more responsive and stable over a wider range of RTTs than Curvy RED. 735 As a consequence, at the time of writing, DualPI2 has attracted more 736 development and evaluation attention than Curvy RED, leaving the 737 Curvy RED design not so fully evaluated. 739 Both AQMs regulate their queue in units of time rather than bytes. 740 As already explained, this ensures configuration can be invariant for 741 different drain rates. With AQMs in a dualQ structure this is 742 particularly important because the drain rate of each queue can vary 743 rapidly as flows for the two queues arrive and depart, even if the 744 combined link rate is constant. 746 It would be possible to control the queues with other alternative 747 AQMs, as long as the normative requirements (those expressed in 748 capitals) in Section 2.5 are observed. 750 The two queues could optionally be part of a larger queuing 751 hierarchy, such as the initial example ideas in 752 [I-D.briscoe-tsvwg-l4s-diffserv]. 754 2.5. Normative Requirements for a DualQ Coupled AQM 756 The following requirements are intended to capture only the essential 757 aspects of a DualQ Coupled AQM. They are intended to be independent 758 of the particular AQMs used for each queue. 760 2.5.1. Functional Requirements 762 A Dual Queue Coupled AQM implementation MUST comply with the 763 prerequisite L4S behaviours for any L4S network node (not just a 764 DualQ) as specified in section 5 of [I-D.ietf-tsvwg-ecn-l4s-id]. 765 These primarily concern classification and remarking as briefly 766 summarized in Section 2.3 earlier. But there is also a subsection 767 (5.5) giving guidance on reducing the burstiness of the link 768 technology underlying any L4S AQM. 770 A Dual Queue Coupled AQM implementation MUST utilize two queues, each 771 with an AQM algorithm. 773 The AQM algorithm for the low latency (L) queue MUST be able to apply 774 ECN marking to ECN-capable packets. 776 The scheduler draining the two queues MUST give L4S packets priority 777 over Classic, although priority MUST be bounded in order not to 778 starve Classic traffic (see Section 4.2.2). The scheduler SHOULD be 779 work-conserving, or otherwise close to work-conserving. This is 780 because Classic traffic needs to be able to efficiently fill any 781 space left by L4S traffic even though the scheduler would otherwise 782 allocate it to L4S. 784 [I-D.ietf-tsvwg-ecn-l4s-id] defines the meaning of an ECN marking on 785 L4S traffic, relative to drop of Classic traffic. In order to ensure 786 coexistence of Classic and Scalable L4S traffic, it says, "The 787 likelihood that an AQM drops a Not-ECT Classic packet (p_C) MUST be 788 roughly proportional to the square of the likelihood that it would 789 have marked it if it had been an L4S packet (p_L)." The term 790 'likelihood' is used to allow for marking and dropping to be either 791 probabilistic or deterministic. 793 For the current specification, this translates into the following 794 requirement. A DualQ Coupled AQM MUST apply ECN marking to traffic 795 in the L queue that is no lower than that derived from the likelihood 796 of drop (or ECN marking) in the Classic queue using Eqn. (1). 798 The constant of proportionality, k, in Eqn (1) determines the 799 relative flow rates of Classic and L4S flows when the AQM concerned 800 is the bottleneck (all other factors being equal). The L4S ECN 801 protocol [I-D.ietf-tsvwg-ecn-l4s-id] says, "The constant of 802 proportionality (k) does not have to be standardised for 803 interoperability, but a value of 2 is RECOMMENDED." 805 Assuming Scalable congestion controls for the Internet will be as 806 aggressive as DCTCP, this will ensure their congestion window will be 807 roughly the same as that of a standards track TCP Reno congestion 808 control (Reno) [RFC5681] and other Reno-friendly controls, such as 809 TCP Cubic in its Reno-compatibility mode. 811 The choice of k is a matter of operator policy, and operators MAY 812 choose a different value using the guidelines in Appendix C.2. 814 If multiple customers or users share capacity at a bottleneck 815 (e.g. in the Internet access link of a campus network), the 816 operator's choice of k will determine capacity sharing between the 817 flows of different customers. However, on the public Internet, 818 access network operators typically isolate customers from each other 819 with some form of layer-2 multiplexing (OFDM(A) in DOCSIS3.1, CDMA in 820 3G, SC-FDMA in LTE) or L3 scheduling (WRR in DSL), rather than 821 relying on host congestion controls to share capacity between 822 customers [RFC0970]. In such cases, the choice of k will solely 823 affect relative flow rates within each customer's access capacity, 824 not between customers. Also, k will not affect relative flow rates 825 at any times when all flows are Classic or all flows are L4S, and it 826 will not affect the relative throughput of small flows. 828 2.5.1.1. Requirements in Unexpected Cases 830 The flexibility to allow operator-specific classifiers (Section 2.3) 831 leads to the need to specify what the AQM in each queue ought to do 832 with packets that do not carry the ECN field expected for that queue. 833 It is expected that the AQM in each queue will inspect the ECN field 834 to determine what sort of congestion notification to signal, then it 835 will decide whether to apply congestion notification to this 836 particular packet, as follows: 838 * If a packet that does not carry an ECT(1) or CE codepoint is 839 classified into the L queue: 841 - if the packet is ECT(0), the L AQM SHOULD apply CE-marking 842 using a probability appropriate to Classic congestion control 843 and appropriate to the target delay in the L queue 845 - if the packet is Not-ECT, the appropriate action depends on 846 whether some other function is protecting the L queue from 847 misbehaving flows (e.g. per-flow queue protection 848 [I-D.briscoe-docsis-q-protection] or latency policing): 850 o If separate queue protection is provided, the L AQM SHOULD 851 ignore the packet and forward it unchanged, meaning it 852 should not calculate whether to apply congestion 853 notification and it should neither drop nor CE-mark the 854 packet (for instance, the operator might classify EF traffic 855 that is unresponsive to drop into the L queue, alongside 856 responsive L4S-ECN traffic) 858 o if separate queue protection is not provided, the L AQM 859 SHOULD apply drop using a drop probability appropriate to 860 Classic congestion control and appropriate to the target 861 delay in the L queue 863 * If a packet that carries an ECT(1) codepoint is classified into 864 the C queue: 866 - the C AQM SHOULD apply CE-marking using the coupled AQM 867 probability p_CL (= k*p'). 869 The above requirements are worded as "SHOULDs", because operator- 870 specific classifiers are for flexibility, by definition. Therefore, 871 alternative actions might be appropriate in the operator's specific 872 circumstances. An example would be where the operator knows that 873 certain legacy traffic marked with one codepoint actually has a 874 congestion response associated with another codepoint. 876 If the DualQ Coupled AQM has detected overload, it MUST introduce 877 Classic drop to both types of ECN-capable traffic until the overload 878 episode has subsided. Introducing drop if ECN marking is 879 persistently high is recommended by Section 7 of the ECN 880 specification [RFC3168] and Section 4.2.1 of the AQM 881 Recommendations [RFC7567]. 883 2.5.2. Management Requirements 884 2.5.2.1. Configuration 886 By default, a DualQ Coupled AQM SHOULD NOT need any configuration for 887 use at a bottleneck on the public Internet [RFC7567]. The following 888 parameters MAY be operator-configurable, e.g. to tune for non- 889 Internet settings: 891 * Optional packet classifier(s) to use in addition to the ECN field 892 (see Section 2.3); 894 * Expected typical RTT, which can be used to determine the queuing 895 delay of the Classic AQM at its operating point, in order to 896 prevent typical lone flows from under-utilizing capacity. For 897 example: 899 - for the PI2 algorithm (Appendix A) the queuing delay target is 900 dependent on the typical RTT; 902 - for the Curvy RED algorithm (Appendix B) the queuing delay at 903 the desired operating point of the curvy ramp is configured to 904 encompass a typical RTT; 906 - if another Classic AQM was used, it would be likely to need an 907 operating point for the queue based on the typical RTT, and if 908 so it SHOULD be expressed in units of time. 910 An operating point that is manually calculated might be directly 911 configurable instead, e.g. for links with large numbers of flows 912 where under-utilization by a single flow would be unlikely. 914 * Expected maximum RTT, which can be used to set the stability 915 parameter(s) of the Classic AQM. For example: 917 - for the PI2 algorithm (Appendix A), the gain parameters of the 918 PI algorithm depend on the maximum RTT. 920 - for the Curvy RED algorithm (Appendix B) the smoothing 921 parameter is chosen to filter out transients in the queue 922 within a maximum RTT. 924 Stability parameter(s) that are manually calculated assuming a 925 maximum RTT might be directly configurable instead. 927 * Coupling factor, k (see Appendix C.2); 929 * A limit to the conditional priority of L4S. This is scheduler- 930 dependent, but it SHOULD be expressed as a relation between the 931 max delay of a C packet and an L packet. For example: 933 - for a WRR scheduler a weight ratio between L and C of w:1 means 934 that the maximum delay to a C packet is w times that of an L 935 packet. 937 - for a time-shifted FIFO (TS-FIFO) scheduler (see Section 4.2.2) 938 a time-shift of tshift means that the maximum delay to a C 939 packet is tshift greater than that of an L packet. tshift could 940 be expressed as a multiple of the typical RTT rather than as an 941 absolute delay. 943 * The maximum Classic ECN marking probability, p_Cmax, before 944 introducing drop. 946 2.5.2.2. Monitoring 948 An experimental DualQ Coupled AQM SHOULD allow the operator to 949 monitor each of the following operational statistics on demand, per 950 queue and per configurable sample interval, for performance 951 monitoring and perhaps also for accounting in some cases: 953 * Bits forwarded, from which utilization can be calculated; 955 * Total packets in the three categories: arrived, presented to the 956 AQM, and forwarded. The difference between the first two will 957 measure any non-AQM tail discard. The difference between the last 958 two will measure proactive AQM discard; 960 * ECN packets marked, non-ECN packets dropped, ECN packets dropped, 961 which can be combined with the three total packet counts above to 962 calculate marking and dropping probabilities; 964 * Queue delay (not including serialization delay of the head packet 965 or medium acquisition delay) - see further notes below. 967 Unlike the other statistics, queue delay cannot be captured in a 968 simple accumulating counter. Therefore the type of queue delay 969 statistics produced (mean, percentiles, etc.) will depend on 970 implementation constraints. To facilitate comparative evaluation 971 of different implementations and approaches, an implementation 972 SHOULD allow mean and 99th percentile queue delay to be derived 973 (per queue per sample interval). A relatively simple way to do 974 this would be to store a coarse-grained histogram of queue delay. 975 This could be done with a small number of bins with configurable 976 edges that represent contiguous ranges of queue delay. Then, over 977 a sample interval, each bin would accumulate a count of the number 978 of packets that had fallen within each range. The maximum queue 979 delay per queue per interval MAY also be recorded, to aid 980 diagnosis of faults and anomalous events. 982 2.5.2.3. Anomaly Detection 984 An experimental DualQ Coupled AQM SHOULD asynchronously report the 985 following data about anomalous conditions: 987 * Start-time and duration of overload state. 989 A hysteresis mechanism SHOULD be used to prevent flapping in and 990 out of overload causing an event storm. For instance, exit from 991 overload state could trigger one report, but also latch a timer. 992 Then, during that time, if the AQM enters and exits overload state 993 any number of times, the duration in overload state is accumulated 994 but no new report is generated until the first time the AQM is out 995 of overload once the timer has expired. 997 2.5.2.4. Deployment, Coexistence and Scaling 999 [RFC5706] suggests that deployment, coexistence and scaling should 1000 also be covered as management requirements. The raison d'etre of the 1001 DualQ Coupled AQM is to enable deployment and coexistence of Scalable 1002 congestion controls - as incremental replacements for today's Reno- 1003 friendly controls that do not scale with bandwidth-delay product. 1004 Therefore there is no need to repeat these motivating issues here 1005 given they are already explained in the Introduction and detailed in 1006 the L4S architecture [I-D.ietf-tsvwg-l4s-arch]. 1008 The descriptions of specific DualQ Coupled AQM algorithms in the 1009 appendices cover scaling of their configuration parameters, e.g. with 1010 respect to RTT and sampling frequency. 1012 3. IANA Considerations (to be removed by RFC Editor) 1014 This specification contains no IANA considerations. 1016 4. Security Considerations 1018 4.1. Low Delay without Requiring Per-Flow Processing 1020 The L4S architecture [I-D.ietf-tsvwg-l4s-arch] compares the DualQ and 1021 per-flow-queuing (FQ) approaches to L4S. The privacy considerations 1022 section in that document motivates the DualQ on the grounds that 1023 users who want to encrypt application flow identifiers, e.g. in IPSec 1024 or other encrypted VPN tunnels, don't have to sacrifice low delay 1025 ([RFC8404] encourages avoidance of such privacy compromises). 1027 The security considerations section of the L4S architecture also 1028 includes subsections on policing of relative flow-rates (section 8.1) 1029 and on policing of flows that cause excessive queuing delay (section 1030 8.2). It explains that the interests of users do not collide in the 1031 same way for delay as they do for bandwidth. For someone to get more 1032 of the bandwidth of a shared link, someone else necessarily gets less 1033 (a 'zero-sum game'), whereas queuing delay can be reduced for 1034 everyone, without any need for someone else to lose out. It also 1035 explains that, on the current Internet, scheduling usually enforces 1036 separation between 'sites' (e.g. households, businesses or mobile 1037 users), but it is not common to need to schedule or police individual 1038 application flows. 1040 By the above arguments, per-flow policing might not be necessary and 1041 in trusted environments it is certainly unlikely to be needed. 1042 Therefore, because it is hard to avoid complexity and unintended 1043 side-effects with per-flow policing, it needs to be separable from a 1044 basic AQM, as an option, under policy control. On this basis, the 1045 DualQ Coupled AQM provides low delay without prejudging the question 1046 of per-flow policing. 1048 Nonetheless, the interests of users or flows might conflict, e.g. in 1049 case of accident or malice. Then per-flow control could be 1050 necessary. If flow-rate control is needed, it can be provided as a 1051 modular addition to a DualQ. And similarly, if protection against 1052 excessive queue delay is needed, a per-flow queue protection option 1053 can be added to a DualQ (e.g. [I-D.briscoe-docsis-q-protection]). 1055 4.2. Handling Unresponsive Flows and Overload 1057 In the absence of any per-flow control, it is important that the 1058 basic DualQ Coupled AQM gives unresponsive flows no more throughput 1059 advantage than a single-queue AQM would, and that it at least handles 1060 overload situations. Overload means that incoming load significantly 1061 or persistently exceeds output capacity, but it is not intended to be 1062 a precise term -- significant and persistent are matters of degree. 1064 A trade-off needs to be made between complexity and the risk of 1065 either traffic class harming the other. In overloaded conditions the 1066 higher priority L4S service will have to sacrifice some aspect of its 1067 performance. Depending on the degree of overload, alternative 1068 solutions may relax a different factor: e.g. throughput, delay, drop. 1069 These choices need to be made either by the developer or by operator 1070 policy, rather than by the IETF. Subsequent subsections discuss 1071 aspects relating to handling of different degrees of overload: 1073 * Unresponsive flows (L and/or C) but not overloaded, i.e. the sum 1074 of unresponsive load before adding any responsive traffic is below 1075 capacity; 1077 This case is handled by the regular Coupled DualQ (Section 2.1) 1078 but not discussed there. So below, Section 4.2.1 explains the 1079 design goal, and how it is achieved in practice; 1081 * Unresponsive flows (L and/or C) causing persistent overload, 1082 i.e. the sum of unresponsive load even before adding any 1083 responsive traffic persistently exceeds capacity; 1085 This case is not covered by the regular Coupled DualQ mechanism 1086 (Section 2.1) but the last para in Section 2.5.1.1 sets out a 1087 requirement to handle the case where ECN-capable traffic could 1088 starve non-ECN-capable traffic. Section 4.2.3 below discusses 1089 the general options and gives specific examples. 1091 * Short-term overload that lies between the 'not overloaded' and 1092 'persistently overloaded' cases. 1094 For the period before overload is deemed persistent, 1095 Section 4.2.2 discusses options for more immediate mechanisms 1096 at the scheduler timescale. These prevent short-term 1097 starvation of the C queue by making the priority of the L queue 1098 conditional, as required in Section 2.5.1. 1100 4.2.1. Unresponsive Traffic without Overload 1102 When one or more L flows and/or C flows are unresponsive, but their 1103 total load is within the link capacity so that they do not saturate 1104 the coupled marking (below 100%), the goal of a DualQ AQM is to 1105 behave no worse than a single-queue AQM. 1107 Tests have shown that this is indeed the case with no additional 1108 mechanism beyond the regular Coupled DualQ of Section 2.1 (see the 1109 results of 'overload experiments' in [DCttH19]). Perhaps counter- 1110 intuitively, whether the unresponsive flow classifies itself into the 1111 L or the C queue, the DualQ system behaves as if it has subtracted 1112 from the overall link capacity. Then, the coupling shares out the 1113 remaining capacity between any competing responsive flows (in either 1114 queue). See also Section 4.2.2, which discusses scheduler-specific 1115 details. 1117 4.2.2. Avoiding Short-Term Classic Starvation: Sacrifice L4S Throughput 1118 or Delay? 1120 Priority of L4S is required to be conditional (see Section 2.4 & 1121 Section 2.5.1) to avoid short-term starvation of Classic. Otherwise, 1122 as explained in Section 2.4, even a lone responsive L4S flow could 1123 temporarily block a small finite set of C packets (e.g. an initial 1124 window or DNS request). The blockage would only be brief, but it 1125 could be longer for certain AQM implementations that can only 1126 increase the congestion signal coupled from the C queue when C 1127 packets are actually being dequeued. There is then the question of 1128 whether to sacrifice L4S throughput or L4S delay (or some other 1129 policy) to make the priority conditional: 1131 Sacrifice L4S throughput: By using weighted round robin as the 1132 conditional priority scheduler, the L4S service can sacrifice some 1133 throughput during overload. This can either be thought of as 1134 guaranteeing a minimum throughput service for Classic traffic, or 1135 as guaranteeing a maximum delay for a packet at the head of the 1136 Classic queue. 1138 Cautionary note: a WRR scheduler can only guarantee Classic 1139 throughput if Classic sources are sending enough to use it -- 1140 congestion signals can undermine scheduling because they determine 1141 how much responsive traffic of each class arrives for scheduling 1142 in the first place. This is why scheduling is only relied on to 1143 handle short-term starvation; until congestion signals build up 1144 and the sources react. Even during long-term overload (discussed 1145 more fully in Section 4.2.3), it's pragmatic to discard packets 1146 from both queues, which again thins the traffic before it reaches 1147 the scheduler. This is because a scheduler cannot be relied on to 1148 handle long-term overload since the right scheduler weight cannot 1149 be known for every scenario. 1151 The scheduling weight of the Classic queue should be small 1152 (e.g. 1/16). In most traffic scenarios the scheduler will not 1153 interfere and it will not need to, because the coupling mechanism 1154 and the end-systems will determine the share of capacity across 1155 both queues as if it were a single pool. However, if L4S traffic 1156 is over-aggressive or unresponsive, the scheduler weight for 1157 Classic traffic will at least be large enough to ensure it does 1158 not starve in the short-term. 1160 Although WRR scheduling is only expected to address short-term 1161 overload, there are (somewhat rare) cases when WRR has an effect 1162 on capacity shares over longer time-scales. But its effect is 1163 minor, and it certainly does no harm. Specifically, in cases 1164 where the ratio of L4S to Classic flows (e.g. 19:1) is greater 1165 than the ratio of their scheduler weights (e.g. 15:1), the L4S 1166 flows will get less than an equal share of the capacity, but only 1167 slightly. For instance, with the example numbers given, each L4S 1168 flow will get (15/16)/19 = 4.9% when ideally each would get 1169 1/20=5%. In the rather specific case of an unresponsive flow 1170 taking up just less than the capacity set aside for L4S 1171 (e.g. 14/16 in the above example), using WRR could significantly 1172 reduce the capacity left for any responsive L4S flows. 1174 The scheduling weight of the Classic queue should not be too 1175 small, otherwise a C packet at the head of the queue could be 1176 excessively delayed by a continually busy L queue. For instance 1177 if the Classic weight is 1/16, the maximum that a Classic packet 1178 at the head of the queue can be delayed by L traffic is the 1179 serialization delay of 15 MTU-sized packets. 1181 Sacrifice L4S Delay: The operator could choose to control overload 1182 of the Classic queue by allowing some delay to 'leak' across to 1183 the L4S queue. The scheduler can be made to behave like a single 1184 First-In First-Out (FIFO) queue with different service times by 1185 implementing a very simple conditional priority scheduler that 1186 could be called a "time-shifted FIFO" (see the Modifier Earliest 1187 Deadline First (MEDF) scheduler [MEDF]). This scheduler adds 1188 tshift to the queue delay of the next L4S packet, before comparing 1189 it with the queue delay of the next Classic packet, then it 1190 selects the packet with the greater adjusted queue delay. 1192 Under regular conditions, this time-shifted FIFO scheduler behaves 1193 just like a strict priority scheduler. But under moderate or high 1194 overload it prevents starvation of the Classic queue, because the 1195 time-shift (tshift) defines the maximum extra queuing delay of 1196 Classic packets relative to L4S. This would control milder 1197 overload of responsive traffic by introducing delay to defer 1198 invoking the overload mechanisms in Section 4.2.3, particularly 1199 when close to the maximum congestion signal. 1201 The example implementations in Appendix A and Appendix B could both 1202 be implemented with either policy. 1204 4.2.3. L4S ECN Saturation: Introduce Drop or Delay? 1206 This section concerns persistent overload caused by unresponsive L 1207 and/or C flows. To keep the throughput of both L4S and Classic flows 1208 roughly equal over the full load range, a different control strategy 1209 needs to be defined above the point where the L4S AQM persistently 1210 saturates to an ECN marking probability of 100% leaving no room to 1211 push back the load any harder. L4S ECN marking will saturate first 1212 (assuming the coupling factor k>1), even though saturation could be 1213 caused by the sum of unresponsive traffic in either or both queues 1214 exceeding the link capacity. 1216 The term 'unresponsive' includes cases where a flow becomes 1217 temporarily unresponsive, for instance, a real-time flow that takes a 1218 while to adapt its rate in response to congestion, or a standard Reno 1219 flow that is normally responsive, but above a certain congestion 1220 level it will not be able to reduce its congestion window below the 1221 allowed minimum of 2 segments [RFC5681], effectively becoming 1222 unresponsive. (Note that L4S traffic ought to remain responsive 1223 below a window of 2 segments (see the L4S 1224 requirements [I-D.ietf-tsvwg-ecn-l4s-id]). 1226 Saturation raises the question of whether to relieve congestion by 1227 introducing some drop into the L4S queue or by allowing delay to grow 1228 in both queues (which could eventually lead to drop due to buffer 1229 exhaustion anyway): 1231 Drop on Saturation: Persistent saturation can be defined by a 1232 maximum threshold for coupled L4S ECN marking (assuming k>1) 1233 before saturation starts to make the flow rates of the different 1234 traffic types diverge. Above that, the drop probability of 1235 Classic traffic is applied to all packets of all traffic types. 1236 Then experiments have shown that queueing delay can be kept at the 1237 target in any overload situation, including with unresponsive 1238 traffic, and no further measures are required (Section 4.2.3.1). 1240 Delay on Saturation: When L4S marking saturates, instead of 1241 introducing L4S drop, the drop and marking probabilities of both 1242 queues could be capped. Beyond that, delay will grow either 1243 solely in the queue with unresponsive traffic (if WRR is used), or 1244 in both queues (if time-shifted FIFO is used). In either case, 1245 the higher delay ought to control temporary high congestion. If 1246 the overload is more persistent, eventually the combined DualQ 1247 will overflow and tail drop will control congestion. 1249 The example implementation in Appendix A solely applies the "drop on 1250 saturation" policy. The DOCSIS specification of a DualQ Coupled 1251 AQM [DOCSIS3.1] also implements the 'drop on saturation' policy with 1252 a very shallow L buffer. However, the addition of DOCSIS per-flow 1253 Queue Protection [I-D.briscoe-docsis-q-protection] turns this into 1254 'delay on saturation' by redirecting some packets of the flow(s) most 1255 responsible for L queue overload into the C queue, which has a higher 1256 delay target. If overload continues, this again becomes 'drop on 1257 saturation' as the level of drop in the C queue rises to maintain the 1258 target delay of the C queue. 1260 4.2.3.1. Protecting against Overload by Unresponsive ECN-Capable 1261 Traffic 1263 Without a specific overload mechanism, unresponsive traffic would 1264 have a greater advantage if it were also ECN-capable. The advantage 1265 is undetectable at normal low levels of marking. However, it would 1266 become significant with the higher levels of marking typical during 1267 overload, when it could evade a significant degree of drop. This is 1268 an issue whether the ECN-capable traffic is L4S or Classic. 1270 This raises the question of whether and when to introduce drop of 1271 ECN-capable traffic, as required by both Section 7 of the ECN 1272 spec [RFC3168] and Section 4.2.1 of the AQM 1273 recommendations [RFC7567]. 1275 As an example, experiments with the DualPI2 AQM (Appendix A) have 1276 shown that introducing 'drop on saturation' at 100% coupled L4S 1277 marking addresses this problem with unresponsive ECN as well as 1278 addressing the saturation problem. At saturation, DualPI2 switches 1279 into overload mode, where the base AQM is driven by the max delay of 1280 both queues and it introduces probabilistic drop to both queues 1281 equally. It leaves only a small range of congestion levels just 1282 below saturation where unresponsive traffic gains any advantage from 1283 using the ECN capability (relative to being unresponsive without 1284 ECN), and the advantage is hardly detectable (see [DualQ-Test] and 1285 section IV-E of [DCttH19]. Also overload with an unresponsive ECT(1) 1286 flow gets no more bandwidth advantage than with ECT(0). 1288 5. Acknowledgements 1290 Thanks to Anil Agarwal, Sowmini Varadhan's, Gabi Bracha, Nicolas 1291 Kuhn, Greg Skinner, Tom Henderson, David Pullen, Mirja Kuehlewind, 1292 Gorry Fairhurst, Pete Heist and Ermin Sakic for detailed review 1293 comments particularly of the appendices and suggestions on how to 1294 make the explanations clearer. Thanks also to Tom Henderson for 1295 insights on the choice of schedulers and queue delay measurement 1296 techniques. 1298 The early contributions of Koen De Schepper, Bob Briscoe, Olga 1299 Bondarenko and Inton Tsang were part-funded by the European Community 1300 under its Seventh Framework Programme through the Reducing Internet 1301 Transport Latency (RITE) project (ICT-317700). Contributions of Koen 1302 De Schepper and Olivier Tilmans were also part-funded by the 5Growth 1303 and DAEMON EU H2020 projects. Bob Briscoe's contribution was also 1304 part-funded by the Comcast Innovation Fund and the Research Council 1305 of Norway through the TimeIn project. The views expressed here are 1306 solely those of the authors. 1308 6. Contributors 1310 The following contributed implementations and evaluations that 1311 validated and helped to improve this specification: 1313 Olga Albisser of Simula Research Lab, Norway 1314 (Olga Bondarenko during early drafts) implemented the prototype 1315 DualPI2 AQM for Linux with Koen De Schepper and conducted 1316 extensive evaluations as well as implementing the live performance 1317 visualization GUI [L4Sdemo16]. 1319 Olivier Tilmans of Nokia 1320 Bell Labs, Belgium prepared and maintains the Linux implementation 1321 of DualPI2 for upstreaming. 1323 Shravya K.S. wrote a model for the ns-3 simulator based on the -01 1324 version of this Internet-Draft. Based on this initial work, Tom 1325 Henderson updated that earlier model and created a 1326 model for the DualQ variant specified as part of the Low Latency 1327 DOCSIS specification, as well as conducting extensive evaluations. 1329 Ing Jyh (Inton) Tsang of Nokia, Belgium built the End-to-End Data 1330 Centre to the Home broadband testbed on which DualQ Coupled AQM 1331 implementations were tested. 1333 7. References 1335 7.1. Normative References 1337 [I-D.ietf-tsvwg-ecn-l4s-id] 1338 Schepper, K. D. and B. Briscoe, "Explicit Congestion 1339 Notification (ECN) Protocol for Very Low Queuing Delay 1340 (L4S)", Work in Progress, Internet-Draft, draft-ietf- 1341 tsvwg-ecn-l4s-id-25, 4 March 2022, 1342 . 1345 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1346 Requirement Levels", BCP 14, RFC 2119, 1347 DOI 10.17487/RFC2119, March 1997, 1348 . 1350 [RFC3168] Ramakrishnan, K., Floyd, S., and D. Black, "The Addition 1351 of Explicit Congestion Notification (ECN) to IP", 1352 RFC 3168, DOI 10.17487/RFC3168, September 2001, 1353 . 1355 [RFC8311] Black, D., "Relaxing Restrictions on Explicit Congestion 1356 Notification (ECN) Experimentation", RFC 8311, 1357 DOI 10.17487/RFC8311, January 2018, 1358 . 1360 7.2. Informative References 1362 [Alizadeh-stability] 1363 Alizadeh, M., Javanmard, A., and B. Prabhakar, "Analysis 1364 of DCTCP: Stability, Convergence, and Fairness", ACM 1365 SIGMETRICS 2011 , June 2011, 1366 . 1368 [AQMmetrics] 1369 Kwon, M. and S. Fahmy, "A Comparison of Load-based and 1370 Queue- based Active Queue Management Algorithms", Proc. 1371 Int'l Soc. for Optical Engineering (SPIE) 4866:35--46 DOI: 1372 10.1117/12.473021, 2002, 1373 . 1375 [ARED01] Floyd, S., Gummadi, R., and S. Shenker, "Adaptive RED: An 1376 Algorithm for Increasing the Robustness of RED's Active 1377 Queue Management", ACIRI Technical Report , August 2001, 1378 . 1380 [BBRv2] Cardwell, N., "BRTCP BBR v2 Alpha/Preview Release", github 1381 repository; Linux congestion control module, 1382 . 1384 [Boru20] Boru Oljira, D., Grinnemo, K-J., Brunstrom, A., and J. 1385 Taheri, "Validating the Sharing Behavior and Latency 1386 Characteristics of the L4S Architecture", ACM CCR 1387 50(2):37--44, May 2020, 1388 . 1390 [CCcensus19] 1391 Mishra, A., Sun, X., Jain, A., Pande, S., Joshi, R., and 1392 B. Leong, "The Great Internet TCP Congestion Control 1393 Census", Proc. ACM on Measurement and Analysis of 1394 Computing Systems 3(3), December 2019, 1395 . 1397 [CoDel] Nichols, K. and V. Jacobson, "Controlling Queue Delay", 1398 ACM Queue 10(5), May 2012, 1399 . 1401 [CRED_Insights] 1402 Briscoe, B., "Insights from Curvy RED (Random Early 1403 Detection)", BT Technical Report TR-TUB8-2015-003 1404 arXiv:1904.07339 [cs.NI], July 2015, 1405 . 1407 [DCttH19] De Schepper, K., Bondarenko, O., Tilmans, O., and B. 1408 Briscoe, "`Data Centre to the Home': Ultra-Low Latency for 1409 All", Updated RITE project Technical Report , July 2019, 1410 . 1412 [DOCSIS3.1] 1413 CableLabs, "MAC and Upper Layer Protocols Interface 1414 (MULPI) Specification, CM-SP-MULPIv3.1", Data-Over-Cable 1415 Service Interface Specifications DOCSIS® 3.1 Version i17 1416 or later, 21 January 2019, . 1419 [DualPI2Linux] 1420 Albisser, O., De Schepper, K., Briscoe, B., Tilmans, O., 1421 and H. Steen, "DUALPI2 - Low Latency, Low Loss and 1422 Scalable (L4S) AQM", Proc. Linux Netdev 0x13 , March 2019, 1423 . 1426 [DualQ-Test] 1427 Steen, H., "Destruction Testing: Ultra-Low Delay using 1428 Dual Queue Coupled Active Queue Management", Masters 1429 Thesis, Dept of Informatics, Uni Oslo , May 2017, 1430 . 1433 [Heist21] Heist, P. and J. Morton, "L4S Tests", github README, 1434 August 2021, . 1437 [I-D.briscoe-docsis-q-protection] 1438 Briscoe, B. and G. White, "The DOCSIS(r) Queue Protection 1439 Algorithm to Preserve Low Latency", Work in Progress, 1440 Internet-Draft, draft-briscoe-docsis-q-protection-03, 7 1441 March 2022, . 1444 [I-D.briscoe-iccrg-prague-congestion-control] 1445 Schepper, K. D., Tilmans, O., and B. Briscoe, "Prague 1446 Congestion Control", Work in Progress, Internet-Draft, 1447 draft-briscoe-iccrg-prague-congestion-control-00, 9 March 1448 2021, . 1451 [I-D.briscoe-tsvwg-l4s-diffserv] 1452 Briscoe, B., "Interactions between Low Latency, Low Loss, 1453 Scalable Throughput (L4S) and Differentiated Services", 1454 Work in Progress, Internet-Draft, draft-briscoe-tsvwg-l4s- 1455 diffserv-02, 4 November 2018, 1456 . 1459 [I-D.cardwell-iccrg-bbr-congestion-control] 1460 Cardwell, N., Cheng, Y., Yeganeh, S. H., Swett, I., and V. 1461 Jacobson, "BBR Congestion Control", Work in Progress, 1462 Internet-Draft, draft-cardwell-iccrg-bbr-congestion- 1463 control-02, 7 March 2022, 1464 . 1467 [I-D.ietf-tsvwg-l4s-arch] 1468 Briscoe, B., Schepper, K. D., Bagnulo, M., and G. White, 1469 "Low Latency, Low Loss, Scalable Throughput (L4S) Internet 1470 Service: Architecture", Work in Progress, Internet-Draft, 1471 draft-ietf-tsvwg-l4s-arch-17, 4 March 2022, 1472 . 1475 [L4Sdemo16] 1476 Bondarenko, O., De Schepper, K., Tsang, I., and B. 1477 Briscoe, "Ultra-Low Delay for All: Live Experience, Live 1478 Analysis", Proc. MMSYS'16 pp33:1--33:4, May 2016, 1479 . 1483 [L4S_5G] Willars, P., Wittenmark, E., Ronkainen, H., Östberg, C., 1484 Johansson, I., Strand, J., Lédl, P., and D. Schnieders, 1485 "Enabling time-critical applications over 5G with rate 1486 adaptation", Ericsson - Deutsche Telekom White Paper BNEW- 1487 21:025455 Uen, May 2021, . 1491 [Labovitz10] 1492 Labovitz, C., Iekel-Johnson, S., McPherson, D., Oberheide, 1493 J., and F. Jahanian, "Internet Inter-Domain Traffic", Proc 1494 ACM SIGCOMM; ACM CCR 40(4):75--86, August 2010, 1495 . 1497 [LLD] White, G., Sundaresan, K., and B. Briscoe, "Low Latency 1498 DOCSIS: Technology Overview", CableLabs White Paper , 1499 February 2019, . 1502 [Mathis09] Mathis, M., "Relentless Congestion Control", PFLDNeT'09 , 1503 May 2009, . 1506 [MEDF] Menth, M., Schmid, M., Heiss, H., and T. Reim, "MEDF - a 1507 simple scheduling algorithm for two real-time transport 1508 service classes with application in the UTRAN", Proc. IEEE 1509 Conference on Computer Communications (INFOCOM'03) Vol.2 1510 pp.1116-1122, March 2003, 1511 . 1513 [PI2] De Schepper, K., Bondarenko, O., Briscoe, B., and I. 1514 Tsang, "PI2: A Linearized AQM for both Classic and 1515 Scalable TCP", ACM CoNEXT'16 , December 2016, 1516 . 1519 [PI2param] Briscoe, B., "PI2 Parameters", Technical Report TR-BB- 1520 2021-001 arXiv:2107.01003 [cs.NI], July 2021, 1521 . 1523 [PragueLinux] 1524 Briscoe, B., De Schepper, K., Albisser, O., Misund, J., 1525 Tilmans, O., Kühlewind, M., and A.S. Ahmed, "Implementing 1526 the `TCP Prague' Requirements for Low Latency Low Loss 1527 Scalable Throughput (L4S)", Proc. Linux Netdev 0x13 , 1528 March 2019, . 1531 [RFC0970] Nagle, J., "On Packet Switches With Infinite Storage", 1532 RFC 970, DOI 10.17487/RFC0970, December 1985, 1533 . 1535 [RFC2309] Braden, B., Clark, D., Crowcroft, J., Davie, B., Deering, 1536 S., Estrin, D., Floyd, S., Jacobson, V., Minshall, G., 1537 Partridge, C., Peterson, L., Ramakrishnan, K., Shenker, 1538 S., Wroclawski, J., and L. Zhang, "Recommendations on 1539 Queue Management and Congestion Avoidance in the 1540 Internet", RFC 2309, DOI 10.17487/RFC2309, April 1998, 1541 . 1543 [RFC2914] Floyd, S., "Congestion Control Principles", BCP 41, 1544 RFC 2914, DOI 10.17487/RFC2914, September 2000, 1545 . 1547 [RFC3246] Davie, B., Charny, A., Bennet, J.C.R., Benson, K., Le 1548 Boudec, J.Y., Courtney, W., Davari, S., Firoiu, V., and D. 1549 Stiliadis, "An Expedited Forwarding PHB (Per-Hop 1550 Behavior)", RFC 3246, DOI 10.17487/RFC3246, March 2002, 1551 . 1553 [RFC3649] Floyd, S., "HighSpeed TCP for Large Congestion Windows", 1554 RFC 3649, DOI 10.17487/RFC3649, December 2003, 1555 . 1557 [RFC5033] Floyd, S. and M. Allman, "Specifying New Congestion 1558 Control Algorithms", BCP 133, RFC 5033, 1559 DOI 10.17487/RFC5033, August 2007, 1560 . 1562 [RFC5348] Floyd, S., Handley, M., Padhye, J., and J. Widmer, "TCP 1563 Friendly Rate Control (TFRC): Protocol Specification", 1564 RFC 5348, DOI 10.17487/RFC5348, September 2008, 1565 . 1567 [RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion 1568 Control", RFC 5681, DOI 10.17487/RFC5681, September 2009, 1569 . 1571 [RFC5706] Harrington, D., "Guidelines for Considering Operations and 1572 Management of New Protocols and Protocol Extensions", 1573 RFC 5706, DOI 10.17487/RFC5706, November 2009, 1574 . 1576 [RFC7567] Baker, F., Ed. and G. Fairhurst, Ed., "IETF 1577 Recommendations Regarding Active Queue Management", 1578 BCP 197, RFC 7567, DOI 10.17487/RFC7567, July 2015, 1579 . 1581 [RFC8033] Pan, R., Natarajan, P., Baker, F., and G. White, 1582 "Proportional Integral Controller Enhanced (PIE): A 1583 Lightweight Control Scheme to Address the Bufferbloat 1584 Problem", RFC 8033, DOI 10.17487/RFC8033, February 2017, 1585 . 1587 [RFC8034] White, G. and R. Pan, "Active Queue Management (AQM) Based 1588 on Proportional Integral Controller Enhanced PIE) for 1589 Data-Over-Cable Service Interface Specifications (DOCSIS) 1590 Cable Modems", RFC 8034, DOI 10.17487/RFC8034, February 1591 2017, . 1593 [RFC8257] Bensley, S., Thaler, D., Balasubramanian, P., Eggert, L., 1594 and G. Judd, "Data Center TCP (DCTCP): TCP Congestion 1595 Control for Data Centers", RFC 8257, DOI 10.17487/RFC8257, 1596 October 2017, . 1598 [RFC8290] Hoeiland-Joergensen, T., McKenney, P., Taht, D., Gettys, 1599 J., and E. Dumazet, "The Flow Queue CoDel Packet Scheduler 1600 and Active Queue Management Algorithm", RFC 8290, 1601 DOI 10.17487/RFC8290, January 2018, 1602 . 1604 [RFC8298] Johansson, I. and Z. Sarker, "Self-Clocked Rate Adaptation 1605 for Multimedia", RFC 8298, DOI 10.17487/RFC8298, December 1606 2017, . 1608 [RFC8312] Rhee, I., Xu, L., Ha, S., Zimmermann, A., Eggert, L., and 1609 R. Scheffenegger, "CUBIC for Fast Long-Distance Networks", 1610 RFC 8312, DOI 10.17487/RFC8312, February 2018, 1611 . 1613 [RFC8404] Moriarty, K., Ed. and A. Morton, Ed., "Effects of 1614 Pervasive Encryption on Operators", RFC 8404, 1615 DOI 10.17487/RFC8404, July 2018, 1616 . 1618 [SCReAM] Johansson, I., "SCReAM", github repository; , 1619 . 1622 [SigQ-Dyn] Briscoe, B., "Rapid Signalling of Queue Dynamics", 1623 Technical Report TR-BB-2017-001 arXiv:1904.07044 [cs.NI], 1624 September 2017, . 1626 Appendix A. Example DualQ Coupled PI2 Algorithm 1628 As a first concrete example, the pseudocode below gives the DualPI2 1629 algorithm. DualPI2 follows the structure of the DualQ Coupled AQM 1630 framework in Figure 1. A simple ramp function (configured in units 1631 of queuing time) with unsmoothed ECN marking is used for the Native 1632 L4S AQM. The ramp can also be configured as a step function. The 1633 PI2 algorithm [PI2] is used for the Classic AQM. PI2 is an improved 1634 variant of the PIE AQM [RFC8033]. 1636 The pseudocode will be introduced in two passes. The first pass 1637 explains the core concepts, deferring handling of edge-cases like 1638 overload to the second pass. To aid comparison, line numbers are 1639 kept in step between the two passes by using letter suffixes where 1640 the longer code needs extra lines. 1642 All variables are assumed to be floating point in their basic units 1643 (size in bytes, time in seconds, rates in bytes/second, alpha and 1644 beta in Hz, and probabilities from 0 to 1. Constants expressed in k 1645 (kilo), M (mega), G (giga), u (micro), m (milli) , %, ... are assumed 1646 to be converted to their appropriate multiple or fraction to 1647 represent the basic units. A real implementation that wants to use 1648 integer values needs to handle appropriate scaling factors and allow 1649 accordingly appropriate resolution of its integer types (including 1650 temporary internal values during calculations). 1652 A full open source implementation for Linux is available at: 1653 https://github.com/L4STeam/sch_dualpi2_upstream and explained in 1654 [DualPI2Linux]. The specification of the DualQ Coupled AQM for 1655 DOCSIS cable modems and CMTSs is available in [DOCSIS3.1] and 1656 explained in [LLD]. 1658 A.1. Pass #1: Core Concepts 1660 The pseudocode manipulates three main structures of variables: the 1661 packet (pkt), the L4S queue (lq) and the Classic queue (cq). The 1662 pseudocode consists of the following six functions: 1664 * The initialization function dualpi2_params_init(...) (Figure 2) 1665 that sets parameter defaults (the API for setting non-default 1666 values is omitted for brevity) 1668 * The enqueue function dualpi2_enqueue(lq, cq, pkt) (Figure 3) 1670 * The dequeue function dualpi2_dequeue(lq, cq, pkt) (Figure 4) 1672 * The recurrence function recur(q, likelihood) for de-randomized ECN 1673 marking (shown at the end of Figure 4). 1675 * The L4S AQM function laqm(qdelay) (Figure 5) used to calculate the 1676 ECN-marking probability for the L4S queue 1678 * The base AQM function that implements the PI algorithm 1679 dualpi2_update(lq, cq) (Figure 6) used to regularly update the 1680 base probability (p'), which is squared for the Classic AQM as 1681 well as being coupled across to the L4S queue. 1683 It also uses the following functions that are not shown in full here: 1685 * scheduler(), which selects between the head packets of the two 1686 queues; the choice of scheduler technology is discussed later; 1688 * cq.byt() or lq.byt() returns the current length (aka. backlog) of 1689 the relevant queue in bytes; 1691 * cq.len() or lq.len() returns the current length of the relevant 1692 queue in packets; 1694 * cq.time() or lq.time() returns the current queuing delay 1695 (aka. sojourn time or service time) of the relevant queue in units 1696 of time (see Note a); 1698 * mark(pkt) and drop(pkt) for ECN-marking and dropping a packet; 1700 In experiments so far (building on experiments with PIE) on broadband 1701 access links ranging from 4 Mb/s to 200 Mb/s with base RTTs from 5 ms 1702 to 100 ms, DualPI2 achieves good results with the default parameters 1703 in Figure 2. The parameters are categorised by whether they relate 1704 to the Base PI2 AQM, the L4S AQM or the framework coupling them 1705 together. Constants and variables derived from these parameters are 1706 also included at the end of each category. Each parameter is 1707 explained as it is encountered in the walk-through of the pseudocode 1708 below, and the rationale for the chosen defaults are given so that 1709 sensible values can be used in scenarios other than the regular 1710 public Internet. 1712 1: dualpi2_params_init(...) { % Set input parameter defaults 1713 2: % DualQ Coupled framework parameters 1714 5: limit = MAX_LINK_RATE * 250 ms % Dual buffer size 1715 3: k = 2 % Coupling factor 1716 4: % NOT SHOWN % scheduler-dependent weight or equival't parameter 1717 6: 1718 7: % PI2 Classic AQM parameters 1719 8: target = 15 ms % Queue delay target 1720 9: RTT_max = 100 ms % Worst case RTT expected 1721 10: % PI2 constants derived from above PI2 parameters 1722 11: p_Cmax = min(1/k^2, 1) % Max Classic drop/mark prob 1723 12: Tupdate = min(target, RTT_max/3) % PI sampling interval 1724 13: alpha = 0.1 * Tupdate / RTT_max^2 % PI integral gain in Hz 1725 14: beta = 0.3 / RTT_max % PI proportional gain in Hz 1726 15: 1727 16: % L4S ramp AQM parameters 1728 17: minTh = 800 us % L4S min marking threshold in time units 1729 18: range = 400 us % Range of L4S ramp in time units 1730 19: Th_len = 1 pkt % Min L4S marking threshold in packets 1731 20: % L4S constants 1732 21: p_Lmax = 1 % Max L4S marking prob 1733 22: } 1735 Figure 2: Example Header Pseudocode for DualQ Coupled PI2 AQM 1737 The overall goal of the code is to apply the marking and dropping 1738 probabilities for L4S and Classic traffic (p_L and p_C). These are 1739 derived from the underlying base probabilities p'_L and p' driven 1740 respectively by the traffic in the L and C queues. The marking 1741 probability for the L queue (p_L) depends on both the base 1742 probability in its own queue (p'_L) and a probability called p_CL, 1743 which is coupled across from p' in the C queue (see Section 2.4 for 1744 the derivation of the specific equations and dependencies). 1746 The probabilities p_CL and p_C are derived in lines 4 and 5 of the 1747 dualpi2_update() function (Figure 6) then used in the 1748 dualpi2_dequeue() function where p_L is also derived from p_CL at 1749 line 6 (Figure 4). The code walk-through below builds up to 1750 explaining that part of the code eventually, but it starts from 1751 packet arrival. 1753 1: dualpi2_enqueue(lq, cq, pkt) { % Test limit and classify lq or cq 1754 2: if ( lq.byt() + cq.byt() + MTU > limit) 1755 3: drop(pkt) % drop packet if buffer is full 1756 4: timestamp(pkt) % attach arrival time to packet 1757 5: % Packet classifier 1758 6: if ( ecn(pkt) modulo 2 == 1 ) % ECN bits = ECT(1) or CE 1759 7: lq.enqueue(pkt) 1760 8: else % ECN bits = not-ECT or ECT(0) 1761 9: cq.enqueue(pkt) 1762 10: } 1764 Figure 3: Example Enqueue Pseudocode for DualQ Coupled PI2 AQM 1766 1: dualpi2_dequeue(lq, cq, pkt) { % Couples L4S & Classic queues 1767 2: while ( lq.byt() + cq.byt() > 0 ) { 1768 3: if ( scheduler() == lq ) { 1769 4: lq.dequeue(pkt) % Scheduler chooses lq 1770 5: p'_L = laqm(lq.time()) % Native LAQM 1771 6: p_L = max(p'_L, p_CL) % Combining function 1772 7: if ( recur(lq, p_L) ) % Linear marking 1773 8: mark(pkt) 1774 9: } else { 1775 10: cq.dequeue(pkt) % Scheduler chooses cq 1776 11: if ( recur(cq, p_C) ) { % probability p_C = p'^2 1777 12: if ( ecn(pkt) == 0 ) { % if ECN field = not-ECT 1778 13: drop(pkt) % squared drop 1779 14: continue % continue to the top of the while loop 1780 15: } 1781 16: mark(pkt) % squared mark 1782 17: } 1783 18: } 1784 19: return(pkt) % return the packet and stop 1785 20: } 1786 21: return(NULL) % no packet to dequeue 1787 22: } 1789 23: recur(q, likelihood) { % Returns TRUE with a certain likelihood 1790 24: q.count += likelihood 1791 25: if (q.count > 1) { 1792 26: q.count -= 1 1793 27: return TRUE 1794 28: } 1795 29: return FALSE 1796 30: } 1798 Figure 4: Example Dequeue Pseudocode for DualQ Coupled PI2 AQM 1800 When packets arrive, first a common queue limit is checked as shown 1801 in line 2 of the enqueuing pseudocode in Figure 3. This assumes a 1802 shared buffer for the two queues (Note b discusses the merits of 1803 separate buffers). In order to avoid any bias against larger 1804 packets, 1 MTU of space is always allowed and the limit is 1805 deliberately tested before enqueue. 1807 If limit is not exceeded, the packet is timestamped in line 4. This 1808 assumes that queue delay is measured using the sojourn time technique 1809 (see Note a for alternatives). 1811 At lines 5-9, the packet is classified and enqueued to the Classic or 1812 L4S queue dependent on the least significant bit of the ECN field in 1813 the IP header (line 6). Packets with a codepoint having an LSB of 0 1814 (Not-ECT and ECT(0)) will be enqueued in the Classic queue. 1815 Otherwise, ECT(1) and CE packets will be enqueued in the L4S queue. 1816 Optional additional packet classification flexibility is omitted for 1817 brevity (see the L4S ECN protocol [I-D.ietf-tsvwg-ecn-l4s-id]). 1819 The dequeue pseudocode (Figure 4) is repeatedly called whenever the 1820 lower layer is ready to forward a packet. It schedules one packet 1821 for dequeuing (or zero if the queue is empty) then returns control to 1822 the caller, so that it does not block while that packet is being 1823 forwarded. While making this dequeue decision, it also makes the 1824 necessary AQM decisions on dropping or marking. The alternative of 1825 applying the AQMs at enqueue would shift some processing from the 1826 critical time when each packet is dequeued. However, it would also 1827 add a whole queue of delay to the control signals, making the control 1828 loop sloppier (for a typical RTT it would double the Classic queue's 1829 feedback delay). 1831 All the dequeue code is contained within a large while loop so that 1832 if it decides to drop a packet, it will continue until it selects a 1833 packet to schedule. Line 3 of the dequeue pseudocode is where the 1834 scheduler chooses between the L4S queue (lq) and the Classic queue 1835 (cq). Detailed implementation of the scheduler is not shown (see 1836 discussion later). 1838 * If an L4S packet is scheduled, in lines 7 and 8 the packet is ECN- 1839 marked with likelihood p_L. The recur() function at the end of 1840 Figure 4 is used, which is preferred over random marking because 1841 it avoids delay due to randomization when interpreting congestion 1842 signals, but it still desynchronizes the saw-teeth of the flows. 1843 Line 6 calculates p_L as the maximum of the coupled L4S 1844 probability p_CL and the probability from the native L4S AQM p'_L. 1845 This implements the max() function shown in Figure 1 to couple the 1846 outputs of the two AQMs together. Of the two probabilities input 1847 to p_L in line 6: 1849 - p'_L is calculated per packet in line 5 by the laqm() function 1850 (see Figure 5), 1852 - Whereas p_CL is maintained by the dualpi2_update() function 1853 which runs every Tupdate (Tupdate is set in line 12 of 1854 Figure 2). 1856 * If a Classic packet is scheduled, lines 10 to 17 drop or mark the 1857 packet with probability p_C. 1859 The Native L4S AQM algorithm (Figure 5) is a ramp function, similar 1860 to the RED algorithm, but simplified as follows: 1862 * The extent of the ramp is defined in units of queuing delay, not 1863 bytes, so that configuration remains invariant as the queue 1864 departure rate varies. 1866 * It uses instantaneous queueing delay, which avoids the complexity 1867 of smoothing, but also avoids embedding a worst-case RTT of 1868 smoothing delay in the network (see Section 2.1). 1870 * The ramp rises linearly directly from 0 to 1, not to an 1871 intermediate value of p'_L as RED would, because there is no need 1872 to keep ECN marking probability low. 1874 * Marking does not have to be randomized. Determinism is used 1875 instead of randomness; to reduce the delay necessary to smooth out 1876 the noise of randomness from the signal. 1878 The ramp function requires two configuration parameters, the minimum 1879 threshold (minTh) and the width of the ramp (range), both in units of 1880 queuing time, as shown in lines 17 & 18 of the initialization 1881 function in Figure 2. The ramp function can be configured as a step 1882 (see Note c). 1884 Although the DCTCP paper [Alizadeh-stability] recommends an ECN 1885 marking threshold of 0.17*RTT_typ, it also shows that the threshold 1886 can be much shallower with hardly any worse under-utilization of the 1887 link (because the amplitude of DCTCP's sawteeth is so small). Based 1888 on extensive experiments, for the public Internet the default minimum 1889 ECN marking threshold (target) in Figure 2 is considered a good 1890 compromise, even though it is significantly smaller fraction of 1891 RTT_typ. 1893 1: laqm(qdelay) { % Returns native L4S AQM probability 1894 2: if (qdelay >= maxTh) 1895 3: return 1 1896 4: else if (qdelay > minTh) 1897 5: return (qdelay - minTh)/range % Divide could use a bit-shift 1898 6: else 1899 7: return 0 1900 8: } 1902 Figure 5: Example Pseudocode for the Native L4S AQM 1904 1: dualpi2_update(lq, cq) { % Update p' every Tupdate 1905 2: curq = cq.time() % use queuing time of first-in Classic packet 1906 3: p' = p' + alpha * (curq - target) + beta * (curq - prevq) 1907 4: p_CL = k * p' % Coupled L4S prob = base prob * coupling factor 1908 5: p_C = p'^2 % Classic prob = (base prob)^2 1909 6: prevq = curq 1910 7: } 1912 Figure 6: Example PI-Update Pseudocode for DualQ Coupled PI2 AQM 1914 (Clamping p' within the range [0,1] omitted for clarity - see text) 1916 The coupled marking probability, p_CL depends on the base probability 1917 (p'), which is kept up to date by the core PI algorithm in Figure 6 1918 executed every Tupdate. 1920 Note that p' solely depends on the queuing time in the Classic queue. 1921 In line 2, the current queuing delay (curq) is evaluated from how 1922 long the head packet was in the Classic queue (cq). The function 1923 cq.time() (not shown) subtracts the time stamped at enqueue from the 1924 current time (see Note a) and implicitly takes the current queuing 1925 delay as 0 if the queue is empty. 1927 The algorithm centres on line 3, which is a classical Proportional- 1928 Integral (PI) controller that alters p' dependent on: a) the error 1929 between the current queuing delay (curq) and the target queuing 1930 delay, 'target'; and b) the change in queuing delay since the last 1931 sample. The name 'PI' represents the fact that the second factor 1932 (how fast the queue is growing) is _P_roportional to load while the 1933 first is the _I_ntegral of the load (so it removes any standing queue 1934 in excess of the target). 1936 The target parameter can be set based on local knowledge, but the aim 1937 is for the default to be a good compromise for anywhere in the 1938 intended deployment environment -- the public Internet. According to 1939 [PI2param], the target queuing delay on line 9 of Figure 2 is related 1940 to the typical base RTT worldwide, RTT_typ, by two factors: target = 1941 RTT_typ * g * f. Below we summarize the rationale behind these 1942 factors and introduce a further adjustment. The two factors ensure 1943 that, in a large proportion of cases (say 90%), the sawtooth 1944 variations in RTT of a single flow will fit within the buffer without 1945 underutilizing the link. Frankly, these factors are educated 1946 guesses, but with the emphasis closer to 'educated' than to 'guess' 1947 (see [PI2param] for full background): 1949 * RTT_typ is taken as 25 ms. This is based on an average CDN 1950 latency measured in each country weighted by the number of 1951 Internet users in that country to produce an overall weighted 1952 average for the Internet [PI2param]. Countries were ranked by 1953 number of Internet users, and once 90% of Internet users were 1954 covered, smaller countries were excluded to avoid 1955 unrepresentatively small sample sizes. Also, importantly, the 1956 data for the average CDN latency in China (with the largest number 1957 of Internet users) has been removed, because the CDN latency was a 1958 significant outlier and, on reflection, the experimental technique 1959 seemed inappropriate to the CDN market in China. 1961 * g is taken as 0.38. The factor g is a geometry factor that 1962 characterizes the shape of the sawteeth of prevalent Classic 1963 congestion controllers. The geometry factor is the fraction of 1964 the amplitude of the sawtooth variability in queue delay that lies 1965 below the AQM's target. For instance, at low bit rate, the 1966 geometry factor of standard Reno is 0.5, but at higher rates it 1967 tends to just under 1. According to the census of congestion 1968 controllers conducted by Mishra _et al_ in Jul-Oct 1969 2019 [CCcensus19], most Classic TCP traffic uses Cubic. And, 1970 according to the analysis in [PI2param], if running over a PI2 1971 AQM, a large proportion of this Cubic traffic would be in its 1972 Reno-Friendly mode, which has a geometry factor of ~0.39 (all 1973 known implementations). The rest of the Cubic traffic would be in 1974 true Cubic mode, which has a geometry factor of ~0.36. Without 1975 modelling the sawtooth profiles from all the other less prevalent 1976 congestion controllers, we estimate a 7:3 weighted average of 1977 these two, resulting in an average geometry factor of 0.38. 1979 * f is taken as 2. The factor f is a safety factor that increases 1980 the target queue to allow for the distribution of RTT_typ around 1981 its mean. Otherwise the target queue would only avoid 1982 underutilization for those users below the mean. It also provides 1983 a safety margin for the proportion of paths in use that span 1984 beyond the distance between a user and their local CDN. Currently 1985 no data is available on the variance of queue delay around the 1986 mean in each region, so there is plenty of room for this guess to 1987 become more educated. 1989 * [PI2param] recommends target = RTT_typ * g * f = 25ms * 0.38 * 2 = 1990 19 ms. However a further adjustment is warranted, because target 1991 is moving year on year. The paper is based on data collected in 1992 2019, and it mentions evidence from speedtest.net that suggests 1993 RTT_typ reduced by 17% (fixed) or 12% (mobile) between 2020 and 1994 2021. Therefore we recommend a default of target = 15 ms at the 1995 time of writing (2021). 1997 Operators can always use the data and discussion in [PI2param] to 1998 configure a more appropriate target for their environment. For 1999 instance, an operator might wish to question the assumptions called 2000 out in that paper, such as the goal of no underutilization for a 2001 large majority of single flow transfers (given many large transfers 2002 use multiple flows to avoid the scaling limitations of Classic 2003 flows). 2005 The two 'gain factors' in line 3 of Figure 6, alpha and beta, 2006 respectively weight how strongly each of the two elements (Integral 2007 and Proportional) alters p'. They are in units of 'per second of 2008 delay' or Hz, because they transform differences in queueing delay 2009 into changes in probability (assuming probability has a value from 0 2010 to 1). 2012 Alpha and beta determine how much p' ought to change after each 2013 update interval (Tupdate). For smaller Tupdate, p' should change by 2014 the same amount per second, but in finer more frequent steps. So 2015 alpha depends on Tupdate (see line 13 of the initialization function 2016 in Figure 2). It is best to update p' as frequently as possible, but 2017 Tupdate will probably be constrained by hardware performance. As 2018 shown in line 13, the update interval should be frequent enough to 2019 update at least once in the time taken for the target queue to drain 2020 ('target') as long as it updates at least three times per maximum 2021 RTT. Tupdate defaults to 16 ms in the reference Linux implementation 2022 because it has to be rounded to a multiple of 4 ms. For link rates 2023 from 4 to 200 Mb/s and a maximum RTT of 100ms, it has been verified 2024 through extensive testing that Tupdate=16ms (as also recommended in 2025 the PIE spec [RFC8033]) is sufficient. 2027 The choice of alpha and beta also determines the AQM's stable 2028 operating range. The AQM ought to change p' as fast as possible in 2029 response to changes in load without over-compensating and therefore 2030 causing oscillations in the queue. Therefore, the values of alpha 2031 and beta also depend on the RTT of the expected worst-case flow 2032 (RTT_max). 2034 The maximum RTT of a PI controller (RTT_max in line 10 of Figure 2) 2035 is not an absolute maximum, but more instability (more queue 2036 variability) sets in for long-running flows with an RTT above this 2037 value. The propagation delay half way round the planet and back in 2038 glass fibre is 200 ms. However, hardly any traffic traverses such 2039 extreme paths and, since the significant consolidation of Internet 2040 traffic between 2007 and 2009 [Labovitz10], a high and growing 2041 proportion of all Internet traffic (roughly two-thirds at the time of 2042 writing) has been served from content distribution networks (CDNs) or 2043 'cloud' services distributed close to end-users. The Internet might 2044 change again, but for now, designing for a maximum RTT of 100ms is a 2045 good compromise between faster queue control at low RTT and some 2046 instability on the occasions when a longer path is necessary. 2048 Recommended derivations of the gain constants alpha and beta can be 2049 approximated for Reno over a PI2 AQM as: alpha = 0.1 * Tupdate / 2050 RTT_max^2; beta = 0.3 / RTT_max, as shown in lines 14 & 15 of 2051 Figure 2. These are derived from the stability analysis in [PI2]. 2052 For the default values of Tupdate=16 ms and RTT_max = 100 ms, they 2053 result in alpha = 0.16; beta = 3.2 (discrepancies are due to 2054 rounding). These defaults have been verified with a wide range of 2055 link rates, target delays and a range of traffic models with mixed 2056 and similar RTTs, short and long flows, etc. 2058 In corner cases, p' can overflow the range [0,1] so the resulting 2059 value of p' has to be bounded (omitted from the pseudocode). Then, 2060 as already explained, the coupled and Classic probabilities are 2061 derived from the new p' in lines 4 and 5 of Figure 6 as p_CL = k*p' 2062 and p_C = p'^2. 2064 Because the coupled L4S marking probability (p_CL) is factored up by 2065 k, the dynamic gain parameters alpha and beta are also inherently 2066 factored up by k for the L4S queue. So, the effective gain factor 2067 for the L4S queue is k*alpha (with defaults alpha = 0.16 Hz and k=2, 2068 effective L4S alpha = 0.32 Hz). 2070 Unlike in PIE [RFC8033], alpha and beta do not need to be tuned every 2071 Tupdate dependent on p'. Instead, in PI2, alpha and beta are 2072 independent of p' because the squaring applied to Classic traffic 2073 tunes them inherently. This is explained in [PI2], which also 2074 explains why this more principled approach removes the need for most 2075 of the heuristics that had to be added to PIE. 2077 Nonetheless, an implementer might wish to add selected details to 2078 either AQM. For instance the Linux reference DualPI2 implementation 2079 includes the following (not shown in the pseudocode above): 2081 * Classic and coupled marking or dropping (i.e. based on p_C and 2082 p_CL from the PI controller) is not applied to a packet if the 2083 aggregate queue length in bytes is < 2 MTU (prior to enqueuing the 2084 packet or dequeuing it, depending on whether the AQM is configured 2085 to be applied at enqueue or dequeue); 2087 * In the WRR scheduler, the 'credit' indicating which queue should 2088 transmit is only changed if there are packets in both queues 2089 (i.e. if there is actual resource contention). This means that a 2090 properly paced L flow might never be delayed by the WRR. The WRR 2091 credit is reset in favour of the L queue when the link is idle. 2093 An implementer might also wish to add other heuristics, e.g. burst 2094 protection [RFC8033] or enhanced burst protection [RFC8034]. 2096 Notes: 2098 a. The drain rate of the queue can vary if it is scheduled relative 2099 to other queues, or to cater for fluctuations in a wireless 2100 medium. To auto-adjust to changes in drain rate, the queue needs 2101 to be measured in time, not bytes or packets [AQMmetrics], 2102 [CoDel]. Queuing delay could be measured directly by storing a 2103 per-packet time-stamp as each packet is enqueued, and subtracting 2104 this from the system time when the packet is dequeued. If time- 2105 stamping is not easy to introduce with certain hardware, queuing 2106 delay could be predicted indirectly by dividing the size of the 2107 queue by the predicted departure rate, which might be known 2108 precisely for some link technologies (see for example in DOCSIS 2109 PIE [RFC8034]). 2111 b. Line 2 of the dualpi2_enqueue() function (Figure 3) assumes an 2112 implementation where lq and cq share common buffer memory. An 2113 alternative implementation could use separate buffers for each 2114 queue, in which case the arriving packet would have to be 2115 classified first to determine which buffer to check for available 2116 space. The choice is a trade off; a shared buffer can use less 2117 memory whereas separate buffers isolate the L4S queue from tail- 2118 drop due to large bursts of Classic traffic (e.g. a Classic Reno 2119 TCP during slow-start over a long RTT). 2121 c. There has been some concern that using the step function of DCTCP 2122 for the Native L4S AQM requires end-systems to smooth the signal 2123 for an unnecessarily large number of round trips to ensure 2124 sufficient fidelity. A ramp is no worse than a step in initial 2125 experiments with existing DCTCP. Therefore, it is recommended 2126 that a ramp is configured in place of a step, which will allow 2127 congestion control algorithms to investigate faster smoothing 2128 algorithms. 2130 A ramp is more general that a step, because an operator can 2131 effectively turn the ramp into a step function, as used by DCTCP, 2132 by setting the range to zero. There will not be a divide by zero 2133 problem at line 5 of Figure 5 because, if minTh is equal to 2134 maxTh, the condition for this ramp calculation cannot arise. 2136 A.2. Pass #2: Edge-Case Details 2138 This section takes a second pass through the pseudocode adding 2139 details of two edge-cases: low link rate and overload. Figure 7 2140 repeats the dequeue function of Figure 4, but with details of both 2141 edge-cases added. Similarly Figure 8 repeats the core PI algorithm 2142 of Figure 6, but with overload details added. The initialization, 2143 enqueue, L4S AQM and recur functions are unchanged. 2145 The link rate can be so low that it takes a single packet queue 2146 longer to serialize than the threshold delay at which ECN marking 2147 starts to be applied in the L queue. Therefore, a minimum marking 2148 threshold parameter in units of packets rather than time is necessary 2149 (Th_len, default 1 packet in line 19 of Figure 2) to ensure that the 2150 ramp does not trigger excessive marking on slow links. Where an 2151 implementation knows the link rate, it can set up this minimum at the 2152 time it is configured. For instance, it would divide 1 MTU by the 2153 link rate to convert it into a serialization time, then if the lower 2154 threshold of the Native L AQM ramp was lower than this serialization 2155 time, it could increase the thresholds to shift the bottom of the 2156 ramp to 2 MTU. This is the approach used in DOCSIS [DOCSIS3.1], 2157 because the configured link rate is dedicated to the DualQ. 2159 The pseudocode given here applies where the link rate is unknown, 2160 which is more common for software implementations that might be 2161 deployed in scenarios where the link is shared with other queues. In 2162 lines 5a to 5d in Figure 7 the native L4S marking probability, p'_L, 2163 is zeroed if the queue is only 1 packet (in the default 2164 configuration). 2166 Linux implementation note: 2168 * In Linux, the check that the queue exceeds Th_len before marking 2169 with the native L4S AQM is actually at enqueue, not dequeue, 2170 otherwise it would exempt the last packet of a burst from being 2171 marked. The result of the check is conveyed from enqueue to the 2172 dequeue function via a boolean in the packet metadata. 2174 Persistent overload is deemed to have occurred when Classic drop/ 2175 marking probability reaches p_Cmax. Above this point, the Classic 2176 drop probability is applied to both L and C queues, irrespective of 2177 whether any packet is ECN-capable. ECT packets that are not dropped 2178 can still be ECN-marked. 2180 In line 10 of the initialization function (Figure 2), the maximum 2181 Classic drop probability p_Cmax = min(1/k^2, 1) or 1/4 for the 2182 default coupling factor k=2. In practice, 25% has been found to be a 2183 good threshold to preserve fairness between ECN capable and non ECN 2184 capable traffic. This protects the queues against both temporary 2185 overload from responsive flows and more persistent overload from any 2186 unresponsive traffic that falsely claims to be responsive to ECN. 2188 When the Classic ECN marking probability reaches the p_Cmax threshold 2189 (1/k^2), the marking probability coupled to the L4S queue, p_CL will 2190 always be 100% for any k (by equation (1) in Section 2). So, for 2191 readability, the constant p_Lmax is defined as 1 in line 22 of the 2192 initialization function (Figure 2). This is intended to ensure that 2193 the L4S queue starts to introduce dropping once ECN-marking saturates 2194 at 100% and can rise no further. The 'Prague L4S' 2195 requirements [I-D.ietf-tsvwg-ecn-l4s-id] state that, when an L4S 2196 congestion control detects a drop, it falls back to a response that 2197 coexists with 'Classic' Reno congestion control. So it is correct 2198 that, when the L4S queue drops packets, it drops them proportional to 2199 p'^2, as if they are Classic packets. 2201 The two queues each test for overload in lines 4b and 12b of the 2202 dequeue function (Figure 7). Lines 8c to 8g drop L4S packets with 2203 probability p'^2. Lines 8h to 8i mark the remaining packets with 2204 probability p_CL. Given p_Lmax = 1, all remaining packets will be 2205 marked because, to have reached the else block at line 8b, p_CL >= 1. 2207 Line 2a in the core PI algorithm (Figure 8) deals with overload of 2208 the L4S queue when there is little or no Classic traffic. This is 2209 necessary, because the core PI algorithm maintains the appropriate 2210 drop probability to regulate overload, but it depends on the length 2211 of the Classic queue. If there is little or no Classic queue the 2212 naive PI update function in Figure 6 would drop nothing, even if the 2213 L4S queue were overloaded - so tail drop would have to take over 2214 (lines 2 and 3 of Figure 3). 2216 Instead, line 2a of the full PI update function in Figure 8 ensures 2217 that the base PI AQM in line 3 is driven by whichever of the two 2218 queue delays is greater, but line 3 still always uses the same 2219 Classic target (default 15 ms). If L queue delay is greater just 2220 because there is little or no Classic traffic, normally it will still 2221 be well below the base AQM target. This is because L4S traffic is 2222 also governed by the shallow threshold of its own native AQM (lines 5 2223 and 6 of the dequeue algorithm in Figure 7). So the base AQM will be 2224 driven to zero and not contribute. However, if the L queue is 2225 overloaded by traffic that is unresponsive to its marking, the max() 2226 in line 2 enables the L queue to smoothly take over driving the base 2227 AQM into overload mode even if there is little or no Classic traffic. 2228 Then the base AQM will keep the L queue to the Classic target 2229 (default 15 ms) by shedding L packets. 2231 1: dualpi2_dequeue(lq, cq, pkt) { % Couples L4S & Classic queues 2232 2: while ( lq.byt() + cq.byt() > 0 ) { 2233 3: if ( scheduler() == lq ) { 2234 4a: lq.dequeue(pkt) % L4S scheduled 2235 4b: if ( p_CL < p_Lmax ) { % Check for overload saturation 2236 5a: if (lq.len()>Th_len) % >1 packet queued 2237 5b: p'_L = laqm(lq.time()) % Native LAQM 2238 5c: else 2239 5d: p'_L = 0 % Suppress marking 1 pkt queue 2240 6: p_L = max(p'_L, p_CL) % Combining function 2241 7: if ( recur(lq, p_L) %Linear marking 2242 8a: mark(pkt) 2243 8b: } else { % overload saturation 2244 8c: if ( recur(lq, p_C) ) { % probability p_C = p'^2 2245 8e: drop(pkt) % revert to Classic drop due to overload 2246 8f: continue % continue to the top of the while loop 2247 8g: } 2248 8h: if ( recur(lq, p_CL) ) % probability p_CL = k * p' 2249 8i: mark(pkt) % linear marking of remaining packets 2250 8j: } 2251 9: } else { 2252 10: cq.dequeue(pkt) % Classic scheduled 2253 11: if ( recur(cq, p_C) ) { % probability p_C = p'^2 2254 12a: if ( (ecn(pkt) == 0) % ECN field = not-ECT 2255 12b: OR (p_C >= p_Cmax) ) { % Overload disables ECN 2256 13: drop(pkt) % squared drop, redo loop 2257 14: continue % continue to the top of the while loop 2258 15: } 2259 16: mark(pkt) % squared mark 2260 17: } 2261 18: } 2262 19: return(pkt) % return the packet and stop 2263 20: } 2264 21: return(NULL) % no packet to dequeue 2265 22: } 2267 Figure 7: Example Dequeue Pseudocode for DualQ Coupled PI2 AQM 2268 (Including Code for Edge-Cases) 2270 1: dualpi2_update(lq, cq) { % Update p' every Tupdate 2271 2a: curq = max(cq.time(), lq.time()) % use greatest queuing time 2272 3: p' = p' + alpha * (curq - target) + beta * (curq - prevq) 2273 4: p_CL = p' * k % Coupled L4S prob = base prob * coupling factor 2274 5: p_C = p'^2 % Classic prob = (base prob)^2 2275 6: prevq = curq 2276 7: } 2278 Figure 8: Example PI-Update Pseudocode for DualQ Coupled PI2 AQM 2279 (Including Overload Code) 2281 The choice of scheduler technology is critical to overload protection 2282 (see Section 4.2.2). 2284 * A well-understood weighted scheduler such as weighted round robin 2285 (WRR) is recommended. As long as the scheduler weight for Classic 2286 is small (e.g. 1/16), its exact value is unimportant because it 2287 does not normally determine capacity shares. The weight is only 2288 important to prevent unresponsive L4S traffic starving Classic 2289 traffic in the short term (see Section 4.2.2). This is because 2290 capacity sharing between the queues is normally determined by the 2291 coupled congestion signal, which overrides the scheduler, by 2292 making L4S sources leave roughly equal per-flow capacity available 2293 for Classic flows. 2295 * Alternatively, a time-shifted FIFO (TS-FIFO) could be used. It 2296 works by selecting the head packet that has waited the longest, 2297 biased against the Classic traffic by a time-shift of tshift. To 2298 implement time-shifted FIFO, the scheduler() function in line 3 of 2299 the dequeue code would simply be implemented as the scheduler() 2300 function at the bottom of Figure 10 in Appendix B. For the public 2301 Internet a good value for tshift is 50ms. For private networks 2302 with smaller diameter, about 4*target would be reasonable. TS- 2303 FIFO is a very simple scheduler, but complexity might need to be 2304 added to address some deficiencies (which is why it is not 2305 recommended over WRR): 2307 - TS-FIFO does not fully isolate latency in the L4S queue from 2308 uncontrolled bursts in the Classic queue; 2310 - TS-FIFO is only appropriate if time-stamping of packets is 2311 feasible; 2313 - Even if time-stamping is supported, the sojourn time of the 2314 head packet is always stale. For instance, if a burst arrives 2315 at an empty queue, the sojourn time only fully measures the 2316 burst's delay when its last packet is dequeued, even though the 2317 queue knew about the burst from the start - so it could have 2318 signalled congestion earlier. To remedy this, each head packet 2319 can be marked when it is dequeued based on the expected delay 2320 of the tail packet behind it, as explained below, rather than 2321 based on the head packet's own delay due to the packets in 2322 front of it. [Heist21] identifies a specific scenario where 2323 bursty traffic significantly hits utilization of the L queue. 2324 If this effect proves to be more widely applicable, it is 2325 believed that using the delay behind the head would improve 2326 performance. 2328 The delay behind the head can be implemented by dividing the 2329 backlog at dequeue by the link rate or equivalently multiplying 2330 the backlog by the delay per unit of backlog. The 2331 implementation details will depend on whether the link rate is 2332 known; if it is not, a moving average of the delay per unit 2333 backlog can be maintained. This delay consists of 2334 serialization as well as media acquisition for shared media. 2335 So the details will depend strongly on the specific link 2336 technology, This approach should be less sensitive to timing 2337 errors and cost less in operations and memory than the 2338 otherwise equivalent 'scaled sojourn time' metric, which is the 2339 sojourn time of a packet scaled by the ratio of the queue sizes 2340 when the packet departed and arrived [SigQ-Dyn]. 2342 * A strict priority scheduler would be inappropriate as discussed in 2343 Section 4.2.2. 2345 Appendix B. Example DualQ Coupled Curvy RED Algorithm 2347 As another example of a DualQ Coupled AQM algorithm, the pseudocode 2348 below gives the Curvy RED based algorithm. Although the AQM was 2349 designed to be efficient in integer arithmetic, to aid understanding 2350 it is first given using floating point arithmetic (Figure 10). Then, 2351 one possible optimization for integer arithmetic is given, also in 2352 pseudocode (Figure 11). To aid comparison, the line numbers are kept 2353 in step between the two by using letter suffixes where the longer 2354 code needs extra lines. 2356 B.1. Curvy RED in Pseudocode 2358 The pseudocode manipulates three main structures of variables: the 2359 packet (pkt), the L4S queue (lq) and the Classic queue (cq) and 2360 consists of the following five functions: 2362 * The initialization function cred_params_init(...) (Figure 2) that 2363 sets parameter defaults (the API for setting non-default values is 2364 omitted for brevity); 2366 * The dequeue function cred_dequeue(lq, cq, pkt) (Figure 4); 2368 * The scheduling function scheduler(), which selects between the 2369 head packets of the two queues. 2371 It also uses the following functions that are either shown elsewhere, 2372 or not shown in full here: 2374 * The enqueue function, which is identical to that used for DualPI2, 2375 dualpi2_enqueue(lq, cq, pkt) in Figure 3; 2377 * mark(pkt) and drop(pkt) for ECN-marking and dropping a packet; 2379 * cq.byt() or lq.byt() returns the current length (aka. backlog) of 2380 the relevant queue in bytes; 2382 * cq.time() or lq.time() returns the current queuing delay 2383 (aka. sojourn time or service time) of the relevant queue in units 2384 of time (see Note a in Appendix A.1). 2386 Because Curvy RED was evaluated before DualPI2, certain improvements 2387 introduced for DualPI2 were not evaluated for Curvy RED. In the 2388 pseudocode below, the straightforward improvements have been added on 2389 the assumption they will provide similar benefits, but that has not 2390 been proven experimentally. They are: i) a conditional priority 2391 scheduler instead of strict priority ii) a time-based threshold for 2392 the native L4S AQM; iii) ECN support for the Classic AQM. A recent 2393 evaluation has proved that a minimum ECN-marking threshold (minTh) 2394 greatly improves performance, so this is also included in the 2395 pseudocode. 2397 Overload protection has not been added to the Curvy RED pseudocode 2398 below so as not to detract from the main features. It would be added 2399 in exactly the same way as in Appendix A.2 for the DualPI2 2400 pseudocode. The native L4S AQM uses a step threshold, but a ramp 2401 like that described for DualPI2 could be used instead. The scheduler 2402 uses the simple TS-FIFO algorithm, but it could be replaced with WRR. 2404 The Curvy RED algorithm has not been maintained or evaluated to the 2405 same degree as the DualPI2 algorithm. In initial experiments on 2406 broadband access links ranging from 4 Mb/s to 200 Mb/s with base RTTs 2407 from 5 ms to 100 ms, Curvy RED achieved good results with the default 2408 parameters in Figure 9. 2410 The parameters are categorised by whether they relate to the Classic 2411 AQM, the L4S AQM or the framework coupling them together. Constants 2412 and variables derived from these parameters are also included at the 2413 end of each category. These are the raw input parameters for the 2414 algorithm. A configuration front-end could accept more meaningful 2415 parameters (e.g. RTT_max and RTT_typ) and convert them into these raw 2416 parameters, as has been done for DualPI2 in Appendix A. Where 2417 necessary, parameters are explained further in the walk-through of 2418 the pseudocode below. 2420 1: cred_params_init(...) { % Set input parameter defaults 2421 2: % DualQ Coupled framework parameters 2422 3: limit = MAX_LINK_RATE * 250 ms % Dual buffer size 2423 4: k' = 1 % Coupling factor as a power of 2 2424 5: tshift = 50 ms % Time shift of TS-FIFO scheduler 2425 6: % Constants derived from Classic AQM parameters 2426 7: k = 2^k' % Coupling factor from Equation (1) 2427 6: 2428 7: % Classic AQM parameters 2429 8: g_C = 5 % EWMA smoothing parameter as a power of 1/2 2430 9: S_C = -1 % Classic ramp scaling factor as a power of 2 2431 10: minTh = 500 ms % No Classic drop/mark below this queue delay 2432 11: % Constants derived from Classic AQM parameters 2433 12: gamma = 2^(-g_C) % EWMA smoothing parameter 2434 13: range_C = 2^S_C % Range of Classic ramp 2435 14: 2436 15: % L4S AQM parameters 2437 16: T = 1 ms % Queue delay threshold for native L4S AQM 2438 17: % Constants derived from above parameters 2439 18: S_L = S_C - k' % L4S ramp scaling factor as a power of 2 2440 19: range_L = 2^S_L % Range of L4S ramp 2441 20: } 2443 Figure 9: Example Header Pseudocode for DualQ Coupled Curvy RED AQM 2445 1: cred_dequeue(lq, cq, pkt) { % Couples L4S & Classic queues 2446 2: while ( lq.byt() + cq.byt() > 0 ) { 2447 3: if ( scheduler() == lq ) { 2448 4: lq.dequeue(pkt) % L4S scheduled 2449 5a: p_CL = (Q_C - minTh) / range_L 2450 5b: if ( ( lq.time() > T ) 2451 5c: OR ( p_CL > maxrand(U) ) ) 2452 6: mark(pkt) 2453 7: } else { 2454 8: cq.dequeue(pkt) % Classic scheduled 2455 9a: Q_C = gamma * cq.time() + (1-gamma) * Q_C % Classic Q EWMA 2456 10a: sqrt_p_C = (Q_C - minTh) / range_C 2457 10b: if ( sqrt_p_C > maxrand(2*U) ) { 2458 11: if ( (ecn(pkt) == 0) { % ECN field = not-ECT 2459 12: drop(pkt) % Squared drop, redo loop 2460 13: continue % continue to the top of the while loop 2461 14: } 2462 15: mark(pkt) 2463 16: } 2464 17: } 2465 18: return(pkt) % return the packet and stop here 2466 19: } 2467 20: return(NULL) % no packet to dequeue 2468 21: } 2470 22: maxrand(u) { % return the max of u random numbers 2471 23: maxr=0 2472 24: while (u-- > 0) 2473 25: maxr = max(maxr, rand()) % 0 <= rand() < 1 2474 26: return(maxr) 2475 27: } 2477 28: scheduler() { 2478 29: if ( lq.time() + tshift >= cq.time() ) 2479 30: return lq; 2480 31: else 2481 32: return cq; 2482 33: } 2484 Figure 10: Example Dequeue Pseudocode for DualQ Coupled Curvy RED AQM 2486 The dequeue pseudocode (Figure 10) is repeatedly called whenever the 2487 lower layer is ready to forward a packet. It schedules one packet 2488 for dequeuing (or zero if the queue is empty) then returns control to 2489 the caller, so that it does not block while that packet is being 2490 forwarded. While making this dequeue decision, it also makes the 2491 necessary AQM decisions on dropping or marking. The alternative of 2492 applying the AQMs at enqueue would shift some processing from the 2493 critical time when each packet is dequeued. However, it would also 2494 add a whole queue of delay to the control signals, making the control 2495 loop very sloppy. 2497 The code is written assuming the AQMs are applied on dequeue (Note 2498 1). All the dequeue code is contained within a large while loop so 2499 that if it decides to drop a packet, it will continue until it 2500 selects a packet to schedule. If both queues are empty, the routine 2501 returns NULL at line 20. Line 3 of the dequeue pseudocode is where 2502 the conditional priority scheduler chooses between the L4S queue (lq) 2503 and the Classic queue (cq). The time-shifted FIFO scheduler is shown 2504 at lines 28-33, which would be suitable if simplicity is paramount 2505 (see Note 2). 2507 Within each queue, the decision whether to forward, drop or mark is 2508 taken as follows (to simplify the explanation, it is assumed that 2509 U=1): 2511 L4S: If the test at line 3 determines there is an L4S packet to 2512 dequeue, the tests at lines 5b and 5c determine whether to mark 2513 it. The first is a simple test of whether the L4S queue delay 2514 (lq.time()) is greater than a step threshold T (Note 3). The 2515 second test is similar to the random ECN marking in RED, but with 2516 the following differences: i) marking depends on queuing time, not 2517 bytes, in order to scale for any link rate without being 2518 reconfigured; ii) marking of the L4S queue depends on a logical OR 2519 of two tests; one against its own queuing time and one against the 2520 queuing time of the _other_ (Classic) queue; iii) the tests are 2521 against the instantaneous queuing time of the L4S queue, but a 2522 smoothed average of the other (Classic) queue; iv) the queue is 2523 compared with the maximum of U random numbers (but if U=1, this is 2524 the same as the single random number used in RED). 2526 Specifically, in line 5a the coupled marking probability p_CL is 2527 set to the amount by which the averaged Classic queueing delay Q_C 2528 exceeds the minimum queuing delay threshold (minTh) all divided by 2529 the L4S scaling parameter range_L. range_L represents the queuing 2530 delay (in seconds) added to minTh at which marking probability 2531 would hit 100%. Then in line 5c (if U=1) the result is compared 2532 with a uniformly distributed random number between 0 and 1, which 2533 ensures that, over range_L, marking probability will linearly 2534 increase with queueing time. 2536 Classic: If the scheduler at line 3 chooses to dequeue a Classic 2537 packet and jumps to line 7, the test at line 10b determines 2538 whether to drop or mark it. But before that, line 9a updates Q_C, 2539 which is an exponentially weighted moving average (Note 4) of the 2540 queuing time of the Classic queue, where cq.time() is the current 2541 instantaneous queueing time of the packet at the head of the 2542 Classic queue (zero if empty) and gamma is the EWMA constant 2543 (default 1/32, see line 12 of the initialization function). 2545 Lines 10a and 10b implement the Classic AQM. In line 10a the 2546 averaged queuing time Q_C is divided by the Classic scaling 2547 parameter range_C, in the same way that queuing time was scaled 2548 for L4S marking. This scaled queuing time will be squared to 2549 compute Classic drop probability so, before it is squared, it is 2550 effectively the square root of the drop probability, hence it is 2551 given the variable name sqrt_p_C. The squaring is done by 2552 comparing it with the maximum out of two random numbers (assuming 2553 U=1). Comparing it with the maximum out of two is the same as the 2554 logical `AND' of two tests, which ensures drop probability rises 2555 with the square of queuing time. 2557 The AQM functions in each queue (lines 5c & 10b) are two cases of a 2558 new generalization of RED called Curvy RED, motivated as follows. 2559 When the performance of this AQM was compared with FQ-CoDel and PIE, 2560 their goal of holding queuing delay to a fixed target seemed 2561 misguided [CRED_Insights]. As the number of flows increases, if the 2562 AQM does not allow host congestion controllers to increase queuing 2563 delay, it has to introduce abnormally high levels of loss. Then loss 2564 rather than queuing becomes the dominant cause of delay for short 2565 flows, due to timeouts and tail losses. 2567 Curvy RED constrains delay with a softened target that allows some 2568 increase in delay as load increases. This is achieved by increasing 2569 drop probability on a convex curve relative to queue growth (the 2570 square curve in the Classic queue, if U=1). Like RED, the curve hugs 2571 the zero axis while the queue is shallow. Then, as load increases, 2572 it introduces a growing barrier to higher delay. But, unlike RED, it 2573 requires only two parameters, not three. The disadvantage of Curvy 2574 RED (compared to a PI controller for example) is that it is not 2575 adapted to a wide range of RTTs. Curvy RED can be used as is when 2576 the RTT range to be supported is limited, otherwise an adaptation 2577 mechanism is needed. 2579 From our limited experiments with Curvy RED so far, recommended 2580 values of these parameters are: S_C = -1; g_C = 5; T = 5 * MTU at the 2581 link rate (about 1ms at 60Mb/s) for the range of base RTTs typical on 2582 the public Internet. [CRED_Insights] explains why these parameters 2583 are applicable whatever rate link this AQM implementation is deployed 2584 on and how the parameters would need to be adjusted for a scenario 2585 with a different range of RTTs (e.g. a data centre). The setting of 2586 k depends on policy (see Section 2.5 and Appendix C.2 respectively 2587 for its recommended setting and guidance on alternatives). 2589 There is also a cUrviness parameter, U, which is a small positive 2590 integer. It is likely to take the same hard-coded value for all 2591 implementations, once experiments have determined a good value. Only 2592 U=1 has been used in experiments so far, but results might be even 2593 better with U=2 or higher. 2595 Notes: 2597 1. The alternative of applying the AQMs at enqueue would shift some 2598 processing from the critical time when each packet is dequeued. 2599 However, it would also add a whole queue of delay to the control 2600 signals, making the control loop sloppier (for a typical RTT it 2601 would double the Classic queue's feedback delay). On a platform 2602 where packet timestamping is feasible, e.g. Linux, it is also 2603 easiest to apply the AQMs at dequeue because that is where 2604 queuing time is also measured. 2606 2. WRR better isolates the L4S queue from large delay bursts in the 2607 Classic queue, but it is slightly less simple than TS-FIFO. If 2608 WRR were used, a low default Classic weight (e.g. 1/16) would 2609 need to be configured in place of the time shift in line 5 of the 2610 initialization function (Figure 9). 2612 3. A step function is shown for simplicity. A ramp function (see 2613 Figure 5 and the discussion around it in Appendix A.1) is 2614 recommended, because it is more general than a step and has the 2615 potential to enable L4S congestion controls to converge more 2616 rapidly. 2618 4. An EWMA is only one possible way to filter bursts; other more 2619 adaptive smoothing methods could be valid and it might be 2620 appropriate to decrease the EWMA faster than it increases, 2621 e.g. by using the minimum of the smoothed and instantaneous queue 2622 delays, min(Q_C, qc.time()). 2624 B.2. Efficient Implementation of Curvy RED 2626 Although code optimization depends on the platform, the following 2627 notes explain where the design of Curvy RED was particularly 2628 motivated by efficient implementation. 2630 The Classic AQM at line 10b calls maxrand(2*U), which gives twice as 2631 much curviness as the call to maxrand(U) in the marking function at 2632 line 5c. This is the trick that implements the square rule in 2633 equation (1) (Section 2.1). This is based on the fact that, given a 2634 number X from 1 to 6, the probability that two dice throws will both 2635 be less than X is the square of the probability that one throw will 2636 be less than X. So, when U=1, the L4S marking function is linear and 2637 the Classic dropping function is squared. If U=2, L4S would be a 2638 square function and Classic would be quartic. And so on. 2640 The maxrand(u) function in lines 16-21 simply generates u random 2641 numbers and returns the maximum. Typically, maxrand(u) could be run 2642 in parallel out of band. For instance, if U=1, the Classic queue 2643 would require the maximum of two random numbers. So, instead of 2644 calling maxrand(2*U) in-band, the maximum of every pair of values 2645 from a pseudorandom number generator could be generated out-of-band, 2646 and held in a buffer ready for the Classic queue to consume. 2648 1: cred_dequeue(lq, cq, pkt) { % Couples L4S & Classic queues 2649 2: while ( lq.byt() + cq.byt() > 0 ) { 2650 3: if ( scheduler() == lq ) { 2651 4: lq.dequeue(pkt) % L4S scheduled 2652 5: if ((lq.time() > T) OR (Q_C >> (S_L-2) > maxrand(U))) 2653 6: mark(pkt) 2654 7: } else { 2655 8: cq.dequeue(pkt) % Classic scheduled 2656 9: Q_C += (qc.ns() - Q_C) >> g_C % Classic Q EWMA 2657 10: if ( (Q_C >> (S_C-2) ) > maxrand(2*U) ) { 2658 11: if ( (ecn(pkt) == 0) { % ECN field = not-ECT 2659 12: drop(pkt) % Squared drop, redo loop 2660 13: continue % continue to the top of the while loop 2661 14: } 2662 15: mark(pkt) 2663 16: } 2664 17: } 2665 18: return(pkt) % return the packet and stop here 2666 19: } 2667 20: return(NULL) % no packet to dequeue 2668 21: } 2670 Figure 11: Optimised Example Dequeue Pseudocode for Coupled DualQ 2671 AQM using Integer Arithmetic 2673 The two ranges, range_L and range_C are expressed as powers of 2 so 2674 that division can be implemented as a right bit-shift (>>) in lines 5 2675 and 10 of the integer variant of the pseudocode (Figure 11). 2677 For the integer variant of the pseudocode, an integer version of the 2678 rand() function used at line 25 of the maxrand(function) in Figure 10 2679 would be arranged to return an integer in the range 0 <= maxrand() < 2680 2^32 (not shown). This would scale up all the floating point 2681 probabilities in the range [0,1] by 2^32. 2683 Queuing delays are also scaled up by 2^32, but in two stages: i) In 2684 line 9 queuing time qc.ns() is returned in integer nanoseconds, 2685 making the value about 2^30 times larger than when the units were 2686 seconds, ii) then in lines 5 and 10 an adjustment of -2 to the right 2687 bit-shift multiplies the result by 2^2, to complete the scaling by 2688 2^32. 2690 In line 8 of the initialization function, the EWMA constant gamma is 2691 represented as an integer power of 2, g_C, so that in line 9 of the 2692 integer code the division needed to weight the moving average can be 2693 implemented by a right bit-shift (>> g_C). 2695 Appendix C. Choice of Coupling Factor, k 2697 C.1. RTT-Dependence 2699 Where Classic flows compete for the same capacity, their relative 2700 flow rates depend not only on the congestion probability, but also on 2701 their end-to-end RTT (= base RTT + queue delay). The rates of 2702 Reno [RFC5681] flows competing over an AQM are roughly inversely 2703 proportional to their RTTs. Cubic exhibits similar RTT-dependence 2704 when in Reno-compatibility mode, but it is less RTT-dependent 2705 otherwise. 2707 Until the early experiments with the DualQ Coupled AQM, the 2708 importance of the reasonably large Classic queue in mitigating RTT- 2709 dependence when the base RTT is low had not been appreciated. 2710 Appendix A.1.6 of the L4S ECN protocol [I-D.ietf-tsvwg-ecn-l4s-id] 2711 uses numerical examples to explain why bloated buffers had concealed 2712 the RTT-dependence of Classic congestion controls before that time. 2713 Then it explains why, the more that queuing delays have reduced, the 2714 more that RTT-dependence has surfaced as a potential starvation 2715 problem for long RTT flows, when competing against very short RTT 2716 flows. 2718 Given that congestion control on end-systems is voluntary, there is 2719 no reason why it has to be voluntarily RTT-dependent. The RTT- 2720 dependence of existing Classic traffic cannot be 'undeployed'. 2721 Therefore, [I-D.ietf-tsvwg-ecn-l4s-id] requires L4S congestion 2722 controls to be significantly less RTT-dependent than the standard 2723 Reno congestion control [RFC5681], at least at low RTT. Then RTT- 2724 dependence ought to be no worse than it is with appropriately sized 2725 Classic buffers. Following this approach means there is no need for 2726 network devices to address RTT-dependence, although there would be no 2727 harm if they did, which per-flow queuing inherently does. 2729 C.2. Guidance on Controlling Throughput Equivalence 2731 The coupling factor, k, determines the balance between L4S and 2732 Classic flow rates (see Section 2.5.2.1 and equation (1)). 2734 For the public Internet, a coupling factor of k=2 is recommended, and 2735 justified below. For scenarios other than the public Internet, a 2736 good coupling factor can be derived by plugging the appropriate 2737 numbers into the same working. 2739 To summarize the maths below, from equation (7) it can be seen that 2740 choosing k=1.64 would theoretically make L4S throughput roughly the 2741 same as Classic, _if their actual end-to-end RTTs were the same_. 2742 However, even if the base RTTs are the same, the actual RTTs are 2743 unlikely to be the same, because Classic traffic needs a fairly large 2744 queue to avoid under-utilization and excess drop. Whereas L4S does 2745 not. 2747 Therefore, to determine the appropriate coupling factor policy, the 2748 operator needs to decide at what base RTT it wants L4S and Classic 2749 flows to have roughly equal throughput, once the effect of the 2750 additional Classic queue on Classic throughput has been taken into 2751 account. With this approach, a network operator can determine a good 2752 coupling factor without knowing the precise L4S algorithm for 2753 reducing RTT-dependence - or even in the absence of any algorithm. 2755 The following additional terminology will be used, with appropriate 2756 subscripts: 2758 r: Packet rate [pkt/s] 2760 R: RTT [s/round] 2762 p: ECN marking probability [] 2764 On the Classic side, we consider Reno as the most sensitive and 2765 therefore worst-case Classic congestion control. We will also 2766 consider Cubic in its Reno-friendly mode ('CReno'), as the most 2767 prevalent congestion control, according to the references and 2768 analysis in [PI2param]. In either case, the Classic packet rate in 2769 steady state is given by the well-known square root formula for Reno 2770 congestion control: 2772 r_C = 1.22 / (R_C * p_C^0.5) (5) 2774 On the L4S side, we consider the Prague congestion 2775 control [I-D.briscoe-iccrg-prague-congestion-control] as the 2776 reference for steady-state dependence on congestion. Prague conforms 2777 to the same equation as DCTCP, but we do not use the equation derived 2778 in the DCTCP paper, which is only appropriate for step marking. The 2779 coupled marking, p_CL, is the appropriate one when considering 2780 throughput equivalence with Classic flows. Unlike step marking, 2781 coupled markings are inherently spaced out, so we use the formula for 2782 DCTCP packet rate with probabilistic marking derived in Appendix A of 2783 [PI2]. We use the equation without RTT-independence enabled, which 2784 will be explained later. 2786 r_L = 2 / (R_L * p_CL) (6) 2788 For packet rate equivalence, we equate the two packet rates and 2789 rearrange into the same form as Equation (1), so the two can be 2790 equated and simplified to produce a formula for a theoretical 2791 coupling factor, which we shall call k*: 2793 r_c = r_L 2794 => p_C = (p_CL/1.64 * R_L/R_C)^2 2796 p_C = ( p_CL / k )^2 (1) 2798 k* = 1.64 * (R_C / R_L) (7) 2800 We say that this coupling factor is theoretical, because it is in 2801 terms of two RTTs, which raises two practical questions: i) for 2802 multiple flows with different RTTs, the RTT for each traffic class 2803 would have to be derived from the RTTs of all the flows in that class 2804 (actually the harmonic mean would be needed); ii) a network node 2805 cannot easily know the RTT of any of the flows anyway. 2807 RTT-dependence is caused by window-based congestion control, so it 2808 ought to be reversed there, not in the network. Therefore, we use a 2809 fixed coupling factor in the network, and reduce RTT-dependence in 2810 L4S senders. We cannot expect Classic senders to all be updated to 2811 reduce their RTT-dependence. But solely addressing the problem in 2812 L4S senders at least makes RTT-dependence no worse - not just between 2813 L4S senders, but also between L4S and Classic senders. 2815 Traditionally, throughput equivalence has been defined for flows 2816 under comparable conditions, including with the same base 2817 RTT [RFC2914]. So if we assume the same base RTT, R_b, for 2818 comparable flows, we can put both R_C and R_L in terms of R_b. 2820 We can approximate the L4S RTT to be hardly greater than the base 2821 RTT, i.e. R_L ~= R_b. And we can replace R_C with (R_b + q_C), where 2822 the Classic queue, q_C, depends on the target queue delay that the 2823 operator has configured for the Classic AQM. 2825 Taking PI2 as an example Classic AQM, it seems that we could just 2826 take R_C = R_b + target (recommended 15 ms by default in 2827 Appendix A.1). However, target is roughly the queue depth reached by 2828 the tips of the sawteeth of a congestion control, not the average 2829 [PI2param]. That is R_max = R_b + target. 2831 The position of the average in relation to the max depends on the 2832 amplitude and geometry of the sawteeth. We consider two examples: 2833 Reno [RFC5681], as the most sensitive worst-case, and Cubic [RFC8312] 2834 in its Reno-friendly mode ('CReno') as the most prevalent congestion 2835 control algorithm on the Internet according to the references in 2836 [PI2param]. Both are AIMD, so we will generalize using b as the 2837 multiplicative decrease factor (b_r = 0.5 for Reno, b_c = 0.7 for 2838 CReno). Then: 2840 R_C = (R_max + b*R_max) / 2 2841 = R_max * (1+b)/2 2843 R_reno = 0.75 * (R_b + target); R_creno = 0.85 * (R_b + target). 2844 (8) 2846 Plugging all this into equation (7) we get a fixed coupling factor 2847 for each: 2849 k_reno = 1.64*0.75*(R_b+target)/R_b 2850 = 1.23*(1 + target/R_b); k_creno = 1.39 * (1 + target/R_b) 2852 An operator can then choose the base RTT at which it wants throughput 2853 to be equivalent. For instance, if we recommend that the operator 2854 chooses R_b = 25 ms, as a typical base RTT between Internet users and 2855 CDNs [PI2param], then these coupling factors become: 2857 k_reno = 1.23 * (1 + 15/25) k_creno = 1.39 * (1 + 15/25) 2858 = 1.97 = 2.22 2859 ~= 2 ~= 2 (9) 2861 The approximation is relevant to any of the above example DualQ 2862 Coupled algorithms, which use a coupling factor that is an integer 2863 power of 2 to aid efficient implementation. It also fits best to the 2864 worst case (Reno). 2866 To check the outcome of this coupling factor, we can express the 2867 ratio of L4S to Classic throughput by substituting from their rate 2868 equations (5) and (6), then also substituting for p_C in terms of 2869 p_CL, using equation (1) with k=2 as just determined for the 2870 Internet: 2872 r_L / r_C = 2 (R_C * p_C^0.5) / 1.22 (R_L * p_CL) 2873 = (R_C * p_CL) / (1.22 * R_L * p_CL) 2874 = R_C / (1.22 * R_L) (10) 2876 As an example, we can then consider single competing CReno and Prague 2877 flows, by expressing both their RTTs in (10) in terms of their base 2878 RTTs, R_bC and R_bL. So R_C is replaced by equation (8) for CReno. 2879 And R_L is replaced by the max() function below, which represents the 2880 effective RTT of the current Prague congestion 2881 control [I-D.briscoe-iccrg-prague-congestion-control] in its 2882 (default) RTT-independent mode, because it sets a floor to the 2883 effective RTT that it uses for additive increase: 2885 ~= 0.85 * (R_bC + target) / (1.22 * max(R_bL, R_typ)) 2886 ~= (R_bC + target) / (1.4 * max(R_bL, R_typ)) 2888 It can be seen that, for base RTTs below target (15 ms), both the 2889 numerator and the denominator plateau, which has the desired effect 2890 of limiting RTT-dependence. 2892 At the start of the above derivations, an explanation was promised 2893 for why the L4S throughput equation in equation (6) did not need to 2894 model RTT-independence. This is because we only use one point - at 2895 the the typical base RTT where the operator chooses to calculate the 2896 coupling factor. Then, throughput equivalence will at least hold at 2897 that chosen point. Nonetheless, assuming Prague senders implement 2898 RTT-independence over a range of RTTs below this, the throughput 2899 equivalence will then extend over that range as well. 2901 Congestion control designers can choose different ways to reduce RTT- 2902 dependence. And each operator can make a policy choice to decide on 2903 a different base RTT, and therefore a different k, at which it wants 2904 throughput equivalence. Nonetheless, for the Internet, it makes 2905 sense to choose what is believed to be the typical RTT most users 2906 experience, because a Classic AQM's target queuing delay is also 2907 derived from a typical RTT for the Internet. 2909 As a non-Internet example, for localized traffic from a particular 2910 ISP's data centre, using the measured RTTs, it was calculated that a 2911 value of k = 8 would achieve throughput equivalence, and experiments 2912 verified the formula very closely. 2914 But, for a typical mix of RTTs across the general Internet, a value 2915 of k=2 is recommended as a good workable compromise. 2917 Authors' Addresses 2919 Koen De Schepper 2920 Nokia Bell Labs 2921 Antwerp 2922 Belgium 2923 Email: koen.de_schepper@nokia.com 2924 URI: https://www.bell-labs.com/usr/koen.de_schepper 2926 Bob Briscoe (editor) 2927 Independent 2928 United Kingdom 2929 Email: ietf@bobbriscoe.net 2930 URI: http://bobbriscoe.net/ 2932 Greg White 2933 CableLabs 2934 Louisville, CO, 2935 United States of America 2936 Email: G.White@CableLabs.com