Dynamic Queue Control Functions for ATM ABR Switch Schemes: Design and Analysis 1 2 3

Bobby Vandalore, Raj Jain, Rohit Goyal, Sonia Fahmy
The Ohio State University
Department of Computer and Information Science
Columbus, OH 43210-1277
Contact Phone: 614-292-3989, Fax: 614-292-2911
E-mail: {vandalor,jain, goyal, fahmy}@cse.wustl.edu


The main goals of a switch scheme are high utilization, low queuing delay and fairness. To achieve high utilization the switch scheme can maintain non-zero (small) queues in steady state which can be used if the sources do not have data to send. Queue length (delay) can be controlled if part of the link capacity is used for draining queues in the event of queue build up. In most schemes a simple threshold function is used for queue control. Better control of the queue and hence delay can be achieved by using sophisticated queue control functions. It is very important to design and analyze such queue control functions. We study step, linear, hyperbolic and inverse hyperbolic queue control functions. Analytical explanation and simulation results consistent with analysis are presented. From the study, we conclude that inverse hyperbolic is the best control function and to reduce complexity the linear control function can be used since it performs satisfactorily in most cases.

Keywords:ATM Switch algorithms, ABR service, congestion control, traffic management, queue management.


The ATM (asynchronous transfer mode) is the chosen technology for implementing B-ISDN (broad-band integrated services digital network). The ABR service in ATM can be used to transport data traffic with minimum rate guarantee. ABR uses closed loop feedback to control the source rates (see Figure  1 (a)). The source sends periodically (after every Nrm-1 data cells) an RM (resource management) cell to gather information from the network [ 1]. The RM cells are turned around at the destination. The switches along the path indicate the rate which they can currently support. When the source receives the backward RM cell, it adjusts its allowed cell rate based on the explicit rate indicated in the RM cell.

The goals of a rate allocation scheme are to maintain high utilization, small queuing delay, small cell loss, and fairness among competing sources. In order to support (low quality) video sources over ABR (Available Bit Rate) service, it is also desirable that in the steady state, the rates and queuing delay be constant. One way to achieve a high utilization and low queuing delay is to vary the target rate as a function of queue length. The function should be a decreasing function of queue length. The function should also be simpleso that it can be implemented in the hardware.

In this paper, we study several queue controlfunctions which satisfy the above needs. We present an analytical explanation for the performance of these functions. Then, we present simulation results which are consistent with the analysis. The various trade-offs between the queue control functions are studied using appropriate metrics. The ERICA+[ 2] switch scheme is used in the simulations.

Switch Scheme Model

There are many ABR switch schemes ([ 2, 3, 4, 5, 6]).

This section gives an overview of the switching scheme model on which this study is based.

The ERICA+algorithm used in this study fits the above model.

Queue control functions

In this section the relationship between the queue length and queue control function is presented for the above switch model. Then various queue control functions to achieve the desired goals are presented.

The following terms are used in the discussion:

number of sources.
``averaging interval'', the period at which feedback to the sources is calculated at the switch.
rate of source i.
explicit rate of source icalculated at the switch.
propagation time from the source to switch.
feedback delay is twice tp.
Available ABR capacity. For simplicity we assume the higher priority traffic such as CBR and VBR are not present. Hence, Rlis same as the link rate.
switch queue length (in cells)
aggregate input rateseen at switch. img21

(conversion function) number of cells transmitted in time tat link rate. img22if Rlis given in Mbps.

Note : X(t) denotes that Xis a function of time.

Queue Length Function

For the simplification of the analysis, we assume that the propagation delay tpfrom source to switch switch is same for all sources. Due to propagation delay tp, the rate seen at the switch at time tis the same as source rate at time t- tp. The sources adjust their rates to the explicit rate indicated in the BRM cells. Due to propagation delay propagation delay tpthe sources adjust their rate at time tto the explicit rate generated at time t-tp. In one averaging interval Q(t) is drained by img23cells. The queue builds up at input rate. Then, Q(t)can be expressed as follows :



