Available bit rate flow control algorithms for ATM networks

Methods and apparatus for an ATM network for determining an allowed cell rate without the introduction of oscillations by using a average cell rate of all virtual circuits. Each ATM switch may be configured to calculate an allowed cell rate (ACR) for each connection between adjacent ATM switches along the virtual circuit and to relay this information back to a source using a BRM cell.

FIELD OF THE INVENTION
 The invention relates generally to asynchronous transfer mode (ATM)
 networks and, more particularly, to available-bit-rate (ABR) flow control
 algorithms.
 BACKGROUND
 The ABR service class has been defined by the ATM Forum as one of the five
 service classes in an ATM network. In an explicit-rate mode of ABR service
 in an ATM network, a real-time determination may be made as to the amount
 of bandwidth that each ABR circuit may utilize. The amount of bandwidth
 allocated to each ABR circuit is known as the Allowed Cell Rate (ACR). The
 ACR may be transmitted to the source of each circuit via special control
 cells known as resource management (RM) cells. The format of RM cells and
 the principles governing their generations and usage are specified by the
 ATM Forum Traffic Management 4.0 standard. There are two types of RM
 cells, Forward RM cells (FRM) which travel from the source to the
 destination, and Backward RM cells (BRM) which travel from the destination
 back to the source. Specifically, the Allowed Cell Rate is marked into the
 BRM cells because they are received by the source with a smaller delay
 than FRM cells. Also, according to the standard, the FRM cell contains a
 Current Cell Rate (CCR) field which is set by the source to indicate to
 the ATM network the cell rate at which the source is currently
 transmitting traffic. The intention of the CCR field is to assist the
 network in determining the ACR for all ABR circuits.
 One key to a successful implementation of ABR service is the ATM network's
 capability to quickly and fairly adjust the allowed cell rate (ACR) for
 each ABR circuit when the level of congestion within the network changes.
 Accordingly, improved algorithms are desirable for varying the allowed
 cell rate (ACR) in ATM networks for each ABR circuit.
 SUMMARY OF THE INVENTION
 The present invention provides improved algorithms for varying the allowed
 cell rate (ACR) in ATM networks for each ABR circuit. Advantages of one or
 more aspects of the present invention include one or more of the
 following: 1) determining optimal ACR values which allow the sources to
 fully utilize the bandwidth of a trunk, 2) allowing convergence to an
 optimal ACR for each circuit quickly with minimal oscillation, 3)
 minimizing ACRs which are below the optimal values to prevent the ATM
 network bandwidth from being under-utilized, 4) minimizing ACRs which are
 above the optimal values to prevent buffer resources from being consumed
 and possible resulting loss of cells, 5) providing for weighted max-min
 fairness criteria as specified in the ATM Forum Traffic Management
 Document version 4.0 such that, for each trunk within the network, the ACR
 allocated to each circuit should be in proportion to the weight assigned
 to each circuit, and for a circuit traversing multiple trunks, the minimum
 ACR value allowed by all traversed trunks should be used as the ACR value
 for the circuit, 6) allowing for widely varying delays among different
 virtual circuits (VC) to accommodate a new allowed cell rate (ACR) values
 which arrive at the source with a varying delay after they are generated,
 7) allowing for bottlenecked trunks where some VCs become bottlenecked at
 other trunks, and thus do not respond to an increase in ACR signaled by a
 particular trunk, and 8) the steady-state of the output queue length
 scales with the number of virtual circuits.
 Aspects of the invention provide improved algorithms for use by the
 available-bit-rate (ABR) service in asynchronous-transfer-mode (ATM)
 networks to rapidly determine the optimal values of the Allowed Cell Rate
 (ACR) for individual Virtual Circuits (VC) using the ABR service.
 In aspects of the present invention, each ATM switch along the path of an
 ABR virtual circuit (VC) calculates a weighted average of a measure of
 congestion at the particular ATM switch. The weighted average of the
 measure of congestion is then used to calculate an acceptable average rate
 at which the switch may operate. A weighted acceptable rate is then
 determined for each virtual circuit and compared with a measured and/or
 indicated cell rate for that virtual circuit. As an option, it may be
 desirable to keep track of the cell rate information of each of the
 virtual circuits to determine which virtual circuits are bottlenecked
 based on responsiveness of a measured cell rate to a newly requested cell
 rate. When the average cell rate is updated, the cell rates of
 bottlenecked connections are not included in the computation of a new
 average cell rate. In this manner, bottlenecked circuits will not reduce
 the responsiveness of the algorithm. In accordance with the above
 determinations, explicit rate and/or single-bit congestion indications are
 sent back to the traffic sources utilizing one or more resource-management
 (RM) cells. The feedback information contained in the resource-management
 cells may be utilized by each traffic source to regulate its traffic flow
 and thereby achieve high utilization of the network.
 In another aspect of the invention, an algorithm is utilized which may
 perform one or more of the following functions in any combination and/or
 subcombination: 1) estimating the direction and extent of the desired
 change in the total flow rate based on both current queue length and sum
 of exponentially weighted past and present queue growth rates; 2) using a
 nonlinear mapping function to map estimated change in the total flow rate
 to the desired change in the average rate of all VCs; and/or 3) adapting
 to change of network conditions quickly.
 Simulation studies show that algorithms in accordance with one or mores
 aspects of the invention exhibits one or more of the following properties:
 1) robust performance in different network configurations, load
 conditions, and/or traffic types; 2) fast transient response yet very
 stable steady-state behaviors, thus maximizing the utilization of the
 network resource; 3) ensures the weighted max-min fairness among all VCs,
 even where there are VCs bottlenecked at some other switches; 4) low
 implementation complexity; 5) compatibility with other ABR flow control
 algorithms; and/or 6) compliance with existing ATM Forum traffic
 management standards.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
 Referring to FIG. 1, an ATM network 1 may include, for example, a plurality
 of interconnected ATM switches ATM A, ATM B, and ATM C interconnecting one
 or more pieces of equipment located on the customer's premises (e.g.,
 customer premises equipment A (CPE A) and customer premises equipment B
 (CPE B)). The ATM network 1 may be configured to carry data over a wide
 area such as an entire country and/or globally. The ATM network 1 may have
 a plurality of virtual circuits operating using any one of a plurality of
 service categories such as constant bit rate, real-time variable bit rate,
 non-real-time variable bit rate, available bit rate (ABR), and/or
 unspecified bit rate. The available bit rate category of service may be
 configured to adapt to a time-varying bandwidth availability in the ATM
 network 1. For example, where the CPE A in FIG. 1 can reduce or increase
 the rate at which data is output responsive to changes in bandwidth
 capacity of the ATM network 1, the available bit rate service class may be
 an appropriate service class for this particular CPE. The available bit
 rate class of service allows the bandwidth of the network to be maximized
 through the exploitation by available bit rate sources of changes and
 other fluctuations in traffic across the ATM network 1.
 To guarantee fairness, each ABR virtal circuit may have a predefined peak
 cell rate and a minimum cell rate. In some embodiments, the minimum cell
 rate may be zero. Within this range, in an explicit-rate mode, a real-time
 determination may be made as to the amount of bandwidth (e.g., the allowed
 cell rate) that each ABR virtual circuit may utilize. This real-time
 determination may be made using a rate based flow control algorithm which
 communicates the new rates using one or more resource management cells.
 The ABR service category may be used for such applications as local area
 network (LAN) emulation across an ATM network.
 Resource management allows network resources to be allocated in a manner
 which is consistent with service characteristics of various customer
 premises equipment such as CPE A and/or CPE B. One technique for
 allocating network resources in, for example, ATM network 1 is the use of
 one or more virtual connections between two network endpoints such as CPE
 A and CPE B. The use of virtual connections allow the separation of
 different traffic types requiring different service classes and/or
 different minimum/peak cell rates within a single service class. Resource
 management functions include service class and route selection, bandwidth
 allocation, and flow control. The need for improved resource management
 functions in the available bit rate (ABR) category of service is
 particularly acute because in this class of service the ATM network 1
 typically must adapt its flow rate very quickly to fluctuations in traffic
 and other network conditions across the ATM network 1. In this manner, the
 ABR applications may make maximum use of the available bandwidth without
 impacting traffic on other service classes such as constant bit rate and
 variable bit rate service classes.
 In order to achieve the above mentioned resource management, it is
 desirable to implement a robust flow control scheme such as rate-based
 flow control and/or credit-based flow control. In exemplary embodiments,
 rate-based flow control may be implemented using resource management cells
 to control the amount of bandwidth allocated to each ABR virtual circuit.
 In a forward direction (e.g., CPE A to CPE B), forward resource management
 cells (FRM) may be utilized to communicate information from the source to
 the destination as shown in FIG. 1. Similarly, in a backward direction,
 backward resource management (BRM) cells may be utilized to communicate
 information from the destination (e.g., CPE B) back to the source (e.g.,
 CPE A). Using rate-based flow control, the ATM network 1 may instruct the
 source to slow down its transmission when the network starts to experience
 congestion.
 In exemplary embodiments, the CPE A sends a forward resource management
 (FRM) cell at regular intervals (e.g., after a certain number of cells
 such as 64 or more cells). The FRM cell may be variously configured to
 contain a current cell rate (CCR) at which the source is transmitting. It
 may also include a field for an explicit cell rate (ER) which is the
 maximum rate that a switch on the virtual circuit (e.g., either ATM A, ATM
 B, and/or ATM C) will allow the source to transmit. An explicit forward
 congestion indication (EFCI) bit may be set in a FRM cell traveling in the
 forward direction (e.g., CPE A to CPE B) to indicate that the network is
 experiencing congestion and to initiate flow control. When the FRM cell
 reaches the destination (e.g., CPE B), it may be turned around by the
 destination and sent back as a backward resource management (BRM) cell.
 Where the explicit forward congestion indication bit is set, the
 destination may include set a congestion indication bit (CI bit) in the
 BRM cell to inform the source that congestion is present in the ATM
 network 1. The setting of the congestion indication bit (CI bit) is used
 in relative rate marking flow rate based flow control algorithms to tell
 the source to slow down and decrease the allowed cell rate (ACR) using a
 predefined algorithm.
 One key to a successful implementation of ABR service is an ability of the
 ATM network 1 to quickly and fairly adjust the allowed cell rate (ACR) for
 each ABR circuit when the level of congestion within the network changes.
 Accordingly, improved algorithms are desirable for varying the allowed
 cell rate (ACR) in ATM networks for each ABR circuit.
 Improved ACR Determination Algorithm
 In exemplary embodiments of the present invention, each switch may be
 configured to calculate an allowed cell rate (ACR) for each connection
 between adjacent ATM switches along the virtual circuit. Conventional
 algorithms tend to have large oscillations due to propagation delays. For
 example, where there is a lot of traffic, one of the switches in the ATM
 network may need to tell the source (e.g., CPE A) to slow down. However,
 because of delays in communicating this information to the source, the
 source cannot respond immediately and hence there is a certain amount of
 overshoot and/or undershoot in determining the new allowed cell rate.
 Further, some connections are bottlenecked (e.g., have cells backed up in
 a queue) upstream and hence do not receive a particular BRM cell having
 new flow control commands for an indeterminate period of time. Under these
 conditions, the over/under shoot problem in the flow control is
 exasperated. Thus, there is a need for improved algorithms which respond
 quickly, treat each virtual connection fairly, and reduce oscillations.
 In one exemplary embodiment, the ATM switches ATM A, ATM B, and/or ATM C
 along the path of the virtual circuit (VC) may be configured to include an
 output queue which includes a separate priority queue for handling data
 associated with the ABR service class. Further, in this embodiment, each
 source (e.g., CPE A) in the ATM network 1 may be configured to operate in
 the explicit cell rate (ER) mode and/or in a binary mode and employ other
 standard ATM traffic management protocols.
 In exemplary embodiments, the allowed cell rate (ACR) may be determined
 using the principles of a proportional derivative algorithm described in
 the text "Linear System Theory and Design" by C. T. Chen, published by
 Saunders College Publishing, Harcourt BraceCollege Publishers, 1984. The
 proportional derivative (PD) algorithm may be variously adapted. In one
 embodiment, the PD algorithm examines the total number of cells disposed
 in the output buffer queue for all virtual circuits operating in ABR mode
 for a single ATM switch.
 As shown in FIG. 2, the output queue 20 may comprise a plurality of storage
 locations for storing individual cell storage locations 21. One or more of
 the individual cell storage locations 21 may include cells of data 23
 waiting to be output from the output queue 20. As the total number of
 cells increases, it may approach a threshold 24. The distance from the
 last full cell storage location 21 to the threshold 24 is one measure of
 the need to make adjustments in the allowed cell rate (ACR). Other
 measures of the need to make adjustments in the allowed cell rate (ACR)
 may include the total number of cells in the queue for all virtual
 circuits, the growth rate of the total number of cells in the queue,
 and/or the rate of change of the distance of the last cell in the queue 25
 to the threshold 24.
 In other embodiments of the present invention, the allowed cell rate (ACR)
 may be modified based on the total number of cells in the queue, the rate
 of change of the total number of cells in the queue, the distance of the
 last cell in the queue from the threshold, and/or the rate of change of
 the distance of the last cell in the queue to the threshold. For example,
 a desired total number of cells and/or distance from the queue threshold
 may be determined. The ACR may thereafter be adjusted based on a
 combination of factors including a desired rate of change of cells in the
 queue given the current total number of cells in the queue, a desired rate
 change of the distance from the threshold based on the current distance of
 the last cell in the queue from the threshold, and/or the rate of change
 of the distance of the last cell in the queue to the threshold.
 The reference point utilized may be what the source indicated was the
 current cell rate (CCR) in a previous FRM message and/or what the previous
 allowed cell rate (ACR) was determined to be set. In order to minimize
 oscillations, it may be desirable to utilize as a reference point to make
 adjustments what the source has declared to be the current cell rate
 (CCR). However, where there is a possibility that the source is
 unreliable, it may be desirable to use a measured current cell rate to
 established a reference point. The use of a measured current cell rate is
 highly desirable where the source is unreliable. In this manner, the ATM
 network 1 retains control over all rate-based flow control parameters.
 Once the current cell rate (CCR) for each virtual circuit (CCR.sub.i (n))
 is known, it may be desirable to calculate a mean cell rate which may be a
 weighted average of all cell rates for all virtual circuits utilized
 within one of the ATM switches. In one exemplary embodiment, the mean cell
 rate (MeanRate) may be calculated to be the exponential average of the
 current cell rates divided by the weights for all of the connections. This
 may be calculated as, for example, indicated in equation 3 in the example
 below.
 A description of one exemplary algorithm which embodies aspects of the
 present invention is described below:
 1. Each ATM switch monitors/samples the queue length of its ABR queue Q(n)
 every T second and then updates variable PastGrowthRate by the following
 rule:
 if (PastGrowthRate==0)
