What is Token Bucket Algorithm?

Token Bucket Algorithm

• In contrast to the leaky bucket, the Token Bucket (TB) algorithm, allows the output rate to vary, depending on the size of the burst.
• In the TB algorithm, the bucket holds tokens.  To transmit a packet, the host must capture and destroy one token.
• Tokens are generated by a clock at the rate of one token every t sec.
• Idle hosts can capture and save up tokens (up to the max. size of the bucket) in order to send larger bursts later.

Token bucket operation

• TB accumulates fixed size tokens in a token bucket.
• Transmits a packet (from data buffer, if any are there) or arriving packet if the sum of the token sizes in the bucket add up to packet size.
• More tokens are periodically added to the bucket (at rate t). If tokens are to be added when the bucket is full, they are discarded
• Does not bound the peak rate of small bursts, because bucket may contain enough token to cover a complete burst size.
• Performance depends only on the sum of the data buffer size and the token bucket size

Token bucket - example

2 tokens of size 100 bytes added each second to the token bucket of capacity 500 bytes
Avg. rate = 200 bytes/sec, burst size = 500 bytes.
Packets bigger than 500 bytes will never be sent
Peak rate is unbounded – i.e., 500 bytes of burst can be transmitted arbitrarily fast

Leaky Bucket vs Token Bucket

• LB discards packets; TB does not. TB discards tokens.
• With TB, a packet can only be transmitted if there are enough tokens to cover its length in bytes.
• LB sends packets at an average rate. TB allows for large bursts to be sent faster by speeding up the output.
• TB allows saving up tokens (permissions) to send large bursts. LB does not allow saving