DYNAMICALLY ADJUSTING LOAD BALANCING

• US 20160094642A1
• Filed: 12/01/2014
• Published: 03/31/2016
• Est. Priority Date: 09/30/2014
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Jain, Jayant, Sengupta, Anirban, Parthasarathy, Mohan, Sequeira, Allwyn, Maskalik, Serge, Lund, Rick
• Granted Patent: US 10,257,095 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: H04L 2101/622 Layer-2 addresses, e.g. medium access control [MAC] addresses
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 61/2521 Translation architectures other than single NAT servers
• CPC Class Codes: H04L 61/5069 for group communication, multicast communication or broadcast communication
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1017 based on a round robin mechanism
• CPC Class Codes: H04L 67/1025 Dynamic adaptation of the criteria on which the server selection is based
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer

Abstract

Some embodiments provide a novel method for load balancing data messages that are sent by a source compute node (SCN) to one or more different groups of destination compute nodes (DCNs). In some embodiments, the method deploys a load balancer in the source compute node'"'"'s egress datapath. This load balancer receives each data message sent from the source compute node, and determines whether the data message is addressed to one of the DCN groups for which the load balancer spreads the data traffic to balance the load across (e.g., data traffic directed to) the DCNs in the group. When the received data message is not addressed to one of the load balanced DCN groups, the load balancer forwards the received data message to its addressed destination. On the other hand, when the received data message is addressed to one of load balancer'"'"'s DCN groups, the load balancer identifies a DCN in the addressed DCN group that should receive the data message, and directs the data message to the identified DCN. To direct the data message to the identified DCN, the load balancer in some embodiments changes the destination address (e.g., the destination IP address, destination port, destination MAC address, etc.) in the data message from the address of the identified DCN group to the address (e.g., the destination IP address) of the identified DCN.

Claims

1. A method for managing load balancers that load balance data messages that source compute nodes send to at least one group of destination compute nodes (DCNs), the method comprising:

collecting message traffic data relating to data messages that the load balancers distribute to the DCNs of the DCN group;

generating aggregated message traffic data from the collected message traffic data;

based on the aggregated message traffic data, distributing adjustment data to at least a subset of the load balancers to cause the subset of load balancers to adjust how they distribute new data message flows to the DCNs of the DCN group.

2. The method of claim 1, wherein the distributed adjustment data comprises aggregated message traffic data that expresses the data message traffic load on each DCN in the DCN group.

3. The method of claim 2, wherein the aggregated message traffic data expresses either the number of flows, packets or bytes directed to each DCN.

6. The method of claim 2, wherein the aggregated message traffic data expresses a relative congestion percentage of each DCN.

7. The method of claim 2, wherein

each load balancer spreads the data messages among the DCNs based on a set of load balancing criteria,

each load balancer that receives the aggregated message traffic data, analyzes the received aggregated message traffic data and adjusts the load balancer'"'"'s set of load balancing criteria if the load balancer determines that such an adjustment is needed based on the analysis of the aggregated message traffic data.

8. The method of claim 7 further comprising providing to each load balancer an initial set of load balancing criteria as part of an initial configuration of the load balancer.

9. The method of claim 8, wherein the load balancing criteria specifies numerical values that affect how the load balancer spreads the data messages among the DCN.

10. The method of claim 9, wherein the numerical values include one weight value for each DCN, wherein based on the weight values, the load balancer performs a weighted round robin selection of the DCNs for new data message flows.

11. The method of claim 7, wherein each load balancer starts with an initial set of load balancing criteria.

12. The method of claim 1, wherein

each load balancer spreads the data messages among the DCNs based on a set of load balancing criteria,

wherein the distributed adjustment data comprises an adjusted set of load balancing criteria for each load balancer in the subset of load balancers.

13. The method of claim 12, wherein each load balancer in the subset of load balancers receives the same adjusted set of load balancing criteria.

14. The method of claim 12, wherein at least two different load balancers in the subset of load balancers receive different adjusted sets of load balancing criteria.

15. The method of claim 12, wherein the distributed load balancing criteria set specifies a weight value for each DCN, wherein based on the weight values, the load balancer performs a weighted round robin selection of the DCNs for new data message flows.

