Token Bucket (Traffic Shaping)

Controlling the flow into the network

If every sender transmitted as fast as it liked, routers would overflow. Networks therefore shape or police traffic. The token bucket is the most widely used method, found in routers, API rate limiters and cloud gateways.

The algorithm

• A bucket holds up to B tokens (the bucket size) and starts full.
• Every tick, r new tokens are added. If the bucket is full the extra tokens are lost.
• To send a packet, take one token out. If there is none, the packet is dropped (or queued).

tokens ← B
every tick:
    tokens ← min(B, tokens + r)
    for each arriving packet:
        if tokens ≥ 1:  tokens ← tokens − 1;  send
        else:            drop

Worked example

Bucket size 5, rate 1, arrivals per tick: 4, 4, 0, 0, 1, 0, 5, 0, 0, 1.

Total: 12 sent, 3 dropped. The idle ticks 3–6 let the bucket refill, which paid for the burst at tick 7.

Token bucket vs leaky bucket

Tuning

• Rate r sets the long-run average the sender may use.
• Size B sets how large a burst is tolerated. A big bucket is friendly to bursty applications but can hit the network with a large spike.

Compare this with TCP congestion control, where the sender slows itself down after losses instead of being limited by a router.

Code

class TokenBucket:
    def __init__(self, size, rate):
        self.size, self.rate, self.tokens = size, rate, size

    def tick(self):
        self.tokens = min(self.size, self.tokens + self.rate)

    def allow(self):
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

Common mistakes

• Thinking the bucket holds packets. It holds permission tokens.
• Forgetting the cap: tokens beyond the bucket size are discarded, so idle time cannot be saved forever.
• Confusing the two buckets: only the leaky bucket forces a constant output rate.