EQU PastGrowthRate=Q(n)-Q(n-1);
 else
EQU PastGrowthRate=(Q(n)-Q(n-1))+F.sub.d *PastGrowthRate; (1)
 where F.sub.d is a constant less than but close to unity.
 2. Within each control interval, if the switch receives an FRM cell, which
 carries the current cell rate (CCR) of a VC, it may update the variable
 MeanRate by the following rule (alternatively, as discussed above, the ATM
 switch may determine current cell rate (CCR) from counting the cell
 arrivals rather than trusting the CCR announced by the source in the FRM
 cell):
EQU if (CCR.sub.i (n)/w.sub.i &gt;MeanRate*F.sub.n) (2)
EQU if (MeanRate==0)
EQU MeanRate=CCR.sub.i (n);
 else
EQU MeanRate=(1-AVF)*MeanRate+AVF*CCR.sub.i (n)/w.sub.i ; (3)
 else
 MeanRate is unchanged.
 Where AVF is an averaging factor having a typical value of 1/16 (e.g., an
 exponential smoothing factor), w.sub.i is the weight of Vci, F.sub.n is a
 small constant whose typical value is about 0.1, however, in a particular
 system, this value may be tuned to an optimum value. CCR is a value
 declared by the source and/or a measured value as discussed above. Where
 the value of AVF is about 0.06, the old mean rate is weighted much heavier
 than the new mean weight.
 3. The AIM switch may be configured to next compute a variable RateChange
 in accordance with the following:
