Transmission Rate Calculation Scheme Using Table-Lookup

1. Field of the Invention

This invention relates to flow control in a packetized data network. In particular, the present invention relates to the calculation of cell transmission rates in an Asynchronous Transfer Mode (ATM) based data network.

2. Description of the Related Art

Data communication under ATM is set forth in a standard entitled "The ATM Forum Specification, version 4.0" (the "ATM standard"). Under the ATM standard, data exchange between a source system and a destination system is accomplished using one or more packetized data streams ("virtual channels"). Data and control information in each virtual channel are transported by 53-byte data packets or cells ("ATM cells"). In general, under the ATM standard, a virtual channel is set up by a virtual circuit connection under a fixed or constant bit rate service (CBR), or a variable bit rate service (VBR). In fact, under the ATM standard, many CBR and VBR virtual circuits can coexist between a given pair of source and destination systems. In one type of VBR service, known as the "available bandwidth rate service" ("ABR service"), the source and destination systems periodically negotiate for each virtual channel a bit rate according to the traffic conditions in all switches along the path of the virtual channel's virtual circuit.

In an ABR virtual circuit, the virtual circuit, the source and destination systems, and all the switches in between, negotiate a "peak cell rate" (PCR), a "minimum cell rate" (MCR), and an "initial cell rate" (ICR). During the life of the virtual circuit, resource management (RM) cells are sent periodically by the source system. Initially, the ATM cells for the virtual channel are sent at the ICR until the first RM cell is sent by the source. Included in the RM cell is an "explicit rate" (ER) field and a "direction" (DIR) field, which are initialized by the source system to the PCR and the value "forward" respectively. Because of the "forward" value in the DIR field, this RM cell is referred to as the "forward RM" (FRM) cell. As the FRM cell traverses the virtual circuit towards the destination system, each switch along the virtual circuit examines the ER field of the FRM cell and, where appropriate, reduces the cell rate specified in that field to indicate the available bandwidth the switch can provide, given its own local traffic condition. If a congestion condition is experienced at the switch, i.e. the instantaneous or immediate rate at which ATM cells are arriving exceeds the rate at which these ATM cells can be processed and forwarded by the switch, a "congestion" field (CI) of the FRM cell is marked. When the FRM cell reaches the destination system, the destination system (i) makes its own adjustment to the ER field, if necessary, (ii) marks the DIR field of the RM cell to indicate that the RM cell is now a "backward" RM (BRM) cell, and (iii) returns the BRM cell to the source system in the reverse direction on the virtual circuit. When the BRM cell reaches the source system, the value in the ER field is examined against the current cell rate. The current cell rate, which is also known as the "allowable cell rate" (ACR), is increased or decreased according to the value in the ER field of the BRM cell returned.

In some applications, e.g. an ATM server, it is necessary to support a very large number of virtual channels (e.g. a 1000 channels) of various fixed and variable bit rates over a given ATM physical media. In such an application, a scheduler coordinates the shared use of the physical media among the large number of virtual channels, so that the use of the physical bandwidth of the physical media can be maximized. In addition, many schedulers provide a "fairness" scheme so that sharing of the available bandwidth among the multiple variable rate virtual channels can be carried out in a predictable manner, and each variable rate virtual channel is given some opportunity to meet its desired cell rate.

One class of fairness schemes is known as the "min-max" fairness schemes. Under a min-max fairness scheme, a system divides the virtual channels into two classes according to their respective cell rates relative to the average cell rater ##EQU1## of the system. In the first class, i.e. those virtual channels having desired cell rates at or below the average cell rate, these virtual channels are provided the desired cell rate. In the second class, i.e. those virtual channels having desired cell rates above the average cell rate, these virtual channels share the remaining bandwidth. Within the second class, the bandwidth can be shared among the virtual channels equally ("unweighted"), or according to some assigned priorities ("weighted"). To ensure robustness under a min-max fairness scheme, the elements in the virtual circuits servicing the virtual channels must be capable of rapid response. Otherwise, data loss may result. For example, consider the case when one congested virtual circuit decreases its cell rate abruptly, thereby relieving the congestion condition at a previously congested element within the virtual circuit. In response to the bandwidth now available at the previous congested element, several virtual circuits may attempt to increase their respective cell rates at the same time. If the readjustment in cell rates in these virtual circuits do not occur rapidly enough, congestion conditions may then reappear at other elements of the network rapidly. Such congestion conditions, if not corrected rapidly, may lead to data loss.

The present invention provide both a circuit and a method for adjusting allowable cell rates (ACRs) under the ATM standard in logarithmic steps. That is, in accordance with the present invention, each allowable cell rate used in any virtual connection can be increased or decreased to the next allowable cell rate by a substantially constant percentage of the current allowable cell rate, over the entire range of allowable cell rates. Under this scheme, a "cell rate density" problem in the prior art, in which the number of available allowable cell rates at the higher transmission rates is small relative to the number of available allowable cell rates at the lower transmission rates, is overcome.

One embodiment of the present invention is implemented in a segmentation and reassembly (SAR) integrated circuit which complies with the aynchronous transfer mode (ATM) standard. In that embodiment, the circuit of the present invention is used for calculating the next allowable cell rate for a variable bit rate service. In that embodiment, a circuit is provided in which the next allowable cell rate is selected from an ordered list of available allowable cell rates in accordance with the current allowable cell rate. In this ordered list, the ratio between two successive elements of the ordered list is substantially constant.

In one embodiment, the circuit of the present invention receives control signals indicating whether the next allowable cell rate is to be (i) greater than the current allowable cell rate, (ii) the same as the current allowable cell rate, or (iii) less than the current allowable cell rate. In that embodiment, the circuit of the present invention includes a storage element containing a data structure indexed by the current allowable cell rate. The storage element outputs a first output value greater than the current allowable cell rate, and a second output value less than the current allowable cell rate. A selection circuit, which receives the control signals, then selects the next cell rate from the first and second output values and the current cell rate, in accordance with the control signals. The circuit in this embodiment can be simply implemented using a state machine and multiplexers and hence avoids computationally expensive steps. Consequently, the present invention allows real time scheduling of a large number of virtual channels. The present invention is particularly convenient for use with a calendar type scheduler. The table look-up method is particularly efficient when the number of available allowable cell rates is an integer power of 2.

In one embodiment, a selection circuit is provided for limiting the next allowable cell rate to between a maximum transmission rate and a minimum transmission rate. Typically, the maximum transmission rate is provided by the periodically negotiated "explicit rate" (ER) of a virtual connection. The ER is also typically limited by a peak cell rate (PCR) which is negotiated at the set-up time of the virtual connection.

The present invention is better understood upon consideration of the detailed description below and the accompanying drawings.

FIG. 1 shows a network interface system 100, including a segmentation and reassembly integrated circuit (SAR) 101, in which the present invention can be implemented.

FIG. 2 illustrates schematically the transmission operations of SAR 101 in an embodiment of the present invention.

FIG. 3 illustrates the static and dynamic scheduling mechanisms used in SAR 101 for scheduling fixed rate channels and variable rate channels, respectively.

FIG. 4 shows the allowable cell rate determination mechanism used in an embodiment of the present invention.

FIG. 5 shows in Table 1 an example of the available data rates that can be specified in an ACR rate table in the embodiment of FIG. 4.

FIG. 6 is a schematic diagram of a next data rate state machine 600 in the embodiment of FIG. 4.

FIG. 7 shows a cell rate update circuit 700 which can be used in the embodiment of FIG. 4.

The present invention can be implemented in a communication system using the ATM protocols. In particular, the present invention can be implemented in a rate calculation circuit of a segmentation and reassembly (SAR) integrated circuit. One implementation of this SAR integrated circuit supports both fixed rate and variable rate virtual channels. Such a SAR integrated circuit is shown in FIG. 1 which shows a network interface system 100 within which the present invention can be implemented. System hinterface system 100 interfaces with a host computer (not shown) over an industry standard PCI bus 108, and interfaces with an ATM network 107 over through a framer and physical media (PHY) device 103. System 100 includes SAR integrated circuit 101 ("SAR 101") which receives data from both the host computer and ATM network 107. SAR 101 segments the data received from the host computer into ATM cells, which are typically received in data packets ("protocol data units") in accordance with an established higher level protocol. The segmented ATM cells are provided over an industry standard UTOPIA bus 104 to PHY device 103 for transmission into ATM network 107. At the same time, SAR 101 receives ATM cells from PHY device 103, which are then reassembled by SAR 101 into the data packets of the higher level protocol for transmission to the host computer over PCI bus 108. An example of such a higher level protocol is the convergence sublayer (CS) protocol. In performing the segmentation and reassembly operations, SAR 101 uses static random access memory (SRAM) for storing such data structures as connection tables, buffer queues, segmentation channels, and scheduling tables. In addition, non-volatile memory, such as EPROM.sup.1 109 or EEPROM.sup.2 106 shown in FIG. 1, can also be provided to store the driver software necessary to drive the operations of SAR 101.

