Method and apparatus for distributing load among a plurality of service nodes

• US 9,935,827 B2
• Filed: 12/12/2014
• Issued: 04/03/2018
• 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
• Primary Examiner(s): Orgad, Edan
• Assistant Examiner(s): Lalchinthang, Vanneilian
• Application Number:
  US14/569,476
• Publication Number:
  US 20160094456A1
• Time in Patent Office: 1,208 Days
• Field of Search: 370235
• CPC Class Codes: H04L 41/0813 characterised by the conditions triggering a change of settings
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 41/5054 Automatic deployment of services triggered by the service manager, e.g. service implementation by automatic configuration of network components
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 63/02 for separating internal from external traffic, e.g. firewalls
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1027 Persistence of sessions during load balancing
• CPC Class Codes: H04L 67/1031 Controlling of the operation of servers by a load balancer, e.g. adding or removing servers that serve requests
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Some embodiments provide an elastic architecture for providing a service in a computing system. To perform a service on the data messages, the service architecture uses a service node (SN) group that includes one primary service node (PSN) and zero or more secondary service nodes (SSNs). The service can be performed on a data message by either the PSN or one of the SSN. However, in addition to performing the service, the PSN also performs a load balancing operation that assesses the load on each service node (i.e., on the PSN or each SSN), and based on this assessment, has the data messages distributed to the service node(s) in its SN group. Based on the assessed load, the PSN in some embodiments also has one or more SSNs added to or removed from its SN group. To add or remove an SSN to or from the service node group, the PSN in some embodiments directs a set of controllers to add (e.g., instantiate or allocate) or remove the SSN to or from the SN group. Also, to assess the load on the service nodes, the PSN in some embodiments receives message load data from the controller set, which collects such data from each service node. In other embodiments, the PSN receives such load data directly from the SSNs.

Claims

1. For a service node (SN) group comprising a plurality of service nodes for performing a service on received data message flows, wherein one service node is a primary service node (PSN) and each other service node is a secondary service node (SSN), a non-transitory machine readable medium storing a PSN program comprising sets of instructions for:

analyzing data message load on each service node;

based on the analysis, identifying several ranges of hash values that are derivable from header values of potential data message flows and associating each range with a service node; and

providing a first set of load balancing parameters (LBPs) to a load balancer (LB) set that distributes the received data message flows to the service nodes of the SN group, wherein the first LBP set comprises the hash value ranges and associated service nodes

after providing the first LBP set to the LB set, continuing to analyze the data message load on the service nodes, and based on the continued analysis, providing a second LBP set to the LB set that has at least one hash range that is not in the first LBP set.

2. The non-transitory machine readable medium of claim 1, wherein each load balancer in the LB set distributes the received data message flows to the service nodes in a stateless manner.

3. The non-transitory machine readable medium of claim 1, wherein upon receiving a new data message flow, each load balancer in the LB set (i) computes a hash value from the flow'"'"'s header parameter set, and (ii) directs data messages of the flow to a particular service node that is associated with a hash value range that contains the computed hash value.

4. The non-transitory machine readable medium of claim 1,

wherein the second LBP set differs from the first LBP set in terms of the association between the hash ranges and service nodes.

5. The non-transitory machine readable medium of claim 1, wherein the second LBP set further has at least one hash range that is in the first LBP set but is associated with different service nodes in the first and second LBP sets.

9. The non-transitory machine readable medium of claim 1,

wherein each load balancer in the LB set distributes the received data message flows to the service nodes in a stateless manner;

wherein after a load balancer receives the second LBP set, the load balancer distributes the received data message flows that were being directed to one service node to another service node, and

wherein the PSN program further comprises sets of instructions for;

obtaining connection-flow state from another service node in the SN group;

using the connection-flow state to determine that a particular data message flow that the PSN receives is a flow that is currently being processed by the other service node; and

directing data messages of the particular data message flow to the other service node.

10. The non-transitory machine readable medium of claim 9,

wherein each service node exchanges connection-flow states with other service nodes, and

wherein each particular service node uses the connection-flow states of each other service node to determine whether a new data message flow that the particular service node receives is currently being processed by another service node, and if so, to direct data messages of the new data message flow to the other service node.

11. The non-transitory machine readable medium of claim 1,

wherein the PSN program further comprises a set of instructions for providing the LBP set to each SSN;

and

wherein each SSN directs a new data message flow that the SSN receives from the LB set to another service node when the SSN determines, based on the LBP set, that another SSN should process the new data message flow.

12. The non-transitory machine readable medium of claim 11,

wherein each load balancer in the LB set distributes the received data message flows to the service nodes in a stateless manner;

and

wherein a particular load balancer forwards the new data message flow to the wrong SSN as part of a load balancing operation for the new data message flow at a time that the PSN has distributed a new LBP set to the LB set but the particular load balancer has not yet updated its load balancing operations based on the new LBP set and uses an older LBP set to perform the load balancing operation for the new data message flow.

