Leaky Bucket - The Leaky Bucket Algorithm As A Meter

The Leaky Bucket Algorithm 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 version of what is essentially the same meter version of the algorithm, the Generic Cell Rate Algorithm, is described 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 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 policing (figure 2), it pulls open a trap door, which causes the packet to be dropped and stops its water from entering the bucket; in shaping (figure 3), it pushes up a flap, which delays the 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's 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. To make Turner’s description clearly aligned with ITU-T, the statement “If the counter exceeds a threshold upon being incremented, the network discards the packet” would have to be changed to something like “If the counter would exceed a threshold upon being incremented, the network discards the packet and the counter is not incremented", i.e. it is only incremented when it is less than or equal to the limit value, τ, or at least T less than the bucket depth in the ITU-T description.

In fairness, the description given by Turner is in terms of a traffic policing function, where overzealousness in limiting a connection containing nonconforming packets may not be an issue. Indeed, in some contexts, such as Variable bitrate (VBR) transmissions, the loss of any one packet may corrupt the entirety of a higher layer message, e.g. an OSI Network Layer PDU. In which case, discarding all the following packets of that corrupted PDU sheds an unnecessary network load. However, it would be entirely unacceptable in traffic shaping for a packet that fails the conformance test to affect how long before conformance can next occur, i.e. if the act of testing a subsequent packet for conformance would change how long a packet currently waiting to conform has to wait. This is exactly what would happen were the bucket not finite, as any subsequent nonconforming packets would raise the water level, and thus make a packet waiting to conform wait longer.

Neither Turner nor the ITU-T addresses the issue of variable length packets. To be fair again, the description according to the ITU-T is for ATM cells, which are fixed length packets, and Turner does not specifically exclude variable length packets. In both cases, if the amount by which the bucket content or counter is incremented for a conforming packet is proportional to the packet length, they will both account for the length and allow the algorithm to limit the bandwidth of the traffic explicitly rather than limiting the packet rate. For example, shorter packets would add less to the bucket, and could thus arrive at smaller intervals; whereas, longer packets would add more and thus have to be separated by proportionally larger intervals to conform.