Q(t) = Q(t-ts) + (R(t) - Rl) C(ts)

The switch scheme tries to adjust the input rate R(t) to match the output rate depending on current queue size, i.e., img26. We assume no higher priority traffic, so img27. Hence,

Q(t) = Q(t-ts) + (f(Q(t-ts)) - 1) RlC(ts)

and (f(Q(t-ts)) - 1) Rlis the rate at which the queue changes in one averaging interval. The function f(Q) is the queue control function. The queue length increases if f(Q) > 1, remains constant if f(Q) = 1, and decreases if f(Q) < 1. Hence, by using an appropriate function f(Q), the queue length can be controlled.

Explicit Rate Feedback

The explicit rate is calculated as follows


The sources adjust their rates ri(t) based on the explicit rate feedback from the switch. The feedback reaches the switch after time tp. Hence, ri(t) (source rate) can be expressed using the following equation ;


Since tf= 2 tp, we get


For simplicity we have assumed there is no HPR traffic (Note in the presence of bursty VBR sources there might not be any steady state of the system). So the above function becomes


For ERICA+scheme the above function is as follows


where Input Rateis the ABR input rate measured at the switch. The scheme tries to match the input rate to the link rate, by over allocating the rates if the queue is small. If the queue are large, it is drained quickly by using (1-f(Q)) part of the link capacity.

For other schemes the following modification can be done to incorporate queue control function with that scheme. Let erA(t) be explicit rate calculated by an algorithm A. Then add the following as last step in the algorithm A:


where PCR is the peak cell rate. It can be shown that if the algorithm Aconverges to max-min rates, then the modified algorithm also converges to the max-min rate. Further, the queue control function f(Q) can be chosen so that the queue length (and hence delay) is constant in steady state.

Design of Queue Control Function

The design considerations for the queue control functions are as follows:

The queue control function with above properties will be of the form


where img35

The following functions are possible candidates.

Step function
The step function has multiple thresholds (See figure 1 (b)). This is the simplest one to implement in hardware (lookup table). img36

where sa> 1 and img37are step parameters. In general it can have nsteps. In the above case n= 4.

Linear function
The function f(Q) has linear relationship with queue length. (See figure 1 (b))


where mband maare slope of the linear portions. This function can be implemented in an efficient manner, using shift operations, if maand mbare of the form 1/2k and the queue length is counted in terms of Q0.

Hyperbolic function
The function f(Q) is a hyperbolic function of the queue length. (See figure 1 (b))


where haand hbare the parameters which control the degree of curvature of the hyperbolic function. This function takes more time to calculate, since it has a division operation. For a high value of hathe hyperbolic function becomes similar to the step function. For an havalue near 1, the hyperbolic function approaches the linear function.

Inverse Hyperbolic function
The fraction f(Q) is an inverse hyperbolic function of the queue length for overload conditions (see Figure 1 (b)). In the underload region, an hyperbolic function is used.


where img41and img42are the parameters which control the degree of curvature of the inverse hyperbolic and hyperbolic functions. This function is continuous and smooth at both Q0and Q1.

The curve used in the control function in underload region is called the ``a-curve'' and the one used in over loaded region is called the ``b-curve''. The parameters used in the a-curve img43are called a-parameters. img44are called the b-parameters. Note that, since all the functions are continuous, at Q2we have the equation f(Q2) = QDLF. So, Q2can be expressed in terms of QDLFand a-parameterfor linear, hyperbolic and inverse hyperbolic functions.

Figure 1: Feedback Control and Queue Control Functions


To compare the performance of the queue control function the following metrics are chosen.

Convergence Time:
The time the scheme takes to converge to steady state. To find the convergence time, the variance and standard deviation of desired variable are calculated between ( img46, img47) for img48, where tk( = 100 ms) is a small time interval). Initially the standard deviation is large due to oscillations. The convergence time is img46after which the variance is small. Also the graphs of (mean+standard deviation) value of the variable versus time are plotted. From the graph the convergence time can be calculated.
Standard Deviation:
The standard deviation of various quantities like ACRs, queue length and utilization is calculated. In order to separate the oscillations before steady state from affecting the measurement, the variance is measured both before and after steady state is achieved.

Visual inspection of the graphs also gives a good idea about the convergence time and the variations.

Analytical Explanation

In this section we analyze the behavior of the proposed queue control functions. We assume a simple configuration in our analysis. Ninfinite ABR sources (always having data to send) are sending data to NABR destinations (See figure 2). The performance study under more stressful conditions is done by a simulation using the Generic Fairness configuration - 2 [ 7] in the section  7.

Figure 2:

The change in queue length in a averaging interval tsis given by:


It is shown in [ 8] that additive increase and additive decrease leads to the steady state. For all four queue control functions f(Q) > 1 for img52and f(Q) < 1 for img53. The change in queue length depends on the value of f(Q) - 1. Hence, the change in the queue length is an additive increase for under utilized region and an additive decrease in the over loaded region. Therefore, the queue length converges to a value between Q0and Q1. An interesting point to note is that the amount of increase and the amount of decrease itself is dictated by the current queue length and its distance from the steady state queue length range. The behavior of the queue length for the inverse hyperbolic function is shown in figure  2 (a). The figure shows the queue length (y-axis) versus time (x-axis). The queue length decreases linearly in the range img54(highly overloaded) with slope QDLF. For queue length in the range img53(lightly overloaded, near the steady state) the slope is given by f(Q) - 1. Hence, the queue decreases hyperbolically (inverse of f(Q) function of a-curve) with respect to time. In the steady state, ( img52) the queue length is constant. In under utilized range img55, the queue increases inverse hyperbolically since the slope is f(Q) - 1and f(Q) is hyperbolic.

Step Function

