GB2307823A - ABR services in ATM networks - Google Patents

Abstract

A method of controlling the flow of cells on an ABR connection at a buffering point in an ATM network switch comprises using a traffic shaping process to guarantee a minimum cell rate for the ABR VC, preferably in combination with arbitration means to ensure a fair distribution of bandwidth through all the VCs on the switch. The invention also provides an ATM network switch comprising cell buffering means, the buffering means comprising traffic shaping means for guaranteeing a minimum cell rate for each ABR VC configured on the switch, arbitration means preferably being provided for ensuring a fair distribution of bandwidth through all the VCs on the switch.

Description

AVAILABLE BIT RATE SERVICES IN ATM NETWORKS Field of the Invention This invention relates to a method of controlling the flow of cells on an ABR connection at a buffering point in an ATM network switch, and to an Asynchronous Transfer Mode (ATM) network switch in which Available Bit Rate (ABR) services are more fully controlled.

Background to the Invention In ATM, the ABR service is intended to make the best use of remaining capacity after higher priority services such as CBR (Constant Bit Rate) and VBR (Variable Bit Rate) have been provided for. In ABR services, special ATM cells known as Rm cells are sent from the source, through the destination and back to the source to provide information on the congestion level in the switches in the path. This information is used by the source to modify its transmission rate, the objective being to utilise link capacity fully whilst not losing any cells as a result of congestion.

The Rm cells contain a number of fields, including CCR (Current Cell Rate), MCR (Minimum Cell Rate) and ER (Explicit Rate). The MCR is configured at connection set up and specifies the minimum rate at which the source is always allowed to send cells on the particular connection.

The CCR is the rate at which the source is currently transmitting; this varies according to a complex set of defined rules. The ER value is used to reduce the source to the transmission rate specified. It is set by switches in the network and may be reduced down to the MCR level.

Many different switch mechanisms have been proposed. These have varying performance levels, but generally require that all ABR connections have the same MCR value for correct operation. ER switch algorithms generally run into problems when the calculated ER is below that of the MCR of certain connections. Since the ER is calculated under the assumption that all active ABR connections will be reduced to this level, the amount of reduction will be insufficient when ER is less than MCR and some connections are not reduced as much as desired.

In practice, MCR values may vary from each other, and some may be zero. To avoid, or reduce, the incidence of congestion, it has been necessary to use iterative methods to reduce the assumed uniform ER value.

The present invention is concerned with a method of guaranteeing the MCR bandwidth for all ABR connections, and calculating an accurate and fair ER value for each connection.

Summary of the Invention According to the invention, there is provided a method of controlling the flow of cells on an ABR connection at a buffering point in an ATM network switch, comprising using a traffic shaping process to guarantee a minimum cell rate for the ABR VC, preferably in combination with arbitration means to ensure a fair distribution of bandwidth through all the VCs on the switch.

The traffic shaping process is any process which evens out the spacing of the cells transmitted from the buffering point as compared with the spacing on arrival at the buffering point.

Preferably, the traffic shaping process comprises a leaky bucket process, for example comprising: timing the arrival of each cell on the ABR; storing a predetermined regular bucket increment, a current bucket level value, a bucket maximum value, being the maximum capacity of the bucket, and an onward transmission time for the previous cell on the same VC; calculating the time difference between the arrival time of the cell and the stored onward transmission time for the preceding cell on the same VC; calculating a new bucket level from the time difference, the current bucket level, and the bucket increment; subtracting the maximum level from the new level to give an overflow value and, if the overflow value is negative, setting the value of the overflow to zero; and adding the overflow value to the current time to give the onward transmission time for the cell.

Suitably, two leaky bucket processes are operated in parallel, one monitoring peak cell flow rates and the other monitoring average cell flow rates, and the method comprises comparing the overflow values calculated for the two buckets, and adding only the greater of the two values to the current time to give the onward transmission time for the cell.

