Bobby Vandalore, Raj Jain, Rohit Goyal, Sonia Fahmy
The Ohio State University
Department of Computer and Information Science
Columbus, OH 432101277
Contact Phone: 6142923989, Fax: 6142922911
Email: {vandalor,jain, goyal, fahmy}@cse.wustl.edu
Abstract
The main goals of a switch scheme are high utilization, low queuing delay and fairness. To achieve high utilization the switch scheme can maintain nonzero (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 BISDN (broadband 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 Nrm1 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 tradeoffs between the queue control functions are studied using appropriate metrics. The ERICA+[ 2] switch scheme is used in the simulations.
This section gives an overview of the switching scheme model on which this study is based.
HPR is the total rate of higher priority classes like VBR (variable bit rate) and CBR (constant bit rate). The ``f(queue length)'' has to be a decreasing function of the queue length. The switch scheme uses the above queue control function to adjust the allocated rate depending on the current switch queue size.
The ERICA+algorithm used in this study fits the above model.
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:
Note : X(t) denotes that Xis a function of time.
The switch scheme tries to adjust the input rate R(t) to match the output rate depending on current queue size, i.e., . We assume no higher priority traffic, so . Hence,
and (f(Q(tt_{s}))  1) R_{l}is 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.
The sources adjust their rates r_{i}(t) based on the explicit rate feedback from the switch. The feedback reaches the switch after time t_{p}. Hence, r_{i}(t) (source rate) can be expressed using the following equation ;
Since t_{f}= 2 t_{p}, 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 (1f(Q)) part of the link capacity.
For other schemes the following modification can be done to incorporate queue control function with that scheme. Let er_{A}(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 maxmin rates, then the modified algorithm also converges to the maxmin rate. Further, the queue control function f(Q) can be chosen so that the queue length (and hence delay) is constant in steady state.
The queue control function with above properties will be of the form
where
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).
where s_{a}> 1 and are 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 m_{b}and m_{a}are slope of the linear portions. This function can be implemented in an efficient manner, using shift operations, if m_{a}and m_{b}are of the form 1/2^{k }and the queue length is counted in terms of Q_{0}.
Hyperbolic function
The function f(Q) is a hyperbolic function of the queue length. (See figure
1 (b))
where h_{a}and h_{b}are 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 h_{a}the hyperbolic function becomes similar to the step function. For an h_{a}value 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 and are the parameters which control the degree of curvature of the inverse hyperbolic and hyperbolic functions. This function is continuous and smooth at both Q_{0}and Q_{1}.
The curve used in the control function in underload region is called the ``acurve'' and the one used in over loaded region is called the ``bcurve''. The parameters used in the acurve are called aparameters. are called the bparameters. Note that, since all the functions are continuous, at Q_{2}we have the equation f(Q_{2}) = QDLF. So, Q_{2}can be expressed in terms of QDLFand aparameterfor linear, hyperbolic and inverse hyperbolic functions.
Visual inspection of the graphs also gives a good idea about the convergence time and the variations.
The change in queue length in a averaging interval t_{s}is 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 and f(Q) < 1 for . 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 Q_{0}and Q_{1}. 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 (yaxis) versus time (xaxis). The queue length decreases linearly in the range (highly overloaded) with slope QDLF. For queue length in the range (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 acurve) with respect to time. In the steady state, ( ) the queue length is constant. In under utilized range , the queue increases inverse hyperbolically since the slope is f(Q)  1and f(Q) is hyperbolic.
If Q(tt_{f}) < Q_{0}then f(Q(tt_{f}) = s_{b}> 1, so the queue grows till feedback information is passed to the sources asking them to decrease their rate. The queue grows for t_{f}time and it can be expressed as follows:
If the condition Q_{0}< Q(t) < Q_{1}is satisfied and the input rate matches the output rate, then the steady state is achieved, and the queue remains at this constant length.
If Q_{1}< Q(t) < Q_{2}then the Q(t) starts decreasing with slope (1s_{a}). This decrease also takes place for t_{f}time, if the queue ends up between Q_{0}and Q_{1}and 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 Q_{0}and Q_{1}. This requirement is satisfied if the condition holds. 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 Q_{0}for t_{f}time, crosses Q_{1}, and decreases for t_{f}time to a value less than Q_{0}. Then, this pattern repeats.
Queue  a  b  Q_{1}  Q_{2}  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 Q_{0}  26 Q_{0}    252.93  552.21017  501.60 
0.90  1.01  4 Q_{0}  26 Q_{0}    98.04  651.82  241.43  
0.90  1.05  4 Q_{0}  26 Q_{0 }    663.63  1226.70  840.36  
0.95  1.01  4 Q_{0}  26 Q_{0}    251.51  816.62  393.26  
0.95  1.05  4 Q_{0}  26 Q_{0}    124.11  805.32  240.04  
0.95  1.01  2 Q_{0}  26 Q_{0}    896.90  1386.87  1036.66  
0.95  1.01  8 Q_{0}  26 Q_{0}    483.20  1001.54  644.73  
Linear  1/16  1/16  2 Q_{0}  26 Q_{0}  0.20  311.85  335.61  0.69 
1/16  1/16  4 Q_{0}  26 Q_{0}  0.32  403.52  457.90  0.69  
1/16  1/16  8 Q_{0}  26 Q_{0}  0.61  402.85  622.02  0.69  
Hyperbolic  1.15  1.05  2 Q_{0}  26 Q_{0}    509.94  423.89  205.65 
1.15  1.05  4 Q_{0}  26 Q_{0}  0.32  214.19  500.14  0.86  
1.15  1.05  8 Q_{0}  26 Q_{0}  0.82  220.96  862.25  0.63  
Inverse  36  1.05  2 Q_{0}  26 Q_{0}  0.22  313.17  525.51  0.69 
Hyperbolic  16.5  1.05  4 Q_{0}  26 Q_{0}  0.25  209.50  580.15  0.50 
6.75  1.05  8 Q_{0}  26 Q_{0}  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 nonzero hence, the utilization at the steady state is 100%.
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.
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 
The graphs in Figure 6and 7were obtained by simulating the GFC2 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 maxmin 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 Q_{1}.




The simulation results obtained by using different queue control functions in the simple and the GFC2 configurations are consistent with the analytical explanation. The step function is sensitive to queue thresholds ( Q_{0},Q_{1},Q_{2}) used. The other functions are not sensitive to these queue thresholds. Small steady state queuing delay can be achieved by choosing nearby values for Q_{0}and Q_{1}.
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 maxmin 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 GFC2) 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.