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.
As a meter
Jonathan S. Turner is credited with the original description of the leaky bucket algorithm and describes it as follows: "A counter associated with each user transmitting on a connection is incremented whenever the user sends a packet and is decremented periodically. If the counter exceeds a threshold upon being incremented, the network discards the packet. 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)". 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.
Another description of what is essentially the same meter version of the algorithm, the generic cell rate algorithm, is given by the ITU-T in recommendation I.371 and in the ATM Forum's UNI specification. The description, in which the term cell is equivalent to packet in Turner's description is given by the ITU-T as follows: "The continuous-state leaky bucket can be viewed as a finite capacity bucket whose real-valued content drains out at a continuous rate of 1 unit of content per time unit and whose content is increased by the increment T for each conforming cell... If at a cell arrival the content of the bucket is less than or equal to the limit value τ, then the cell is conforming; otherwise, the cell is non-conforming. The capacity of the bucket (the upper bound of the counter) is (T + τ)". These specifications also state that, due to its finite capacity, if the contents of the bucket at the time the conformance is tested is greater than the limit value, and hence the cell is non-conforming, then the bucket is left unchanged; that is, the water is simply not added if it would make the bucket overflow.
David E. McDysan and Darrel L. Spohn provide a commentary on the description given by the ITU-T/ATM Forum. In this, they state, "In the leaky bucket analogy, the [ATM] cells do not actually flow through the bucket; only the check for conforming admission does". However, uncommonly in the descriptions in the literature, McDysan and Spohn also refer to the leaky bucket algorithm as a queue, going on, "Note that one implementation of traffic shaping is to actually have the cells flow through the bucket".
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". 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 τ.
The difference between the descriptions given by Turner and the ITU-T/ATM Forum is that Turner's is specific to traffic policing, whereas the ITU-T/ATM Forum description is applicable to both traffic policing and traffic shaping. Also, Turner does not state that the contents of the counter should only be affected by conforming packets, and should only be incremented when this would not cause it to exceed a limit, i.e. Turner does not explicitly state that the bucket's capacity or counter's maximum value is finite.
Concept of operation A description of the concept of operation of the leaky bucket algorithm as a meter that can be used in either traffic policing or traffic shaping may be described as a fixed capacity bucket, associated with each virtual connection or user. The bucket leaks at a fixed rate. If the bucket is empty, it stops leaking. For a packet to conform, it has to be possible to add a specific amount of water to the bucket. The specific amount added by a conforming packet can be the same for all packets or can be proportional to the length of the packet. If this amount of water would cause the bucket to overflow, then the packet does not conform, and the water in the bucket is left unchanged.
Uses The leaky bucket as a meter can be used in either traffic shaping or traffic policing. 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. In traffic policing, cells that do not conform to these limits (nonconforming cells) may be dropped or may be reduced in priority for downstream traffic management functions to drop if there is congestion. In traffic shaping, cells are delayed until they conform. Traffic policing and traffic shaping are commonly used in UPC and NPC to protect the network against excess or excessively bursty traffic. (See bandwidth management and congestion avoidance.) Traffic shaping is commonly used in the network interfaces in hosts to prevent transmissions from exceeding the bandwidth or jitter limits and being discarded by traffic management functions in the network. (See scheduling (computing) and network scheduler.)
The leaky bucket algorithm as a meter can also be used in a leaky bucket counter to measure the rate of random (stochastic) processes. 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. For example, such a leaky bucket counter can be used to detect when there is a sudden burst of correctable memory errors or when there has been a gradual, but significant, increase in the average rate, which may indicate an impending correction failure.
The use of the leaky bucket algorithm in a leaky bucket counter is similar to that in traffic management, in that it is used as a meter. Essentially, the events replace the packets in the description, with each event causing a quantity of water to be added to the bucket. If the bucket would overflow, as a result of the event, then the event should trigger the action associated with an out-of-limits event. Some implementations seem to parallel Turner's description, 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.
Parameters In the case of the leaky bucket algorithm as a meter, the limits on the traffic can be bandwidth and the burstiness of the output. The bandwidth limit and burstiness limit for the connection may be specified in a traffic contract. A bandwidth limit may be specified as a packet rate, a bit rate, or as an emission interval between the packets. 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 .
Emission interval