Token bucket

The token bucket algorithm is an algorithm for traffic shaping in packet-switched data networks. He regulated by the network scheduler, the average data rate and maximum burst size.

Operation

The data stream will be allocated regularly certain quotas that can be exploited or accumulated up to a certain limit. To make the matter clearer, one imagines the allocation pictorially in the form of " tokens " (English token ), which are thrown at regular intervals in a metaphorical "bucket " (english bucket ). Each token represents a specific data quota that may be transferred. When the bucket is full, no tokens are assigned.

When a data packet is to be transmitted, the amount of data to be collected tokens from the bucket in the package according to the counter value.

What happens if not enough tokens are in the bucket depends on the implementation. Either the data packet is put in a queue to have accumulated through the regular allocation enough tokens, or it is discarded. Another option is to send the data packet immediately anyway, but as to mark it "non- compliant", so it can be rejected for his future, if it should lead to bottlenecks.

If less data being sent over a period of time allotted as tokens, these accumulate in the bucket. This creates a balance, which makes it possible to transmit larger amounts of data in the short term. In the long term, the transmission rate is limited by the rate of token allocation.

The size (capacity) of the bucket determines the maximum number of credits that can accumulate. This prevents that the average data rate is exceeded for too long a period of time.