Leaky bucket
The leaky bucket is an algorithm based on an analogy of how a bucket with a constant 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…
≈ 10 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The leaky bucket is an algorithm based on an analogy of how a bucket with a constant 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. It can be used to determine whether some sequence of discrete events conforms to defined limits on their average and peak rates or frequencies, e.g. to limit the actions associated with these events to these rates or delay them until they do conform to the rates.
It may also be used to check conformance or limit to an average rate alone, i.e. remove any variation from the average. It is used in packet-switched computer networks and telecommunications networks in both the traffic policing, traffic shaping and scheduling of data transmissions, in the form of packets, to defined limits on bandwidth and burstiness (a measure of the variations in the traffic flow).
A version of the leaky bucket, the generic cell rate algorithm, is recommended for Asynchronous Transfer Mode (ATM) networks in UPC and NPC at user–network interfaces or inter-network interfaces or network-to-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.…
The leaky bucket is an algorithm based on an analogy of how a bucket with a constant 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. It can be used to determine whether some sequence of discrete events conforms to defined limits on their average and peak rates or frequencies, e.g. to limit the actions associated with these events to these rates or delay them until they do conform to the rates.
It may also be used to check conformance or limit to an average rate alone, i.e. remove any variation from the average. It is used in packet-switched computer networks and telecommunications networks in both the traffic policing, traffic shaping and scheduling of data transmissions, in the form of packets, to defined limits on bandwidth and burstiness (a measure of the variations in the traffic flow).
A version of the leaky bucket, the generic cell rate algorithm, is recommended for Asynchronous Transfer Mode (ATM) networks in UPC and NPC at user–network interfaces or inter-network interfaces or network-to-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.
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.
Overview
Two different methods of applying this leaky bucket analogy are described in the literature. These give what appear to be two different algorithms, both of which are referred to as the leaky bucket algorithm and generally without reference to the other method. This has resulted in confusion about what the leaky bucket algorithm is and what its properties are.
In one version, the bucket is a counter or variable separate from the flow of traffic or schedule of events. This counter is used only to check that the traffic or events conform to the limits: The counter is incremented as each packet arrives at the point where the check is being made or an event occurs, which is equivalent to the way water is added intermittently to the bucket.
The counter is also decremented at a fixed rate, equivalent to the way the water leaks out of the bucket. As a result, the value in the counter represents the level of the water in the bucket.
If the counter remains below a specified limit value when a packet arrives or an event occurs, i.e., the bucket does not overflow, that indicates its conformance to the bandwidth and burstiness limits or the average and peak rate event limits. This version is referred to here as the leaky bucket as a meter. In the second version, the bucket is a queue in the flow of traffic.
This queue is used to directly control that flow: Packets are entered into the queue as they arrive, equivalent to the water being added to the bucket. 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. So in this version, the traffic itself is the analogue of the water passing through the bucket.
This version is referred to here as leaky bucket as a queue. The leaky bucket as a meter is exactly equivalent to (a mirror image of) the token bucket algorithm, i.e. the process of adding water to the leaky bucket exactly mirrors that of removing tokens from the token bucket when a conforming packet arrives, the process of leaking of water from the leaky bucket exactly mirrors that of regularly adding tokens to the token bucket, and the test that the leaky bucket will not overflow is a mirror of the test that the token bucket contains enough tokens and will not underflow.
Thus, given equivalent parameters, the two algorithms 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.
A burst or clump of packets can arrive at a higher rate than determined by the emission interval T. This may be the line rate of the physical layer connection when the packets in the burst will arrive back-to-back. However, as in ATM, the tolerance may be applied to a lower rate, in that case, the Sustainable Cell Rate (SCR), and the burst of packets (cells) can arrive at a higher rate, but less than the line rate of the physical layer, in that case, the Peak Cell Rate (PCR).
The MBS may then be the number of cells needed to transport a higher layer packet (see Segmentation and reassembly), where the packets are transmitted with a maximum bandwidth determined by the SCR and cells within the packets are transmitted at the PCR; thus allowing the last cell of the packet, and the packet itself, to arrive significantly earlier than it would if the cells were sent at the SCR: transmission duration = (MBS-1)/PCR rather than (MBS-1)/SCR. This bursting at the PCR puts a significantly higher load on shared resources, e.g., switch output buffers, than does transmission at the SCR, and is thus more likely to result in buffer overflows and network congestion.
However, it puts a lesser load on these resources than would transmitting at the SCR with a limit value, τ SCR , that allows MBS cells to be transmitted and arrive back-to-back at the line rate. If the limit value is large enough, then several packets can arrive in a burst and still conform: if the bucket starts from empty, the first packet to arrive will add T, but if, by the time the next packet arrives, the contents is below τ, this will also conform.
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. Similarly, if τ is equal to or greater than (T – δ) × 2, then 3 packets can arrive in a burst, etc. 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: M = \left \lfloor 1 + \frac{\tau}{T - \delta} \right \rfloor Equally, the minimum value of jitter tolerance τ that gives a specific MBS can be calculated from the MBS as follows: \tau = \left (M - 1 \right )\left (T - \delta \right ) 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 T PCR , and the emission interval, T, is the emission interval for the SCR T SCR .
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 . However, at the UNI or an NNI, where cells at the PCR will have been subjected to delay variation, it should be the limit value for the SCR plus that for the PCR τ SCR + τ PCR .
For variable-length packets, the maximum burst size will depend on the lengths of the packets in the burst, and there is no single value for the maximum burst size. However, it is possible to specify the total burst length in bytes, from the byte rate of the input stream, the equivalent byte rate of the leak, and the bucket depth.
See also
Fluid queue Generic cell rate algorithm Traffic contract UPC and NPC
Text derived from https://en.wikipedia.org/w/index.php?oldid=1351218966 under CC BY-SA 4.0; modifications have been made.