The Single Token Bucket

Essentially a Token Bucket is a meter. It is used to measure the amount of information transmitted by a certain data flow. When coupled with an algorithmic dropper it becomes a policer, and it is a means of bandwidth enforcement.

The token bucket has two parameters:

• token accumulation rate           
• burst tolerance                         

With the single token bucket, the token accumulation rate is often called Committed Information Rate (CIR), to distinguish it from combined meters that have multiple buckets and token sources.

Tokens represent equivalents of traffic volume. They are most commonly defined in bytes. In ATM it is often defined in cells because cells have constant size.

The bucket stores tokens, never actual data. Tokens accumulate at constant pace until the bucket is full. Tokens are removed when traffic arrives to the meter, and exactly an amount that corresponds to the size of the packet.

Tokens are removed at infinite speed. Packets that arrive to the meter at a moment when there are sufficient tokens in the bucket corresponding to its the size are declared ‘Conforming’ or ‘In Profile’.

The Single Token Bucket Policer

The combination of a token bucket meter and an algorithmic dropper forms the Single Token Bucket Policer. It represents a means to enforce an upper bound on the amount of traffic a source or a port is allowed to transmit over any specified time interval.

The operation of the policer is as follows:

Data packets that arise from the source reach the metering point of the token bucket. At that time instance a comparison is done between the size of the packet and the available tokens in the bucket.

If there are sufficient tokens corresponding to the size of the packet then the packet is tagged ‘conformant’ and equivalent amount of tokens are removed from the bucket. The subsequent dropper will allow this packet to continue into the network.

If there are insufficient tokens corresponding to the size of the packet, then the packet is tagged ‘non conforming’ and no tokens are removed from the bucket. The subsequent algorithmic dropper discards the packet.

Tokens accumulate at constant pace, which is equal to CIR bits/sec. As long as the amount of tokens does not exceed the bucket depth tokens are accumulated, otherwise tokens are lost. The term ‘overflow’ or ‘overspill’ is often used to depict this situation.

The Token Bucket Policer does not involve queuing. Policing is executed on data flows ‘on the fly’. Typically in network devices a policing stage is followed by a queuing stage, although egress policing (after the egress queuing stage) also exists, mainly when policing is applied on an aggregate, such as traffic belonging to subscribers of an ISP over a wholesaler’s network gear.

By convention, a token bucket starts full at time zero.

The traffic envelope enforced by a single token bucket can be illustrated with arrival curves. The thin black curve illustrates the cumulative amount of bytes transmitted by the source. The arrival curve is a non-decreasing function that is incremented each time a new packet is passed by the policer by the amount of bytes in the packet.

A source can ‘burst’ at time zero at infinite speed at most CBS bytes. Then packet by packet it can send only at CIR bits/sec. When the source remains idle tokens accumulate in the bucket. As long as the bucket does not overflow, the idle ‘credits’ can be recovered by the source via sending packets later at a pace faster than CIR bits/sec. However, if the source remains idle too long (period ‘a’) tokens will overflow and the source can never recover those.

The constraining envelope (CBS, CIRxt) remains valid at each moment in time, thus tokens lost in period ‘a’ cannot be recovered and the cumulative units of bytes transmitted by the source will never reach again their original envelope.  At period ‘b’ the policer kicks in and discards packets that are above the permitted envelope.

In software implementation it is sufficient to update the token count upon packet arrival. This will save processing time vs updating the token count at regular intervals. At each arrival event first the token count is updated, and eventual overspilling is removed. Then the match for the packet size is executed and eventual further tokens removed according to the packet size.