METHODS AND APPARATUS FOR FLOW CONTROL ASSOCIATED WITH A SWITCH FABRIC

• US 20120140626A1
• Filed: 12/01/2010
• Published: 06/07/2012
• Est. Priority Date: 12/01/2010
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Aybay, Gunes, Sarcar, Arijit, Anand, Prashant, Bhalala, Hardik
• Granted Patent: US 9,660,940 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/506 Backpressure

Abstract

In some embodiments, an apparatus includes a flow control module configured to receive a first data packet from an output queue of a stage of a multi-stage switch at a first rate when an available capacity of the output queue crosses a first threshold. The flow control module is configured to receive a second data packet from the output queue of the stage of the multi-stage switch at a second rate when the available capacity of the output queue crosses a second threshold. The flow control module configured to send a flow control signal to an edge device of the multi-stage switch from which the first data packet or the second data packet entered the multi-stage switch.

Claims

1. An apparatus, comprising:

a flow control module configured to receive a first data packet from an output queue of a stage of a multi-stage switch at a first rate when an available capacity of the output queue crosses a first threshold,

the flow control module configured to receive a second data packet from the output queue of the stage of the multi-stage switch at a second rate when the available capacity of the output queue crosses a second threshold, the flow control module configured to send a flow control signal to an edge device of the multi-stage switch from which the first data packet or the second data packet entered the multi-stage switch.

2. The apparatus of claim 1, wherein the flow control module is separate from a data flow of the multi-stage switch.

3. The apparatus of claim 1, wherein the flow control module is configured to randomly receive the first data packet at the first rate when the available capacity of the output queue crosses the first threshold.

4. The apparatus of claim 1, wherein the flow control module is configured to periodically monitor the available capacity of the output queue.

5. The apparatus of claim 1, wherein the flow control module is configured to send the flow control signal to the edge device using a first flow control protocol such that the edge device sends a flow control signal to a peripheral processing device from which the first data packet or the second data packet originated using a second flow control protocol.

6. The apparatus of claim 1, wherein the available capacity of the output queue is greater at the first threshold than at the second threshold, the second rate being greater than the first rate.

7. The apparatus of claim 1, wherein the multi-stage switch is a Clos network.

8. An apparatus, comprising:

a first switch module of a distributed switch fabric, the first switch module configured to receive a plurality of data packets from a plurality of second switch modules of the distributed switch fabric and store the plurality of data packets in an output queue, the first switch module configured to send a data packet in the output queue to an out-of-band flow control module if an available capacity of the output queue crosses a threshold such that the out-of-band flow control module sends a flow control signal to a source edge device associated with the data packet.

9. The apparatus of claim 8, wherein the first switch module is configured to randomly select the data packet from the data packets in the output queue.

10. The apparatus of claim 8, wherein the first switch module is configured to select the data packet in the output queue based on a time at which the first switch module receives a signal from the out-of-band flow control module.

11. The apparatus of claim 8, wherein the first switch module is configured to receive the data packet substantially immediately after the first switch module receives a request for a data packet from the out-of-band flow control module.

12. The apparatus of claim 8, wherein the distributed switch fabric is a Clos network.

13. The apparatus of claim 8, wherein the first switch module is configured to send the out-of-band flow control module a signal when the available capacity of the output queue crosses the threshold.

14. The apparatus of claim 8, wherein the flow control signal is a first flow control signal, the out-of-band flow control module is configured to send the first flow control signal to the source edge device using a first flow control protocol such that the source edge device sends a second flow control signal to a source peripheral processing device associated with the data packet using a second flow control protocol.

15. A non-transitory processor-readable medium storing code representing instructions to cause a processor to:

receive an indicator of an available capacity of an output queue of a stage of a multi-stage switch;

send a request for a data packet within the output queue if the indicator of the available capacity of the output queue satisfies a condition; and

send a first flow control signal to a source edge device of the data packet using a first flow control protocol such that the source edge device sends a second flow control signal to a source peripheral processing device using a second flow control protocol.

16. The non-transitory processor-readable medium of claim 15, wherein the indicator of the available capacity of the output queue satisfies the condition if an available capacity of the output queue is less than a predetermined threshold.

17. The non-transitory processor-readable medium of claim 15, wherein the multi-stage switch is a Clos network.

18. The non-transitory processor-readable medium of claim 15, wherein the request for the data packet is a request for a randomly selected data packet from a plurality of data packets within the output queue.

19. The non-transitory processor-readable medium of claim 15, wherein the data packet is a first data packet, the non-transitory processor-readable medium further comprising code representing instructions to cause the processor to:

send a request for a second data packet within the output queue a predetermined period of time after sending the request for the first data packet.

20. The non-transitory processor-readable medium of claim 15, wherein the data packet is a first data packet, the condition is a first condition, the non-transitory processor-readable medium further comprising code representing instructions to cause the processor to:

send a request for a second data packet within the output queue a first predetermined period of time after sending the request for the first data packet if the first condition is satisfied the first predetermined time after sending the request for the first data packet; and

send a request for a third data packet within the output queue a second predetermined period of time after sending the request for the first data packet if a second condition is satisfied the second predetermined period of time after sending the request for the first data packet.

21. The non-transitory processor-readable medium of claim 15, further comprising code representing instructions to cause the processor to:

receive the data packet from the stage of the multi-stage switch; and

parse the data packet to identify an identifier of the source edge device of the data packet.