3

I am researching rate limiting and encountered those two strategies: leaky bucket and token bucket. After reading several articles these strategies seem the same too me, but all articles are mentioning different pros and cons for those approaches so I must be missing something.

As I understand they use the same algorithm but use different names.

Leaky bucket Token bucket Description
space left number of tokens Size of burst we can handle in this moment
space filled max - number of tokens How much more burst we can accumulate if we did not perform any requests
leak rate refill rate Minimum amount of requests we can handle in time, also how quickly we accumulate burst capability

I don't see any significant difference here. In leaky bucket you count from 0 to max in the other from max to 0 and that's the main difference. Why there are different pros and cons? What I am missing?

Improve this question
3
  • What are those different pros and cons for the two algorithms? Were any of the articles comparing them directly? Commented Jun 6 at 7:59
  • Interesting question. It feels simple, until one tries to actually write the answer. Skimming through a few articles and the explanation of the difference by Wikipedia, the question still remains. Commented Jun 6 at 9:13
  • @BartvanIngenSchenau for example pros: Token bucket: Allows for flexibility in handling bursts of traffic, Leaky bucket: Simple to implement and understand Commented Jun 6 at 9:22

2 Answers 2

Reset to default
4

There are no behavior differences. Moreover, some implementations of leaky bucket and token bucket produce identical outcomes.

Leaky bucket has another interpretation, where bucket may model a queue of network packets or tasks. This model is convenient for cases when each client already needs its own buffer for unrelated reasons. For example, individual buffers would prevent a rogue client from consuming extra space in a shared input queue on a multiport router.

Improve this answer
1
  • Now I see that Leaky bucket is better to explain rate limiting solutions in certain problem spaces like networking. I don't see any reason to compare this algorithms. Commented Jun 11 at 7:58
3

I think the key difference here is that you don't expect the tokens in the token bucket to all be used up.

So imagine you want to limit the rate on your network, Bob is downloading from limewire and eating all the available bandwidth. Andy is complaining because his webpages are slow. Both computers contend for the same bandwidth and it leads to dropped packets and timeouts.

You add two leaky buckets one for each user at 50% max flow. Now they both have half the bandwidth each. The computers adjust to the steady rate and no longer contend. Apps work well but at a slower rate.

But! they are both displeased. Downloads and webpages now take twice as long to load! "I understand that andy needs to use the bandwidth too", say Bob "but once my file downloads I won't need the bandwidth any more and Andy can have it all!"

You change the leaky buckets to token buckets, with the refill rate set at 50% of the total bandwidth . Now if Bob downloads a file it eats up all the tokens and he has a fast download. But.. if he downloads 24/7 the tokens are used up and he'll be limited to the slow 50% download the same as a leaky bucket

Andy's webpages load fast, they never use all the tokens because 90% of the time he is reading the webpage not downloading it.

Charley joins the network. He plays Counter Strike beta 5! although the volume is low the important thing is that its not interrupted.

You add a leaky bucket set at 90% of the traffic put both Andy and Bobs Token buckets as feeds into it. Even if they both max out their connections there is always 10% left for Charley

When they are all using the network at the same time Bob gets a steady 45%, Charley gets a steady 10% and Andy spikes to 45% on load.

Everyone is happy.

With no limiting, Bob would have 99% because he's got multiple aggressive connections, Andy gets slow webpages and Charley shouts "OMG Lag!" every few minutes.

Token Buckets sound superior, why not always use them?

They are, but only if you have the over head to allow the burst traffic in the first place. In our home network example the WAN link acts as a hard limit to the total bandwidth. In effect its a leaky bucket.

If you put in a Token Bucket with too high a refill rate, it won't do anything at all. If you put in too many tokens It won't do anything either.

Your job as the network admin is to make sure that hard bucket never leaks. You build a tree of software buckets of various kinds all feeding into each other to try and make sure that all the applications get nice steady fixed rate streams without having any spare bandwidth left over.

What about spare bandwith?

leaky and token buckets aren't the only way to do things. If you recognise there is free bandwidth it can be apportioned out according to various rules.

Improve this answer
12
  • 1
    That's an outstanding, very clear explanation! Nice example with two users, with two buckets, one per user—when trying to figure it out myself, I somehow convinced myself that it's one bucket for everyone, which doesn't make too much sense, in retrospect. Commented Jun 6 at 12:33
  • If I replace every token bucket in this answer with leaky bucket, nothing changes. Does this mean that there is no difference? Commented Jun 6 at 13:06
  • Also, the example is strange. Why did Bob stop complaining? He still effectively has 50% of bandwidth, even when Andy is offline. The load balancing imlies some kind of shared resource, and I do not see any shared buckets in the example. Commented Jun 6 at 13:10
  • Ah, I see now. If token inflow matches the bandwidth AND tokens round-robin between buckets AND overflow is added to other buckets, then this answer makes sense. But could we add these clarifications to the answer body? It was hard to figure out. Commented Jun 6 at 13:20
  • Still no difference with leaky buckets, because an anolog for them would be total leak adjusted to bandwidth. Commented Jun 6 at 13:32

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.