Method and apparatus for traffic flow control in data switches

• US 6,721,273 B1
• Filed: 02/03/2000
• Issued: 04/13/2004
• Est. Priority Date: 12/22/1999
• Status: Expired due to Fees

• Current Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Lyon, Norman A.
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): RYMAN, DANIEL J
• Application Number:
  US09/496,651
• Time in Patent Office: 1,531 Days
• Field of Search: 370/235, 370/395.1, 370/396, 370/398, 370/395.71, 370/413, 370/414, 370/468
• US Class Current: 370/235
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5647 Cell loss
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/255 Control mechanisms for ATM switching fabrics
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Method and apparatus for traffic flow control in data switches are disclosed. Emission and loss priorities of cells to be switched are translated into a single discard priority, referred to as a bandwidth priority, which has consistent meaning across different emission priorities. This translation allows simultaneous consideration of loss and emission priority in determining which cells to discard when a switch becomes congested with cell traffic. Such consideration alleviates problems that can arise if cell discard decisions are based solely on either loss priority or emission priority. The invention is particularly useful for Asynchronous Transfer Mode (ATM) switches.

Claims

1. A data switch for switching data traffic in the form of cells, each cell having an indication of loss priority and emission priority of the cell, the data switch comprising:

a plurality of input ports, each input port being operable to either forward or discard a cell in dependence upon a flow control message received at the input port;

a switching fabric having multiple fabric inputs and multiple fabric outputs, the switching fabric being operable to switch a cell from any one of the fabric inputs to any one of a plurality of the fabric outputs, each of a plurality of the fabric inputs coupled to one of said input ports;

a plurality of output ports, each output port being operable to transmit an output port message having an indication of the emission and loss priorities of a cell received from the switching fabric, each output port coupled to one of said fabric outputs, each of the output ports includes an output queue for queuing cells that are awaiting transmission from the output port; and

a traffic flow controller coupled to the input and output ports, the traffic flow controller being operable to formulate, in dependence upon the output port messages, the flow control message indicating, for a particular output port, the loss and emission priorities of cells to discard that are destined for that particular output port;

wherein the traffic flow controller further comprises;

an accumulator for maintaining a count for each output queue, each count corresponding to a level of congestion of its respective output queue, the level of congestion effecting the number of cells in that output queue;

a memory for storing a bandwidth priority matrix which defines a bandwidth priority for each combination of loss priority and emission priority;

a register for storing at least one threshold for each output queue, each of the thresholds for an output queue corresponding to a bandwidth priority; and

a controller being operable to update and compare the count of each output queue to the thresholds of the output queue and determine the highest bandwidth priority corresponding to an exceeded threshold of that output queue, determine for each emission priority, the bandwidth priority of cells to discard in dependence upon said highest bandwidth priority corresponding to the emission priority, and encode the bandwidth priority of cells to discard into a flow control message indicating the loss priority and emission priority of cells to discard, the controller coupled to the accumulator, the memory and the register.

2. The data switch of claim 1, wherein:

each of the output ports includes a plurality of output queues and each of the output queues is for queuing cells of a unique emission priority; and

the controller is operable to determine that for each output queue of an output port, cells having a lower bandwidth priority than the highest bandwidth priority of that output queue are to be discarded if they have the same emission priority of that output queue or a higher emission priority.

3. The data switch of claim 2, wherein:

the accumulator comprises a counter for each of the output queues, each of the counters being operable to store the count corresponding to the level of congestion in its respective output queue.

4. The data switch of claim 3, wherein the controller comprises:

an incrementor, coupled to the counters, for receiving output port messages and incrementing the counters in dependence upon the output port messages;

a timer for determining a cell period;

a priority scheduler, coupled to the timer, for determining for each output port, which counter to decrement in any given cell period, the priority scheduler operable to select the counter of the highest emission priority having a non-zero count;

a decrementor, coupled to the counters, for causing a counter to be decremented in response to the priority scheduler; and

an encoder for comparing the count of each output queue to the thresholds of the output queue and determine the highest bandwidth priority corresponding to an exceeded threshold of that output queue, determining for each emission priority, the bandwidth priority of cells to discard in dependence upon said highest bandwidth priority corresponding to the emission priority, and encoding the bandwidth priority of cells to discard into a flow control message indicating the loss priority and emission priority of cells to discard, the controller coupled to the counters, the memory and the register.

5. The data switch of claim 1, wherein:

each of the output ports includes a scheduler for granting the transmission of cells from the output port, each of the schedulers being operable to include, in an output port message, an indication of the emission priorities of cells granted transmission.

6. The data switch of claim 5, wherein:

the memory is further for storing sets of state variables, each set of state variables representing transient congestion conditions of each output port, and storing a set of increment variables for incrementing the counts in dependence upon their respective set of state variables;

