Methods and apparatus for flow control associated with a switch fabric

• US 9,660,940 B2
• Filed: 12/01/2010
• Issued: 05/23/2017
• Est. Priority Date: 12/01/2010
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Aybay, Gunes, Anand, Prashant, Bhalala, Hardik, Sarcar, Arijit
• Primary Examiner(s): SMITH, MARCUS
• Application Number:
  US12/957,472
• Publication Number:
  US 20120140626A1
• Time in Patent Office: 2,365 Days
• 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 processor configured to be operatively coupled to a memory and that is configured to execute a flow control module; and

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

the flow control module configured to (1) stop receiving the first plurality of sample data packets from the output queue of the stage of the multi-stage switch at the first sample rate and (2) receive a second plurality of sample data packets from the output queue of the stage of the multi-stage switch at a second sample rate greater than the first sample rate, when the available capacity of the output queue crosses a second threshold,

the available capacity of the output queue being greater at the first threshold than at the 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 plurality of sample data packets or the second plurality of sample data packets entered the multi-stage switch, the flow control signal being an out-of-band flow control signal.

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 plurality of sample data packets at the first sample 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 signal is a first control signal, and

the flow control module is configured to send the first flow control signal to the edge device using a first flow control protocol such that the edge device sends a second flow control signal to a peripheral processing device from which the first plurality of sample data packets or the second plurality of sample data packets originated using a second flow control protocol.

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

7. An apparatus, comprising:

a first switch module configured to be included in 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,

if an available capacity of the output queue crosses a threshold, and in response to a data packet request received at the first switch module from an out-of-band flow control module, the first switch module configured to send a data packet in the output queue to the out-of-band flow control module such that the out-of-band flow control module sends a first out-of-band flow control signal to a source edge device associated with the data packet using a first flow control protocol and 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,

the first switch module configured to select the data packet in the output queue based on a time at which the first switch module receives the data packet request from the out-of-band flow control module.

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

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

10. The apparatus of claim 7, wherein the distributed switch fabric is a Clos network.

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

12. 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 operatively coupled to the source edge device using a second flow control protocol, the first flow control signal being an out-of-band flow control signal.

13. The non-transitory processor-readable medium of claim 12, 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.

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

15. The non-transitory processor-readable medium of claim 12, 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.

16. The non-transitory processor-readable medium of claim 12, 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.

17. The non-transitory processor-readable medium of claim 12, 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.

18. The non-transitory processor-readable medium of claim 12, 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.