If Q(t-tf) < Q0then f(Q(t-tf) = sb> 1, so the queue grows till feedback information is passed to the sources asking them to decrease their rate. The queue grows for tftime and it can be expressed as follows:


If the condition Q0< Q(t) < Q1is satisfied and the input rate matches the output rate, then the steady state is achieved, and the queue remains at this constant length.

If Q1< Q(t) < Q2then the Q(t) starts decreasing with slope -(1-sa). This decrease also takes place for tftime, if the queue ends up between Q0and Q1and if input rate is close to output rate then again the steady state is achieved.

Therefore, for the system to achieve the steady state, the value of queue length after one feedback interval should be within the range Q0and Q1. This requirement is satisfied if the condition img57holds. Since step function has discontinuities, it is very sensitive to queue length value near the thresholds and steady state might not be reached if the parameters are not set properly. If parameters are not set properly, then the queue grows from a value below Q0for tftime, crosses Q1, and decreases for tftime to a value less than Q0. Then, this pattern repeats.

Linear Function

If Q(t-tf) < Q0, then f(Q(t)) > 1. Similar to the step function the queue keeps growing for tftime with a slope of img58. But unlike the step function, the slope now depends on the value of queue length. After tfseconds, if the queue Q(t) > Q1, the queue length starts decreasing with a slope of img59. The slope now depends on the value of the queue length so the there are no sudden changes in the slope. Therefore the oscillations are fewer when compared to the step function. If the system is near the steady state, then the oscillations decrease, the queue length reaches a value between Q0and Q1, and system reaches the steady state.

Hyperbolic Function

The analysis for this case is similar to above. If haand hbparameter are close to one (typical values are ha= 1.15, hb= 1.05) the hyperbolic function has similar behavior as the linear function. If ha is high then the hyperbolic function is close to the step function. Since the hyperbolic function has a larger curvature initially and then smoothes out, img60value will be smaller than corresponding img60value obtained using the linear function. Hence, the fluctuations in the rates are greater, but the queue draining is faster.

Inverse Hyperbolic Function

The behavior of the queue length versus time for the inverse hyperbolic function is shown in figure  2 (a). The behavior of this queue control function has been explained earlier in this section. Since the inverse hyperbolic function is continuous and smooth near Q1, it gives rise to less oscillations compared to other cases.

Simulation: Configuration and Parameters

In this section the two configurations used in the simulations are explained. In all the simulation no higher priority (CBR and VBR) traffic is present.

Simple Configuration: N Source - N Destinations

In this configuration: (See figure 2)

Generic Fairness Configuration - 2 (GFC-2)

This configuration (See figure 3) was used to test the performance of the queue control functions and the switch scheme under more stressful conditions. The value of link distance D was chosen to be 1000 Km. In this configuration the expected max-min fairness rate for the different VC's are: A VCs = 10 Mbps, B VCs = 5 Mbps, C VCs = 35 Mbs, D VC = 35 Mbps, E VCs = 35 Mbps, F VC = 10 Mbps, G VCs = 25 Mbps, H VCs = 52.5. This configuration is explained more in [ 7].

Figure 3: Generic Fairness Configuration - 2

Simulation: Results

In this section the simulation results using the above two configurations are given. The graphs of rates, queue length and utilization are given. The tables and the graphs are used to study the performance of different queue control functions. In the simulations for both configurations, QDLFwas chosen to be 0.5.

Simple Configuration: Results

The table 1shows the performance for different step values (parameters) of the step queue control functions as the queue threshold Q1is varied. The mean bottleneck link queue length, its standard deviation before one second and after one second (last two columns) are shown in the table. Note that Q2is fixed given the QDLFand other parameters of the linearand hyperbolicfunctions. Number of sources N= 3.

Table 1: Simple Configuration: Results
Queue a b Q1 Q2 Convg Mean Std Dev Std Dev
Control param param     time(secs) Q(cells) (bef 1 sec) (after 1 sec)
Step 0.75 1.01 4 Q0 26 Q0 - 252.93 552.21017 501.60
  0.90 1.01 4 Q0 26 Q0 - 98.04 651.82 241.43
  0.90 1.05 4 Q0 26 Q0 - 663.63 1226.70 840.36
  0.95 1.01 4 Q0 26 Q0 - 251.51 816.62 393.26
  0.95 1.05 4 Q0 26 Q0 - 124.11 805.32 240.04
  0.95 1.01 2 Q0 26 Q0 - 896.90 1386.87 1036.66
  0.95 1.01 8 Q0 26 Q0 - 483.20 1001.54 644.73
Linear 1/16 1/16 2 Q0 26 Q0 0.20 311.85 335.61 0.69
  1/16 1/16 4 Q0 26 Q0 0.32 403.52 457.90 0.69
  1/16 1/16 8 Q0 26 Q0 0.61 402.85 622.02 0.69
Hyperbolic 1.15 1.05 2 Q0 26 Q0 - 509.94 423.89 205.65
  1.15 1.05 4 Q0 26 Q0 0.32 214.19 500.14 0.86
  1.15 1.05 8 Q0 26 Q0 0.82 220.96 862.25 0.63
Inverse 36 1.05 2 Q0 26 Q0 0.22 313.17 525.51 0.69
Hyperbolic 16.5 1.05 4 Q0 26 Q0 0.25 209.50 580.15 0.50
  6.75 1.05 8 Q0 26 Q0 1.12 202.27 704.02 16.98

The following things can be observed from the Table 1.

The graphs 4 (a), 4 (e), 5 (a), 5 (e) show the ACR rate of the three sources.

The mean and standard deviation of the rates and the queue lengths are calculated for every 100 milliseconds. These are shown in figures 4 (b), 4 (f), 5 (b) and 5 (f) for ACR rates and in figures 4 (d), 4 (h), 5 (h) for the queue lengths. From these graphs the converging time can be estimated. In steady state the oscillations are small, the standard deviation is small compared to mean. So the quantity (mean + standard deviation) has a value close to the mean in the steady state.

For the step function, there is oscillation in all the quantities (rates, queue and utilization). For linear and hyperbolic functions, the oscillations die down and the system reaches steady state. In the steady state, the rate and queue length are constant and utilization is 100%. Hence the linear, hyperbolicand inverse hyperbolicqueue control functions fulfill the desired goal. This is consistent with the analytical explanation given in the previous section.

In all the cases when the queue length and the rates converge, the queue length is non-zero hence, the utilization at the steady state is 100%.

GFC-2 Configuration: Results

The following parameters were used in the simulations for this configuration.

The table 2shows the performance for three queue control functions. The table shows the H(1) VC's mean rate, switch queue length for SW5 and its convergence time, standard deviation before one second and after one second. The queue length variation is present in all three cases. The rate variation is much less in the linearand hyperbolicfunctions compared to the stepfunction. This is also evident from the graphs which are explained in the next section.

Table 2: GFC-2 Configuration: Results
Queue Quantity Convergence Mean Std Dev Std Dev
Control   Time (secs)   (before 1 sec) (after 1 sec)
Step H(1) ACR - 72.81 18.4 4.46
  SW5 Queue - 284.28 878.63 281.85
Linear H(1) ACR 1.25 52.46 14.38 1.08
  SW5 Queue 1.3 455.46 1043.71 220.42
Hyperbolic H(1) ACR 1.45 52.77 13.57 0.58
  SW5 Queue 1.3 361.32 968.27 201.86
Inverse Hyperbolic H(1) ACR 1.51 52.38 14.04 0.92
  SW5 Queue 2.0 1443.72 3829.17 999.62

GFC-2 Configuration: Graphs

The graphs in Figure  6and 7were obtained by simulating the GFC-2 configuration using the step, linearand hyperbolicand inverse hyperbolicqueue control functions. Graphs 6 (a), 6 (e), 7 (a) and 7 (e) show the ACR rate for one VC of each of A through H type VCs versus time when different queue control functions are used. From these graphs it can be seen that the expected rates are obtained when linear, hyperbolic and inverse hyperbolic functions are used for queue control.

The (c) and (g) graphs have the queue length for all the switches. The maximum queue is due to the initial overload, before the first round trip time. Once the feedback control loop is established the f(Q)value is QDLFand queues are drained quickly.

When step function (Figure  6 (b)) is used the oscillations are more compared to the oscillations when other functions are used. The graphs 6 (b), 6 (f), 7 (b), 7 (f) plot mean plus standard deviation for VC (ACR) rates. The figures 6 (d), 6 (h), 7 (d), 7 (h) plot corresponding (mean+standard deviation) graphs for the queue lengths.

Note that in the graphs when the step function is used, some of the VCs do not get their max-min fair share rates and the VCs near the fair share have considerable oscillations. The step function is very sensitive to queue length variation near the thresholds. Since the configuration is complex, with large number of VCs passing through each of the switches, the queue length and hence the rates vary. For the graphs 6 (e), 7 (a) and 7the oscillations are only present before steady state. The oscillations die down and the rates become steady since the function f(Q) changes smoothly. The maximum queue length is same for all queue control functions since this depends only on the ICR. When the inverse hyperbolic function is used the queues are larger since in this case the steady state queue length is near Q1.

Figure 4: Simple Configuration: Rate, Queue and Utilization graphs: Step and Linear queue control function
[] img66[] img67  
[] img68[] img69  
[] img70[] img71  
[] img72[] img73  

Figure 5: Simple Configuration: Rate, Queue and Utilization graphs: Hyperbolic and Inverse Hyperbolic queue control function
[] img74[] img75  
[] img76[] img77  
[] img78[] img79  
[] img80[] img81  

Figure 6: GFC-2 Configuration: Rate, Queue and Utilization graphs: Step and Linear queue control function
[] \includegraphics[height=2.8in,angle=-90]{/home/cong/tests/param/1997/ERICA_SIMS/gfc2.snapfile,step,14403,3000000,0.9,1.01,0.95,26,4,1,1,DIR/r.ps}[] img83  
[] img84[] img85  
[] img86[] img87  
[] img88[] img89  

Figure 7: GFC-2 Configuration:: Rate, Queue and Utilization graphs: Hyperbolic and Inverse Hyperbolic queue control function
[] img90[] img91  
[] img92[] img93  
[] img94[] img95  
[] img96[] img97  

Summary of Results

The simulation results obtained by using different queue control functions in the simple and the GFC-2 configurations are consistent with the analytical explanation. The step function is sensitive to queue thresholds ( Q0,Q1,Q2) used. The other functions are not sensitive to these queue thresholds. Small steady state queuing delay can be achieved by choosing nearby values for Q0and Q1.


In this paper we have considered the problem of designing a simple and robust queue control function for switch schemes. A switch scheme tries to maximize utilization, minimize queuing delay and give max-min fair rates to the sources. It is also desirable to have less oscillations in rates and queue length to support (low quality) video over ABR service. We assume a switch scheme model which dynamically adjusts the rate of the sources to match the output rate and drain large queues. The design considerations were discussed with analytical explanations. Four different queue control functions were analyzed. The choice of parameters for the queue control functions was both explored analytically and by simulation. The simulation showed that even in complex configuration (like GFC-2) the system behavior was consistent with of the analytical explanation. When the step function is used, the systems oscillates and does not converge in most cases. From both the analytical and the simulation results, it can be concluded that the inverse hyperbolic is the best queue control function, followed by the hyperbolic and the linear queue control functions. For simpler implementation complexity, the linear function is recommended.


The ATM Forum.
The ATM forum traffic management specification version 4.0.
ftp://ftp.atmforum.com/pub/approved-specs/af-tm-0056.000.ps, April 1996.

S. Kalyanaraman, R. Jain, S. Fahmy, R. Goyal, and B. Vandalore 4.
The ERICA switch algorithm for ABR traffic management in ATM networks.
Submitted to IEEE/ACM Transactions on Networking, Nov. 1997.

L. Roberts.
Enhanced PCRA (Proportional Rate Control Algorithm).
ATM Forum/AF-TM 94-0735R1, 1994.

Ambalavanar Arulambalam, Xiaoqiang Chen, and Nirwan Ansari.
Allocating fair rates for available bit rate service in ATM networks.
IEEE Communications Magazine, 34(11):92-100, November 1996.

Y. Afek, Y. Mansour and Z. Ostfeld.
Phantom: A simple and effective flow control scheme.
In Proc. of the ACM SIGCOMM, August 1996.

A. W. Barnhart.
Example Switch Algorithm for TM Spec.
ATM Forum 95-0195, Feburary 1995.

Robert J. Simcoe.
Test configurations for fairness and other tests.
ATM Forum/94-0557, July 1994.

D. Chiu and R. Jain.
Analysis of the increase/decrease algorithms for congestion avoidance in computer networks.
Computer Networks and ISDN, 17(1), June 1989.


... Analysis 1
Based on ``Design and Analysis of Queue Control Functions for Explicit Rate Switch Schemes'', Bobby Vandalore, Raj Jain, Rohit Goyal, Sonia Fahmy, Proceedings of International Conference on Computer and Communications Networks (IC3N), October 12-15, 1998, Lafayette, Lousiana, pp. 780-786 ©1998 IEEE.
...1 2
Submitted to Computer Networks and ISDN Systems, November 1998.
...2 3
This research was sponsored in part by Rome Laboratory/C3BC Contract #F30602-96-C-0156.
... Vandalore 4
All our papers and ATM Forum contributions are available through http://www.cse.wustl.edu/~jain/index.html

Bobby Vandalore