Leaky Bucket - The Leaky Bucket Algorithm As A Queue

The Leaky Bucket Algorithm As A Queue

A seminal description of the leaky bucket as a queue is given by Andrew S. Tanenbaum, in his book Computer Networks as “The leaky bucket consists of a finite queue. When a packet arrives, if there is room on the queue it is appended to the queue; otherwise it is discarded. At every clock tick one packet is transmitted (unless the queue is empty)”. An implementation of the leaky bucket as a queue is therefore always a form of traffic shaping function.

As can be seen this implementation is restricted in that the packets are only ever transmitted at a fixed rate. 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 traffic is”. However, this assertion is only strictly true as long as the queue does not become empty: if the average arrival rate is less than the rate of clock ticks, or if the input is sufficiently bursty that the losses bring the rate of the remainder below the clock tick rate (i.e. gaps in the input stream are long enough and the queue is small enough that it can become empty), there will be gaps in the output stream.

A further restriction is that the leaky bucket as a queue traffic shaping function only transmits packets on the ticks; hence, if it is used within a network, equivalent to UPC and NPC, it also imposes a fixed phase on the onward transmission of packets. Perversely, in the context of the transfer delay, this imposition of a fixed phase that may, over time, differ from that of an otherwise conforming input packet stream, constitutes a delay variation and hence a jitter. However, jitter caused in this particular way could only be observed when making a 2-point delay variation measurement, where the delay is measured as the transit time between two separate measurement points, one either side of the leaky bucket as a queue shaping function. It would not be observable to a downstream traffic management function using, e.g., a token or leaky bucket algorithm, where the delay variation is made as a 1-point measurement.

Limiting variable length packets using the leaky bucket algorithm as a queue is significantly more complicated than it is for fixed length packets. Tanenbaum gives a description of a “byte-counting” leaky bucket for variable length packets as follows: “At each tick, a counter is initialized to n. If the first packet on the queue has fewer bytes than the current value of the counter, it is transmitted, and the counter is decremented by that number of bytes. Additional packets may also be sent, as long as the counter is high enough. 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 and the flow can continue”.