*********************************************************************
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/