Controlled available bit rate service in an ATM switch

• US 6,327,246 B1
• Filed: 05/19/1998
• Issued: 12/04/2001
• Est. Priority Date: 11/29/1995
• Status: Expired due to Term

• Current Assignee: Fournier Assets LLC (Intellectual Ventures LLC)
• Original Assignee: Ahead Communications Systems, Inc. (General DataComm Industries, Inc.)
• Inventors: Jones, Trevor
• Primary Examiner(s): Jung, Min
• Application Number:
  US09/077,219
• Time in Patent Office: 1,295 Days
• Field of Search: 370/230, 370/232, 370/233, 370/234, 370/235, 370/412, 370/415, 370/462, 370/468, 709/232, 709/234, 709/235
• US Class Current: 370/232
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction

Abstract

An ATM switch (10) has a plurality of link controllers (12) each having a FIFO (30) for each VC established, a FIFO (32) for each priority level, and a traffic shaping FIFO (34) for pointers to ABR cells. Cells are pushed into the VC FIFO (30) and a pointer to the VC FIFO (30) is pushed into an arbitration FIFO (32) for the priority level of the VC FIFO (30). Pointers to ABR cells with onward transmission times are pushed into the traffic shaping FIFO (34). The arbitration FIFOs (32) are examined according to a schedule and cells are popped from VC FIFOs (30) according to priority for exit from the controller (12). A leaky bucket processor (22) calculates an average output cell rate OCR and ABR cells are popped from VC FIFOs out of turn if the MCR for the ABR VC exceed the OCR.

Claims

1. An ATM network switch, comprising:

a) at least one switch fabric; and

b) a plurality of controllers, each controller having,

an input link and an output link to said switch fabric,

at least one external link to an ATM network,

means for receiving ATM cells from the ATM network,

means for determining the VC of cells received from the ATM network,

a plurality of cell buffer means for separately buffering groups of cells of each VC,

means for determining whether each cell received from the ATM network is an ABR cell,

means for creating a pointer to each ABR cell, said pointer including an onward transmission time,

traffic shaping buffer means for buffering said pointers to said ABR cells,

look-up table means for storing an MCR for each ABR VC,

means for determining available output bandwidth for ABR traffic,

calculating means for calculating an allocated output cell rate for each ABR VC,

means for reading pointers from said traffic shaping buffer means,

means for comparing the MCR associated with a pointer read from said traffic shaping buffer means with said allocated output cell rate, and

means for transmitting cells from each of said cell buffer means to another controller via said switch fabric when the MCR associated with a pointer read from said traffic shaping buffer is greater than said allocated output cell rate.

2. An ATM network switch according to claim 1, wherein:

each controller further includes

means for determining a peak rate for ABR traffic,

means for determining if said peak rate has been exceeded,

means for delaying said onward transmission time when said peak rate has been exceeded.

3. An ATM network switch according to claim 2, wherein:

each controller further includes

means for determining an average rate for ABR traffic,

means for determining if said average rate has been exceeded,

means for delaying said onward transmission time when said average rate has been exceeded.

4. An ATM network switch according to claim 1, wherein:

each controller further includes

means for determining an ER based on said allocated output cell rate.

5. An ATM network switch according to claim 1, wherein:

each controller further includes

means for creating an arbitration pointer to each of said cell buffer means,

arbitration buffer means for buffering said arbitration pointers to said cell buffer means,

means for reading arbitration pointers from said arbitration buffer means, and

means for transmitting cells from each of said cell buffer means to another controller via said switch fabric according to arbitration pointers read from said arbitration buffer means.

6. An ATM network switch according to claim 5, wherein:

each controllers further includes means for determining a priority level for each VC,

said arbitration buffer means comprises a separate arbitration buffer for each priority level, and

said means for reading arbitration pointers includes means for ordering the reading of said separate arbitration buffers.

7. An ATM network switch according to claim 6, wherein:

said arbitration buffer means includes an ABR arbitration buffer for ABR arbitration pointers,

said means for reading arbitration pointers includes

