---
title: "Token bucket algorithm"
subject: "Computer Networks and Security"
chapter: 5
key: "semester_7/computer_networks_and_security:token-bucket"
source: https://www.bctengineer.com/q/semester_7/computer_networks_and_security/token-bucket
site: BCT Engineering
---

# Token bucket algorithm

Computer Networks and Security · Chapter 5: Transport Layer

- Asked in: 2074 Chaitra, 4 marks; 2073 Chaitra; 2072 Chaitra, 4 marks; 2069 Chaitra, 3 marks (asked 4 times)
- Video: [Congestion Control in TCP Using Traffic Shaping: Leaky Bucket and Token Bucket Algorithms](https://www.youtube.com/watch?v=krJcfScWQMU) — Engineering Funda
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/computer_networks_and_security/token-bucket
- Whole chapter: https://www.bctengineer.com/md/semester_7/computer_networks_and_security/chapter-5

## Question

Explain the token bucket algorithm for congestion control, with a diagram.

## Short answer

Token bucket limits average rate r, allows bursts of up to b packets. Tokens added at rate r into bucket of capacity b; a packet consumes one token if available, else waits or is dropped. Idle hosts accumulate tokens for bursts. Unlike leaky bucket, it permits variable output rates and saves idle credit as tokens.

## Answer

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.

```text
  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.

| Tick | Packets arrive | Tokens available | Sent | Waiting |
|---|---|---|---|---|
| 0 | 5 | 5 | 5 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 2 | 0 | 2 | 0 | 0 |
| 3 | 3 | 3 | 3 | 0 |
| 4 | 3 | 1 | 1 | 2 |
| 5 | 0 | 1 | 1 | 1 |
| 6 | 0 | 1 | 1 | 0 |

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
| Point | Leaky bucket | Token bucket |
|---|---|---|
| Output rate | Constant | Variable; bursts allowed |
| Idle credit | Not saved | Saved as tokens |
| Bursts | Smoothed out | Allowed up to b |
| When bucket is full | Packets discarded | Tokens discarded, packets kept |

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).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How are tokens added in the token bucket?
   A. At constant rate r, discarded when the bucket (capacity b) is full
   B. At the packet rate, with unlimited storage
   C. Only when the network is idle
   D. Only when a packet arrives
   Answer: A. Tokens are generated at fixed rate r and overflow tokens are discarded. (Key point: Token generation)

2. Why can a token bucket allow a burst?
   A. An idle host saves tokens, up to b, and spends them at once
   B. It ignores the token count
   C. It increases r automatically
   D. It drops all waiting packets
   Answer: A. Saved tokens let up to b packets be sent together. (Key point: Burst allowed)

3. How does token bucket differ from leaky bucket?
   A. They are identical
   B. Leaky bucket saves tokens
   C. Token bucket output is variable and saves idle credit; leaky bucket is constant
   D. Token bucket has constant output
   Answer: C. Leaky bucket smooths to a constant rate; token bucket allows bursts. (Key point: Versus leaky bucket)

4. What limits the long-term rate of a token bucket flow?
   A. Queue length
   B. Packet size only
   C. Token rate r
   D. Bucket size b
   Answer: C. Over time the average rate cannot exceed r; b only bounds the burst. (Key point: Long-term rate)

## Related in other subjects

- [Token ring mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atoken-ring-mutex) — Distributed System, chapter 6, asked 3×
- [Mutex requirements; token vs non-token](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Amutex-requirements-compare) — Distributed System, chapter 6
- [PID control operation with block diagram](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Apid-operation-block-diagram) — Embedded System, chapter 7, asked 4×
- [Closed loop control system block diagram explained](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Awhat-is-cs-bd-closed-loop) — Control Systems, chapter 1, asked 4×