RFC 8290
The Flow Queue CoDel Packet Scheduler and Active Queue Management Algorithm
RFC 8290 is "The Flow Queue CoDel Packet Scheduler and Active Queue Management Algorithm" 💖 It's an Experimental document from the IETF (Internet Engineering Task Force), dated January 2018, with ISSN 2070-1721. The authors are T. Hoeiland-Joergensen (Karlstad University), P. McKenney (IBM Linux Technology Center), D. Taht (Teklibre), J. Gettys, and E. Dumazet (Google, Inc.). The header doesn't list any RFCs that it obsoletes or updates 🦋
Abstract ✨
This memo presents the FQ-CoDel hybrid packet scheduler and Active Queue Management (AQM) algorithm, a powerful tool for fighting bufferbloat and reducing latency 🔥
FQ-CoDel mixes packets from multiple flows and reduces the impact of head-of-line blocking from bursty traffic. It gives low-rate traffic like DNS, web, and videoconferencing some isolation 🫶 It also improves utilisation across the networking fabric, especially for bidirectional traffic, by keeping queue lengths short. And it can be implemented in a memory- and CPU-efficient way across a wide range of hardware 💅
Status of This Memo
This document is not an Internet Standards Track specification. It's published for examination, experimental implementation, and evaluation 🧪
This document defines an Experimental Protocol for the Internet community. It's a product of the Internet Engineering Task Force (IETF) and represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Not all documents approved by the IESG are candidates for any level of Internet Standard, so see Section 2 of RFC 7841 for more on that 🌸
Information about the current status of this document, any errata, and how to give feedback on it can be found at https://www.rfc-editor.org/info/rfc8290 ✨
Copyright Notice
Copyright (c) 2018 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 (https://trustee.ietf.org/license-info) as in effect on the date of publication of this document. Please review these documents carefully, because they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they are provided without warranty as described in the Simplified BSD License 📜
Table of Contents 🧚
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Conventions Used in This Document . . . . . . . . . . . . 4
1.2. Terminology and Concepts . . . . . . . . . . . . . . . . 5
1.3. Informal Summary of FQ-CoDel . . . . . . . . . . . . . . 5
2. CoDel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3. Flow Queueing . . . . . . . . . . . . . . . . . . . . . . . . 7
4. The FQ-CoDel Scheduler . . . . . . . . . . . . . . . . . . . 8
4.1. Enqueue . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.1.1. Alternative Classification Schemes . . . . . . . . . 9
4.2. Dequeue . . . . . . . . . . . . . . . . . . . . . . . . . 10
5. Implementation Considerations . . . . . . . . . . . . . . . . 11
5.1. Data Structures . . . . . . . . . . . . . . . . . . . . . 11
5.2. Parameters . . . . . . . . . . . . . . . . . . . . . . . 12
5.2.1. Interval . . . . . . . . . . . . . . . . . . . . . . 12
5.2.2. Target . . . . . . . . . . . . . . . . . . . . . . . 12
5.2.3. Packet Limit . . . . . . . . . . . . . . . . . . . . 13
5.2.4. Quantum . . . . . . . . . . . . . . . . . . . . . . . 13
5.2.5. Flows . . . . . . . . . . . . . . . . . . . . . . . . 13
5.2.6. Explicit Congestion Notification (ECN) . . . . . . . 14
5.2.7. CE Threshold . . . . . . . . . . . . . . . . . . . . 14
5.3. Probability of Hash Collisions . . . . . . . . . . . . . 14
5.4. Memory Overhead . . . . . . . . . . . . . . . . . . . . . 15
5.5. Per-Packet Timestamping . . . . . . . . . . . . . . . . . 16
5.6. Limiting Queueing in Lower Layers . . . . . . . . . . . . 16
5.7. Other Forms of Fair Queueing . . . . . . . . . . . . . . 17
5.8. Differences between CoDel and FQ-CoDel Behaviour . . . . 17
6. Limitations of Flow Queueing . . . . . . . . . . . . . . . . 18
6.1. Fairness between Things Other Than Flows . . . . . . . . 18
6.2. Flow Bunching by Opaque Encapsulation . . . . . . . . . . 18
6.3. Low-Priority Congestion Control Algorithms . . . . . . . 19
7. Deployment Status and Future Work . . . . . . . . . . . . . . 19
8. Security Considerations . . . . . . . . . . . . . . . . . . . 20
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 21
10.1. Normative References . . . . . . . . . . . . . . . . . . 21
10.2. Informative References . . . . . . . . . . . . . . . . . 21
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 24
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 251. Introduction ✨
The Flow Queue CoDel (FQ-CoDel) algorithm is a combined packet scheduler and Active Queue Management (AQM) [RFC3168] algorithm. It was developed as part of the bufferbloat-fighting community effort [BLOATWEB]. It's based on a modified Deficit Round Robin (DRR) queue scheduler [DRR] [DRRPP], with the CoDel AQM [RFC8289] algorithm operating on each queue. This document describes the combined algorithm. Reference implementations are available for the ns-2 [NS2] and ns-3 [NS3] network simulators, and the algorithm is included in the mainline Linux kernel as the fq_codel queueing discipline [LINUXSRC] 🌈
FQ-CoDel is a general, efficient, nearly parameterless queue management approach that combines flow queueing with CoDel. It's a powerful tool for solving bufferbloat [BLOAT], and it has already been turned on by default in a number of Linux distributions 💜 In this document, we describe the Linux implementation in enough detail for others to independently implement the algorithm for deployment outside the Linux ecosystem 🍓
Since the FQ-CoDel algorithm was originally developed in the Linux kernel, that implementation is still considered canonical. This document describes the algorithm in the abstract in Sections 1-4 and separates out most implementation details in subsequent sections. However, the Linux implementation is used as a reference for default behaviour in the abstract algorithm description 🎀
This document is structured as follows. This section gives some concepts and terminology used in the rest of the document, plus a short informal summary of the FQ-CoDel algorithm. Section 2 gives an overview of the CoDel algorithm. Section 3 covers the flow hashing and DRR portion. Section 4 then describes how the algorithm works in detail, while Section 5 describes implementation details and considerations. Section 6 lists some of the limitations of using flow queueing. Section 7 outlines the current status of FQ-CoDel deployment and lists some possible future areas of inquiry. Finally, Section 8 reiterates some important security points that must be observed in the implementation. Don't skip that one, bestie 😭🔥
1.1. Conventions Used in This Document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here 🫶
1.2. Terminology and Concepts
- Flow: A flow is typically identified by a 5-tuple of source IP address, destination IP address, source port number, destination port number, and protocol number. It can also be identified by a superset or subset of those parameters, by Media Access Control (MAC) address, or by other means. FQ-CoDel hashes flows into a configurable number of buckets to assign packets to internal queues 🦋
- Queue: A queue of packets represented internally in FQ-CoDel. In most instances, each flow gets its own queue. However, because of the possibility of hash collisions, this is not always the case. To avoid confusion, the word "queue" is used to refer to the internal data structure, and "flow" is used to refer to the actual stream of packets being delivered to the FQ-CoDel algorithm 🧃
- Scheduler: A mechanism to select which queue a packet is dequeued from 🎯
- CoDel AQM: The Active Queue Management algorithm employed by FQ-CoDel, as described in [RFC8289] 💅
- DRR: Deficit Round Robin scheduling [DRR] 🔁
- Quantum: The maximum amount of bytes to be dequeued from a queue at once 🍰
- Interval: Characteristic time period used by the control loop of CoDel to detect when a persistent queue is developing (see Section 4.2 of [RFC8289]) 👀
- Target: Setpoint value of the minimum sojourn time of packets in a queue, used as the target of the control loop in CoDel (see Section 4.3 of [RFC8289]) 🎯
1.3. Informal Summary of FQ-CoDel ✨
okay bestie, FQ-CoDel is basically a mashup of DRR [DRR] and CoDel [RFC8289] 💖 it also has a sparse-flow boost that's kinda like Shortest Queue First (SQF) [SQF] and DRR++ [DRRPP] 🦋 we call it "flow queueing" and not "fair queueing" because flows that build a queue get treated differently from flows that don't 💅
by default, FQ-CoDel sorts incoming packets into different queues by hashing the 5-tuple: protocol number, source and destination IP addresses, and source and destination port numbers 🎀 it also mixes in a random number picked at initiation time to shake things up. other flow classification schemes can be configured instead, if you want (see Section 4.1.1) 🧚 every queue gets managed by the CoDel AQM algorithm [CODEL] [RFC8289] ⭐ inside a queue, packet ordering is kept, since queues are FIFO 🌸
the FQ-CoDel algorithm has two logical parts. first, there's the scheduler, which picks which queue to dequeue a packet from. second, there's the CoDel AQM, which works on each of the queues 👑 the real drama is in the scheduling part, while the way the scheduler and CoDel work together is pretty straightforward 💜
at initialisation, each queue gets its own set of CoDel state variables. by default, 1024 queues get created. the Linux implementation at the time of writing supports anywhere from one to 65535 separate queues 🌈 each queue keeps its state variables for its whole lifetime, so it acts the same way the non-FQ version of CoDel would. which means with only one queue, FQ-CoDel basically behaves like CoDel by itself 🙈
on dequeue, FQ-CoDel picks a queue using a two-tier, round-robin scheme. each queue can dequeue up to a configurable quantum of bytes per iteration 🍓 any deviations from that quantum get kept as byte credits for the queue, which makes the fairness scheme byte-based instead of packet-based 💅 the two-tier round-robin tells apart "new" queues (ones that don't build up a standing queue) from "old" queues (ones that have queued enough data to be active for more than one iteration of the round-robin scheduler) 😭
this new/old split has a big consequence for queues that don't build up more than a quantum of bytes before the scheduler visits them. that kind of queue gets removed from the list after it empties, then gets re-added as a new queue the next time a packet shows up for it 🦋 so it effectively jumps ahead of queues that don't empty out each round. (there's a small caveat here to protect against starvation, see below 🫶) how little data a flow needs to send to stay in this state is kinda hard to reason about, because it depends on both the egress link speed and how many flows are running at once 🌸 but in practice, lots of things people want prioritised for normal internet use (ACKs, DNS lookups, interactive Secure Shell (SSH), HTTP requests, Voice over IP (VoIP)) tend to fall into this category. that's why FQ-CoDel does so well for so many real-world apps ✨
the prioritisation is implicit, though, so apps that need guaranteed priority (like multiplexing the network control plane over the network itself) still need explicit classification 🙈
this scheduling scheme has some subtlety, and the rest of this document explains it in detail 🎀
2. CoDel 🌷
CoDel is described in the Communications of the ACM paper [CODEL] and the IETF document [RFC8289] 💖 the basic idea is to control queue length: keep enough queueing to keep the outgoing link busy, but don't let the queue grow past that point 🍓 it does this by preferentially dropping packets that have been sitting in the queue for "too long" 😭 packets get dropped by head drop, which shortens the time for the drop signal to get back to the sender by the length of the queue, and it helps trigger TCP fast retransmit sooner 🚀
the CoDel algorithm isn't described here. instead, go read the CoDel document [RFC8289] 📖✨
3. Flow Queueing 🦋
the whole point of FQ-CoDel's scheduler is to give each flow its own queue, which is where "flow queueing" comes from 💅 but instead of doing that perfectly, it uses a hashing-based scheme: flows get hashed into a number of buckets, and each bucket has its own queue 🌈 the number of buckets is configurable and defaults to 1024 in the Linux implementation 👑 that's enough to avoid hash collisions for a moderate number of flows, like the ones you'd see in a home gateway 🏠 depending on the link's characteristics, you can tune it to trade memory for a lower chance of hash collisions 🧚 see Sections 5.3 and 5.4 for a deeper dive on that 💜
by default, flow hashing uses the 5-tuple: source and destination IP addresses, source and destination port numbers, and protocol number 🎀 you can customise the hashing to match on arbitrary packet bytes, but be careful, because much of the FQ-CoDel scheduler's benefit comes from that per-flow separation ⚠️ the default hashing does have some limitations, which Section 6 covers 🙈
FQ-CoDel's DRR scheduler is byte-based and uses a deficit round-robin mechanism between queues 💖 it works by tracking the current number of "byte credits" for each queue. that number starts at the configurable quantum. each time a queue gets a dequeue opportunity, it can dequeue packets, and its credits go down by each packet's size 🍓 this keeps going until the byte credits counter hits zero or less. at that point, the counter goes up by one quantum and the dequeue opportunity ends 🌸
so say one queue has packets of size quantum/3 and another has quantum-sized packets. the first queue dequeues three packets each time it gets a turn, while the second only dequeues one 🦋 that means flows sending small packets don't get penalised just because their packets are smaller. instead, DRR approximates a byte-based fair queueing scheme 💅 the quantum sets the scheduling granularity, and if it's too small, the trade-off is scheduling overhead 😭 for small bandwidths, lowering the quantum from the default MTU size can be a good move 🫶
unlike plain DRR, there are two sets of flows here: a "new" list for flows that haven't built a queue recently, and an "old" list for queues that build up a backlog 👑 this split is a core part of the FQ-CoDel scheduler and gets a closer look in Section 4 ✨
4. The FQ-CoDel Scheduler 👑
to make its scheduling calls, FQ-CoDel keeps two ordered lists of active queues: new and old 💅 when a packet gets added to a queue that isn't currently active, that queue becomes active by joining the list of new queues 🌈 later on, it moves to the list of old queues, and it gets removed from there once it's no longer active 🦋 this behaviour is where a lot of the subtlety in packet scheduling at dequeue time comes from, as explained below 🙈
4.1. Enqueue 🎀
the packet enqueue mechanism has three stages: classifying into a queue, timestamping and bookkeeping, and optionally dropping a packet when the total number of enqueued packets goes over the maximum 💖
first up, when a packet gets enqueued, it's classified into the right queue. by default, that's done by hashing (with a Jenkins hash function [JENKINS]) on the 5-tuple of IP protocol, source and destination IP addresses, and source and destination port numbers (if they exist). then the hash value gets taken modulo the number of queues 🧚 the hash is salted by modulo addition of a random value picked at initialisation time, to prevent possible DoS attacks if the hash is predictable ahead of time (see Section 8) 🔥 the Linux kernel implements the Jenkins hash by mixing three 32-bit values into a single 32-bit output value. inputs bigger than 96 bits get reduced by extra mixing steps, 96 bits at a time 🌸
once the packet's been successfully classified, it gets handed to the CoDel algorithm for timestamping 🍓 then it's added to the tail of the selected queue, and that queue's byte count goes up by the packet size 💜 next, if the queue isn't currently active (meaning it's in neither the new list nor the old list), it gets added to the end of the new list, and its credits are set to the configured quantum 🦋 otherwise, the queue just stays where it is in its current list ✨
finally, to protect against overload, the total number of enqueued packets gets compared with the configured limit 🚨 if the limit gets exceeded (which can happen right after a packet was enqueued), the queue with the largest current byte count is selected. then half the packets from that queue (up to a max of 64 packets) get dropped from the head of it 😭 dropping several packets at once helps amortise the cost of finding the longest queue, which significantly lowers CPU usage in an overload situation 💅
4.1.1. Alternative Classification Schemes 🌈
like I mentioned before, you can change the classification scheme to get a different notion of a flow 🧚 the Linux implementation gives you this option through the tc filter command 🛠️ this can add some cool capabilities (like matching on other parameters such as MAC address, Diffserv code point values, firewall rules, flow-specific markings, IPv6 flow label, etc.). but be careful to keep the notion of a flow intact, because so much of FQ-CoDel's benefit comes from keeping flows in separate queues 💖
for protocols with no port number (like ICMP), the Linux implementation just sets the port numbers to zero and hashes as usual 🙈 in practice, that means each of these protocols gets its own queue (unless there's a hash collision) 🌸 an implementation can do other classifications for protocols that have their own notion of a flow, but it SHOULD fall back to simply hashing on source and destination IP address and protocol number when there's no other information 🫶
the default classification can also get better by decapsulating tunnelled packets before hashing on the 5-tuple in the encapsulated payload 🎀 the Linux implementation does this for common encapsulations the kernel knows about, like 6in4 [RFC4213], IP-in-IP [RFC2003], and Generic Routing Encapsulation (GRE) [RFC2890] 🦋 this helps tell apart flows that share the same outer 5-tuple, but of course it only works for unencrypted tunnels (see Section 6.2 for the deal with encrypted tunnels) 🔐
4.2. Dequeue 💅✨
Okay bestie, most of FQ-CoDel's heavy lifting happens at dequeue time 🔥. It's basically three steps: picking which queue to pull from, actually dequeueing (with CoDel doing its thing in the middle 🧠), and then some tidy-up bookkeeping 🧹.
Step one: the scheduler checks the list of new queues first 👀. If the queue at the head of that list has a negative number of credits (aka it has already dequeued at least a quantum of bytes), it gets one more quantum of credits and gets shipped to the end of the list of old queues. Then the routine picks the next queue and starts over 🔄.
Otherwise, that queue gets selected for dequeue 🎯. If the new list is empty, the scheduler moves on to the old queues and does the same check. It checks the credits, then either picks the queue for dequeueing or adds credits and puts it back at the end of the line 🙃.
Once a queue is picked, CoDel gets invoked on it 🫶. This runs the CoDel control law, which is the mechanism CoDel uses to decide when to drop packets (see [RFC8289]). Because of this, one or more packets might get tossed from the head of the selected queue before the packet that should be dequeued is returned. Or nothing comes back at all if the queue is or becomes empty while CoDel is handling it 💀.
Last bit: if CoDel doesn't return a packet, then the queue must be empty 😭, and the scheduler does one of two things. If the queue came from the new list, it gets moved to the end of the old list. If it came from the old list instead, it gets removed from the list, to be added back as a new queue the next time a packet arrives that hashes to it 👋. Then, since there was no packet to send, the whole dequeue process restarts from the beginning 🔁.
If CoDel did hand back a packet, the scheduler subtracts that packet's size from the selected queue's byte credits and returns the packet as the result of the dequeue ✅.
The step that moves an empty queue from the new list to the end of the old list before it's removed is absolutely crucial to prevent starvation 🚨. Without it, the queue could reappear (the next time a packet arrives for it) before the old list gets visited. This can go on forever, even with just a few active flows, if the flow feeding the queue sends at just the right rate. Moving the queue to the end of the old list first forces the scheduler to service all the old queues before the empty queue gets removed, and that's what stops starvation 🙌.
The migration of queues between the different states is summarised in the state diagram in Figure 1 📊. Both the new and old queue states can also have arrival and dequeue events that don't change the state, but those are left out of the figure 🙈.
+-----------------+ +------------------+
| | Empty | |
| Empty |<---------------+ Old +----+
| | | | |
+-------+---------+ +------------------+ |
| ^ ^ |Credits
|Arrival | | |Exhausted
v | | |
+-----------------+ | | |
| | Empty or | | |
| New +-------------------+ +-------+
| | Credits Exhausted
+-----------------+Figure 1: Partial State Diagram for Queues between Different States
5. Implementation Considerations 🛠️
This section is all the implementation details for FQ-CoDel 🤓. It covers the data structures and parameters used in the Linux implementation, plus some required features of the target platform and other considerations.
5.1. Data Structures 🧱
The main data structure of FQ-CoDel is the array of queues 📦. It gets instantiated with the number of queues specified by the "flows" parameter at instantiation time. Each queue is basically an ordered list of packets with FIFO semantics, plus two state variables tracking the queue credits and the total number of bytes enqueued, plus the set of CoDel state variables. You can also add other state variables to track queue statistics. For example, the Linux implementation keeps a count of dropped packets 📉.
Besides the queue structures themselves, FQ-CoDel keeps two ordered lists holding references to the subset of queues that are currently active 🫧. These are the lists of new and old queues, as explained in Section 4 above.
In the Linux implementation, queue space is shared. There's a global limit on the number of packets the queues can hold, but no limit for each individual queue 🤝.
5.2. Parameters 🎛️
The following are the user configuration parameters exposed by the Linux implementation of FQ-CoDel ⚙️.
5.2.1. Interval ⏱️
The "interval" parameter has the same semantics as CoDel. It's used to make sure the minimum sojourn time of packets in a queue (the estimator the CoDel control algorithm uses) is a relatively up-to-date value. Basically, CoDel only reacts to delay experienced in the last epoch of length interval ✨. It SHOULD be set to be on the order of the worst-case RTT through the bottleneck, so the end points have enough time to react 🫶.
The default interval value is 100 ms 💜.
5.2.2. Target 🎯
The "target" parameter has the same semantics as CoDel. It's the acceptable minimum standing/persistent queue delay for each FQ-CoDel queue 🌊. That minimum delay is identified by tracking the local minimum queue delay that packets experience.
The default target value is 5 ms 🌸. But this value should be tuned to be at least the transmission time of a single MTU-sized packet at the prevalent egress link speed. For example, that's ~15 ms for 1 Mbps and MTU 1500 📡. This stops CoDel from being too aggressive at low bandwidths. Otherwise, it should be set to 5-10% of the configured interval 💅.
5.2.3. Packet Limit 🧺
Routers do not have infinite memory, so some packet limit MUST be enforced 🚧. Non-negotiable, bestie.
The "limit" parameter is the hard limit on the real queue size, measured in number of packets. This limit is a global limit on the number of packets in all queues. Each individual queue does not have an upper limit 🙅. When the limit is reached and a new packet arrives for enqueue, packets are dropped from the head of the largest queue (measured in bytes) to make room for the new one 🗑️.
In Linux, the default packet limit is 10240 packets, which is suitable for up to 10-Gigabit Ethernet speeds 🚀. In practice, the hard limit is rarely (if ever) hit, because drops happen via the CoDel algorithm long before the limit comes into play 😌. For platforms that are severely memory constrained, a lower limit can be used 🧠.
5.2.4. Quantum 🍰
The "quantum" parameter is the number of bytes each queue gets to dequeue on each round of the scheduling algorithm 🔁. The default is set to 1514 bytes, which is the Ethernet MTU plus the hardware header length of 14 bytes 🧮.
In systems using TCP Segmentation Offload (TSO), where a "packet" is an offloaded packet train, it can presently be as large as 64 kilobytes 📏. In systems using Generic Receive Offload (GRO), they can be up to 17 times the TCP max segment size (or 25 kilobytes). These mega-packets seriously mess with FQ-CoDel's ability to schedule traffic, and they hurt latency for no good reason 😤. There's ongoing work in Linux to make smarter use of offload engines 🛠️.
5.2.5. Flows 🧵
The "flows" parameter sets the number of queues the incoming packets get classified into 🗂️. Because hashing is stochastic, multiple flows may end up hashed into the same slot 🎲.
This parameter can only be set at initialisation time in the current implementation, since memory has to be allocated for the hash table 🧱.
The default value is 1024 in the current Linux implementation 🌈.
5.2.6. Explicit Congestion Notification (ECN) 🚩
ECN [RFC3168] is enabled by default ✅. Rather than doing anything special with misbehaved ECN flows, FQ-CoDel relies on the packet scheduling system to minimise their impact. So the number of unresponsive packets in a flow being marked with ECN can grow to the overall packet limit, but it won't otherwise affect the performance of the system 🫠.
ECN can be disabled by specifying the "noecn" parameter 🙅♀️.
5.2.7. CE Threshold 🌡️
This parameter enables DCTCP-like processing, which results in Congestion Encountered (CE) marking on ECN-Capable Transport (ECT) packets [RFC3168]. It starts at a lower sojourn delay setpoint than the default CoDel target 🔥. Details of Data Center TCP (DCTCP) can be found in [RFC8257] 📚.
The "ce_threshold" parameter is disabled by default. You can enable it by setting it to a number of microseconds ⏰.
5.3. Probability of Hash Collisions 🎰
Since the Linux FQ-CoDel implementation uses 1024 hash buckets by default, the probability that (say) 100 flows will all hash to the same bucket is something like ten to the power of minus 300 🤯. So at least one of the flows will almost certainly hash to some other queue 🫨.
Expanding on this, based on analytical equations for hash collision probabilities, for 100 flows: the probability of no collision is 90.78% ✨. The probability that no more than two of the 100 flows will be involved in any given collision is 99.57% 💖. And the probability that no more than three of the 100 flows will be involved in any given collision is 99.99% 🥹. These probabilities assume a hypothetical perfect hashing function, so in practice they may be a bit lower. We have not found this difference to matter in practice 🤷♀️.
These probabilities can be improved upon by using set-associative hashing 🧩. That's a technique used in the Cake algorithm, which is currently being developed as a further refinement of the FQ-CoDel principles [CAKE]. For a 4-way associative hash with the same total number of queues, the probability of no collisions for 100 flows is 99.93% 👑. For an 8-way associative hash, it's ~100% 🦋.
5.4. Memory Overhead
okay so the good news is that FQ-CoDel can run with a super low memory footprint 💖 (less than 64 bytes per queue on 64-bit systems) 🦋 These are the data structures the Linux implementation uses:
struct codel_vars {
u32 count; /* number of dropped packets */
u32 lastcount; /* count entry to dropping state */
bool dropping; /* currently dropping? */
u16 rec_inv_sqrt; /* reciprocal sqrt computation */
codel_time_t first_above_time; /* when delay above target */
codel_time_t drop_next; /* next time to drop */
codel_time_t ldelay; /* sojourn time of last dequeued packet */
};
struct fq_codel_flow {
struct sk_buff *head;
struct sk_buff *tail;
struct list_head flowchain;
int credits; /* current number of queue credits */
u32 dropped; /* # of drops (or ECN marks) on flow */
struct codel_vars cvars;
};The master table managing all queues looks like this 🧚
struct fq_codel_sched_data {
struct tcf_proto *filter_list; /* optional external classifier */
struct fq_codel_flow *flows; /* Flows table [flows_cnt] */
u32 *backlogs; /* backlog table [flows_cnt] */
u32 flows_cnt; /* number of flows */
u32 perturbation; /* hash perturbation */
u32 quantum; /* psched_mtu(qdisc_dev(sch)); */
struct codel_params cparams;
struct codel_stats cstats;
u32 drop_overlimit;
u32 new_flow_count;
struct list_head new_flows; /* list of new flows */
struct list_head old_flows; /* list of old flows */
};5.5. Per-Packet Timestamping
okay, timestamps 🕰️ So the CoDel part of the algorithm needs per-packet timestamps stored right alongside each packet. This works really well for software-based routers ✨ but it may be impossible to retrofit devices that do most of their processing in silicon and don't have the space or mechanism for timestamping. not ideal, bestie 😭
Also, perfect resolution is not needed, but timestamp resolution finer than the CoDel target setting is necessary 🎯 And the timestamping functions in the core OS need to be efficient, because they get called at least once on every packet enqueue and dequeue. so no slacking here 💅
5.6. Limiting Queueing in Lower Layers
when you deploy a queue management algorithm like FQ-CoDel, it is super important that the algorithm actually runs in the right place to control the queue 👑 The thing is, lower layers of the OS networking stack can have queues of their own, and so can device drivers and hardware. So it's desirable for the queue management algorithm to run as close to the hardware as possible 🔥 However, scheduling that much complexity at interrupt time is really hard, so a small standing queue between the algorithm and the wire is often needed at higher transmit rates. it's a balancing act, iykyk 🫶
In Linux, the mechanism that balances these different needs is called "Byte Queue Limits" [BQL] 🌸 It controls the device driver ring buffer (for physical line rates). When that functionality isn't available, the queue can be controlled with a software rate limiter, like Hierarchical Token Bucket [HTB] or Hierarchical Fair-Service Curve [HFSC] 💜 The Cake algorithm [CAKE] has a software rate limiter built right in for this purpose ✨
Other issues with queues at lower layers are described in [CODEL]. go read that one if you want the full tea ☕
5.7. Other Forms of Fair Queueing
so a lot of the scheduling part of FQ-CoDel is derived from DRR and is substantially similar to DRR++ 🎀 Versions based on Stochastic Fair Queueing [SFQ] have also been produced and tested in ns2 🧪 Other forms of fair queueing, like Weighted Fair Queueing [WFQ] or Quick Fair Queueing [QFQ], haven't been thoroughly explored yet. but there's no a priori reason why the round-robin scheduling of FQ-CoDel couldn't be swapped out for something else 🦋
For a comprehensive discussion of fairness queueing algorithms and how they combine with AQM, see [RFC7806] 📚
5.8. Differences between CoDel and FQ-CoDel Behaviour
okay, so CoDel can be applied to a single queue system as a straight AQM 🌈 In that setup it converges towards an "ideal" drop rate (i.e., one that minimises delay while keeping a high link utilisation) and then optimises around that control point. chef's kiss 👌
The scheduling of FQ-CoDel mixes packets from competing flows, which acts to pace bursty flows so they better fill the pipe 🌊 Also, a new flow gets substantial leeway over other flows until CoDel finds an ideal drop rate for it 🍓 However, for a new flow that exceeds the configured quantum, more time passes before all of its data is delivered, because its packets get mixed in with the other queue-building flows too 😭 So FQ-CoDel takes longer (measured in time) to converge towards an ideal drop rate for a given new flow, but it does so within fewer delivered packets from that flow. the math is mathing 🧮
Finally, the flow isolation provided by FQ-CoDel means the CoDel drop mechanism operates on the flows that are actually building queues 🎯 This results in packets being dropped more accurately from the largest flows than when only CoDel is used. Flow isolation also radically improves the transient behaviour of the network when traffic or link characteristics change (e.g., when new flows start up or the link bandwidth changes) ⚡ CoDel by itself can take a while to respond, but FQ-CoDel reacts almost immediately 💨
6. Limitations of Flow Queueing ⚠️
okay bestie, real talk: FQ-CoDel has been shown in many scenarios to offer significant performance gains compared to other queue management strategies 💖 But there are some scenarios where the scheduling algorithm in particular is not a good fit 🙈 This section documents some of the known cases where either the default behaviour may need tweaking, or alternatives to flow queueing should be considered 🧚
6.1. Fairness between Things Other Than Flows
in some parts of the network, enforcing flow-level fairness may not be desirable, or some other form of fairness may matter more 👑 Examples include an ISP that cares more about fairness between customers than between flows, or a hosting or transit provider that wants fairness between connecting Autonomous Systems or networks 🌐 Another issue is that the number of simultaneous flows at a particular link can be too high for flow-based fairness queueing to be effective 🙃
Whatever the reason, in a scenario where fairness between flows isn't desirable, reconfiguring FQ-CoDel to match on a different characteristic can be a way forward 💅 The Linux implementation can use the packet matching mechanism of the "tc" subsystem to use any available packet field to partition packets into virtual queues. For instance, it can match on address or subnet source/destination pairs, application-layer characteristics, etc. 🦋
Also, as commonly deployed today, FQ-CoDel is used with three or more tiers of service classification, based on Diffserv markings: priority, best effort, and background 🎀 Some products do more detailed classification, including deep packet inspection and destination-specific filters to get their desired result 🔍
6.2. Flow Bunching by Opaque Encapsulation
where possible, FQ-CoDel will attempt to decapsulate packets before matching on the header fields for flow hashing 🎁 However, for some encapsulation techniques, most notably encrypted VPNs, this isn't possible 😭 If several flows get bunched into one encapsulated tunnel, FQ-CoDel will see them as one flow. This means they'll share a queue and drop behaviour, so the flows inside the encapsulation won't get the implicit prioritisation of FQ-CoDel, but they will still benefit from the reduced overall queue length from CoDel operating on the queue 💜 Plus, when such an encapsulated bunch competes against other flows, it counts as one flow and isn't assigned a share of the bandwidth based on how many flows are inside the encapsulation 🫠
Depending on the application, this may or may not be desirable behaviour 🤷♀️ If it isn't, changing FQ-CoDel's matching to be non-flow-based (as detailed in the previous subsection above) can be a mitigation 🍓 Going forward, having some mechanism for opaque encapsulations to tell the outer layer which flow a packet belongs to could be a way to mitigate this too ✨ Naturally, care needs to be taken when designing such a mechanism so no new privacy and security issues are raised by exposing information from inside the encapsulation to the outside world 🔐 Keeping the extra information out of band, and dropping it before it hits the network, could be one way to achieve this 🧠
6.3. Low-Priority Congestion Control Algorithms
okay, so in the presence of queue management schemes that limit latency under load, low-priority congestion control algorithms like Low Extra Delay Background Transport (LEDBAT) [RFC6817] (or, in general, algorithms that try to voluntarily use up less than their fair share of bandwidth) experience little added latency when the link is congested 🌙 That means they lack the signal to back off that added latency previously gave them 😵💫 This effect shows up with FQ-CoDel as well as with any effective AQM [GONG2014] 🫠
As such, these delay-based algorithms tend to revert to loss-based congestion control, and they'll consume the fair share of bandwidth afforded to them by the FQ-CoDel scheduler 💀 However, low-priority congestion control mechanisms may be able to take steps to stay low priority. For instance, they can take into account the vastly reduced level of delay afforded by an AQM, or use a coupled approach to observing the behaviour of multiple flows 🌸✨
7. Deployment Status and Future Work ✨
okay so FQ-CoDel is already out in the wild and it's SO iconic 😭 it's been in the Linux kernel since version 3.5 (dropped on the 21st of July, 2012 🎂), and the ce_threshold option showed up in version 4.2 🔥. It's been tested in a bunch of different situations and it's the default queueing discipline in a few mainline Linux distros (at the time of writing that's at least OpenWRT, Arch Linux, and Fedora 🧚). There's also a BSD implementation floating around 🌸. Every trial result has shown FQ-CoDel being a massive upgrade over the old default FIFO queue, so honestly? Go turn it on 💅
Obviously there's always room to level up, and this doc has listed some of the known limitations 🙈 so we really want more research into refining the algorithm and fixing those gaps. The bufferbloat crew already took a swing at this with the Cake queue management scheme [CAKE] 🍓 Here's a (not-complete) list of stuff we think is worth digging into:
- Variations on the flow classification mechanism so it fits different ideas of what a "flow" even is. Like, an ISP might want per-subscriber scheduling 💜, but in other cases several flows can share a 5-tuple, which is exactly what the RTCWEB QoS recommendations [WEBRTC-QOS] show off 🦋
- Interactions between flow queueing and delay-based congestion control algorithms, plus scavenger protocols 🌈
- Other scheduling mechanisms to swap in for the DRR part of the algorithm, e.g., QFQ or WFQ 🎀
- How sensitive the parameters are, most notably the number of queues and the CoDel parameters ⭐
8. Security Considerations 🔐
Okay, real talk, this section is serious but also kind of a plot twist: there are no specific security exposures tied to FQ-CoDel that aren't already present in current FIFO systems 💀 And honestly? Some of the vulnerabilities FIFO systems have get reduced with FQ-CoDel, like simple minded packet floods 🙈 BUT the implementation needs some care to make sure that's actually true. We already covered these in the description above, but we're repeating them here because they're that important 😤
- To stop packets in the new queues from starving the old queues, it's super important that when a queue on the list of new queues empties, it gets moved to the end of the list of old queues 🚨 This is described at the end of Section 4.2.
- To stop an attacker from picking out one specific flow and denial-of-service-ing it, the hash that maps packets to queues should not be predictable 🕵️♀️ So FQ-CoDel salts the hash, as described at the beginning of Section 4.1. The size of the salt and how strong the hash function is are obviously a trade-off between performance and security ⚖️ The Linux implementation uses a 32-bit random value as the salt and a Jenkins hash function 🧂 That makes high throughput possible, and we think it's enough to ward off the most obvious attacks 👑
- Packet fragments without a Layer 4 header can get hashed into different bins than the first fragment, the one with the header intact 😬 That can cause reordering and/or hurt the performance of the flow. Two ways to fix this are keeping state so the fragments get matched to the beginning of the packet, or just putting all the packet fragments (including the first fragment of each fragmented packet) into the same queue 🫶
9. IANA Considerations 📋
This document does not require any IANA actions 🌸 Nothing to see here for the registry folks!
10. References 📚
10.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC7806] Baker, F. and R. Pan, "On Queuing, Marking, and Dropping",
RFC 7806, DOI 10.17487/RFC7806, April 2016,
<https://www.rfc-editor.org/info/rfc7806>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[RFC8289] Nichols, K., Jacobson, V., McGregor, A., Ed., and J.
Iyengar, Ed., "Controlled Delay Active Queue Management",
RFC 8289, DOI 10.17487/RFC8289, January 2018,
<https://www.rfc-editor.org/info/rfc8289>.10.2. Informative References
[BLOAT] Gettys, J. and K. Nichols, "Bufferbloat: Dark Buffers in
the Internet", Communications of the ACM, Volume 55, Issue
1, DOI 10.1145/2063176.2063196, January 2012.
[BLOATWEB] "Bufferbloat", <https://www.bufferbloat.net>.
[BQL] Herbert, T., "bql: Byte Queue Limits", August 2011,
<https://lwn.net/Articles/454378/>.
[CAKE] "Cake - Common Applications Kept Enhanced",
<http://www.bufferbloat.net/projects/codel/wiki/Cake>.
[CODEL] Nichols, K. and V. Jacobson, "Controlling Queue Delay",
ACM Queue, Volume 10, Issue 5,
DOI 10.1145/2208917.2209336, May 2012,
<http://queue.acm.org/detail.cfm?id=2209336>.
[DRR] Shreedhar, M. and G. Varghese, "Efficient Fair Queueing
Using Deficit Round Robin", IEEE/ACM Transactions on
Networking, Volume 4, Issue 3, DOI 10.1109/90.502236, June
1996.
[DRRPP] MacGregor, M. and W. Shi, "Deficits for Bursty Latency-
Critical Flows: DRR++", Proceedings of the IEEE
International Conference on Networks 2000 (ICON 2000),
DOI 10.1109/ICON.2000.875803, September 2000,
<http://ieeexplore.ieee.org/xpls/
abs_all.jsp?arnumber=875803>.
[GONG2014] Gong, Y., Rossi, D., Testa, C., Valenti, S., and D. Taht,
"Fighting the bufferbloat: On the coexistence of AQM and
low priority congestion control", Elsevier Computer
Networks, Volume 65, DOI 10.1016/j.bjp.2014.01.009, June
2014, <https://www.sciencedirect.com/science/article/pii/
S1389128614000188>.
[HFSC] Stoica, I., Zhang, H., and T. Eugene Ng, "A Hierarchical
Fair Service Curve Algorithm for Link-Sharing, Real-Time
and Priority Services", Proceedings of ACM SIGCOMM,
DOI 10.1145/263105.263175, September 1997,
<http://conferences.sigcomm.org/sigcomm/1997/papers/
p011.pdf>.
[HTB] Wikipedia, "Token Bucket: Variations", October 2017,
<https://en.wikipedia.org/w/
index.php?title=Token_bucket&oldid=803574657>.
[JENKINS] Jenkins, B., "A Hash Function for Hash Table Lookup",
<http://www.burtleburtle.net/bob/hash/doobs.html>.
[LINUXSRC] "Linux Kernel Source Tree", <https://git.kernel.org/cgit/l
inux/kernel/git/torvalds/linux.git/tree/net/sched/
sch_fq_codel.c>.
[NS2] "ns-2", December 2014, <http://nsnam.sourceforge.net/wiki/
index.php?title=Main_Page&oldid=8076>.
[NS3] "ns-3", February 2016, <https://www.nsnam.org/mediawiki/
index.php?title=Main_Page&oldid=9883>.
[QFQ] Checconi, F., Rizzo, L., and P. Valente, "QFQ: Efficient
Packet Scheduling with Tight Guarantees", IEEE/ACM
Transactions on Networking (TON), Volume 21, Issue 3, pp.
802-816, DOI 10.1109/TNET.2012.2215881, June 2013,
<http://dl.acm.org/citation.cfm?id=2525552>.
[RFC2003] Perkins, C., "IP Encapsulation within IP", RFC 2003,
DOI 10.17487/RFC2003, October 1996,
<https://www.rfc-editor.org/info/rfc2003>.
[RFC2890] Dommety, G., "Key and Sequence Number Extensions to GRE",
RFC 2890, DOI 10.17487/RFC2890, September 2000,
<https://www.rfc-editor.org/info/rfc2890>.
[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,
<https://www.rfc-editor.org/info/rfc3168>.
[RFC4213] Nordmark, E. and R. Gilligan, "Basic Transition Mechanisms
for IPv6 Hosts and Routers", RFC 4213,
DOI 10.17487/RFC4213, October 2005,
<https://www.rfc-editor.org/info/rfc4213>.
[RFC6817] Shalunov, S., Hazel, G., Iyengar, J., and M. Kuehlewind,
"Low Extra Delay Background Transport (LEDBAT)", RFC 6817,
DOI 10.17487/RFC6817, December 2012,
<https://www.rfc-editor.org/info/rfc6817>.
[RFC8257] Bensley, S., Thaler, D., Balasubramanian, P., Eggert, L.,
and G. Judd, "Data Center TCP (DCTCP): TCP Congestion
Control for Data Centers", RFC 8257, DOI 10.17487/RFC8257,
October 2017, <https://www.rfc-editor.org/info/rfc8257>.
[SFQ] McKenney, P., "Stochastic Fairness Queueing", Proceedings
of IEEE INFOCOM, DOI 10.1109/INFCOM.1990.91316, June 1990,
<http://perso.telecom-
paristech.fr/~bonald/Publications_files/BMO2011.pdf>.
[SQF] Carofiglio, G. and L. Muscariello, "On the Impact of TCP
and Per-Flow Scheduling on Internet Performance", IEEE/ACM
Transactions on Networking, Volume 20, Issue 2,
DOI 10.1109/TNET.2011.2164553, August 2011.
[WEBRTC-QOS]
Jones, P., Dhesikan, S., Jennings, C., and D. Druta, "DSCP
Packet Markings for WebRTC QoS", Work in Progress,
draft-ietf-tsvwg-rtcweb-qos-18, August 2016.
[WFQ] Demers, A., Keshav, S., and S. Shenker, "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://doi.acm.org/10.1145/75247.75248>.Acknowledgements 🫶
Huge thank-yous to Kathie Nichols, Van Jacobson, and everyone in the bufferbloat.net effort 💖 They helped out a ton with developing and testing the algorithm. Also, a big shout-out to Anil Agarwal for helping get the hash collision probabilities in this document right 🧮✨
Authors' Addresses 🦋
Toke Hoeiland-Joergensen
Karlstad University
Dept. of Computer Science
Karlstad 65188
Sweden
Email: toke@toke.dk
Paul McKenney
IBM Linux Technology Center
1385 NW Amberglen Parkway
Hillsboro, OR 97006
United States of America
Email: paulmck@linux.vnet.ibm.com
URI: http://www2.rdrop.com/~paulmck/
Dave Taht
Teklibre
2104 W First street
Apt 2002
FT Myers, FL 33901
United States of America
Email: dave.taht@gmail.com
URI: http://www.teklibre.com/
Jim Gettys
21 Oak Knoll Road
Carlisle, MA 993
United States of America
Email: jg@freedesktop.org
URI: https://en.wikipedia.org/wiki/Jim_Gettys
Eric Dumazet
Google, Inc.
1600 Amphitheatre Pkwy
Mountain View, CA 94043
United States of America
Email: edumazet@gmail.com📦 where this page comes from
- ietf: rfc8290 2018-01
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms