DATA SWITCHING FLOW CONTROL WITH VIRTUAL OUTPUT QUEUING

• US 20090003212A1
• Filed: 06/23/2008
• Published: 01/01/2009
• Est. Priority Date: 06/22/2007
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Kwan, Bruce, Agarwal, Puneet
• Granted Patent: US 8,331,387 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/508 Head of Line Blocking Avoidance

Abstract

Methods and apparatus for data switching are disclosed. An example method includes receiving a data traffic flow at a data ingress module and buffering the data traffic flow in a virtual output queue included in the data ingress module, where the virtual output queue being associated with a data egress module. The example method also includes communicating the data traffic flow to the data egress module via a fabric egress queue included in a data-switch fabric. The example method further includes monitoring data occupancy in the fabric egress queue and determining, based on the data occupancy, that a change in congestion state in the fabric egress queue has occurred. The example method still further includes, in response to the change in congestion state, communicating a flow control message to the data ingress module and, in response to the flow control message, modifying communication of the data traffic flow.

Claims

1. An apparatus comprising:

a plurality of data ingress modules;

a data-switch fabric operationally coupled with the plurality of data ingress modules; and

a plurality of data egress modules operationally coupled with the data-switch fabric,

wherein;

each of the plurality of data ingress modules includes a set of virtual output queues, each of the virtual output queues corresponding with a respective data egress module; and

the data-switch fabric includes;

a plurality of fabric ingress ports; and

a plurality of fabric egress ports each including a set of fabric egress queues, each set of fabric egress queues being respectively associated with one of the data egress modules, each fabric egress queue corresponding with a respective data ingress module;

the data-switch fabric being configured to;

monitor an amount of data buffered in each of the fabric egress queues;

determine a change in a congestion state for one or more of the fabric egress queues; and

send a flow control message to a data ingress module corresponding with the change in congestion state; and

the data ingress modules being configured to receive and route data traffic to the respective data egress modules via the virtual output queues and the data-switch fabric in accordance with the flow control message.

2. The apparatus of claim 1, wherein the data-switch fabric comprises a plurality of fabric elements, each of the fabric elements being operationally coupled with each of the data egress modules via one or more respective fabric egress ports and operationally coupled with each of the data ingress modules via one or more respective fabric ingress ports.

3. The apparatus of claim 1, wherein each set of virtual output queues includes:

a unicast data virtual output queue corresponding with each of the data egress modules; and

a multicast data virtual output queue.

4. The apparatus of claim 1, wherein each data ingress module includes a plurality of sets of virtual output queues associated with each data egress module, each set of virtual output queues corresponding with a data traffic class of service.

5. The apparatus of claim 1, wherein each set of virtual output queues includes:

a unicast data virtual output queue corresponding with each of the data egress modules; and

a multicast data virtual output queue,

the apparatus further comprising;

a first scheduler configured to schedule transmission of unicast data from the unicast data virtual output queues in accordance with a bandwidth allocation policy; and

a second scheduler configured to schedule transmission of the unicast data and multicast data in accordance with the bandwidth allocation policy.

6. The apparatus of claim 1, wherein:

each data ingress module includes a plurality of sets of virtual output queues associated with each data egress module, each set of virtual output queues corresponding with a respective data traffic class of service, and

each set of virtual output queues includes;

a unicast data virtual output queue corresponding with each of the data egress modules; and

a multicast data virtual output queue.

7. The apparatus of claim 6, wherein each data ingress module further comprises:

for each set of virtual output queues;

a first scheduler configured to schedule transmission of unicast data from the unicast data virtual output queues in accordance with a bandwidth allocation policy; and

a second scheduler configured to schedule transmission of the unicast data and multicast data in accordance with the bandwidth allocation policy; and

a third scheduler configured to schedule transmission of data for each data traffic class of service in accordance with the bandwidth allocation policy.

8. The apparatus of claim 1, wherein the one or more data queues corresponding with each data ingress module of each set of fabric egress queues includes a unicast data queue and a multicast data queue.

9. The apparatus of claim 1, wherein each set of fabric egress queues includes multiple sets of fabric egress queues, each of the multiple sets being associated with a respective data traffic class of service.

10. The apparatus of claim 1, wherein the flow control message includes:

an indication of the change in congestion state;

an indication of a data traffic class of service associated with the change in congestion state;