16. The method of claim 1, wherein the distributed adjustment data comprises updated membership data regarding DCNs that are part of the DCN group.

17. The method of claim 16, wherein

the updated membership data identifies at least one new DCN that has been added to the DCN group, and

after receiving the updated membership data, the subset of load balancers starts to direct a portion of new data message flows to the newly added DCN.

18. The method of claim 17 further comprising deploying a virtual machine (VM) on one of host computing devices to act as the newly added DCN before sending the updated membership data to the subset of load balancers.

19. The method of claim 18 further comprising before deploying the VM, determining that the load on the DCNs in the DCN group has passed a particular threshold that requires another DCN to be added to the DCN group.

20. The method of claim 16, wherein

the updated membership data identifies at least one DCN that has been removed from the DCN group due to an operational failure at the DCN, and

after receiving the updated membership data, each load balancer in the subset redirects data message flows that were previously being directed to the removed DCN to other DCNs in the group.

21. The method of claim 16, wherein

the updated membership data identifies at least one DCN that has been removed from the DCN group, and

after receiving the updated membership data, each load balancer in the subset either does not direct new data message flows to the removed DCN or stops directing new data message flows to the removed DCN at a particular time after receiving the updated membership data.

23. The method of claim 1, wherein the subset of load balancers comprises each load balancer that receives data messages for the DCN group and has to spread the received data messages amongst the DCNs in the DCN group.

24. The method of claim 1, wherein

the subset of load balancers comprises some but not all of the load balancers that receive data messages for the DCN group and have to spread the received data messages amongst the DCNs in the DCN group,

the subset of load balancers including only the load balancers that need to adjust their load balancing operations in view of the aggregated message traffic data.

25. The method of claim 1, wherein

the source compute nodes (SCNs) and the load balancers execute on a set of host computing devices,

each load balancer is a load balancer for one SCN that executes on the same host computing device as the load balancer,

each load balancer intercepts each data message from its associated SCN, determines whether the data message is addressed to the DCN group, and if so, directs the data message to one of the DCNs in the DCN group.

26. The method of claim 25, wherein each SCN'"'"'s load balancer directs at least two different data messages that are part of two different data message flows to two different DCNs of the DCN group.

27. The method of claim 25, wherein after processing each data message, each load balancer supplies the data message to a software forwarding element (SFE) that executes on the load balancer'"'"'s host computing device, for the SFE to forward the data message to an addressed destination.

4-5. -5. (canceled)

22. (canceled)

28. A non-transitory machine readable medium storing a program for managing load balancers that load balance data messages that source compute nodes send to at least one group of destination compute nodes (DCNs), the program comprising sets of instructions for:

collecting message traffic data relating to data messages that the load balancers distribute to the DCNs of the DCN group;

generating aggregated message traffic data from the collected message traffic data;

based on the aggregated message traffic data, distributing adjustment data to at least a subset of the load balancers to cause the subset of load balancers to adjust how they distribute new data message flows to the DCNs of the DCN group.

29. The machine readable medium of claim 28, wherein the distributed adjustment data comprises aggregated message traffic data that expresses the data message traffic load on each DCN in the DCN group.

30. The machine readable medium of claim 29, wherein

each load balancer spreads the data messages among the DCNs based on a set of load balancing criteria,

each load balancer that receives the aggregated message traffic data, analyzes the received aggregated message traffic data and adjusts the load balancer'"'"'s set of load balancing criteria if the load balancer determines that such an adjustment is needed based on the analysis of the aggregated message traffic data.

31. The machine readable medium of claim 28,

wherein each load balancer spreads the data messages among the DCNs based on a set of load balancing criteria,

wherein the distributed adjustment data comprises an adjusted set of load balancing criteria for each load balancer in the subset of load balancers.

32. The machine readable medium of claim 28,

wherein the distributed adjustment data comprises updated membership data regarding DCNs that are part of the DCN group,

wherein after receiving the updated membership data, each load balancer in the subset modifies how the load balancer directs new data message flows to the DCNs.