Linux Solutions

Welcome to the tutorial guide. The tutorial guide will provide a user with guidance and instructions on marking packets for Netfilter & iproute.

Please note that Netfilter allows a user to filter packets, or mangle their headers. A special feature is that a user can mark a packet with a number. In order to do this a user can use the –set-mark facility.
A command is provided which can mark all the packets destined for port 25, outgoing mail:
# iptables -A PREROUTING -i eth0 -t mangle -p tcp –dport 25 \
-j MARK –set-mark 1
If a user has multiple connections, one that is fast (and expensive, per megabyte) and one that is slower, but flat fee. It is a good idea that the outgoing mail goes through the cheap route.
A user can see that the packets are marked with a ‘1′. It is now time to instruct the routing policy database to act on this:
# echo 201 mail.out >> /etc/iproute2/rt_tables
# ip rule add fwmark 1 table mail.out
# ip rule ls
0: from all lookup local
32764: from all fwmark 1 lookup mail.out
32766: from all lookup main
32767: from all lookup default
After this a user can generate a route to the slow but cheap link in the mail.out table by running following command:
# /sbin/ip route add default via 195.96.98.253 dev ppp0 table mail.out
Please note that a user can modify the netfilter statement to exclude certain hosts, or he/she can insert a rule with a lower priority that points to the main table for the excepted hosts.
A user can also use this feature to honour TOS bits by marking packets with a different type of service with different numbers, and creating rules to act on that. This way a user can even dedicate, say, an ISDN line to interactive sessions.
A user should be aware that MASQ and SNAT can collide with marking packets. In order to address this issue, it is best to turn off the reverse path filter so that it works properly. If a user wants to mark packets, then he/she should have some of the options enabled in his/her kernel. This is provided below:
IP: advanced router (CONFIG_IP_ADVANCED_ROUTER) [Y/n/?]
IP: policy routing (CONFIG_IP_MULTIPLE_TABLES) [Y/n/?]
IP: use netfilter MARK value as routing key (CONFIG_IP_ROUTE_FWMARK) [Y/n/?]

If you followed this tutorial guide then you would have learnt about marking packets for Netfilter & iproute .

Welcome to the tutorial guide. The guide will provide a user with guidance and instructions on load sharing over multiple interfaces.

Please note that there are several ways of doing this. Let’s start with an easy way which is ‘TEQL’ - “True” (or “trivial”) link equalizer. Like most things having to do with queueing, load sharing goes both ways. Both ends of a link may need to participate for full effect.
Imagine this situation:
+——-+ eth1 +——-+
| |==========| |
‘network 1′ —-| A | | B |—- ‘network 2′
| |==========| |
+——-+ eth2 +——-+
A and B are routers, and for the moment we’ll assume both run Linux. If traffic is going from network 1 to network 2, router A needs to distribute the packets over both links to B. Router B needs to be configured to accept this. Same goes the other way around, when packets go from network 2 to network 1, router B needs to send the packets over both eth1 and eth2.
The distributing part is done by a ‘TEQL’ device, like this:
# tc qdisc add dev eth1 root teql0
# tc qdisc add dev eth2 root teql0
# ip link set dev teql0 up
Please don’t forget the ‘ip link set up’ command. This command should be done on both hosts. The device teql0 is basically a roundrobbin distributor over eth1 and eth2, for sending packets. No data ever comes in over an teql device, that just appears on the ‘raw’ eth1 and eth2.
A user has now only the devices and he/she also need proper routing. A way to do this is to assign a /31 network to both links, and a /31 to the teql0 device as well:
On router A:
# ip addr add dev eth1 10.0.0.0/31
# ip addr add dev eth2 10.0.0.2/31
# ip addr add dev teql0 10.0.0.4/31
On router B:
# ip addr add dev eth1 10.0.0.1/31
# ip addr add dev eth2 10.0.0.3/31
# ip addr add dev teql0 10.0.0.5/31
Router A should now be able to ping 10.0.0.1, 10.0.0.3 and 10.0.0.5 over the 2 real links and the 1 equalized device. Router B should be able to ping 10.0.0.0, 10.0.0.2 and 10.0.0.4 over the links.
If this works, Router A should make 10.0.0.5 its route for reaching network 2, and Router B should make 10.0.0.4 its route for reaching network 1. For the special case where network 1 is your network at home, and network 2 is the Internet, Router A should make 10.0.0.5 its default gateway.

If you followed this tutorial guide then you would have learnt about load sharing over multiple interfaces.

