Computer Networks · TEE · papers
Q7(a) · Leaky versus token bucket
2024-12-06 · Final 2024-25 / Re-exam 2023-24
Actual paper; 100 marks attempted. Current-syllabus alignment is stated per question.
Q7(a). Compare and contrast Leaky Bucket and Token Bucket algorithm for QoS improvement. [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.
- Choose buffer capacity B and output service rate r in consistent units.
- Admit arrivals that fit. Drop/mark overflow according to the stated implementation; this queue example drops the excess.
- Drain at rate r while the queue is nonempty. Idle time does not accumulate permission for a later faster burst.
- 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.
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.
- Initialize a stated token count, often B for a full bucket. Add rΔt tokens over elapsed time, capped at B.
- 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.
- 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.
- Over interval t, a full token bucket bounds admitted data by B+rt. Actual output is also limited by link capacity and packet scheduling.
- Unlike the queue-style leaky bucket, token storage allows limited bursts after idle time. It bounds average rate and burst size separately.
LaTeX: \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 |
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 |