The generic cell rate algorithm (or GCRA) is an algorithm which measures cell rate at a specified timescale [1]. The GCRA is an implementation of the leaky bucket algorithm in ATM networks, and provides a traffic shaping function [2].

What is the GCRA used for?

The generic cell rate algorithm (GCRA) is an internationally agreed upon algorithm, defined by both the ITU-T and the ATM Forum, which measures cell rate at a specified timescale. It may be used for monitoring CBR services or any service where the cell rate is fixed over a given period of time (e.g., ABR service), or any service where a maximum cell rate is specified, including many VBR services (see Traffic Contract for ABR, CBR and VBR) [1].

How does the algorithm work?

The algorithm starts with the assumption that the cells will have a minimum time gap between them, set by the current peak cell rate at the time. The algorithm is generally called the “leaky bucket algorithm”, a name that gives considerable insight into the way it works [1]. It is illustrated in figure 1.

The bucket is filled with a cell’s worth of water every time a cell arrives, while at the same time the bucket regularly leaks a cell’s worth of water at the deterministic rate set by the peak cell rate. If the actual cell rate is below the peak cell rate, the buffer will never start filling beyond one cell’s worth of water; however, if it starts rising above this rate, then the bucket will start to fill. The height to the top of the bucket is the second parameter. If this height is set high, then the bucket will absorb bursts and CDV without overflowing. However, if the bucket height is set much lower, then smaller bursts and even excessive CDV will cause the bucket to spill. Any cells that cause the bucket to spill can be marked for cell loss priority, as they have caused a violation in the GCRA [1][3].

Formal definition of the GCRA

The actual algorithm is defined by the flow chart in figure 2. The algorithm is normally written as GCRA(T, t), where T is 1/PCR (Peak Cell Rate) and t is the maximum acceptable excursion from the theoretical arrival time (i.e., the height of the bucket). The value t can be much smaller than T if CDV (Cell Delay Variation – see traffic contract) is to be measured on a CBR service, or many times T if a mean cell rate is being measured [1].

See Also

• Leaky bucket algorithm
• Traffic Shaping
• Token bucket algorithm
• Teletraffic Engineering
• Broadband Networks

References

[1] Sexton M., Reid A., “Broadband Networking: ATM, SDH and SONET”, Artech House Inc., Boston, London, 1997. ISBN 0-89006-578-0.

[2] Hiroshi Saito, Teletraffic Technologies in ATM Networks, Artech House, 1993. ISBN 0-89006-622-1.

[3] Ferguson P., Huston G., “Quality of Service: Delivering QoS on the Internet and in Corporate Networks”, John Wiley & Sons, Inc., 1998. ISBN 0-471-24358-2.