Thursday, November 15, 2007

Implementing the Token Bucket algorithm


Implementing this algorithm is relatively straightforward.  I run a thread in the background that periodically fills the token bucket.  This required a minor transformation of the algorithm; instead of adding a single token every 1/r seconds I added T tokens every S seconds where T = r * S.

 

So the background thread just loops ala:

while ( true )

{

   sleep(S);

   EnterCriticalSection(...);

   if tokens < maxTokens

      tokens += T;

   LeaveCriticalSection(...);

}

 

I've left off a few details (e.g., try/catch blocks) but that's the heart of the implementation.

 

In my case the bucket starts off full (since no data has been sent yet) but that may not be the case in other situations.

No comments :

Post a Comment