Welcome to the tutorial guide. The guide will provide a user with advise and guidance on CBQ parameters (split & defmap).
Please note that CBQ offers other options, defmap & split.
If a user wants to filter on the Type of Service field only, a special syntax is provided. Whenever the CBQ needs to figure out where a packet needs to be enqueued, it checks if this node is a ’split node’. If so, one of the sub-qdiscs has indicated that it wishes to receive all packets with a certain configured priority, as might be derived from the TOS field, or socket options set by applications.
The packets’ priority bits are and-ed with the defmap field to see if a match exists. In other words, this is a short-hand way of creating a very fast filter, which only matches certain priorities. A defmap of ff (hex) will match everything, a map of 0 nothing. A sample configuration may help make things clearer:
# tc qdisc add dev eth1 root handle 1: cbq bandwidth 10Mbit allot 1514 \
cell 8 avpkt 1000 mpu 64

# tc class add dev eth1 parent 1:0 classid 1:1 cbq bandwidth 10Mbit \
rate 10Mbit allot 1514 cell 8 weight 1Mbit prio 8 maxburst 20 \
avpkt 1000
Standard CBQ preamble. I never get used to the sheer amount of numbers required!
Defmap refers to TC_PRIO bits, which are defined as follows:
TC_PRIO.. Num Corresponds to TOS
————————————————-
BESTEFFORT 0 Maximize Reliablity
FILLER 1 Minimize Cost
BULK 2 Maximize Throughput (0×8)
INTERACTIVE_BULK 4
INTERACTIVE 6 Minimize Delay (0×10)
CONTROL 7
The TC_PRIO.. number corresponds to bits, counted from the right.
Now the interactive and the bulk classes:
# tc class add dev eth1 parent 1:1 classid 1:2 cbq bandwidth 10Mbit \
rate 1Mbit allot 1514 cell 8 weight 100Kbit prio 3 maxburst 20 \
avpkt 1000 split 1:0 defmap c0

# tc class add dev eth1 parent 1:1 classid 1:3 cbq bandwidth 10Mbit \
rate 8Mbit allot 1514 cell 8 weight 800Kbit prio 7 maxburst 20 \
avpkt 1000 split 1:0 defmap 3f
The ’split qdisc’ is 1:0, which is where the choice will be made. C0 is binary for 11000000, 3F for 00111111, so these two together will match everything. The first class matches bits 7 & 6, and thus corresponds to ‘interactive’ and ‘control’ traffic. The second class matches the rest.
Node 1:0 now has a table like this:
priority send to
0 1:3
1 1:3
2 1:3
3 1:3
4 1:3
5 1:3
6 1:2
7 1:2
For additional fun, you can also pass a ‘change mask’, which indicates exactly which priorities you wish to change. You only need to use this if you are running ‘tc class change’. For example, to add best effort traffic to 1:2, a user can run this:
# tc class change dev eth1 classid 1:2 cbq defmap 01/01
The priority map at 1:0 now looks like this:
priority send to
0 1:2
1 1:3
2 1:3
3 1:3
4 1:3
5 1:3
6 1:2
7 1:2
If you followed advise and guidance as provided in this tutorial guide then you would have learnt about CBQ parameters (split & defmap).

Welcome to the tutorial guide. The guide will provide a user with advise and guidance on CBQ classful behaviour.

Please note that CBQ also acts like the PRIO queue in the sense that classes can have differing priorities and that lower priority numbers will be polled before the higher priority ones.
Each time a packet is requested by the hardware layer to be sent out to the network, a weighted round robin process (’WRR’) starts, beginning with the lower-numbered priority classes.
These are then grouped and queried if they have data available. If so, it is returned. After a class has been allowed to dequeue a number of bytes, the next class within that priority is tried.
The following parameters control the WRR process:
allot
When the outer CBQ is asked for a packet to send out on the interface, it will try all inner qdiscs (in the classes) in turn, in order of the ‘priority’ parameter. Each time a class gets its turn, it can only send out a limited amount of data. ‘Allot’ is the base unit of this amount. See the ‘weight’ parameter for more information.
prio
The CBQ can also act like the PRIO device. Inner classes with higher priority are tried first and as long as they have traffic, other classes are not polled for traffic.
weight
Weight helps in the Weighted Round Robin process. Each class gets a chance to send in turn. If you have classes with significantly more bandwidth than other classes, it makes sense to allow them to send more data in one round than the others.
A CBQ adds up all weights under a class, and normalizes them, so you can use arbitrary numbers: only the ratios are important. People have been using ‘rate/10′ as a rule of thumb and it appears to work well. The renormalized weight is multiplied by the ‘allot’ parameter to determine how much data can be sent in one round.

If you followed advise and guidance as provided in this tutorial guide then you would have learnt about the CBQ classful behaviour

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

