Talk:Leaky bucket

Distinction

This article blurs the distinction between a leaky bucket as a model (i.e. a meter) and the shaper (a FIFO) or policer (an algorithmic dropper and/or marker) it assists.

A leaky bucket is just a meter. It does not store packets and it does not shape them. Its operation as a meter is used to declare conforming packets when it assists a policer, or the times when packets can be releases from FIFO shapers. This latter CAN BE VBR, does not have to be CBR.

The leaky bucket is characterized by starting empty and arriving protocol data units pouring tokens into the bucket from where these are leaked at constant pace. This does not mean that a leaky bucket is a CBR shaper. It would be a CBR shaper if it assisted the release of packets from a FIFO and if it had just one PDU's worth of burst tolerance. If it has a bigger burst tolerance then packets can be released in VBR manner. The burst tolerance of a leaky bucket is not equal to the size of the shaped FIFO queue.

A leaky bucket IS equivalent to a token bucket in the sense that it would find exactly the same packets conforming and non conforming of a traffic stream. This case is met when the filling rate of the token bucket is equal to the draining rate of the leaky bucket; when their burst tolerances are the same; and when at time zero the leaky bucket starts empty and the token bucket starts full.

A CBR shaper is not necessarily inefficient. It depends what you want to achieve. A network operator may have perfectly good reasons why to shape a flow or aggregate CBR, and another one VBR, or not shape at all. In legacy network devices (especially old ATM gear) that had very small cell buffers, it was important that incoming flows were CBR shaped.

I agree. This article confuses between rate shaping using a buffer and the algorithm itself. I have never really seen the term leaky bucket used as any other than the traffic analyser/meter it is. There is a reference for current usage, though, but I don't have access to it. Anyway, his article needs to be rewritten anyway, to agree with GCRA. Alinja (talk) 09:01, 19 November 2007 (UTC)

I did some reserch, and it seems there are different usages for the same term. ATM traffic management specification talks about Leaky Bucket and GCRA as being equivalent. On the other hand, At least Tanenbaum's "Computer Networks" refers to Leaky Bucket only as a buffer with constant emptying rate ("nothing other than single-server queuing system with constant service time"). Most hits on google seem to refer to the ATM way, though. Maybe this term should be discarded and this page replaced with a disambiguation page to relevant articles? Alinja (talk) 11:14, 19 November 2007 (UTC)

Most of what I have seen with google does point to just traffic shapping use of Leaky bucket. However not everything is encompassed by google. (I know I know - that is heresy.) I was introduced to leaky bucket algorithm as a form of hysteresis/debouncing of alarm information. The concept was that every time an event occurred it would put a 10 (or some large number) into the bucket. Then every time period a count of 1 would "leak" from the bucket. An alarm wasn't generated for the user unless the bucket overflowed, which it did at 30. These are made up numbers, but it shows the general concept. As far as I can remember this came from Bellcore (now Telecordia) documents, but I no longer have access to that library to provide detailed information. Danoelke (talk) 15:04, 19 February 2008 (UTC)

A couple of examples of other applications that use leaky bucket algorithms:

