Linux Solutions

Welcome to the tutorial guide. The guide will provide a user with guidance and instructions on how to deal with fast massive filtering.

If a user needs thousands of rules because he/she has a lot of clients or computers with different QoS specifications, then a user will note that he/she will note that the kernel spends a lot of time matching all those rules.
By default, all filters reside in one big chain which is matched in descending order of priority. If a user has 1000 rules, then he/she will require 1000 checks. These checks are required in order to determine what to do with a packet.
If a user has 256 chains with four rules then matching will be quicker also, if he/she can divide packets over those 256 chains, so that the right rule will be there.
If a user has 1024 cable modem customers in his/her network, with IP addresses ranging from 1.2.0.0 to 1.2.3.255, and each has to go in another bin, for example ‘lite’, ‘regular’ and ‘premium’. A user will then have 1024 rules like this:
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.0.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.0.1 classid 1:1
…
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.3.254 classid 1:3
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.3.255 classid 1:2
If a user wants to speed up then he can use the last part of the IP address as a hash key and 256 tables will be obtained. The first table will look like as below:
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.0.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.1.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.2.0 classid 1:3
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.3.0 classid 1:2
The next table will start as described below:
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.0.1 classid 1:1
…
In this way, a user will require only four checks.
Please note that configuration is difficult but it is useful by the time a user has many rules. First a user needs to make a filter root, then he/she has to create a table with 256 entries:
# tc filter add dev eth1 parent 1:0 prio 5 protocol ip u32
# tc filter add dev eth1 parent 1:0 prio 5 handle 2: protocol ip u32 divisor 256
A user can now add some rules to entries in the created table:
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
match ip src 1.2.0.123 flowid 1:1
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
match ip src 1.2.1.123 flowid 1:2
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
match ip src 1.2.3.123 flowid 1:3
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
match ip src 1.2.4.123 flowid 1:2

This is entry 123, which contains matches for 1.2.0.123, 1.2.1.123, 1.2.2.123, 1.2.3.123, and sends them to 1:1, 1:2, 1:3 and 1:2 respectively. Please note that a user will need to specifiy the hash bucket in hex, 0×7b is 123.
After that a user will then need to create a ‘hashing filter’ that directs traffic to the right entry in the hashing table:
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 800:: \
match ip src 1.2.0.0/16 \
hashkey mask 0×000000ff at 12 \
link 2:

It is good know what are these numbers. The default hash table is called 800:: and all filtering starts there. Then a user can select the source address, which lives as position 12, 13, 14 and 15 in the IP

A user should note that this is difficult but the good thing about it is that it works in practice and performance is good.
If you have followed this tutorial guide then you would have learnt about dealing with fast massive filtering.

Welcome to the tutorial guide. The guide will provide a user with advise and guidance on filtering commands. Please note that most of the commands presented in this guide will start with this preamble:
# tc filter add dev eth0 parent 1:0 protocol ip prio 1 u32 ..
These are the so called ‘u32′ matches, which can match on ANY part of a packet.
On source/destination address
Source mask ‘match ip src 1.2.3.0/24′, destination mask ‘match ip dst 4.3.2.0/24′. To match a single host, use /32, or omit the mask.
On source/destination port, all IP protocols
Source: ‘match ip sport 80 0xffff’, destination: ‘match ip dport 80 0xffff’
On ip protocol (tcp, udp, icmp, gre, ipsec)
Use the numbers from /etc/protocols, for example, icmp is 1: ‘match ip protocol 1 0xff’.
On fwmark
A user can mark packets with either ipchains or iptables and have that mark survive routing across interfaces. This is really useful to for example only shape traffic on eth1 that came in on eth0. Syntax:
# tc filter add dev eth1 protocol ip parent 1:0 prio 1 handle 6 fw flowid 1:1
Note that this is not a u32 match!
A user can place a mark like this:
# iptables -A PREROUTING -t mangle -i eth0 -j MARK –set-mark 6
The number 6 is arbitrary.
If a user is not interested in understanding the full tc filter syntax, just use iptables, and only learn to select on fwmark.
On the TOS field
To select interactive, minimum delay traffic:
# tc filter add dev ppp0 parent 1:0 protocol ip prio 10 u32 \
match ip tos 0×10 0xff \
flowid 1:4
Use 0×08 0xff for bulk traffic.

If you followed advise and guidance as provided in this tutorial guide then you would have learnt about filtering commands.

