# Q4(a) · Traffic shaping buckets

Subject: Computer Networks

Exam: TEE

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

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

Actual paper; 100 marks attempted. Current-syllabus alignment is stated per question.

### Q4(a). Describe in detail the working of token bucket and leaky bucket in traffic shaping. Illustrate with diagrams the implementation of each. [10 marks]

### Answer

In the textbook **leaky-bucket queue/shaper** model, arriving packets enter a finite buffer. The output sends at a configured rate whenever data is queued. When the queue empties, it cannot send nonexistent packets; when the buffer is full, excess arrivals are dropped in this finite-buffer model.

Swipe across the diagram to read its labels ↔

![Leaky-bucket data queue](https://deep-learning-study-room.vercel.app/cn/fig/tee-leaky.77bdbcf957.svg)

Diagram: Leaky-bucket data queue. Labels: Leaky-bucket data queue | Leaky-bucket data queue | Bursty arrivals enter finite buffer B | Accept packets that fit; the stated queue model drops overflow. | Queue drains at configured rate r | Send while data exists. An empty queue produces no packets. | Smoother departure stream | Buffering adds delay; idle service cannot be saved for a later burst.

Finite data buffer smooths a burst into a bounded departure rate.

1. Choose buffer capacity B and output service rate r in consistent units.
2. Admit arrivals that fit. Drop/mark overflow according to the stated implementation; this queue example drops the excess.
3. Drain at rate r while the queue is nonempty. Idle time does not accumulate permission for a later faster burst.
4. The result is smoothed output. Larger buffers accommodate larger bursts but can increase waiting delay.

| Advantage | Limitation |
| --- | --- |
| Simple bound on output rate | Bursts may overflow or suffer delay |
| Reduces short-term output variation | Unused idle service cannot be saved |
| Useful for predictable traffic shaping | No end-to-end delay/loss guarantee by itself |

The term “leaky bucket” can also describe a conformance meter in standards. This course’s diagrams and numerical questions explicitly use the finite data-queue model, so its state is queued data rather than tokens.

#### Practical example

A queue of 20 packets drained at 5 packets/s needs 4 seconds to empty without new arrivals. If it is already full, an instantaneous extra burst cannot all be stored.

No algorithm is universally better. The leaky data-queue model is useful for a smooth output profile; token bucket is preferable when controlled bursts should be allowed. State the application’s delay, burst and rate needs before recommending one.

**Yaad rakho:** Leaky bucket stores data; idle service save nahi hota.

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.

**Yaad rakho:** Token permission store hota hai; actual packet alag queue mein.

| Point | Leaky data queue | Token bucket |
| --- | --- | --- |
| Stored state | Queued data | Tokens representing permission |
| Idle period | Empty queue; unused service lost | Tokens accumulate up to B |
| Output burst | Smoothed by configured service rate | Allowed if enough tokens and physical capacity exist |
| Overflow/shortage | Finite queue can overflow | Shaper waits; policer may mark/drop |
| Main parameters | Queue capacity and drain rate | Token capacity and generation rate |
| Useful when | A smoother output profile is required | Average rate plus burst allowance is required |

#### Practical example

A steady-rate interface may use leaky shaping. A bursty file application can use token shaping to send short bursts while limiting its sustained rate.