# Q7B · Token bucket

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/tee-paper-final/q7b

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/tee-paper-final--q7b/

TEE · Actual TEE paper · all questions · current syllabus 702AI0C023

### Actual PYQ · Q7B. Draw a neat diagram and explain the working of the Token Bucket Algorithm. State any two limitations of the Token Bucket algorithm. [10 marks]

#### Answer

A **token bucket** generates tokens at rate r up to capacity B. Sending one unit of data consumes the corresponding tokens. Tokens accumulate during idle periods only until the bucket is full. Data can therefore burst when saved tokens exist, subject to the physical link rate.

Swipe across the diagram to read its labels ↔

![Token bucket: permission is separate from data](https://deep-learning-study-room.vercel.app/cn/fig/tee-token.c3ff1dbf76.svg)

Diagram: Token bucket: permission is separate from data. Labels: Token bucket: permission is separate from data | Token bucket: permission is separate from data | Token generator adds r tokens per second | Store at most B tokens; extra tokens disappear when the bucket is full. | Packet of L bytes requests L tokens | Enough tokens: deduct L and permit transmission, subject to link speed. | Insufficient tokens: policy matters | Shaper buffers/waits. Policer marks or drops according to policy. | Saved tokens permit bounded bursts | Initially full: allowance over t ≤ B + rt. This alone is not an end-to-end QoS guarantee.

Tokens store permission; the separate data queue stores packets.

1. Initialize a stated token count, often B for a full bucket. Add rΔt tokens over elapsed time, capped at B.
2. A packet of length L needs L byte-tokens (or one packet-token in a fixed-packet model). If enough tokens exist, deduct them and permit transmission.
3. If tokens are insufficient, a **shaper** waits/buffers until enough are available. A **policer** marks or drops nonconforming traffic according to policy. Token shortage does not universally mean drop.
4. Over interval t, a full token bucket bounds admitted data by B+rt. Actual output is also limited by link capacity and packet scheduling.
5. Unlike the queue-style leaky bucket, token storage allows limited bursts after idle time. It bounds average rate and burst size separately.



$$
\mathrm{admitted\ data}(t)\le B+rt
$$



| Limitation | Reason |
| --- | --- |
| Bursts can still congest downstream queues | Local conformance does not ensure every later link has capacity |
| Parameters must match traffic and link requirements | A small B delays/drops legitimate packets; a large B permits disruptive bursts |
| No complete QoS guarantee alone | Admission, scheduling and end-to-end capacity may still be needed |

#### Practical example

With B=10 KB and r=2 KB/s, an idle sender can immediately use up to 10 KB of saved tokens; additional sustained traffic must respect the refill rate, and physical serialization still takes time.

Source: Final · 5 December 2025, original question paper page 3. Original marks retained; solution independently authored.