In one embodiment of the invention, the method comprises for each ABR cell arriving at the buffering point: (a) storing the cell in a buffer for that particular VC and, if that buffer was previously empty, storing in an arbitration FIFO a pointer to the VC buffer; (b) monitoring the input cell rate on the ABR connection; (c) determining from the input rate the onward transmission time for the cell and storing in a traffic shaping FIFO at an address corresponding to the onward transmission time a pointer to the cell address; (d) monitoring the onward cell rate for the ABR connection and determining an average;; (e) when the next cell transmission pointer emerges from the traffic shaping FIFO, obtaining from storage means the MCR for that VC and comparing the MCR with the average onward cell rate (OCR) determined in step (d) and, only if the OCR < MCR, outputting the cell to which the pointer refers; and (f) when the next cell transmission pointer for that VC emerges from the arbitration FIFO, obtaining from said storage means the MCR for that VC and comparing the MCR with the OCR determined in step (d) and, if OCR > MCR, outputting the cell to which the pointer refers, and then reintroducing the pointer into the bottom of the arbitration FIFO.

The invention also provides an ATM network switch comprising cell buffering means, the buffering means comprising traffic shaping means for guaranteeing a minimum cell rate for each ABR VC configured on the switch. Preferably, the switch comprises arbitration means for ensuring a fair distribution of bandwidth through all the VCs on the switch.

Preferably, the switch comprises a separate FIFO for each VC configured through the switch; and control means arranged to store each incoming cell in the appropriate FIFO; wherein the arbitration means is arranged to determine which of the FIFOs is to send the next cell to be transmitted onward from the buffering means, and the traffic shaping means is arranged to regulate the onward transmission time of ABR cells according to the rate of output of the ABR cells from the buffering means.

The traffic shaping means preferably comprises at least one leaky bucket processor, the or each leaky bucket processor comprising: timer means for timing the arrival of each ATM cell at the buffering means; memory means for storing a predetermined regular bucket increment, a current bucket level value, a bucket maximum value, being the maximum capacity of the bucket, and an onward transmission time for the previous cell on the same VC; calculating means for calculating the time difference between the arrival time of the cell and the stored onward transmission time for the preceding cell on the same VC, and for calculating a new bucket level from the time difference, the current bucket level and the bucket increment;; means for subtracting the maximum level from the new level to give an overflow value and, if the overflow value is negative, for setting the value of the overflow to zero; and adding means for adding the overflow value to the current time to give the onward transmission time for the cell and for storing said time in the memory means.

The traffic shaping means more preferably comprises a single leaky bucket processor, arranged to monitor peak cell flow rates.

In addition to the above-described mechanisms, an Explicit Rate (ER) value will be signalled back to the source for the particular VC, and means may be provided for changing the ER according to the congestion state of the switch. If congestion is occurring, the ER is reduced so as to cause the source to reduce the rate at which the cells are sent on the VC.

The ER is ideally set to the OCR or just below it, but a threshold is needed, since there should be at least a few cells in the FIFO for the system to operate. Thus, it is preferred to provide a minimum threshold value which can be programmed for a particular VC. When the threshold is exceeded, the ER may be set to the per VC OCR for the ABR VC. Preferably, however, the value is de-rated slightly. A global de-rating factor could be set for the whole network or simply for the port. The de-rating factors are needed to ensure that queues do not build up. It is necessary to allow for a lag in the effect of changing the ER.A further adjustment factor may also be used, viz.: (1 Uu tt), where VCcount is the number of cells in the particular buffer, and MAXcount is a configurable parameter for that particular VC, representing a maximum number of cells which can be haled by the VC buffer. Thus, as the FIFO grows, the ER value is reduced further.

Brief Description of the Drawings In the drawings, which illustrate an exemplary embodiment of the invention: Figure 1 is a diagrammatic representation of an ATM network switch; Figure 2 is a more detailed representation of one of the slot controllers of the switch shown in Figure 1; and Figure 3 is a more detailed representation of a cell ingress side buffering system within the slot controller shown in Figure 2 Detailed Description of the Illustrated Embodiment Referring first to Figure 1, the ATM network switch consists of a plurality of slot controllers 2; in the simple arrangement illustrated eight slot controllers are shown, but a typical switch might have 16 slot controllers. Each slot controller 2 has external input/output links 3.The switch also has a pair of switch fabrics 1 of a dynamic crosspoint type and each having input and output connections 4 and 5 respectively to each of the slot controllers 2. The two switch fabrics may be operated in such a manner as to double the bandwidth of the switch or to provide an immediate alternative path should any particular path through one switch fabric fail. This type of arrangement is described in more detail in our earlier application GB9507454.8. The structure of the slot controllers is, for example, of the general type described and claimed in our earlier application GB9505358.3, and ATM cells arriving on an input link 3 may be processed in the general manner described in that application.It will be appreciated that the particular structure of switch described is not the only type of switch to which the invention may be applied, but is given by way of example only.

Figure 2 shows the structure of a slot controller 2 in more detail.

For simplicity of illustration, the connections to only one of the switch fabrics are shown. The slot controller 2 comprises an output cell processor 21, whose structure will not be described further since it has no bearing on the present invention. The output cell processor 21 is connected to the external link 3 and to the output connection 5 from the switch fabric 1. It will be appreciated that the output cell processor principally handles functions such as the writing to the cell headers of the new VPI/VCI information, and output to the external data link 3. Data input on the external data link 3 is received by the input cell processor 22, which passes the cells to, and receives cells from, the buffering system 23, described hereinafter in more detail with reference to Figure 3.The cells are passed in sequence from the buffering system 23 via the input cell processor to the switching fabric 1 (Figure 1) on the input connection 4, to be switched to the appropriate destination slot controller.

Referring now to Figure 3, the buffering system 23 on the ingress side of the slot controller comprises a plurality of FIFOs 24, for example up to 64K FIFOs, configured dynamically in RAM according to the establishment of VCs through the switch. For convenience of illustration, only four of the FIFOs are shown in the Figure. The buffering system in accordance with the invention can be located at any queueing point in the switch, whether on the ingress or egress side. Each of the FIFOs 24 is configured dynamically according to the number of cells to be stored at any time on a particular VC. Since it is possible to configure VCs to use a particular switch fabric in a dual switch fabric switch, each VC will be configured to one or other of the switch fabrics.

A second set of FIFOs, the arbitration FIFOs 25, is also provided.

These may also be configured in a separate part of the same RAM, or in a separate RAM, if desired. The arbitration FIFOs are divided into two groups of four 25a and 25b, with one group for use with each of the two switch fabrics used in the switch as disclosed in our earlier UK Patent Application No 9507454.8. In Figure 3, each group consists of four arbitration FIFOs 25, one for each of the four classes or priority levels of ATM traffic typically provided for. It will be understood, however, that more or fewer arbitration FIFOs may be provided in each group according to the priority requirements of the network, and that, where the switch only has a single switch fabric, only one group of arbitration FIFOs may be required.

In use, the input cell processor 22 of the slot controller receives an incoming cell and determines its VCI and priority level from the cell header information (it will be appreciated that the cell processor also performs other functions to process the cell, but these are not described here as they do not affect the operation of the present invention). The processor 22 then checks the switch fabric (SF) paths through the two SFs for the particular VC. If both are broken, the cell is discarded at that point. If at least one of the paths is available, the processor 22 routes the cell to the "bottom" or input end of the appropriate VC FIFO 24, and at the same time increments a stored cell count for the individual VC FIFO.If the stored count was previously 0, a pointer is written to the "bottom" or input end of the appropriate arbitration FIFO 25, according to the cell priority and switch fabric used.

For output, the arbitration FIFOs are considered according to the priority level. Subject to a timing system described hereinafter, the level 0 or highest priority FIFO is always considered first, and only when there is nothing at this priority level will the lower priority levels be considered, the lower levels being considered in the same way so that only when all higher priority levels are empty will the level 3 FIFO be considered. Taking the case where the priority level 0 FIFO is not empty, a pointer is read from the "top" or output end of the FIFO. This pointer indicates the next VC FIFO to send a cell, and a signal is sent to that FIFO to output the next ATM cell to the processor 22 for onward routing via the switch fabric.

At the same time, the cell count for that particular VC is decremented in the cell processor 22, and, if the count is not 0, the pointer is re-entered into the "bottom" of the FIFO. Thus, there is only one pointer entry for any of the VCs in any of the arbitration FIFOs at any given time, and no pointer entry if the VC FIFO is empty. The cells are thus output from the VC FIFOs in turn, subject to the cell priority level, providing a "fair" allocation of the output bandwidth amongst the various VCs.

If the desired SF path is broken when the cell is to be sent, but the alternative path is available, the cell is not sent, and the pointer is entered instead at the bottom of the arbitration or output FIFO 25 for the alternative SF.

Entries in the output FIFOs 25 consist not only of the pointer to the VC FIFO, but also the output port number. The switch fabric preference and the priority bit are stored in the VC FIFO, so that these are available if the pointer has been transferred to the alternative SF output FIFO 25.

With the system described, it is possible that lower priority cells would wait an excessively long time in the VC FIFOs if there were a higher loading of higher priority cells. To overcome this potential difficulty, a timer may be associated with each of the arbitration FIFOs at priority levels 1, 2 and 3, arranged to output a time-out signal after a predetermined time period from the last output of a pointer from the respective arbitration FIFO 25. On receipt of the time-out signal, the priority given to the higher levels is temporarily over-ridden, permitting a pointer from the lower level FIFO 25 to be output, the respective timer then being reset.

It is possible with the system described to encounter "head-of-line" blocking, where one or more ports are full up (blocked), and so cells cannot be sent to the SF. To overcome this problem, yet another FIFO may be provided for the blocked outputs. The appropriate pointers are moved from the output FIFO 25 to the blocked output FIFO, which is given top priority for outputting cells from the VC FIFOs. Since it is possible then for several pointers to be present in the blocked output FIFO, a situation can arise where continued blockage of some ports would prevent cells being sent to other previously-blocked ports which subsequently become available.To overcome this problem, the pointers in this FIFO do not remain fixed, but are considered once per cell time, and if the pointer at the top of the FIFO relates to a VC for which the port is still blocked, so that the cell cannot be sent, the pointer is re-entered at the bottom of the FIFO so that the next pointer is considered in turn at the next cell time. There will need to be one blocked output FIFO for each output FIFO 25.

The processor 22 also incorporates a traffic shaping function which operates in conjunction with a further FIFO 26 (also configurable in RAM). The traffic shaping function is configured as a leaky bucket process, monitoring the peak cell rates for ABR VCs on the switch. The operation of the leaky bucket process is suitably of the general type described in our earlier application GB9509483.5.

The output cell processor 22 comprises leaky bucket processing means 23 which receives cells arriving from the switch fabric and which determines for each cell whether the peak cell flow rate appropriate to the cell's VC has been exceeded. If the cell conforms with the peak flow rate specified, the cell is entered into a buffer memory 24 at an address corresponding to the current time. If the peak rate has been exceeded, so that the leaky bucket overflows, the amount of the overflow is added to the current time as the address for the cell in the buffer memory 24. Thus, the onward transmission of the cell is delayed by the amount of the overflow, to ensure that the cell will conform with the specified rates. The ABR cells are output from the buffer memory 24 in order of stored time slot; the cells are not transmitted onwards before the relevant time slot becomes due.

However, a further stage of processing is carried out to ensure that the Minimum Cell Rate (MCR) is guaranteed for ABR VCs, where the MCR is not zero. The processor 22 monitors the output bandwidth for the ABR traffic, taking an average over a predetermined period of time. The rate per ABR VC can then be determined by dividing the rate of ABR cell output by the number of pointers in the FIFO 26. When a pointer is output from the end of the FIFO 26, the current value of the per VC output bandwidth is determined, and the MCR for the VC is looked up in a look-up table stored in monitoring means 27, which then compares the MCR with the ABR output cell rate (OCR).If the OCR > MCR, the basic requirement for the ABR service is met, and the pointer from the traffic shaping FIFO 26 is not used, but is simply discarded, reliance instead being placed on the ABR pointer from the arbitration FIFOs 25. If, on the other hand, the OCR < MCR, the pointer from the FIFO 26 is immediately used to initiate output of a cell from the appropriate per VC FIFO 24 (signalled via line 29).

Additionally, when a pointer is taken from the arbitration FIFO for an ABR VC, the OCR is again compared with the MCR for that VC, and if OCR > MCR, the cell is output from the relevant FIFO 24 and the pointer is re-entered in the arbitration FIFO at the input end. If OCR < MCR, the traffic shaping mechanism is used instead of the arbitration mechanism.

In practice, the traffic shaping mechanism will be configured to give a slightly higher value than the actual MCR, in order to ensure that the relevant FIFO queues tend to empty.

Claims (10)

Claims

1. A method of controlling the flow of cells on an ABR connection at a buffering point in an ATM network switch, comprising using a traffic shaping process to guarantee a minimum cell rate for the ABR VC.

2. A method according to Claim 1, which also comprises using an arbitration process to ensure a fair distribution of bandwidth through all the VCs on the switch.

3. A method according to Claim 1 or 2, wherein the traffic shaping process comprises a leaky bucket process comprising: timing the arrival of each cell on the ABR; storing a predetermined regular bucket increment, a current bucket level value, a bucket maximum value, being the maximum capacity of the bucket, and an onward transmission time for the previous cell on the same VC; calculating the time difference between the arrival time of the cell and the stored onward transmission time for the preceding cell on the same VC; calculating a new bucket level from the time difference, the current bucket level, and the bucket increment; subtracting the maximum level from the new level to give an overflow value and, if the overflow value is negative, setting the value of the overflow to zero; and adding the overflow value to the current time to give the onward transmission time for the cell.

4. A method according to Claim 2, comprising for each ABR cell arriving at the buffering point: (a) storing the cell in a buffer for that particular VC and storing in an arbitration FIFO a pointer to the cell address; (b) monitoring the input cell rate on the ABR connection; (c) determining from the input rate the onward transmission time for the cell and storing in a traffic shaping FIFO at an address corresponding to the onward transmission time a pointer to the cell address; (d) monitoring the onward cell rate for the ABR connection and determining an average; (e) when the next cell transmission pointer emerges from the traffic shaping FIFO, obtaining from storage means the MCR for that VC and comparing the MCR with the average onward cell rate (OCR) determined in step (d) and, only if the OCR < MCR, outputting the cell to which the pointer refers; and (f) when the next cell transmission pointer for that VC emerges from the arbitration FIFO, obtaining from said storage means the MCR for that VC and comparing the MCR with the OCR determined in step (d) and, if OCR > MCR, outputting the cell to which the pointer refers, and then reintroducing the pointer into the bottom of the arbitration FIFO.

5. An ATM network switch comprising cell buffering means, the buffering means comprising traffic shaping means for guaranteeing a minimum cell rate for each ABR VC configured on the switch.

6. A switch according to Claim 5, also comprising arbitration means for ensuring a fair distribution of bandwidth through all the VCs on the switch.

7. A switch according to Claim 6, comprising: a separate FIFO for each VC configured through the switch; and control means arranged to store each incoming cell in the appropriate FIFO; wherein the arbitration means is arranged to determine which of the FIFOs is to send the next cell to be transmitted onward from the buffering means, and the traffic shaping means is arranged to regulate the onward transmission time of ABR cells according to the rate of output of the ABR cells from the buffering means.

8. A switch according to any of Claims 5 to 7, wherein the traffic shaping means comprises at least one leaky bucket processor, the or each leaky bucket processor comprising: timer means for timing the arrival of each ATM cell at the buffering means; memory means for storing a predetermined regular bucket increment, a current bucket level value, a bucket maximum value, being the maximum capacity of the bucket, and an onward transmission time for the previous cell on the same VC; calculating means for calculating the time difference between the arrival time of the cell and the stored onward transmission time for the preceding cell on the same VC, and for calculating a new bucket level from the time difference, the current bucket level and the bucket increment; ; means for subtracting the maximum level from the new level to give an overflow value and, if the overflow value is negative, for setting the value of the overflow to zero; and adding means for adding the overflow value to the current time to give the onward transmission time for the cell and for storing said time in the memory means.

9. An ATM network switch, substantially as described with reference to the drawings.

10. A method of controlling the flow of cells on an ABR connection at a buffering point in an ATM network switch, substantially as described with reference to the drawings.