Please note that CBQ works by making sure that the link is idle just long enough to bring down the real bandwidth to the configured rate. To do so, it calculates the time that should pass between average packets. During operations, the effective idletime is measured using an exponential weighted moving average (EWMA), which considers recent packets to be exponentially more important than past ones. The UNIX loadaverage is calculated in the same way. The calculated idle time is subtracted from the EWMA measured one, the resulting number is called ‘avgidle’. A perfectly loaded link has an avgidle of zero: packets arrive exactly once every calculated interval.

An overloaded link has a negative avgidle and if it gets too negative, CBQ shuts down for a while and is then ‘overlimit’. An idle link might amass a huge avgidle, which would then allow infinite bandwidths after a few hours of silence. To prevent this, avgidle is capped at maxidle.
If overlimit, in theory, the CBQ could throttle itself for exactly the amount of time that was calculated to pass between packets, and then pass one packet, and throttle again. But see the ‘minburst’ parameter below.
These are parameters you can specify in order to configure shaping:
avpkt
Average size of a packet, measured in bytes. Needed for calculating maxidle, which is derived from maxburst, which is specified in packets.
bandwidth
The physical bandwidth of your device, needed for idle time calculations.
cell
The time a packet takes to be transmitted over a device may grow in steps, based on the packet size. An 800 and an 806 size packet may take just as long to send, for example - this sets the granularity. Most often set to ‘8′. Must be an integral power of two.
maxburst
This number of packets is used to calculate maxidle so that when avgidle is at maxidle, this number of average packets can be burst before avgidle drops to 0. Set it higher to be more tolerant of bursts. You can’t set maxidle directly, only via this parameter.
minburst
As mentioned before, CBQ needs to throttle in case of overlimit. The ideal solution is to do so for exactly the calculated idle time, and pass 1 packet. For Unix kernels, however, it is generally hard to schedule events shorter than 10ms, so it is better to throttle for a longer period, and then pass minburst packets in one go, and then sleep minburst times longer.
The time to wait is called the offtime. Higher values of minburst lead to more accurate shaping in the long term, but to bigger bursts at millisecond timescales.
minidle
If avgidle is below 0, we are overlimits and need to wait until avgidle will be big enough to send one packet. To prevent a sudden burst from shutting down the link for a prolonged period of time, avgidle is reset to minidle if it gets too low.
Minidle is specified in negative microseconds, so 10 means that avgidle is capped at -10us.
mpu
Minimum packet size - needed because even a zero size packet is padded to 64 bytes on ethernet, and so takes a certain time to transmit. CBQ needs to know this to accurately calculate the idle time.
rate
Desired rate of traffic leaving this qdisc - this is the ’speed knob’

If you followed this tutorial guide then you would have learnt about CBQ shaping.

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

CBQ is the most complex qdisc available, the most hyped and the least understood. This is because the CBQ algorithm isn’t all that precise and doesn’t really match the way Linux works.
Besides being classful, CBQ is also a shaper and it is in that aspect that it really doesn’t work very well. It should work like this. If a user tries to shape a 10mbit/s connection to 1mbit/s, the link should be idle 90% of the time, but if it isn’t, then a user will need to throttle so that it IS idle 90% of the time.
Please note that it is very difficult task to measure, so CBQ instead derives the idle time from the number of microseconds that elapse between requests from the hardware layer for more data. Combined, this can be used to approximate how full or empty the link is.
This is rather tortuous and doesn’t always arrive at proper results. For example, what if the actual link speed of an interface that is not really able to transmit the full 100mbit/s of data, perhaps because of a badly implemented driver? A PCMCIA network card will also never achieve 100mbit/s because of the way the bus is designed - again, how does a user calculates the idle time?
It can get worse if a user considers not-quite-real network devices like PPP over Ethernet or PPTP over TCP/IP. The effective bandwidth in that case is probably determined by the efficiency of pipes to userspace - which is huge.
People who have done measurements discover that CBQ is not always very accurate and sometimes completely misses the mark.

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

Welcome to the tutorial guide. The guide will provide a user with adivse and guidance on qdisc configuration.
Let’s see if a tree is set up as following:
1: root qdisc
/ | \
/ | \
/ | \
1:1 1:2 1:3 classes
| | |
10: 20: 30: qdiscs qdiscs
sfq tbf sfq
band 0 1 2
Bulk traffic will go to 30:, interactive traffic to 20: or 10:.
Command lines:
# tc qdisc add dev eth0 root handle 1: prio
## This *instantly* creates classes 1:1, 1:2, 1:3

