Rate control in transmission of packet data over an ATM network

[0002] The present invention relates generally to data communication systems, and specifically to traffic management of subscriber access to a high-speed network.

[0003] When a subscriber establishes a data connection to an Asynchronous Transfer Mode (ATM) network, a traffic contract is negotiated between the subscriber and the network specifying, inter alia, rates at which the network will accept data from the subscriber. Within the limits of these rates, the network guarantees that all data transmitted by the subscriber will be accepted and transmitted over the network. When the subscriber exceeds the contract rates, the network is liable to discard the excess data, although it may attempt to transmit the excess data when bandwidth is available.

[0004] The algorithm used in ATM networks for controlling transmission rates is known as the Generic Cell Rate Algorithm (GCRA) . GCRA operates, metaphorically, as a leaky bucket, with a fixed leak rate corresponding to a sustainable transmission rate specified by the subscriber's contract. When the subscriber transmits for a period at a rate that is lower than the sustainable contract rate, the bucket empties out, giving the subscriber the option subsequently of transmitting at a higher rate until the bucket fills up. Sustained transmission above the contract rate, however, will cause the bucket to fill up and overflow, whereupon excess cells are discarded. GCRA is defined formally in recommendation I.371 of the International Telecommunication Union (ITU-T) and in specification AF-TM-0056.00 of the ATM Forum (Traffic Management Specification Version 4.0). A concise definition and description of the algorithm is provided by de Prycker in Chapter 7 of Asynchronous Transfer Mode: Solution for Broadband ISDN(Prentice Hall, London, 1995). All of these documents are incorporated herein by reference.

[0005] GCRA specifies three key parameters for controlling subscriber transmission rates: the Peak Cell Rate (PCR), Sustainable Cell Rate (SCR) and Burst Tolerance (τ_s). PCR is a mandatory parameter, defined as the inverse of a minimum time T that is allowed between the arrivals of any two consecutive cells at the network interface. If cells are spaced by less than T, there is no guarantee that they will be transmitted. SCR and τ_sare optional, and are provided in order to enable the network to allocate resources more efficiently. SCR represents the average, long-term cell rate (less than the PCR) that the network guarantees to support. It corresponds to the leak rate of the bucket mentioned above. The subscriber may transmit data continuously at the SCR. If the subscriber transmits below the SCR for a period of time, however, the subscriber's “bucket” empties out, and it becomes possible for the subscriber to transmit a burst of data at the PCR. The size of the burst that will be accepted by the network depends on how “empty” the bucket is (i.e., how far below the SCR was the subscriber's transmission rate, and for how long) . In any case, the burst may be no larger than a Maximum Burst Size (MBS), defined by:

[0006] MBS=[1+τ_s/(T_s−T)]  (1)

[0007] wherein T_s=1/SCR. The MBS corresponds roughly to the volume of the bucket.

[0008] ATM networks carry cells of constant, fixed size. The GCPA is therefore defined in terms of minimum times allowed between cells (T, T_s, and τ_s). ATM systems measure these times in order to implement the algorithm. On the other hand, in packet data networks, such as Internet Protocol (IP) networks, the size of the packets is variable. Thus, when subscriber equipment generating variable-size packets is interfaced to a high-speed ATM network, it is necessary to take the packet size and packet rate into account in applying the GCRA. An approach of this sort is used in the Cisco Systems LightStream 2020 multiservice ATM switch. The traffic management properties of this switch are described in a document available at www.cisco.com/univercd/cc/td/doc/product/atm/12020/2020r211/sysover/traffic.htm, which is incorporated herein by reference. The approach adopted by this switch, however, applies only the mandatory PCR to the incoming packets. It does not attempt to deal with the added complication of the optional SCR and MBS parameters.

[0009] It is an object of the present invention to provide improved methods and apparatus for network traffic control.

[0010] It is a further object of some aspects of the present invention to provide improved methods and apparatus for implementing the GCRA in an ATM network access system that receives packet data for transmission over the network. It is a particular object of such aspects of the present invention to provide methods and apparatus for applying the GCRA using the optional SCR and MBS parameters.

[0011] In preferred embodiments of the present invention, an ATM network edge access interface receives data packets from a subscriber for transmission over the ATM network as cells. A contract between the subscriber and the network specifies the PCR, SCR and MBS (or the equivalent times T, τ_sand τ_s). As long as the data rate of the input packets does not exceed the SCR, the interface converts the packets to ATM cells and transmits them at a rate equal to or less than the SCR. As long as the input packet data rate is below the SCR, the subscriber accrues a “credit” at the network interface, up to a maximum given by the MBS. This credit is used subsequently, if the packet rate exceeds the SCR, to enable the interface to accept a burst of packet data and to transmit the data at the PCR.

[0012] The network access interface of the present invention is thus able to transmit packet data over the ATM network at either the PCR or the SCR (or below), making more efficient use of available bandwidth than is afforded by network equipment known in the art. Furthermore, by implementing transmission rate control at the packet level, rather than at the cell level as in systems known in the art, the present invention can help to reduce the computational load due to the rate control algorithm.

[0013] There is therefore provided, in accordance with a preferred embodiment of the present invention, a method for controlling data transmission over a network, including:

[0014] receiving a succession of data packets from a packet input at a potentially variable input data rate, each packet in the succession potentially having a respective, non-uniform packet size; and

[0015] for each of the packets in the succession:

[0016] comparing the respective packet size to a transmission credit allocated to the input;

[0017] if the allocated credit is sufficient, compared to the respective packet size, transmitting the packet over the network at a peak data transmission rate predetermined by the network; and

[0018] if the allocated credit is insufficient, compared to the respective size, transmitting at least a portion of the packet over the network at a rate no greater than a sustainable transmission data rate predetermined by the network, which sustainable transmission rate is less than the peak data transmission rate.

[0019] Preferably, transmitting at least a portion of the packet includes, if the allocated credit is insufficient compared to the respective packet size, transmitting the entire packet at the sustainable data transmission rate.

[0020] Alternatively, transmitting at least a portion of the packet includes, if the allocated credit is insufficient compared to the respective packet size, transmitting a first portion of the packet at the peak data transmission rate and transmitting a remaining portion of the packet at the sustainable data transmission rate. Preferably, transmitting the first portion comprises transmitting a quantity of the data that is substantially equal to the allocated credit, and reducing the credit substantially to zero after transmitting the quantity of the data that is substantially equal to the allocated credit.

[0021] In a preferred embodiment, the network includes an Asynchronous Transfer Mode (ATM) network, and the peak and sustainable data transmission rates respectively correspond to peak and sustainable cell rates. Preferably, receiving the succession of data packets includes receiving the packets over an Ethernet link.

[0022] Preferably, the method includes increasing the transmission credit allocated to the input when the variable input rate is less than the sustainable transmission rate. Further preferably, increasing the transmission credit includes finding a time of completion of transmission from the interface of a first one of the packets and a time of arrival at the interface of a second one of the packets, successive to the first packet, and increasing the credit responsive to a difference between the time of completion of transmission of the first packet and the time of arrival of the second packet. Most preferably, finding the time of transmission includes estimating the time of transmission of the first packet responsive to the size of the first packet and the rate of transmission of the first packet. Additionally or alternatively, increasing the transmission credit includes increasing the credit up to a maximum credit that is proportional to a maximum burst size predetermined by the network.

[0023] Preferably, transmitting the packet at the peak transmission rate includes reducing the transmission credit allocated to the input by an amount proportional to the packet size.

[0024] There is also provided, in accordance with a preferred embodiment of the present invention, apparatus for controlling data transmission over a high-speed network, including:

[0025] an input packet interface, configured to receive over a packet link at a variable input rate a succession of packets containing data, each packet in the succession having a respective, non-uniform packet size;

[0026] an output interface to the network, configured to transmit the data over the high-speed network at either a peak transmission rate predetermined by the network or at a rate no greater than a sustainable transmission rate predetermined by the network, which sustainable transmission rate is less than the peak transmission rate; and

[0027] a processor, coupled between the input and output interfaces and adapted to control the transmission rate of the data contained in each of the data packets in the succession by comparing the respective packet size to an allocated transmission credit, such that if the allocated credit is sufficient, compared to the respective packet size, the packet is transmitted over the network at the peak transmission rate, while if the allocated credit is insufficient, compared to the respective packet size, the packet is transmitted at the rate no greater than the sustainable transmission rate.

[0028] The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings in which:

[0029] FIG. 1 is a block diagram that schematically illustrates network access interface apparatus, in accordance with a preferred embodiment of the present invention;

[0030] FIG. 2 is a schematic plot of packet data transmission rate over time, in accordance with a preferred embodiment of the present invention;

[0031] FIG. 3 is a flow chart that schematically illustrates a method for network traffic control, in accordance with a preferred embodiment of the present invention; and

[0032] FIG. 4 is a flow chart that schematically illustrates an alternative method for network traffic control, in accordance with a preferred embodiment of the present invention.

[0033] FIG. 1 is a block diagram that schematically illustrates network access interface apparatus 20, for linking subscriber equipment 22 to an ATM network, in accordance with a preferred embodiment of the present invention. The subscriber equipment generates packet data, which are preferably conveyed to apparatus 20 over a Local Area Network (LAN) connection, such as an Ethernet line, as is known in the art. Apparatus 20 is preferably a part of a Digital Subscriber Line access device, such as the CPE system produced by Orckit Communications Ltd., of Tel Aviv, Israel. Typically, apparatus 20 belongs to a remote access unit (known as ATU-R) of the DSLAM. The ATU-R is typically installed at the subscriber's premises and is linked by a telephone line to a central office having a trunk connection to the ATM network. Alternatively, apparatus 20 may be used, mutatis mutandis, in other ATM network access applications.

[0034] Apparatus 20 comprises a network processor 24, which communicates with subscriber equipment 22, and a modem 30, preferably an Asymmetric DSL (ADSL) modem, for communicating over the telephone line with the ATM network. For example, Virata, of Santa Clara, Calif., produces a device known as “Helium,” which can perform the functions of processor 24. The network processor is responsible for the Ethernet packet interface with equipment 22, as well as for converting the packets received from equipment 22 into ATM cells, while implementing the ATM Generic Cell Rate Algorithm (GCRA) to control data throughput, as described hereinbelow. The protocol processor preferably communicates with modem 30 over a Utopia interface, as is known in the ATM art.

