Download (direct link):
4.7.1 The Generic Cell Rate Algorithm (GCRA)
Unlike the leaky bucket mechanism, GCRA is a deterministic algorithm and it does catch all of the violating cells. However, for this it requires an additional new traffic parameter known as the cell delay variation tolerance (CDVT). Note that this parameter is different from the peak-to-peak cell delay variation parameter described in Section 4.2.
Let us assume that a source is transmitting at peak cell rate and it produces a cell every T units of time, where T = 1/PCR. Due to multiplexing with cells from other sources and with signaling and network management cells, the inter-arrival time of successive cells belonging to the same UNI source could potentially vary around T (see Figure 4.15). That is, for some cells it might be greater than T, and for others it might be less than T. In the former case, there is no penalty in arriving late. However, in the latter case, the cells will appear to the UNI that they were transmitted at a higher rate, even though they were transmitted conformally to the peak cell rate. In this case, these cells should not be penalized by the network. The cell delay variation tolerance is a parameter that permits the network to tolerate a number of cells arriving at a rate which is faster than the agreed upon peak cell rate. This parameter is not source dependent. Rather, it depends on the number of sources that use the same UNI and the access to the UNI. It is specified by a network administrator.
GCRA can be used to monitor the peak cell rate and the sustained cell rate. There are two implementations of GCRA: the virtual scheduling algorithm and the continuous-state leaky bucket algorithm. These two algorithms are equivalent to each other.
Policing the peak cell rate
In order to monitor the peak cell rate, the following two parameters are required: peak emission interval T and cell delay variation tolerance ̣. T = 1/PCR. This is obtained from the user’s declared peak cell rate and the network administrator’s ̣.
Figure 4.15 Arrival times at the UNI.
Figure 4.16 The virtual scheduling algorithm.
A flowchart of the virtual scheduling algorithm is shown in Figure 4.16. Variable TAT is the theoretical arrival time of a cell and ts is the actual arrival time of a cell. At the time of arrival of the first cell, TAT = ts. Each time a cell arrives, the algorithm calculates the theoretical time TAT of the next arrival. If the next cell arrives late (i.e., TAT < ts), then the next theoretical arrival time is set to TAT = ts + T. If the next arrival is early (i.e., TAT > ts), then the cell is either accepted or classified as noncompliant. The decision is based on the cell delay variation tolerance ̣ and also on previously arrived cells that were late but they were accepted as compliant. Specifically, if TAT < ts + ̣, then the cell is considered as compliant. Notice, however, that the next theoretical arrival time TAT is set equal to the theoretical arrival time of the current cell plus T (i.e., TAT = TAT + T). If the next arrival occurs before the theoretical arrival time TAT, then it can still be accepted if TAT < ts + ̣ However, if cells continue to arrive early, then the cell delay variation will be used up and eventually a cell will be classified as noncompliant.
As an example, let us consider the case where T = 10, ̣ = 15, and the actual arrival times of the first five cells are: 0, 12, 18, 20 and 25. For cell 1, we have that ts = TAT = 0. The cell is accepted, and TAT is set to TAT + 10 = 10. For cell 2, ts = 12 and since TAT < ts, the cell is accepted and TAT is set equal to ts + T = 22. Cell 3 arrives at time ts = 18, and so TAT > ts. Since TAT < ts + ̣, the cell is accepted and TAT is set equal to TAT + T = 32. Cell 4 arrives at time ts = 20, and TAT > ts. Since TAT < ts + ̣, the cell is accepted, and TAT is set equal to TAT + T = 42. Cell 5 is not as lucky as cells 3 and 4. Its arrival time is ts = 25, which makes TAT > ts. Since TAT > ts + ̣, the cell is considered to be noncompliant.
A flowchart of the continuous state leaky bucket algorithm is shown in Figure 4.17. In this algorithm, a finite-capacity leaky bucket is implemented whose real-value content is drained out at a continuous rate of one unit of content per unit-time. Its content is
CONGESTION CONTROL IN ATM NETWORKS
Figure 4.17 Continuous state leaky bucket algorithm.
increased by a fixed increment T each time a conforming cell arrives. The algorithm makes use of the variables X, X', and LCT. X indicates the current value of the leaky bucket; X' is an auxiliary variable; and LCT is the last compliance time (i.e., the last time a compliant cell arrived). At the arrival time of the first cell, X = 0 and LCT = ts.
When a cell arrives, the quantity X — (ts — LCT) is calculated and saved in the auxiliary variable X'. If X' < 0, then the cell has arrived late and the cell is accepted, X is increased by T, and LCT = ts. If X' > 0, then depending upon whether X' is less or greater than ̣, the cell is accepted or it is considered as noncompliant. If X > ̣, the cell is classified as noncompliant and the values of X and LCT remain unchanged. If X < ̣, then the cell is accepted, X is set to X' + T, and LCT = ts.