# tc qdisc add dev eth0 parent 1:1 handle 10: sfq
# tc qdisc add dev eth0 parent 1:2 handle 20: tbf rate 20kbit buffer 1600 limit 3000
# tc qdisc add dev eth0 parent 1:3 handle 30: sfq
Now let’s see what has been created:
# tc -s qdisc ls dev eth0
qdisc sfq 30: quantum 1514b
Sent 0 bytes 0 pkts (dropped 0, overlimits 0)

qdisc tbf 20: rate 20Kbit burst 1599b lat 667.6ms
Sent 0 bytes 0 pkts (dropped 0, overlimits 0)

qdisc sfq 10: quantum 1514b
Sent 132 bytes 2 pkts (dropped 0, overlimits 0)

qdisc prio 1: bands 3 priomap 1 2 2 2 1 2 0 0 1 1 1 1 1 1 1 1
Sent 174 bytes 3 pkts (dropped 0, overlimits 0)
As you can see, band 0 has already had some traffic, and one packet was sent while running this command!
A user can do bulk data transfer with a tool that properly sets TOS flags, and take another look:
# scp tc ahu@10.0.0.11:./
ahu@10.0.0.11’s password:
tc 100% |*****************************| 353 KB 00:00
# tc -s qdisc ls dev eth0
qdisc sfq 30: quantum 1514b
Sent 384228 bytes 274 pkts (dropped 0, overlimits 0)

qdisc tbf 20: rate 20Kbit burst 1599b lat 667.6ms
Sent 2640 bytes 20 pkts (dropped 0, overlimits 0)

qdisc sfq 10: quantum 1514b
Sent 2230 bytes 31 pkts (dropped 0, overlimits 0)

qdisc prio 1: bands 3 priomap 1 2 2 2 1 2 0 0 1 1 1 1 1 1 1 1
Sent 389140 bytes 326 pkts (dropped 0, overlimits 0)

A user can view all traffic went to handle 30:, which is the lowest priority band, just as intended. Now to verify that interactive traffic goes to higher bands, we create some interactive traffic:
# tc -s qdisc ls dev eth0
qdisc sfq 30: quantum 1514b
Sent 384228 bytes 274 pkts (dropped 0, overlimits 0)

qdisc tbf 20: rate 20Kbit burst 1599b lat 667.6ms
Sent 2640 bytes 20 pkts (dropped 0, overlimits 0)

qdisc sfq 10: quantum 1514b
Sent 14926 bytes 193 pkts (dropped 0, overlimits 0)

qdisc prio 1: bands 3 priomap 1 2 2 2 1 2 0 0 1 1 1 1 1 1 1 1
Sent 401836 bytes 488 pkts (dropped 0, overlimits 0)
It worked - all additional traffic has gone to 10:, which is our highest priority qdisc. No traffic was sent to the lowest priority, which previously received our entire scp.

If you followed adivse and guidance as provided in this tutorial guide then you would have learnt about qdisc configuration.

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

It is a good idea that a user understand concepts to fully understand complicated configurations. Different words are used with the same meaning. These are provided below with explanations.
Queueing Discipline (qdisc)
An algorithm that manages the queue of a device, either incoming (ingress) or outgoing (egress).
root qdisc
The root qdisc is the qdisc attached to the device.
Classless qdisc
A qdisc with no configurable internal subdivisions.
Classful qdisc
A classful qdisc contains multiple classes. Some of these classes contains a further qdisc, which may again be classful, but need not be. According to the strict definition, pfifo_fast *is* classful, because it contains three bands which are, in fact, classes. However, from the user’s configuration perspective, it is classless as the classes can’t be touched with the tc tool.
Classes
A classful qdisc may have many classes, each of which is internal to the qdisc. A class, in turn, may have several classes added to it. So a class can have a qdisc as parent or an other class. A leaf class is a class with no child classes. This class has 1 qdisc attached to it. This qdisc is responsible to send the data from that class. When you create a class, a fifo qdisc is attached to it. When you add a child class, this qdisc is removed. For a leaf class, this fifo qdisc can be replaced with an other more suitable qdisc. You can even replace this fifo qdisc with a classful qdisc so you can add extra classes.
Classifier
Each classful qdisc needs to determine to which class it needs to send a packet. This is done using the classifier.
Filter
Classification can be performed using filters. A filter contains a number of conditions which if matched, make the filter match.
Scheduling
A qdisc may, with the help of a classifier, decide that some packets need to go out earlier than others. This process is called Scheduling, and is performed for example by the pfifo_fast qdisc mentioned earlier. Scheduling is also called ‘reordering’, but this is confusing.
Shaping
The process of delaying packets before they go out to make traffic confirm to a configured maximum rate. Shaping is performed on egress. Colloquially, dropping packets to slow traffic down is also often called Shaping.
Policing
Delaying or dropping packets in order to make traffic stay below a configured bandwidth. In Linux, policing can only drop a packet and not delay it - there is no ‘ingress queue’.
Work-Conserving
A work-conserving qdisc always delivers a packet if one is available. In other words, it never delays a packet if the network adaptor is ready to send one (in the case of an egress qdisc).
non-Work-Conserving
Some queues, like for example the Token Bucket Filter, may need to hold on to a packet for a certain time in order to limit the bandwidth. This means that they sometimes refuse to pass a packet, even though they have one available.

