Traffic shaping is a mechanism to control the amount and the rate of traffic sent to the  network. Two techniques can shape traffic: leaky bucket and token bucket.

Leaky Bucket


If a bucket has a small hole at the bottom, the water leaks from the bucket at a constant rate as long as there is water in the bucket. The rate at which the water leaks does not depend on the rate at which the water is input to the bucket unless the bucket is empty. The input rate can vary, but the output rate remains constant. Similarly, in networking, a technique called leaky bucket can smooth out burst traffic. Bursty chunks are stored in the bucket and sent out at an average rate. The figure shows a leaky bucket and its effects.

                   

In the figure, we assume that the network has committed a bandwidth of 3 Mbps for a host. The use of the leaky bucket shapes the input traffic to make it conform to this commitment. In Figure the host sends a burst of data at a rate of 12 Mbps for 2 s, for a total of 24 Mbits of data. The host is silent for 5 s and then sends data at a rate of 2 Mbps for 3 s, for a total of 6 Mbits of data. In all, the host has sent 30 Mbits of data in l0s. The leaky bucket smooths the traffic by sending out data at a rate of 3 Mbps during the same 10 s. Without the leaky bucket, the beginning burst may have hurt the network by consuming more bandwidth than is set aside for this host. We can also see that the leaky bucket may prevent congestion.

                       

                                                          Leaky Bucket Implementation

A simple leaky bucket implementation is shown in Figure. A FIFO queue holds the packets. If the traffic consists of fixed-size packets (e.g., cells in ATM networks), the process removes a fixed number of packets from the queue at each tick of the clock. If the traffic consists of variable-length packets, the fixed output rate must be based on the number of bytes or bits.

 

The following is an algorithm for variable-length packets:

  • Initialize a counter to n at the tick of the clock.
  • If n is greater than the size of the packet, send the packet and decrement the counter by the packet Repeat this step until n is smaller than the packet size.
  • Reset the counter and go to step

 

A leaky bucket algorithm shapes bursty traffic into fixed-rate traffic by averaging the data rate. It may drop the packets if the bucket is full.

 

Token Bucket Algorithm

The leaky bucket algorithm described above, enforces a rigid pattern at the output stream, irrespective of the pattern of the input. For many applications it is better to allow the output to speed up somewhat when a larger burst arrives than to lose the data. Token Bucket algorithm provides such a solution. In this algorithm leaky bucket holds token, generated at regular intervals.

Main steps of this algorithm can be described as follows: ƒ

  • In regular intervals tokens are thrown into the bucket.
  • The bucket has a maximum capacity.
  • If there is a ready packet, a token is removed from the bucket, and the packet is send.
  • If there is no token in the bucket, the packet cannot be send.

The figure shows the two scenarios before and after the tokens present in the bucket have been consumed. In Figure (a), the bucket holds two tokens, and three packets are waiting to be sent out of the interface, in Figure (b) two packets have been sent out by consuming two tokens, and 1 packet is still left.

The token bucket algorithm is less restrictive than the leaky bucket algorithm, in a sense that it allows bursty traffic. However, the limit of burst is restricted by the number of tokens available in the bucket at a particular instant of time.

The implementation of basic token bucket algorithm is simple; a variable is used just to count the tokens. This counter is incremented every t seconds and is decremented whenever a packet is sent. Whenever this counter reaches zero, no further packet is sent out as shown in Figure (c).

             

                                             

TCP Congestion Control

Admission control is one such closed-loop technique, where action is taken once congestion is detected in the network.

Different approaches can be followed:

  • Simpler one being: do not set-up new connections, once the congestion is signaled. This type of approach is often used in normal telephone networks. When the exchange is overloaded, then no new calls are established.
  • Another approach, which can be followed, is: to allow new virtual connections, but route these carefully so that none of the congested router (or none of the problem area) is a part of this route.
  • Yet another approach can be: To negotiate different parameters between the host and the network, when the connection is setup. During the setup time itself, Host specifies the volume and shape of traffic, quality of service, maximum delay and other parameters, related to the traffic it would be offering to the network. Once the host specifies its requirement, the resources needed are reserved along the path, before the actual packet follows.