The leaky bucket sends data out at a fixed constant rate, smoothing bursts; the token bucket sends data only when tokens are available, so it allows bursts up to the bucket size while limiting the average rate.
Leaky bucket algorithm
- Imagine a bucket with a small hole: water (packets) may pour in irregularly, but leaks out at a constant rate.
- Packets enter a finite queue (the bucket). The output is sent at a fixed rate \(r\), e.g. one packet per clock tick (or \(n\) bytes per tick for variable-size packets).
- If the bucket is full, arriving packets are discarded.
- Result: bursty input becomes smooth, uniform output, which helps reduce congestion.
Token bucket algorithm
- Tokens are added to a bucket at a constant rate \(r\); the bucket holds at most \(b\) tokens (extra tokens are thrown away).
- To send a packet (or byte), a token must be removed. If no tokens are available, the packet waits.
- When the host is idle, tokens accumulate, so it can later send a burst of up to \(b\) at the maximum line speed \(M\).
- Maximum burst duration: \(S = \dfrac{b}{M - r}\). Example: \(b = 1\) MB, \(M = 25\) MB/s, \(r = 2\) MB/s gives \(S = 1/23 \approx 43\) ms.
Comparison
| Leaky bucket | Token bucket |
|---|---|
| Output at a constant rate, no bursts | Allows bursts up to bucket size \(b\) |
| Bucket holds packets | Bucket holds tokens |
| When the bucket is full, packets are discarded | When the bucket is full, tokens are discarded; packets wait |
| Idle time is not saved | Idle time is saved as tokens (permission to send later) |
| Rigid; may waste bandwidth | Flexible; better use of bandwidth |
| Traffic shaping by rate | Traffic shaping by rate and burst size |
The two are often combined: a token bucket followed by a leaky bucket gives bursts that are still capped at a peak rate.