- 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
