idnits 2.17.00 (12 Aug 2021) /tmp/idnits22968/draft-morton-tsvwg-codel-approx-fair-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There is 1 instance of too long lines in the document, the longest one being 2 characters in excess of 72. ** The abstract seems to contain references ([RFC8289], [I-D.morton-tsvwg-cheap-nasty-queueing]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (9 March 2020) is 797 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-03) exists of draft-morton-tsvwg-sce-01 Summary: 2 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Transport Working Group J. Morton 3 Internet-Draft 4 Intended status: Informational P. Heist 5 Expires: 10 September 2020 9 March 2020 7 Controlled Delay Approximate Fairness AQM 8 draft-morton-tsvwg-codel-approx-fair-01 10 Abstract 12 This note presents CodelAF, or Controlled Delay Approximate Fairness 13 in full, as an alternative to single-queue AQM or Fair Queue 14 implementations in the low-cost or high-speed network hardware 15 spaces. It builds on the seminal work in Codel [RFC8289], and guides 16 multiple competing flows towards similar throughputs by differential 17 congestion signalling, whilst requiring only a single FIFO queue. It 18 may also be combined with CNQ [I-D.morton-tsvwg-cheap-nasty-queueing] 19 to provide a latency optimisation for sparse flows. 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at https://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on 10 September 2020. 38 Copyright Notice 40 Copyright (c) 2020 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 45 license-info) in effect on the date of publication of this document. 46 Please review these documents carefully, as they describe your rights 47 and restrictions with respect to this document. Code Components 48 extracted from this document must include Simplified BSD License text 49 as described in Section 4.e of the Trust Legal Provisions and are 50 provided without warranty as described in the Simplified BSD License. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 55 2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 3 56 3. The Codel Approximate Fairness Algorithm . . . . . . . . . . 4 57 4. Extending CodelAF to Provide a Low Latency PHB . . . . . . . 4 58 5. Security Considerations . . . . . . . . . . . . . . . . . . . 5 59 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 5 60 7. Informative References . . . . . . . . . . . . . . . . . . . 5 61 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 7 63 1. Introduction 65 For some years, the solution of choice for improving network 66 performance as been the combination of Fair Queuing (FQ) with Active 67 Queue Management (AQM) as demonstrated in FQ-Codel [RFC8290]. 68 However, concerns are legitimately raised over the difficulty of 69 implementing FQ in hardware, making it a weak proposition for very 70 low-cost and very high-speed network devices alike. There is some 71 evidence to suggest that implementing multiple AQM instances is not 72 very difficult in hardware, but implementing multiple FIFOs can be 73 prohibitive. 75 CodelAF addresses this design space with a straightforward extension 76 to the Codel AQM, allowing its target to be biased according to 77 relative queue occupancy of a particular flow, and its signals 78 applied only to that flow. An arbitrary number of independent flows 79 can then be signalled to more independently than a single AQM can, 80 allowing convergence towards a fair-throughput state. 82 This approach also successfully addresses the problem of allowing 83 flows responding to dissimilar congestion signals to share the same 84 FIFO queue without excessive bias. In particular, it applies to Some 85 Congestion Experienced [I-D.morton-tsvwg-sce] flows sharing a queue 86 with conventional ECN [RFC3168] and Not-ECT flows. 88 It is likely that a similar AF technique can also be applied to other 89 AQMs that employ a target queue sojourn time, such as PIE and BLUE. 91 Building on the basic CodelAF algorithm, this memo also shows how to 92 provide a low-latency PHB through a twinned CodelAF configuration, 93 requiring configuration of only a second set of AQM parameters and 94 retaining approximate flow-fairness between the low-latency and best- 95 effort traffic classes. 97 2. Background 99 A brief summary of the basic Codel algorithm follows. For full 100 details, see [RFC8289]. 102 Codel is parameterised by a target setpoint, indicating the amount of 103 tolerable standing queue (default 5 ms) and an initial signalling 104 interval which is set to an estimate of the typical path latency 105 (default 100 ms). The principle dynamic state elements are a flag 106 indicating whether Codel is in the "marking" state or not, a timer 107 indicating when the next mark is due, and a counter indicating how 108 many marks have been set since entering the marking state. 110 Since Codel was designed at a time when ECN was not commonly used, 111 the "marking" state is often described as the "dropping" state, 112 including by the original authors. Here the term "marking" state is 113 used to match the increased deployment of ECN today. 115 Codel enters the "marking" state when the sojourn time of a packet 116 within its queue first exceeds its target setpoint. At this time, 117 the counter is initialised to 1 and the timer is set for interval/ 118 sqrt(counter) time in the future. This first packet, therefore, is 119 not marked, as it may be an outlier belonging to an isolated and 120 temporary burst of traffic. Only if the sojourn times of all 121 subsequent packets (until the timer expires) also exceed the target 122 will ECN marking (or dropping of Not-ECT packets) begin. Marking is 123 always performed at the head of the queue, where the sojourn time of 124 individual packets is precisely known. 126 After each mark (or drop), the counter is incremented and the timer 127 advanced, again, by interval/sqrt(counter). This causes a linear 128 increase of marking frequency over time, until the queue is brought 129 under control. This is signified by the sojourn times of packets 130 dropping below the target, at which time marking immediately stops 131 and Codel exits the marking state. 133 When Codel exits the marking state, the counter is not immediately 134 reset, as further control of an aggressive flow may still be needed. 135 The reference implementation pauses for some multiple of the interval 136 and then resets the counter. The COBALT variant instead decrements 137 the counter and resets the timer on the same linear frequency ramp, 138 run in reverse, the benefit of which can be seen in [COBALT]. 140 The reference CodelAF implementation is built around a combination of 141 COBALT with CNQ [I-D.morton-tsvwg-cheap-nasty-queueing], to which 142 only small code changes were required. 144 3. The Codel Approximate Fairness Algorithm 146 In CodelAF, a separate instance of the Codel state variables (marking 147 flag, timer, and counter) are kept for each flow. In addition, an 148 account of the instantaneous queue occupancy of each flow is 149 maintained, as well as the total queue occupancy, and the number of 150 "active flows" which have traffic in the queue. 152 Flows may be distinguished by whichever means is convenient, for 153 example a hash function over the traditional 5-tuple of protocol 154 number, source/destination addresses and port numbers. Some 155 deployments may prefer to use a smaller set of packet header 156 information, or to distinguish based on subscriber ID metadata. The 157 result in any case is an index into a flow table containing the queue 158 occupancy data and AQM state mentioned above. 160 The Codel parameters (interval, target) are common to all flows. 161 However, when evaluating the AQM state for a packet, the target 162 parameter is locally adjusted based on the actual queue occupancy by 163 that packet's flow, compared to the fair-share queue occupancy based 164 on dividing the total occupancy between all active flows. Hence a 165 sparser flow, with lower than average occupancy, will receive more 166 leniency from the AQM. 168 The basic Codel criterion: 170 if(sojourn > target): 171 enter_dropping_state; 173 becomes: 175 if(sojourn * flow occupancy * active flows > target * total occupancy): 176 enter_dropping_state; 178 This is sufficient to guide flows that are responsive to AQM signals 179 towards throughput fairness. 181 4. Extending CodelAF to Provide a Low Latency PHB 183 The Internet is a highly heterogeneous environment, with path lengths 184 as short as single-digit milliseconds on some paths, and approaching 185 a full second on others. An AQM is thus set for a reasonable 186 compromise corresponding to a "typical" path length; in the case of 187 Codel and CodelAF, this is 100ms RTT, which works well on 188 transcontinental and inter-continental paths, and also has acceptable 189 behaviour on shorter paths for many applications. However, better 190 control of latency may be desired for traffic known to be on such a 191 short path, eg. between an end-user and a Content Distribution 192 Network (CDN) or gaming service local to that end-user. This 193 requires that a second queue and AQM is selectable by some 194 classifier, such as a Diffserv codepoint (DSCP) 195 [RFC2475][RFC7657][RFC8100], and tuned for the shorter path length. 197 A perennial concern with Diffserv deployment is ensuring that traffic 198 originators are not incentivised to mis-mark their traffic by, for 199 example, obtaining an unreasonable throughput increase at the expense 200 of traffic legitimately marked one way or the other. The 201 configuration described here addresses this concern by ensuring that 202 throughput is controlled in a flow-fair manner between the classes, 203 as well as within them. Hence there is no unfair throughput benefit 204 from selecting the low-latency class, while the more severe AQM 205 action will encourage long-path flows to select the more appropriate 206 default class. Hence marking incentives are properly aligned with 207 the intent of the PHB. 209 Two complete CodelAF instances are provided, the ensemble being 210 referred to as Twin-CodelAF. Packets are simply enqueued into one of 211 the two instances, depending on whether the classifier matches the 212 configured value(s) or not. Admission control of any kind is not 213 necessary. The "low latency" instance is configured for the expected 214 path RTT of suitably marked traffic, while the "default" instance 215 remains configured for a general Internet path RTT. 217 Because CodelAF keeps track of the number of active flows, it is then 218 straightforward to perform Weighted Round Robin (WRR) between the two 219 instances on dequeue, with the weight of each instance corresponding 220 to the number of active flows in each. This is the mechanism which 221 enforces flow-fairness between the classes. 223 if(only one queue contains packets): 224 deliver from that queue; 225 else 226 deliver from queue with lowest deficit; 228 deficit of delivered queue += active flows of other queue; 229 deficit of both queues -= min(deficits); 231 5. Security Considerations 233 No particular security concerns are anticipated. 235 6. IANA Considerations 237 There are no IANA considerations. 239 7. Informative References 241 [RFC8100] Geib, R., Ed. and D. Black, "Diffserv-Interconnection 242 Classes and Practice", RFC 8100, DOI 10.17487/RFC8100, 243 March 2017, . 245 [I-D.morton-tsvwg-cheap-nasty-queueing] 246 Morton, J. and P. Heist, "Cheap Nasty Queueing", Work in 247 Progress, Internet-Draft, draft-morton-tsvwg-cheap-nasty- 248 queueing-01, 4 November 2019, 249 . 252 [RFC8290] Hoeiland-Joergensen, T., McKenney, P., Taht, D., Gettys, 253 J., and E. Dumazet, "The Flow Queue CoDel Packet Scheduler 254 and Active Queue Management Algorithm", RFC 8290, 255 DOI 10.17487/RFC8290, January 2018, 256 . 258 [RFC7657] Black, D., Ed. and P. Jones, "Differentiated Services 259 (Diffserv) and Real-Time Communication", RFC 7657, 260 DOI 10.17487/RFC7657, November 2015, 261 . 263 [COBALT] Palmei, J., Gupta, S., Imputato, P., Morton, J., 264 Tahiliani, M.P., Avallone, S., and D. Taht, "Design and 265 Evaluation of COBALT Queue Discipline", September 2019, 266 . 268 [RFC2475] Blake, S., Black, D., Carlson, M., Davies, E., Wang, Z., 269 and W. Weiss, "An Architecture for Differentiated 270 Services", RFC 2475, DOI 10.17487/RFC2475, December 1998, 271 . 273 [RFC8289] Nichols, K., Jacobson, V., McGregor, A., Ed., and J. 274 Iyengar, Ed., "Controlled Delay Active Queue Management", 275 RFC 8289, DOI 10.17487/RFC8289, January 2018, 276 . 278 [I-D.morton-tsvwg-sce] 279 Morton, J. and R. Grimes, "The Some Congestion Experienced 280 ECN Codepoint", Work in Progress, Internet-Draft, draft- 281 morton-tsvwg-sce-01, 4 November 2019, 282 . 284 [RFC3168] Ramakrishnan, K., Floyd, S., and D. Black, "The Addition 285 of Explicit Congestion Notification (ECN) to IP", 286 RFC 3168, DOI 10.17487/RFC3168, September 2001, 287 . 289 Authors' Addresses 291 Jonathan Morton 292 Kokkonranta 21 293 FI-31520 Pitkajarvi 294 Finland 296 Phone: +358 44 927 2377 297 Email: chromatix99@gmail.com 299 Peter G. Heist 300 Redacted 301 463 11 Liberec 30 302 Czech Republic 304 Email: pete@heistp.net