Leaky bucket

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 stated as follows:

• A fixed capacity bucket, associated with each virtual connection or user, 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 exceed its capacity then the packet does not conform and the water in the bucket is left unchanged.

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 discarded (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/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 or stochastic processes. A Leaky bucket counter can be used to detect when the average or peak rate of events increases above some, acceptable, background level, i.e. when the bucket overflows.[8] However, events that do not cause an overflow, i.e. have sufficiently low rates and are well distributed over time, can be ignored. 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 failure,[9] etc.

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[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.[4][5][note 3]

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 or frame rate, a byte or bit rate, or as an emission interval between the packets. A limit on burstiness may be specified as a jitter or 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.

The rate at which the bucket leaks will determine the bandwidth limit, which is referred to as the average rate by Turner[2] and the inverse of which is referred to as the emission interval by the ITU-T. It is easiest to explain what this interval is where packets have a fixed length. Hence, the first part of this description assumes this, and the implications of variable packet lengths are considered separately.

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. The minimum interval before the next packet can conform is then the time it takes for the bucket to leak exactly the amount of water delivered by a packet, and if a packet is tested and conforms at that time, this will exactly fill the bucket once more. Thus, once the bucket is filled, the maximum rate that packets can conform is with this interval between each packet.

Turner[2] refers to this rate as the average, implying that its inverse is the average interval. There is, however, some ambiguity in what the average rate and interval are. Since packets can arrive at any lower rate, this is an upper bound, rather than a fixed value, so it could at best be called the maximum for the average rate. Also, during the time the maximum burstiness occurs, packets can arrive at smaller intervals and thus at a higher rate than this. So, for any period less than infinity, the actual average rate can be (but isn't necessarily) greater than this and the average interval can be (but isn't necessarily) less than the emission interval. Hence, because of this ambiguity, the term emission interval is used hereafter. However, it is still true that the minimum value that the long-term average interval can take tends to be the emission interval.

For variable-length packets, where the amount added to the bucket is proportional to the packet length, the maximum rate at which they can conform varies according to their length: the amount that the bucket must have leaked from full for a packet to conform is the amount the packet will add, and if this is proportional to the packet length, so is the interval between it and the preceding packet that filled the bucket. Hence, it is not possible to specify a specific emission interval for variable-length packets, and the bandwidth limit has to be specified explicitly, in bits or bytes per second.

It is easiest to explain what this tolerance is where packets have a fixed length. Hence, the first part of this description assumes this, and the implications of variable packet lengths are considered separately.

The ITU-T defines a limit value, τ, that is less than the capacity of the bucket by T (the amount by which the bucket contents is incremented for each conforming cell), so that the capacity of the bucket is T + τ. This limit value specifies how much earlier a packet can arrive than it would normally be expected if the packets were arriving with exactly the emission interval between them.

Imagine the following situation: A bucket leaks at 1 unit of water per second, so the limit value, τ and the amount of water added by a packet, T, are effectively in units of seconds. This bucket starts off empty, so when a packet arrives at the bucket, it does not quite fill the bucket by adding its water T, and the bucket is now τ below its capacity. So when the next packet arrives the bucket only has to have drained by T – τ for this to conform. So the interval between these two packets can be as much as τ less than T.

This extends to multiple packets in a sequence: Imagine the following: The bucket again starts off empty, so the first packet to arrive must conform. The bucket then becomes exactly full after a number of conforming packets, N, have arrived in the minimum possible time for them to conform. For the last (the Nth) packet to conform, the bucket must have leaked enough of the water from the preceding N – 1 packets ((N – 1) * T seconds' worth) for it to be exactly at the limit value τ at this time. Hence, the water leaked is (N – 1)T – τ, which because the leak is one unit per second, took exactly (N – 1)T – τ seconds to leak. Thus the shortest time in which all N packets can arrive and conform is (N – 1)T – τ seconds, which is exactly τ less than the time it would have taken if the packets had been arriving at exactly the emission interval.

However, packets can only arrive with intervals less than T where the bucket is not filled by the previous packet. If it is, then the bucket must have drained by the full amount T before the next packet conforms. So once this tolerance has been used up by packets arriving at less than T, subsequent frames must arrive at intervals no less than T. They may, however, arrive at greater intervals, when the bucket will not be filled by them. When this has happened, packets may, again, arrive with intervals less than T until the tolerance is again used up. However, since the bucket stops leaking when it is empty, there is always a limit (τ) to how much tolerance can be accrued by these intervals greater than T, however, much greater than T they may be or, however, many of them there are.

Since the limit value τ defines how much earlier a packet can arrive than would be expected, it is the limit on the difference between the maximum and minimum delays from the source to the point where the conformance test is being made (assuming the packets are generated with no jitter). Hence, the use of the term Cell Delay Variation tolerance (CDVt) for this parameter in ATM.

As an example, a possible source of delay variation is where a number of connections (streams of packets) are multiplexed together at the output of a switch. Assuming that the sum of the bandwidths of these connections is less than that of the output, all of the packets that arrive can be transmitted, eventually. However, if their arrivals are independent, e.g. because they arrive at different inputs of the switch, then several may arrive at or nearly at the same time. Since the output can only transmit one packet at a time, the others must be queued in a buffer until it is their turn to be transmitted. This buffer then introduces an additional delay between a packet arriving at an input and being transmitted by the output, and this delay varies, depending on how many other packets are already queued in the buffer. A similar situation can occur at the output of a host (in the NIC) when multiple packets have the same or similar release times, and this delay can usually be modelled as a delay in a virtual output buffer.

For variable length packets, where the amount of water added by a given packet is proportional to its length, τ can't be seen as a limit on how full the bucket can be when a packet arrives, as this varies depending on the packet size. However, the time it takes to drain from this level to empty is still how much earlier a packet can arrive than is expected, when packets are transmitted at the bandwidth limit. Thus, it is still the maximum variation in transfer delay to the point where the conformance test is being applied that can be tolerated, and thus the tolerance on maximum delay variation.

The limit value or delay variation tolerance also controls how many packets can arrive in a burst, determined by the excess depth of the bucket over the capacity required for a single packet. Hence MBS is also a measure of burstiness or jitter, and it is possible to specify the burstiness as an MBS and derive the limit value τ from this or to specify it as a jitter/delay variation tolerance/limit value, and derive the MBS from this.

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:[4]

${\displaystyle 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:[4]

${\displaystyle \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.

The leaky bucket algorithm is sometimes contrasted with the token bucket algorithm. However, the above concept of operation for the leaky bucket as a meter may be directly compared with the token bucket algorithm, the description of which is given in that article as the following:

• A token is added to the bucket every 1/r seconds.

• The bucket can hold at the most b tokens. If a token arrives when the bucket is full, it is discarded.

• When a packet (network layer PDU) [sic][note 1] of "n" bytes arrives, n tokens are removed from the bucket, and the packet is sent to the network.

• If fewer than n tokens are available, no tokens are removed from the bucket, and the packet is considered to be non-conformant.

This can be compared with the concept of operation, repeated from above:

• A fixed capacity bucket, associated with each virtual connection or user, 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 exceed its capacity then the packet does not conform and the water in the bucket is left unchanged.

As can be seen, these two descriptions are essentially mirror images of one another: one adds something to the bucket on a regular basis and takes something away for conforming packets down to a limit of zero; the other takes away regularly and adds for conforming packets up to a limit of the bucket's capacity. So, is an implementation that adds tokens for a conforming packet and removes them at a fixed rate an implementation of the leaky bucket or of the token bucket? Similarly, which algorithm is used in an implementation that removes water for a conforming packet and adds water at a fixed rate? In fact both are effectively the same, i.e. implementations of both the leaky bucket and token bucket, as these are the same basic algorithm described differently. This explains why, given equivalent parameters, the two algorithms will see exactly the same packets as conforming or nonconforming. The differences in the properties and performance of implementations of the leaky and token bucket algorithms thus result entirely from the differences in the implementations, i.e. they do not stem from differences in the underlying algorithms.

The points to note are that the leaky bucket algorithm, when used as a meter, can allow a conforming output packet stream with jitter or burstiness, can be used in traffic policing as well as shaping, and can be implemented for variable-length packets.

The leaky bucket as a queue can only be used in shaping traffic to a specified bandwidth with no jitter in the output.[10] It may be used within the network, e.g. as part of bandwidth management, but is more appropriate to traffic shaping in the network interfaces of hosts. 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.[11]

In the case of the leaky bucket algorithm as a queue, the only defined limit for this algorithm is the bandwidth of its output.[10][note 3]

The bandwidth limit for the connection may be specified in a traffic contract. A bandwidth limit may be specified as a packet or frame rate, a byte or bit rate, or as an emission interval between the packets.

The implementation of the leaky bucket as a queue does not use available network resources efficiently. 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. Therefore no mechanism exists in the leaky-bucket implementation as a queue to allow individual flows to burst up to port speed, effectively consuming network resources at times when there would not be resource contention in the network. Implementations of the token bucket and leaky bucket as a meter do, however, allow output traffic flows to have bursty characteristics.