If you followed this guide then you would have learnt about Linux terminologies

Welcome to the tutorial guide. The guide will provide a user with guidance and instructions on parameters & usage. Please note the parameters that are always available. These are: limit or latency.

limit or latency
Limit is the number of bytes that can be queued waiting for tokens to become available. A user can has an opportunity to specify this the other way around by setting the latency parameter, which specifies the maximum amount of time a packet can sit in the TBF. The latter calculation takes into account the size of the bucket, the rate and possibly the peakrate (if set).
burst/buffer/maxburst
Size of the bucket, in bytes. This is the maximum amount of bytes that tokens can be available for instantaneously. In general, larger shaping rates require a larger buffer. For 10mbit/s on Intel, a user will need at least 10kbyte buffer if the user want to reach his/her configured rate!
If a user’s buffer is too small, packets may be dropped because more tokens arrive per timer tick than fit in his/her bucket.
mpu
A zero-sized packet does not use zero bandwidth. For ethernet, no packet uses less than 64 bytes. The Minimum Packet Unit determines the minimal token usage for a packet.
rate
The speedknob. See remarks above about limits!
If the bucket contains tokens and is allowed to empty, by default it does so at infinite speed. If this is unacceptable, please use the following parameters:
peakrate
If tokens are available, and packets arrive, they are sent out immediately by default, at ‘lightspeed’ so to speak. Please note that this might not be what a user wants if he has a large bucket.
The peakrate can be used to specify how quickly the bucket is allowed to be depleted. If doing everything by the book, this is achieved by releasing a packet, and then wait just long enough, and release the next. We calculated our waits so we send just at peakrate.
However, due to the default 10ms timer resolution of Unix, with 10.000 bits average packets, we are limited to 1mbit/s of peakrate!
mtu/minburst
The 1mbit/s peakrate is not very useful if users regular rate is more than that. A higher peakrate is possible by sending out more packets per timertick, which effectively means that we create a second bucket!
This second bucket defaults to a single packet, which is not a bucket at all.
To calculate the maximum possible peakrate, multiply the configured mtu by 100 (or more correctly, HZ, which is 100 on Intel, 1024 on Alpha).

If you followed adivse and guidance as provided in this tutorial guide then you would have learnt about parameters and their usage.

Welcome to the tutorial guide. The guide will provide a user with advise and guidance on how token bucket filter.

The Token Bucket Filter (TBF) is a simple qdisc that only passes packets arriving at a rate which is not exceeding some administratively set rate, but with the possibility to allow short bursts in excess of this rate.
TBF is very precise, network- and processor friendly. The TBF implementation consists of a buffer (bucket), constantly filled by some virtual pieces of information called tokens, at a specific rate (token rate). The most important parameter of the bucket is its size, that is the number of tokens it can store.
Each arriving token collects one incoming data packet from the data queue and is then deleted from the bucket. Associating this algorithm with the two flows (i.e., token and data), provides a user with three possible scenarios:
• The data arrives in TBF at a rate that’s equal to the rate of incoming tokens. In this case each incoming packet has its matching token and passes the queue without delay.
• The data arrives in TBF at a rate that’s smaller than the token rate. Only a part of the tokens are deleted at output of each data packet that’s sent out the queue, so the tokens accumulate, up to the bucket size. The unused tokens can then be used to send data at a speed that’s exceeding the standard token rate, in case short data bursts occur.
• The data arrives in TBF at a rate bigger than the token rate. This means that the bucket will soon be devoid of tokens, which causes the TBF to throttle itself for a while. This is called an ‘overlimit situation’. If packets keep coming in, packets will start to get dropped.
Please note that the accumulation of tokens will allow a short burst of overlimit data to be still passed without loss, but any lasting overload will cause packets to be constantly delayed, and then dropped. Also note that in the actual implementation, tokens correspond to bytes, not packets.

If you followed advise and guidance as provided in this tutorial guide then you would have learnt about token bucket filter.