I've read many times about Linux's token bucket filter (tbf) and still I don't fully understand how I should calculate the burst and latency parameters, shame on me :(

I suppose that a reasonable latency is around 50 ms. OK, but what value should burst take?

The manpage says:

The latter calculation takes into account the size of the bucket, the rate and possibly the peakrate (if set). These two parameters are mutually exclusive.

So, how is latency related to bucket and filter? Is there a formula to calculate it? Or is it simply a matter of, "OK, X bytes of burst and Y seconds of latency is good for me"?

  • 1
    To everyone finding this unclear: tbf is part of the Linux traffic control framework. man tbf or man tc-tbf ought to bring up documentation. – derobert Nov 11 '13 at 17:39
  • 1
    From your edit, it sounds like you need an explanation of what a token bucket filter is, conceptually. I'll add one in to my answer once I'm back in front of a computer (writing this on my phone.) – derobert Nov 11 '13 at 21:42
  • Finally added in the conceptual explanation – derobert Nov 12 '13 at 19:22

From the manpage, the only constraint on burst is that it must be high enough to allow your configured rate: it must be at least rate / HZ. HZ is a kernel configuration parameter; you can figure out what it is on your system by checking your kernel config. E.g., on Debian, you can:

$ egrep '^CONFIG_HZ_[0-9]+' /boot/config-`uname -r`
CONFIG_HZ_250=y

so HZ on my system is 250. To hit a rate of 10mbps, I'd thus need a burst of at least 10,000,000 bits/sec ÷ 250 Hz = 40,000 bits = 5000 bytes. (Note the higher value in the manpage is from when HZ=100 was the default).

But beyond this, burst is also a policy tool. It configures the extent to which you can use less bandwidth now to "save" it for future use. One common thing here is that you may want to allow small downloads (say, a web page) to go very fast, while throttling big downloads. You do this by increasing burst to the size you consider a small download. (Though, you'd often switch to a classfull qdisc like htb, so you can segment out the different traffic types.)

So: you configure burst to be at least large enough to achieve the desired rate. Beyond that, you may increase it further, depending on what you're trying to achieve.

Conceptual Model of a Token Bucket Filter

Token Bucket Filter

A "bucket" is a metaphorical object. Its key properties are that it can hold tokens, and that the number of tokens it can hold is limited—if you attempt to add more, it "overflows" and the extra tokens are lost (just like trying to put too much water in an actual bucket). The size of the bucket is called burst.

In order to actually transmit a packet onto the network, that packet must obtain tokens equal to its size in bytes or mpu (whichever is larger).

There is (or can be) a line (queue) of packets waiting for tokens. This occurs when the bucket is empty, or alternatively has fewer tokens than the size of the packet. There is only so much room on the sidewalk in front of the bucket, and the amount of room (in bytes) is set directly by limit. Alternatively, it can be set indirectly with latency (in an ideal world, the calculation would be rate×latency).

When the kernel wants to send a packet out the filtered interface, it attempts to place the packet at the end of the line. If there isn't any room on the sidewalk, that's unfortunate for the packet, because at the end of the sidewalk is a bottomless pit, and the kernel drops the packet.

The final piece is a token-making machine that adds rate/HZ tokens to the bucket every tick. (This is why your bucket must be at least this large, otherwise some of the newly-minted tokens will be immediately discarded).

  • I thought that burst it's the opposite, that you allow surpass the rate for a moment, that were compensated by a lower rate later to reach the average rate... – sebelk Nov 11 '13 at 21:31
  • @sebelk I'm not sure without RTFS, but it'd work out to the same result, except for the case when tbf is added to an interface that is currently running above the rate. Or not, as you could just say the bucket starts full... – derobert Nov 12 '13 at 19:21
  • @sebelk: That is also true. Lets say we have a bucket of 1000 bytes (burst size) and the token rate is 10 bytes pr. second. So if no packets have arrived for 100 seconds the bucket will be filled. Then the next 1000 bytes of packets that arrive will be transmitted immediately without being queued, aka. a burst in the data rate which can be above the rate of token creation. – Bjarke Freund-Hansen May 11 '15 at 13:23

Another answer to complement derobert's.

Firstly on modern Intel CPU's the manual is out of date. Modern CPU's have high resolution timers, and modern Linux is tick less - literally meaning there are no timer ticks. Thus all those comments making buckets big enough to hold the tokens in one timer are irrelevant. In fact the bucket analogy was only there to help the user understand the interaction between the timer granularity and send speed. Now that Linux has nanosecond timers on modern hardware it loses it's usefulness.

For TBF the burst parameter is the number of bytes that can be sent at unlimited speed before the rate limiting (specified by rate) kicks in. Once rate limiting has kicked in the only way to burst again is to limit your sending to below that rate.

For example, lets say your tbf burst parameter is 10K bytes, and your tbf rate parameter is 2K bytes/second, and you are currently rate limited (ie the burst is exhausted, so you are limited to sending at 2kbps). If you voluntarily reduced the speed you sending at to 1Kbps for 10 seconds, you would accumulate your 10K bytes burst allowance back again (= (2000 [bytes/sec] - 1000 [bytes/sec]) * 10 sec). Keeping it below 1kbps for more than 10sec would have no effect because tbf does not allow you are not allowed to accumulate more than the burst parameter.

If you stopped spending entirely then you would get your burst allowance back again in 5sec (= 100000 [bytes] / 2000 [bytes/sec]).

You don't have to get all your burst allowance back to use it, you can use as much as you have accumulated.

Another way of looking at this is: you are allowed to send burst bytes at unlimited speed, thereafter your long term average speed can never exceed rate. However, because it is a long term average, if you drop below rate you are allowed to catch up by sending at full speed - but even then you are only allowed to send at full for at most burst bytes (and if that doesn't allow you to catch up you can't).

The other wrinkle is TBF has two of these rate limiters, and your traffic has to pass through both. In the second one, the burst parameter is called mtu and, and the rate is called peakrate. You are supposed to use this second one to limit the speed the first one can send it's bursts at. Using this second one is optional, and if you don't use it the bursts are sent at device speed.

Finally, tbf has a limit parameter. If the program persistently sends faster than rate, then packets will build up in the queue. There isn't infinite kernel memory, so limit says how many bytes can build up before the kernel starts discarding packets.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.