Token Bucket

Similar to the Leaky Bucket 202211231056. Also used to check that data (packet) transmissions conform to defined limits on bandwidth and burstiness.

It can also be used as a scheduling algorithm to determine the timing of transmissions that will comply with the limits set for the bandwidth and burstiness.

The difference between the token bucket and the leaky bucket 202211231056 is that the output of the token bucket can be bursty.

Algorithm

1. A token is added to the bucket once every 1/r seconds.
2. The bucket can hold a maximum of b tokens. Nothing happens once you try to add a token to the bucket once it already has b tokens.
3. If a packet of n bytes tries to enter the network:
   • If there are >= n tokens available in the bucket, let the packet through and decrease the number of tokens in the bucket by n.
     • If there are < n tokens, don’t remove any tokens, and the packet is considered non-conformant.

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.

Created from: Algorithms to know before system design interviews 202211231052

---

uid: 202211231057 tags: #algorithms #software-engineering

---

---

---