The transmission operations of SAR 101 is illustrated schematically in FIG. 2. As shown in FIG. 2, SAR 101 receives data from the host computer over PCI bus 108 in CS protocol data unit (CS-PDU) data packets. The operations of SAR 101 is globally controlled by a SAR device driver 201. The CS-PDU data packets are segmented into ATM cells and queued for transmission in their respective virtual channels. To emphasize that SAR 101 typically supports both fixed rate (i.e. CBR) services and variable rate (i.e. VBR or ABR) services, fixed rate virtual channels are illustrated separately as CBR channels 202, and variable rate virtual channels are illustrated as VBR/ABR channels 203 respectively. The physical bandwidth of SAR 101 is shared amongst CBR and VBR/ABR channels 202 and 203 according to the transmission schedule implemented in transmission schedule tables 204. A state machine, represented in FIG. 2 by ATM layer control module 205, controls multiplexing SAR 101's ATM cell transmission time slots 206 among CBR channels 202 and VBR/ABR channels 203. FIG. 2 shows, in particular, that the present embodiment further controls transmission of ATM cells in VBR/ABR channels 203 by including a rate control mechanism represented by rate counters 208.

In this embodiment, scheduling is provided by a 2-level scheme, in which a static master scheduler is used for scheduling ATM cell transmissions in fixed rate channels, and a dynamic scheduler is used for scheduling transmissions in the variable rate channels. FIG. 3 illustrates in the split into static and dynamic scheduling mechanisms. As shown in FIG. 3, for fixed rate channels, a static scheduler 301 schedules transmissions for fixed rate channels at regular intervals in a master schedule table 302. Master schedule table 302 is read by ATM layer control module 205 to determine which of the packets (i.e., cells), if any, queued at the fixed rate channels are to be transmitted into ATM network 107. In this embodiment, static scheduler 301 schedules into master schedule table 302 time slots allocated for the transmission of ATM cells from variable rate channels, or transmission of null cells from fixed rate channels. The null cells are used to maintain substantially constant bit rates for fixed rate channels. Such a static scheduler for the fixed rate channels can be implemented, for example, by the static scheduler described in copending U.S. patent application ("Static Scheduler Application"), entitled "SYSTEM AND METHOD FOR TRANSMISSION RATE CONTROL IN A SEGMENTATION AND REASSEMBLY CIRCUIT UNDER ATM PROTOCOL", by Michael J. Miller et al, Ser. No. 08/520,285, filed Aug. 25, 1995, and assigned to Integrated Device Technology, which is also the assignee of the present invention. The disclosure of the above-referenced Static Scheduler Application is hereby incorporated by reference in its entirety.

The variable rate channels are scheduled by a "dynamic scheduler" 303, which schedules the variable rate channels according to their "allowable cell rates" (ACRs). Under the ATM standard, data rates are represented in "cells per second" (cps) by a 16-bit floating point representation, thus spanning a dynamic range from "kilobits per second" to "gigabits per second". While the floating point representation provides a large dynamic range, calculation based on the floating point representation is computationally expensive. In addition, such a floating point-based data rate is difficult to use with a calendar type scheduler, such as static and dynamic schedulers 301 and 303. When using a calendar type scheduler, data rates are more conveniently expressed in number of time slots or intervals between transmissions, each interval representing the time duration necessary for transmission of a single cell. Converting a data rate from "bits per second" (bps) representation to intervals between transmissions is computationally expensive. To minimize computational time, a table look-up technique could be used.