means for reading ABR arbitration pointers,

means for comparing the MCR associated with an ABR arbitration pointer with said allocated output cell rate, and

means for transmitting cells from a cell buffer means pointed to by said ABR arbitration pointer to another controller via said switch fabric when the MCR associated with a pointer read from said traffic shaping buffer is less than said allocated output cell rate.

8. A method of controlling ABR traffic in an ATM network switch, comprising:

a) determining the VC for each ABR cell;

b) storing each ABR cell in a respective VC buffer for each ABR VC;

c) determining the MCR for each ABR VC;

d) storing the MCR for each ABR VC in a look-up table;

e) creating a pointer to each ABR cell, the pointer including an onward transmission time;

f) storing the pointers in a pointer buffer;

g) determining available output bandwidth for ABR traffic;

h) calculating an allocated output cell rate for each ABR VC,

i) reading pointers from the pointer buffer in order of onward transmission time;

j) comparing the MCR associated with a pointer with the allocated output cell rate; and

k) transmitting the cell associated with the pointer when the MCR associated with the pointer is greater than the allocated output cell rate.

9. A method according to claim 8, further comprising:

l) determining a peak rate for ABR traffic;

m) determining if the peak rate has been exceeded;

n) delaying the onward transmission time when the peak rate has been exceeded.

10. A method according to claim 9, further comprising:

o) determining an average rate for ABR traffic;

p) determining if the average rate has been exceeded;

q) delaying the onward transmission time when the average rate has been exceeded.

11. A method according to claim 8, further comprising:

1) determining an ER for each ABR VC based on the allocated output cell rate.

12. A method according to claim 11, further comprising:

m) adjusting the ER for each ABR VC based on the number of cells in a respective ABR VC buffer.

13. An ATM network switch, comprising:

a) at least one switch fabric; and

b) a plurality of controllers, each controller having,

an input link and an output link to said switch fabric,

at least one external link to an ATM network,

means for receiving ATM cells from the ATM network,

means for determining whether each cell received from the ATM network is an ABR cell,

means for determining the MCR for each ABR VC,

means for determining available output bandwidth for ABR traffic,

buffer means for buffering ABR cells,

means for comparing the MCR associated with a pointer read from said traffic shaping buffer means with said allocated output cell rate, and

means for transmitting ABR cells from said buffer means to another controller via said switch fabric based on a comparison of MCR and available output bandwidth for ABR traffic.

14. An ATM network switch according to claim 13, wherein:

each controller further includes

means for determining a peak rate for ABR traffic,

means for determining if said peak rate has been exceeded,

means for delaying transmission of ABR cells when said peak rate has been exceeded.

15. An ATM network switch according to claim 14, wherein:

each controller further includes

means for determining an average rate for ABR traffic,

means for determining if said average rate has been exceeded,

means for delaying transmission of ABR cells when said average rate has been exceeded.

16. An ATM network switch according to claim 13, wherein:

each controller further includes

means for determining an ER based on said available output bandwidth for ABR traffic.

17. An ATM network switch according to claim 16, wherein:

each controller further includes

means for determining the number of ABR cells in said buffer means, and

means for adjusting said ER based on the number of ABR cells in said buffer means.

18. 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 (MCR) for the ABR VC said traffic shaping process including

determining the MCR for each ABR VC,

determining the output bandwidth for ABR traffic,

comparing each MCR associated with a pointer to the allocated output cell rate, and

using the result of the comparison to control the transmission of ABR cells.

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

20. A method according to claim 18, 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 over flow 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.

21. A method according to claim 19, 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.

22. 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 said traffic shaping means comprising

means for determining the MCR for each ABR VC,

means for determining the output bandwidth for ABR traffic,

means for comparing each MCR associated with a pointer to the allocated output cell rate, and

means for using the result of the comparison to control the transmission of ABR cells.

23. A switch according to claim 22, also comprising arbitration means for ensuring a fair distribution of bandwidth through all the VCs on the switch.

24. A switch according to claim 23, 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.

25. A switch according to any of claim 22, 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.