Token bucket vs Fixed window (Traffic Burst)

Question

I was comparing Token bucket and Fixed window rate limiting algorithm, But a bit confused with traffic bursts in both algorithm.

Let's say i want to limit traffic to 10 requests/minute.

In Token bucket, tokens are added at the rate of 10 tokens per minute.

 Time      Requests AvailableTokens
10:00:00     0          10 (added 10 tokens)
10:00:58    10          0
10:01:00     0          10 (added 10 tokens)
10:01:01    10          0 

Now if we see at timestamp 10:01:01, in last minute 20 requests were allowed, more than our limit.

Similarly, With Fixed window algorithms. Window size: 1 minute.

 Window    RequestCount IncomingRequests
10:00:00      10         10 req at 10:00:58
10:01:00      10         10 req at 10:01:01

Similar problem is here as well.

Does both the algorithms suffer from this problem, or is there a gap in my understanding?

Codee

This here here should answer most of your question and it is much more detailed than an answer here could be. In short, in the Token bucket, the abovementioned scenario should not happen/can be prevented, although there are other issues. In the fixed window case, the double-the-rate issue can happen exactly the way you have described so to remove this possibility you would need to set the rate to N/2 where N is the maximum rate you want. – Aliaalias

I went through this link before but couldn't find answer to my concern. What my understanding is to prevent this problem in token bucket, We would have to optimize the bucket size, as it defines the max burst traffic can be served. But this would be similar to reducing the rate from N to N/2 in fixed window. – Codee

@shamis the link you gave implements token bucket with the notion of timestamp, so it includes some form of sliding window approach which does not apply in this question with the vanilla token bucket approach. – Georginegeorglana

I think in the standard way of implementing token bucket we refill as a first step when we get a new request. We do not refill at fixed interval. Instead, we refill based on time elapsed since last refill. So we do not add tokens at 10:01:00 and at 10:01:01 we would add for 3 second elapsed since last refill adding 10 * (3 / 60) = 0.5 tokens. – Wyndham

Answer 1

I had the same confusion about those algorithms.

The trick with the Token Bucket is that Bucket size(b) and Refill rate(r) don't have to be equal.

For your particular example, you could set Bucket size to be b = 5 and refill rate r = 1/10 (1 token per 10 seconds).

With this example, the client is still able to make 11 requests per minute, but that's already less than 20 as in your example, and they are spread over time. And I also believe if you play with the parameters you can achieve a strategy when >10 requests/min is not allowed at all.

 Time      Requests AvailableTokens
10:00:00     0          5 (we have 5 tokens initially)
10:00:10     0          5 (refill attempt failed cause Bucket is full)
10:00:20     0          5 (refill attempt failed cause Bucket is full)
10:00:30     0          5 (refill attempt failed cause Bucket is full)
10:00:40     0          5 (refill attempt failed cause Bucket is full)
10:00:50     0          5 (refill attempt failed cause Bucket is full)
10:00:58     5          0 
10:01:00     0          1 (refill 1 token)
10:01:10     0          2 (refill 1 token)
10:01:20     0          3 (refill 1 token)
10:01:30     0          4 (refill 1 token)
10:01:40     0          5 (refill 1 token)
10:01:49     5          0 
10:01:50     0          1 (refill 1 token)
10:01:56     1          0

Other options:

• b = 10 and r = 1/10
• b = 9 and r = 1/10

Nanosecond

Great answer! Is there an equation showing the maximum rate given both b and r? – Georginegeorglana

if you're asking about burst size then this quote from Wikipedia might be an answer. T: burst time. M: throughput. B: burst size. T = b / (M - r) if (r < M). And B = T * M. – Nanosecond

> "The trick with the Token Bucket is that Bucket size(b) and Refill rate(r) don't have to be equal." Comparing these two is like comparing apples and oranges. Bucket size has unit of token and refill rate has unit of token/time. – Wyndham

@AyushShukla you're right, it's just wrong wording, what I meant was that the volume of a single refill operation can be different from the bucket size. If you let me know how'd rephrase it, I'm glad to edit my answer – Nanosecond

Answer 2

The difference lies in the way tokens are refilled in the bucket.

If we were to refill the entire bucket exactly at fixed intervals, then it would be analogous to a Fixed Window.

However in case of a Token Bucket, the logic of the refilling of tokens can be modified to be able to control the burst. Let's consider the following example

MaximumCapacity - 10 InitialTokens - 10 refill rate - 10 tokens per minute.

Taking your example

 Time      Requests AvailableTokens
10:00:00     0          10 (added 10 tokens)
10:00:58    10          0
10:01:00     0          10 (added 10 tokens)
10:01:01    10          0 

This behaviour is analogous to Fixed Window, however we can split the token addition into granular intervals of refill time. In our case 10 tokens/minute could be spread to something like 2 tokens every 12 seconds. In that way we now have

 Time      Requests AvailableTokens
10:00:00     0          10 (initial 10 tokens)
10:00:58    10          0
10:01:00     0          2 
10:01:01    10          0 (rejected)
10:01:12     0          4 (2 tokens added)
10:01:24     0          6 (2 tokens added)
10:01:36     0          8 (2 tokens added)
10:01:48     0          10(2 tokens added)

bucket4j calls this implementation greedy-refill. bucket4j-refill But it will also take care of avoiding 10 + 10 requests at the end and start of two different windows.

Accomplice

Answer 3

Seems that I don’t have reputation enough to reply to comments. But token bucket and fixed window are equivalent. For the people that say that you can adjust the bucket size and the refresh rate, well, why can’t you can adjust the window size and the quota?

If you have a bucket of 2 with a refresh rate of 12 seconds, you can also have a window size of 12 seconds with a quota of 2.

The only difference is that one counts from 0 up to a limit and the other from a limit down to 0 haha

Linter