FQ-PIE(8)

🎀 FQ-PIE(8) 🎀

✨ NAME ✨

FQ-PIE, aka Flow Queue Proportional Integral controller Enhanced 💖

🧚 SYNOPSIS 🧚

tc qdisc ... fq_pie [ limit PACKETS ] [ flows NUMBER ]
                    [ target TIME ] [ tupdate TIME ]
                    [ alpha NUMBER ] [ beta NUMBER ]
                    [ quantum BYTES ] [ memory_limit BYTES ]
                    [ ecn_prob PERENTAGE ] [ [no]ecn ]
                    [ [no]bytemode ] [ [no_]dq_rate_estimator ]

🌸 DESCRIPTION 🌸

okay so FQ-PIE (Flow Queuing with Proportional Integral controller Enhanced) is a queuing discipline that mashes together Flow Queuing and the PIE AQM scheme, and it's honestly so iconic ✨ It uses a Jenkins hash function to sort incoming packets into different flows, which gives every flow a fair share of the bandwidth through the qdisc. Each flow then gets managed by the PIE algorithm 💅

🦋 ALGORITHM 🦋

ngl this part is where the magic happens. The FQ-PIE algorithm has two logical parts: the scheduler, which decides which queue to dequeue a packet from, and the PIE AQM, which works on each of the queues. Most of the heavy lifting is in the scheduler. The way the scheduler and PIE talk to each other is pretty straightforward 🫶

During the enqueue stage, a hashing-based scheme is used, so flows get hashed into a bunch of buckets, and every bucket has its own queue. The number of buckets is configurable and currently defaults to 1024 in the implementation. The flow hashing is done on the 5-tuple of source and destination IP addresses, port numbers, and IP protocol number. Once a packet is successfully classified into a queue, it gets handed to the PIE algorithm for enqueuing. Then it's added to the tail of the selected queue, and that queue's byte count goes up by the packet size. If the queue isn't active right now (meaning it's not in either the list of new queues or the list of old queues) , it gets added to the end of the list of new queues, and its credits are set to the configured quantum. Otherwise, the queue just stays in whatever list it's already in 🌈

During the dequeue stage, the scheduler looks at the list of new queues first. For the queue at the head of that list, if it has a negative number of credits (aka it has already dequeued at least a quantum of bytes), it gets an extra quantum of credits, gets put on the end of the list of old queues, and the routine picks the next queue and starts over. Otherwise, that queue is selected for dequeue again. If the list of new queues is empty, the scheduler goes down the list of old queues in the same way, checking credits and either selecting the queue for dequeuing or adding credits and sending the queue back to the end of the list. Once a queue has been selected for dequeuing a packet, the PIE algorithm gets invoked on that queue ✨

Finally, if the PIE algorithm doesn't return a packet, the queue must be empty, and the scheduler does one of two things:

If the queue selected for dequeue came from the list of new queues, it gets moved to the end of the list of old queues. If it came from the list of old queues instead, it gets removed from the list, and it'll be added back (as a new queue) the next time a packet arrives that hashes to that queue. Then, since no packet was available, the whole dequeue process restarts from the beginning 🙈

If the scheduler did get a packet back from the PIE algorithm, it subtracts the packet's size from the byte credits for the selected queue and returns the packet as the result of the dequeue operation 💖

👑 PARAMETERS 👑

✨ limit ✨

This is the limit on the queue size, counted in packets. Incoming packets get dropped once the limit is hit. The default is 10240 packets.

✨ flows ✨

This is how many flows the incoming packets get sorted into. Because hashing is kinda random, multiple flows can end up hashed into the same slot. Newer flows get priority over older ones. This one can only be set at load time, since memory has to be allocated for the hash table. The default is 1024.

✨ target ✨

This is the queue delay that the PIE algorithm tries to keep things at. The default target delay is 15ms.

✨ tupdate ✨

This is the time interval at which the system drop probability gets calculated. The default is 15ms.

✨ alpha ✨ and ✨ beta ✨

alpha and beta are parameters that control the drop probability. They should be somewhere in the range between 0 and 32 🎀

✨ quantum ✨

quantum is the number of bytes that can be dequeued from a queue before the scheduler switches to the next queue in the deficit round robin scheme 🍓

✨ memory_limit ✨

This is the maximum total memory allowed for packets across all flows. The default is 32Mb.

✨ ecn_prob ✨

This is the drop probability threshold below which packets get ECN marked instead of dropped. The default is 10%. Setting this parameter requires ecn to be enabled.

✨ [no]ecn ✨

This has the same semantics as pie and can be used to mark packets instead of dropping them. If ecn has been enabled, noecn can be used to turn it off, and vice versa 🦋

✨ [no]bytemode ✨

This is used to scale the drop probability in proportion to packet size. bytemode turns bytemode on, and nobytemode turns it off. By default, bytemode is turned off.

✨ [no_]dq_rate_estimator ✨

dq_rate_estimator calculates queue delay using Little's Law, and no_dq_rate_estimator calculates queue delay using timestamps instead. By default, dq_rate_estimator is turned off 💜

🌈 EXAMPLES 🌈

# tc qdisc add dev eth0 root fq_pie
# tc -s qdisc show dev eth0
qdisc fq_pie 8001: root refcnt 2 limit 10240p flows 1024 target 15.0ms
tupdate 16.0ms alpha 2 beta 20 quantum 1514b memory_limit 32Mb ecn_prob
10
 Sent 159173586 bytes 105261 pkt (dropped 24, overlimits 0 requeues 0)
 backlog 75700b 50p requeues 0
  pkts_in 105311 overlimit 0 overmemory 0 dropped 24 ecn_mark 0
  new_flow_count 7332 new_flows_len 0 old_flows_len 4 memory_used 108800

# tc qdisc add dev eth0 root fq_pie dq_rate_estimator
# tc -s qdisc show dev eth0
qdisc fq_pie 8001: root refcnt 2 limit 10240p flows 1024 target 15.0ms
tupdate 16.0ms alpha 2 beta 20 quantum 1514b memory_limit 32Mb ecn_prob
10 dq_rate_estimator
 Sent 8263620 bytes 5550 pkt (dropped 4, overlimits 0 requeues 0)
 backlog 805448b 532p requeues 0
  pkts_in 6082 overlimit 0 overmemory 0 dropped 4 ecn_mark 0
  new_flow_count 94 new_flows_len 0 old_flows_len 8 memory_used 1157632

🫧 SEE ALSO 🫧

tc(8), tc-pie(8), tc-fq_codel(8)

📚 SOURCES 📚

RFC 8033: https://tools.ietf.org/html/rfc8033

💅 AUTHORS 💅

FQ-PIE was implemented by Mohit P. Tahiliani. Corrections go to the Linux Networking mailing list <netdev@vger.kernel.org>, so send them there 🫶

bye bestie 💖 that's the whole page, served from iproute2, dated 23 January 2020, filed under FQ-PIE(8) ✨🌸