Welcome to the tutorial guide. The guide will provide a user with advise and guidance on filtering.
If a user has a PRIO qdisc called ‘10:’ which contains three classes, and he/she wants to assign all traffic from and to port 22 to the highest priority band, the filters would be:
# tc filter add dev eth0 protocol ip parent 10: prio 1 u32 match \
ip dport 22 0xffff flowid 10:1
# tc filter add dev eth0 protocol ip parent 10: prio 1 u32 match \
ip sport 80 0xffff flowid 10:1
# tc filter add dev eth0 protocol ip parent 10: prio 2 flowid 10:2
Let’s see what does this mean. It means that: attach to eth0, node 10: a priority 1 u32 filter that matches on IP destination port 22 *exactly* and send it to band 10:1. And it then repeats the same for source port 80. The last command says that anything unmatched so far should go to band 10:2, the next-highest priority.
A user needs to add ‘eth0′, or whatever his/her interface is called, because each interface has a unique namespace of handles.
If a user wants to select on an IP address, thene he/she needs to use this:
# tc filter add dev eth0 parent 10:0 protocol ip prio 1 u32 \
match ip dst 4.3.2.1/32 flowid 10:1
# tc filter add dev eth0 parent 10:0 protocol ip prio 1 u32 \
match ip src 1.2.3.4/32 flowid 10:1
# tc filter add dev eth0 protocol ip parent 10: prio 2 \
flowid 10:2
This assigns traffic to 4.3.2.1 and traffic from 1.2.3.4 to the highest priority queue, and the rest to the next-highest one.
A user can concatenate matches, to match on traffic from 1.2.3.4 and from port 80, do this:
# tc filter add dev eth0 parent 10:0 protocol ip prio 1 u32 match ip src 4.3.2.1/32 \
match ip sport 80 0xffff flowid 10:1.

If a user followed advise and guidance as provided in this tutorial guide then he/she learnt about filtering.

Welcome to the tutorial guide. The guide will provide a user with advise and guidance on how to police the filters.

If a user wants to police at 4mbit/s, but 5mbit/s of traffic is present, then he or she can stop matching either the entire 5mbit/s, or only not match 1mbit/s, and do send 4mbit/s to the configured class.
If bandwidth exceeds the configured rate, then a user can drop a packet, reclassify it, or see if another filter will match it.
There are two different ways to police the filter. For example, if a user compiled the kernel with Estimators, the kernel can measure for each filter how much traffic it is passing, more or less. These estimators are very easy on the CPU, as they simply count 25 times per second how many data has been passed, and calculate the bitrate from that.
The other way for policing the filter is through a Token Bucket Filter, this time living within his/her filter. Please note that the TBF only matches traffic up to a users configured bandwidth, if more is offered, only the excess is subject to the configured overlimit action.
Policing with kernel estimator
This is very simple and has only one parameter: avrate. Either the flow remains below avrate, and the filter classifies the traffic to the classid configured, or a users rate exceeds it in which case the specified action is taken, which is reclassify by default.
The kernel uses an Exponential Weighted Moving Average for the bandwidth which makes it less sensitive to short bursts.
Policing with Token Bucket Filter
A user has a choice to use the following parameters:
• burst/buffer/maxburst
• mtu/minburst
• mpu
• rate
A user should be aware that if he/she sets the mtu of a TBF policer too low then no packets will pass, whereas the egress TBF qdisc will just pass them slower.

Overlimit actions
If a users filter decides that it is overlimit, it can take actions. Currently, four actions are available:
continue
Causes this filter not to match, but perhaps other filters will.
drop
This is a very fierce option which simply discards traffic exceeding a certain rate. It is often used in the ingress policer and has limited uses.
Pass/OK
Pass on traffic ok. Might be used to disable a complicated filter, but leave it in place.
reclassify
Most often comes down to reclassification to Best Effort. This is the default action.
Please have a look at this example:
Limit incoming icmp traffic to 2kbit, drop packets over the limit:
tc filter add dev $DEV parent ffff: \
protocol ip prio 20 \
u32 match ip protocol 1 0xff \
police rate 2kbit buffer 10k drop \
flowid :1
Limit packets to a certain size (i.e. all packets with a length greater than 84 bytes will get dropped):
tc filter add dev $DEV parent ffff: \
protocol ip prio 20 \
u32 match tos 0 0 \
police mtu 84 drop \
flowid :1
This method can be used to drop all packets:
tc filter add dev $DEV parent ffff: \
protocol ip prio 20 \
u32 match ip protocol 1 0xff \
police mtu 1 drop \
flowid :1
It actually drops icmp packets greater-than 1 byte. While packets with a size of 1 byte are possible in theory, a user will not find these in a real network.
If you followed this tutorial guide then you would have learnt about policing the filters.

Welcome to the tutorial guide. The tutorial guide will provide a user with guidance and instructions about the route classifier.

