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?

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