FQ-PIE - Flow Queue Proportional Integral controller Enhanced
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 ]
During the enqueue stage, a hashing-based scheme is used, where flows are hashed into a number of buckets with each bucket having its own queue. The number of buckets is configurable, and presently defaults to 1024 in the implementation. The flow hashing is performed on the 5-tuple of source and destination IP addresses, port numbers and IP protocol number. Once the packet has been successfully classified into a queue, it is handed over to the PIE algorithm for enqueuing. It is then added to the tail of the selected queue, and the queue's byte count is updated by the packet size. If the queue is not currently active (i.e., if it is not in either the list of new or the list of old queues) , it is added to the end of the list of new queues, and its number of credits is initiated to the configured quantum. Otherwise, the queue is left in its current queue list.
During the dequeue stage, the scheduler first looks at the list of new queues; for the queue at the head of that list, if that queue has a negative number of credits (i.e., it has already dequeued at least a quantum of bytes), it is given an additional quantum of credits, the queue is put onto the end of the list of old queues, and the routine selects the next queue and starts again. Otherwise, that queue is selected for dequeue again. If the list of new queues is empty, the scheduler proceeds down the list of old queues in the same fashion (checking the credits, and either selecting the queue for dequeuing, or adding credits and putting the queue back at the end of the list). After having selected a queue from which to dequeue a packet, the PIE algorithm is invoked on that queue.
Finally, if the PIE algorithm does not return a packet, then 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 is moved to the end of the list of old queues. If instead it came from the list of old queues, that queue is removed from the list, to be added back (as a new queue) the next time a packet arrives that hashes to that queue. Then (since no packet was available for dequeue), the whole dequeue process is restarted from the beginning.
If, instead, the scheduler did get a packet back from the PIE algorithm, it subtracts the size of the packet from the byte credits for the selected queue and returns the packet as the result of the dequeue operation.
# 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