1FQ-PIE(8)                            Linux                           FQ-PIE(8)
2
3
4

NAME

6       FQ-PIE - Flow Queue Proportional Integral controller Enhanced
7
8

SYNOPSIS

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
17

DESCRIPTION

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
26

ALGORITHM

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
34       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
48       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
61       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
64       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
71       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
76

PARAMETERS

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
82
83   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
90
91   target
92       It  is  the  queue delay which the PIE algorithm tries to maintain. The
93       default target delay is 15ms.
94
95
96   tupdate
97       It is the time interval at which the system drop probability is  calcu‐
98       lated.  The default is 15ms.
99
100
101   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
106
107   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
111
112   memory_limit
113       It  is  the  maximum total memory allowed for packets of all flows. The
114       default is 32Mb.
115
116
117   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
122
123   [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
128
129   [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
134
135   [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
140

EXAMPLES

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
153       # 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
163

SEE ALSO

165       tc(8), tc-pie(8), tc-fq_codel(8)
166
167

SOURCES

169       RFC 8033: https://tools.ietf.org/html/rfc8033
170
171

AUTHORS

173       FQ-PIE was implemented by Mohit P. Tahiliani. Please report corrections
174       to the Linux Networking mailing list <netdev@vger.kernel.org>.
175
176
177
178iproute2                        23 January 2020                      FQ-PIE(8)
Impressum