EQU RateChange=-k.sub.1 *[Q(n)-Q.sub.T ]-k.sub.2 * PastGrowthRate (4)
 where k.sub.1 and k.sub.2 are control constants and Q.sub.T is the desired
 queue level at steady-state. The control constants may be used to
 emphasize and/or deemphasize the distance from the threshold versus
 smoothed past growth rate. It will be apparent to those skilled in the art
 that [Q(n)-Q.sub.T ] is the distance from the threshold and that Q(n) is
 the total queue length of all virtual circuits and Q.sub.T is the queue
 threshold. Thus, when the queue is above the threshold, it is desirable to
 have a negative rate change. When the queue is below the threshold, it is
 desirable to have a positive rate change. When the past growth rate is
 positive, it may be desirable to slow down and when the past growth rate
 is negative, it may be desirable to speed up.
 4. The ATM switch may be configured to next estimate the fair rate for Vci
 in the following way:
EQU FairMultiplier=MeanRate*[1+f.sub.m (RateChange)] (5)
EQU FairRate.sub.i =FairMultiplier*w.sub.i (6)
 where f.sub.m (x) is a nonlinear mapping function of the shape shown in
 FIG. 3 (e.g. y=A*tanh(B*x)). The non-linear mapping function may be
 implemented in a ROM lookup table. The particular shape off f.sub.m (x)
 may be chosen to discourage large rate changes. Thus, the fair rate for
 virtual circuit i is equal to the FairMultiplier times the weight of the
 virtual connection i.
 5. The ATM switch may be configured next to locate a backwards resource
 management (BRM) cell for a particular virtual circuit and set the
 explicit rate (ER) as the following:
EQU ACR.sub.i (n+1)=max (MCR.sub.i, min (CCR.sub.i (n)+.mu.*[FairRate.sub.i
 -CCR.sub.i (n)], PCR.sub.i)) (7)
 where .mu. is a small constant used as a damping factor (e.g., 0.5), and
 MCR.sub.i & PCR.sub.i are the minimum and peak cell rate of Vci,
 respectively, [FairRate.sub.i -CCR.sub.i (n)] define the distance between
 a fair rate and the current rate.
 Once a mean cell rate is known, it may be desirable to calculate the amount
 by which the weighted cell rate (e.g., CCR.sub.i (n)/w.sub.i) for each ABR
 virtual circuit varies from the mean cell rate.
 As reflected in equation (4), the target rate change may be a function of
 a) the queue length in relation to a target threshold Q.sub.T, and b) the
 detected growth rate of the queue. Part a) is significant because it
 ensures that, in a steady state, the buffer occupancy is around a non-zero
 threshold, thus keeping the output port of the ATM switch busy. An
 algorithm that does not attempt to adjust the steady-state buffer content
 to a non-zero threshold may suffer from loss of throughput.
 Similar to an earlier patent application (Dynamic ATM Network Access
 Control Using an Availability Parameter At Each Port In A Network Path,
 Albert K. Wong, U.S. patent application Ser. No. 08/299,472, filed Aug.
 31, 1994), hereby incorporated by reference, the algorithm may be
 configured to estimate a rate multiplier parameter for each port (e.g.,
 the FairMultiplier in equation (5)), which is generally similar to the
 Availability Parameter A in the earlier patent application). One
 distinction is that the FairMultiplier is estimated based on the intended
 rate change (RateChange) derived, for example, in equation (4), and an
 estimate of the average value of the rate multipliers that the active VCs
 are actually using at the time (e.g., based on equation (3)), which
 represents an exponential averaging method). In contrast, in the earlier
 patent application the new multiplier value is generated based on the old
 multiplier value and the desired direction of change. The new approach
 provides a clear advantage in the stability of the algorithm.
 Specifically, in the earlier approach, when the trunk increases its rate
 multiplier value in an attempt to increase its bandwidth utilization, it
 may happen that the VCs do not necessarily respond with a higher input
 rate as they may not need the higher rate or may be bottle-necked by other
 trunks. As a result, the trunk may increase the rate multiplier still some
 more in an attempt to increase its bandwidth utilization. In this new
 approach, the rate multiplier does not feed on itself, hence oscillations
 are reduced, instabilities are prevented, and efficiencies are increased.
 Further, where a damping function and/or non-linear mapping function
 .function.(m) is applied to the intended rate change (e.g., equation (5))
 to prevent large changes in the rate multiplier, the overall system
 efficiency is improved.
 In equation (2), VCs with an actual current cell rate that may be too small
 will not enter into the estimate of the mean rate. This may be
 advantageous since it may prevent VCs that are bottlenecked at other
 trunks from lowering the estimate the actual operative rate multiplier. In
 other words, it may be desirable to estimate and change the rate
 multiplier being used by VCs that would respond to the changes of this
 multiplier, not those that are bottlenecked somewhere else and would thus
 cannot not respond to a change in the rate multiplier.
 As described in equation (1), the growth rate of the queue may be estimated
 based on the current growth rate and the past growth rate. This smoothing
 of the estimate prevents the algorithm from being overly oscillatory.
 Further, the target rate of a VC (FairRate).sub.i may be the rate
 multiplier times the individual weight of the VC (equation (6)). The
 Allowed Cell Rate (ACR) for the VC may be adjusted towards the target rate
 according to equation (7). This ACR value may then be sent back to the
 source of VC via the Explicit Rate (ER) field of the BRM cell. As
 described in U.S. patent application Ser. No. 08/299,472 incorporated by
 reference above, each trunk may compare the value of the ER field in a BRM
 cell it receives with the ACR value that it generates via its internal
 algorithm. This may help ensure that the minimum of the two values is
 stored in the ER field of the BRM cell before the BRM cell is sent further
 upstream. In other words, the VC source will receive in a BRM cell the
 smallest of the ACR values determined by each trunk along the path
 traversed by the VC.
 In one exemplary embodiment, an average rate for all virtual circuits is
 determined as described above. Factors described above associated with the
 queue are examined to determine if a change is required. If a change is
 required, the amount of change is input into a smoothing function as, for
 example, shown in FIG. 3. If there is a small amount of total rate change,
 then the rate change actually implemented is proportional to the desired
 amount of rate change. However, where there is a large amount of rate
 change indicated, then the amount of rate change only changes by a fixed
 amount regardless of the magnitude of the indicated rated change. The
 fixed amount may be at the point where fm(x) becomes parallel to the X
 axis in FIG. 2.
 While exemplary systems and methods embodying the present invention are
 shown by way of example, it will be understood, of course, that the
 invention is not limited to these embodiments. Modifications may be made
 by those skilled in the art, particularly in light of the foregoing
 teachings. For example, it will be well known in the art that a processor
 in each of the ATM switches in FIG. 1 implements the algorithms discussed
 herein. Further, each of the steps of the aforementioned embodiments may
 be utilized alone or in combination with steps of the other embodiments.