an indication of whether unicast or multicast data is associated with the change in congestion state; and

an identifier of a fabric egress module destination associated with the change in congestion state.

11. The apparatus of claim 1, wherein, in response to the flow control message, the data ingress modules are configured to:

in the event the flow control message indicates that data occupancy in a fabric egress queue has exceeded a first threshold, stop communicating data from a virtual output queue associated with the change in congestion state; and

in the event the flow control message indicates that data occupancy in a previously congested fabric egress queue has been reduced below a second threshold, resume communicating data from a virtual output queue associated with the change in congestion state.

12. The apparatus of claim 1, wherein, in response to the flow control message, the data ingress modules are configured to:

in the event the flow control message indicates that data occupancy in a fabric egress queue has exceeded a first threshold, reduce a data rate for data communicated from a virtual output queue associated with the change in congestion state;

in the event the flow control message indicates that data occupancy in a fabric egress queue has exceeded a second threshold, stop communicating data from a virtual output queue associated with the change in congestion state; and

in the event the flow control message indicates that the data occupancy in a previously congested fabric egress queue has been reduced below a third threshold, resume communicating data from a virtual output queue associated with the change in congestion state at a normal data rate.

13. A method comprising:

receiving a data traffic flow at a data ingress module;

buffering the data traffic flow in a virtual output queue included in the data ingress module, the virtual output queue being associated with a data egress module;

communicating the data traffic flow to the data egress module via a fabric egress queue included in a data-switch fabric;

monitoring data occupancy in the fabric egress queue;

determining, based on the data occupancy, that a change in congestion state in the fabric egress queue has occurred;

in response to the change in congestion state, communicating a flow control message to the data ingress module; and

in response to the flow control message, modifying communication of the data traffic flow.

14. The method of claim 13, wherein:

determining the change in congestion state comprises determining that data occupancy in the fabric egress queue has exceeded a first threshold; and

modifying communication of the data traffic flow comprises stopping communication of the data traffic flow.

15. The method of claim 14, wherein:

determining the change in congestion state comprises determining that data occupancy in the fabric egress queue has fallen below a second threshold, the second threshold being lower than the first threshold; and

modifying communication of the data traffic flow comprises resuming communication of the data traffic flow.

16. The method of claim 13, wherein the flow control message includes:

an indication of the change in congestion state; and

an indication of the fabric egress module.

17. A method comprising:

receiving a first data traffic flow at a first data ingress module;

buffering the first data traffic flow in a first virtual output queue included in the first data ingress module, the first virtual output queue being associated with a first data egress module;

receiving a second data traffic flow at a second data ingress module;

buffering the second data traffic flow in a second virtual output queue included in the second data ingress module, the second virtual output queue being associated with the first data egress module;

receiving a third data traffic flow at the second data ingress module;

buffering the third data traffic flow in a third virtual output queue included in the second data ingress module, the third virtual output queue being associated with a second data egress module;

communicating the first data traffic flow to the first data egress module via a first fabric egress queue included in a data-switch fabric;

communicating the second data traffic flow to the first data egress module via the first fabric egress queue;

communicating the third data traffic flow to the second fabric egress module via a second fabric egress queue included in the data-switch fabric;

monitoring data occupancy in the first and second fabric egress queues;

determining that data occupancy in the first fabric egress queue has exceeded a first threshold;

in response to the data occupancy in the first fabric egress queue exceeding the first threshold, communicating a flow control message to at least one of the first data ingress module and the second data ingress module; and

in response to the flow control message, stopping communication of at least one of the first data flow and the second data flow.

18. The method of claim 17, wherein:

the first data flow is associated with a first data traffic class of service;

the second data flow is associated with a second data traffic class of service;

the first data traffic class of service has a higher transmission priority than the second data traffic class of service;

communicating the flow control message includes only communicating the flow control message to the second data ingress module; and

stopping communication includes only stopping communication of the second data traffic flow.

19. The method of claim 18, wherein the second data traffic flow comprises a best effort class of service data traffic flow.

20. The method of claim 17, wherein the flow control message includes:

an indication of the change in congestion state;

an indication of a data traffic class of service associated with the change in congestion state;

an indication of whether unicast or multicast data is associated with the change in congestion state; and

an identifier of a fabric egress module destination associated with the change in congestion state.