← 🧭 Routing & Congestion Control
Subtopic 4 of 4

6.4Congestion and traffic shaping: leaky and token bucket

The idea

Traffic shaping controls how fast a host can send. A leaky bucket outputs at a fixed rate. A token bucket accumulates tokens and allows a burst up to its capacity.

Think of it like this: A leaky bucket is a tap dripping at a fixed rate. A token bucket is a savings account: you can spend a lot at once if you saved it up, and afterwards only what comes in.

Why it exists

GATE asks for the minimum time to send D data through a token bucket.

How it works

  1. The bucket starts full with C. Tokens arrive at rate r. Output rate cannot exceed M.
  2. While bursting, the bucket empties at rate M − r, so the burst lasts C/(M − r).
  3. Data sent in the burst = M × C/(M − r).
  4. The rest is sent at rate r. Total time = burst time + remaining/r.

Worked example: C = 1 MB, r = 10 MB/s, M = 20 MB/s, send 12 MB.

Burst = 1/10 = 0.1 s, sends 2 MB. Remaining 10 MB at 10 MB/s = 1 s. Total 1.1 s (GATE 2016).

Now play with it

  • →Change D to 2 MB: the whole file fits in the burst.
  • →Make M equal to r: the bucket gives no advantage.
Burst lasts (s)0.1
Data sent in the burst (MB)2
Minimum time to send D (s)1.1

GATE 2016: 1 MB bucket, 10 MB/s tokens, 20 MB/s maximum, 12 MB to send. The burst lasts 1/(20 − 10) = 0.1 s and sends 2 MB; the remaining 10 MB take 1 s at 10 MB/s: 1.1 s.

Check yourself

A token bucket lets a source

Remember: Token bucket: burst C/(M − r), then token rate r. Leaky bucket: constant output.
Exam notes (the dense version)

The leaky bucket smooths traffic to a constant output rate: bursts queue in the bucket and leave at a fixed rate. The token bucket allows bursts: tokens arrive at rate r into a bucket of capacity C; sending needs tokens, so a full bucket lets you burst at the maximum rate M until the tokens run out, then continue at r. Burst duration = C / (M − r). To send D units from a full bucket: burst for C/(M − r) (sending M · C/(M − r)), then send the rest at rate r.

Previous year questions: Routing & Congestion Control (3)

PYQs are grouped by topic, so this is the full set for Routing & Congestion Control; try the ones that match this subtopic. Open all 3 on the topic page.