[0035] FIG. 2 is a schematic plot 40 of the rate of cell data transmission over time by apparatus 20, in accordance with a preferred embodiment of the present invention. Two rates are defined by the above-mentioned ATM standards: the PCR and the SCR. Normally, processor 24 passes data through to modem 30 at the SCR or below, depending on the rate of packet data received from equipment 22. During a given period 42, the data rate drops below the SCR, and the subscriber accordingly accrues a “credit,” indicated by hatching in the figure. The method by which this credit is calculated is described hereinbelow with reference to FIG. 3. During a subsequent period 44, equipment 22 generates a burst of packets. Using the credit accrued during period 42, processor 24 transmits the burst at the PCR during period 44. The duration of the burst is limited by either the amount of the credit that accrued previously or by the MBS, whichever is smaller. When the credit is exhausted, processor 24 resumes transmission at the SCR.

[0036] FIG. 3 is a flow chart that schematically illustrates a method for network traffic control implemented by processor 24, in accordance with a preferred embodiment of the present invention. For the purpose of this method, the following variables are defined for each packet processed by processor 24:

[0037] VTP—Estimated time of completion of transmission of the preceding packet by modem 30.

[0038] CTC—Arrival time of current packet at interface 24.

[0039] VTC—Estimated time of completion of transmission of the current packet by modem 30.

[0040] PS—packet size, in equivalent ATM cells (424 bits), wherein it is assumed that for any packet, PS(t)≦SMBS.

[0041] A constant R is defined by R=(PCR−SCR)/PCR.

[0042] At start-up of the connection between equipment 22 and processor 24, VTP is set to zero, and a maximum credit amount [credit(0)], equal to R*MBS cells, is allocated to the subscriber. Subsequently, for each arriving packet, having a size PS, the processor first checks whether the packet has arrived later than the estimated end of transmission time of the preceding packet, i.e., if CTC>VTP. If so, the subscriber is entitled to accrue additional credit for as long as the subscriber's current credit level is less than the maximum credit. In this case, the credit is increased by SCR*(CTC-VTP), i.e., by an amount proportional to the “idle” time of the interface between the estimated end of transmission time of the preceding packet and the arrival time of the current packet.

[0043] Next the processor checks to determine whether the subscriber has sufficient credit accrued to send the current packet at the PCR, i.e., whether R*PS<credit. If so, the packet is sent at the PCR and the credit is reduced by R*PS. The estimated transmission time of the current packet, VTC (which becomes VTP in the next cycle of the method of FIG. 3), is set based on the arrival time CTC, assuming transmission of the packet at the PCR. On the other hand, if there is not sufficient credit accrued, the packet is sent at the SCR, and VTP is set assuming transmission at this slower rate.

[0044] If the current packet arrives before the estimated transmission time of the preceding packet, no additional credit can accrue. In this case, as in the previous case, if the credit accrued previously is greater than R*PS, then the packet is sent at the PCR, and the credit is reduced by R*PS. The estimated transmission time VTP of the current packet is set in this case based on the estimated transmission time VTP of the preceding packet. If there is not sufficient credit, the packet is sent at the SCR, and VTP is set accordingly.

[0045] After the current packet has been sent at the appropriate rate, the cycle repeats for each subsequent packet. Pseudocode corresponding to the cycle shown in FIG. 3 is listed in Table I, below:

[0046] FIG. 4 is a flow chart that schematically illustrates an alternative procedure for network traffic control, in accordance with a preferred embodiment of the present invention. This procedure is similar to the method of FIG. 3, but has the advantage of using available transmission capacity more fully and efficiently. For the sake of brevity, only those aspects of the procedure of FIG. 4 that differ substantively from those described above with reference to FIG. 3 are described hereinbelow.

[0047] Whenever it is determined that the subscriber's accrued credit is less than R*PS, the subscriber's remaining credit level is checked. If the credit has dropped to zero, then the entire packet is sent at the SCR and the new VTP is calculated, as in the embodiment of FIG. 3. On the other hand, if the subscriber has non-zero credit, processor 24 divides the packet into cells, and sends as many cells as the remaining credit will allow at the PCR. Once the credit is exhausted, the processor sends the remaining cells at the SCR. Upon completion of sending this packet, the subscriber remains with zero credit. For the case in which CTC >VTP (the left branch in the figure), VTP for the next packet will be given by:

[0048] VTP=CTC+credit/PCR+(PS-credit)/SCR.

[0049] Otherwise (in the right branch), VTP is given by:

[0050] VTP=VTP+credit/PCR+(PS-credit)/SCR.

[0051] Pseudocode corresponding to the cycle of FIG. 4 is presented in the table below:

[0052] Although the preferred embodiments described hereinabove are designed specifically for controlling a packet data input to an ATM network, the principles of the present invention may similarly be applied in interfacing to networks of other types. It will thus be appreciated that this preferred embodiment is cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and subcombinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art.