Oct 10, 2018

[HDGEM] The leaky bucket is an algorithm that may be used to determine whether some sequence of discrete events conforms to defined limits on their average and peak rates or frequencies.

The leaky bucket is based on an analogy of how a bucket with a leak will overflow if either the average rate at which water is poured in exceeds the rate at which the bucket leaks, or if more water than the capacity of the bucket is poured in all at once.

The leaky bucket algorithm is used in packet switched computer networks and telecommunications networks to check that data transmissions, in the form of packets, conform to defined limits on bandwidth and burstiness (a measure of the unevenness or variations in the traffic flow). It can also be used as a scheduling algorithm to determine the timing of transmissions that will comply with the limits set for the bandwidth and burstiness applied by the network: see network scheduler.

A version of the leaky bucket, the Generic Cell Rate Algorithm, is recommended for Asynchronous Transfer Mode (ATM) networks in Usage/Network Parameter Control at User–Network Interfaces or Inter-Network Interfaces or Network-Network Interfaces to protect a network from excessive traffic levels on connections routed through it. The Generic Cell Rate Algorithm, or an equivalent, may also be used to shape transmissions by a Network Interface Card onto an ATM network (i.e. on the user side of the User-Network Interface), e.g. to levels below the levels set for Usage/Network Parameter Control in the network to prevent it taking action to further limit that connection.

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 or stochastic processes, such as faults or failures, exceed defined limits.

At least some implementations of the leaky bucket are a mirror image of the Token Bucket algorithm and will, given equivalent parameters, determine exactly the same sequence of events to conform or not conform to the same limits. However, there are at least two different descriptions of the leaky bucket that can and have caused confusion.

Posted By Blogger to HDGEM at 3/20/2017 07:05:00 AM