Token Bucket Algorithm

It is an improved version of the leaky bucket algorithm, which can adjust flow in case of burst traffic. It allows sending bursty traffic when required, up to the maximum size of the bucket.

Token Bucket Algorithm


1. A variable counts token

2. Counter incremented by one in every DT second.

3. The counter is decremented when the packet is sent.

4. If counter=0 then no packet is sent.

5. In the case of the byte-count version:
(i) The counter is incremented by k bytes in every DT second.
(ii) The counter is decremented by the length of the packet sent.
(iii) If counter=0 then no packet is sent.

6. Length of the burst is a design issue.
Let S=burst length(sec) and C=token bucket capacity(byte)
r=token arrival rate(byte/sec)
M=maximum output rate(byte/sec)