idnits 2.17.1 draft-ietf-aqm-fq-implementation-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 1, 2015) is 3092 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-10) exists of draft-ietf-aqm-codel-01 == Outdated reference: A later version (-06) exists of draft-ietf-aqm-fq-codel-02 == Outdated reference: A later version (-10) exists of draft-ietf-aqm-pie-02 -- Obsolete informational reference (is this intentional?): RFC 2309 (Obsoleted by RFC 7567) Summary: 0 errors (**), 0 flaws (~~), 4 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Active Queue Management F. Baker 3 Internet-Draft R. Pan 4 Intended status: Informational Cisco Systems 5 Expires: May 4, 2016 November 1, 2015 7 On Queuing, Marking, and Dropping 8 draft-ietf-aqm-fq-implementation-05 10 Abstract 12 This note discusses queuing and marking/dropping algorithms. While 13 these algorithms may be implemented in a coupled manner, this note 14 argues that specifications, measurements, and comparisons should 15 decouple the different algorithms and their contributions to system 16 behavior. 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at http://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on May 4, 2016. 35 Copyright Notice 37 Copyright (c) 2015 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 53 2. Fair Queuing: Algorithms and History . . . . . . . . . . . . 3 54 2.1. Generalized Processor Sharing . . . . . . . . . . . . . . 3 55 2.1.1. GPS Comparisons: transmission quanta . . . . . . . . 4 56 2.1.2. GPS Comparisons: flow definition . . . . . . . . . . 4 57 2.1.3. GPS Comparisons: unit of measurement . . . . . . . . 5 58 2.2. GPS Approximations . . . . . . . . . . . . . . . . . . . 5 59 2.2.1. Definition of a queuing algorithm . . . . . . . . . . 5 60 2.2.2. Round Robin Models . . . . . . . . . . . . . . . . . 6 61 2.2.3. Calendar Queue Models . . . . . . . . . . . . . . . . 7 62 2.2.4. Work Conserving Models and Stochastic Fairness 63 Queuing . . . . . . . . . . . . . . . . . . . . . . . 9 64 2.2.5. Non Work Conserving Models and Virtual Clock . . . . 9 65 3. Queuing, Marking, and Dropping . . . . . . . . . . . . . . . 10 66 3.1. Queuing with Tail Mark/Drop . . . . . . . . . . . . . . . 10 67 3.2. Queuing with CoDel Mark/Drop . . . . . . . . . . . . . . 11 68 3.3. Queuing with RED or PIE Mark/Drop . . . . . . . . . . . . 11 69 4. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 12 70 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 71 6. Security Considerations . . . . . . . . . . . . . . . . . . . 12 72 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 13 73 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 13 74 8.1. Normative References . . . . . . . . . . . . . . . . . . 13 75 8.2. Informative References . . . . . . . . . . . . . . . . . 13 76 Appendix A. Change Log . . . . . . . . . . . . . . . . . . . . . 15 77 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 15 79 1. Introduction 81 In the discussion of Active Queue Management, there has been 82 discussion of the coupling of queue management algorithms such as 83 Stochastic Fairness Queuing [SFQ], Virtual Clock [VirtualClock], or 84 Deficit Round Robin [DRR] with mark/drop algorithms such as CoDel 85 [I-D.ietf-aqm-codel] or PIE [I-D.ietf-aqm-pie]. In the interest of 86 clarifying the discussion, we document possible implementation 87 approaches to that, and analyze the possible effects and side- 88 effects. The language and model derive from the Architecture for 89 Differentiated Services [RFC2475]. 91 This note is informational, intended to describe reasonable 92 possibilities without constraining outcomes. This is not so much 93 about "right" or "wrong" as it is "what might be reasonable", and 94 discusses several possible implementation strategies. Also, while 95 queuing might be implemented in almost any layer, specifically the 96 note addresses queues that might be used in the Differentiated 97 Services Architecture, and are therefore at or below the IP layer. 99 2. Fair Queuing: Algorithms and History 101 There is extensive history in the set of algorithms collectively 102 referred to as "Fair Queuing". The model was initially discussed in 103 [RFC0970], which proposed it hypothetically as a solution to the TCP 104 Silly Window Syndrome issue in BSD 4.1. The problem was that, due to 105 a TCP implementation bug, some senders would settle into sending a 106 long stream of very short segments, which unnecessarily consumed 107 bandwidth on TCP and IP headers and occupied short packet buffers, 108 thereby disrupting competing sessions. Nagle suggested that if 109 packet streams were sorted by their source address and the sources 110 treated in a round robin fashion, a sender's effect on end-to-end 111 latency and increased loss rate would primarily affect only itself. 112 This touched off perhaps a decade of work by various researchers on 113 what was and is termed "Fair Queuing," philosophical discussions of 114 the meaning of the word "fair," operational reasons that one might 115 want a "weighted" or "predictably unfair" queuing algorithm, and so 116 on. 118 2.1. Generalized Processor Sharing 120 Conceptually, any Fair Queuing algorithm attempts to implement some 121 approximation to the Generalized Processor Sharing [GPS] model. 123 The GPS model, in its essence, presumes that a set of identified data 124 streams, called "flows", pass through an interface. Each flow has a 125 rate when measured over a period of time; A voice session might, for 126 example, require 64 kbps plus whatever overhead is necessary to 127 deliver it, and a TCP session might have variable throughput 128 depending on where it is in its evolution. The premise of 129 Generalized Processor Sharing is that on all time scales, the flow 130 occupies a predictable bit rate, so that if there is enough bandwidth 131 for the flow in the long term, it also lacks nothing in the short 132 term. "All time scales" is obviously untenable in a packet network - 133 and even in a traditional TDM circuit switch network - because a 134 timescale shorter than the duration of a packet will only see one 135 packet at a time. But it provides an ideal for other models to be 136 compared against. 138 There are a number of attributes of approximations to the GPS model 139 that bear operational consideration, including at least the 140 transmission quanta, the definition of a "flow", and the unit of 141 measurement. Implementation approaches have different practical 142 impacts as well. 144 2.1.1. GPS Comparisons: transmission quanta 146 The most obvious comparison between the GPS model and common 147 approximations to it is that real world data is not delivered 148 uniformly, but in some quantum. The smallest quantum, in a packet 149 network, is a packet. But quanta can be larger; for example, in 150 video applications it is common to describe data flow in frames per 151 second, where a frame describes a picture on a screen or the changes 152 made from a previous one. A single video frame is commonly on the 153 order of tens of packets. If a codec is delivering thirty frames per 154 second, it is conceivable that the packets comprising a frame might 155 be sent as thirty bursts per second, with each burst sent at the 156 interface rate of the camera or other sender. Similarly, TCP 157 exchanges have an initial window, common values of which include 1, 158 2, 3, 4 [RFC3390], and 10 [RFC6928], and there are also reports of 159 bursts of 64 kB at the relevant MSS, which is to say about 45 packets 160 in one burst, presumably coming from TCP Segment Offload (TSO, also 161 called TOE) engines (at least one implementation is known to be able 162 to send a burst of 256 kB). After that initial burst, TCP senders 163 commonly send pairs of packets, but may send either smaller or larger 164 bursts [RFC5690]. 166 2.1.2. GPS Comparisons: flow definition 168 An important engineering trade-off relevant to GPS is the definition 169 of a "flow". A flow is, by definition, a defined data stream. 170 Common definitions include: 172 o Packets in a single transport layer session ("microflow"), 173 identified by a five-tuple [RFC2990], 175 o Packets between a single pair of addresses, identified by a source 176 and destination address or prefix, 178 o Packets from a single source address or prefix [RFC0970], 180 o Packets to a single destination address or prefix, 182 o Packets to or from a single subscriber, customer, or peer 183 [RFC6057]. In Service Provider operations, this might be a 184 neighboring Autonomous System; in broadband, a residential 185 customer. 187 The difference should be apparent. Consider a comparison between 188 sorting by source address or destination address, to pick two 189 examples, in the case that a given router interface has N application 190 sessions going through it between N/2 local destinations and N remote 191 sources. Sorting by source, or in this case by source/destination 192 pair, would give each remote peer an upper bound guarantee of 1/N of 193 the available capacity, which might be distributed very unevenly 194 among the local destinations. Sorting by destination would give each 195 local destination an upper bound guarantee of 2/N of the available 196 capacity, which might be distributed very unevenly among the remote 197 systems and correlated sessions. Who is one fair to? In both cases, 198 they deliver equal service by their definition, but that might not be 199 someone else's definition. 201 Flow fairness, and the implications of TCP's congestion avoidance 202 algorithms, is discussed extensively in [NoFair]. 204 2.1.3. GPS Comparisons: unit of measurement 206 And finally, there is the question of what is measured for rate. If 207 the only objective is to force packet streams to not dominate each 208 other, it is sufficient to count packets. However, if the issue is 209 the bit rate of an SLA, one must consider the sizes of the packets 210 (the aggregate throughput of a flow, measured in bits or bytes). And 211 if predictable unfairness is a consideration, the value must be 212 weighted accordingly. 214 [RFC7141] discusses measurement. 216 2.2. GPS Approximations 218 Carrying the matter further, a queuing algorithm may also be termed 219 "Work Conserving" or "Non Work Conserving". A queue in a "work 220 conserving" algorithm, by definition, is either empty, in which case 221 no attempt is being made to dequeue data from it, or contains 222 something, in which case the algorithm continuously tries to empty 223 the queue. A work conserving queue that contains queued data, at an 224 interface with a given rate, will deliver data at that rate until it 225 empties. A non-work-conserving queue might stop delivering even 226 though it still contains data. A common reason for doing this is to 227 impose an artificial upper bound on a class of traffic that is lower 228 than the rate of the underlying physical interface. 230 2.2.1. Definition of a queuing algorithm 232 In the discussion following, we assume a basic definition of a 233 queuing algorithm. A queuing algorithm has, at minimum: 235 o Some form of internal storage for the elements kept in the queue, 237 o If it has multiple internal classifications, 239 * a method for classifying elements, 240 * additional storage for the classifier and implied classes, 242 o potentially, a method for creating the queue, 244 o potentially, a method for destroying the queue, 246 o an enqueuing method, for placing packets into the queue or queuing 247 system 249 o a dequeuing method, for removing packets from the queue or queuing 250 system 252 There may also be other information or methods, such as the ability 253 to inspect the queue. It also often has inspectable external 254 attributes, such as the total volume of packets or bytes in queue, 255 and may have limit thresholds, such as a maximum number of packets or 256 bytes the queue might hold. 258 For example, a simple FIFO queue has a linear data structure, 259 enqueues packets at the tail, and dequeues packets from the head. It 260 might have a maximum queue depth and a current queue depth, 261 maintained in packets or bytes. 263 2.2.2. Round Robin Models 265 One class of implementation approaches, generically referred to as 266 "Weighted Round Robin" (WRR), implements the structure of the queue 267 as an array or ring of sub-queues associated with flows, for whatever 268 definition of a flow is important. 270 The arriving packet must, of course, first be classified. If a hash 271 is used as a classifier, the modulus of the hash might be used as an 272 array index, selecting the sub-queue that the packet will go into. 273 One can imagine other classifiers, such as using a Differentiated 274 Services Code Point (DSCP) value as an index into an array containing 275 the queue number for a flow, or more complex access list 276 implementations. 278 In any event, a sub-queue contains the traffic for a flow, and data 279 is sent from each sub-queue in succession. 281 On enqueue, the enqueue method places a classified packet into a 282 simple FIFO sub-queue. 284 On dequeue, the sub-queues are searched in round-robin order, and 285 when a sub-queue is identified that contains data, the dequeue method 286 removes a specified quantum of data from it. That quantum is at 287 minimum a packet, but it may be more. If the system is intended to 288 maintain a byte rate, there will be memory between searches of the 289 excess previously dequeued. 291 +-+ 292 +>|1| 293 | +-+ 294 | | 295 | +-+ +-+ 296 | |1| +>|3| 297 | +-+ | +-+ 298 | | | | 299 | +-+ +-+ | +-+ 300 | |1| +>|2| | |3| 301 | +-+ | +-+ | +-+ 302 | A | A | A 303 | | | | | | 304 ++--++ ++--++ ++--++ 305 +->| Q |-->| Q |-->| Q |--+ 306 | +----+ +----+ +----+ | 307 +----------------------------+ 309 Figure 1: Round Robin Queues 311 2.2.3. Calendar Queue Models 313 Another class of implementation approaches, generically referred 314 Calendar Queue Implementations [CalendarQueue], implements the 315 structure of the queue as an array or ring of sub-queues (often 316 called "buckets") associated with time or sequence; Each bucket 317 contains the set of packets, which may be null, intended to be sent 318 at a certain time or following the emptying of the previous bucket. 319 The queue structure includes a look-aside table that indicates the 320 current depth (which is to say, the next bucket) of any given class 321 of traffic, which might similarly be identified using a hash, a DSCP, 322 an access list, or any other classifier. Conceptually, the queues 323 each contain zero or more packets from each class of traffic. One is 324 the queue being emptied "now"; the rest are associated with some time 325 or sequence in the future. The characteristics under load have been 326 investigated in [Deadline]. 328 On enqueue, the enqueue method, considering a classified packet, 329 determines the current depth of that class with a view to scheduling 330 it for transmission at some time or sequence in the future. If the 331 unit of scheduling is a packet and the queuing quantum is one packet 332 per sub-queue, a burst of packets arrives in a given flow, and at the 333 start the flow has no queued data, the first packet goes into the 334 "next" queue, the second into its successor, and so on; if there was 335 some data in the class, the first packet in the burst would go into 336 the bucket pointed to by the look-aside table. If the unit of 337 scheduling is time, the explanation in Section 2.2.5 might be 338 simplest to follow, but the bucket selected will be the bucket 339 corresponding to a given transmission time in the future. A 340 necessary side-effect, memory being finite, is that there exist a 341 finite number of "future" buckets. If enough traffic arrives to 342 cause a class to wrap, one is forced to drop something (tail-drop). 344 On dequeue, the buckets are searched at their stated times or in 345 their stated sequence, and when a bucket is identified that contains 346 data, the dequeue method removes a specified quantum of data from it 347 and, by extension, from the associated traffic classes. A single 348 bucket might contain data from a number of classes simultaneously. 350 +-+ 351 +>|1| 352 | +-+ 353 | | 354 | +-+ +-+ 355 | |2| +>|2| 356 | +-+ | +-+ 357 | | | | 358 | +-+ | +-+ +-+ 359 | |3| | |1| +>|1| 360 | +-+ | +-+ | +-+ 361 | A | A | A 362 | | | | | | 363 ++--++ ++--++ ++--++ 364 "now"+->| Q |-->| Q |-->| Q |-->... 365 +----+ +----+ +----+ 366 A A A 367 |3 |2 |1 368 +++++++++++++++++++++++ 369 |||| Flow |||| 370 +++++++++++++++++++++++ 372 Figure 2: Calendar Queue 374 In any event, a sub-queue contains the traffic for a point in time or 375 a point in sequence, and data is sent from each sub-queue in 376 succession. If sub-queues are associated with time, an interesting 377 end case develops: If the system is draining a given sub-queue, and 378 the time of the next sub-queue arrives, what should the system do? 379 One potentially valid line of reasoning would have it continue 380 delivering the data in the present queue, on the assumption that it 381 will likely trade off for time in the next. Another potentially 382 valid line of reasoning would have it discard any waiting data in the 383 present queue and move to the next. 385 2.2.4. Work Conserving Models and Stochastic Fairness Queuing 387 Stochastic Fairness Queuing [SFQ] is an example of a work conserving 388 algorithm. This algorithm measures packets, and considers a "flow" 389 to be an equivalence class of traffic defined by a hashing algorithm 390 over the source and destination IPv4 addresses. As packets arrive, 391 the enqueue method performs the indicated hash and places the packet 392 into the indicated sub-queue. The dequeue method operates as 393 described in Section 2.2.2; sub-queues are inspected in round-robin 394 sequence, and if they contain one or more packets, a packet is 395 removed. 397 Deficit Round Robin [DRR] model modifies the quanta to bytes, and 398 deals with variable length packets. A sub-queue descriptor contains 399 a waiting quantum (the amount intended to be dequeued on the previous 400 dequeue attempt that was not satisfied), a per-round quantum (the 401 sub-queue is intended to dequeue a certain number of bytes each 402 round), and a maximum to permit (some multiple of the MTU). In each 403 dequeue attempt, the dequeue method sets the waiting quantum to the 404 smaller of the maximum quantum and the sum of the waiting and 405 incremental quantum. It then dequeues up to the waiting quantum, in 406 bytes, of packets in the queue, and reduces the waiting quantum by 407 the number of bytes dequeued. Since packets will not normally be 408 exactly the size of the quantum, some dequeue attempts will dequeue 409 more than others, but they will over time average the incremental 410 quantum per round if there is data present. 412 [SFQ] and [DRR] could be implemented as described in Section 2.2.3. 413 The weakness of a WRR approach is the search time expended when the 414 queuing system is relatively empty or the overhead of obviating that 415 issue, which the calendar queue model also obviates. 417 2.2.5. Non Work Conserving Models and Virtual Clock 419 Virtual Clock [VirtualClock] is an example of a non-work-conserving 420 algorithm. It is trivially implemented as described in 421 Section 2.2.3. It associates buckets with intervals in time, with 422 durations on the order of microseconds to tens of milliseconds. Each 423 flow is assigned a rate in bytes per interval. The flow entry 424 maintains a point in time the "next" packet in the flow should be 425 scheduled. 427 On enqueue, the method determines whether the "next schedule" time is 428 "in the past"; if so, the packet is scheduled "now", and if not, the 429 packet is scheduled at that time. It then calculates the new "next 430 schedule" time, as the current "next schedule" time plus the length 431 of the packet divided by the rate; if the resulting time is also in 432 the past, the "next schedule" time is set to "now", and otherwise to 433 the calculated time. As noted in Section 2.2.3, there is an 434 interesting point regarding "too much time in the future"; if a 435 packet is scheduled too far into the future, it may be marked or 436 dropped in the AQM procedure, and if it runs beyond the end of the 437 queuing system, may be defensively tail dropped. 439 On dequeue, the bucket associated with the time "now" is inspected. 440 If it contains a packet, the packet is dequeued and transmitted. If 441 the bucket is empty and the time for the next bucket has not arrived, 442 the system waits, even if there is a packet in the next bucket. As 443 noted in Section 2.2.3, there is an interesting point regarding the 444 queue associated with "now". If a subsequent bucket, even if it is 445 actually empty, would be delayed by the transmission of a packet, one 446 could imagine marking the packet ECN CE [RFC3168] [RFC6679] or 447 dropping the packet. 449 3. Queuing, Marking, and Dropping 451 Queuing, marking, and dropping are integrated in any system that has 452 a queue. If nothing else, as memory is finite, a system has to drop 453 as discussed in Section 2.2.3 and Section 2.2.5 in order to protect 454 itself. However, host transports interpret drops as signals, so AQM 455 algorithms use that as a mechanism to signal. 457 It is useful to think of the effects of queuing as a signal as well. 458 The receiver sends acknowledgements as data is received, so the 459 arrival of acknowledgements at the sender paces the sender at 460 approximately the average rate it is able to achieve through the 461 network. This is true even if the sender keeps an arbitrarily large 462 amount of data stored in network queues, and is the basis for delay- 463 based congestion control algorithms. So, delaying a packet 464 momentarily in order to permit another session to improve its 465 operation has the effect of signaling a slightly lower capacity to 466 the sender. 468 3.1. Queuing with Tail Mark/Drop 470 In the default case, in which a FIFO queue is used with defensive 471 tail-drop only, the effect is therefore to signal to the sender in 472 two ways: 474 o Ack Clocking, pacing the sender to send at approximately the rate 475 it can deliver data to the receiver, and 477 o Defensive loss, when a sender sends faster than available capacity 478 (such as by probing network capacity when fully utilizing that 479 capacity) and overburdens a queue. 481 3.2. Queuing with CoDel Mark/Drop 483 In any case wherein a queuing algorithm is used along with CoDel 484 [I-D.ietf-aqm-codel], the sequence of events is that a packet is 485 time-stamped, enqueued, dequeued, compared to a subsequent reading of 486 the clock, and then acted on, whether by dropping it, marking and 487 forwarding it, or simply forwarding it. This is to say that the only 488 drop algorithm inherent in queuing is the defensive drop when the 489 queue's resources are overrun. However, the intention of marking or 490 dropping is to signal to the sender much earlier, when a certain 491 amount of delay has been observed. In a FIFO+CoDel, Virtual 492 Clock+CoDel, or FlowQueue-Codel [I-D.ietf-aqm-fq-codel] 493 implementation, the queuing algorithm is completely separate from the 494 AQM algorithm. Using them in series results in four signals to the 495 sender: 497 o Ack Clocking, pacing the sender to send at approximately the rate 498 it can deliver data to the receiver through a queue, 500 o Lossless signaling that a certain delay threshold has been 501 reached, if ECN [RFC3168][RFC6679] is in use, 503 o Intentional signaling via loss that a certain delay threshold has 504 been reached, if ECN is not in use, and 506 o Defensive loss, when a sender sends faster than available capacity 507 (such as by probing network capacity when fully utilizing that 508 capacity) and overburdens a queue. 510 3.3. Queuing with RED or PIE Mark/Drop 512 In any case wherein a queuing algorithm is used along with PIE 513 [I-D.ietf-aqm-pie], RED [RFC2309], or other such algorithms, the 514 sequence of events is that a queue is inspected, a packet is dropped, 515 marked, or left unchanged, enqueued, dequeued, compared to a 516 subsequent reading of the clock, and then forwarded on. This is to 517 say that the AQM Mark/Drop Algorithm precedes enqueue; if it has not 518 been effective and as a result the queue is out of resources anyway, 519 the defensive drop algorithm steps in, and failing that, the queue 520 operates in whatever way it does. Hence, in a FIFO+PIE, SFQ+PIE, or 521 Virtual Clock+PIE implementation, the queuing algorithm is again 522 completely separate from the AQM algorithm. Using them in series 523 results in four signals to the sender: 525 o Ack Clocking, pacing the sender to send at approximately the rate 526 it can deliver data to the receiver through a queue, 528 o Lossless signaling that a queue depth that corresponds to a 529 certain delay threshold has been reached, if ECN is in use, 531 o Intentional signaling via loss that a queue depth that corresponds 532 to a certain delay threshold has been reached, if ECN is not in 533 use, and 535 o Defensive loss, when a sender sends faster than available capacity 536 (such as by probing network capacity when fully utilizing that 537 capacity) and overburdens a queue. 539 4. Conclusion 541 To summarize, in Section 2, implementation approaches for several 542 classes of queuing algorithms were explored. Queuing algorithms such 543 as SFQ, Virtual Clock, and FlowQueue-Codel [I-D.ietf-aqm-fq-codel] 544 have value in the network, in that they delay packets to enforce a 545 rate upper bound or to permit competing flows to compete more 546 effectively. ECN Marking and loss are also useful signals if used in 547 a manner that enhances TCP/SCTP operation or restrains unmanaged UDP 548 data flows. 550 Conceptually, queuing algorithms and mark/drop algorithms operate in 551 series, as discussed in Section 3, not as a single algorithm. The 552 observed effects differ: defensive loss protects the intermediate 553 system and provides a signal, AQM mark/drop works to reduce mean 554 latency, and the scheduling of flows works to modify flow interleave 555 and acknowledgement pacing. Certain features like flow isolation are 556 provided by fair queuing related designs, but are not the effect of 557 the mark/drop algorithm. 559 There is value in implementing and coupling the operation of both 560 queuing algorithms and queue management algorithms, and there is 561 definitely interesting research in this area, but specifications, 562 measurements, and comparisons should decouple the different 563 algorithms and their contributions to system behavior. 565 5. IANA Considerations 567 This memo asks the IANA for no new parameters. 569 6. Security Considerations 571 This memo adds no new security issues; it observes on implementation 572 strategies for Diffserv implementation. 574 7. Acknowledgements 576 This note grew out of, and is in response to, mailing list 577 discussions in AQM, in which some have pushed an algorithm the 578 compare to AQM marking and dropping algorithms, but which includes 579 Flow Queuing. 581 8. References 583 8.1. Normative References 585 [RFC2475] Blake, S., Black, D., Carlson, M., Davies, E., Wang, Z., 586 and W. Weiss, "An Architecture for Differentiated 587 Services", RFC 2475, DOI 10.17487/RFC2475, December 1998, 588 . 590 8.2. Informative References 592 [CalendarQueue] 593 "Calendar queues: a fast 0(1) priority queue 594 implementation for the simulation event set problem", 595 Communications of the ACM 1988, October 1988, 596 . 598 [Deadline] 599 , , , and , "Heavy Traffic Analysis For Edf Queues With 600 Reneging", Annals of Applied Probability 2011, 2011, 601 . 603 [DRR] Microsoft Corporation and Washington University in St. 604 Louis, "Efficient fair queueing using deficit round 605 robin", ACM SIGCOMM 1995, October 1995, 606 . 609 [GPS] Xerox PARC, University of California, Berkeley, and Xerox 610 PARC, "Analysis and simulation of a fair queueing 611 algorithm", ACM SIGCOMM 1989, September 1989, 612 . 615 [I-D.ietf-aqm-codel] 616 Nichols, K., Jacobson, V., McGregor, A., and J. Jana, 617 "Controlled Delay Active Queue Management", draft-ietf- 618 aqm-codel-01 (work in progress), April 2015. 620 [I-D.ietf-aqm-fq-codel] 621 Hoeiland-Joergensen, T., McKenney, P., 622 dave.taht@gmail.com, d., Gettys, J., and E. Dumazet, 623 "FlowQueue-Codel", draft-ietf-aqm-fq-codel-02 (work in 624 progress), October 2015. 626 [I-D.ietf-aqm-pie] 627 Pan, R., Natarajan, P., and F. Baker, "PIE: A Lightweight 628 Control Scheme To Address the Bufferbloat Problem", draft- 629 ietf-aqm-pie-02 (work in progress), August 2015. 631 [NoFair] British Telecom, "Flow rate fairness: dismantling a 632 religion", ACM SIGCOMM 2007, April 2007, 633 . 635 [RFC0970] Nagle, J., "On Packet Switches With Infinite Storage", 636 RFC 970, DOI 10.17487/RFC0970, December 1985, 637 . 639 [RFC2309] Braden, B., Clark, D., Crowcroft, J., Davie, B., Deering, 640 S., Estrin, D., Floyd, S., Jacobson, V., Minshall, G., 641 Partridge, C., Peterson, L., Ramakrishnan, K., Shenker, 642 S., Wroclawski, J., and L. Zhang, "Recommendations on 643 Queue Management and Congestion Avoidance in the 644 Internet", RFC 2309, DOI 10.17487/RFC2309, April 1998, 645 . 647 [RFC2990] Huston, G., "Next Steps for the IP QoS Architecture", 648 RFC 2990, DOI 10.17487/RFC2990, November 2000, 649 . 651 [RFC3168] Ramakrishnan, K., Floyd, S., and D. Black, "The Addition 652 of Explicit Congestion Notification (ECN) to IP", 653 RFC 3168, DOI 10.17487/RFC3168, September 2001, 654 . 656 [RFC3390] Allman, M., Floyd, S., and C. Partridge, "Increasing TCP's 657 Initial Window", RFC 3390, DOI 10.17487/RFC3390, October 658 2002, . 660 [RFC5690] Floyd, S., Arcia, A., Ros, D., and J. Iyengar, "Adding 661 Acknowledgement Congestion Control to TCP", RFC 5690, 662 DOI 10.17487/RFC5690, February 2010, 663 . 665 [RFC6057] Bastian, C., Klieber, T., Livingood, J., Mills, J., and R. 666 Woundy, "Comcast's Protocol-Agnostic Congestion Management 667 System", RFC 6057, DOI 10.17487/RFC6057, December 2010, 668 . 670 [RFC6679] Westerlund, M., Johansson, I., Perkins, C., O'Hanlon, P., 671 and K. Carlberg, "Explicit Congestion Notification (ECN) 672 for RTP over UDP", RFC 6679, DOI 10.17487/RFC6679, August 673 2012, . 675 [RFC6928] Chu, J., Dukkipati, N., Cheng, Y., and M. Mathis, 676 "Increasing TCP's Initial Window", RFC 6928, 677 DOI 10.17487/RFC6928, April 2013, 678 . 680 [RFC7141] Briscoe, B. and J. Manner, "Byte and Packet Congestion 681 Notification", BCP 41, RFC 7141, DOI 10.17487/RFC7141, 682 February 2014, . 684 [SFQ] SRI International, "Stochastic Fairness Queuing", IEEE 685 Infocom 1990, June 1990, 686 . 689 [VirtualClock] 690 Xerox PARC, "Virtual Clock", ACM SIGCOMM 1990, September 691 1990, 692 . 694 Appendix A. Change Log 696 Initial Version: June 2014 698 Authors' Addresses 700 Fred Baker 701 Cisco Systems 702 Santa Barbara, California 93117 703 USA 705 Email: fred@cisco.com 706 Rong Pan 707 Cisco Systems 708 Milpitas, California 95035 709 USA 711 Email: ropan@cisco.com