[ ftp://ftp.penguincomputing.com/pub/support/Product_Support/Relion_1670/Documentation/D92944-004_S5400SF_TPS_rev1_0.pdf Error Counters and Thresholds ]

[ http://hillside.net/chiliplop/2005/D4M-MbyD.pdf Leaky Bucket Counter] (search for leaky bucket in the document) --Megalithic (talk) 17:28, 22 January 2009 (UTC)

Remove autombile anlogy

I have decided to remove the automobile analogy because it dose not add to the article. The leaky bucket algorithm is *already described better* by the analogy of a real leaky bucket. So no need for the automobile analogy.Lotu (talk) 21:51, 6 February 2009 (UTC)

I agree ("the volume of the traffic is greater than the bucket size" is a terribly mixed metaphor) but why did you delete the section "Inefficiency of the leaky-bucket implementation"? I have just restored it. Qwfp (talk) 14:27, 19 July 2009 (UTC)

Major Problems with this Article

The major problems with this article appear to stem from the fact that there are two dissimilar descriptions of the leaky bucket algorithm in the literature. On one hand, we have J. S. Turner (quoted in the existing article) and the ITU-T (in recommendation I.371), and on the other A. S. Tanenbaum (in his book Computer Networks). The major conflict between these stems from the fact that Turner and the ITU-T describe the algorithm as something used as an adjunct to the packet stream used to check conformance to a contract, where the arrival or transmission of a packet changes the contents of an analogue of the bucket; whereas, Tanenbaum describes it in terms of the packets actually passing through the analogue of the bucket.

This means that Tanenbaum’s rather more literal interpretation of how to apply the analogy of a leaking bucket results in a much simplified algorithm, and this simplification results in limitations in its properties. Specifically, Tanenbaum states “The leaky bucket algorithm enforces a rigid output pattern at the average rate, no matter how bursty the [input] traffic is”. This is clearly in contradiction of Turner’s description, which describes the counter threshold as “a measure of burstiness”. It is also actually contradicted by Tanenbaum’s own suggested implementation for variable packet lengths, which allows multiple packets to be released within or at (the description is vague on this point) the same clock tick, which is obviously a bursty output.

Careful analysis of the Turner/ITU-T and Tanenbaum’s algorithms shows that Tanenbaum’s description is a special case of the Turner/ ITU-T algorithm applied only to shaping, and the Turner/ ITU-T algorithm is in fact an exact mirror image of the Token Bucket Algorithm: it adds content to the bucket where the TBA removes it, and leaks it away where the TBA adds it in.

It is for these reasons that there is such confusion and argument over what the leaky bucket algorithm is and what its properties are. However, both perspectives are correct, as long as one has only read either the Turner/ITU-T descriptions or Tanenbaum’s.

With regard to the article itself, while it quotes Turner, and makes some reference to the GCRA, in the main it reiterates the limitation that Tanenbaum attributes to the algorithm, i.e. that it cannot allow burstiness in the output stream. However, this is clearly contradictory to Turners original (according to Tanenbaum himself) description, and to the use of the LBA in UPC/NPC in ATM networks. I feel that this article should address both descriptions and should properly explain their relationships with one another and the TBA. I also believe, in the context of the ITU-T description, that it should explain such additional issues as the relationships between bucket depth, emission interval (T), jitter or delay variation tolerance (CDVt), and maximum burst size (MBS), etc., and reference self similarity.

I understand that it is not the norm to engage in wholesale re-writing of Wikipedia articles; however in this case, I feel that an editing of the article would have to be so thorough as to be indistinguishable from a total re-write.

Graham Fountain 23:00, 5 June 2010 (UTC) —Preceding unsigned comment added by Graham.Fountain (talk • contribs)

I'll not get involved in the discussion about whether the article needs a rewrite (I've only glanced at it myself, and have little knowledge of the subject matter), but I've seen wholesale rewrites occurring on numerous occasions, usually in a sub-page of the main article (e.g. Leaky bucket/rewrite) so as to avoid disrupting the main article, and possibly with a note at the top to signify that such a rewrite is occurring. me_and (talk) 12:46, 8 June 2010 (UTC)

I have put this page at Leaky bucket/rewrite that addresses the problems with this page, i.e. that it mostly talks about one of the two competing versions. Graham Fountain 15:25, 27 June 2010 (UTC) —Preceding unsigned comment added by Graham.Fountain (talk • contribs)

Subpages are not enabled in articlespace, unlike user and talk spaces. I have moved the draft to Talk:Leaky bucket/rewrite. ---— Gadget850 (Ed) ^talk 09:52, 30 June 2010 (UTC)

Rewrite of page

The leaky bucket/rewrite page, having received no adverse comments has been used to overwrite the existing leaky bucket page Graham Fountain 12:43, 30 June 2010 (UTC)

Page Ratings

Just wondering if anyone knows why this article has got relatively low ratings for trustworthy and complete. Graham.Fountain | Talk 14:30, 12 June 2012 (UTC)