************************************************************************** ATM Forum Document Number: ATM Forum/97-1087 ************************************************************************** Title: Design and Analysis of Queue Control Function for Switch Schemes ************************************************************************** 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 non-zero (small) queues in steady state which can be used if the sources do not have data to send. It is very important to design and analyze the queue control function which is used in such a scheme. In this contribution we study various queue control functions and present analytical explanation of its behavior and simulation results. From the study, we conclude that a simple linear queue control function performs satisfactorily. ************************************************************************* Source: 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}@cse.wustl.edu The presentation of this contribution at ATM Forum is sponsored by NASA Lewis Research Center. ************************************************************************** Date: December 1997 ************************************************************************** Distribution: ATM Forum Technical Working Group Members (AF-TM) ************************************************************************** Notice: This contribution has been prepared to assist the ATM Forum. It is offered to the Forum as a basis for discussion and is not a binding proposal on the part of any of the contributing organizations. The statements are subject to change in form and content after further study. Specifically, the contributors reserve the right to add to, amend or modify the statements contained herein. ************************************************************************** A postscript version of this contribution including all figures and tables has been uploaded to the ATM Forum ftp server in the incoming directory. It may be moved from there to atm97 directory. The contribution is also available on our web page through: http://www.cse.wustl.edu/~jain/atmf/a97-1087.htm 1. Introduction: ---------------- The goals of rate allocation schemes are maintaining high utilization, small queue delay and 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 steady state the rates and queuing delay be constant. One way to achieve 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 simple so that it can be implemented in hardware. In this contribution, we study several queue control functions which satisfy the above needs. We present analytical explanation for performance of these functions. Then we present simulation results which are consistent with the analysis. The various trade-offs between the queue control functions is studied using appropriate metrics. The ERICA+ [6] switch scheme is used in the simulation. 2. Switch Scheme Model: ---------------------- There are many ABR switch schemes ([1, 2, 3, 4, 6]) This section gives an overview of the switching scheme model on which this study is based. * An ABR switch scheme achieves the goals by giving explicit feedback to the sources to adjust their source rates. These are usually known as Explicit Rate Feedback switches. The other common switch model is the Explicit Forward Congestion Indication (EFCI) switch. We assume that an Explicit Rate Feedback switch is used. * One way to achieve high utilization (100%) and control queuing delay by quick draining of queues is to vary the target ABR rate dynamically. During steady state, the target ABR rate is 100% while it is lower during transient overloads. Higher overloads result in even lower target rates (thereby draining the queues faster). In other words: Target rate = f(queue length) x function(current rate,link rate,HPR rate) The HPR rate 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 switch measures the load, queue length and gives explicit feedback of target rate at fixed intervals. This interval is called the "averaging interval". The measurements are done using the FRM cells and the feedback is given using the BRM cells. We assume that only one feedback is given in each averaging interval to the sources. This avoids unnecessary conflicting feedbacks to the sources. The ERICA+ algorithm used in this study fits the above model. 3. 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 desirable goals are presented. The following terms are used in the discussion: N number of sources. ts "averaging interval", the period at which feedback to the sources is calculated at the switch. CCRi(t) current rate of source i. ACRi(t) allowed cell rate calculated at switch. tp propagation time from the source to switch. tf feedback delay is twice tp. Rl link rate (for simplicity, assume all links have same rate) Q(t) switch queue length (in cells) Ri(t) aggregate input rate seen at switch. Ri(t) = Sum (CCRi(t)) 1 <= i <= N C(t) (conversion function) number of cells transmitted in time t at link rate. C(t) = (Rl x t)/424 if Rlis given in Mbps. Note : X(t) denotes that X is a function of time. 3.1 Queue Length Function -------------------------- The current rate is seen at the switch after tp time, so CCRi(t - tp) is rate of source i seen at the switch. The sources adjust their rates based on the feedback information of the switches, ie., CCRi(t) = ACRi(t - tp). In one averaging interval Q(t) is drained by Rlx C(ts) cells. The queue builds up at input rate. Then Q(t) can be expressed as follows: N Q(t) = Q(t - ts) + Sum CCRi(t - tp) - Rl)C(ts) i=1 N Q(t) = Q(t - ts) + Sum ACRi(t - tf) - Rl)C(ts) i=1 Q(t) = Q(t - ts) + (Ri(t) - Rl)ts The switch scheme tries to adjust the input rate Ri(t) to match output rate depending on current queue size, ie., Ri(t) = f(Q(t)) x Available ABR Capacity, if we assume no HPR then Ri(t) = f(Q(t)) x Rl. Hence, Q(t) = Q(t - ts) + (f(Q(t - ts) - 1)RlC(ts) and (f(Q(t - ts) - 1)Rl) is the rate at which the queue changes. 3.2 Explicit Rate ------------------ The sources adjust their rates ACR(t) based on explicit rate feedback from the switch. The source rates lag from the explicit rate by Tf Hence ACR(t) (source rate) can be expressed using the following function; ACR(t) = f(Q(t - tf)) x F(ACR(t - tf); Link Rate; HP rate) For simplicity we assume 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 ACR(t) = f(Q(t - tf) x F(ACR(t - tf); Link Rate) For our ERICA+ scheme the above function is as follows ACR(t - tf) x Link Rate Link Rate ACR(t) = f(Q(t - tf)) x max(_____________________ , ________) Input Rate N where Input Rate is the ABR input rate measured at the switch. The other terms used in ERICA+ are ignored since this is the only term which has the queue control function. The scheme tries to match the input rate to the link rate, by over allocating the rates if the queue is small. If queues are large then they are drained quickly by using part of the link capacity. The function f(Q) is a fraction which modifies the link rate to achieve the above. 3.3 Design of Queue Control Function ------------------------------------- The design considerations for the queue control functions are as follows: o If queue length is very small it should be increased, so that the scheme can maintain some small queue which can used when link is under utilized. This implies that f(Q) should be greater than one. o In steady state we desire constant queue length and target rate to be the max-min fairness rate. The function Q(t) satisfies this goal if f(Q) = 1 in steady state. o If queue is large then part of the link capacity is used to drain the queues. Hence f(Q) should be less than one. It is desirable not to use all the capacity to drain the queue. Therefore, there is a minimum threshold, queue drain limit factor (QDLF), for f(Q). o The f(Q) function has to continuous. Discontinuities imply sudden changes which give rise to oscillations. The queue control function with above properties will be of the form ( 1 0 < Q < Q0 ( = 1 Q0 < Q < Q1 f(Q) = ( < 1 Q1 < Q < Q2 ( = QDLF Q2 < Q < 1 where Q0 < Q1 < Q2 < 1 The following three functions are possible candidates. Step function The step function has multiple thresholds (See figure 1). This is most simplest to implement in hardware (lookup table). ( = sa 0 < Q < Q0 ( = 1 Q0 < Q < Q1 f(Q) = ( = sb Q1 < Q < Q2 ( = QDLF Q2 < Q < infinity where sa > 1 and QDLF < sb < 1 are step parameters. In general it can have n steps. In the above case n = 4. Linear function The fraction f(Q) has linear relationship with queue length. (See figure 1) ( = 1 - mb(Q-Q0)/Q0 0 < Q < Q0 f(Q) = ( = 1 Q0 < Q < Q1 ( = 1 - ma (Q-Q1)/Q1 Q1 < Q Q2 ( = QDLF Q2 < Q < infinity where mb and ma are slope of the linear portions. This function can be implemented in a efficient manner, using shift operations, if ma and mbare of the form 1=2k and the queue length is counted in terms of Q0. Hyperbolic function The fraction f(Q) is a hyperbolic function of the queue length. (See figure 1) ( = 1 - hb(Q-Q0)/((hb-1)Q+Q0) 0 < Q < Q0 ( = 1 Q0 < Q < Q1 f(Q) = ( = 1 - ha(Q-Q1)/((ha-1)Q+Q1) Q1 < Q < Q2 ( = QDLF Q2 < Q < infinity where ha and hbare parameters which control degree of curvature of the hyperbolic function. This function takes more time to calculate, since it has a division operation. For high value of ha the hyperbolic function becomes similar to step function. For ha value near 1, the hyperbolic function approaches the linear function. Note: f(Q2) = QDLF, so Q2 can be expressed in terms of QDLF and a parameter in the case of linear and hyperbolic functions. Figure 1: Queue Control Functions 4. Metrics ---------- 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 (i x tk,(i + 1) x tk) for i = 0, 1,..., where tk ( = 100ms) is a small time interval). Initially the standard deviation is large due to oscillations. The convergence time is i x tk after 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. 5. Analytical Explanation ------------------------- In this section we analyze the behavior of the proposed queue control functions. We assume a simple configuration in our analysis. N infinite ABR sources (always has data to send) are sending data to N ABR destinations (See figure 2). The performance study under more stressful conditions is done by simulation using the Generic Fairness configuration - 2 [7] in the simulations section. Figure 2: N Sources - N Destinations Configuration In the beginning, the queue lengths grow depending on the initial ICR (initial cell rate). So the maximum queue depends on the ICR and round trip time and is independent of the queue control function used. The feedback information reaches the sources and the sources adjust their rates accordingly. The switch initially estimates that the link is under utilized, so it asks the source to increase their rates. But this gives rise to overloaded condition and increases the switch queue lengths. When the queue length crosses Q2 the queues are quickly drained by using (1-QDLF) fraction of link capacity. In the meantime the feedback control loop is established, and the switch gives reliable feedback to the sources. The feedback information tries to match the input rate to output rate. As the input rate approaches output rate the oscillations die down and the network reaches steady state. In steady state the rates and the queue lengths remain constant. This behavior of the system is independent of the queue control function used, since all of them have f(Q) = QDLF when Q(t) > Q2. So, in this analysis we assume that the initial convergence period is over and the network is near the steady state. The change in queue length in a averaging interval ts is given by: Q = f(Q(t - tf) - 1) x Rlx C(ts) 5.1 Step Function ------------------ If Q(t - tf) < Q0 then 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 tf time and it can be expressed as follows: tf Q(t) = Q(t - tf) + (sb- 1) x Rl __ C(ts) ts if tf is a multiple of ts the above simplifies to Q(t) = Q(t - tf) + (sb- 1) x Rl C(tf) If the condition Q0 < Q(t) < Q1 is satisfied, and input rate matches the output rate, then the steady state is achieved, and queue remains at this constant length. If Q1 < Q(t) < Q2 then the Q(t) starts decreasing with slope -(1 - sa). This decrease also takes place for tf time, if the queue ends up between Q0 and Q1 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 parameter Q0, should be small and Q1 should be such that Q1 > Q0+(sb-1)xRlC(tf) is satisfied. 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 Q0 for tf time crosses Q1 and decreases for tf time to a value less than Q0 and this pattern repeats. 5.2 Linear Function -------------------- If Q(t - tf) < Q0, then f(Q(t)) > 1. Similar to the step function the queue keeps growing for tf time with slope of (f(Q(t - tf)) - 1) x Rl. But unlike the step function, the slope now depends on the value of queue length. After tf seconds if the queue Q(t) > Q1, the queue length starts decreasing with a slope of (f(Q(t) - 1) x Rl. 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 less compared to the step function. If the system is near steady state, then the oscillations decrease, queue length becomes Q1 and system reaches steady state. 5.3 Hyperbolic Function ------------------------ The analysis for this case is similar to above. If ha and 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 hyperbolic function has a larger curvature initially and then smooths out, f(Q) value will be smaller when Q1 threshold is crossed compared to the linear function. Hence the fluctuations in the rates are more, but the queue draining is faster. 6. Simulation: Configuration and Parameters ------------------------------------------- In this section the two configurations used in the simulations are explained. 6.1 Simple Configuration: N Source - N Destinations ---------------------------------------------------- In this configuration: (See figure 2) o N infinite sources send data to N destinations o The traffic is one way o The initial value of ICR are chosen randomly in the range (0,link rate) o All links are of length 1000 Km, which corresponds to a propagation delay of 5 ms at 149.76 Mbps o All links have a bandwidth of 149.76 Mbps (after accounting for SONET overhead). o The sources start at random time between (0, tRTT), where tRTT is the round trip time. tRTT = 30 ms for the above configuration. 6.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. This configuration and the expected max-min fairness rate for the different VC's are given in [7] 7. 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, QDLF was chosen to be 0.5. 7.1 Simple Configuration: Results ---------------------------------- The table 1 shows the performance for different step values (parameters) of the step queue control functions as the queue threshold Q1 is 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 Q2 is fixed given the QDLF and other parameters of the linear and hyperbolic functions. Number of sources N = 3. The following things can be observed from the table 1. Figure 3: Generic Fairness Configuration - 2 o The step function never converges entirely. The values are fluctuating near the target values, so the standard deviation after one second is lower than the standard deviation in the first second. o The linear and hyperbolic function reach steady state. The standard deviation after one second is very small. o As Q1 increases the convergence time increases for linear and hyperbolic functions o For Q1 = 2Q0, the linear function converged. The value of f(Q) for hyperbolic function value is less compared to that of linear function, so the queue is drained faster and Q becomes less than Q0. Therefore for the hyperbolic function the queue length and rate values are oscillating near the target value. o For Q1 = 8Q0, the convergence time for hyperbolic function is more than linear. The graphs 4(b), 5(a), 6(a) 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 figures 4(b), 5(b), 6(b) for VC rates and in figures 4(d), 5(d), 6(d) 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 value close to the mean in the steady state. 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) | |___________|________________________________________________________________| | | | | Step | 0.75 1.01 4xQ0 26xQ0 - 252.93 552.21017 501.60 | | | 0.90 1.01 4xQ0 26xQ0 - 98.04 651.82 241.43 | | | 0.90 1.05 4xQ0 26xQ0 - 663.63 1226.70 840.36 | | | 0.95 1.01 4xQ0 26xQ0 - 251.51 816.62 393.26 | | | 0.95 1.05 4xQ0 26xQ0 - 124.11 805.32 240.04 | | | 0.95 1.01 2xQ0 26xQ0 - 896.90 1386.87 1036.66 | | | 0.95 1.01 8xQ0 26xQ0 - 483.20 1001.54 644.73 | | Linear | 1/16 1/16 2xQ0 26xQ0 0.20 311.85 335.61 0.69 | | | 1/16 1/16 4xQ0 26xQ0 0.32 403.52 457.90 0.69 | | | 1/16 1/16 8xQ0 26xQ0 0.61 402.85 622.02 0.69 | |Hyperbolic | 1.15 1.05 2xQ0 26xQ0 - 509.94 423.89 205.65 | | | 1.15 1.05 4xQ0 26xQ0 0.32 214.19 500.14 0.86 | | | 1.15 1.05 8xQ0 26xQ0 0.82 220.96 862.25 0.63 | |___________|________________________________________________________________| The (e) graph shows the utilization for the bottleneck link. 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 steady state the rate and queue length are constant and utilization is 100%. Hence the linear and hyperbolic queue control function fulfill the desired goal. This is consistent with the analytical explanation given in the previous section. 7.2 GFC-2 Configuration: Results --------------------------------- The following parameters were used in the simulations for this configuration. o Thresholds: Q0 = 176, Q1 = 4 x Q0, Q2 = 26 x Q0, QDLF = 0:5 o Step: sa = 0:95, sb= 1:01 o Linear: ma = 1=16, mb= 1=16 o Hyperbolic: ha = 1:15, mb= 1:05 The table 2 shows 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 the three cases. The rate variation is much less in linear and hyperbolic functions compared to step function. 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 | | HyperbolicH(1) ACR 1.45 52.77 13.57 0.58 | | SW5 Queue 1.3 361.32 968.27 201.86 | |_________________________________________________________________| 7.3 GFC-2 Configuration: Graphs -------------------------------- The graphs 7, 8, 9 were obtained by simulating the GFC-2 configuration using the step, linear and hyperbolic queue control functions respectively. Figures 7(a), 8(a), 9(a) show the ACR rate for one VC of each of A through H type VCs versus time. The (b) 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 QDLF and queues are drained quickly. Again in 7(b) oscillations when step function is used are more compared to the oscillations when other two functions are used. The graphs 7(c), 8(c), 9(c) plot mean plus standard deviation for VC rates. The figures 7(d), 8(d), 9(d) plot corresponding (mean+standard deviation) graphs for the queue lengths. The graphs 7(e), 8(e), 9(e) give the utilization of all the links between the switches. Note that in graphs when 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 switchs, the queue length and hence the rates vary. For the graphs 8(a),9(a) the oscillations are only present before steady state. The oscillations die down and the rates become steady since the function f(Q) changes smoothly. Figure 4: Simple Configuration: Rate, Queue and Utilization graphs: Step queue control function Figure 5: Simple Configuration: Rate, Queue and Utilization graphs: Linear queue control function Figure 6: Simple Configuration: Rate, Queue and Utilization graphs: Hyperbolic queue control function Figure 7: GFC-2 Configuration: Rate and Queue graphs for: Step queue control function Figure 8: GFC-2 Configuration: Rate, Queue and Utilization graphs: Linear queue control function Figure 9: GFC-2 Configuration:: Rate, Queue and Utilization graphs: Hyperbolic queue control function 8. Conclusion -------------- In this contribution we have considered the problem of designing a simple and good queue control function for switch schemes. A switch schemes 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. Three different queue control functions were considered. The choice of parameters for the queue control functions was explored analytically and by simulation. Simulation showed that even in complex configuration (like GFC-2) the system behavior was similar as explained analytically. Both from the analytical and the simulation results it can be concluded that the both hyperbolic and linear queue control function achieve the desired goals. For simpler implementation complexity the linear function is recommended. References ---------- [1] Larry Roberts. Enhanced PRCA (Proportional Rate-Control Algorithm). ATM Forum 94-0735R1, August 1994. [2] 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. [3] Yehuda Afek, Yishay Mansour, and Zvi Ostfeld. Phantom: A Simple and Effective Flow Control Scheme. In Proceedings of the ACM SIGCOMM, pages 169-182, August 1996. [4] A. W. Barnhart. Example Switch Algorithm for TM Spec. ATM Forum 95-0195, February 1995. [5] R. Jain A. Charny, D. D. Clark. Congestion control with explicit rate indication. In Proceedings of ICC 95, June 1995. [6] Raj Jain, Shivkumar Kalyanaraman, Rohit Goyal, Sonia Fahmy, and Ram Viswanathan. ERICA switch algorithm: A complete description. ATM Forum/96-1172, August 1996. [7] Robert J. Simcoe. Test configurations for fairness and other tests. ATM Forum/94-0557, July 1994.