Token bucket algorithm

The token bucket algorithm is a traffic-shaping / congestion-control method that limits the average rate of a flow but still allows short bursts.

Working

1. A bucket of capacity b tokens holds tokens. Tokens are added at a constant rate r (tokens per second). If the bucket is full, new tokens are discarded.
2. One token permits one packet (or one byte, in byte-based versions) to be sent.
3. When a packet arrives, if enough tokens are present, the tokens are removed and the packet is sent at once. If not, the packet waits (shaping) or is dropped/marked (policing).
4. An idle host saves tokens, so later it can send a burst of up to b packets.

  tokens added at rate r
          |
          v
      +--------+
      | bucket |  capacity b
      | o o o  |
      +---+----+
          | one token per packet
 packets  v
 -------> [ queue ] ---(token available?)---> network

Example

Bucket capacity b = 5 tokens, r = 1 token per tick, 1 token per packet, bucket initially full.

The burst of 5 packets passes at once, but in the long run the rate cannot exceed 1 packet per tick.

Token bucket vs leaky bucket

If M is the peak output rate of the link, the maximum time S for which a burst can be sent at rate M is S = b / (M − r).