BACKPRESSURE MECHANISM FOR SWITCHING FABRIC

• US 20080212472A1
• Filed: 05/14/2008
• Published: 09/04/2008
• Est. Priority Date: 03/06/2002
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Agere Systems Incorporated (Broadcom, Inc.)
• Inventors: Agarwal, Gaurav, Mo, Jeonghoon, Parekh, Shyam P., Walrand, Jean, Musacchio, John T., Myers, Roy T.
• Granted Patent: US 7,983,287 B2
• Time in Patent Office: Days
• US Class Current: 370/232
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/3072 Packet splitting
• CPC Class Codes: H04Q 3/68 Grouping or interlacing selector groups or stages

Abstract

Roughly described, a packet switching fabric contains a separate queue scheduler for each combination of an input module and a fabric output port. The schedulers may also be specific to a single class of service. Each queue scheduler schedules its packets without regard to state of other input queues and without regard to packets destined for other output ports. In an aspect, the fabric manages per-flow bandwidth utilization of output port bandwidth capacity by monitoring the same and asserting backpressure toward the queue scheduler for any thread that is exceeding its bandwidth allocation. In another aspect, a switching fabric uses leaky buckets to apply backpressure in response to overutilization of downstream port capacity by particular subflows. In another aspect, a switching fabric includes a cascaded backpressure scheme.

Claims

1. Switching apparatus comprising:

an output port;

a plurality of sets of input queues, at least one of said sets having more than one of said input queues; and

a queue scheduler corresponding to each of said sets of input queues, each given one of said queue schedulers operable to schedule packets for transmission toward said output port from among the input queues in the set corresponding to the given scheduler, in dependence upon the states of input queues in the set corresponding to the given scheduler and without regard to state of the input queues in any others of said sets.

2. Apparatus according to claim 1, wherein each of said sets of input queues is disposed on a separate input module, and the queue scheduler corresponding to each of said sets of input queues is disposed on the same module as its input queues.

3. Apparatus according to claim 1, wherein a particular one of said queue schedulers is responsive to a backpressure signal that is specific to a particular subset of less than all of the input queues from which the particular scheduler schedules packets for transmission toward said output port, said particular scheduler operable to schedule packets for transmission toward said output port from among only those (if any) of its input queues that are not subject to said backpressure signal.

4. Apparatus according to claim 3, wherein said particular subset contains only one input queue.

5. Apparatus according to claim 1, comprising an input stage, an intermediate stage and an output stage, said input queues being disposed in said input stage and said output port being disposed in said output stage, said intermediate stage having a plurality of alternative routes via which packets from each of said input queues can be forwarded toward said output port.

6. A method of switching packets from a plurality of sets of input queues toward an output port, at least one of said sets of input queues having more than one of said input queues, comprising the step of scheduling packets for transmission toward said output port from each of said sets of input queues without consideration of the scheduling of packets for transmission toward said output port from the others of said sets of input queues.

7. A method according to claim 6, wherein said step of scheduling packets is responsive to a backpressure signal that is specific to a particular subset of at least one and less than all of the input queues in a particular one of said sets of input queues,

and wherein said step of scheduling packets withholds the scheduling of any packets destined for said output port from the input queues that are subject to one of said backpressure signals while said one backpressure signal is asserted.

8. Switching apparatus comprising:

a plurality of sets of output ports;

a plurality of input queues operable to store incoming packets destined for said output ports; and

a queue scheduler corresponding to each of said sets of output ports, each given one of said queue schedulers operable to schedule only those packets in said input queues which are destined for the output ports in the set corresponding to the given queue scheduler, and to do so without regard to packets destined for other output ports.

9. Apparatus according to claim 8, wherein each of said sets of output ports contains exactly one output port.

10. Apparatus according to claim 8, wherein said given queue scheduler is responsive to a backpressure signal that is specific to a particular subset of less than all of said input queues, said given queue scheduler operable to schedule packets for transmission from among only those (if any) of said input queues that are not subject to said backpressure signal.

11. Apparatus according to claim 10, wherein said particular subset contains exactly one input queue and the set of output ports corresponding to said given queue scheduler contains exactly one output port.

12. Apparatus according to claim 8, comprising an input stage, an intermediate stage and an output stage, said input queues being disposed in said input stage and said output ports being disposed in said output stage, said intermediate stage having a plurality of alternative routes via which packets from each of said input queues can be forwarded toward said output ports.

13. A method for switching packets toward a plurality of sets of output ports from a plurality of input queues operable to store incoming packets destined for said output ports, comprising the step of scheduling those packets in said input queues which are destined for each of said output ports without consideration of the scheduling of packets in said input queues which are destined for the others of said sets of output ports.

14. Switching apparatus comprising:

a plurality of sets of output ports;

a plurality of sets of input queues, at least one of said sets of input queues having more than one of said input queues; and

