CONGESTION-AWARE LOAD BALANCING IN DATA CENTER NETWORKS

• US 20170295101A1
• Filed: 04/11/2017
• Published: 10/12/2017
• Est. Priority Date: 04/12/2016
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: HIRA, Mukesh, KATTA, Naga
• Granted Patent: US 11,777,853 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 47/115 using a dedicated packet
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

Example methods are provided for a first switch to perform congestion-aware load balancing in a data center network. The method may comprise: receiving probe packets from multiple next-hop second switches that connect the first switch with a third switch via multiple paths. The method may also comprise: processing congestion state information in each probe packet to select a selected next-hop second switch from the multiple next-hop second switches, the selected next-hop second switch being associated with a least congested path from the first switch to the third switch. The method may further comprise: in response to receiving data packets from a fourth switch that are destined for a destination connected with the third switch, sending the data packets to the selected next-hop second switch such that the data packets travel to the third switch along the least congested path.

Claims

1. A method for a first switch to perform congestion-aware load balancing in a data center network that includes the first switch, multiple next-hop second switches, a third switch and a fourth switch, the method comprising:

receiving probe packets from the multiple next-hop second switches that connect the first switch with the third switch via multiple paths, wherein each probe packet identifies the third switch and includes congestion state information associated with one of the multiple paths to the third switch;

processing the congestion state information in each probe packet to select a selected next-hop second switch from the multiple next-hop second switches, wherein the selected next-hop second switch is associated with a least congested path from the first switch to the third switch; and

in response to receiving data packets from the fourth switch that are destined for a destination connected with the third switch, sending the data packets to the selected next-hop second switch such that the data packets travel to the third switch along the least congested path.

2. The method of claim 1, wherein receiving the probe packets comprises:

receiving the probe packets that each include congestion state information of a least congested path from the one of the multiple next-hop second switches to the third switch.

3. The method of claim 2, wherein receiving the probe packets comprises:

receiving the probe packets that each include congestion state information specifying a maximum link utilization level along the least congested path from the one of the multiple next-hop second switches to the third switch.

4. The method of claim 1, wherein processing the congestion state information comprises:

selecting the selected next-hop second switch based on a first comparison to determine which of the following indicates a higher level of congestion;

(a) the congestion state information in a particular probe packet from the selected next-hop second switch, and (b) local congestion state information associated with an ingress port via which the particular probe packet is received from the selected next-hop second switch.

5. The method of claim 4, wherein processing the congestion state information comprises:

selecting the selected next-hop second switch based on a second comparison to determine which of the following indicates a lower level of congestion;

(a) a result of the first comparison, and (b) congestion state information associated with a current next-hop second switch to the third switch.

6. The method of claim 1, wherein processing the congestion state information comprises:

selecting the selected next-hop second switch based on a time elapsed since a current next-hop second switch was selected for the third switch exceeds a predetermined threshold.

7. The method of claim 1, wherein the method further comprises:

sending a probe packet to the third switch, wherein the probe packet identifies the third switch and includes congestion state information associated with the least congested path from the first switch to the third switch.

8. The method of claim 7, wherein the method further comprises:

determining to send the probe packet to the third switch based on a time elapsed since the first switch sends a previous probe packet associated with the third switch exceeds a predetermined threshold.

9. The method of claim 1, wherein sending the data packets comprises:

assigning each of the data packets, being a current data packet, to a new flowlet or current flowlet based on an inter-packet gap between the current data packet and a previous data packet associated with a same communication flow.

10. The method of claim 9, wherein sending the data packets comprises:

in response to determination that the current data packet is assigned to a new flowlet, storing flowlet information that associates the selected next-hop second switch with the new flowlet;

otherwise, retrieving the selected next-hop second switch associated with the current flowlet.

11. A first switch configured to perform congestion-aware load balancing in a data center network that includes the first switch, multiple next-hop second switches, a third switch and a fourth switch, wherein the first switch comprises:

first ports to receive probe packets from the respective multiple next-hop second switches that connect the first switch with the third switch via multiple paths, each probe packet identifying the third switch and includes congestion state information associated with one of the multiple paths to the third switch;

a second port to receive data packets from the fourth switch that are destined for a destination connected with the third switch; and

a switch logic configured to;

in response to receiving the probe packets via the first ports, process the congestion state information in each probe packet to select a selected next-hop second switch from the multiple next-hop second switches, wherein the selected next-hop second switch is associated with a least congested path from the first switch to the third switch; and

in response to receiving the data packets via the second port, send the data packets to the selected next-hop second switch such that the data packets travel to the third switch along the least congested path.

12. The switch of claim 11, wherein the first ports are configured to:

receive the probe packets that each include congestion state information of a least congested path from the one of the multiple next-hop second switches to the third switch.

13. The switch of claim 12, wherein the first ports are configured to:

receive the probe packets that each include congestion state information specifying a maximum link utilization level along the least congested path from the one of the multiple next-hop second switches to the third switch.

14. The switch of claim 11, wherein the switch logic is configured to process the congestion state information by selecting the selected next-hop second switch based on a first comparison to determine which of the following indicates a higher level of congestion:

(a) the congestion state information in a particular probe packet from the selected next-hop second switch, and (b) local congestion state information associated with an ingress port via which the particular probe packet is received from the selected next-hop second switch.

15. The switch of claim 14, wherein the switch logic is configured to process the congestion state information by selecting the selected next-hop second switch based on a second comparison to determine which of the following indicates a lower level of congestion:

(a) a result of the first comparison, and (b) congestion state information associated with a current next-hop second switch to the third switch.

16. The switch of claim 11, wherein the switch logic is configured to process the congestion state information by selecting the selected next-hop second switch based on a time elapsed since a current next-hop second switch was selected for the third switch exceeds a predetermined threshold.

17. The switch of claim 11, wherein the switch logic is further configured to:

send a probe packet to the third switch, wherein the probe packet identifies the third switch and includes congestion state information associated with the least congested path from the first switch to the third switch.

18. The switch of claim 17, wherein the switch logic is further configured to:

determine to send the probe packet to the third switch based on a time elapsed since the first switch sends a previous probe packet associated with the third switch exceeds a predetermined threshold.

19. The switch of claim 11, wherein the switch logic is configured to send the data packets by assigning each of the data packets, being a current data packet, to a new flowlet or current flowlet based on an inter-packet gap between the current data packet and a previous data packet associated with a same communication flow.

20. The switch of claim 19, wherein the switch logic is configured to send the data packets by, in response to determination that the current data packet is assigned to a new flowlet, storing flowlet information that associates the selected next-hop second switch with the new flowlet;

otherwise, retrieving the selected next-hop second switch associated with the current flowlet.