United States Patent Patent Number: 5805577 Series Code: 8 Application No.: 683,871 Patent Type: 1 Art Record No.: 263 Date Filed: 19960719 Title: ERICA: EXPLICIT RATE INDICATION FOR CONGESTION AVOIDANCE IN ATM NETWORKS Issue Date: 19980908 No. of Claims: 36 Exemplary Claim: 1 Asst. Examiner: Yao; Kwang Bin Pri. Examiner: Hsu; Alpus H. No. of Drawings: 47 No. of Figures: 86 [INVENTOR] Name: Jain; Raj Street: 4591 Lanercost Way City: Upper Arlington State: OH Zip Code: 43220 [INVENTOR] Name: Goyal; Rohit Street: 1170 Chambers Rd. Apt. 4C City: Columbus State: OH Zip Code: 43212 [INVENTOR] Name: Kalyanaraman; Shiv Street: Dept. of CIS, Ohio State University City: Columbus State: OH Zip Code: 43210 [INVENTOR] Name: Viswanathan; Ram Street: 14557 36th St., NE. Apt. J11 City: Bellevue State: WA Zip Code: 98007 [INVENTOR] Name: Fahmy; Sonia Street: 101 Curl Dr. Apt. 772 City: Columbus State: OH Zip Code: 43210 [CLASSIFICATION] US Class: 370/234 Cross Ref Class: 370/253 Cross Ref Class: 370/465 Intl. Class Ed. Field: 6 Intl. Class: H04Q 1104 Field of Search: 370 Subclasses: 229;230;231;232;233;234;235;236;237;238;252;253;395;397;399;468;477;465 Field of Search: 395 Subclasses: 200.01;200.02;200.03;200.11;200.13 [US REFERENCE] Patent: 5280470 Issue Date: 19940100 Name: Buhrke et al. US Class: 370/232 [US REFERENCE] Patent: 5367523 Issue Date: 19941100 Name: Chang et al. US Class: 370/235 [US REFERENCE] Patent: 5457687 Issue Date: 19951000 Name: Newman US Class: 370/232 [US REFERENCE] Patent: 5515359 Issue Date: 19960500 Name: Zheng US Class: 370/231 [US REFERENCE] Patent: 5633859 Issue Date: 19970500 Name: Jain et al. US Class: 370/234 [US REFERENCE] Patent: 5646943 Issue Date: 19970700 Name: Elwalid US Class: 370/230 [LEGAL INFORMATION] Legal Firm: Fay, Sharpe, Beall, Fagan, Minnich & McKee [ABSTRACT] A congestion avoidance scheme for data traffic in ATM networks. The scheme achieves both efficiency and fairness, and exhibits a fast transient response. A congestion avoidance scheme for ATM networks is described which has its optimal operating point at 100% utilization and a fixed, non-zero queue delay. The scheme improves control of end-to-end delay and keeps link utilization of expensive links high despite idle periods in the input load. [BACKGROUND AND SUMMARY] This application claims the benefit of U.S. Provisional patent application Ser. No. 60/001,259 (filed Jul. 20, 1995) and U.S. Provisional patent application Ser. No. 60/001,286 (filed Jul. 20, 1995). BACKGROUND OF THE INVENTION This invention relates a method and apparatus for congestion management in computer and/or telecommunications networks using explicit rate indication for congestion avoidance in ATM networks--hereinafter referred to as "ERICA" or, in at least one alternative embodiment "ERICA+". More particularly, the invention is directed to a method (and apparatus) wherein switches provide feedback to data sources for controlling the rate at which the data sources send data to the switches. While the invention is particularly directed to the art of data congestion management, and will thus be described with specific reference thereto, it will be appreciated that the invention may have usefulness in other fields and applications. Asynchronous Transfer Mode (ATM) is a technology of choice for Broadband Integrated Services Digital Networks (B-ISDN). ATM is proposed to transport a wide variety of services, such as voice, video and data, in a seamless manner. In this mode, user information is transferred in a connection oriented fashion between communicating entities using fixed-size packets, known as ATM cells. ATM cells are fifty-three bytes long, consisting of a five byte header and a forty-eight byte information field, sometimes referred to as payload. The ATM cells flow along predetermined paths called Virtual Channels (VCs). End systems must set up Constant Bit Rate (CBR), Variable Bit Rate (VBR), Available Bit Rate (ABR) or Unspecified Bit Rate (UBR) virtual channels (VCs) prior to transmitting information. Bandwidth is dynamically divided among the active VCs. Data traffic, which is highly "bursty" and does not have strict delay requirements, is usually transported by the ABR service. Supporting the ABR traffic class requires congestion management at intermediate switches in the network. Congestion occurs whenever a total input rate exceeds the available link capacity (as illustrated below). .SIGMA. Input Rate>Available Link Capacity. Congestion is a dynamic problem arising due to dynamic changes in the network load. Congestion control schemes need to provide feedback to the traffic sources asking them to readjust their loads. The ATM forum has adopted the rate-based paradigm as its standard for congestion control. In a rate-based scheme, source end systems send data at specific rates, and switches react to overload or underload conditions by asking sources to decrease or increase their rates respectively. The feedback in rate-based schemes can consist of a single bit indicating congestion, or an explicit rate (ER) at which the source must send data. The explicit rate (calculated by the switches) is indicated in special cells called Resource Management (RM) cells which are periodically sent by the source. Objectives of Rate-Based Congestion Control Congestion control is a difficult problem. A rate-based congestion control scheme attempts to achieve the objectives discussed below. Efficiency and Minimal Delay There is a tradeoff between the link utilization and an end-to-end delay. For low utilization, the queues at the switches are small and the delay is small. Once utilization is very high, queues grow, and cells are dropped when the queue size exceeds the available buffer size. The delay varies according to the load, but there is always a non-zero queueing delay. FIGS. 1A and 1B show throughput and delay for various loads in a network. The operating point which has a utilization close to 100% and moderate delays is called a knee of the delay-throughput curve. This is a good choice for an optimal operating point, and congestion control schemes which operate at this point are called congestion avoidance schemes. FIGS. 1C and 1D show link utilization and queue length as a function of time at the optimal operating point. Fairness Fairness and efficiency are measured by a criterion called a max-min allocation. Mathematically, this criterion is defined as follows. Given a configuration with n contending sources, suppose the ith source is allocated a bandwidth x.sub.i. An allocation vector {x.sub.1, x.sub.2, . . . , x.sub.n } will be feasible if all link load levels are less than or equal to 100%. The total number of possible vectors will then be infinite. Given any allocation vector, the source getting the least allocation may be called an "unhappiest source." It is necessary to find the feasible vector that gives the maximum allocation to the "unhappiest source." The number of such vectors is also infinite. Once the "unhappiest source" receives its maximum allocation, the problem remains only to the remaining n-1 sources operating on the network with reduced link capacities. Again, the "unhappiest source" among these n-1 sources is identified. The "unhappiest source" among these n-1 sources is given the maximum allocation. This process is repeated until all sources have been allocated the maximum allocation possible. Good Steady State as Well as Transient Response Characteristics Persistent sources always have cells to send. Steady state characteristics can be tested using these sources. These sources can consistently overload or underload the system and maintain a steady state. Schemes attempt to exhibit little oscillations during steady state conditions. Most real world traffic is bursty because most sources are transient. A transient response can be tested using transient sources which start after other sources have started and/or stop before the other sources have stopped. Good schemes must be able to respond rapidly to these load transients and achieve optimal performance. Scalability to ATM Networks that Cover a Wide Range of Speeds, Distances, Number of Switches and Number of VCs The same scheme should perform well for Local Area Networks (LANS) as well as Wide Area Networks (WANs). LANs and WANs differ in their round-trip delay times. LANs have a round-trip delay of a few microseconds while WANs may have round-trip delays of a few milliseconds. The time taken for feedback to reach the source from a switch clearly depends on the distance between them. The scheme must exhibit an optimal behavior under these widely varying conditions without excessive need for parameter adjustment. Adaptation to the presence of multiple traffic classes and variant demands Both VBR and CBR traffic are delay sensitive and have a higher priority than ABR traffic. When VBR and CBR sources are active, the available ABR capacity may be reduced significantly. The ABR Capacity may be illustrated using the following equation: ABR Capacity=Link Capacity-VBR Capacity-CBR Capacity Moreover, ABR capacity is no longer fixed, but varies according to the VBR and CBR load. Congestion control schemes must respond quickly to dynamic changes in ABR capacity. ABR congestion control also needs to perform optimally for high variance in the demand (bursty and greedy traffic, as well as bottlenecked sources). Fair scheduling Switches usually reserve a minimum bandwidth for each of the four classes: CBR, VBR, ABR and UBR. This prevents starvation of any class regardless of traffic of the higher priority classes. In addition, when the higher priority classes are not using their allocations, it is desirable to divide the excess capacity in a fair manner among competing classes. Minimal complexity The time for processing an RM cell and giving feedback does not depend upon the number of VCs. That is, the computational complexity of the algorithm should be order 1 ("O(1)"). Further, the minimum queueing and scheduling requirements of the scheme should be O(1) complexity to allow flexible implementations. In particular, mandatory per-VC queueing and scheduling are undesirable. Robustness The scheme should be insensitive to slight mistuning of parameters, loss of control messages. Load measurement errors should not bring down the network. The scheme should also isolate misbehaving users and protect other users from them. The MIT and OSU Schemes The so-called MIT scheme (A. Charny, D. D. Clark, R. Jain, "Congestion Control with Explicit Rate Indication," Proc. I.C.C., June 1995) and the so-called OSU scheme (U.S. Ser. No. 08/307,375 filed Sep. 16, 1994) were among the earliest explicit rate schemes to be considered by the ATM Forum. The MIT Scheme calculates an advertised rate as follows: Advertised Rate=(Capacity-.SIGMA.Underloading VC's rate)/Number of Bottlenecked VCs A VC is defined as bottlenecked if its rate is smaller than the calculated advertised rate. Because the advertised rate is a function of number of bottlenecked VC's, the advertised rate is recursive. The explicit rate calculated at the switch is the minimum of the VC's rate and the advertised rate. The MIT scheme has the following problems. First, it has an Order N ("O(N)") computation, that is, the amount of computation is proportional to the number of Vcs N. This is expensive to implement. Second, it uses declared rates of the sources alone and does not measure the input load at the switch. Hence, it suffers from inefficiency in cases when the source declares one rate and is bottlenecked at another rate. Since the switch does not measure the load, it assumes that the system is efficient when, in reality, it is not. The OSU scheme overcomes some of the problems of the MIT scheme. It uses an order one ("O(1)") algorithm as opposed to the O(N) algorithm of the MIT scheme. Further, it uses measured rates as opposed to declared rates used in the MIT scheme. The key innovations of the OSU scheme are: 1) the use of input rate rather than the queue length to measure overload, 2) the use of a target utilization parameter to achieve congestion avoidance for rate-based control, 3) the use of a switch averaging interval to measure quantities to be used in the algorithm, and 4) rules for the correct operation of Backward Explicit Congestion Notification (BECN), some of which have become part of the standard or arts of other switch schemes. Achieving Efficiency To achieve efficiency, the OSU scheme simply asks the sources to divide their rates by the current load level, z. The maximum value of z among all the switches reaches the source. The idea behind this step is that, if all sources divide their rates by this factor in the current cycle (round trip), the bottleneck link (the link with the maximum utilization) will reach a load level of 1 in the next cycle. This statement is true if all the round trip times are equal and the sources get feedback at the same time (synchronous operation). Otherwise, the bottleneck moves towards a load level of 1 in every cycle, given that sources can use their allocations to send data. Achieving Fairness Observe that, though the bottleneck reaches a load level of 1, the allocation of the available bandwidth among contending sources may not be fair. This is because, for z=1, the switch does not ask sources to change their rates, even if the distribution of rates is unfair. The first goal is to achieve efficient operation. Once the network is operating close to the target utilization (z=1), steps are taken to achieve fairness. For fairness, the network manager declares a target utilization band (TUB), say, 90.+-.9% or 81% to 99%. When the link utilization is in the TUB, the link is said to be operating efficiently. The TUB is henceforth expressed in the U(1.+-..DELTA.) format, where U is the target utilization and .DELTA. is the half-width of the TUB. For example, 90.+-.9% is expressed as 90(1.+-.0.1)%. We first define a Fair share variable as: ##EQU1## A source is said to be active if any cells from the source are seen at the switch during the current averaging interval. To achieve fairness, we treat the underloading and overloading sources differently. Underloading sources are those that are using bandwidth less than the fair share and overloading sources are those that are using more than the fair share. Specifically, if the current load level is z, the underloading sources are treated as if the current load level is z/(1+.DELTA.) and the overloading sources are treated as if the load level is z/(1-.DELTA.). This algorithm guarantees that the system converges towards fair operation. We also note that all the switch steps are O(1) with respect to the number of VCs. However, the OSU scheme is not completely compatible with the ATM Forum standards, since it was developed while the standards were being formulated. The present scheme, or ERICA scheme, upgrades the OSU scheme, making its standards compatible, and uses the metrics (current load level (z), number of active sources) and concepts (target utilization, fair share, dividing source rates by z) in a more aggressive fashion to achieve the desired scheme goals. ERICA differs from the OSU scheme in several aspects. First, the OSU scheme achieves efficiency and fairness in separate steps. It defines a Target Utilization Band (TUB) which represents efficient operation. When the system is outside the TUB, the OSU scheme simply attempts to bring it into the TUB, i.e., bring the system to efficient operation. After the system is inside the TUB, the OSU scheme improves fairness at each step. ERICA uses a new algorithm to improve efficiency and fairness simultaneously, i.e., at every step. Second, the OSU scheme gives feedback in the forward direction, whereas ERICA gives feedback in the reverse direction. The latter technique allows feedback to be delivered faster to the sources. Third, the OSU scheme requires the source and switch measurement intervals to be co-related. The ERICA scheme does not require the co-relation of source and switch intervals because it gives exactly one feedback in every switch interval irrespective of the source measurement interval. Fourth, the OSU scheme requires the sources to send RM cells at fixed time intervals. ERICA allows RM cells to be sent after a fixed count of data cells as required by the ATM Forum standards. Fifth, ERICA has several other innovations which allow the network to efficiently support bursty input traffic even though the ABR capacity may be highly variable. The switches indicate their feedback in the RM cells which travel back to the source. SUMMARY OF THE INVENTION It is an object of the present invention to provide a method (and apparatus) for congestion management in a computer network. It is a further object of the present invention to provide congestion avoidance in ATM networks using explicit rate indication. It is a still further object of the present invention to provide a method (and apparatus) wherein switches provide feedback to data sources for controlling the rate at which the data sources send data to the switches. Further scope of the applicability of the present invention will become apparent from the detailed description provided below. It should be understood, however, that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope for the invention will become apparent to those skilled in the art. [DRAWING DESCRIPTION] DESCRIPTION OF THE DRAWINGS The present invention exists in the construction, arrangement, and combination of the various parts of the device and method herein, whereby the objects contemplated are attained as hereinafter more fully set forth, specifically pointed out in the claims, and illustrated in the accompanying drawings in which: FIG. 1A is a graphic representation of throughput versus load in a network; FIG. 1B is a graphic representation of delay versus load in a network; FIG. 1C is a graphic representation of link utilization versus time in a network; FIG. 1D is a graphic representation of queue length versus time in a network; FIG. 2 is a graphic representation of an RM cell path; FIG. 3 is a flow chart representing the basic scheme; FIG. 4 is a flow chart representing a variation of the basic scheme--achieving max-min fairness; FIG. 5 is a flow chart representing a variation of the basic scheme--fair share first to avoid transient overloads; FIG. 6 is a graphic representation of Reverse Direction Feedback; FIG. 7 is a flow chart representing a variation of the basic scheme--forward CCR used for reverse direction feedback; FIG. 8 is a graphic representation of single feedback in a switch interval; FIG. 9 is a flow chart representing a variation of the basic scheme--single feedback in an averaging interval; FIG. 10 is a flow chart representing a variation of the basic scheme--operation with VBR and CBR background traffic; FIG. 11 is a flow chart representing a variation of the basic scheme--bi-directional counting; FIGS. 12 and 13 are flow charts representing a variation of the basic scheme--averaging the number of active sources; FIG. 14 is a flow chart representing a modification of the basic scheme--boundary case with zero active sources; FIG. 15 is a flow chart representing a modification of the basic scheme--boundary case with zero ABR capacity; FIG. 16 and 17 are flow charts representing a variation of the basic scheme--exponential averaging of load factor; FIG. 18A is a graphical representation of throughput versus load in a queue control network; FIG. 18B is a graphical representation of delay versus load in a queue control network; FIG. 18C is a graphical representation of link utilization versus time in a queue control network; FIG. 18D is a graphical representation of queue length versus time in a queue control network; FIG. 19 illustrates step functions for queue control; FIG. 20 illustrates linear functions for queue control; FIG. 21 illustrates hysteresis functions for queue control; FIG. 22 illustrates a queue control function; FIG. 23 is a flow chart representing a variation of the basic scheme--queue control option; FIG. 24 illustrates a one source configuration for ERICA; FIG. 25A is a graphical representation of the transmitted cell rate for the configuration of FIG. 24; FIG. 25B is a graphical representation of the queue length for the configuration of FIG. 24; FIG. 25C is a graphical representation of the link utilization for the configuration of FIG. 24; FIG. 25D is a graphical representation of the cells received for the configuration of FIG. 24; FIG. 26 illustrates a two source configuration for ERICA; FIG. 27A is a graphical representation of the transmitted cell rate for the configuration of FIG. 26; FIG. 27B is a graphical representation of the queue length for the configuration of FIG. 26; FIG. 27C is a graphical representation of the link utilization for the configuration of FIG. 26; FIG. 27D is a graphical representation of the cells received for the configuration of FIG. 26; FIG. 28 illustrates a parking lot configuration for ERICA; FIG. 29A is a graphical representation of the transmitted cell rate for the configuration of FIG. 28; FIG. 29B is a graphical representation of the queue length for the configuration of FIG. 28; FIG. 29C is a graphical representation of the link utilization for the configuration of FIG. 28; FIG. 29D is a graphical representation of the cells received for the configuration of FIG. 28; FIG. 30 illustrates an upstream configuration for ERICA; FIG. 31A is a graphical representation of the transmitted cell rate for the configuration of FIG. 30; FIG. 31B is a graphical representation of the queue length for the configuration of FIG. 30; FIG. 31C is a graphical representation of the link utilization for the configuration of FIG. 30; FIG. 31D is a graphical representation of the cells received for the configuration of FIG. 30; FIG. 32A is a graphical representation of the transmitted cell rate for the behavior of ERICA on a WAN where the VBR source was active for alternating periods of 1 ms with 1 ms inactive periods in between; FIG. 32B is a graphical representation of the queue length for the behavior of ERICA on a WAN where the VBR source was active for alternating periods of 1 ms with 1 ms inactive periods in between; FIG. 32C is a graphical representation of the link utilization for the behavior of ERICA on a WAN where the VBR source was active for alternating periods of 1 ms with 1 ms inactive periods in between; FIG. 32D is a graphical representation of the cell received for the behavior of ERICA on a WAN where the VBR source was active for alternating periods of 1 ms with 1 ms inactive periods in between; FIG. 33A is a graphical representation of the transmitted cell rate for the performance with VBR on/off periods of 20 ms; FIG. 33B is a graphical representation of the queue length for the performance with VBR on/off periods of 20 ms; FIG. 33C is a graphical representation of the link utilization for the performance with VBR on/off periods of 20 ms; FIG. 33D is a graphical representation of the cell received for the performance with VBR on/off periods of 20 ms; FIG. 34A is a graphical representation of the transmitted cell rate for small burst sizes; FIG. 34B is a graphical representation of the queue length for small burst sizes; FIG. 34C is a graphical representation of the link utilization for small burst sizes; FIG. 34D is a graphical representation of the cell received for small burst sizes; FIG. 35A is a graphical representation of the transmitted cell rate for medium burst sizes; FIG. 35B is a graphical representation of the queue length for medium burst sizes; FIG. 35C is a graphical representation of the link utilization for medium burst sizes; FIG. 35D is a graphical representation of the cell received for medium burst sizes; FIG. 36A is a graphical representation of the transmitted cell rate for large burst sizes; FIG. 36B is a graphical representation of the queue length for large burst sizes; FIG. 36C is a graphical representation of the link utilization for large burst sizes; FIG. 36D is a graphical representation of the cell received for large burst sizes; FIG. 37A is a graphical representation of the transmitted cell rate for one greedy source and one bursty source in a WAN (large bursts) with bi-directional counting; FIG. 37B is a graphical representation of the queue length for one greedy source and one bursty source in a WAN (large bursts) with bi-directional counting; FIG. 37C is a graphical representation of the link utilization for one greedy source and one bursty source in a WAN (large bursts) with bi-directional counting; FIG. 37D is a graphical representation of the cell received for one greedy source and one bursty source in a WAN (large bursts) with bi-directional counting; FIG. 38A is a graphical representation of the transmitted cell rate for one greedy source and one bursty source in a WAN (large bursts) with exponential averaging; FIG. 38B is a graphical representation of the queue length for one greedy source and one bursty source in a WAN (large bursts) with exponential averaging; FIG. 38C is a graphical representation of the link utilization for one greedy source and one bursty source in a WAN (large bursts) with exponential averaging; FIG. 38D is a graphical representation of the cell received for one greedy source and one bursty source in a WAN (large bursts) with exponential averaging; FIG. 39A is a graphical representation of the transmitted cell rate for ten ACR retaining sources in a WAN (effect of per-VC CCR); FIG. 39B is a graphical representation of the queue length for ten ACR retaining sources in a WAN (effect of per-VC CCR); FIG. 39C is a graphical representation of the link utilization for ten ACR retaining sources in a WAN (effect of per-VC CCR); FIG. 39D is a graphical representation of the cell received for ten ACR retaining sources in a WAN (effect of per-VC CCR); FIG. 40A is a graphical representation of the transmitted cell rate for a transient source configuration in a LAN (effect of 2-step increase); FIG. 40B is a graphical representation of the queue length for a transient source configuration in a LAN (effect of 2-step increase); FIG. 40C is a graphical representation of the link utilization for a transient source configuration in a LAN (effect of 2-step increase); FIG. 40D is a graphical representation of the cell received for a transient source configuration in a LAN (effect of 2-step increase); and, FIG. 41 is a flowchart showing 2-class scheduling. [DETAILS] DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Reference will now be made in detail to the referred embodiments of the invention, an example of which is illustrated in the accompanying drawings. It is to be appreciated that the present scheme may be implemented on any suitable computer and/or telecommunications network configuration through hardware and/or software configurations that will be apparent to those skilled in the art. Source, Destination and Switch Behaviors FIG. 2 shows the path of a network 110 and the path of a Resource Management (RM) cell 112 through the network 110. A source end system 114 ("SES") sends data cells 116 at a rate called a Current Cell Rate (CCR). Every Nrm th cell sent from the source end system 114 will be an RM cell 112. The RM cell 112 contains information describing the CCR and an Explicit Rate (ER). Based on optimality and other considerations, switches 118 may calculate and set the ER field in the RM cells 112. The ER field indicates the rate the network 110 can support for a particular VC 120 at that time. A destination end system 122 ("DES") simply returns the RM cells 112 to the source 114 (possibly reducing the ER field). When the source 114 receives its RM cell 112, it adjusts its CCR to the value specified in the ER field of the RM cell 112. The SES 114 also performs interoperability functions (for bit-based feedback), handles the scheduling of data and RM cells 112 in both directions, and performs some open-loop control functions which control the behavior during the time of the first round-trip, before the first feedback is received. The Switch Algorithm This section briefly summarizes the source 114, destination 122 and switch 118 behaviors and then examines ERICA switch scheme, or algorithm, in detail. The switch algorithm is executed for every queueing point. In most switches, such queues occur at the outgoing link (output port). The switch 118 periodically monitors the load on each link and determines an overload factor, z, the available capacity, and the number of currently active VCs (N). Pseudocode for the switch algorithm is illustrated below: Notes: All rates are in the units of cell/s The following pseudocode assumes a simple fixed-time averaging interval The variable "Overload factor" is used instead of z 1. Initialization: ______________________________________ ABR.sub.-- Capacity .rarw.Target.sub.-- Utilization X Link.sub.-- Bandwidth - VBR.sub.-- Capacity Aggregate.sub.-- Received.sub.-- Cell.sub.-- Count .rarw.0 Clear VC.sub.-- Seen.sub.-- Bit for all VCs ABR.sub.-- Cell.sub.-- Count .rarw.ABR.sub.-- Capacity X Averaging.sub.-- Interval Num.sub.-- Active.sub.-- VCs .rarw.Some Initial Value FairShare .rarw.ABR.sub.-- Capacity/Num.sub.-- Active.sub.-- VCs MaxAllocPrevious .rarw.0 for all VCs MaxAllocCurrent .rarw.FairShare for all VCs IF (Per.sub.-- VC.sub.-- CCR.sub.-- Option) THEN NumberOfCells .rarw.0 for all VCs END (* IF *) ______________________________________ 2. A cell of "VC" is received: ______________________________________ Increment Aggregate.sub.-- Received.sub.-- Cell.sub.-- Count Mark VC.sub.-- Seen.sub.-- Bit IF (Bidirectional.sub.-- Counting.sub.-- Option AND (Cell is a BRM cell)) THEN Mark VC.sub.-- Seen.sub.-- Bit in the Reverse Direction END (* IF *) IF (Per.sub.-- VC.sub.-- CCR.sub.-- Option) THEN Increment NumberOfCells[VC] END (* IF *) ______________________________________ 3. The averaging interval timer expires ______________________________________ Num.sub.-- Active.sub.-- VCs .rarw.max (.SIGMA. VC.sub.-- Seen.sub.-- Bit, 1) Seen.sub.-- VC.sub.-- In.sub.-- Last.sub.-- Interval.sub.-- Bit .rarw.VC.sub.-- Seen.sub.-- Bit for all VCs ABR.sub.-- Capacity .rarw.Target.sub.-- Utilization X Link.sub.-- Bandwidth - VBR.sub.-- Capacity ABR.sub.-- Cell.sub.-- Count .rarw.ABR.sub.-- Capacity X Averaging.sub.-- Interval FairShare .rarw.ABR.sub.-- Capacity/Num.sub.-- Active.sub.-- VCs Overload.sub.-- Factor.rarw.Aggregate.sub.-- Received.sub.-- Cell.sub.-- Count/ABR.sub.-- Cell.sub.-- Count MaxAllocPrevious .rarw.MaxAllocCurrent for all VCs MaxAllocCurrent .rarw.FairShare for all VCs Reset all VC.sub.-- Seen.sub.-- Bits Reset all Seen.sub.-- RM.sub.-- Cell In This Interval bits Aggregate.sub.-- Received.sub.-- Cell.sub.-- Count .rarw.0 IF (Per.sub.-- VC.sub.-- CCR.sub.-- Option) THEN BEGIN For all VCs: CCR[VC] .rarw.NumberOfCells[VC]/Averaging.sub.-- Interval NumberofCells .rarw.0 for all VCs END (* IF-THEN-BEGIN *) Restart averaging interval timer 4. A Forward RM (FRM) Cell of "VC" is received: IF (NOT Per.sub.-- VC.sub.-- CCR.sub.-- Option) THEN CCR[VC] .rarw.CCR in FRM cell ______________________________________ 5. A Backward RM (BRM) cell of "VC" is received: The information for feedback is accessed from the corresponding forward direction port. ______________________________________ IF (Bidirectional.sub.-- Counting Option AND Bursty.sub.-- Source.sub.-- Counting.sub.-- Option) THEN BEGIN IF (NOT Seen.sub.-- VC.sub.-- In.sub.-- Last.sub.-- Interval) THEN BEGIN Set Seen.sub.-- VC.sub.-- In.sub.-- Last.sub.-- Interval bit Increment Num.sub.-- Active.sub.-- VCs FairShare .rarw.ABR.sub.-- Capacity/Num.sub.-- Active.sub.-- VCs END END IF (NOT Seen.sub.-- RM.sub.-- Cell.sub.-- In.sub.-- This.sub.-- Interval) THEN BEGIN VCShare .rarw.CCR[VC] / Overload factor (* Max-Min Fairness Algorithm *) IF (Overload factor > 1 & &) THEN ER.sub.-- Calculated .rarw.Max (FairShare, VCShare) ELSE ER.sub.-- Calculated .rarw.Max (FairShare, VCShare, MaxAllocPrevious) END (*IF-THEN-ELSE*) MaxAllocCurrent .rarw.Max (MaxAllocCurrent, ER.sub.-- Calculated) ER.sub.-- Calculated .rarw.Max (FairShare, VCShare) (* Avoid Unnecessary Transient Overloads *) IF ((CCR[VC] 1+.delta., where .delta. is a small fraction, the basic ERICA algorithm is used where the source 114 is allocated as Max (FairShare, VCShare). But, for z<=1+.delta., an attempt is made to make all the rate allocations equal. The ER is calculated as Max (FairShare, VCShare, MaxAllocPrevious). A key point is that the VCShare is only used to achieve efficiency. Fairness can be achieved only by giving the contending sources equal rates. The solution proposed here attempts to give the sources 114 equal allocations during underload and then divide the (equal) CCRs by the same z during the subsequent overload to bring them to their max-min fair shares. The system is considered to be in a state of overload when its overload factor, z, is greater than 1+.delta.. The aim of introducing the quantity .delta. is to force the allocation of equal rates when the overload is fluctuating around unity, thus avoiding unnecessary rate oscillations. One possibility is to simply set the parameter 6 equal to 1-target utilization. Thus, referring to FIG. 4, an initialization and subsequent determination of values for MaxAllocPrevious and MaxAllocCurrent are calculated after Steps 1-5, e.g. of FIG. 3. After Step 8, e.g. of the basic scheme illustrated in FIG. 3, a new Step 9 as shown in FIG. 4 is executed. The scheme then proceedes to Step 10. It is to be recognized that variations of the basic scheme illustrated herein may be utilized with the basic scheme or with variations of the basic scheme. Thus, for example, new Step 9 of FIG. 4 may be implemented to follow, among others, Step 8 of FIG. 3 or Step 8 of FIG. 7. As a further example, new Step 2 of FIG. 10 may be implemented to follow, among others, Step 1 of FIG. 3 or new Step 1 of FIG. 12. As a still further example, the variation of FIG. 5 may be implemented wherever appropriate including between Steps 9 and 10 of FIG. 3 or between new Step 9 and Step 10 (or a variation thereof) in FIG. 4. This flexibility creates a multitude of possibilities--too numerous to practically list but apparent to those skilled in the art--with respect to implementation of the present scheme by users. All such possibilities and variations are intended to fall within the scope of the present invention. Fair Share First to Avoid Transient Overloads The inter-RM cell time determines how frequently a source 114 receives feedback. It is also a factor in determining the transient response time when load conditions change. With the basic ERICA scheme, it is possible that a source 114 which receives feedback first can keep getting rate increase indications, purely because it sends more RM cells 112 before competing sources can receive feedback. This may result in unnecessary spikes (sudden increases) in rates and queues with the basic ERICA scheme. The problem arises when the Backward RM (BRM) cells from different sources arrive asynchronously at the switch 118. Consider a LAN configuration of two sources (A and B), initially sending at low rates. When the BRM arrives, the switch 118 calculates the feedback for the current overload. Without loss of generality, assume that the BRM of source A is encountered before that of source B. Now it is possible that the BRM changes the rate of source A and the new overload due to the higher rate of A is experienced at the switch before the BRM from the source B reaches the switch. The transient overload experienced at the switch may still be below unity, and the rate of source A is increased further (BRMs for source A are available since source A sends more RM cells at higher rates). This effect is observed as an undesired spike in the rate graphs and sudden queue spikes when the source B gets its fair share. This problem can be solved by incorporating the following change to the ERICA algorithm. When the calculated ER is greater than the fair share value, and the source is increasing from a CCR below fair share, we limit its increase to fair share. Alternatively, the switch could decide not to give new feedback to this source for one measurement interval. This is useful in LANs where the round trip time is shorter than the inter-RM cell gap and the switch measurement interval. The following computation is added to the switch algorithm. After "ER.sub.-- Calculated" is computed: IF ((CCRFairShare)) THEN ER.sub.-- Calculated=FairShare In addition, feedback can be optionally disabled to this source for one measurement interval. "ER in RM Cell" is then computed as before. Thus, after Step 9 as shown in FIG. 5, a determination is made whether the current cell rate is less than fair share and whether the ER.sub.-- Calculated is greater than or equal to the fair share. If the answer is Yes, the ER.sub.-- Calculated is set to be the fair share and, in addition, an option is provided to disable feedback to the source for one measurement interval. If the answer to the initial question is No, Step 10 is simply executed. Forward CCR used for Reverse Direction Feedback The original OSU scheme provided its feedback to the RM cells 112 going in the forward direction. This ensured that the CCR in the RM cell 112 was correlated to the load level measured by the switch during that interval. However, the time taken by the forward going RM cell 112 to travel back to the source 114 was long and this slowed down the response of the system. The only requirement for each switch 118 is to provide its feedback to the sources 114. This can also be achieved if it indicates the feedback in the reverse path of the RM cell 112. FIG. 6 illustrates reverse direction feedback. A backward going RM (BRM) cell 124 takes less time to reach the source 114 than the forward going RM (FRM) cell 112 which has to reach the destination 122 first. Thus, the system responds faster to changes in the load level. However, the CCR carried by the BRM cell 124 no longer reflects the load level in the system. To maintain the most current CCR value, the switch 118 copies the CCR field from FRM cells 112, and uses this information to compute the ER value to be inserted in the BRM cells 124. This ensures that the latest CCR information is used in the ER calculation and that the feedback path is as short as possible. FIG. 6 shows that the first RM cell 124 carries (in its backward path), the feedback calculated from the information in the most recent FRM cell 112. The CCR table update and read operations still preserve the 0(1) time complexity of the algorithm. Thus, referring to FIG. 7, when a forward RM cell is received, the current cell rate of the virtual channel is recorded. When a backward RM cell is received, the VC's share is calculated (Step 8) and Steps 9-11 are then executed. Single Feedback in a Switch Interval The switch 118 measures the overload, the number of active sources and the ABR capacity periodically (at the end of every switch averaging interval). The source 114 also sends RM cells 112 periodically (once every Nrm cells). These RM cells 112 may contain different rates in their CCR fields. If the switch 118 encounters more than one RM cell 112 from the same VC 120 during the same switch interval, then it uses the same value of overload for computing feedback in both cases. For example, if two RM cells 112 from the same VC 120 carried different CCR values, then the feedback in one of them will not accurately reflect the overload. As a result, the switch feedback will be erroneous and may result in unwanted rate oscillations. The switch 118 thus needs to give only one feedback value per VC 120 in a single switch interval. The above example illustrates a fundamental principle in control theory, which says that the system is unstable when the control is faster than feedback. Further, the system is unresponsive if the control is slower than feedback. Ideally, the control rate should be matched to the feedback rate. In our system, the delay between successive feedbacks should not be greater than the delay between successive measurements (controls). The original OSU scheme solved the problem of matching the feedback and control rate by correlating the source and switch intervals. The source interval is set to the maximum of all the switch intervals in the path. This ensures that no more than one RM cell from each VC is encountered by any switch during a single switch interval. A disadvantage of this approach is that RM cells can be spaced quite far apart if any switch in the path of the VC has a long interval. As a result, switches with shorter intervals may not see any RM cells for many intervals and would be unable to rapidly provide their feedback to the source. This affects the transient response of the system. ERICA, the present scheme, adopts a different approach, where the source 114 and the switch intervals need not be correlated. The switch 118 provides only one feedback value during each switch interval irrespective of the number of RM cells it encounters. The switch calculates the ER only once per interval, and the ER value obtained is stored. It inserts the same ER value in all the RM cells it sees during this interval. The source and switch intervals are completely independent. Furthermore, a switch 118 with a smaller interval can now convey its feedback faster and is not dependent on any other switches in the path. The source independently decides the inter-RM cell distance, thus determining the frequency of feedback. In FIG. 8, the switch interval is greater than the RM cell distance. The ER.sub.-- Calculated in the interval marked Load Measurement Interval is maintained in a table and set in all the RM cells passing through the switch during the next interval. Thus, referring to FIG. 9, a variation is shown. More specifically, the variation includes the following. When a backward RM cell is received, it is determined whether a backward RM cell for that particular virtual channel was seen during that averaging interval. If the answer is yes, the ER Calculated is determined to be the last allocated ER and then Step 11 is performed. If the answer is no, Steps 8, 9 and 10 are performed and the last allocated ER is set to be ER Calculated. Per-VC CCR Measurement Option The CCR of a source is obtained from the CCR field of the forward going RM cell 112. The latest CCR value is used in the ERICA computation. It is assumed that the CCR is correlated with the overload factor measured. When the CCR is low, the frequency of forward RM cells 112 becomes very low. Hence, the switch may not have a new CCR estimate though a number of averaging intervals have elapsed. Moreover, the CCR value may not be an accurate measure of the rate of the VC if the VC is bottlenecked at the source, and is not able to use its ACR allocation. Note that if a VC 120 is bottlenecked on another link, the CCR is set to the bottleneck allocation within one round-trip. A possible solution to the problems of inaccurate CCR estimates is to measure the CCR of every VC during the same averaging interval as the overload factor. This requires the switch to count the number of cells received per VC during every averaging interval and update the estimate as follows: At the end of a switch averaging interval: ##EQU6## When a cell is received: NumberOfCells[VC]=NumberOfCells[VC]+1 Initialization:FOR VC=T0 (NumberofVCs-1) NumberOfCells[VC]=0 When an FRM cell is received, do not copy CCR field from FRM into CCR[VC]. Note that using this method, the switch ignores the CCR field of the RM cell. The per-VC CCR computation can have a maximum error of (one cell/averaging interval) in the rate estimate. Hence the error is minimized if the averaging interval is larger. The effect of the per VC CCR measurement can be explained as follows. The basic ERICA uses the following formula: ER.sub.-- Calculated=Max (FairShare, VCShare) The measured CCR estimate is always less than or equal to the estimate obtained from the RM cell CCR field. If the other quantities remain constant, the term "VCShare" decreases. Thus the ER.sub.-- Calculated will decrease whenever the first term dominates. This change results in a more conservative feedback, and hence shorter queues at the switches. VBR and CBR Background The discussion so far assumed that the entire link was being shared by ABR sources. Normally, ATM links will be used by constant bit rate (CBR) and variable bit rate (VBR) traffic along with ABR traffic. In fact, CBR and VBR have a higher priority. Only the capacity left unused by VBR and CBR is given out to ABR sources. For such links, we need to measure the CBR and VBR usage along with the input rate. The ABR capacity is then calculated as follows: ABR Capacity=Target Utilization X Link Bandwidth-VBR Usage-CBR usage The rest of ERICA algorithm (or variations) remains unchanged. Notice that the target utilization is applied to the entire link bandwidth and not the left over capacity. That is, ABR Capacity.noteq.Target Utilization X {Link Bandwidth-VCR Usage-CBR Usage} There are two implications of this choice. First, (1-Target Utilization) x (link bandwidth) is available to drain the queues, which is much more that what would be available otherwise. Second, the sum of VBR and CBR usage must be less than (target utilization) x (link bandwidth). Thus, the VBR and CBR allocation should be limited to below the target utilization. Thus, referring to FIG. 10, when a VBR or CBR cell is received, the number of VBR and CBR cells are counted. At the end of an averaging interval, Step 1 is performed and Step 2 is replaced as shown in FIG. 10. Steps 3, 4 and 5 are then performed and the CBR and VBR cell count is reset. Bi-directional Counting of Bursty Sources A bursty source sends data in bursts during its active periods, and remains idle during other periods. It is possible that the BRM cell of a bursty source could be traveling in the reverse direction, but no cells of this source are traveling in the forward direction. A possible enhancement to the counting algorithm is to also count a source as active whenever a BRM of this source is encountered in the reverse direction. We refer to this as the "Bidirectional counting of active VCs". One problem with this technique is that the reverse queues may be small and the feedback may be given before the Fair share is updated, taking into consideration the existence of the new source. Hence, when feedback is given, one can optionally check to see if the source has been counted in the earlier interval and if the Fair share has been updated based upon the existence of the source. If the source had not been counted, the number of active sources and the fair share is updated before giving the feedback. This enhancement entails the following modifications to the switch algorithm: BRM processing, before the ERICA feedback calculation: ##EQU7## We could also reset the CCR of such a source to zero after updating the fair share value, so that the source is not allocated more than the fair share value. The motivation behind this strategy is that the source may be idle, but its CCR is unchanged because no new FRMs are encountered. When the per-VC CCR measurement is used, this option is not necessary, because the switch measures the CCRs periodically. The setting of CCR to zero is a conservative strategy which avoids large queues due to bursty or ACR retaining sources. A drawback of this strategy is that in certain configurations, the link may not be fully utilized if the entire traffic is bursty. This is because all the bursty sources are asked to send at fair share, which may not be the optimal value if some sources are bottlenecked elsewhere. This option can also be enabled and disabled based upon a certain queue threshold. Thus, referring to FIG. 11, when a backward RM cell is received, it is determined whether the virtual channel is marked active in the forward direction in the current averaging interval. If it is then Steps 8, 9, 10 and 11 are performed. If not, the virtual channel is marked as active in the forward direction and the immediate fair share update option may be performed. Whether or not the option is performed, steps 8, 9, 10 and 11 of are subsequently performed. Averaging of the Number of Sources Another technique to overcome the problem of underestimating the number of active sources is to use exponential averaging to decay the contribution of each VC to the number of active sources count. A motivation behind this idea is that if a source is inactive during the current interval, but was recently active, it should still contribute to the number of active sources. This is because this source might be sending its data in bursts, and just happened to be idle during the current interval. This technique entails the following modifications to the switch algorithm: Initialization: ##EQU8## At the end of each interval: ______________________________________ Number of Active Sources in the Last Interval = Number of Active Sources in the Current Interval Number of Active Sources in the Current Interval = 0 FOR ALL VCs DO Contribution[VC] = Contribution[VC] * Decay.sub.-- Factor Number of Active Sources in the Current Interval = Number of Active Sources in the Current Interval + Contribution[VC] END Cell from virtual channel VC is seen: Number of Active Sources in the Current Interval = Number of Active Sources in the Current Interval - Contribution[VC] + 1 Contribution[VC] = 1 ______________________________________ The factor used in decaying the contribution of each VC is a value between zero and one, and is usually selected to be a large fraction, say 0.9. The larger the value of the Decay.sub.-- Factor, the larger the contribution of the sources active in prior intervals, and the less sensitive the scheme is to measurement errors. Setting the Decay.sub.-- Factor to a smaller fraction makes the scheme adapt faster to sources which become idle, but makes the scheme more sensitive to the averaging interval length. Thus, referring to FIG. 12, the initialization is performed and, at the end of the averaging interval, a new Step 1 is performed prior to Steps 2-5. As shown in FIG. 13, when a cell in the forward direction is received, it is determined whether the virtual channel is active in the current interval (that is, its contribution is 1). If the virtual channel is active, step 7 is performed. If the virtual channel is not active, the number of active sources is calculated based on the formula shown in FIG. 13B and then the immediate fair share update option may be performed. Step 7 is then performed after setting the VC's contribution to 1. Boundary Conditions Two boundary conditions are introduced in the calculations at the end of the averaging interval. First, the estimated number of active sources should never be less than one. If the calculated number of sources is less than one, the variable is set to one. Second, the load factor becomes infinity (when the ABR capacity is measured to be zero) or the the load factor becomes zero (when the input rate is measured to be zero). The corresponding allocations are made as follows: ______________________________________ ABR Input Over- Fair CCR/ Feedback Capacity Rate I load Share Overload 0 Nonzero .infin. 0 0 0 Nonzero 0 0 C/N 0 C/N Nonzero Nonzero I/C C/N CCR*C/I Max{CCR* C/I, C/N} 0 0 .infin. 0 0 0 The pseudo code for the boundary cases are: /* Boundary case for N */ IF (N < 1) THEN N := 1; /* Boundary case for load level, z */ IF ( ABR.sub.-- Capacity <= 0 ) THEN z:= Infinity; ELSE z:= (ABR.sub.-- Input.sub.-- Rate / ABR.sub.-- Capacity); ______________________________________ Thus, referring to FIG. 14, at the end of the averaging interval, step 1 is performed and then it is determined whether the number of active sources is less than one. If the number of active sources is less than one, then the number of active sources is set to one and steps 2-5 are performed. If the number of active sources is not less than one, steps 2-5 are performed. Referring to FIG. 15, in a boundary case relating to ABR capacity being zero, at the end of the averaging interval, steps 1 and 2 are performed and then a determination is made whether the ABR capacity is less than or equal to zero. If it is, the load factor is set to infinity and Steps 4-5 are performed. If the ABR is greater than zero, the load factor is calculated as in the basic scheme of FIG. 3 and steps 4-5 are performed. This entails a new step 3 as compared to that of, for example, FIG. 3. Averaging of Overload Factor In cases where no input cells are seen in an interval, or when the ABR capacity changes suddenly (possibly due to a VBR source going away), the overload measured in successive intervals may be considerably different. This leads to considerably different feedbacks in successive intervals. An optional enhancement to smoothen this variance is by averaging the overload factor. This effectively increases the length of the averaging interval over which the load factor is measured. Method 1 One method of averaging the load factor is given below: ______________________________________ IF ( ABR capacity <= 0 ) THEN z:= Infinity; ELSE IF (z = Infinity) THEN z:= ABR Input Rate / ABR Capacity; ELSE z := ( 1 -.alpha.) * z + .alpha. * (ABR Input Rate / ABR Capacity); ENDIF ENDIF ______________________________________ Method 2 The method 1 described above has the following drawbacks. First, the average resets everytime z becomes infinity. The entire history accumulated in the average prior to the interval where the load is measured to be infinity is lost. For example, suppose the overload is measured in successive intervals as: 2, 1, .infin., 3, .infin., 0.5. Method 1 forgets the history in the fourth interval, and restarts at the new value 3. Similarly in the sixth interval, it restarts at the value 0.5. Note that this method introduces dependencies between the boundary cases and the average value of the load factor. The second problem with method 1 is that the exponential average does not give a good indication of the average value of quantities which are not additive. In our case, the load factor is not an additive quantity. However, the number of ABR cells received or output is additive. Observe that the load factor is a ratio of the input rate and the ABR capacity. The correct way to average a ratio, whose numerator and denominator both have additive property, is to find the average (or the sum) of the numerators and divide it by the average (or the sum) of the denominators. That is, the average of x1/y1, x2/y2, . . . , xn/yn is (x1+x2+. . .+xn)/(y1+y2+. . .+yn). To average load factor, the input rate (numerator) and the ABR capacity (denominator) should be averaged separately. However, the input rate and the ABR capacity are themselves ratios of cells over time. The input rate is the ratio of number of cells input and the averaging interval. If the input rates are x1/T1, x2/T2, . . . , xn/Tn, the average input rate is {(x1+x2+. . .+xn)/n}/{(T1+T2+. . .+Tn)/n}. Here, xi's are the number of ABR cells input in averaging interval i of lengthTi. Similarly the average ABR capacity is {(y1+y2+. . . +yn)/n}/{(T1+T2+. . .+Tn)/n}. Here, yi's are the maximum number of ABR cells that can be output in averaging interval i of length Ti. The load factor is the ratio of these two averages. Observe that each of the quantities added is not a ratio, but a number. Exponential averaging is an extension of arithmetic averaging used above. Hence, the averages like (x1+x2+. . . . xn)/n can be replaced by the exponential average of the variable xi. The pseudo code describe this averaging is given below: At the end of averaging interval: ______________________________________ (* New Step 2: Calculating Input Rate and ABR Capacity * ABR Capacity in cells := Max{(Target Utilization * Link Bandwidth * This Interval Length) - VBR and CBR cell count, 0} Average ABR Capacity in cells := (1 -.alpha.) * Average ABR Capacity in cells + .alpha. * ABR capacity in cells Average Interval Length := (1 - .alpha.) * Average Interval Length + a * This Interval Length Average ABR Input Cell Count := (1 -.alpha.) * Average ABR Input Cell Count + .alpha. * ABR Input Cell Count for this Interval Average ABR capacity := Average ABR Capacity in cells / Average Interval Length; Average ABR Input rate := Average ABR Input Cell Count / Average Interval Length (* -- Step 3: Load Factor Calculation -- *) IF ( Average ABR capacity <= 0 ) THEN z := Infinity; ELSE z:= Average ABR Input rate / Average ABR capacity; ______________________________________ Average ABR Input rate: Observe that the overload factor thus calculated is never zero or infinity unless the input rate or ABR capacity are always zero. If the input rate or the ABR capacity is measured to be zero in any particular interval, the boundary cases for overload are not invoked. The load level increases or decreases to finite values. FIGS. 16 and 17 show alternate methods for exponential averaging of the load factor. Time+Count Based Averaging The overload factor, available ABR capacity and the number of active sources need to be measured periodically. There is a need for an interval at the end of which the switch renews these quantities for each output port. The length of this interval determines the accuracy and the variance of the measured quantities. As mentioned before, longer intervals provide lower variance but result in slower updating of information. Alternatively, shorter intervals allow fast response but introduce greater variance in the response. This section proposes alternative intervals for averaging the quantities. The averaging interval can be set as the time required to receive a fixed number of ABR cells (M) at the switch in the forward direction. While this definition is sufficient to correctly measure the load factor and the ABR capacity at the switch, it is not sufficient to measure the number of active VCs (N) or the CCR per VC accurately. This is because the quantities N and CCR depend upon the fact that at least one cell from the VC is encountered in the averaging interval. Moreover, when the rates are low, the time to receive M cells may be large. Hence the feedback in the reverse direction may be delayed. An alternative way of averaging the quantities is by a fixed time interval, T. This ensures that any source sending at a rate greater than (one cell/T) will be encountered in the averaging interval. This interval is independent of the number of sources, but is dependent upon the minimum rate of the source. In addition to this, if the aggregate input rate is low, the fixed-time interval is smaller than the fixed-cells interval. However, when there is an overload, the fixed-cells interval provides faster response. One way of combining these two kinds of intervals is to use the minimum of the fixed-cell interval and the fixed-time interval. This combination ensures quick response for both overload and underload conditions. But it still suffers from the disadvantages of a fixed-cell interval, where N and per-VC CCR cannot be measured accurately. Another strategy for overcoming this limitation is to measure N and per-VC CCR over a fixed-time interval, and the capacity and load factor over the minimum of the fixed-cell and fixed-time interval. The time intervals can be different as long as some correlation exists between the quantities measured over the different intervals. Typically, the intervals to measure CCR and N would be larger to get more stable estimates. A limitation of this strategy is that a sudden increase in the number of sources, N, or the measured CCRs cannot be sensed quickly. If we aim at allocating rates conservatively, the increase in CCRs does not pose a problem because we will use a smaller value of CCR in the ERICA formula, and give a smaller rate allocation. Rate increase will occur as soon as the fixed-time averaging interval yields a new value. However, the sudden increase in number of active sources (N) is of concern, since the allocation is inversely proportional to N. A smaller N may result in a larger allocation to all the sources and subsequent overload until the new value of N is calculated. Scheduling of ABR and VBR Since the switches provide multiple classes of service, they maintain multiple queues. The key question is how cells in these different queues are serviced. In this section, we describe a scheduling policy which allows the implementor (or user) to allocate "soft" percentages of link capacity for various classes. These allocations are soft in the sense that if one class does not use its allocation, it is automatically passed on to the other class(es). For example, in the case of a simple two class (VBR and ABR) system, an implementor could decide to give VBR a maximum of 90% and ABR a minimum of 10% bandwidth. If total VBR load is only 20%, ABR gets the remaining 80%. On the other hand if VBR input rate is 110% and ABR input rate is 15%, VBR gets only 90% and ABR gets 10%. If VBR and ABR are 110% and 5%, VBR gets 95% and ABR gets 5%. Notice that no class is starved and no bandwidth is wasted. The idea can be easily extended to any number of classes. The pseudocode for a two-class system is given below. In the pseudo-code the following variables are used: ______________________________________ afrac = Minimum Fraction desired for ABR vfrac = Maximum Fraction desired for VBR (afrac ABR cells are transmitted for every vfrac VBR cells) acredit = Current credit for ABR traffic vcredit = Current credit for VBR traffic (In general, the traffic with higher credit is serviced next.) aqueue = Number cells in the ABR queue vqueue = Number cells in the VBR queue acount = Number of ABR cells served vcount = Number of VBR cells served ______________________________________ The pseudo code is as follows: ______________________________________ Initialization vfrac, afrac = preassigned bandwidth fractions vcredit = vfrac, acredit = afrac. Algorithm For each slot time do IF vcredit >= acredit THEN IF VBR Queue is Non-empty THEN Schedule VBR Cell If ABR Queue is Non-empty THEN vcredit := vcredit - 1 vcredit := vcredit + vfrac acredit := acredit + afrac ENDIF ELSIF ABR Queue is Non-empty THEN Schedule ABR Cell ENDIF ELSE IF ABR Queue is Non-empty THEN Schedule ABR Cell If VBR Queue is Non-empty THEN acredit := acredit - 1 acredit := acredit + afrac vcredit := vcredit + vfrac ENDIF ELSIF VBR Queue is Non-empty THEN Schedule VBR Cell ENDIF ENDIF ENDFOR ______________________________________ Referring to FIG. 41, the flow chart for 2-class scheduling is shown. As illustrated, at every time slot, a determination of whether vcredit is greater than or equal to acredit is made. Subsequent determinations are made on queue status before allocations of link capacity are made. Queue length as a Secondary Metric ERICA depends upon the measurement of metrics like the overload factor, and the number of active ABR sources. If there is a high error in the measurement, and the target utilization is set to very high values, ERICA may diverge, i.e., the queues may become unbounded, and the capacity allocated to drain the queues becomes insufficient. The solution, under such cases is to set the target utilization to a smaller value, allowing more bandwidth to drain queues. However, steady state utilization (utilization when there is no overload) is reduced because it depends upon the target utilization parameter. One simple enhancement to ERICA is to have a queue threshold, and reduce the target utilization if the queue is greater than the threshold. Once the target utilization is low, the queues are drained out quickly. Hence, this enhancement maintains high utilization when the queues are small, and drains out queues quickly when they become large. Essentially, we are using the queue length as a secondary metric (input rate is the primary metric). In other schemes queue length or queue delay were not considered as a possible metric. In fact, they were rejected, because it was felt they gave no indication of the correct rates of the sources. The correct rate assignments depend upon the aggregate input rate, rather than the queue length. However, two facts about queues are important: a) non-zero queues imply 100% utilization, and, b) a system with very long queues is far away from the intended operating point. Hence in this embodiment, if the input rates are low and the queues are long, we recognize the need to reserve more capacity to drain the queues and allocate rates conservatively until the queues are under control. Further, keeping in line with the design principles of OSU scheme and ERICA, we use continuous functions of the queue length, rather than discontinuous functions. Since feedback to sources is likely to be regular (as long as queues last), the allocations due to a continuous function, in successive averaging intervals track the behavior of the queue, and reflect it in the rate allocations. 100% Utilization and Quick Drain of Queues ERICA achieves high utilization in the steady state, but utilization is limited by the target utilization parameter. For expensive links, it is desirable to keep the steady state utilization at 100%. This is because a link being able to service 5% more cells can translate into 5% more revenue. The way to get 100% utilization in steady state, and quick draining of queues is to vary the target ABR rate dynamically. During steady state 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 =fn(queue length, link rate, VBR rate) The "fn" above has to be a decreasing function of queue length. Note that ERICA has a fixed target utilization, which means that the drain rate is independent of the queue size. Maintain a "Pocket" of Queues One feature of ABR is that its capacity varies dynamically, due to the presence of higher priority classes (CBR and VBR). Hence, if the higher priority classes are absent for a short interval (which may be smaller than the feedback delay), the remaining capacity is not utilized. In such situations, it useful to have a "pocket" full of ABR cells which use the available capacity while the RM cells are taking the "good news" to the sources and asking them to increase their rates. One way to achieve this effect is to control the queues to a "target queue length." In the steady state, the link is 100% utilized, and the queue length is equal to the target queue length, which is the "pocket" of queues we desire. If the queue length falls below this value, the sources are encouraged to increase their rate and vice versa. In other words: Target rate=fn(queue length, target queue length, Link rate, VBR rate) Scalability to Various Link Speeds The above function is not scalable to various link speeds because, queue length measured in cells translates to different drain times for different transmission speeds. For example, a queue length of 5 at a Ti link may be considered large while a queue length of 50 at an OC-3 link may be considered small. This point is significant due to varying nature of ABR capacity, especially in the presence of VBR sources. To achieve scalability, we need to measure all queue lengths in units of time rather than cells. However, the queue is only directly measurable quantity at the switch. The queueing delay is then estimated using the measured ABR capacity value. Hence the above function for target rate becomes: Target Rate=fn(queue delay, target queue delay, Link Rate, VBR Rate) There are two problems to be faced before reaching the new set of goals. First, there is a tradeoff in maintaining high utilization and low end-to-end delay in steady state. An additional dimension is added to this tradeoff when we want good transient performance from underload and overload conditions. The optimal operating point may now be shifted from the knee of the throughput-delay curve for these considerations. Second, due to non zero feedback delays, the effect of the switch feedback in a cycle is observed only in the next cycle. If a larger fraction of link capacity is allocated for queue drain, then lesser capacity is allocated to the sources. This manifests as an underload in the next cycle and accelerates the process of queue drain. However, if the cycle length is large, then queues may quickly drop to zero and utilization drops to the input load level. We also note that end-to-end delay is affected by queueing, propagation, transmission, switching and processing delays. Of these, the propagation, switching and processing delays are constant. The transmission delay is variable depending on VBR load. Therefore, any scheme must control the queueing delay to influence the end-to-end delay characteristics. Target Operating Point of ERICA+ Queue Control for Congestion Avoidance ("ERICA+") uses a new target operating point, as shown in FIGS. 18A-D. The new target operating point has 100% utilization and a fixed non-zero queueing delay. This point differs from the knee point (congestion avoidance: 100% throughput, minimum delay) in that it has a fixed non-zero delay goal. This is due to non-zero queueing delay at the operating point. Note that the utilization remains 100% as long as the queue is non-zero. The utilization remains at 100% even if there are short transient underloads, or the output capacity increases (appearing as an underload). We note that, non-zero queue values in steady state implies that the system is in an unstable equilibrium. Queues grow immediately during transient overloads. In contrast, the ERICA and OSU schemes could allow small load increases (5 to 10%) without queue length increases. The challenge of ERICA+ is to maintain the unstable equilibrium of non-zero queues and 100% utilization. Specifically, when the queueing delay drops below the target value, T0, ERICA+ increases allocation of VCs to reach the optimum delay. Similarly, when the queueing delay increases beyond T0, the allocation to VCs is reduced and the additional capacity is used for queue drain in the next cycle. When the queueing delay is T0, 100% of the ABR capacity is allocated to the VCs. ERICA+ hence, introduces a new parameter, T0 in place of the target utilization parameter of ERICA. The ERICA+ Switch Scheme As mentioned before, the ERICA+ scheme is a modification of the ERICA scheme. In addition to the suggested scheduling method between VBR and ABR classes, the following are the changes to ERICA. 1. The link utilization is no longer targeted at a constant Target Utilization as in ERICA and OSU schemes. Instead, the total ABR capacity is measured given the link capacity and the VBR bandwidth used in that interval. Total ABR Capacity+VBR Capacity=Link Capacity 2. The target ABR capacity is a fraction of the total ABR capacity and this fraction is a function of the queueing delay T.sub.q at the switch. Total ABR Capacity=f(T.sub.q) X Total ABR Capacity This function must satisfy the following constraints: 1. It must have a value greater than or equal to 1 when the queuing delay, T.sub.q is 0 (zero queues). This allows the queues to increase and T.sub.q can go up to T0, the threshold value. A simple choice is to keep the value equal to one. The queue increases due to the slight errors in measurement. Another alternative is to have a linear function, with a small slope. Note that we should not use an aggressive increase function. Since queueing delay is a highly variant quantity, a small variance in delay values may cause large changes in rate allocations, and hence lead to instability. 2. It must have a value less than 1 when the queuing delay, T.sub.q is greater than T0. This forces the queues to decrease and T.sub.q can go down to T0. Since queue increases are due to traffic bursts, a more aggressive control policy is required for this case compared to the former case where we project a higher capacity than available. Since we project a lower capacity than what is available, the remaining capacity is used to drain the queues. 3. If the queues grow unboundedly, then we would like the function to go to zero. Since zero, or very low ABR capacity is unacceptable, we place a cutoff on the capacity allocated to queue drain. The cutoff is characterized by a parameter, called the queue drain limit factor (QDLF). A value of 0.5 for QDLF parameter is sufficient in practice. 4. When the queueing delay, T.sub.q is T0 we want f(T.sub.q)=1. A step function which reduces the capacity in steps (down to the cutoff value) as the queueing delay exceeds thresholds is a possible choice. This is shown in FIG. 19. Linear segments as shown in FIG. 20 can be used in place of step functions. Hysteresis thresholds FIG. 21 can be used in place of using a single threshold to increase and decrease the capacity. Hysteresis implies that we use one threshold to increase the capacity and another to decrease the capacity. However, these functions require the use of multiple thresholds (multiple parameters). Further, the thresholds are points of discontinuity, i.e., the feedback given to the source will be very different if the system is on the opposite sides of the threshold. However, it is possible to have a function with just 2 parameters, one for the two ranges: (0, Q0) and (Q0, infinity) respectively. The rectangular hyperbolic and the negative exponential functions are good choices to provide the aggressive control required when the queues grow. We choose the former which is the simpler of the two. Since the portion T