Leaky Bucket Algorithm

A traffic shaping / congestion control algorithm that converts bursty traffic into a constant-rate output, like water leaking from a hole at the bottom of a bucket at a fixed rate.

Working

1. Incoming packets are placed in a finite-size queue (bucket).
2. Packets leave the bucket at a fixed rate $\rho$, regardless of the input rate.
3. If the bucket is full, arriving packets are discarded.
4. For variable-size packets, a fixed number of bytes per tick is released.

Characteristics

• Output rate is constant and smooth
• Bursts are absorbed up to the bucket size
• Excess traffic is dropped
• Does not allow idle-time credit (unlike Token Bucket, which permits bursts)

Applications

• Traffic shaping at network edges (ISP-customer)
• Enforcing a Service Level Agreement/rate limit
• QoS in ATM and multimedia traffic
• Congestion prevention in routers