a queue scheduler corresponding to each pair of one of said sets of input queues and one of said sets of output ports, each given one of said queue schedulers operable to schedule packets for transmission toward its corresponding set of output ports from among the input queues in its corresponding set of input queues, in dependence upon the states of input queues in its corresponding set of input queues, without regard to state of the input queues in any others of said sets, and without regard to packets destined for other output ports.

15. Apparatus according to claim 14, wherein each of said sets of output ports contains exactly one output port.

16. Apparatus according to claim 14, wherein each of said sets of input queues is disposed on a separate input module, and the queue scheduler corresponding to each of said sets of input queues is disposed on the same module as its input queues.

17. Apparatus according to claim 14, wherein a particular one of said queue schedulers is responsive to a backpressure signal that is specific to a particular subset of less than all of the input queues from among which the particular scheduler schedules packets for transmission toward its corresponding set of output ports, said particular scheduler operable to schedule packets for transmission toward its corresponding set of output ports from among only those (if any) of its input queues that are not subject to said backpressure signal.

18. Apparatus according to claim 17, wherein said particular subset of input queues contains only one input queue.

19. Apparatus according to claim 14, comprising an input stage, an intermediate stage and an output stage, said input queues being disposed in said input stage and said output ports being disposed in said output stage, said intermediate stage having a plurality of alternative routes via which packets from each of said input queues can be forwarded toward each of said output ports.

20. A method for switching packets toward a plurality of output ports from a plurality of sets of input queues, at least one of said sets of input queues having more than one of said input queues, comprising the step of scheduling packets for transmission toward each of said output ports from each one of said sets of input queues, independently of the scheduling of packets for transmission toward the others of said output ports and independently of the scheduling of packets from the others of said sets of input ports.

21. A method according to claim 20, wherein said step of scheduling packets is responsive to backpressure signals that are specific to one of said output ports and a subset of at least one and less than all of the input queues in one of said sets of input queues,

and wherein in response to assertion of a particular one of said backpressure signals, said particular backpressure signal being specific to a particular one of said output ports and a particular subset of at least one and less than all of the input queues in a particular one of said sets of input queues, said step of scheduling packets withholds the scheduling of any packets destined for said particular output port from said particular subset of input queues.

22. Switching apparatus comprising:

an input stage having a plurality of sets of input queues;

an output stage having a plurality of output ports;

an intermediate stage having a plurality of alternative routes via which packets from each of said input queues can be forwarded toward each of said output ports; and

a queue scheduler corresponding to each pair of one of said sets of input queues and one of said output ports, each given one of said queue schedulers operable to schedule packets for transmission toward its corresponding output port from among only the input queues in its corresponding set of input queues, and operable to do so in dependence upon the states of input queues in its corresponding set of input queues, without regard to state of the input queues in any others of said sets, and without regard to packets destined for other output ports.

23. Apparatus according to claim 22, wherein each particular one of said queue schedulers is responsive to a respective backpressure signal indicating overutilization of bandwidth capacity of the output port toward which the particular queue scheduler schedules packets for transmission, the backpressure signals being specific to a particular subset of less than all of the input queues from among which the particular scheduler schedules packets, the particular scheduler being operable to schedule packets for transmission toward its corresponding output port from among only those (if any) of its input queues that are not subject to said backpressure signal.

24. A multi-stage switch fabric (e.g., 100) comprising:

an input stage (e.g., 110) having a plurality of input modules (e.g., 116);

an intermediate stage (e.g., 112) connected to the input stage and having a plurality of intermediate modules (e.g., 118); and

an output stage (e.g., 114) connected to the intermediate stage and having a plurality of output modules (e.g., 120), each output module has one or more output ports (e.g., 730, 732), wherein the multi-stage switch fabric has;

one or more per-microbundle monitors (e.g., 746, 748), each adapted to monitor a microbundle flow of a corresponding output port and assert microbundle backpressure signals for the microbundle flow, each microbundle flow having a plurality of threads; and

one or more per-thread monitors (e.g., 750), each adapted to monitor a different thread and assert thread backpressure signals for the thread.

25. The multi-stage switch fabric of claim 24, wherein each per-microbundle monitor is implemented outside of the output stage.

26. The multi-stage switch fabric of claim 25, wherein each per-microbundle monitor is implemented in the intermediate stage.

27. A multi-stage switch fabric (e.g., 100) comprising:

an input stage (e.g., 110) having a plurality of input modules (e.g., 116);

an intermediate stage (e.g., 112) connected to the input stage and having a plurality of intermediate modules (e.g., 118); and

an output stage (e.g., 114) connected to the intermediate stage and having a plurality of output modules (e.g., 120), each output module has one or more output ports (e.g., 730, 732), wherein the multi-stage switch fabric has;

one or more microbundle leaky buckets (e.g., uB-VLBs), each adapted to monitor a microbundle flow of a corresponding output port, each microbundle flow having a plurality of threads; and

one or more thread leaky buckets (e.g., 926), each adapted to monitor a different thread.