[Click] adding TokenBucket

[Cliff Frey]

RatedUnqueue has never supported intervals above 1 second (the minimum rate
is 1/sec).

In any case, I changed the default behavior to use 20ms of burstiness, and
added documentation and config options to change it.

The latest round of the commit is here
https://github.com/clifffrey/click/commit/05a99bf3de7c752fe4971884a9309208a819d0ae

commit 05a99bf3de7c752fe4971884a9309208a819d0ae
Author: Cliff Frey <cliff at meraki.com>
Date:   Tue Jan 4 22:22:53 2011

    Change (BW)RatedUnqueue and (BW)RatedSplitter elements to use
TokenBuckets.

    The biggest functional change here is that these elements now have
    consistent and customizable burst behavior.  The elements now all use
    token buckets configured by default with a capacity of 10 milliseconds
    worth of traffic.  This leads to a slight spike in traffic after
    periods of idle time.  The capacity of the token bucket (and therefor
    the maximum burst size) can be configured using an absolute size
    (BURST_SIZE) or by specifying a duration of time (BURST_DURATION).

    I believe (untested) that GapRate would also have bursty behavior,
    except for the special case of the very first packet through it.  At
    that point there was no burst.  After idle periods in the future,
    GapRate would provide some amount of bursting (I believe on the order
    of 1 second, but am not sure).

    The other big change is that these elements all now include timers
    which they are willing to use, so they should not ever end up pegging
    the CPU.

    This also greatly improves performance.  I believe that this is
    because of TokenBucket's relative efficiency to GapRate.
      cat myconfig
        InfiniteSource(LIMIT 4000000, TIMESTAMP false, STOP true)
        -> Queue(CAPACITY 100)
        -> RatedUnqueue(4000000000)
        -> Discard
      time ./userlevel/click myconfig
        real                  0m6.319s
        user                  0m3.212s
        sys                   0m3.088s
      time ./userlevel/click myconfig
        real                  0m1.729s
        user                  0m1.200s
        sys                   0m0.520s

On Wed, Jan 5, 2011 at 5:17 AM, Bart Braem <bart.braem at ua.ac.be> wrote:

> Hi,
>
> On 05 Jan 2011, at 07:50, Cliff Frey wrote:
>
> > Eddie and I worked on a new TokenBucket data structure that is good for
> > implementing rate-limited operations (like RatedUnqueue).  I'm hoping to
> > push this to mainline soon, but wanted to solicit feedback from the list
> > first.
> >
> > The commits have the details.  I'm mostly curious if anyone objects to
> the
> > behavioral change to the Rated* elements having a 1 second burst.
>
> Actually, I am not sure about this one. From a performance point of view,
> this is a welcome change of course.
> However, I often see our students use Rated* elements a sort of cheap timer
> for generating packets. When the interval is above 1 second, behaviour will
> not change. However below 1 second...
> On the other hand, a token bucket is a really standard concept in networks.
> Which they are supposed to know or learn about. So this behaviour should not
> be completely unexpected, if the used token bucket mechanism is documented.
> So I'd say that I do not object, if there is documentation.
>
> best regards,
> Bart