In one table look-up technique, the data rate in intervals is provided by a 16-bit integer which represents the number of intervals between successive cell transmissions. For example, if one cell is transmitted at every interval, i.e., the number of intervals between successive transmissions is one, the top data rate of is achieved. In one implementation, that data rate is 155 Megabits per second (Mbps). If the number of intervals between successive Transmissions is two, i.e., a cell is transmitted every second interval, the data rate drops to 77.5 Mbps. However, one can easily observe that, under that implementation, the possible data rates for high frequencies is "sparse", i.e., the percentage difference in data rate between two data rates represented by small successive integer values of the 16-bit are much larger than between two data rates represented by large successive integer values of the 16-bit integer. For example, in the implementation discussed above, the data rate reduction between transmitting a cell every two intervals result and transmitting a cell every interval is 77.5 Mbps, or 50%. However, the data rate reduction between transmitting a cell every 65535 intervals and transmitting a cell every 65536 intervals is 0.03 bits per second.

To solve the sparse rate density problem, e.g., to achieve a data rate between 155 Mbps and 77.5 Mbps in the above example, while using a calendar type scheduling method, additional bits for fractional precision could be used. For example, an additional 4-bit is provided in the intervals between successive transmissions representation and more complex schedulers can be used. However, under such an approach, while increasing the rate density at the high data rates, further aggravates the rate density at the low data rates, and may result in unduly complex scheduling schemes and an astronomically large data rate table. As discussed below, the present invention provides more desirable data rate densities throughout the dynamic range of the data rates, using a data rate conversion table of reasonable size (e.g. 256 entries).

The allowable cell rate (ACR) for each variable bit rate channel is stored in ACR rate table 304, which is modified by rate control module 305 for each variable rate channel according to traffic conditions, e.g. congestions, in the channel's associated virtual circuit. Dynamic scheduling of variable rate channels are discussed in copending patent application ("Dynamic Scheduler Application"), entitled "METHOD FOR FAIR DYNAMIC SCHEDULING OF AVAILABLE BANDWIDTH RATE (ABR) SERVICE UNDER ASYNCHRONOUS TRANSFER MODE (ATM)", by Michael J. Miller et al., filed on the same day as the present application, attorney docket number M-3887-US, and assigned to Integrated Device Technology, Inc., which is also the Assignee of the present application. The disclosure of the Dynamic Scheduler Application is hereby incorporated by reference in its entirety. As provided in the Dynamic Scheduler Application, dynamic scheduler 303 inherently provides an unweighted fairness scheme which shares the available bandwidth among the variable bit rate channels. However, it is conceivable that an additional fairness scheme can be provided to control the static and dynamic scheduling mechanisms. This additional fairness scheme, represented in FIG. 3 by fairness calculator 306, can be provided, for example, in a software driver for SAR 101. One example of such an additional fairness scheme allocates a local maximum cell rate to each variable rate channel. This local maximum cell rates of all variable channels can be reallocated periodically according to the average local traffic load experienced by SAR 101 in the immediately preceding time period.

Under the ATM standard, when the virtual circuit for an ABR channel is first established, the elements in the virtual circuit negotiate an initial cell rate (ICR), a peak cell rate (PCR) and a minimum cell rate (MCR) upon set-up. Initially, the ICR is the ACR. The values of the PCR and MCR parameters constitute the maximum and the minimum acceptable cell rates during the life time of the virtual circuit. As discussed above, the ACR for each virtual channel is revised periodically by transmitting from the source end-station a resource monitor (RM) cell. The rate determination mechanism using an RM cell is illustrated by FIG. 4.

As shown in FIG. 4, for each variable bit rate channel, source end-station 100 transmits an RM cell periodically (e.g. every 32 data ATM cells) into the variable bit rate channel's associated virtual circuit in ATM network 107. In addition to identification information identifying the virtual bit rate channel, an RM cell includes the fields: "direction" (DIR), "congestion indicator" (CI), "no increase" (NI), "explicit cell rate" (ER), "current cell rate" (CCR) and "MCR". Source end-station 100 designates the "DIR" field of the RM cell the value "forward" (i.e. a forward RM (FRM) cell) and provides the values of the "ER", "CCR" and "MCR" fields to be the current ACR, the PCR and MCR values. As mentioned above, PCR and MCR values are negotiated when the virtual circuit is set up. Each element in the virtual circuit of the virtual channel can decrease, but not increase, the value of the ER field of the FRM cell according to the element's local traffic condition. Neither can the element decrease the value of the ER field below the negotiated MCR. If an element is experiencing a congestion condition, or if no increase in the CCR is desired, the element can so indicate by appropriately setting the "CI" and "NI" fields respectively. When destination end-station 401 receives the FRM cell, destination end-station 401 overwrites the "DIR" field of the FRM cell by the value "backward", thereby converting the ATM cell from an FRM cell to a "backward RM" (BRM) cell. Destination end-station 401 can also make appropriate modification to the BRM cell, if necessary, before returning the BRM cell to source end-station 100 via the associated virtual circuit in ATM network 107.

