See Our team

Wondering how we keep quality?

Got unsolved questions?

Ask Questions

## Explain leaky bucket algorithm.

Related to computer networks.By:Purnima

Taged users:

|Aparna-Dasgupta

Likes:

|milan-ransingh|leo

Dislikes:

Be first to dislike this question

Talk about thisDelete|Like|Dislike|

## Answers

o understand this concept first we have to know little about traffic shaping.**Traffic Shaping :**This is a mechanism to control the amount and the rate of the traffic sent to the network.

Two techniques can shape traffic:

- Leaky Bucket
- Token Bucket.

Suppose we have a bucket in which we are pouring water in a random
order but we have to get water in a fixed rate , for this we will make a
hole at the bottom of the bucket. It will ensure that water coming out
is in a some fixed rate . And also if bucket will full we will stop
pouring in it.

The input rate can vary, but the output rate remains constant.
Similarly, in networking, a technique called leaky bucket can smooth out
bursty traffic. Bursty chunks are stored in the bucket and sent out at
an average rate.

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 10 s. 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.

A simple leaky bucket algorithm can be implemented using FIFO queue. 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 size. Repeat this step until n is smaller than the packet size.
- Reset the counter and go to step 1.

harshshah822

Likes:

Be first to like this answer

Dislikes:

Be first to dislike this answer

Talk about this|Once you have earned teacher badge you can edit this questionDelete|Like|Dislike|

------------------------------------

**The leaky bucket algorithm is a method of temporarily storing a variable number of requests and organizing them into a set-rate output of packets in an asynchronous transfer mode (ATM) network.**

**The leaky bucket is used to implement traffic policing in Ethernet**** and cellular data networks. The **algorithm** can also be used to control metered-**bandwidth** Internet connections to prevent going over the allotted bandwidth for a month, thereby avoiding extra charges.**

**The algorithm works similarly to the way an actual leaky bucket holds water: The leaky bucket takes data and collects it up to a maximum capacity. Data in the bucket is only released from the bucket at a set rate and size of packet. When the bucket runs out of data, the leaking stops. If incoming data would overfill the bucket, then the packet is considered to be non-conformant and is not added to the bucket. Data is added to the bucket as space becomes available for conforming packets.The leaky bucket algorithm can also detect both gradually increasing and dramatic memory error increases by comparing how the average and peak data rates exceed set acceptable background amounts.**

**In a broader context, the leaky bucket is an analogy for describing how inputs and outputs work in a wide variety of business and technology systems.**

mmodi1995

Likes:

Be first to like this answer

Dislikes:

Be first to dislike this answer

Talk about this|Once you have earned teacher badge you can edit this questionDelete|Like|Dislike|

------------------------------------

## Use Me ?