Please note that the route classifier filters based on the results of the routing tables. When a packet that is traversing through the classes reaches one that is marked with the “route” filter, it splits the packets up based on information in the routing table.
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 route
A user can add a route classifier onto the parent node 1:0 with priority 100 as you can see in the mentioned example. When a packet reaches this node, it will consult the routing table. If the packet matches, it will be send to the given class and have a priority of 100. Please note that in order to action this a user needs to add the appropriate routing entry:
A user can define the realm based on either destination or source. It is easy to do it like this:
# ip route add Host/Network via Gateway dev Device realm RealmNumber
If a user wants to define the destination network 192.168.10.0 with a realm number 10, then it an be done as shown below:
# ip route add 192.168.10.0/24 via 192.168.10.1 dev eth1 realm 10
When adding route filters, a user can use realm numbers to represent the networks or hosts and specify how the routes match the filters.
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 \
route to 10 classid 1:10
This rule matches the packets going to the network 192.168.10.0.
Please note that a route filter can be used to match source routes. For example, there is a subnetwork attached to the Linux router on eth2.
# ip route add 192.168.2.0/24 dev eth2 realm 2
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 \
route from 2 classid 1:2
In this case the filter specifies that packets from the subnetwork 192.168.2.0 (realm 2) will match class id 1:2.
If you followed advise and guidance as provided in this tutorial guide then you would have learnt about the route classifier.

Welcome to the tutorial guide. The tutorial guide will provide a user with advise and guidance on specific selectors.

If a user wants to increase the readability of his/her filter’s configuration then it is a good idea to have a look at a list of specific selectors in the tc program source code.
FIXME: table placeholder - the table is in separate file ,,selector.html”
FIXME: it’s also still in Polish
FIXME: must be sgml’ized
Some examples:
# tc filter add dev ppp0 parent 1:0 prio 10 u32 \
match ip tos 0×10 0xff \
flowid 1:4
FIXME: tcp dport match does not work as described below:
Please note that the rule will match packets which have the TOS field set to 0×10. The TOS field starts at second byte of the packet and is one byte big. A user can write an equivalent general selector: match u8 0×10 0xff at 1. It is good to know that the tcp and udp selectors are exactly the same and single match tcp dport 53 0xffff selector can not be used to match TCP packets sent to given port — they will also match UDP packets sent to this port. It is good to remember that a user should also specify the protocol and end up with the following rule:
# tc filter add dev ppp0 parent 1:0 prio 10 u32 \
match tcp dport 53 0xffff \
match ip protocol 0×6 0xff \
flowid 1:2

If you followed the tutorial guide then you would have learnt about the specific selectors.

Welcome to the tutorial guide. The guide will provide a user with guidance and instructions on general selectors.

Please note that the general selectors define the pattern, mask and offset the pattern will be matched to the packet contents. By using the general selectors a user can match virtually any single bit in the IP (or upper layer) header. The general selector syntax is:
match [ u32 | u16 | u8 ] PATTERN MASK [ at OFFSET | nexthdr+OFFSET]
One of the keywords u32, u16 or u8 specifies length of the pattern in bits. PATTERN and MASK should follow, of length defined by the previous keyword. The OFFSET parameter is the offset, in bytes, to start matching. If nexthdr+ keyword is given, the offset is relative to start of the upper layer header.
Here are some examples presented below:
Packet will match to this rule, if its time to live (TTL) is 64. TTL is the field starting just after 8-th byte of the IP header.
# tc filter add dev ppp14 parent 1:0 prio 10 u32 \
match u8 64 0xff at 8 \
flowid 1:4
The following matches all TCP packets which have the ACK bit set:
# tc filter add dev ppp14 parent 1:0 prio 10 u32 \
match ip protocol 6 0xff \
match u8 0×10 0xff at nexthdr+13 \
flowid 1:3
Use this to match ACKs on packets smaller than 64 bytes:
## match acks the hard way,
## IP protocol 6,
## IP header length 0×5(32 bit words),
## IP Total length 0×34 (ACK + 12 bytes of TCP options)
## TCP ack set (bit 5, offset 33)
# tc filter add dev ppp14 parent 1:0 protocol ip prio 10 u32 \
match ip protocol 6 0xff \
match u8 0×05 0×0f at 0 \
match u16 0×0000 0xffc0 at 2 \
match u8 0×10 0xff at 33 \
flowid 1:3
This rule will only match TCP packets with ACK bit set, and no further payload. The example shows an example of two selectors. The diagram shows that the ACK bit is second older bit (0×10) in the 14-th byte of the TCP header (at nexthdr+13). For the second selector, a user could write match u8 0×06 0xff at 9 instead of using the specific selector protocol tcp, because 6 is the number of TCP protocol, present in 10-th byte of the IP header. A user couldn’t use any specific selector for the first match. This is because there is no specific selector to match TCP ACK bits.
A filter is provided below which is a modified version of the filter above. The difference is, that it doesn’t check the ip header length. This is because the filter above does only work on 32 bit systems.
tc filter add dev ppp14 parent 1:0 protocol ip prio 10 u32 \
match ip protocol 6 0xff \
match u8 0×10 0xff at nexthdr+13 \
match u16 0×0000 0xffc0 at 2 \
flowid 1:3

