[Click] adding TokenBucket

[Eddie Kohler]

To close this loop, the TokenBucket changes are now in mainline.  Thank 
you very much, Cliff, for getting this done!!  I think it's a very good 
change.

Eddie


On 1/7/11 12:56 AM, Cliff Frey wrote:
> 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
> _______________________________________________
> click mailing list
> click at amsterdam.lcs.mit.edu
> https://amsterdam.lcs.mit.edu/mailman/listinfo/click