Leaky Bucket and Token Bucket Algorithms for Traffic Shaping and Rate Limiting

Verified Sources

Nov 4, 2026

The Leaky Bucket and Token Bucket algorithms are widely used to control how data flows through networks. Both limit the average rate of sending/processing, but they differ in how they handle bursts.

At a high level:

Leaky Bucket enforces a steady “drip” (constant release) with optional buffering.
Token Bucket allows sending in bursts as long as tokens are available, while still limiting the long-term average rate.

A helpful mental model is:

With leaky bucket, packets “wait in a bucket” that drains at a fixed rate.
With token bucket, packets “spend tokens”; tokens regenerate at a fixed rate, enabling short-term bursts.

Key parameters you’ll see in both algorithms:

$R$ : allowed average rate (e.g., tokens added per second)
$B$ : bucket capacity (max queue size or max tokens)
Time unit: discretized intervals or continuous time (implementation choice)

Token Bucket vs Leaky Bucket (Traffic Shaping Overview)

Core idea and state representation

Leaky bucket (queue + constant drain)

In leaky bucket, you conceptually maintain a buffer of capacity $B$ :

When a packet/request arrives:
- If buffer is not full, it is queued.
- If buffer is full, the packet/request is dropped (or equivalently, not admitted).
A “leak” process continuously removes data from the buffer at a fixed rate $R$ .

This makes the output rate approximately constant, which is why it’s popular for traffic shaping.

Token bucket (tokens + spending)

In token bucket, you maintain:

A token counter $T$ with maximum capacity $B$
Tokens are added at rate $R$ up to $B$
When a packet/request arrives:
- If $T \ge 1$ (or $T \ge$ packet cost), it is allowed and tokens are consumed.
- Otherwise, it is delayed (wait for tokens) or rejected/dropped depending on policy.

This is why token bucket can allow bursts up to the bucket size.

Terminology keywords (for this section)

Rate limiting
Traffic shaping
Burst tolerance

Leaky Bucket Algorithm (Admission + Constant Output)

1
Step 1
Set average output rate $R$ and buffer capacity $B$ . Decide whether overflow causes drops or blocking.
2
Step 2
Start with an empty buffer (queue length $q=0$ ).
3
Step 3
If $q < B$ , enqueue the packet and set $q\leftarrow q+1$ (or add packet size if variable). If $q=B$ , drop the packet.
4
Step 4
Every time interval (or continuously), remove from the queue at rate $R$ : if $q>0$ , dequeue and set $q\leftarrow q-1$ according to the drain schedule.
5
Step 5
The departure process is smoothed: long-term average outflow approaches $R$ , and instantaneous output is limited by the leak rate and available buffered data.

Token Bucket Algorithm (Token Generation + Spend to Transmit)

1
Step 1
Set token generation rate $R$ and maximum tokens $B$ . Decide whether you ‘delay’ or ‘drop’ when tokens are insufficient.
2
Step 2
Start with $T=B$ (common for immediate burst) or $T=0$ (strict warm-up), depending on policy.
3
Step 3
Between arrivals, increase $T$ by $R\cdot \Delta t$ , but clamp to $B$ : $T\leftarrow \min(B,\,T+R\cdot\Delta t)$ .
4
Step 4
Let each packet require $c$ tokens (often $c=1$ ). If $T\ge c$ , admit and consume tokens $T\leftarrow T-c$ . Otherwise, either delay until tokens accumulate or drop/reject.
5
Step 5
If arrivals come in bursts, the bucket allows them as long as cumulative tokens permit. The long-term average send rate cannot exceed $R$ .

Side-by-side behavior (burst handling and smoothing)

