QoS Improving Techniques: Leaky Bucket and Token Bucket Algorithms

---

1. Traffic Shaping Fundamentals

Computer data traffic is inherently bursty: applications alternate between long periods of transmission silence and sudden, high-volume packet bursts. If bursty traffic enters an unmanaged network, intermediate router queues instantly overflow, resulting in buffer drops, excessive retransmissions, and network congestion.

Traffic Shaping is a traffic management technique that regulates the rate and volume of packets entering a network, smoothing bursty traffic into a predictable, well-behaved profile.

                            TRAFFIC SHAPING TECHNIQUES
                                        |
         +------------------------------+------------------------------+
         |                                                             |
   LEAKY BUCKET ALGORITHM                                    TOKEN BUCKET ALGORITHM
 (Strictly constant output rate)                           (Allows controlled traffic bursts)

---

2. The Leaky Bucket Algorithm

The Leaky Bucket uses the physical analogy of a bucket with a small hole in the bottom:

  Bursty Inflow (Packets arrive in bursts)
       | | |    | |
       v v v    v v
   +--------------------+
   |  LEAKY BUCKET      |  <-- Capacity C (Buffer size)
   |  ~~~~~~~~~~~~~~~~~ |
   |  ~~~~~~~~~~~~~~~~~ |
   +---------+----------+
             |
             v
   Constant Outflow Rate R (Fixed leak: drops at steady pace)
   (Smooth, non-bursty output stream)

Operational Rules:

1. FIFO Buffer of Capacity $C$: Stores incoming packets up to limit $C$.
2. Constant Leak Rate $R$: Packets are dequeued and transmitted onto the network at a strictly constant rate of $R$ bytes/sec, regardless of the arrival rate.
3. Packet Dropping: If a burst arrives when the bucket is full ($> C$), excess packets overflow and are discarded.
4. Limitation: Inflexible. It cannot burst at higher speeds even when the communication link is completely idle, introducing artificial transmission delays for bursty applications.

---

3. The Token Bucket Algorithm

The Token Bucket Algorithm overcomes the inflexibility of the Leaky Bucket by allowing controlled bursts of traffic up to the maximum physical link rate ($M$):

  Tokens generated at constant rate R (tokens/sec)
                      |
                      v
            +--------------------+
            |    TOKEN BUCKET    |  <-- Capacity C tokens (Max credits saved)
            |   (•)  (•)  (•)    |
            +---------+----------+
                      |
                      | 1 Byte consumes 1 Token
                      v
  Packets Arrive ──> [ Gate ] ───> Transmitted into Network
  (Bursty Queue)    (Consumes tokens)(Can burst at full link speed M)

Operational Rules:

1. Token Generation: Abstract tokens ("credits") are added to the bucket at a constant rate of $R$ tokens per second.
2. Bucket Capacity ($C$): The bucket can hold at most $C$ tokens. When full, newly generated tokens are discarded.
3. Transmission Rules:
   • To transmit a packet of $b$ bytes, $b$ tokens must be removed from the bucket.
   • If Tokens $\geq b$: The packet is transmitted immediately at the maximum link rate $M$.
   • If Tokens $< b$: The packet must wait for more tokens to generate, or be dropped.

---

4. Mathematical Derivation of Maximum Burst Time

When a full bucket of capacity $C$ encounters a massive burst of incoming data, the sender transmits at the peak link rate $M$ while new tokens continue to arrive at rate $R$ ($M > R$).

Let $T$ be the maximum duration of the burst:

Equating data transmitted to available tokens:

• Maximum Burst Volume ($V_{\max}$):

---

5. Solved Step-by-Step Numerical

Problem:

A token bucket regulator has a bucket capacity of $C = 1\text{ Megabyte}$ ($8\text{ Megabits}$), a token arrival rate of $R = 2\text{ Mbps}$, and the physical network link operates at a maximum transmission speed of $M = 10\text{ Mbps}$.

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

Solution:

• $C = 8\text{ Megabits}$
• $R = 2\text{ Mbps}$
• $M = 10\text{ Mbps}$

1. Maximum Burst Duration ($T$):

2. Total Transmitted Burst Volume:

---

6. 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 Data Rate	Strictly Constant (Fixed rate $R$)	Variable / Bursty (Up to link rate $M$)
Traffic Bursts	Smooths bursts into a constant trickle	Allows controlled bursts up to capacity $C$
Idle Periods	Discards idle ticks	Accumulates tokens up to capacity $C$
Packet Loss	Occurs when buffer queue fills ($> C$)	Packets wait or drop when tokens run out
Hardware Core	FIFO Queue + Rate limiter	Simple counter register

---

7. Key Exam Questions & Takeaways

1. Why does the Token Bucket algorithm handle bursty traffic better than the Leaky Bucket algorithm?
   • The Leaky Bucket forces packets out at a strictly constant rate even when the network has idle bandwidth. The Token Bucket accumulates credits during idle periods, allowing the sender to burst at maximum wire speed when needed.
2. What happens to generated tokens when the Token Bucket is full?
   • Newly generated tokens overflow and are discarded. The bucket capacity $C$ sets the upper bound on the maximum burst credit.
3. State the formula for maximum burst time in a Token Bucket.
   • $T = \frac{C}{M - R}$, where $C$ is bucket capacity, $M$ is peak transmission speed, and $R$ is continuous token generation rate.