---

The Token Bucket Algorithm

---

1. Motivation: Overcoming Leaky Bucket Rigidity

The Leaky Bucket algorithm enforces a rigid constant output rate, dropping packets if a burst arrives even if the network was completely idle for the preceding hour.

The Token Bucket Algorithm resolves this by allowing controlled traffic bursts:

• If a host is idle, it saves up "credits" in the form of Tokens.
• When a burst of data arrives, the host can consume its accumulated tokens to transmit at the maximum physical link rate ($M$) for a brief period before settling back to the sustained average rate ($R$).

---

2. Operating Mechanism of Token Bucket

Operational Rules:

1. Token Generation: Tokens are added to the bucket at a constant rate of $R$ tokens per second.
2. Bucket Capacity ($C$): The bucket has a finite capacity of $C$ tokens. If the bucket is full, newly generated tokens overflow and are discarded.
3. Transmission Condition:
   • To transmit a packet of length $b$ bytes, the sender must remove $b$ tokens from the bucket.
   • If Tokens $\geq b$: The tokens are removed, and the packet is transmitted immediately at full link speed $M$.
   • If Tokens $< b$: The packet must wait in a queue until sufficient tokens accumulate, or be dropped.

---

3. Mathematical Formula for Maximum Burst Duration

When a full bucket of capacity $C$ encounters a massive burst of incoming traffic, the transmitter empties the bucket at maximum rate $M$ while new tokens continue to flow into the bucket at sustained rate $R$ ($M > R$).

Let $T$ be the maximum duration of the burst at rate $M$:

Equating the two:

• Maximum Burst Duration ($T$): The longest time the system can continuously transmit at peak link rate $M$.
• Total Burst Volume ($V_{\max}$):

---

4. Solved Numerical Example

Problem:

A token bucket regulator has a bucket capacity of $C = 2\text{ Megabytes}$ ($16\text{ Megabits}$) and a token generation rate of $R = 5\text{ Mbps}$. The maximum physical link transmission speed is $M = 25\text{ Mbps}$.

1. Calculate the maximum burst duration ($T$) at peak rate $25\text{ Mbps}$.
2. Calculate the total data volume transmitted during this peak burst.

Solution:

• $C = 16\text{ Megabits}$
• $R = 5\text{ Mbps}$
• $M = 25\text{ Mbps}$

1. Maximum Burst Duration ($T$):

2. Total Burst Volume:

Analysis: In $0.8$ seconds, the bucket delivered $2.5\text{ MB}$ of data at peak speed: $2\text{ MB}$ came from accumulated stored tokens, and $0.5\text{ MB}$ ($5\text{ Mbps} \times 0.8\text{ s}$) came from new tokens generated during the burst itself!

---

5. Comprehensive Comparison: Leaky Bucket vs. Token Bucket

Parameter	Leaky Bucket Algorithm	Token Bucket Algorithm
Bucket Contents	Stores actual Packets / Data	Stores abstract Tokens (Credits)
Output Rate	Strictly Constant (Fixed leak rate $R$)	Variable / Bursty (Up to maximum link rate $M$)
Burst Handling	Smooths bursts into a constant trickle	Allows controlled bursts up to capacity $C$
Token Generation	None (Direct packet queue)	Generated at fixed periodic rate $R$
Idle Behavior	Discards empty ticks	Accumulates tokens up to capacity $C$
Packet Dropping	Drops packets when bucket buffer is full	Drops tokens when full; delays or drops packets
Implementation	FIFO Queue + Rate limiter	Counter + Token Generator

---