1FQ-PIE(8) Linux FQ-PIE(8)
2
6 FQ-PIE - Flow Queue Proportional Integral controller Enhanced
7
10 tc qdisc ... fq_pie [ limit PACKETS ] [ flows NUMBER ]
11 [ target TIME ] [ tupdate TIME ]
12 [ alpha NUMBER ] [ beta NUMBER ]
13 [ quantum BYTES ] [ memory_limit BYTES ]
14 [ ecn_prob PERENTAGE ] [ [no]ecn ]
15 [ [no]bytemode ] [ [no_]dq_rate_estimator ]
16
19 FQ-PIE (Flow Queuing with Proportional Integral controller Enhanced) is
20 a queuing discipline that combines Flow Queuing with the PIE AQM
21 scheme. FQ-PIE uses a Jenkins hash function to classify incoming pack‐
22 ets into different flows and is used to provide a fair share of the
23 bandwidth to all the flows using the qdisc. Each such flow is managed
24 by the PIE algorithm.
25
28 The FQ-PIE algorithm consists of two logical parts: the scheduler which
29 selects which queue to dequeue a packet from, and the PIE AQM which
30 works on each of the queues. The major work of FQ-PIE is mostly in the
31 scheduling part. The interaction between the scheduler and the PIE
32 algorithm is straight forward.
33 During the enqueue stage, a hashing-based scheme is used, where flows
35 are hashed into a number of buckets with each bucket having its own
36 queue. The number of buckets is configurable, and presently defaults to
37 1024 in the implementation. The flow hashing is performed on the
38 5-tuple of source and destination IP addresses, port numbers and IP
39 protocol number. Once the packet has been successfully classified into
40 a queue, it is handed over to the PIE algorithm for enqueuing. It is
41 then added to the tail of the selected queue, and the queue's byte
42 count is updated by the packet size. If the queue is not currently
43 active (i.e., if it is not in either the list of new or the list of old
44 queues) , it is added to the end of the list of new queues, and its
45 number of credits is initiated to the configured quantum. Otherwise,
46 the queue is left in its current queue list.
47 During the dequeue stage, the scheduler first looks at the list of new
49 queues; for the queue at the head of that list, if that queue has a
50 negative number of credits (i.e., it has already dequeued at least a
51 quantum of bytes), it is given an additional quantum of credits, the
52 queue is put onto the end of the list of old queues, and the routine
53 selects the next queue and starts again. Otherwise, that queue is
54 selected for dequeue again. If the list of new queues is empty, the
55 scheduler proceeds down the list of old queues in the same fashion
56 (checking the credits, and either selecting the queue for dequeuing, or
57 adding credits and putting the queue back at the end of the list).
58 After having selected a queue from which to dequeue a packet, the PIE
59 algorithm is invoked on that queue.
60 Finally, if the PIE algorithm does not return a packet, then the queue
62 must be empty and the scheduler does one of two things:
63 If the queue selected for dequeue came from the list of new queues, it
65 is moved to the end of the list of old queues. If instead it came from
66 the list of old queues, that queue is removed from the list, to be
67 added back (as a new queue) the next time a packet arrives that hashes
68 to that queue. Then (since no packet was available for dequeue), the
69 whole dequeue process is restarted from the beginning.
70 If, instead, the scheduler did get a packet back from the PIE algo‐
72 rithm, it subtracts the size of the packet from the byte credits for
73 the selected queue and returns the packet as the result of the dequeue
74 operation.
75
78 limit
79 It is the limit on the queue size in packets. Incoming packets are
80 dropped when the limit is reached. The default value is 10240 packets.
81 flows
84 It is the number of flows into which the incoming packets are classi‐
85 fied. Due to the stochastic nature of hashing, multiple flows may end
86 up being hashed into the same slot. Newer flows have priority over
87 older ones. This parameter can be set only at load time since memory
88 has to be allocated for the hash table. The default value is 1024.
89 target
92 It is the queue delay which the PIE algorithm tries to maintain. The
93 default target delay is 15ms.
94 tupdate
97 It is the time interval at which the system drop probability is calcu‐
98 lated. The default is 15ms.
99 alpha
102 beta
103 alpha and beta are parameters chosen to control the drop probability.
104 These should be in the range between 0 and 32.
105 quantum
108 quantum signifies the number of bytes that may be dequeued from a queue
109 before switching to the next queue in the deficit round robin scheme.
110 memory_limit
113 It is the maximum total memory allowed for packets of all flows. The
114 default is 32Mb.
115 ecn_prob
118 It is the drop probability threshold below which packets will be ECN
119 marked instead of getting dropped. The default is 10%. Setting this
120 parameter requires ecn to be enabled.
121 [no]ecn
124 It has the same semantics as pie and can be used to mark packets
125 instead of dropping them. If ecn has been enabled, noecn can be used to
126 turn it off and vice-a-versa.
127 [no]bytemode
130 It is used to scale drop probability proportional to packet size byte‐
131 mode to turn on bytemode, nobytemode to turn off bytemode. By default,
132 bytemode is turned off.
133 [no_]dq_rate_estimator
136 dq_rate_estimator can be used to calculate queue delay using Little's
137 Law, no_dq_rate_estimator can be used to calculate queue delay using
138 timestamp. By default, dq_rate_estimator is turned off.
139
142 # tc qdisc add dev eth0 root fq_pie
143 # tc -s qdisc show dev eth0
144 qdisc fq_pie 8001: root refcnt 2 limit 10240p flows 1024 target 15.0ms
145 tupdate 16.0ms alpha 2 beta 20 quantum 1514b memory_limit 32Mb ecn_prob
146 10
147 Sent 159173586 bytes 105261 pkt (dropped 24, overlimits 0 requeues 0)
148 backlog 75700b 50p requeues 0
149 pkts_in 105311 overlimit 0 overmemory 0 dropped 24 ecn_mark 0
150 new_flow_count 7332 new_flows_len 0 old_flows_len 4 memory_used
151 108800
152 # tc qdisc add dev eth0 root fq_pie dq_rate_estimator
154 # tc -s qdisc show dev eth0
155 qdisc fq_pie 8001: root refcnt 2 limit 10240p flows 1024 target 15.0ms
156 tupdate 16.0ms alpha 2 beta 20 quantum 1514b memory_limit 32Mb ecn_prob
157 10 dq_rate_estimator
158 Sent 8263620 bytes 5550 pkt (dropped 4, overlimits 0 requeues 0)
159 backlog 805448b 532p requeues 0
160 pkts_in 6082 overlimit 0 overmemory 0 dropped 4 ecn_mark 0
161 new_flow_count 94 new_flows_len 0 old_flows_len 8 memory_used 1157632
162
165 tc(8), tc-pie(8), tc-fq_codel(8)
166
169 RFC 8033: https://tools.ietf.org/html/rfc8033
170
173 FQ-PIE was implemented by Mohit P. Tahiliani. Please report corrections
174 to the Linux Networking mailing list <netdev@vger.kernel.org>.
175iproute2 23 January 2020 FQ-PIE(8)