Leaky bucket
In one version the bucket is a counter or variable separate from the flow of traffic or schedule of events.
These packets are then removed from the queue (first come, first served), usually at a fixed rate, e.g. for onward transmission, equivalent to water leaking from the bucket.
This configuration imposes conformance rather than checking it, and where the output is serviced at a fixed rate (and where the packets are all the same length), the resulting traffic stream is necessarily devoid of burstiness or jitter.
The user specifies the rate at which the counter is decremented (this determines the average bandwidth) and the value of the threshold (a measure of burstiness)".
[2] The bucket (analogous to the counter) is, in this case, used as a meter to test the conformance of packets, rather than as a queue to directly control them.
[6] In describing the operation of the ITU-T's version of the algorithm, McDysan and Spohn invoke a "notion commonly employed in queueing theory of a fictional gremlin".
[6] This gremlin inspects the level in the bucket and takes action if the level is above the limit value τ: in traffic policing, it pulls open a trap door, which causes the arriving packet to be dropped and stops its water from entering the bucket; in traffic shaping, it pushes up a flap, which delays the arriving packet and prevents it from delivering its water, until the water level in the bucket falls below τ.
For example, in ATM networks, in the form of the generic cell rate algorithm, it is used to compare the bandwidth and burstiness of traffic on a virtual channel (VC) or virtual path (VP) against the specified limits on the rate at which cells may arrive and the maximum jitter, or variation in inter-arrival intervals, for the VC or VP.
A Leaky bucket counter can be used to indicate, by its overflowing when the average or peak rate of events increases above some acceptable background level.
Some implementations[8] seem to parallel Turner's description,[2] in that there is no explicit limit on the maximum value that the counter may take, implying that once the counter has exceeded the threshold, it may not return to its previous state until a period significantly greater than the equivalent of the emission interval has passed, which may be increased by what would otherwise be conforming events.
However, other implementations may not increment the counter while it is overflowed, allowing it to correctly determine whether the following events conform or not.
In the case of the leaky bucket algorithm as a meter, the limits on the traffic can be bandwidth and a burstiness of the output.
A limit on burstiness may be specified as a delay variation tolerance, or as a maximum burst size (MBS).
Multiple sets of contract parameters can be applied concurrently to a connection using multiple instances of the leaky bucket algorithm, each of which may take a bandwidth and a burstiness limit: see Generic cell rate algorithm § Dual Leaky Bucket Controller.
Consider a bucket that is exactly filled to the top by preceding traffic, i.e. when the maximum permitted burstiness has already occurred, i.e. the maximum number of packets or cells have just arrived in the minimum amount of time for them to still conform to the bandwidth and jitter limits.
Also, during the time the maximum burstiness occurs, packets can arrive at smaller intervals and thus at a higher rate than this.
Assuming that the sum of the bandwidths of these connections is less than the capacity of the output, all of the packets that arrive can be transmitted eventually.
Assuming that each packet takes δ to arrive, then if τ (expressed as the time it takes the bucket to empty from the limit value) is equal to or greater than the emission interval less the minimum interarrival time, T – δ, the second packet will conform even if it arrives as a burst with the first.
The maximum size of this burst, M, can be calculated from the emission interval, T; the maximum jitter tolerance, τ; and the time taken to transmit/receive a packet, δ, as follows:[4] Equally, the minimum value of jitter tolerance τ that gives a specific MBS can be calculated from the MBS as follows:[4] In the case of ATM, where technically MBS only relates to the SCR tolerance, in the above equation the time it takes each packet to arrive, δ, is the emission interval for cells at the PCR TPCR, and the emission interval, T, is the emission interval for the SCR TSCR.
Where MBS is to be the number of cells required to transport a segmented packet, the limit value in the above, τ, should be that for the SCR τSCR.
A description of it is given by Andrew S. Tanenbaum, in (an older version of) his book Computer Networks as "The leaky bucket consists of a finite queue.
To underline this, Tanenbaum also states that "The leaky bucket algorithm enforces a rigid output pattern at the average rate, no matter how bursty the [input] traffic is.
When the counter drops below the length of the next packet on the queue, transmission stops until the next tick, at which time the residual byte count is reset [to n] and the flow can continue".
[3] As with the version for fixed length packets, this implementation has a strong effect on the phase of transmissions, resulting in variable end-to-end delays, and unsuitability for real-time traffic shaping.
The leaky bucket as a queue can only be used in shaping traffic to a specified bandwidth with no jitter in the output.
Leaky bucket algorithm is used in Nginx's ngx_http_limit_conn_module module for limiting the number of concurrent connections originating from a single IP address.
Because it transmits packets only at fixed intervals, there will be many instances when the traffic volume is very low and large portions of network resources (bandwidth in particular) are not being used.
Imagine also that the bucket in this meter has a depth equal to the amount added by a packet, i.e. has a limit value, τ, of zero.
The suggested implementation[3] can, like the fixed length implementation, be seen as traffic shaping function in which the queue is a delay element, rather than the bucket, and the function that services the queue is, in this case, explicitly given as a token bucket: it is decremented for conforming packets and incremented at a fixed rate.
Hence, it is possible to quantify the burstiness of the output of this "byte counting" leaky bucket as a meter, unless all packets are of the maximum length when it becomes pointless.
