CISCO EXPLANATION ABOUT TOKEN BUCKET ALGORITHM

CISCO EXPLANATION ABOUT TOKEN BUCKET ALGORITHM

This information was taken from Cisco at:

http://www.cisco.com/en/US/products/sw/iosswrel/ps1835/products_command_reference_chapter09186a0080087f42.html#1064737.

Examples

Token Bucket Algorithm with One Token Bucket

The token bucket algorithm for the police command that was introduced in Cisco IOS Release 12.0(5)XE is different from the token bucket algorithms introduced in Cisco IOS Release 12.1(5)T. The following example is for the token bucket algorithm with one token bucket introduced in Cisco IOS Release 12.1(5)T.

If the violate-action option is not specified when you configure a policy with the police command in Cisco IOS Release 12.1(5)T onward, the token bucket algorithm uses one token bucket. If the violate-action option is specified, the token bucket algorithm uses two token buckets. In the following example, the violate-action option is not specified, so the token bucket algorithm only uses one token bucket.

The following configuration shows users how to define a traffic class (using the class-map command) and associate the match criteria from the traffic class with the Traffic Policing configuration, which is configured in the service policy (using the policy-map command). The service-policy command is then used to attach this service policy to the interface.

In this particular example, Traffic Policing is configured with the average rate at 8000 bits per second and the normal burst size at 1000 bytes for all packets leaving Fast Ethernet interface 0/0:

Router(config)# class-map access-match

Router(config-cmap)# match access-group 1

Router(config-cmap)# exit

Router(config)# policy-map police-setting

Router(config-pmap)# class access-match

Router(config-pmap-c)# police 8000 1000 conform-action transmit exceed-action drop

Router(config-pmap-c)# exit

Router(config-pmap)# exit

Router(config)# interface fastethernet 0/0

Router(config-if)# service-policy output police-setting

The treatment of a series of packets leaving Fast Ethernet interface 0/0 depends on the size of the packet and the number of bytes remaining in the conform bucket. These packets are policed based on the following rules:

· Tokens are updated in the conform bucket. If the previous arrival of the packet was at t1 and the current time is t, the bucket is updated with T -T1 worth of bits based on the token arrival rate. The token arrival rate is calculated as follows:

(time between packets<which is equal to T - T1> * policer rate)/8 bytes

· If the number of bytes in the conform bucket B is greater than or equal to 0, the packet conforms and the conform action is taken on the packet. If the packet conforms, B bytes are removed from the conform bucket and the conform action is completed for the packet.

· If the number of bytes in the conform bucket B is fewer than 0, the exceed action is taken.

In this example, the initial token buckets starts full at 1000 bytes. If a 450-byte packet arrives, the packet conforms because enough bytes are available in the conform token bucket. The conform action (send) is taken by the packet and 450 bytes are removed from the conform token bucket (leaving 550 bytes).

If the next packet arrives 0.25 seconds later, 250 bytes are added to the token bucket ((0.25 * 8000)/8), leaving 800 bytes in the token bucket. If the next packet is 900 bytes, the packet exceeds and the exceed action (drop) is taken. No bytes are taken from the token bucket.

Token Bucket Algorithm with Two Token Buckets Example

If the violate-action option is specified when you configure a policy with the police command in Cisco IOS Release 12.1(5)T onward, the token bucket algorithm uses two token buckets. The following example uses the token bucket algorithm with two token buckets.

In this particular example, Traffic Policing is configured with the average rate at 8000 bits per second, the normal burst size at 1000 bytes, and the excess burst size at 1000 bytes for all packets leaving Fast Ethernet interface 0/0.

Router(config)# class-map access-match

Router(config-cmap)# match access-group 1

Router(config-cmap)# exit

Router(config)# policy-map police-setting

Router(config-pmap)# class access-match

Router(config-pmap-c)# police 8000 1000 1000 conform-action transmit exceed-action set-qos-transmit 1 violate-action drop

Router(config-pmap-c)# exit

Router(config-pmap)# exit

Router(config)# interface fastethernet 0/0

Router(config-if)# service-policy output police-setting

The treatment of a series of packets leaving Fast Ethernet interface 0/0 depends on the size of the packet and the number of bytes remaining in the conform and exceed token buckets. The series of packets are policed based on the following rules:

· If the previous arrival of the packet was at T1 and the current arrival of the packet is at T, the bucket is updated with T -T1 worth of bits based on the token arrival rate. The refill tokens are placed in the conform bucket. If the tokens overflow the conform bucket, the overflow tokens are placed in the exceed bucket. The token arrival rate is calculated as follows:

(time between packets<which is equal to T - T1> * policer rate)/8 bytes

· If the number of bytes in the conform bucket B is less than 0, the excess token bucket is checked for bytes by the packet. If the number of bytes in the exceed bucket - B is greater than or equal to 0, the exceed action is taken and B bytes are removed from the exceed token bucket. No bytes are removed from the conform bucket in this scenario.

· If the number bytes in the exceed bucket B is fewer than 0, the packet violates the rate and the violate action is taken. The action is complete for the packet.

If the next packet arrives 0.25 seconds later, 250 bytes are added to the conform token bucket ((0.25 * 8000)/8), leaving 800 bytes in the conform token bucket. If the next packet is 900 bytes, the packet does not conform because only 800 bytes are available in the conform token bucket.

The exceed token bucket, which starts full at 1000 bytes (as specified by the excess burst size) is then checked for available bytes. Because enough bytes are available in the exceed token bucket, the exceed action (set the QoS transmit value of 1) is taken and 900 bytes are taken from the exceed bucket (leaving 100 bytes in the exceed token bucket.

If the next packet arrives 0.40 seconds later, 400 bytes are added to the token buckets ((.40 * 8000)/8). Therefore, the conform token bucket now has 1000 bytes (the maximum number of tokens available in the conform bucket) and 200 bytes overflow the conform token bucket (because it only 200 bytes were needed to fill the conform token bucket to capacity). These overflow bytes are placed in the exceed token bucket, giving the exceed token bucket 300 bytes.

If the arriving packet is 1000 bytes, the packet conforms because enough bytes are available in the conform token bucket. The conform action (transmit) is taken by the packet and 1000 bytes are removed from the conform token bucket (leaving 0 bytes).

If the next packet arrives 0.20 seconds later, 200 bytes are added to the token bucket ((.20 * 8000)/8). Therefore, the conform bucket now has 200 bytes. If the arriving packet is 400 bytes, the packet does not conform because only 200 bytes are available in the conform bucket. Similarly, the packet does not exceed because only 300 bytes are available in the exceed bucket. Therefore, the packet violates and the violate action (drop) is taken.