At source end-station 100, rate control module 305 examines the BRM cell received and determines if an increase or decrease in ACR is warranted. If neither the "CI" nor the "NI" field are set, i.e. indicating neither a congestion condition, nor a "no increase" constraint, ACR can be increased. ACR can be increased by a predetermined increment factor (RIF) of the PCR negotiated at virtual circuit creation time, subject to the negotiated ER returned in the BRM cell. The relationship between the new ACR (ACR.sub.new) and the current ACR (ACR.sub.old) is given by:

Source end-station 100 can decrease ACR when one or more of the following conditions are met: (i) the "CI" field of the received BRM is set, indicating a congestion condition in one or more elements of the virtual circuit in ATM network 107; (ii) an idle virtual channel condition, or (iii) a condition in which an extreme congestion safeguard is indicated. An idle virtual channel is indicated when CCR is greater than ICR and, at the time the FRM cell is sent, a predetermined threshold time period elapsed since the last RM cell is sent. An extreme congestion safeguard is indicated when multiple FRM cells have been sent, and not returned, since the last BRM cell is received at the source end-station 100. With a congestion condition, ACR can be decreased by a predetermined reduction factor (RDF) of the last ACR, subject to the MCR negotiated at the creation of the virtual circuit. The relationship between ACR.sub.new and ACR.sub.old under a congestion condition is given by:

In the case of an idle virtual channel condition, ACR is not decreased below ICR, and ACR.sub.new can be calculated as a function of the ACR.sub.old and the elapsed time since the last FRM cell (t.sub.last.sbsb.--.sub.FRM). One relationship between ACR.sub.new and ACR.sub.old that can be used under the idle virtual channel condition is given by:

where c is a constant.

When extreme congestion safeguard is indicated, ACR can be further decreased by a second predetermined reduction factor (CDF). The relationship between ACR.sub.new ', i.e. the ACR after adjustment for the idle virtual channel condition, and ACR.sub.new under extreme congestion safeguard is given by:

