|
Token bucket - Definition and Overview |
| Related Words: Bail, Bark, Barrel, Boat, Bottom, Can, Cooler, Craft, Cup, Dip, Dish, Fly, Fork, Highball |
|
|
|
Although the token bucket algorithm has several uses, it is best understood in
the context of network traffic shaping or rate limiting. Typically, the algorithm is used to control the rate at which data is injected into a network, limiting "burstiness" in the data rate.
The algorithm can be conceptually understood as follows:
- A token is added to the bucket every <math>1/r<math> seconds.
- The bucket can hold at the most b tokens. If a token arrives when the bucket is full, it is discarded.
- When a packet (network layer PDU) of n bytes arrives, n tokens are removed from the bucket, and the packet is sent to the network.
- If fewer than n tokens are available, no tokens are removed from the bucket, and the packet is considered to be non-conformant.
The algorithm allows bursts of up to b bytes, but over the long run the output of conformant packets is limited to the constant rate, <math>r<math>. Non-conformant packets can be treated in various ways:
- They may be dropped.
- They may be enqueued for subsequent transmission when sufficient tokens have accumulated in the bucket.
- They may be transmitted, but marked as being non-conformant, possibly to be dropped subsequently if the network is overloaded.
Sometimes the token bucket and the leaky bucket algorithms are lumped together under the same name. They differ principally in that the leaky bucket imposes a hard limit on the data transmission rate, whereas the token bucket allows a certain amount of burstiness while imposing a limit on the average data transmission rate.
The Generic Cell Rate Algorithm used in traffic shaping of ATM networks is equivalent to the leaky bucket algorithm.
References
Andrew S. Tanenbaum, Computer Networks, 3rd Edition, Prentice-Hall, 1996.
See also
External links
|
|
|