the controller is operable to update each set of state variables by determining, for each output port, a highest congested emission priority of cells not granted transmission and for filtering out transient downward priority changes thereto, and updating each of the counts in dependence upon the increment variables and the respective set of state variables for the count; and

the controller is further operable to determine that for each output port, cells having a lower bandwidth priority than the highest bandwidth priority corresponding to an exceeded threshold of that output port are to be discarded if they have the same emission priority, or higher, as said highest congested emission priority.

7. The data switch of claim 6, wherein:

the controller in updating each set of state variables is further operable to filter out transient periods of no congestion.

8. The data switch of claim 1, wherein:

the register is further for storing a flow control threshold for each output queue; and

the controller is further operable to compare the count of each output queue to the flow control threshold of the output queue and in response to the count exceeding the flow control threshold, encode a flow control message indicating that flow control is to be initiated for cells destined for that output queue.

9. A traffic flow controller for controlling traffic congestion in a data switch, the data switch including multiple input ports and output ports, the data switch being operable to switch data traffic in the form of cells received at the input ports to the output ports, each cell having an indication of loss priority and emission priority of the cell, the input ports being operable to discard cells in dependence upon flow control messages received from the traffic flow controller, the output ports operable to send output port messages to the traffic flow controller, the output port messages containing an indication of loss and emission priorities of cells received at the respective output port, the traffic flow controller comprising:

an accumulator for maintaining a count for each output port, each count corresponding to a level of congestion of its respective output port, the level of congestion effecting the number of cells in that output port;

a memory for storing a bandwidth priority matrix which defines a bandwidth priority for each combination of loss priority and emission priority;

a register for storing at least one threshold for each output port, each of the thresholds for an output port corresponding to a bandwidth priority; and

a controller being operable to update and compare the count for each output port to the thresholds for the output port and determine the highest bandwidth priority corresponding to an exceeded threshold of that output port, determine for each emission priority, the bandwidth priority of cells to discard in dependence upon said highest bandwidth priority, and encode the bandwidth priority of cells to discard into a flow control message indicating the loss priority and emission priority of cells to discard, the controller coupled to the accumulator, the memory and the register.

10. The traffic flow controller of claim 9 for a data switch in which each of the output ports includes a plurality of output queues and each of the output queues is for queuing cells of a unique emission priority, wherein:

the controller is operable to determine that for each output queue of an output port, cells having a lower bandwidth priority than said highest bandwidth priority of that output queue are to be discarded if they have the same emission priority of that output queue or a higher emission priority.

13. The traffic flow controller of claim 9 for a data switch in which each of the output ports includes a scheduler for granting the transmission of cells from the output port, each of the schedulers being operable to include, in an output port message, an indication of the emission priorities of cells granted transmission, wherein:

the memory is further for storing a sets of state variables, each set of state variables representing transient congestion conditions of each output port, and storing a set of increment variables for incrementing the counts;

the controller is operable to update each set of state variables by determining, for each output port, a highest congested emission priority without a grant and for filtering out transient downward priority changes thereto, and updating each of the counts in dependence upon the increment variables and the set of state variables associated with the output port; and

the controller is further operable to determine, for each output port, cells having a lower bandwidth priority than the highest bandwidth priority corresponding to an exceeded threshold of that output port are to be discarded if they have the same, or higher, emission priority as said highest congested emission priority of the output port.

14. The traffic flow controller of claim 13, wherein:

the controller in updating each set of state variables is further operable to filter out transient periods of no congestion.

11. The traffic flow controller of claim 11, wherein:

the accumulator comprises a counter for each of the output queues, each of the counters being operable to store the count corresponding to the level of congestion in its respective output queue.

12. The traffic flow controller of claim 11, wherein the controller comprises:

an incrementor, coupled to the counters, for receiving output port messages and incrementing the counters in dependence upon the output port messages;

a timer for determining a cell period;

a priority scheduler, coupled to the timer, for determining for each output port, which counter to decrement in any given cell period, the priority scheduler operable to select the counter of the highest emission priority having a non-zero count;

a decrementor, coupled to the counters, for causing a counter to be decremented in response to the priority scheduler; and

an encoder for comparing the count of each output queue to the thresholds of the output queue and determine the highest bandwidth priority corresponding to an exceeded threshold of that output queue, determining for each emission priority, the bandwidth priority of cells to discard in dependence upon said highest bandwidth priority corresponding to the emission priority, and encoding the bandwidth priority of cells to discard into a flow control message indicating the loss priority and emission priority of cells to discard, the controller coupled to the counters, the memory and the register.

15. A method of controlling traffic flow in a data switch, the data switch operable to switch data traffic in the form of cells, each cell including a loss priority and an emission priority of the cell, the data switch including multiple input ports and output ports, the method comprising the steps of:

assigning a bandwidth priority to each combination of loss and emission priority;

