2005-04-16 22:20:36 +00:00
|
|
|
#
|
|
|
|
|
# Makefile for the Linux Traffic Control Unit.
|
|
|
|
|
#
|
|
|
|
|
|
2009-09-06 08:58:51 +00:00
|
|
|
obj-y := sch_generic.o sch_mq.o
|
2005-04-16 22:20:36 +00:00
|
|
|
|
2006-11-10 00:16:21 +00:00
|
|
|
obj-$(CONFIG_NET_SCHED) += sch_api.o sch_blackhole.o
|
2005-04-16 22:20:36 +00:00
|
|
|
obj-$(CONFIG_NET_CLS) += cls_api.o
|
2005-04-25 03:10:16 +00:00
|
|
|
obj-$(CONFIG_NET_CLS_ACT) += act_api.o
|
2006-01-09 06:22:14 +00:00
|
|
|
obj-$(CONFIG_NET_ACT_POLICE) += act_police.o
|
|
|
|
|
obj-$(CONFIG_NET_ACT_GACT) += act_gact.o
|
|
|
|
|
obj-$(CONFIG_NET_ACT_MIRRED) += act_mirred.o
|
|
|
|
|
obj-$(CONFIG_NET_ACT_IPT) += act_ipt.o
|
2007-09-27 19:48:05 +00:00
|
|
|
obj-$(CONFIG_NET_ACT_NAT) += act_nat.o
|
2006-01-09 06:22:14 +00:00
|
|
|
obj-$(CONFIG_NET_ACT_PEDIT) += act_pedit.o
|
|
|
|
|
obj-$(CONFIG_NET_ACT_SIMP) += act_simple.o
|
2008-09-12 23:30:20 +00:00
|
|
|
obj-$(CONFIG_NET_ACT_SKBEDIT) += act_skbedit.o
|
2010-08-18 13:10:35 +00:00
|
|
|
obj-$(CONFIG_NET_ACT_CSUM) += act_csum.o
|
2006-11-10 00:16:21 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_FIFO) += sch_fifo.o
|
2005-04-16 22:20:36 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_CBQ) += sch_cbq.o
|
|
|
|
|
obj-$(CONFIG_NET_SCH_HTB) += sch_htb.o
|
|
|
|
|
obj-$(CONFIG_NET_SCH_HFSC) += sch_hfsc.o
|
|
|
|
|
obj-$(CONFIG_NET_SCH_RED) += sch_red.o
|
|
|
|
|
obj-$(CONFIG_NET_SCH_GRED) += sch_gred.o
|
|
|
|
|
obj-$(CONFIG_NET_SCH_INGRESS) += sch_ingress.o
|
|
|
|
|
obj-$(CONFIG_NET_SCH_DSMARK) += sch_dsmark.o
|
net_sched: SFB flow scheduler
This is the Stochastic Fair Blue scheduler, based on work from :
W. Feng, D. Kandlur, D. Saha, K. Shin. Blue: A New Class of Active Queue
Management Algorithms. U. Michigan CSE-TR-387-99, April 1999.
http://www.thefengs.com/wuchang/blue/CSE-TR-387-99.pdf
This implementation is based on work done by Juliusz Chroboczek
General SFB algorithm can be found in figure 14, page 15:
B[l][n] : L x N array of bins (L levels, N bins per level)
enqueue()
Calculate hash function values h{0}, h{1}, .. h{L-1}
Update bins at each level
for i = 0 to L - 1
if (B[i][h{i}].qlen > bin_size)
B[i][h{i}].p_mark += p_increment;
else if (B[i][h{i}].qlen == 0)
B[i][h{i}].p_mark -= p_decrement;
p_min = min(B[0][h{0}].p_mark ... B[L-1][h{L-1}].p_mark);
if (p_min == 1.0)
ratelimit();
else
mark/drop with probabilty p_min;
I did the adaptation of Juliusz code to meet current kernel standards,
and various changes to address previous comments :
http://thread.gmane.org/gmane.linux.network/90225
http://thread.gmane.org/gmane.linux.network/90375
Default flow classifier is the rxhash introduced by RPS in 2.6.35, but
we can use an external flow classifier if wanted.
tc qdisc add dev $DEV parent 1:11 handle 11: \
est 0.5sec 2sec sfb limit 128
tc filter add dev $DEV protocol ip parent 11: handle 3 \
flow hash keys dst divisor 1024
Notes:
1) SFB default child qdisc is pfifo_fast. It can be changed by another
qdisc but a child qdisc MUST not drop a packet previously queued. This
is because SFB needs to handle a dequeued packet in order to maintain
its virtual queue states. pfifo_head_drop or CHOKe should not be used.
2) ECN is enabled by default, unlike RED/CHOKe/GRED
With help from Patrick McHardy & Andi Kleen
Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
CC: Juliusz Chroboczek <Juliusz.Chroboczek@pps.jussieu.fr>
CC: Stephen Hemminger <shemminger@vyatta.com>
CC: Patrick McHardy <kaber@trash.net>
CC: Andi Kleen <andi@firstfloor.org>
CC: John W. Linville <linville@tuxdriver.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2011-02-23 10:56:17 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_SFB) += sch_sfb.o
|
2005-04-16 22:20:36 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_SFQ) += sch_sfq.o
|
|
|
|
|
obj-$(CONFIG_NET_SCH_TBF) += sch_tbf.o
|
|
|
|
|
obj-$(CONFIG_NET_SCH_TEQL) += sch_teql.o
|
|
|
|
|
obj-$(CONFIG_NET_SCH_PRIO) += sch_prio.o
|
2008-09-12 23:29:34 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_MULTIQ) += sch_multiq.o
|
2005-04-16 22:20:36 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_ATM) += sch_atm.o
|
|
|
|
|
obj-$(CONFIG_NET_SCH_NETEM) += sch_netem.o
|
2008-11-20 12:10:00 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_DRR) += sch_drr.o
|
2012-02-05 13:51:32 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_PLUG) += sch_plug.o
|
2011-01-17 08:06:09 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_MQPRIO) += sch_mqprio.o
|
2011-02-02 15:21:10 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_CHOKE) += sch_choke.o
|
2011-04-04 05:30:58 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_QFQ) += sch_qfq.o
|
codel: Controlled Delay AQM
An implementation of CoDel AQM, from Kathleen Nichols and Van Jacobson.
http://queue.acm.org/detail.cfm?id=2209336
This AQM main input is no longer queue size in bytes or packets, but the
delay packets stay in (FIFO) queue.
As we don't have infinite memory, we still can drop packets in enqueue()
in case of massive load, but mean of CoDel is to drop packets in
dequeue(), using a control law based on two simple parameters :
target : target sojourn time (default 5ms)
interval : width of moving time window (default 100ms)
Based on initial work from Dave Taht.
Refactored to help future codel inclusion as a plugin for other linux
qdisc (FQ_CODEL, ...), like RED.
include/net/codel.h contains codel algorithm as close as possible than
Kathleen reference.
net/sched/sch_codel.c contains the linux qdisc specific glue.
Separate structures permit a memory efficient implementation of fq_codel
(to be sent as a separate work) : Each flow has its own struct
codel_vars.
timestamps are taken at enqueue() time with 1024 ns precision, allowing
a range of 2199 seconds in queue, and 100Gb links support. iproute2 uses
usec as base unit.
Selected packets are dropped, unless ECN is enabled and packets can get
ECN mark instead.
Tested from 2Mb to 10Gb speeds with no particular problems, on ixgbe and
tg3 drivers (BQL enabled).
Usage: tc qdisc ... codel [ limit PACKETS ] [ target TIME ]
[ interval TIME ] [ ecn ]
qdisc codel 10: parent 1:1 limit 2000p target 3.0ms interval 60.0ms ecn
Sent 13347099587 bytes 8815805 pkt (dropped 0, overlimits 0 requeues 0)
rate 202365Kbit 16708pps backlog 113550b 75p requeues 0
count 116 lastcount 98 ldelay 4.3ms dropping drop_next 816us
maxpacket 1514 ecn_mark 84399 drop_overlimit 0
CoDel must be seen as a base module, and should be used keeping in mind
there is still a FIFO queue. So a typical setup will probably need a
hierarchy of several qdiscs and packet classifiers to be able to meet
whatever constraints a user might have.
One possible example would be to use fq_codel, which combines Fair
Queueing and CoDel, in replacement of sfq / sfq_red.
Signed-off-by: Eric Dumazet <edumazet@google.com>
Signed-off-by: Dave Taht <dave.taht@bufferbloat.net>
Cc: Kathleen Nichols <nichols@pollere.com>
Cc: Van Jacobson <van@pollere.net>
Cc: Tom Herbert <therbert@google.com>
Cc: Matt Mathis <mattmathis@google.com>
Cc: Yuchung Cheng <ycheng@google.com>
Cc: Stephen Hemminger <shemminger@vyatta.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2012-05-10 07:51:25 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_CODEL) += sch_codel.o
|
fq_codel: Fair Queue Codel AQM
Fair Queue Codel packet scheduler
Principles :
- Packets are classified (internal classifier or external) on flows.
- This is a Stochastic model (as we use a hash, several flows might
be hashed on same slot)
- Each flow has a CoDel managed queue.
- Flows are linked onto two (Round Robin) lists,
so that new flows have priority on old ones.
- For a given flow, packets are not reordered (CoDel uses a FIFO)
- head drops only.
- ECN capability is on by default.
- Very low memory footprint (64 bytes per flow)
tc qdisc ... fq_codel [ limit PACKETS ] [ flows number ]
[ target TIME ] [ interval TIME ] [ noecn ]
[ quantum BYTES ]
defaults : 1024 flows, 10240 packets limit, quantum : device MTU
target : 5ms (CoDel default)
interval : 100ms (CoDel default)
Impressive results on load :
class htb 1:1 root leaf 10: prio 0 quantum 1514 rate 200000Kbit ceil 200000Kbit burst 1475b/8 mpu 0b overhead 0b cburst 1475b/8 mpu 0b overhead 0b level 0
Sent 43304920109 bytes 33063109 pkt (dropped 0, overlimits 0 requeues 0)
rate 201691Kbit 28595pps backlog 0b 312p requeues 0
lended: 33063109 borrowed: 0 giants: 0
tokens: -912 ctokens: -912
class fq_codel 10:1735 parent 10:
(dropped 1292, overlimits 0 requeues 0)
backlog 15140b 10p requeues 0
deficit 1514 count 1 lastcount 1 ldelay 7.1ms
class fq_codel 10:4524 parent 10:
(dropped 1291, overlimits 0 requeues 0)
backlog 16654b 11p requeues 0
deficit 1514 count 1 lastcount 1 ldelay 7.1ms
class fq_codel 10:4e74 parent 10:
(dropped 1290, overlimits 0 requeues 0)
backlog 6056b 4p requeues 0
deficit 1514 count 1 lastcount 1 ldelay 6.4ms dropping drop_next 92.0ms
class fq_codel 10:628a parent 10:
(dropped 1289, overlimits 0 requeues 0)
backlog 7570b 5p requeues 0
deficit 1514 count 1 lastcount 1 ldelay 5.4ms dropping drop_next 90.9ms
class fq_codel 10:a4b3 parent 10:
(dropped 302, overlimits 0 requeues 0)
backlog 16654b 11p requeues 0
deficit 1514 count 1 lastcount 1 ldelay 7.1ms
class fq_codel 10:c3c2 parent 10:
(dropped 1284, overlimits 0 requeues 0)
backlog 13626b 9p requeues 0
deficit 1514 count 1 lastcount 1 ldelay 5.9ms
class fq_codel 10:d331 parent 10:
(dropped 299, overlimits 0 requeues 0)
backlog 15140b 10p requeues 0
deficit 1514 count 1 lastcount 1 ldelay 7.0ms
class fq_codel 10:d526 parent 10:
(dropped 12160, overlimits 0 requeues 0)
backlog 35870b 211p requeues 0
deficit 1508 count 12160 lastcount 1 ldelay 15.3ms dropping drop_next 247us
class fq_codel 10:e2c6 parent 10:
(dropped 1288, overlimits 0 requeues 0)
backlog 15140b 10p requeues 0
deficit 1514 count 1 lastcount 1 ldelay 7.1ms
class fq_codel 10:eab5 parent 10:
(dropped 1285, overlimits 0 requeues 0)
backlog 16654b 11p requeues 0
deficit 1514 count 1 lastcount 1 ldelay 5.9ms
class fq_codel 10:f220 parent 10:
(dropped 1289, overlimits 0 requeues 0)
backlog 15140b 10p requeues 0
deficit 1514 count 1 lastcount 1 ldelay 7.1ms
qdisc htb 1: root refcnt 6 r2q 10 default 1 direct_packets_stat 0 ver 3.17
Sent 43331086547 bytes 33092812 pkt (dropped 0, overlimits 66063544 requeues 71)
rate 201697Kbit 28602pps backlog 0b 260p requeues 71
qdisc fq_codel 10: parent 1:1 limit 10240p flows 65536 target 5.0ms interval 100.0ms ecn
Sent 43331086547 bytes 33092812 pkt (dropped 949359, overlimits 0 requeues 0)
rate 201697Kbit 28602pps backlog 189352b 260p requeues 0
maxpacket 1514 drop_overlimit 0 new_flow_count 5582 ecn_mark 125593
new_flows_len 0 old_flows_len 11
PING 172.30.42.18 (172.30.42.18) 56(84) bytes of data.
64 bytes from 172.30.42.18: icmp_req=1 ttl=64 time=0.227 ms
64 bytes from 172.30.42.18: icmp_req=2 ttl=64 time=0.165 ms
64 bytes from 172.30.42.18: icmp_req=3 ttl=64 time=0.166 ms
64 bytes from 172.30.42.18: icmp_req=4 ttl=64 time=0.151 ms
64 bytes from 172.30.42.18: icmp_req=5 ttl=64 time=0.164 ms
64 bytes from 172.30.42.18: icmp_req=6 ttl=64 time=0.172 ms
64 bytes from 172.30.42.18: icmp_req=7 ttl=64 time=0.175 ms
64 bytes from 172.30.42.18: icmp_req=8 ttl=64 time=0.183 ms
64 bytes from 172.30.42.18: icmp_req=9 ttl=64 time=0.158 ms
64 bytes from 172.30.42.18: icmp_req=10 ttl=64 time=0.200 ms
10 packets transmitted, 10 received, 0% packet loss, time 8999ms
rtt min/avg/max/mdev = 0.151/0.176/0.227/0.022 ms
Much better than SFQ because of priority given to new flows, and fast
path dirtying less cache lines.
Signed-off-by: Eric Dumazet <edumazet@google.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2012-05-11 09:30:50 +00:00
|
|
|
obj-$(CONFIG_NET_SCH_FQ_CODEL) += sch_fq_codel.o
|
2011-02-02 15:21:10 +00:00
|
|
|
|
2005-04-16 22:20:36 +00:00
|
|
|
obj-$(CONFIG_NET_CLS_U32) += cls_u32.o
|
|
|
|
|
obj-$(CONFIG_NET_CLS_ROUTE4) += cls_route.o
|
|
|
|
|
obj-$(CONFIG_NET_CLS_FW) += cls_fw.o
|
|
|
|
|
obj-$(CONFIG_NET_CLS_RSVP) += cls_rsvp.o
|
|
|
|
|
obj-$(CONFIG_NET_CLS_TCINDEX) += cls_tcindex.o
|
|
|
|
|
obj-$(CONFIG_NET_CLS_RSVP6) += cls_rsvp6.o
|
|
|
|
|
obj-$(CONFIG_NET_CLS_BASIC) += cls_basic.o
|
[NET_SCHED]: Add flow classifier
Add new "flow" classifier, which is meant to extend the SFQ hashing
capabilities without hard-coding new hash functions and also allows
deterministic mappings of keys to classes, replacing some out of tree
iptables patches like IPCLASSIFY (maps IPs to classes), IPMARK (maps
IPs to marks, with fw filters to classes), ...
Some examples:
- Classic SFQ hash:
tc filter add ... flow hash \
keys src,dst,proto,proto-src,proto-dst divisor 1024
- Classic SFQ hash, but using information from conntrack to work properly in
combination with NAT:
tc filter add ... flow hash \
keys nfct-src,nfct-dst,proto,nfct-proto-src,nfct-proto-dst divisor 1024
- Map destination IPs of 192.168.0.0/24 to classids 1-257:
tc filter add ... flow map \
key dst addend -192.168.0.0 divisor 256
- alternatively:
tc filter add ... flow map \
key dst and 0xff
- similar, but reverse ordered:
tc filter add ... flow map \
key dst and 0xff xor 0xff
Perturbation is currently not supported because we can't reliable kill the
timer on destruction.
Signed-off-by: Patrick McHardy <kaber@trash.net>
Signed-off-by: David S. Miller <davem@davemloft.net>
2008-02-01 02:37:42 +00:00
|
|
|
obj-$(CONFIG_NET_CLS_FLOW) += cls_flow.o
|
2008-11-08 06:56:00 +00:00
|
|
|
obj-$(CONFIG_NET_CLS_CGROUP) += cls_cgroup.o
|
2005-04-16 22:20:36 +00:00
|
|
|
obj-$(CONFIG_NET_EMATCH) += ematch.o
|
|
|
|
|
obj-$(CONFIG_NET_EMATCH_CMP) += em_cmp.o
|
|
|
|
|
obj-$(CONFIG_NET_EMATCH_NBYTE) += em_nbyte.o
|
|
|
|
|
obj-$(CONFIG_NET_EMATCH_U32) += em_u32.o
|
|
|
|
|
obj-$(CONFIG_NET_EMATCH_META) += em_meta.o
|
2005-06-24 04:00:58 +00:00
|
|
|
obj-$(CONFIG_NET_EMATCH_TEXT) += em_text.o
|
2012-07-04 03:32:03 +00:00
|
|
|
obj-$(CONFIG_NET_EMATCH_CANID) += em_canid.o
|
2012-07-11 10:56:57 +00:00
|
|
|
obj-$(CONFIG_NET_EMATCH_IPSET) += em_ipset.o
|