Methods and apparatus for multi-path flow control within a multi-stage switch fabric

• US 8,811,183 B1
• Filed: 10/04/2011
• Issued: 08/19/2014
• Est. Priority Date: 10/04/2011
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Bhalala, Hardik, Anand, Prashant
• Primary Examiner(s): Cheng, Peter
• Application Number:
  US13/252,615
• Time in Patent Office: 1,050 Days
• Field of Search: 370235-237, 370/360, 370367- 8, 370380- 8
• US Class Current: 370/237
• CPC Class Codes: H04L 41/0631 using root cause analysis; using analysis of correlation between notifications, alarms or events based on decision criteria, e.g. hierarchy, tree or time analysis
• CPC Class Codes: H04L 41/0681 Configuration of triggering conditions
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/127 by using congestion prediction
• CPC Class Codes: H04L 47/25 with rate being modified by the source upon detecting a change of network conditions
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/6205 Arrangements for avoiding head of line blocking
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/109 Integrated on microchip, e.g. switch-on-chip
• CPC Class Codes: H04L 49/111 Switch interfaces, e.g. port details
• CPC Class Codes: H04L 49/118 Address processing within a device, e.g. using internal ID or tags for routing within a switch
• CPC Class Codes: H04L 49/1507 Distribute and route fabrics, e.g. sorting-routing or Batcher-Banyan
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/25 : Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/251 : Cut-through or wormhole routing
• CPC Class Codes: H04L 49/253 : using establishment or release of connections between ports
• CPC Class Codes: H04L 49/254 : Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/505 : Corrective measures
• CPC Class Codes: H04W 28/02 : Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 28/0278 : using buffer status reports dynamic wireless traffic scheduling definition H04W72/12
• CPC Class Codes: H04W 28/12 : using signalling between network elements

Abstract

In some embodiments, an apparatus comprises a switch from a set of switches associated with a stage of a multi-stage switch fabric. The switch is configured to receive a data packet having a destination address of a destination device from a source device, and then store the data packet in a queue of the switch. The switch is configured to define a message based on the queue having an available capacity less than a threshold, and include a congestion root indicator in the message if the switch is a congestion root. The switch is then configured to send the message to the source device such that the source device sends another data packet having the destination address of the destination device to another switch from the set of switches and not to the previous switch if the message includes the congestion root indicator.

Claims

1. An apparatus, comprising:

a first switch from a plurality of switches associated with a stage of a switch fabric, the first switch configured to receive a first data packet having a destination address of a destination device from a source device, the first switch configured to store the first data packet in a queue,

the first switch configured to define a message based on the queue having an available capacity less than a threshold, the first switch configured to include a congestion root indicator in the message if the available capacity of the queue is decreasing and the first switch is sending data packets at substantially a maximum rate, the first switch is configured to not include the congestion root indicator in the message if the first switch is sending data packets at a rate substantially less than the maximum rate, the first switch configured to send the message to the source device such that the source device sends a second data packet having the destination address of the destination device to a second switch from the plurality of switches and not to the first switch from the plurality of switches if the message includes the congestion root indicator.

2. The apparatus of claim 1, wherein the first switch is configured to include a congestion victim indicator in the message if the available capacity of the queue is decreasing and the first switch is not sending data packets at substantially the maximum rate.

3. The apparatus of claim 1, wherein the first switch is configured to include a congestion victim indicator in the message if the available capacity of the queue is decreasing and the first switch is not sending data packets at substantially the maximum rate, the first switch configured to send the message to the source device such that the source device reduces a rate of data packets sent to the destination device in response to the message without sending any data packet having the destination address of the destination device to the second switch if the message includes the congestion victim indicator.

4. The apparatus of claim 1, wherein the first switch is configured to route the first data packet based on a hash function using a header of the first data packet as an input.

5. The apparatus of claim 1, wherein the first switch is configured to send the message to the source device such that the source device reduces a rate of data packets sent to the destination device in response to the message.

6. The apparatus of claim 1, wherein the first switch is configured to define the message such that the message includes at least one value associated with a header of the first data packet.

