GCRA ALGORITHM PDF
2. Overview. ❑ Leaky bucket. ❑ Generic Cell Rate Algorithm. ❑ GCRA Implementations: ❍ Virtual Scheduling Algorithm. ❍ Leaky bucket algorithm. ❑ Examples. The leaky bucket algorithm has two variations, meter and queue. The meter one is more relevant here, so let’s focus on it. The idea is that a. It can shape multiple incoming variable bit rate (VBR) cell streams simultaneously to be strictly conforming according to the GCRA algorithm when the cells.
|Published (Last):||2 October 2008|
|PDF File Size:||16.69 Mb|
|ePub File Size:||1.79 Mb|
|Price:||Free* [*Free Regsitration Required]|
The meter one is more relevant here, so let’s focus on it.
Generic Cell Rate Algorithm
The idea is that a bucket is assigned a drip rate either uniform across buckets, or based on some tier. A gdra that comes in has some “volume” associated with it.
It can either fit into the bucket or not. If it does not, it is discarded.
Oh no, there’s been an error
If it fits, it is passed through for processing at least in the meter version. Who is in charge of dripping the bucket?
The blog you mentioned claims that this is usually algorothm by a background process, that circulates around the buckets and drips them. It mentions the downside that if the rate at which it can process the buckets is low with the extreme case of its going offlinea job might be discarded not because there is not enough empty volume belonging to the bucket, but because the dripping process just didn’t update it.
This is basically your point 1; I don’t see the issue with your point 2 although you might have read a description of one of the zillions of versions of leaky bucket that is constrained to uniform volumes, but nothing inherent about the algorithm requires this.
That’s where GCRA comes in. If you think about it, a separate dripping process is not really necessary.
If you track, per a bucket, the current state and a job comes in, you can calculate the next time there will be enough empty volume for alogrithm given future job size.
So, when a job arrives, it just checks if it came before or after this time. If it came before, it is discarded. If it came after, it is let through, and the times-until-next-jobs are updated.
Generic cell rate algorithm – Wikiwand
Since with GCRA you don’t rely on a separate process for dripping, you won’t run into a problem where it died or just couldn’t keep up. Tcra leads to algorifhm next point: If you run separate-process with very high frequency, then, as long as the dripping process keeps up, things are fine. Hcra high frequency, though, there’s a chance the dripping process won’t keep up.
Note that there are no free lunches, though. Whatever processing power you have, someone needs to check for empty volume, and update drips. For some settings and implementations, it’s easy to imagine where a separate dripping process assuming someone engineered the system well, and it doesn’t go offlinegives a system with overall lower latency, higher throughput, or both. Other settings and implementations might have the opposite.
Generic cell rate algorithm – Wikipedia
Virtual Schedulling” As per my understanding Leaky Bucket has the following limitations: Variable length packet in network domain I have gone through this blog which implements “Generic Cell Rate Algorithm: Can some explain me the following: In my use case if I set the clock tick to low may be check in every nanoseconds shouldn’t the problem with Leaky Bucket be mitigated?
Regarding your questions which are related: Sign up or log in Sign up using Google. Sign up using Facebook.