IGNOU MCA 4th Semester

MCS-042

Explain the operation of leaky and token bucket algorithms?

The Token Bucket(Leaky Bucket) Model

This is introduction and basic explanation of  the model, it is not completed . First part is similar to the document which submitted by Dr. Chimento. The other parts briefly explain the idea.

This document tries to explain basic token bucket model(some document use leaky bucket), its parameters and its usage in diffserv environment. Token bucket represents the  Policing function of  Traffic Conditioning Block of diffserv. A token bucket flow is defined by (r,b), r denotes the rate at which tokens(credits) are accumulated and b is the depth of the token pool(in bytes).

 

                                                           

b

     

 

Token wait

Packets

                                                                                                                                  

 

As it shown above the new token are adding to the bucket at rate of r tokens/sec, the maximum token can be accumulated is b bytes. If the bucket is full, the incoming tokens will be thrown away. The Token Bucket(TB) profile  contains three parameters: an average rate, a peak rate, and burst size. Lets look at the meaning of these parameters:

Average rate: The network may wish to limit the long-term average rate at which a flow’s packets can be sent into the network. The important point here is the interval of time over which the average rate will be policed.  For example; a flow which has 10000 packets/sec is more flexible than a flow which has 10 packets/msec. Even though both have the same average rate, their behaviors are different. The flow which has 10000 packets/sec can send 100 packets in a one msec long-term, but the flow which has 10 packets/msec cannot sent 100 packets in a one msec long-term. This is one of the important feature we should consider.

Peak rate: Defines the maximum rate at which packets can be sent in short interval time. In above example; even though the flow’s long term average rate is 10000 packets/sec peak rate can be limited to 200 packets/msec.

Burst size: Burst size is the maximum number of packets which can be transmitted extremely in a short interval time. In other word, when time interval approaches zero, the burst size limits the number of packets which can be transmitted to the network. when we don’t consider time interval as zero, burst size depends on  bucket depth b, and maximum speed of output link . We will clarify in the next section in more detail.

In any interval t  [S,S+t], let say in time S, and the number of tokens in the bucket are a(a<=b), and during time interval [S,S+t] the counter accumulate rt tokens more. The total number of tokens available for source to transmit packets is a+rt, (a+rt<=b+rt). When the bucket size is b and during interval time [S,S+t], b+rt tokens accumulated. In this case bucket gets empty by the maximum rate of output link. If we call maximum speed of output  B.  The time which buckets gets empty b+rt=Bt  è t=b/(B-r). Choosing all these parameters can be a bit tricky. One of the potential problem with token bucket is it allows burst again. If another burst come during this time interval, it cannot be handled, or in the case of bursts come very often the output speed will be maximum for the period of burst which can cause congestion. This problem can be reduced by carefully choosing parameters.

Essentially, the network has to simulate the algorithm and make sure that no more packets or bytes are being sent than are permitted. Depends on the agreements the excess packets can be dropped, remarked etc.

When we concern about delay and reliability, we could think some other aspects of the parameters. If we consider single flow, delay can be expressed as

Delay=b/R+C/R +D  R is the maximum transmit rate of  output link, D is non-rate-dependent delay, C is the delay which depends on flow transmission rate. C and D are local parameters. The delay in node must be less than the above value[6].  The end-to-end delay for this flow is the sum of all the delay through the route.

The leaky bucket is an algorithm used in packet switched computer networks and telecommunications networks to check that data transmissions conform to defined limits on bandwidth and burstiness (a measure of the unevenness or variations in the traffic flow). The leaky bucket algorithm is also used in leaky bucket counters, e.g. to detect when the average or peak rate of random or stochastic events orstochastic processes exceed defined limits.

The Leaky Bucket Algorithm is based on an analogy of a bucket (figure 1) that has a hole in the bottom through which any water it contains will leak away at a constant rate, until or unless it is empty. Water can be added intermittently, i.e. in bursts, but if too much is added at once, or it is added at too high an average rate, the water will exceed the capacity of the bucket, which will overflow.

There are actually two different methods of applying this analogy described in the literature . These give what appear to be two different algorithms, both of which are referred to as the leaky bucket algorithm. This has resulted in confusion about what the leaky bucket algorithm is and what its properties are.

In one version , the analogue of the bucket is a counter or variable, separate from the flow of traffic, and is used only to check that traffic conforms to the limits, i.e. the analogue of the water is brought to the bucket by the traffic and added to it so that the level of water in the bucket indicates conformance to the rate and burstiness limits. This version is referred to here as the leaky bucket as a meter. In the second version ^[2], the traffic passes through a queue that is the analogue of the bucket, i.e. the traffic is the analogue of the water passing through the bucket. This version is referred to here as the leaky bucket as a queue. The leaky bucket as a meter is equivalent to (a mirror image of) the token bucket algorithm, and given the same parameters will see the same traffic as conforming or nonconforming. The leaky bucket as a queue can be seen as a special case of the leaky bucket as a meter .