7. The apparatus of claim 1, wherein the first switch is configured to send the message to the source device such that the source device sends the second data packet to the second switch and not to the first switch without reducing a rate of data packets sent to the destination device in response to the message if the message includes the congestion root indicator.

8. A non-transitory processor-readable medium storing code representing instructions to be executed by a processor, the code comprising code to cause the processor to:

receive, at a switch within a switch fabric, a data packet associated with a data flow between a source device and a destination device;

store the data packet in a queue of the switch;

select the data packet from a plurality of data packets in the queue if an available capacity of the queue is less than a threshold;

define a message including at least a portion of a header of the data packet and an indicator of a flow control status of the switch, the indicator indicates that the switch is a congestion root if the available capacity of the queue is decreasing and the switch is sending data packets at substantially a maximum rate, the indicator indicates that the switch is a congestion victim and not a congestion root if the available capacity of the queue is decreasing and the switch is not sending data packets at substantially the maximum rate; and

send the message from the switch to the source device such that the source device modifies the data flow based on the at least the portion of the header of the data packet and the indicator of the flow control status of the switch.

9. The non-transitory processor-readable medium of claim 8, wherein the at least the portion of the header includes at least one value associated with the header of the data packet used by the switch to route the data packet.

10. The non-transitory processor-readable medium of claim 8, wherein the code to cause the processor to send the message includes code to cause the processor to send the message to the source device such that the source device reduces a rate associated with the data flow without modifying a data path through the switch fabric associated with the data flow based on the indicator of the flow control status identifying the switch as a congestion victim.

11. The non-transitory processor-readable medium of claim 8, wherein the code to cause the processor to send the message includes code to cause the processor to send the message to the source device such that the source device reduces a rate associated with the data flow in response to the message.

12. The non-transitory processor-readable medium of claim 8, wherein the code to cause the processor to send the message includes code to cause the processor to send the message to the source device such that the source device modifies a data path through the switch fabric associated with the data flow based on the indicator of the flow control status identifying the switch as a congestion root.

13. The non-transitory processor-readable medium of claim 8, wherein the code to cause the processor to send the message includes code to cause the processor to send the message to the source device such that the source device modifies a data path through the switch fabric associated with the data flow without reducing a rate associated with the data flow based on the indicator of the flow control status identifying the switch as a congestion root.

14. The non-transitory processor-readable medium of claim 8, wherein the data packet is a first data packet, the code to cause the processor to send the message includes code to cause the processor to send the message to the source device at a first time such that the source device is less likely to send a second data packet via the data flow at a second time after the first time than a third data packet via the data flow before the first time, based on the at least the portion of the header of the first data packet and the indicator of the flow control status of the switch.

15. An apparatus, comprising:

a source device configured to send a first data packet to a destination device via a multi-stage switch fabric having a plurality of switches associated with a stage of the multi-stage switch fabric, the source device configured to receive a message from a switch from the plurality of switches in response to the switch receiving the first data packet,

the source device configured to define a header of a second data packet to be sent to the destination device in response to the message such that the header of the second data packet is different than a header of the first data packet and the second data packet is configured to be more likely sent to the destination device via a remaining switch from the plurality of switches than the first data packet if the message indicates that a number of data packets in a queue at the switch is increasing and the switch is sending data packets at substantially a maximum rate.

16. The apparatus of claim 15, wherein the source device is configured to reduce a rate at which a plurality of data packets is sent to the destination device based on the message if the message indicates that the number of data packets in the queue at the switch is increasing and the switch is sending data packets at a rate substantially less than the maximum rate.

17. The apparatus of claim 15, wherein the source device is configured not to reduce a rate at which a plurality of data packets is sent to the destination device based on the message if the message indicates that the number of data packets in the queue at the switch is increasing and the switch is sending data packets at substantially the maximum rate.

18. The apparatus of claim 15, wherein the source device is configured to send the first data packet to the destination device via the switch fabric such that the switch from the plurality of switches switches the first data packet based on at least one hash function using a header of the first data packet as an input.

19. The apparatus of claim 15, wherein the message includes at least one value associated with a header of the first data packet.

20. The apparatus of claim 15, wherein the source device is configured to receive the message from the switch in response to the queue at the switch having an available capacity less than a predetermined threshold.