In this embodiment, to minimize the size of ACR rate table 304 and to ensure that any increase or decrease in ACR is a meaningful increase or decrease, i.e. affecting the cell rate of the virtual channel in a reasonably significant manner, increase or decrease of ACR in a virtual channel is taken in logarithmic-linear steps, each representing an increase or decrease in cell rate of a predetermined percentage from the immediately previous rate. An example of the available rates that can be specified in an ACR rate table is reproduced in Table 1 of FIG. 5. Table 1 includes 256 entries and each data rate can be represented by a 20-bit fixed-point number ("20-bit interval representation), including a 15-bit integer and 5 bits of fractional precision. The 20-bit fixed point representation, although not necessary for the present invention, requires cell rate computation operations which are simpler than those involved in the corresponding 16-bit floating point representation. Each allowable cell rate in Table 1 differs from the immediately previous allowable cell rate by approximately 4%. As shown in Table 1, the data rates can be alternatively represented in a interval representation (ACRI), or as a data rate (ACR) in either "bits per second" representation or "cells per second" representation. When a cell rate increase or a cell rate decrease is required, the new current cell rate can be obtained by a single table lookup operation into a rate increase table or a rate decrease table, using the present current allowable cell rate. The allowable cell rates can be represented by reference to the position of the corresponding entry in Table 1 ("8-bit interval representation"). An inverse table can be provided which maps the 16-bit floating point representation into the 8-bit interval representation.

By confining the allowable cell rates to the data rates of the above ACR data rate table, the computation necessary for calculating the next allowable cell rate resulting from an allowable cell rate increase or an allowable cell rate decrease can be achieved by a state machine-based data rate update circuit, using a table lookup method. FIG. 6 is a schematic diagram of such a next data rate state machine 600, in accordance with the present invention.

As shown in FIG. 6, next data rate state machine 600 includes a storage circuit 601, in which a rate increase table (601a) and a rate decrease table (601b) are stored. Rate increase table 601a and rate decrease table 601b in storage circuit 601 are each indexed by the current allowable cell rate, provided in the 8-bit interval representation ("LACRI"). In FIG. 6, the current allowable cell rate is held in a register 602. As discussed above, the current allowable cell rate is used to index into both rate increase table 601a and rate decrease table 601b. The tables provide two 8-bit allowable cell rate values, being respectively the next increased allowable cell rate and the next decreased allowable cell rate. A multiplexer 605 selects the allowable cell rate from the next increased allowable cell rate, the next decreased allowable cell rate, and the current cell rate, according to the values of the NI field and the CI field of the most recently returned BRM cell, as discussed above. The selected next allowable cell rate can be provided in the 20-bit interval representation, by looking up a rate conversion table in storage circuit 604. Alternatively, the data rate can also be mapped from the 8-bit interval representation into the 16-bit floating point of the ATM standard. The next allowable cell rate becomes the current allowable cell rate when loaded into register 602.

Using a next cell rate state machine, such as state machine 600 of FIG. 6, the allowable cell rate of a virtual circuit can be updated by the cell rate update circuit 700 of FIG. 7. FIG. 7 shows an update circuit 700 for periodically updating the allowable cell rate which can be used in conjunction with the embodiment of the present invention shown in FIG. 4. As shown in FIG. 7, a connection table is stored in a storage circuit 701. The connection table in storage circuit 701 includes a record for each active virtual connection. Each connection table record, indexed by the virtual connection number, includes the fields: (i) an 8-bit field 702a (LMCRI), which is the 8-bit interval representation of the minimum cell rate (MCR) negotiated when the virtual connection is set up; (ii) the current allowable cell rate field 702b in 8-bit interval representation (i.e., LACRI), (iii) the culrent allowable cell rate field 702c in 20-bit interval representation (i.e., ACRI), (iv) a 5-bit counter 702d for data cells (i.e., NRM cells) remained to be transmitted since transmitting the last RM cell, and (v) the current peak cell rate (PCR) field 702e, negotiated when the virtual connection is set up.

Periodically, an RM cell of the virtual connection is transmitted as an FRM cell initialized with the explicit rate (ER) field initialized to the value in PCR field 702e. When the RM cell is received as a BRM cell from the virtual connection, the value of the ER field is mapped to its 8-bit interval representation by a table look-up operation at storage element 703, which includes a table for mapping the 16-bit floating point data rate into a corresponding "LERI" value 707 in the internal 8-bit interval representation. At the same time, next cell rate state machine 701, which can be implemented by the state machine 600 of FIG. 6, provides the next allowable cell rate 706. Logic circuit 704 first selects the lesser of the "LERI" value 707 and next allowable cell rate 706 The greater of this selected value is then and the minimum cell rate (LMCRI) value 702a from the connection table is then provided as the current interval cell rate (LACRI). This current interval cell rate is mapped in storage circuit 705 by a table look-up process into a 20-bit interval representation (ACRI). The ACRI and LACRI current cell rates are stored into the LACRI and ACRI fields in the corresponding entries 702b and 702c of the connection table of storage circuit 702. In addition, the number of NRM cells to be transmitted before the next RM cell is written into data cell counter 702d in the corresponding entry of the connection table. The LACRI current cell rate is mapped into the 16-bit floating point representation in storage circuit 705 for use in the CCR field of the next RM cell. Upon initialization, the peak cell rate (PCR) is provided in the ER field.of the next RM cell.

Although not shown in FIG. 7, further cell rate adjustments under additional traffic conditions, e.g., the virtual idle channel, or the second rate reduction factor (CDF) discussed above, can be achieved by including additional circuits in logic circuit 704, or in the driver program.

The above detailed description is provided to illustrate the exemplary embodiments herein and is not intended to be limiting. Numerous modifications and variations within the scope of the present invention are possible. The present invention is defined by the following appended claims.