The idea
A host that sends in sudden bursts can swamp a router even if its average rate is modest. The fix is to control the traffic at the source of the problem before it enters the network. Traffic shaping controls the amount and the rate of the traffic sent into the network, and the lecture gives two techniques: the leaky bucket and the token bucket.
How it works
Leaky bucket
The leaky bucket shapes bursty traffic into fixed-rate traffic by averaging the data rate. It may drop packets if the bucket is full, and it also prevents congestion.
Bursty data goes into the bucket and leaves at a fixed rate. The lecture’s algorithm figure does not survive text extraction. Its verdict is that the leaky bucket is very restrictive. It does not credit an idle host: if a host is not sending for a while, its bucket becomes empty. The lecture also labels it as unaware of buffer or queue status.
How it works
Token bucket
The leaky bucket imposes a hard limit on the data transmission rate. The token bucket allows a certain amount of burstiness while imposing a limit on the average data transmission rate. It allows bursty traffic at a regulated maximum rate, and it allows idle hosts to accumulate credit for the future in the form of tokens. The lecture labels it as aware of buffer or queue status.
How it works:
- The bucket contains tokens.
- Tokens are added periodically at the desired maximum average rate.
- Packets can only be sent when there are tokens in the bucket.
- Tokens are removed when packets are sent.
| Leaky bucket | Token bucket | |
|---|---|---|
| Output | Fixed rate | Bursts allowed, average rate limited |
| Idle host | Gets no credit, the bucket becomes empty | Accumulates tokens as credit for the future |
| Packets dropped | May drop if the bucket is full | Not stated in the lecture |
| Queue status | Unaware | Aware |
How it works
Token bucket analysis
The lecture’s analysis uses two symbols: the capacity of the bucket c tokens
and the token rate r tokens per second entering the bucket. The system removes
one token for every cell of data sent. In any interval of length t:
- r
- Token rate in tokens per second
- t
- Interval length in seconds
- c
- Bucket capacity in tokens
The maximum average rate follows by dividing by t:
- r
- Token rate in tokens per second
- t
- Interval length in seconds
- c
- Bucket capacity in tokens
Worked example
Token bucket limits over 2 seconds
Given (our own numbers, the lecture gives none):
c = 10tokens,r = 5tokens/s,t = 2s.Tokens arriving in the interval:
r x t=5 x 2=10tokens.Add the full bucket:
10 + 10=20tokens, so at most20packets enter the network.Average rate:
20 / 2=10packets per second.Compare with the token rate:
10is abover = 5. The excess is the burst that the saved credit allows. Astgrows,c / tshrinks and the average approachesr.
AnswerUp to 20 packets, an average of 10 packets per second.
Where marks get lost
The limit is on average, not on instants
The token bucket does not cap each second at r. It caps the long-run average
near r, and lets a full bucket go out at once. If an answer says the token
bucket gives a fixed output rate, that is the leaky bucket.
In the exam
- Both are traffic shaping techniques that control the amount and rate of traffic sent to the network.
- Leaky bucket: fixed output, drops when full, no credit for idle hosts.
- Token bucket: tokens at rate
r, capacityc, one token per cell, bursts allowed, idle time banked. - Formulas: maximum packets
r x t + c, maximum average rate(r x t + c) / t.
Check yourself
- Shaping controls the amount and rate of traffic going into the network.
- Leaky bucket gives fixed-rate output and does not credit idle hosts.
- Token bucket banks tokens while idle and allows bursts within an average limit.
- Over time
ta token bucket passes at mostr x t + cpackets.