BACKPRESSURE MECHANISM FOR SWITCHING FABRIC
First Claim
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.
8 Assignments
0 Petitions
Accused Products
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.
164 Citations
27 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. - View Dependent Claims (2, 3, 4, 5)
-
- 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.
-
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. - View Dependent Claims (9, 10, 11, 12)
-
-
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. - View Dependent Claims (15, 16, 17, 18, 19)
-
- 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.
-
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. - View Dependent Claims (23)
-
-
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. - View Dependent Claims (25, 26)
-
-
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.
-
Specification