Title of Invention: Method and apparatus for explicit rate flow control in ATM networks
Abstract: An efficient, cost effective method and apparatus for performing resource allocation of available bit rate (ABR) virtual circuit (VC) in an asynchronous transfer mode (ATM) network includes an explicit rate switch process performed at at least one switch of an ABR VC. The process provides a fast and more accurate computation of the number of active VCs in an ATM network. Furthermore, the fair share allocation is calculated at the switch in a way that is efficient and lends itself easily to implementation in hardware. For example, in one embodiment, the fair share is implemented using a series of counters and registers controlled by a state machine. This simple hardware implementation enables fast convergence to a current final state so that timely accurate resource utilization and allocation to the ABR VCs can be determined.
Detailed Description: Part PAC: DETAILED DESCRIPTION
Part PAR: A simplified block diagram of an exemplary asynchronous transfer mode (ATM) network is shown in FIG. 1. The network is composed of a plurality of switches, e.g., 10, 15, 20, 25, 30, 35 interconnected by a plurality of links. For example, link 40 is located between switch 10 and switch 15. Each switch 10, 15, 20, 25, 30, 35 maintains information regarding each virtual circuit routed through the switch in order to switch a cell between an input and an output link of the switch. By selecting the proper links, a particular path can be obtained between a source device 50 and destination device 55. The links and switches through which data is routed and the associated resources used are referred to as a virtual circuit (VC). For example, the VC as shown in FIG. 1 between device 50 and 55 would be composed of links 40, 42, 44 and 46 and switches 10, 15 and 20. Exemplary switches include those manufactured by Fore Systems in Warrendale, Pa., Newbridge in Herndon, Va. and American Telephone and Telegraph (AT&T) in Murray Hill, N.J. It is readily apparent that this network is exemplary and the process and structures described herein are not limited to this particular network embodiment.
Part PAR_2: Each link typically can support a plurality of VCs. However, the links have a physical bandwidth which can limit the bandwidth at which a virtual circuit operates. For those devices that do not schedule resources in advance, the virtual circuit is constrained by the bandwidth available at the time it requests use of resources, e.g., switches and links.
Part PAR_3: In accordance with ATM network protocols (see, for example, ATM Forum, Traffic Management Specification, version 4.0 (atmf 95-0013 R10), February, 1996) the source device of a virtual circuit sends a forward resource management (FRM) cell periodically through the links and switches composing the virtual circuit. This FRM cell typically is sent once every predetermined number of data cells that are transmitted by the source, or when the source is idle, at least once every predetermined time period. The FRM cell traverses through the links and is processed by switches of the virtual circuit until it reaches the destination device 50, which sends the message back as a backward RM (BRM) cell. In the system of the present invention, at the switches a value of fair share of the available bandwidth is determined. This fair share value is used to determine the explicit rate (ER) that the virtual circuit can use at that time to transmit cells. The ER is a field in the RM cells (220, FIG. 2). Once the source device 55 receives the BRM cell containing the ER field updated by the switches, the allowed communication rate is updated to the ER rate to conform the allowed transmission rate to the ER rate provided. The source device can then update the current communication rate (CCR) to be a value up to the allowed transmission rate.
Part PAR_4: A portion of the contents of an exemplary RM cell is shown in FIG. 2. As is readily apparent to one skilled in the art, the RM cell utilized is not limited to the embodiment disclosed herein and can include more information than that shown. Referring to FIG. 2, the RM cell 200 includes an explicit rate (ER) field 220. Initially, the explicit rate (ER) field indicates the bandwidth which the ABR virtual circuit desires. This value is updated by the switches of the virtual circuit in accordance with the fair share of a valuable bandwidth computed. The CCR field 225 indicates the current transmission rate used.
Part PAR_5: As will be described below, each switch through which the VC is routed computes the fair share of the available bandwidth for every active ABR VC and uses this value to determine the value of the ER field of the BRM cell. Upon receiving a BRM cell, if the value in the ER field contained within the message is greater than the fair share computed, the value in the ER field is replaced with a value that is a function of the newly computed fair share value and the value of the CCR field.
Part PAR_6: The computation of the fair share and the variables required to compute the fair share must be performed in a timely and efficient manner such that the rate of convergence to a current final value is rapid. Thus, accurate allocation of resources can be provided based on the current state of the network.
Part PAR_7: One significant variable which requires timely computation is the number of active virtual circuits (#Active.sub.-- VC). An accurate estimate of the number of active virtual circuits is needed to best utilize resources. For example, if the number of active virtual circuits is overestimated, the resources will be underutilized. Correspondingly, if the number of active virtual circuits is underestimated, congestion can occur.
Part PAR_8: The system and method of the present invention uses a technique for estimating the number of active virtual circuits which is more accurate than prior art techniques. More particularly, in the system and method of the present invention, an active VC is one upon which cell activity has been viewed within a predetermined timeframe. Thus, by providing a more accurate estimate of the number of active VCs and using this number in the computation of fair share, better usage of resources are utilized. To determine the number of active VCs, the system and method of the present invention utilizes a mechanism which identifies a VC to be in one of three states. The state information is stored in a VC table located in each switch through which a VC is routed.
Part PAR_9: FIG. 3a is a simplified state diagram illustrating the three states. A VC initially is considered to be in an inactive state 302. When a cell arrives at the switch, the switch updates the VC state to be active 304. Similarly, if the VC state is indicated as the test state 306 and a cell arrives, the state will be updated to active 304. Concurrently with the monitoring of cell activity, a timer is used to set a predetermined time interval. At the lapse of each time interval, those VCs identified as active are changed to the test state 306, and those VCs identified in the test state 306 are set to the inactive state 302. When a VC state is changed from the test state 306 to the inactive state 302, the ongoing count of the number of active VCs is decremented by one. Similarly, when a VC state is changed from inactive 302, to active 304 (when a cell arrives), the ongoing count of the number of active VCs is incremented by one. Thus, a simple but effective technique for determining the number of active VCs is used.
Part PAR_10: FIG. 3a illustrates the flow for one process for determining the number of active VCs. This process further identifies whether a particular VC is in an overload state. A VC is identified to be in an overload state if the current rate of the VC (as indicated by the CCR field) is greater than the fair share computed. This situation arises when the available network resources change (e.g., due to establishment of additional ABR VCs) prior to updating the rate at the source. As will be explained subsequently, the overload state and the count of the number of VCs operating in an overload state is used to determine the fair share and the rate at which the VC is permitted to operate.
Part PAR_11: Referring to FIG. 3b, at step 310, at the end of the active timer interval 310, the state of each VC routed through the switch is examined, steps 312, 314, 315. If the VC state for a particular VC is active, then the VC state is set to test 320. If the state is inactive, the state remains in the inactive state and loops back to step 312. If, at step 315, the VC state is test, then at step 325 the VC state is set to inactive and the number of active VCs (#Active.sub.-- VC) is decremented by one. At step 330, it is then determined whether the overload state for a VC, also maintained in the VC table at the switch through which a particular VC is routed, has been set to true. If the overload state has been set to true, it is then reset to false, step 335, and a count maintained of the number of virtual circuits operating in overload (#Ovld.sub.-- VC) is decremented by one.
Part PAR_12: FIG. 4 is a flow chart that illustrates a more detailed embodiment of the ongoing update of parameters utilized to compute the fair share. At step 410, when a cell arrives, the cell type is determined, step 415. As explained previously, the cell can be a resource management (RM) cell or a cell containing data. If the cell type is a BRM cell then the explicit rate (ER) is set to a value which is a function of the fair share (FS) and the current communications rate (CCR), step 420. It is contemplated that a variety of functions can be used. For example, the ER is set to: EQU ER=FS-d*(FS-CCR)
Part PAL: where d is a configurable positive constant between 0 and 1.
Part PAR_13: Continuing with the process set forth in FIG. 4, if the cell type is other than a BRM cell, the VC state is examined, step 425. If the VC state is inactive, then at step 430 the VC state is set to active and the number of active VCs is incremented by one. At step 435, the type of cell is then examined. If the cell is an FRM cell, and the CCR is greater than the FS, then the overload state for the VC is set to true and the number of overloaded VCs is incremented by one, step 450. If at step 440, the CCR is not greater than the FS, then the overload state of the VC is set to false, step 445. If at step 435, the type of cell is a data cell, then step 450 is again performed.
Part PAR_14: Going back to step 425, if the VC state is active or test, the VC state is set to active. If at step 460, the type of cell is an FRM, the overload state is examined, step 465. If the overload state is false and the CCR is greater than the FS, step 470, step 450 is performed. If, however, the overload state is true and the CCR is less than the fair share, step 475, then the overload state is set to false, step 480, and the number of overloaded VCs is decremented by one, step 480.
Part PAR_15: Using this information, the fair share can then rapidly be determined on an ongoing basis. An exemplary flow diagram is shown in FIG. 5. At steps 505 and 510, if the number of active VCs change, or if the available bandwidth for ABR traffic changes, then the reference fair share is updated.
Part PAR_16: The available bandwidth for ABR traffic can be measured in a variety of ways. For example, in a static discipline the available bandwidth is equal to a fraction or percent of the non-reserved bandwidth at the output link. In a dynamic discipline, the bandwidth is equal to the fraction or percent of the maximum of the non-reserved bandwidth at the output length, and the unused bandwidth during a time interval, such as the time interval during which the average load of ABR traffic is measured.
Part PAR_17: The number of active VCs is preferably measured in accordance with the teachings provided herein, although it is contemplated that other methods for determining the number of active VCs can be used with this process for determining fair share.
Part PAR_18: Referring back to FIG. 5, if the available bandwidth for ABR traffic or the number of active VCs change, then a reference fair share value (Ref.sub.-- FS) is updated to a value which corresponds to the available bandwidth for ABR traffic divided by the number of active virtual circuits (steps 505, 510, 515). This provides a way to immediately respond to change in the dynamics of the environment so that a more accurate calculation of fair share and thus, utilization of resources can be obtained.
Part PAR_19: In addition, it is preferred that the fair share be updated as needed on a periodic basis. Referring to step 520, the fair share will be updated every T.sub.-- load time interval. T.sub.-- load is a time interval during which the average load of ABR traffic is measured. The size of the interval affects the accuracy of the measurement and the response to changes in the load. Small intervals are desirable to achieve fast response, i.e., increase or decrease of the fair share in underload or overload conditions, respectively. Large intervals are desired for better estimation of load; especially for bursty traffic where small intervals may cause oscillations in the feedback sent to the source. Thus, the T.sub.-- load interval can be set according to the performance desired. Preferably, T.sub.-- load is set to a value within the range of 5 to 20 milliseconds.
Part PAR_20: Thus, once a time interval corresponding to T.sub.-- load has elapsed, step 520, and the number of overloaded VCs is not equal to zero, step 522, at step 525, the fair share is updated according to: EQU FS=FS+(Av.sub.-- Bw-Ac.sub.-- Bw)/#Ovld.sub.-- VC,
Part PAL_2: where FS represents the fair share, Av.sub.-- Bw represents the available bandwidth for ABR traffic, Ac.sub.-- Bw represents the arrival rate of ABR traffic at the switch, and #Ovld.sub.-- VC represents the number of overloaded VCs, that is, the number of active VCs whose most recently examined current communication rate is greater or equal to the fair share.
Part PAR_21: Preferably, the arrival rate of ABR traffic is measured in cells per second and is obtained by counting the number of ABR cells that arrived at the switch during a predetermined period, such as T.sub.-- load, and dividing this number by the quantity of the time period, e.g., T.sub.-- load. It is readily apparent that other techniques can be used to compute the arrival rate of ABR traffic. Similarly, the number of overloaded VCs is preferably computed in accordance with the teachings herein. However, it is readily apparent that other techniques can be used to determine the number of overloaded virtual circuits.
Part PAR_22: Referring back to FIG. 5 at step 530, if the fair share is less than the reference fair share, then the fair share is updated to equal the reference fair share. The reference fair share is identified as the equal allocation of bandwidth among all active VCs and is used as a minimum value to which the fair share, step 535, can be set during congestion situation. Preferably, the reference fair share is defined as Av.sub.-- Bw/#Active.sub.-- VC. If the fair share is greater than the available bandwidth for ABR traffic, then the fair share is updated to a maximum cap of the available bandwidth, steps 540 and 545. At step 550, if the state of the link is congested, then the fair share also is updated to the minimum fair share value which is in this embodiment the reference fair share value.
Part PAR_23: A variety of methods can be used to identify whether a congestion situation has occurred. In the present embodiment, a congestion flag is set when the queue in the switch holding the ABR traffic exceeds a congested high threshold. The flag is reset when the ABR queue falls below a congested low threshold. Although a single threshold value can be used, the frequency of oscillations and the feedback due to queue length changes around the congestion threshold is minimized by using a high threshold and low threshold. For example, a value of 50 to 100 can be used for the congested high threshold and a value of 5 to 10 can be used for a congested low threshold.
Part PAR_24: Thus, as described herein, an efficient process for computing the fair share is described. This process lends itself to an efficient hardware implementation, as many of the elements are simple hardware elements, such as registers, counters and the like, controlled by a controller such as finite state machine, microcontroller, microprocessor, or other forms of control logic.
Part PAR_25: FIG. 6 is an illustrative block diagram of one hardware implementation of a portion of a switch that operates in accordance with the teachings of the present invention. The elements shown are utilized to perform the processes described earlier, including determining the number of active VCs, and determining the fair share and the parameters utilized. It is readily apparent that the present invention is not limited to this specific hardware implementation. Furthermore, it is readily apparent that the switch also includes other hardware and software to handle other aspects of switch operation known to those skilled in the art and not described further herein.
Part PAR_26: Referring to FIG. 6, a VC table 605 maintains a variety of information regarding the VCs routed through the switch. In the embodiment described herein the VC table further includes VC state information. Thus, the VC table 605 includes a plurality of VC entries, each entry including fields identifying parameters with respect to the VC. With regard to the present invention, the VC table further identifies the virtual circuit state 607, and whether the virtual circuit is operating in an overload condition wherein the current communication rate (CCR) is greater than or equal to the fair share computed. Also included are a plurality of constants 620, which are considered parameters utilized in the computation of fair share that generally do not change, or change infrequently under control of a function of the switch that is responsible for changing the values or states during switch operation. These include the amount of non-reserved bandwidth 622, the available bandwidth for ABR traffic 624, the congested high threshold 626, and congested low threshold 628 and the congested flag 630, T.sub.-- load 632, and T.sub.-- active 634 (the time period between updates of VC states). Also used are registers or memory locations to store the fair share 636, reference fair share 638, actual bandwidth of ABR traffic 640, and the amount of unused bandwidth available 642. Simple arithmetic and comparator circuitry 680 also is preferably included to compute some of the values described previously.
Part PAR_27: Counters preferably are included, such as load timer 650 which counts a time period corresponding to T.sub.-- load, active timer 655 which counts a time period corresponding to T.sub.-- active, the number of active VC counter which, under control of a finite state machine, 670 increments or decrements the count of the number of active VCs 657 and the number of overloaded VC counter 659 which, under control of the finite state machine 670, maintains a count of the overloaded VCs. In addition, the Ac.sub.-- Bw counter 661 maintains a count, under control of the finite state machine, of the arrival rate of ABR traffic at the switch. As this value maintains a count of ABR cells that arrive during a period, for example T.sub.-- load, when the load timer times out, the value currently located in the counter 661 is moved to a register 640, so that the current value can be maintained for calculations and the value in the counter can be reset to count the number of cells during the next time period.
Part PAR_28: As is readily apparent from the diagrams, the finite state machine in the present embodiment interacts in a manner understood by those skilled in the art, with the constants, the counters and the registers to perform the computations relative to the number of active VCs and the fair share. As is readily apparent, the hardware is straight forward, easy to implement and fast to provide a timely, accurate determination of the fair share, and therefore, an efficient allocation of bandwidth for the different resources.
Part PAR_29: The invention has been described in conjunction with the preferred embodiment. It is evident that numerous alternatives, modifications, variations and uses will be apparent to those skilled in the art in light of the foregoing description.


{'bibliographic_information': "{'Patent Number': '059663812', 'Series Code': '8', 'Application Number': '6190405', 'Application Type': '1', 'Art unit': '278', 'Application Filing Date': '19960320', 'Title of Invention': 'Method and apparatus for explicit rate flow control in ATM networks', 'Issue Date': '19991012', 'Number of Claims': '25', 'Exemplary Claim Number(s)': '1', 'Primary Examiner': 'Patel; Ajit', 'Number of Drawing Sheets': '5', 'Number of figures': '7'}", 'source_file': './grant/1999/pftaps19991012_wk41.txt', 'source_data': 'USPTO-Grant'}