13. The non-transitory machine readable medium of claim 1,

wherein each SSN derives the LBP set independently of the PSN as each SSN executes same sets of instructions as the PSN in order to derive an LBP set;

and

wherein each particular SSN directs to another SSN a new data message flow that the particular SSN receives from the LB set when the SSN determines, based on the LBP set that the SSN derives, that the other SSN should process the new data message flow.

14. The non-transitory machine readable medium of claim 1, wherein the program further comprises sets of instructions for:

providing, to a controller set, message load data regarding the data messages on which the PSN performs the service, wherein each other service node provides message load data regarding the data messages on which the service node performs the service; and

receiving aggregated message load data from the controller set, the aggregated message load data quantifying message load on each service node and derived from the message load data that the controller set obtains from each service node;

wherein the set of instructions for analyzing the message load comprises a set of instructions for analyzing the received aggregated message load data.

15. The non-transitory machine readable medium of claim 1, wherein the program further comprises sets of instructions for:

receiving message load data from each SSN in the SN group;

aggregating the message load data to analyze relative message load on each service node; and

distributing a new LBP set to adjust the data message flow distribution to the service nodes and thereby adjust the load on the service nodes.

16. The non-transitory machine readable medium of claim 1, wherein the program further comprises sets of instructions for:

maintaining message load data regarding data messages on which the PSN performs the service; and

receiving message load data from each SSN in the SN group;

wherein the set of instructions for analyzing data message load on each service node comprises a set of instructions for analyzing the message load data provided by the SSN and the maintained message load data regarding data messages on which the PSN performs the service.

17. The non-transitory machine readable medium of claim 1, wherein the LB set includes only one load balancer.

18. The non-transitory machine readable medium of claim 1, wherein the LB set includes more than one load balancer.

6. For a service node (SN) group comprising a plurality of service nodes for performing a service on received data message flows, wherein one service node is a primary service node (PSN) and each other service node is a secondary service node (SSN), a non-transitory machine readable medium storing a PSN program comprising sets of instructions for:

analyzing data message load on each service node;

based on the analysis, identifying several ranges of hash values that are derivable from header values of potential data message flows and associating each range with a service node;

providing to a load balancer (LB) set the hash value ranges and associated service nodes as a first set of load balancing parameters (LBP), the LB set for distributing the received data message flows to the service nodes of the SN group;

after providing the first LBP set to the LB set, continuing to analyze message load on each service node;

based on the continued analysis, determining that a service node should be added to the SN group; and

distributing a second LBP set to add the service node to the SN group, the second LBP set differing from the first LBP set in terms of at least one hash range that is not in the first LBP set.

19. The non-transitory machine readable medium of claim 6, wherein each load balancer in the LB set distributes the data message flows to the service nodes in a stateless manner.

7. For a service node (SN) group comprising a plurality of service nodes for performing a service on received data message flows, wherein one service node is a primary service node (PSN) and each other service node is a secondary service node (SSN), a non-transitory machine readable medium storing a PSN program comprising sets of instructions for:

analyzing data message load on each service node;

based on the analysis, identifying several ranges of hash values that are derivable from header values of potential data message flows and associating each range with a service node;

providing to a load balancer (LB) set the hash value ranges and associated service nodes as a first set of load balancing parameters (LBP), the LB set for distributing the received data message flows to the service nodes of the SN group;

after providing the first LBP set to the LB set, continuing to analyze message load on each service node; and

based on the continued analysis, determining that a service node should be added to the SN group;

directing a controller set to add the service node to the SN group;

receiving confirmation from the controller set that the service node has been added; and

after receiving confirmation, distributing a second LBP set to add the service node to the SN group.

8. For a service node (SN) group comprising a plurality of service nodes for performing a service on received data message flows, wherein one service node is a primary service node (PSN) and each other service node is a secondary service node (SSN), a non-transitory machine readable medium storing a PSN program comprising sets of instructions for:

analyzing data message load on each service node;

based on the analysis, identifying several ranges of hash values that are derivable from header values of potential data message flows and associating each range with a service node;

providing to a load balancer (LB) set the hash value ranges and associated service nodes as a first set of load balancing parameters (LBP), the LB set for distributing the received data message flows to the service nodes of the SN group;

after providing the first LBP set to the LB set, continuing to analyze message load on each service node;

based on the continued analysis, determining that a service node should be removed from the SN group; and

distributing a second LBP set to remove the service node from the SN group, the second LBP set differing from the first LBP set in terms of at least one hash range that is not in the first LBP set.

20. The non-transitory machine readable medium of claim 8, wherein each load balancer in the LB set distributes the data message flows to the service nodes in a stateless manner.