Comparison Between The Two Versions of The Leaky Bucket Algorithm
Analysis of the two versions of the leaky bucket algorithm shows that the version as a queue is a special case of the version as a meter.
Imagine a traffic shaping function for fixed length packets that is implemented using a fixed length queue, forming a delay element, which is serviced using a leaky bucket as a meter. Imagine also that the bucket in this meter has a depth equal to the amount added by a packet, i.e. has a limit value, τ, of zero. However, the conformance test is only performed at intervals of the emission interval, when the packet at the head of the queue is transmitted and its water is added. This water then leaks away during the next emission interval (or is removed just prior to perfoming the next conformance test), allowing the next packet to conform then or at some subsequent emission interval. The service function can also be viewed in terms of a token bucket with the same depth, where enough tokens for one packet are added (if the bucket is not full) at the emission intervals. This implementation will then receive packets with a bursty arrival pattern (limited by the queue depth) and transmit them on at intervals that are always exact (integral) multiples of the emission interval.
However, the implementation of the leaky bucket as a meter (or token bucket) in a traffic shaping function described above is an exact equivalent to the description of the leaky bucket as a queue: the delay element of the meter version is the bucket of the queue version; the bucket of the meter version is the process that services the queue, and the leak is such that the emission interval is the same as the tick interval. Therefore for fixed length packets, the implementation of the leaky bucket as a queue is of a special case of a traffic shaping function using a leaky bucket (or token bucket) as a meter in which the limit value, τ, is zero and the process of testing conformance is performed at the lowest possible rate.
The leaky bucket as a queue for variable packet lengths can also be described as equivalent to a special case of the leaky bucket as a meter. The suggested implementation can, like the fixed length implementation, be seen as traffic shaping function in which the queue is a delay element, rather than the bucket, and the function that services the queue is, in this case, explicitly given as a token bucket: it is decremented for conforming packets and incremented at a fixed rate. Hence, as the leaky bucket as a meter and token bucket are equivalent, the leaky bucket as a queue for variable packet lengths is also a special case of a traffic shaping function using a leaky bucket (or token bucket) as a meter.
There is an interesting consequence of seeing the leaky bucket as a queue for variable packet lengths as a specific implementation of the token bucket or leaky bucket as a meter in traffic shaping. This is that the bucket of the meter has a depth, n, and, as is always the case with the token bucket, this depth determines the burstiness of the output traffic (perhaps in relation to the average or minimum number of tokens required by the packets). Hence, it is possible to quantify the burstiness of the output of this "byte counting" leaky bucket as a meter, unless all packets are of the maximum length when it becomes pointless. However, this ability to define a burstiness for the output is in direct contradiction to the statement that the leaky bucket (as a queue) necessarily gives an output with a rigid rate, no matter how bursty the input.
Read more about this topic: Leaky Bucket
Famous quotes containing the words comparison, versions, leaky and/or bucket:
“[Girls] study under the paralyzing idea that their acquirements cannot be brought into practical use. They may subserve the purposes of promoting individual domestic pleasure and social enjoyment in conversation, but what are they in comparison with the grand stimulation of independence and self- reliance, of the capability of contributing to the comfort and happiness of those whom they love as their own souls?”
—Sarah M. Grimke (1792–1873)
“The assumption must be that those who can see value only in tradition, or versions of it, deny man’s ability to adapt to changing circumstances.”
—Stephen Bayley (b. 1951)
“A leaky faucet, a barking dog—those are things you tolerate.”
—Candace Gingrich (b. c. 1967)
“And now, far removed from the loved habitation,
The tear of regret will intrusively swell,
As fancy reverts to my father’s plantation,
And sighs for the bucket that hung in the well.”
—Samuel Woodworth (1788–1842)