updating a count, the count corresponding to a level of traffic congestion in particular output port;

determining, for the particular output port and for each mission priority the bandwidth priorities of cells to discard in dependence upon the count associated with the particular output port;

translating the bandwidth priorities of cells to discard into loss and emission priorities of cells to discard; and

discarding, at the input ports, cells destined for the particular output port in response to the cells having loss and emission priorities matching said loss and emission priorities of cells to discard.

16. The method of claim 15, for a data switch in which the particular output port includes a plurality of output queues and each of the output queues is for queuing cells of a unique emission priority, wherein the step of updating comprises the step of:

updating counts, each count corresponding to a level of traffic congestion in an output queue.

17. The method of claim 16, wherein the step of updating further comprises the steps of:

detecting the emission priority of a cell entering the particular output port; and

incrementing the count corresponding to the output queue of the particular output port.

18. The method of claim 17, wherein the step of updating further comprises the steps of:

detecting the end of a cell period;

determining, for the particular output port and cell period, the count to decrement in dependence upon the count for each output queue of the particular output port, the count chosen to decrement being a non-zero count having the highest emission priority of the queues in the particular output port; and

decrementing the chosen count at the end of the cell period (original).

19. The method of claim 18, wherein the method further comprises an initial step of:

storing at least one threshold for each output queue, each of the thresholds for an output queue corresponding to a bandwidth priority, and

wherein the step of determining, for a particular output port and for each emission priority, the bandwidth priority of cells to discard further comprises the steps of;

comparing the count of each output queue to the thresholds of the output queue;

determining, for each output queue, the highest bandwidth priority corresponding to an exceeded threshold of that output queue;

determining, for the particular output port, the bandwidth priority of cells to discard in dependence upon the highest bandwidth priorities of the particular output port;

encoding, for the particular output port, the bandwidth priority of cells to discard into a flow control message indicating the loss priority and emission priority of cells to discard; and

sending the flow control message to the input ports.

20. The method of claim 19, wherein the step of determining, for the particular output port, the bandwidth priority of cells to discard, comprises the step of:

identifying, for each output queue of the particular output port, bandwidth priorities of cells to discard as being bandwidth priorities that are lower than the highest bandwidth priority corresponding to an exceeded threshold of the output queue and have the same emission priority as the output queue or a higher emission priority.

21. The method of claim 15, for a data switch in which the particular output port includes a plurality of output queues and each of the output queues is for queuing cells of a unique emission priority, the particular output port further includes a scheduler for granting the transmission of cells from the output queues, the scheduler being operable to include, in an output port message, an indication of the emission priorities of cells granted transmission, wherein the step of updating a count comprises the steps of:

calculating, for the particular output port, state-information which represents transient traffic congestion conditions at the particular output port; and

updating, for the particular output port, the respective count in dependence upon the state information of the particular output port.

22. The method of claim 21, wherein the step of calculating comprises the steps of:

determining, for the particular output port from a respective output port message, the highest congested emission priority of a cell not granted transmission;

determining, for the particular output port, transient downward changes in the priority of said highest congested emission priority; and

determining, for the particular output port, transient periods of no traffic congestion.

23. The method of claim 22, wherein the step of updating comprises the steps of:

filtering out, for the particular output port, transient downward changes in the priority of the respective highest congested emission priority;

filtering out, for the particular output port, transient periods of no traffic congestion; and

updating, for the particular output port, the respective count in dependence upon the filtered highest congested emission priority and filtered periods of traffic congestion.

24. The method of claim 23, wherein the method further comprises an initial step of:

storing at least one threshold for the particular output port, each of the thresholds corresponding to a bandwidth priority, and

wherein the step of determining, for the particular output port and for each emission. priority, the bandwidth priority of cells to discard further comprises the steps of;

comparing the count, for the particular output port, to the thresholds;

determining, for the particular port, the highest bandwidth priority corresponding to an exceeded threshold of the particular output port;

determining, for the particular output port, the bandwidth priority of cells to discard in dependence upon the highest bandwidth priority of the particular output port;

encoding, for the particular output port, the bandwidth priority of cells to discard into a flow control message indicating the loss priority and emission priority of cells to discard; and

sending the flow control message to the input ports.

25. The method of claim 24, wherein the step of determining, for the particular output port, the bandwidth priority of cells to discard, comprises the step of:

identifying, bandwidth priorities of cells to discard as being bandwidth priorities that are lower than the highest bandwidth priority of the particular output port and have an emission priority that is equal to or higher than said highest congested emission priority of the particular output port.

26. The method of claim 15, wherein the step of determining further comprises the step of:

determining, for the particular output port, the emission priority of cells to flow control in dependence upon the count associated with the particular output port; and

wherein the method further comprises the step of;

flow controlling, at the input ports, cells destined for the particular output port having an emission priority matching said emission priority of cells to flow control.