Aspect	Leaky Bucket	Token Bucket
Long-term average rate	Enforced by constant drain at $R$	Enforced by token generation at $R$
Burst handling	Limited by buffer then constant leak; burst is “smoothed”	Naturally allows bursts up to token capacity $B$
Queueing vs admission	Typically queues up to $B$ , drops on overflow	Can admit immediately when tokens exist; else delay or drop
Output shape	More constant/regular departure rate	More bursty (but bounded by tokens)
Parameters meaning	$B$ is max queued backlog; $R$ is leak rate	$B$ is max token storage; $R$ is refill rate

Practical interpretation

If your goal is strictly smooth output, leaky bucket is a strong fit.
If you want to permit occasional bursts while still capping the long-term rate, token bucket is typically preferred.

Keywords for this section

Bucket capacity
Token refill rate
Drain rate

Implementation detail: discrete vs continuous time

In real systems you’ll implement token generation/draining with a timer or on each request. Either way, ensure you cap at $B$ and compute available tokens/queue correctly from elapsed time.

Overflow policy changes the semantics

For leaky bucket, overflow usually drops or blocks. For token bucket, insufficient tokens can cause delay or rejection. Pick the policy to match your SLA and client behavior.

When to Choose Each Algorithm

Use Leaky Bucket

Constant-rate shaping goal

Prefer stable departure spacing to reduce jitter and smooth downstream load."

Use Token Bucket

Burst-tolerant admission goal

Prefer immediate allowance for short bursts while controlling long-term average rate."

Combine with per-flow buckets

Need bounded fairness under load

Apply buckets per user/flow to avoid one source consuming all capacity."

Select drop vs delay

Operational constraints

Delay increases latency; drop increases loss. Choose based on requirements."

Variable packet sizes (important extension)

Both algorithms can be generalized from “1 unit per packet” to packet sizes/costs:

In token bucket, each packet costs $c$ tokens proportional to its size.
In leaky bucket, each packet adds $c$ units to backlog, and draining removes tokens/units at rate $R$ .

Then:

Token check becomes: admit if $T \\ge c$
Leaky bucket overflow becomes: queue if $q + c \\le B$ , else drop

This is common in routers and traffic engineering where “packet weight” matters.

Mathematical framing (conceptual)

Let token count evolve as: $T(t) = \\min\\left(B,\\,T(t_0) + \\int_{t_0}^{t} R\\,dt\\right)$

Admission with cost $c$ occurs only if $T(t) \\ge c$ .

(Implementation usually discretizes the integral using elapsed time.)

Common FAQs and edge cases

Behavior Comparison Summary

Qualitative scoring: higher means more of that property in typical implementations.

Leaky vs Token Bucket—Self Check

1 / 5

Question · Term

Leaky bucket: what happens when the queue is full?

Click to reveal

Answer · Definition

The new arriving packet/request is typically dropped (or blocked, depending on policy).

Knowledge Check

Question 1 of 4

Q1Single choice

In a leaky bucket algorithm, what primarily determines the departure (output) rate when the bucket is not empty?

The constant leak/drain rate $R$

The arrival rate only

The maximum capacity $B$ only

The number of tokens accumulated (token concept)

Explore Related Topics

Cache Memory: Why FIFO and LRU Are Replacement Algorithms

Pure ALOHA vs Slotted ALOHA: Differentiation, Throughput, and Worked Examples

The Banker's Algorithm: Deadlock Avoidance in Operating Systems

The Banker's Algorithm is a deadlock‑avoidance method that keeps a system in a safe state by checking each resource request against the maximum declared needs of processes.

Maintains Available, Max, Allocation, and Need matrices, where $\text{Need}[i][j]=\text{Max}[i][j]-\text{Allocation}[i][j]$ .
The Safety Algorithm uses vectors Work and Finish to find an execution order; if all processes finish, the state is safe.
The Resource‑Request Algorithm simulates allocation, runs the safety check, and commits only if the resulting state remains safe.
Time complexity of the safety check is $O(m \times n^{2})$ .
In practice the algorithm is rarely used because processes must predeclare maximum needs and the algorithm’s overhead is high.

Browse all research articles