Q7B · Traffic-shaping algorithm

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 ↔

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.

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.

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