If you followed advise and guidance as provided in this tutorial guide then you would have learnt about the general selectors.

Welcome to the tutorial guide. The guide will provide a user with guidance and instructions on U32 selector.
Before proceeding further, it is a good idea to know what is U32 selector. The U32 selector defines which bits are to be matched in the packet header

It is a good idea to have a look at an examplye as provided below:
# tc filter add dev eth0 protocol ip parent 1:0 pref 10 u32 \
match u32 00100000 00ff0000 at 0 flowid 1:10
Please note that after leaving the first line, all the parameters explain the filter’s hash tables. If a user focuses on the selector line which contains the match keyword. This selector will match to IP headers, whose second byte will be 0×10 (0010). The 00ff number is the match mask, telling the filter exactly which bits to match. Here it’s 0xff, so the byte will match if it’s exactly 0×10. The at keyword means that the match is to be started at specified offset (in bytes) in this case it’s beginning of the packet. Translating all that to human language, the packet will match if its Type of Service field will have `low delay’ bits set. It is a good ideas to have a look at another rule which is:
# tc filter add dev eth0 protocol ip parent 1:0 pref 10 u32 \
match u32 00000016 0000ffff at nexthdr+0 flowid 1:10
The nexthdr option means next header encapsulated in the IP packet, i.e. header of upper-layer protocol. The match will also start here at the beginning of the next header. The match should occur in the second, 32-bit word of the header. In TCP and UDP protocols this field contains packet’s destination port. The number is given in big-endian format, i.e. older bits first, so we simply read 0×0016 as 22 decimal, which stands for SSH service if this was TCP.
If a user has read all the mentioned information then he/she will find the selector easy to read: match c0a80100 ffffff00 at 16. This is a three byte match at 17-th byte, counting from the IP header start. This will match for packets with destination address anywhere in 192.168.1/24 network.
If you followed the tutorial guide then you would have learnt about U32 selector.

Welcome to the tutorial guide. The tutorial guide will provide a user with advise and guidance on u32 classifier. Please note that the U32 filter is the most advanced filter available in the current implementation. It is entirely based on hashing tables, which make it robust when there are many filter rules.

It is good to know what a u32 classifier is. It is a list of records, each consisting of two fields: a selector and an action. The selectors, described below, are compared with the currently processed IP packet until the first match occurs, and then the associated action is performed. The simplest type of action would be directing the packet into defined class.
A user should know that the command line of tc filter program, used to configure the filter, consists of three parts: filter specification, a selector and an action. The filter specification can be defined as:
tc filter add dev IF [ protocol PROTO ]
[ (preference|priority) PRIO ]
[ parent CBQ ]
The protocol field describes protocol that the filter will be applied to. We will only discuss case of ip protocol. The preference field (priority can be used alternatively) sets the priority of currently defined filter. Each list will be passed in the order the rules were added, then list with lower priority (higher preference number) will be processed. The parent field defines the CBQ tree top (e.g. 1:0), the filter should be attached to.

If you followed advise and guidance as provided in this tutorial guide then you would have learnt about u32 classifier.

Welcome to the tutorial guide. The guide will provide a user with advise and guidance on advanced filters for re-classifying packets. Please note that filters are a requirement in order to classify packets into any of the sub-queues. These filters are called from within the classful qdisc.
A list of classifiers is provided below:
fw
This bases the decision on how the firewall has marked the packet
u32
This bases the decision on fields within the packet (i.e. source IP address, etc)
route
This bases the decision on which route the packet will be routed by
rsvp, rsvp6
These routes packet are based on rsvp and are useful on networks that a user controls - the Internet does not respect RSVP.
tcindex
This is used in the DSMARK qdisc, see the relevant section.
There are few arguments which classifiers accept. These arguments are provided below:
protocol
The protocol this classifier will accept.
parent
The handle this classifier is to be attached to. This handle must be an already existing class. Required.
prio
The priority of this classifier. Lower numbers get tested first.
handle
This handle means different things to different filters.

If you followed this tutorial guide then you would have learnt about the advanced filters for re-classifying packets