User's Manual

UTT Technologies Chapter 10 QoS
http://www.uttglobal.com Page 258
10.1.2 Token Bucket Algorithm
As bandwidth management feature provided by the UTT products is based on token
bucket algorithm, this section describe token bucket in brief.
Token bucket algorithm is one of the most common algorithms which are used for network
traffic shaping and rate limiting. Typically, token bucket algorithm is used to control the
amount of data injected into a network, and it allows bursts of data to be sent.
The token bucket is a control mechanism that dictates when traffic can be transmitted,
based on the presence of tokens in the bucket. The bucket contains tokens, each of which
can represent a byte. If tokens are present, traffic can be transmitted; else, traffic cannot
be transmitted. Therefore, if the burst threshold is configured appropriately and there are
adequate tokens in the bucket, traffic can be transmitted in its peak burst rate.
The basic process of token bucket algorithm is as follows:
Ɣ The token rate is r, that is, a token is added to the bucket every 1/ r seconds.
Ɣ The bucket can hold at the most ȕ tokens. If a token arrives when the bucket is full, it
is discarded.
Ɣ When a packet of n bytes arrives, n tokens are removed from the bucket, and the
packet is sent to the network.
Ɣ If fewer than n tokens are available, no tokens are removed from the bucket, and the
packet is considered to be non-conformant.
Ɣ Although the algorithm allows for the burst of up to ȕ bytes of traffic, over the long run
the output of conformant packets is limited by the constant rate, r.
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.
In conclusion, the token bucket algorithm allows bursts of up to ȕ bytes, but over the long
run the output of conformant packets is limited to the constant rate, r.