********************************************************************* ATM Forum Document Number: ATM Forum/98-0408 ********************************************************************* Title: Overload based Explicit Rate Switch Schemes with MCR guarantees ********************************************************************* Abstract: In this contribution, we present four overload based switch schemes which provide MCR guarantees. A typical explicit rate switch scheme monitors the load and gives feedback to the sources. We define the overload factor as the ratio of the input rate to the available ABR capacity. All the switch schemes proposed in this contribution use the overload factor to calculate feedback rates. A dynamic queue control mechanism is used to control queues and achieve constant queuing delay at steady state. The algorithms proposed are studied and compared using several configurations. ********************************************************************* Source: Bobby Vandalore, Sonia Fahmy, Raj Jain, Rohit Goyal, Mukul Goyal 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 This presentation of this contribution is sponsored by NASA Lewis Research Center. *********************************************************************.fi Date: February 1998 ********************************************************************* 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. ********************************************************************* 1 Introduction In [2], we had proposed a general definition of fairness, and gave an overload based ABR (available bit rate) switch scheme which provides MCR (minimum cell rate) guarantees. In this contribution, we propose three additional algorithms which use the overload factor to calculate the explicit rate feedback. All the proposed algorithms provide MCR guarantee and generalized fairness. The load factor (also referred to as "overload factor" or "overload") is the ratio of the measured input rate to the available ABR (available bit rate) capacity. Our switch schemes monitor the load on the link and calculate feedback [4, 1] based on the load. The switch schemes try to achieve unit load to efficiently use the link and also converge to max-min fairness [5]. Max-min fairness assumes zero MCR values. In this contribution, we have used the generalized fairness with MCR as defined in [2]. The proposed algorithms are similar to the ERICA+ scheme [1]. We first briefly describe ERICA+ and then the algorithms proposed. The algorithms are tested using simulations on various con- figurations. The simulations test whether the schemes provide MCR guarantees and converge to generalized fairness. We give a comparison of the algorithms based on the simulations results. 2 General Fairness: Definition We define the following parameters: Al= Total available bandwidth for all ABR connections on a given link l. Ab = Sum of bandwidth of under-loaded connections which are bottle-necked elsewhere. A = Al- Ab, excess bandwidth, to be shared by connections bottle-necked on this link. Na = Number of active connections Nb= Number of active connections bottle-necked elsewhere. n = Na- Nb, number of active connections bottle-necked on this link. i= MCR of connection i. P n mu = i=1iSum of MCRs of active connections within bottle-necked on this link. wi= preassigned weight associated with the connection i. gi= GW fair Allocation for connection i. The general fair allocation is defined as follows: gi= i+ wi(A_-_)_Pn j=1wj The excess available bandwidth (A - mu) is divided in proportion to the predetermined weights. 3 The Switch Schemes The general structure of the algorithms proposed are similar to the ERICA+ [1]. First, we briefly discuss the ERICA+ algorithm and then give the general structure of the proposed algorithms. The four different algorithms have the same structure and only differ in the end of interval accounting, and in the manner in which the feedback is calculated. 3.1 Overview of ERICA+ ERICA+ operates at the output port of a switch. It periodically monitors the load, active number of VCs and provides feedback in the BRM (backward RM) cells. The measurement period is called the "averaging interval." The measurements are done in forward direction and feedback is given in the reverse direction. ERICA+ Algorithm At the end of the Averaging Interval: Total ABR Capacity <-- Link Capacity- VBR Capacity (1) Target ABR Capacity <-- Fraction x Total ABR Capacity (2) (3) z <-- ABR_Input_Rate/Target ABR Capacity (4) FairShare <-- Target_ABR_Capacity/Number of Active(VCs5) MaxAllocPrevious <-- MaxAllocCurrent (6) MaxAllocCurrent <-- FairShare (7) When an FRM is received: CCR[VC] CCR_in_RM_Cell When a BRM is received: VCShare CCR[V_C]_z (8) IF(z > 1 + ffi) THEN ER Max (FairShare, VCShare) (9) ELSE ER Max (MaxAllocPrevious, VCShare) (10) MaxAllocCurrent Max (MaxAllocCurrent,ER) (11) IF (ER> FairShareAND CCR[VC] < FairShare) THEN ER FairShare (12) ER_in_RM_Cell Min (ER_in_RM_Cell, ER, Target ABR Capacity)(13) In overload (z > 1 + ffi) conditions, the algorithm calculates the maximum of the FairShare and VCShare as the feedback rate. In under- load conditions, the maximum of MaxAllocPrevious (which is the maximum allocation given in the previous averaging interval) and the previous two terms is the feedback rate. Equation 12 avoids sudden increase in the feedback rate. The Fraction term is used to control the queues, by dynamically varying target ABR capacity. 3.2 Overload Based Algorithm: General Structure The four different switch schemes have the following common algorithmic structure. They differ in the manner in which the feedback rate is calculated and accounting. Overload Based Algorithm X At the end of Averaging Interval: Total ABR Capacity Link Capacity- VBR Capacity nX - min(SourceRate(i); i) (14) i=0 Target ABR Capacity Fraction x Total ABR Capacity nX Input Rate ABR Input Rate- min(SourceRate(i); i) i=0 z ____Input_Rate___Target ABR Capacity (15) End_of_Interval_Accounting() (16) (17) When an FRM is received: CCR[VC] CCR_in_RM_Cell When a BRM is received: Excess_ER Calculate_Excess_ER() (18) ER i+ Excess_ER (19) ER_in_RM_Cell Min(ER_in_RM_Cell,ER,Target ABR Capacity) (20) (21) The key steps which differentiate the algorithms are the procedures End_of_Interval_Accounting() and Calculate_Excess_ER(). 3.3 Algorithm A: VCShare and ExcessFairShare The ExcessFairShare term is defined as follows: ExcessFairShare(i) = wi(A_-_)_Pn j=1wj This divides the excess available bandwidth (A - ) proportional to the weights w(i). The activity level for a given VC is defined as follows: AL(i) = minimum 1; SourceRate(i)_-_iExcessFairShare(i) The activity level can be used to accurately estimate the effective number of VCs [3]. We extend this notion to the weighted case by multiplying the weight function with the activity level of the ExcessFairShare term. Therefore the ExcessFairShare is: ExcessFairShare(i) = wiAL(i)(A_-_)_Pn j=1wjAL(j) In Algorithm A, the Excess_ER is calculated based on the V CShare and the ExcessFairShare terms. End_of_Interval_Accounting(): foreach VC i AL(i) minimum 1; SourceRate(i)_-_iExcessFairShare(i)(22) ExcessFairShare(i) (Target_ABR_Capacity)wi_Pn (23) j=1wjAL(j) (24) endfor Calculate_Excess_ER(): VCShare SourceRate(i)_-_iz (25) Excess_ER Max (ExcessFairShare(i), VCShare) (26) (27) 3.4 Algorithm B: ExcessFairShare/Overload In this version, the Excess_ER is calculated based on ExcessFairShare and overload factor z. As the network reaches steady state, the overload will become one and the Excess_ER will converge to the required fairshare. In this algorithm, the End_of_Interval_Accounting() is the same as in the previous algorithm (algorithm A). Calculate_Excess_ER(): Excess_ER ExcessFairShare(i)_z (28) 3.5 Algorithm C: MaxAllocation/Overload The weighted maximum allocation is defined as the maximum of allocation divided by the weight among all VCs. The Excess_ER is calculated based on weighted maximum previous allocation (WtMaxAllocPrevious) and overload. Let i be the VC number in the BRM cell. End_of_Interval_Accounting(): WtMaxAllocPrevious WtMaxAllocCurrent (29) WtMaxAllocCurrent 0 (30) (31) Calculate_Excess_ER(): Excess_ER w(i)WtMaxAllocPrevious_z (32) WtMaxAllocCurrent Max (WtMaxAllocCurrent,Excess_ER/w(i)) (33) (34) Let j be the VC such that Excess_ER(j)=w(j) is the maximum of Excess_ER(i)=w(i). The Excess_ER(i) calculated by the above algorithm is proportional to the weight w(i). As the overload converges to one, the allocation Excess_ER(i) converges to the ExcessFairShare(i) term. 3.6 Algorithm D: VCShare and MaxAllocation The Excess_ER is calculated based on weighted maximum previous allocation (WtMaxAllocPrevious) and V CShare. In this algorithm, the End_of_Interval_Accounting() is the same as in the previous algorithm (algorithm C). Calculate_Excess_ER(): VCShare SourceRate(i)_-_iz (35) IF (z > 1 + ffi) THEN Excess_ER VCShare (36) ELSE Excess_ER Max (w(i) WtMaxAllocPrevious, VCShare) (37) WtMaxAllocCurrent Max (WtMaxAllocCurrent,Excess_ER/w(i)) (38) (39) 4 Simulation Configurations We used simple, transient, link bottleneck and source bottleneck configurations to test the proposed algorithms. Infinite sources were used (which have infinite amount of data to send, and always send data at ACR) in all the simulations. The data traffic is only one way, from source to destina- tion. All the link bandwidths are 149.76 (155.52 less the SONET overhead), except in the GFC-2 configuration. 4.1 Three Sources This is a simple configuration in which three sources send data to three destinations over a two switches and a bottleneck link. See figure 1. This configuration is used to demonstrate that the switches algorithms can achieve the general fairness. Figure 1: N Sources - N Destinations Configuration 4.2 Source Bottleneck In this configuration, the source S1, is bottle-necked to rate (10 Mbps), which below its fairshare (50 Mbps) for first 400 ms of the simulation. This configuration tests whether the fairness criterion can be achieved in the presence of source bottleneck. Figure 2: 3 Sources - Bottleneck Configuration 4.3 Generic Fairness Configuration - 2 (GFC-2) This configuration is a combination of upstream and parking lot configuration (See Figure 3). In the configuration all the links are bottle-necked links. This configuration is explained in [7]. Figure 3: Generic Fairness Configuration - 2 4.4 Simulation Parameters The simulations were done using extensively modified version of NIST ATM simulator [6]. The parameter values for different configurations is given in Table 1. The algorithms use dynamic queue control to vary the target ABR capacity depending on length of queue at the switch. The queue control function achieves a constant queue length at steady state. The "Target Delay" parameter specifies the desired queue length at steady state. Table 1: Simulation Parameter Values _____________________________________________________ | | ConfigurationLin|k A|veragingT|arget |Weight | | |_|______Name_____D|istancei|nterval_D|elayFu|nction_| | | | Three Sources100|0 Km |5 ms |1.5 ms | 1 | | | | Source Bottleneck1|000 Km5|ms |1.5 ms | 1 | | |_|______GFC-2___100|0_Km_|_15_ms___|1.5_ms_|_1____|_|_ Exponential averaging was used to decrease the variation in measured quantities such as overload and number of VCs. Exponential averaging of overload factor and number of VCs were done with a decay factor of 0.8 for algorithms A and D. The algorithms B and C are more sensitive to overload factor. So, a the decay factor of 0.4 was used to average overload in algorithms C and D. The weight function of one was used in all configurations. This corresponds to MCR plus equal share of excess bandwidth. The value of ffi = 0:1 was used for algorithm D. 5 Simulation Results In this section we present the simulation results of algorithms using different configurations. 5.1 Three Source: Results The MCR value for the three source configuration is 10,30,50 for the source 1, source 2 and source 3 respectively. The excess bandwidth (149.76 - 90 =) 59.76 is divided equally among the three sources. The expected allocation is (10+59.76/3, 30+59.76/3, 50+59.76/3) = (29.92, 39.92, 69.92). The figure 4(a)-(d) shows the ACRs (allowed cell rate) for algorithms A,B,C and D respectively. From the figure it can be seen that the expected allocation is achieved by all the four algorithms. 5.2 Three Source transient : Results MCR value of zero was used for all three sources in this configuration. The configuration simulation was simulated for 1.2 seconds. Source 2, is a transient source. It is active between 0.4 to 0.8 seconds of the simulation. The expected allocation is (74.88,0,74.88) during (0,0.4s) and (0.8-1.2s) where source 2 is not active. The expected allocation is (49.92,49.92,49.92) during (0.4,0.8) interval. The figure 5 (a)-(d) shows the ACRs for the algorithms A, B, C and D respectively. All the algorithms achieve the expected allocation in both non-transient and transient periods. Algorithm B is sensitive to queue control function, hence there rates oscillate during the non-transient periods. 5.3 Source Bottleneck: Results In this configuration the MCR values of (10,30,50) were used. The total simulation time was 800 ms. The source S1, is bottlenecked at 10 Mbps for first 400 ms of the simulation. It always sends data up to 10 Mbps even its ACR larger than 10 Mbps. The figures 6 (a)-(d) shows the ACRs for the algorithms A, B, C and D respectively. The expected allocation is (49.86,59.86,79.86) for first 400 ms and it is (29.92,49.92,69.92) after 400 ms. The algorithms A and B do not converge to the expected allocation. The CCR value in the RM cells of source S1, do not reflect the actual source rate. The algorithms C and D do converge to the expected allocation. Algorithm C performs better than algorithm D, since it has lesser oscillations. The figures 7 (a)-(b) show the ACRs using measured source rate (per VC option) instead CCR field of for algorithms A, B. When measured source rate is used the algorithms A and B do converge to expected allocations in the presence of source bottleneck. 5.4 GFC2 : Results MCR value of zero was used for all sources. The figure 8 (a)-(d) show the ACRs of each type of VCs A through H for algorithms A, B, C and D respectively. The graphs show that the expected allocation as given in the table 2 is achieved by all the algorithms. Algorithm B and D have rate oscillations due to queue control. The maximum queue occurred at switch SW6 around 500 ms for all algorithms. The value of the maximum queue was 39000, 30000, 340000 and 34000 cells for algorithms A, B, C and D respectively. Algorithm C does not have any queue control. Algorithm C had a huge queue because the maximum allocation for A type VC which has large round trip time was assigned for seven VCs of type G which have small round trip time. The input rate at the link between SW6 and SW7 is overloaded by a factor of seven which gives rise to the huge queues. Table 2: GFC-2 configuration: Expected allocations __________________________________________________ |_|________VC______A_||B_|C__|D_|_E__|F__|G_|_H__| | |_|_Expected_allocation1|05||353|53|51|0_|5__|52.5_|_| 6 Comparison of Switch Schemes The Table 3 gives a comparison of the algorithms. ________________________________________________________________________________ | Scheme En|d of IntervalF|eedbackMa|x. QueueR|equires Per VC forS|ensitivity | ___Name____|Complexity_Co|mplexity_|Length___|Source_BottleneckQu|eue_control_| | Algorithm A |O(N) | O(1) | Medium | Yes | Yes | | Algorithm B |O(N) | O(1) | Medium | Yes | Yes | | Algorithm C |O(1) | O(1) | Large | No | No | |_Algorithm_D_|O(1)_____|___O(1)____|_Medium___|______No________|____No______| Table 3: Comparison of the algorithms The algorithm D is the best of the proposed algorithm since it is of O(1) complexity, does not require per VC accounting and is not sensitive of the queue control function. 7 Conclusion In this contribution we have presented four algorithms which achieve generalized fairness and provide MCR guarantee. The algorithms monitor the load on the link and calculate the overload factor. The overload is used with ExcessFairShare or WtMaxAllocPrevious to calculate the feedback. The algorithm D, which uses the V CShare and WtMaxAllocPrevious is the best, since it has O(1) complexity and does not require per VC accounting to handle source bottlenecks. (a) Algorithm A (b) Algorithm B (c) Algorithm C (d) Algorithm D Figure 4: Three Sources: ACR graphs for algorithms A, B, C and D. (a) Algorithm A (b) Algorithm B (c) Algorithm C (d) Algorithm D Figure 5: Three Sources transient: ACR graphs for algorithms A, B, C and D. (a) Algorithm A (b) Algorithm B (c) Algorithm C (d) Algorithm D Figure 6: Source Bottleneck: ACR graphs for Algorithm A, B, C and D (a) Algorithm A (b) Algorithm B Figure 7: Source Bottleneck: ACR graphs for Algorithm A, B using measured source rate (a) Algorithm A (b) Algorithm B (c) Algorithm C (d) Algorithm D Figure 8: GFC-2 configuration: ACR graphs for algorithms A, B, C and D. References [1]Shivkumar Kalyanaraman, Raj Jain, Rohit Goyal, Sonia Fahmy, and Bobby Vandalore (see footnote 1) "The ERICA Switch Algorithm for ABR Traffic Management in ATM Networks". Submitted to IEEE/ACM Transactions on Networking, November 1997, [2]Bobby Vandalore, Sonia Fahmy, Raj Jain, Rohit Goyal, Mukul Goyal, "Generalized Fairness support in Switch Algorithms" ATM Forum/98-0151, February 1998, [3]Sonia Fahmy, Raj Jain, Shivkumar Kalyanaraman, Rohit Goyal, and Bobby Vandalore. Deter- mining the number of active ABR sources in switch algorithms. ATM Forum/98-0154, February 1998. [4]L. Roberts. "Enhanced PCRA (Proportional Rate Control Algorithm)". ATM Forum Contribution/AF-TM 94-0735R1, August 1994. [5]Shirish S. Sathaye. "ATM Forum Traffic Management Specification Version 4.0". April 1996 [6]Nada Golmie. "Netsim: network simulator". http://www.nist.gov/. [7]Robert J. Simcoe. "Test configurations for fairness and other tests". ATM Forum/94-0557, July 1994. _______________________________ (Footnote 1:) All our papers and ATM Forum contributions are available through http://www.cse.wustl.edu/"jain/