RFC 7806
On Queuing, Marking, and Dropping
RFC 7806: On Queuing, Marking, and Dropping ๐
Okay bestie, here are the deets โจ This is RFC 7806 from April 2016, written by F. Baker and R. Pan, both at Cisco Systems. It's categorised as Informational, so it's a chill explainer and not a Standards Track spec ๐ It's published under ISSN 2070-1721. The title block doesn't list any RFCs it obsoletes or updates, so it isn't replacing or patching anything ๐ซถ
Abstract ๐
Queuing algorithms and marking/dropping algorithms can be implemented in a coupled way, but this note argues that when we write specs, take measurements, or compare them, we should separate the different algorithms and look at what each one contributes to how the system behaves ๐ฆ
Status of This Memo ๐ธ
This document is not an Internet Standards Track specification. It's published just for information ๐ง
It's a product of the Internet Engineering Task Force (IETF), so it represents what the IETF community agrees on. It went through public review and was approved for publication by the Internet Engineering Steering Group (IESG). Not every document the IESG approves is a candidate for any level of Internet Standard, though. See Section 2 of RFC 5741 for that ๐
You can find out the current status of this document, any errata, and how to send feedback at http://www.rfc-editor.org/info/rfc7806.
Copyright Notice ๐
Copyright (c) 2016 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as they stood on the date this document was published. Please read these carefully, because they spell out your rights and restrictions for this document. Any Code Components pulled out of this document must include the Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come with no warranty, as described in the Simplified BSD License ๐
Table of Contents ๐๏ธ
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Fair Queuing: Algorithms and History . . . . . . . . . . . . 3
2.1. Generalized Processor Sharing . . . . . . . . . . . . . . 3
2.1.1. GPS Comparisons: Transmission Quanta . . . . . . . . 4
2.1.2. GPS Comparisons: Flow Definition . . . . . . . . . . 4
2.1.3. GPS Comparisons: Unit of Measurement . . . . . . . . 5
2.2. GPS Approximations . . . . . . . . . . . . . . . . . . . 5
2.2.1. Definition of a Queuing Algorithm . . . . . . . . . . 5
2.2.2. Round-Robin Models . . . . . . . . . . . . . . . . . 6
2.2.3. Calendar Queue Models . . . . . . . . . . . . . . . . 7
2.2.4. Work-Conserving Models and Stochastic Fairness
Queuing . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.5. Non-Work-Conserving Models and Virtual Clock . . . . 9
3. Queuing, Marking, and Dropping . . . . . . . . . . . . . . . 10
3.1. Queuing with Tail Mark/Drop . . . . . . . . . . . . . . . 11
3.2. Queuing with CoDel Mark/Drop . . . . . . . . . . . . . . 11
3.3. Queuing with RED or PIE Mark/Drop . . . . . . . . . . . . 11
4. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 12
5. Security Considerations . . . . . . . . . . . . . . . . . . . 13
6. References . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.1. Normative References . . . . . . . . . . . . . . . . . . 13
6.2. Informative References . . . . . . . . . . . . . . . . . 13
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 15
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 16
1. Introduction โจ
Okay so, Active Queue Management (AQM) has a lot of conversations about coupling queue management algorithms with mark/drop algorithms ๐ The queue managers in those talks are Stochastic Fairness Queuing [SFQ], Virtual Clock [VirtualClock], and Deficit Round Robin [DRR]. The mark/drop side includes Controlled Delay (CoDel) [DELAY-AQM] and Proportional Integral controller Enhanced (PIE) [AQM-PIE]. To make things clearer, this doc walks through the possible ways to implement that pairing and looks at the effects and side effects they could have ๐ฆ The language and model come from the Architecture for Differentiated Services [RFC2475] ๐
This note is informational. It's meant to describe reasonable possibilities without boxing in the outcomes ๐ It's less about "right" versus "wrong" and more about "what might be reasonable," and it covers several possible implementation strategies ๐ Also, queuing can happen at almost any layer, but this note specifically looks at queues that might be used in the Differentiated Services Architecture, which means they sit at or below the IP layer ๐ง
2. Fair Queuing: Algorithms and History ๐ซง
There's a long history behind the group of algorithms people call "fair queuing" ๐ The idea first came up in [RFC970], which proposed it hypothetically as a fix for the TCP Silly Window Syndrome issue in BSD 4.1. The problem was that, thanks to a TCP implementation bug, some senders would fall into a pattern of sending a long stream of very short segments ๐ That wasted bandwidth on TCP and IP headers, filled up the short packet buffers, and knocked over competing sessions ๐ Nagle suggested that if packet streams were sorted by source address and the sources were handled round-robin, then a sender's effect on end-to-end latency and increased loss rate would mostly hit only that sender ๐ซถ That kicked off about a decade of research on what was and still is called "fair queuing." It also sparked philosophical debates about what "fair" even means, operational reasons you might want a "weighted" or "predictably unfair" queuing algorithm, and a whole lot more ๐ญ
2.1. Generalized Processor Sharing ๐
Conceptually, any fair queuing algorithm tries to approximate the Generalized Processor Sharing [GPS] model ๐
At its core, the GPS model assumes that a set of identifiable data streams, called "flows," pass through an interface ๐ธ Every flow has a rate measured over a period of time. For example, a voice session might need 64 kbit/s plus whatever overhead it takes to deliver it, while a TCP session's throughput might vary depending on where it is in its life cycle ๐ The premise of Generalized Processor Sharing is that, on all time scales, a flow occupies a predictable bit rate. So if there's enough bandwidth for the flow in the long term, it also lacks nothing in the short term โจ "All time scales" is totally untenable in a packet network ๐ญ The same goes for a traditional Time-Division Multiplexer (TDM) circuit switch network, because any timescale shorter than the duration of one packet only ever sees one packet at a time ๐ Even so, it gives other models an ideal to be compared against ๐ฆ
There are a bunch of attributes of GPS approximations that matter operationally, including at least the transmission quanta, the definition of a "flow," and the unit of measurement ๐ง Implementation approaches also have different practical impacts ๐
2.1.1. GPS Comparisons: Transmission Quanta ๐
The most obvious comparison between the GPS model and common approximations is that real-world data isn't delivered uniformly. It comes in some quantum ๐ฆ In a packet network, the smallest quantum is a packet, but quanta can be bigger. In video applications, for example, data flow is usually described in frames per second, where a frame is a picture on a screen or the changes made from the previous one ๐ฌ A single video frame is commonly on the order of tens of packets. If a codec delivers thirty frames per second, the packets in each frame might be sent as thirty bursts per second, with each burst going out at the interface rate of the camera or other sender ๐ธ TCP has its own initial window (common values include 1, 2, 3, 4 [RFC3390], and 10 [RFC6928]) ๐ช There are also reports of bursts of 64 KB at the relevant Maximum Segment Size (MSS), which works out to about 45 packets in one burst. These presumably come from TCP Segment Offload ((TSO) also called TCP Offload Engine (TOE)) engines ๐ฅ At least one implementation is known to send a burst of 256 KB ๐ฎ After that initial burst, TCP senders usually send pairs of packets, but they may send smaller or larger bursts [RFC5690] ๐
2.1.2. GPS Comparisons: Flow Definition ๐
Defining a "flow" is an important engineering trade-off for GPS ๐ By definition, a flow is a defined data stream, and there are several common ways to define one ๐ง
- Packets in a single transport layer session ("microflow"), identified by a five-tuple [RFC2990] ๐
- Packets between a single pair of addresses, identified by a source and destination address or prefix ๐ฎ
- Packets from a single source address or prefix [RFC970] ๐ค
- Packets to a single destination address or prefix ๐ฅ
- Packets to or from a single subscriber, customer, or peer [RFC6057]. In Service Provider operations, this might be a neighboring Autonomous System. In broadband, it might be a residential customer ๐
The difference is pretty obvious when you compare sorting by source address with sorting by destination address ๐ Say a router interface has N application sessions going through it, between N/2 local destinations and N remote sources. Sorting by source, or by source/destination pair, would give each remote peer an upper-bound guarantee of 1/N of the available capacity. That capacity could be spread very unevenly among the local destinations ๐ฌ Sorting by destination would give each local destination an upper-bound guarantee of 2/N of the available capacity. That could be spread very unevenly among the remote systems and correlated sessions ๐ So who is one fair to? In both cases the service is equal by their own definition, but that might not match someone else's definition ๐คทโโ๏ธ
Flow fairness, and what TCP's congestion avoidance algorithms mean for it, is covered in depth in [NoFair] ๐
2.1.3. GPS Comparisons: Unit of Measurement ๐
Last but not least, there's the question of what gets measured for rate ๐ If the only goal is to stop packet streams from dominating each other, counting packets is enough ๐ But if the issue is the bit rate of a Service Level Agreement (SLA), you have to consider the packet sizes, meaning the aggregate throughput of a flow measured in bits or bytes ๐ฐ And if predictable unfairness is part of the plan, the value has to be weighted to match ๐ฏ
[RFC7141] discusses measurement ๐
2.2. GPS Approximations ๐งฉ
Going further, a queuing algorithm may be called either "work conserving" or "non work conserving" โจ By definition, a queue in a work-conserving algorithm is either empty, in which case nothing is trying to dequeue data from it, or it has something in it, in which case the algorithm keeps trying to empty it ๐งน A work-conserving queue that holds data at an interface with a given rate will deliver data at that rate until it's empty ๐ A non-work-conserving queue might stop delivering even while it still has data in it ๐ฅบ A common reason to do this is to put an artificial upper bound on a class of traffic that's lower than the rate of the underlying physical interface ๐
2.2.1. Definition of a Queuing Algorithm โจ
okay so before we get into the fun stuff, we need to agree on what a queuing algorithm even IS ๐ซถ for the rest of this, we're assuming it has, at minimum:
- some form of internal storage for the elements kept in the queue;
- if it has multiple internal classifications, then it has
- a method for classifying elements and
- additional storage for the classifier and implied classes;
- potentially, a method for creating the queue;
- potentially, a method for destroying the queue;
- an enqueuing method for placing packets into the queue or queuing system; and
- a dequeuing method for removing packets from the queue or queuing system.
there can also be other stuff, like being able to inspect the queue ๐ it also usually has inspectable external attributes, like the total volume of packets or bytes sitting in the queue, and it might have limit thresholds, like a maximum number of packets or bytes it's allowed to hold. the vibe is very "knows its limits" ๐
for example, a simple FIFO queue has a linear data structure, enqueues packets at the tail, and dequeues packets from the head. it might have a maximum queue depth and a current queue depth maintained in packets or bytes. simple, iconic, no notes ๐ธ
2.2.2. Round-Robin Models ๐
okay so one whole class of implementation approaches is generically called "Weighted Round Robin" (WRR) ๐ the structure of the queue is an array or ring of subqueues, and each subqueue is associated with a flow, for whatever definition of a flow is important to you. it's giving organized chaos but make it structured โจ
the arriving packet must, of course, first be classified. if a hash is used as a classifier, the hash result might be used as an array index, selecting the subqueue the packet will go into. you could imagine other classifiers too, like using a Differentiated Services Code Point (DSCP) value as an index into an array that holds the queue number for a flow, or more complex access list implementations. so many options, bestie, we love a menu ๐
either way, a subqueue contains the traffic for a flow, and data gets sent from each subqueue in succession. it's a taking-turns energy ๐ฆ
when a packet enters the queue, the enqueue method places the classified packet into a simple FIFO subqueue. easy.
on dequeue, the subqueues are searched in round-robin order. when a subqueue is found that contains data, the dequeue method removes a specified quantum of data from it. that quantum is at minimum a packet, but it may be more. and if the system is intended to maintain a byte rate, there will be memory between searches of the excess previously dequeued ๐ง
+-+
+>|1|
| +-+
| |
| +-+ +-+
| |1| +>|3|
| +-+ | +-+
| | | |
| +-+ +-+ | +-+
| |1| +>|2| | |3|
| +-+ | +-+ | +-+
| A | A | A
| | | | | |
++--++ ++--++ ++--++
+->| Q |-->| Q |-->| Q |--+
| +----+ +----+ +----+ |
+----------------------------+
Figure 1: Round-Robin Queues
2.2.3. Calendar Queue Models ๐
next up, another class of implementation approaches, generically called Calendar Queue Implementations [CalendarQueue] ๐๏ธ this one structures the queue as an array or ring of subqueues (often called "buckets") tied to time or sequence. each bucket holds the set of packets intended to be sent at a certain time or after the previous bucket empties. a bucket is allowed to be null too, so it can be empty and that's still valid ๐คทโโ๏ธ
the queue structure also includes a look-aside table that tells you the current depth (aka, the next bucket) of any given class of traffic. that class could be identified with a hash, a DSCP, an access list, or any other classifier. conceptually, the queues each hold zero or more packets from each class of traffic. one is the queue being emptied "now", and the rest are tied to some time or sequence in the future. the characteristics under "load" have been looked into in [Deadline] ๐
when a packet enters, the enqueue method looks at a classified packet and figures out the current depth of that class, so it can schedule it for transmission at some time or sequence in the future. now here's a fun little scenario ๐ฟ if the unit of scheduling is a packet and the queuing quantum is one packet per subqueue, and a burst of packets arrives in a given flow, then if the flow has no queued data at the start, the first packet goes into the "next" queue, the second into its successor, and so on. but if there was already some data in the class, the first packet in the burst would go into the bucket pointed to by the look-aside table. if the unit of scheduling is time, the explanation in Section 2.2.5 might be the simplest to follow, but the bucket selected will be the one matching a given transmission time in the future.
a necessary side effect (memory is finite, after all) is that there exist a finite number of "future" buckets. so if enough traffic arrives to make a class wrap around, something has to be dropped. that's a tail drop, and it's not a vibe ๐
on dequeue, the buckets are searched at their stated times or in their stated sequence. when a bucket with data is found, the dequeue method removes a specified quantum of data from it and, by extension, from the associated traffic classes. a single bucket might hold data from a number of classes all at once, which is very multitasking of it ๐
+-+
+>|1|
| +-+
| |
| +-+ +-+
| |2| +>|2|
| +-+ | +-+
| | | |
| +-+ | +-+ +-+
| |3| | |1| +>|1|
| +-+ | +-+ | +-+
| A | A | A
| | | | | |
++--++ ++--++ ++--++
"now"+->| Q |-->| Q |-->| Q |-->...
+----+ +----+ +----+
A A A
|3 |2 |1
+++++++++++++++++++++++
|||| Flow ||||
+++++++++++++++++++++++
Figure 2: Calendar Queue
again, in any event, a subqueue holds the traffic for a point in time or a point in sequence, and data gets sent from each subqueue in succession. now if the subqueues are tied to time, an interesting end case shows up ๐ what should the system do if it's draining a subqueue and the time for the next subqueue arrives? one potentially valid line of reasoning says keep delivering the data in the present queue, on the assumption that it'll likely trade off for time in the next one. another potentially valid line of reasoning says throw away whatever is waiting in the present queue and move on to the next. both have a point, which is honestly the most annoying thing about queue design ๐ญ
2.2.4. Work-Conserving Models and Stochastic Fairness Queuing ๐ฆ
Stochastic Fairness Queuing [SFQ] is an example of a work-conserving algorithm ๐ this one measures packets and treats a "flow" as an equivalence class of traffic, defined by a hashing algorithm over the source and destination IPv4 addresses. as packets arrive, the enqueue method performs the indicated hash and places the packet into the indicated subqueue. the dequeue method works as described in Section 2.2.2: subqueues get inspected in round-robin sequence, and a packet is removed if they contain one or more packets ๐
then there's the Deficit Round Robin [DRR] model, which changes the quanta to bytes and deals with variable length packets ๐ each subqueue descriptor holds a waiting quantum (the amount intended to be dequeued on the previous dequeue attempt that didn't get satisfied), a per-round quantum (the number of bytes the subqueue is intended to dequeue each round), and a maximum to permit (some multiple of the MTU). in each dequeue attempt, the dequeue method sets the waiting quantum to the smaller of the maximum quantum and the sum of the waiting and incremental quantum. then it dequeues up to the waiting quantum (in bytes) of packets in the queue, and reduces the waiting quantum by the number of bytes dequeued. since packets won't normally be exactly the size of the quantum, some dequeue attempts will dequeue more than others, but over time they'll average out to the incremental quantum per round, as long as there's data present. math being mathing ๐งฎโจ
[SFQ] and [DRR] could be implemented as described in Section 2.2.3. the weakness of a classical WRR approach is the search time spent inspecting, and not choosing, subqueues that contain no data or not enough to trigger a transmission from them. so much time wasted on empty subqueues, honestly rude ๐
2.2.5. Non-Work-Conserving Models and Virtual Clock โฐ
Virtual Clock [VirtualClock] is an example of a non-work-conserving algorithm ๐ it's trivially implemented as described in Section 2.2.3. it associates buckets with intervals in time that last somewhere on the order of microseconds to tens of milliseconds. each flow is assigned a rate in bytes per interval, and the flow entry keeps track of a point in time when the "next" packet in the flow should be scheduled. main character energy for timestamps ๐
on enqueue, the method checks whether the "next schedule" time is "in the past". if it is, the packet is scheduled "now". if not, the packet is scheduled at that time. then it calculates the new "next schedule" time as the current "next schedule" time plus the length of the packet divided by the rate. if that resulting time is also in the past, the "next schedule" time is set to "now"; otherwise, it's set to the calculated time. as noted in Section 2.2.3, there's an interesting point about "too much time in the future": if a packet is scheduled too far out, it may be marked or dropped in the AQM procedure, and if it runs beyond the end of the queuing system, it may be defensively tail dropped. not the future we want ๐ญ
on dequeue, the bucket associated with the time "now" gets inspected. if it contains a packet, that packet is dequeued and transmitted. if the bucket is empty and the time for the next bucket hasn't arrived yet, the system waits, even if there's a packet sitting in the next bucket. patience is a virtue, apparently ๐ซ as noted in Section 2.2.3, there's also an interesting point about the queue associated with "now". if a subsequent bucket, even one that's actually empty, would be delayed by the transmission of a packet, you could imagine marking the packet Explicit Congestion Notification - Congestion Experienced (ECN-CE) [RFC3168] [RFC6679] or dropping the packet. choices, choices, and every single one of them is a plot twist ๐ญ๐ฉท
3. Queuing, Marking, and Dropping ๐
okay bestie, so queuing, marking, and dropping are basically a package deal. If there's a queue, all three are in play ๐ง Even if you don't care about anything else, memory is finite, so a system has to drop stuff (see Sections 2.2.3 and 2.2.5) just to protect itself ๐ The fun twist is that host transports read drops as signals, so AQM algorithms use drops as a way to talk to the sender. It's giving communication ๐โจ
It's also worth thinking of queuing itself as a signal ๐ The receiver sends acknowledgements as it gets data, so acks showing up back at the sender set the sender's pace to roughly the average rate the network can actually handle. This is true even if the sender has an arbitrarily large amount of data sitting in network queues, and it's the reason delay-based congestion control algorithms exist ๐ซถ So when you hold a packet back for a moment so another session can do better, you're basically telling the sender that the capacity is a bit lower. Iconic behavior from the queue, honestly ๐
3.1. Queuing with Tail Mark/Drop
In the default setup, where a FIFO queue only uses defensive tail drop, the queue sends the sender two kinds of signal ๐ธ
- Ack clocking ๐ฆ: this paces the sender so it sends at roughly the rate it can actually get data to the receiver. Pacing = vibes.
- Defensive loss ๐: this happens when a sender sends faster than the available capacity (for example, by probing for network capacity while fully using it) and overburdens a queue. Too much, too fast, not it.
3.2. Queuing with CoDel Mark/Drop
Okay, so when a queuing algorithm is paired with CoDel [DELAY-AQM], here's the play-by-play ๐ฌ A packet gets time stamped, enqueued, dequeued, and then compared to a later clock reading. After that it gets acted on: dropped, marked and forwarded, or just forwarded. The only drop algorithm built into queuing is the defensive drop that kicks in when the queue's resources get overrun ๐ญ The real purpose of marking or dropping is to tell the sender way earlier that a certain amount of delay has been noticed. In a FIFO+CoDel, Virtual Clock+CoDel, or FlowQueue-Codel [FQ-CODEL] setup, the queuing algorithm and the AQM algorithm are totally separate, and when they run in series you get four signals to the sender ๐งโโ๏ธโจ
- Ack clocking ๐ฆ: this paces the sender so it sends at roughly the rate it can deliver data to the receiver through a queue.
- Lossless signaling ๐ซง: this says a certain delay threshold has been reached, if ECN [RFC3168] [RFC6679] is in use.
- Intentional signaling via loss ๐ : this says a certain delay threshold has been reached, if ECN is not in use. Loss doing the job on purpose, iconic.
- Defensive loss ๐: this happens when a sender sends faster than the available capacity (for example, by probing for network capacity while fully using it) and overburdens a queue.
3.3. Queuing with RED or PIE Mark/Drop
Now for PIE [AQM-PIE], Random Early Detection (RED) [RFC7567], and other algorithms like them ๐ The order here is: a queue gets inspected, a packet is dropped, marked, or left alone, then it gets enqueued, dequeued, compared to a later clock reading, and forwarded on.
So the AQM Mark/Drop Algorithm comes before enqueue ๐ง If it doesn't work well and the queue runs out of resources anyway, the defensive drop algorithm steps in. If that's not enough either, the queue just does whatever it does ๐คทโโ๏ธ That means in a FIFO+PIE, SFQ+PIE, or Virtual Clock+PIE setup, the queuing algorithm is once again completely separate from the AQM algorithm. Run in series, you get four signals to the sender ๐
- Ack clocking ๐ฆ: this paces the sender so it sends at roughly the rate it can deliver data to the receiver through a queue.
- Lossless signaling ๐ซง: this says a queue depth that corresponds to a certain delay threshold has been reached, if ECN is in use.
- Intentional signaling via loss ๐ : this says a queue depth that corresponds to a certain delay threshold has been reached, if ECN is not in use.
- Defensive loss ๐: this happens when a sender sends faster than the available capacity (for example, by probing for network capacity while fully using it) and overburdens a queue.
4. Conclusion ๐
Okay, recap time ๐ In Section 2, we looked at implementation approaches for several classes of queuing algorithms. Algorithms like SFQ, Virtual Clock, and FlowQueue-Codel [FQ-CODEL] are valuable in the network because they delay packets to enforce a rate upper bound, or to let competing flows compete more effectively. ECN marking and loss are useful signals too, as long as they're used in a way that improves TCP / Steam Control Transmission Protocol (SCTP) operation or keeps unmanaged UDP data flows in check ๐ซถ
Conceptually, queuing algorithms and mark/drop algorithms work in series (as Section 3 covered), not as one single algorithm ๐ง The effects are different, though. Defensive loss protects the intermediate system and gives a signal. AQM mark/drop works to reduce mean latency. Scheduling flows changes how flows interleave and how acks get paced ๐ฆ Features like flow isolation come from fair-queuing-related designs, not from the mark/drop algorithm, so don't mix those up ๐
There's real value in implementing and coupling queuing algorithms with queue management algorithms, and honestly there's some seriously interesting research going on there ๐ฅ But specifications, measurements, and comparisons should decouple the different algorithms and their contributions to system behavior. Keep the receipts separate, babe ๐๐
5. Security Considerations ๐
This memo adds no new security issues ๐ซถ It just observes implementation strategies for Diffserv implementation.
6. References ๐
6.1. Normative References
- [RFC2475] Blake, S., Black, D., Carlson, M., Davies, E., Wang, Z., and W. Weiss, "An Architecture for Differentiated Services", RFC 2475, DOI 10.17487/RFC2475, December 1998, http://www.rfc-editor.org/info/rfc2475.
6.2. Informative References
- [AQM-PIE] Pan, R., Natarajan, P., and F. Baker, "PIE: A Lightweight Control Scheme To Address the Bufferbloat Problem", Work in Progress, draft-ietf-aqm-pie-06, April 2016.
- [CalendarQueue] Brown, R., "Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem", Communications of the ACM Volume 21, Issue 10, pp. 1220-1227, DOI 10.1145/63039.63045, October 1988, http://dl.acm.org/citation.cfm?id=63045.
- [Deadline] Kruk, L., Lohoczky, J., Ramanan, K., and S. Shreve, "Heavy Traffic Analysis For EDF Queues With Reneging", The Annals of Applied Probability Volume 21, Issue No. 2, pp. 484-545, DOI 10.1214/10-AAP681, 2011, http://www.math.cmu.edu/users/shreve/Reneging.pdf.
- [DELAY-AQM] Nichols, K., Jacobson, V., McGregor, A., and J. Iyengar, "Controlled Delay Active Queue Management", Work in Progress, draft-ietf-aqm-codel-03, March 2016.
- [DRR] Shreedhar, M. and G. Varghese, "Efficient fair queuing using deficit round-robin", IEEE/ACM Transactions on Networking Volume 4, Issue 3, pp. 375-385, DOI 10.1109/90.502236, June 1996, http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=502236.
- [FQ-CODEL] Hoeiland-Joergensen, T., McKenney, P., Taht, D., Gettys, J., and E. Dumazet, "The FlowQueue-CoDel Packet Scheduler and Active Queue Management Algorithm", Work in Progress, draft-ietf-aqm-fq-codel-06, March 2016.
- [GPS] Demers, A., University of California, Berkeley, and Xerox PARC, "Analysis and Simulation of a Fair Queueing Algorithm", ACM SIGCOMM Computer Communication Review, Volume 19, Issue 4, pp. 1-12, DOI 10.1145/75247.75248, September 1989, http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/89/fq.pdf.
- [NoFair] Briscoe, B., "Flow rate fairness: dismantling a religion", ACM SIGCOMM Computer Communication Review, Volume 37, Issue 2, pp. 63-74, DOI 10.1145/1232919.1232926, April 2007, http://dl.acm.org/citation.cfm?id=1232926.
- [RFC970] Nagle, J., "On Packet Switches With Infinite Storage", RFC 970, DOI 10.17487/RFC0970, December 1985, http://www.rfc-editor.org/info/rfc970.
- [RFC2990] Huston, G., "Next Steps for the IP QoS Architecture", RFC 2990, DOI 10.17487/RFC2990, November 2000, http://www.rfc-editor.org/info/rfc2990.
- [RFC3168] Ramakrishnan, K., Floyd, S., and D. Black, "The Addition of Explicit Congestion Notification (ECN) to IP", RFC 3168, DOI 10.17487/RFC3168, September 2001, http://www.rfc-editor.org/info/rfc3168.
- [RFC3390] Allman, M., Floyd, S., and C. Partridge, "Increasing TCP's Initial Window", RFC 3390, DOI 10.17487/RFC3390, October 2002, http://www.rfc-editor.org/info/rfc3390.
- [RFC5690] Floyd, S., Arcia, A., Ros, D., and J. Iyengar, "Adding Acknowledgement Congestion Control to TCP", RFC 5690, DOI 10.17487/RFC5690, February 2010, http://www.rfc-editor.org/info/rfc5690.
- [RFC6057] Bastian, C., Klieber, T., Livingood, J., Mills, J., and R. Woundy, "Comcast's Protocol-Agnostic Congestion Management System", RFC 6057, DOI 10.17487/RFC6057, December 2010, http://www.rfc-editor.org/info/rfc6057.
- [RFC6679] Westerlund, M., Johansson, I., Perkins, C., O'Hanlon, P., and K. Carlberg, "Explicit Congestion Notification (ECN) for RTP over UDP", RFC 6679, DOI 10.17487/RFC6679, August 2012, http://www.rfc-editor.org/info/rfc6679.
- [RFC6928] Chu, J., Dukkipati, N., Cheng, Y., and M. Mathis, "Increasing TCP's Initial Window", RFC 6928, DOI 10.17487/RFC6928, April 2013, http://www.rfc-editor.org/info/rfc6928.
- [RFC7141] Briscoe, B. and J. Manner, "Byte and Packet Congestion Notification", BCP 41, RFC 7141, DOI 10.17487/RFC7141, February 2014, http://www.rfc-editor.org/info/rfc7141.
- [RFC7567] Baker, F., Ed. and G. Fairhurst, Ed., "IETF Recommendations Regarding Active Queue Management", BCP 197, RFC 7567, DOI 10.17487/RFC7567, July 2015, http://www.rfc-editor.org/info/rfc7567.
- [SFQ] Mckenney, P., "Stochastic Fairness Queuing", Proceedings of IEEE INFOCOM '90, Volume 2, pp. 733-740, DOI 10.1109/INFCOM.1990.91316, June 1990, http://www2.rdrop.com/~paulmck/scalability/paper/sfq.2002.06.04.pdf.
- [VirtualClock] Zhang, L., "VirtualClock: A New Traffic Control Algorithm for Packet Switching Networks", Proceedings of the ACM Symposium on Communications Architectures and Protocols, Volume 20, DOI 10.1145/99508.99525, September 1990, http://dl.acm.org/citation.cfm?id=99508.99525.
Acknowledgements ๐ซถ
This note grew out of, and is in response to, mailing list discussions in AQM ๐ฌ Some people pushed an algorithm to compare against AQM marking and dropping algorithms, but that algorithm includes flow queuing, which is the whole plot twist โจ
Authors' Addresses โจ
okay bestie, this is the last stop ๐ and it's where the RFC tells you who to contact. two authors, both at Cisco Systems, both absolutely iconic ๐
here are their details, copied exactly so you know where to find them ๐:
Fred Baker
Cisco Systems
Santa Barbara, California 93117
United States
Email: fred@cisco.com
Rong Pan
Cisco Systems
Milpitas, California 95035
United States
Email: ropan@cisco.com
Fred is the one in Santa Barbara ๐ด and Rong is over in Milpitas ๐ธ. their emails are right there in the block, so if something in this doc is giving confusing vibes, you know who to ask ๐ซถ๐
๐ฆ where this page comes from
- ietf: rfc7806 2016-04
- ๐ girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms