I believe, tokens are nothing but packets, but my question is, weather these tokens are fixed size? If yes, why fixed packets? Can anyone explain the algorithm clearly with examples. Thanks.
The concept of a token bucket is generic/universal, but the implementations for QoS may use different token units to control traffic flow at a specified rate.
In Cisco traffic policing (the most basic QoS token bucket technique), the token bucket size is specified in bytes (each token is one byte). For example, if you want to police traffic at a rate of 100Kbps, you could use a command like
police 100000 18750 which sets your cir (committed information rate) to 100 thousand bits per second and your bc (burst committed/token bucket size) to 18,750 bytes. Here is an example of how this token bucket works with some sample traffic (t is the elapsed time in milliseconds):
- Policer bucket starts full with 18,750 bytes
- at t=0ms: 1,500 byte packet is sent leaving 17,250 bytes in bucket
- at t=100ms: we add 1,250 bytes (tokens) to the bucket (0.1s at 100k) then transmit two 1500 byte packets that just arrived. 17250+1250-3000=15,500 bytes left in bucket
- at t=200ms: we add 1,250 bytes (tokens) to bucket then transmit three 1500 byte packets that just arrived. 15500+1250-4500=12,250 bytes left in bucket
- at t=300ms: we add 1,250 bytes (tokens) to bucket then transmit four 1500 byte packets that just arrived. 12250+1250-6000=7,500 bytes (tokens) left in bucket
- at t=500ms: we add 2,500 bytes (100Kbps for 0.2seconds without traffic) then transmit six 1000 byte newly arrived packets. 7500+2500-6000=4,000 bytes
- at t=600ms: we add 1,250 bytes (tokens) to bucket then transmit three 1500 byte fresh packets. 4000+1250-4500=750 bytes
- at t=650ms: we add 625 bytes (tokens) and try to send a just arrived 1500 byte packet but must DROP IT because there are not enough tokens (bytes) in the bucket. 750+625=1375 bytes (not enough tokens, drop 1500 byte packet)
Let me try to describe how the algorithm works. Bucket starts full when first packet arrives we take bytes from bucket. When next packet(s) arrive, we add tokens based on time since last packet(s) processed then transmit as many packets as new bucket size allows. When new packets arrive we always add tokens (bytes) (rate * seconds since last packet(s) / 8bitsperbyte) then transmit as many packets as the bucket will allow. We can NEVER fill bucket beyond the fixed size (bc / bucket size) and we can never take out more tokens to transmit packets at a given instant if the size exceeds tokens IN the bucket.
Another way to think of this is that you turn on a water faucet at a set rate (liters per second) and place a bucket under. You may empty the bucket into your baby pool or other cistern (consume water from token bucket) at a rate of no more than the rate at which water is flowing into the bucket. If you wait too long while the bucket is filling under the faucet, the extra water (tokens) will be lost (wasted/thrown away) due to the fixed size of the bucket. Since packets are measured in fixed bytes, we can compare a byte to a fixed size droplet of water - the token bucket has a maximum capacity measured in number of water droplets (tokens).
Does this help? See the Cisco article I linked to as well.