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

• US 9,426,085 B1
• Filed: 08/06/2014
• Issued: 08/23/2016
• Est. Priority Date: 10/04/2011
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Anand, Prashant, Bhalala, Hardik
• Primary Examiner(s): Cheng, Peter
• Application Number:
  US14/453,250
• Time in Patent Office: 748 Days
• Field of Search: 370235-237, 370/360, 370367- 8, 370380- 8
• US Class Current: 1/1
• 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 associated with a stage of a switch fabric, the first switch configured to receive a first data unit having a destination address of a destination device from a source device, the first switch configured to store the first data unit in a queue,

the first switch configured to define a message when an available capacity of the queue falls below a predetermined capacity threshold,

the first switch configured to include a congestion root indicator in the message, the congestion root indicator indicating that the first switch is a congestion root, when the available capacity of the queue is decreasing and the first switch is sending data units substantially at a maximum rate,

the first switch configured to include a congestion victim indicator in the message, the congestion victim indicator indicating that the first switch is a victim of congestion, when the available capacity of the queue is decreasing and the first switch is sending data units at a rate below the maximum rate,

the first switch configured to send the message to the source device such that (1) the source device sends a second data packet having the destination address of the destination device to a second switch associated with the stage of the switch fabric and not to the first switch when the message includes the congestion root indicator, and (2) the source device reduces a data rate at which data packets of a data flow associated with the destination address are sent from the source device when the message includes the congestion victim indicator.

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

3. 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 unit.

4. The apparatus of claim 1, wherein the source device is an edge device of the switch fabric.

5. The apparatus of claim 1, wherein the destination device is an edge device of the switch fabric.

6. An apparatus, comprising:

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

the switch configured to define a message when an available capacity of the queue falls below a predetermined capacity threshold,

the switch configured to include a congestion victim indicator indicating that the first switch is a congestion victim, in the message when a rate at which the switch sends data units is below a maximum rate,

the switch configured to include a congestion root indicator indicating that the first switch is a congestion root, in the message when the rate at which the switch sends data units is equivalent to or above the maximum rate;

the switch configured to send the message to the source device such that the source device reduces a rate of data units sent to the destination device in response to the message without sending any data unit having the destination address of the destination device to an alternative switch when the message includes the congestion victim indicator.

7. The apparatus of claim 6, wherein the switch is configured to route the data unit based on a hash function using a header of the data unit as an input.

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

9. The apparatus of claim 6, wherein the source device is an edge device of the switch fabric.

10. The apparatus of claim 6, wherein the destination device is an edge device of the switch fabric.

11. 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, from a source device and at a switch from a plurality of switches associated with a stage of a switch fabric, a first data unit having a destination address of a destination device;

store the first data unit in a queue;

define a message when an available capacity of the queue falls below a predetermined capacity′

threshold, the message defined to include a congestion status indicator in the message based at least in part on a rate at which the switch sends data units, the congestion status indicator being a congestion root indicator indicating that the switch from the plurality of switches is a congestion root when the switch is sending data units substantially at a maximum rate, the congestion status indicator being a congestion victim indicator indicating that the switch from the plurality of switches is a congestion victim when the switch is sending data units at a rate below the maximum rate; and

send the message to the source device such that the source device (1) modifies a header of a second data unit associated with a data flow associated with the switch when the message includes the congestion root indicator, and (2) reduces a data rate at which data packets of a data flow associated with the destination address are sent from the source device when the message includes the congestion victim indicator.

12. The non-transitory processor-readable medium of claim 11, wherein the switch is a first switch from the plurality of switches,

the code to cause the processor to send includes code to cause the processor to send the message to the source device such that the source device sends to a second switch from the plurality of switches and not to the first switch from the plurality of switches when the congestion status indicator is the congestion root indicator.

13. The non-transitory processor-readable medium of claim 11, wherein

the code to cause the processor to send includes code to cause the processor to send the message to the source device such that the source device reduces a rate of data units sent to the destination device in response to the message without sending any data unit having the destination address of the destination device to an alternative switch when the congestion status indicator is the congestion victim indicator.

14. The non-transitory processor-readable medium of claim 11, the code further comprising code to cause the processor to:

route the first data unit based on a hash function using a header of the first data unit as an input.

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

define the message such that the message includes at least one value associated with a header of the first data unit.

16. The non-transitory processor-readable medium of claim 11, wherein the source device is an edge device of the switch fabric.