Method and system to rebalance constrained services in a cloud using a genetic algorithm

Patent metadata

Field	Value
Publication number	US-9880885-B2
Application number	US-201514689934-A
Country	US
Kind code	B2
Filing date	Apr 17, 2015
Priority date	Feb 4, 2015
Publication date	Jan 30, 2018
Grant date	Jan 30, 2018

Abstract

A method in a server end station is described. The method includes performing an iteration of a rebalancing computation by selecting a set of one or more service sets for rebalancing, wherein the selecting the set of one or more service sets is based on service set constraints and host constraints; generating candidate solutions, wherein each candidate solution includes a randomized one-to-one mapping of each of the service sets to one of the hosts; performing one or more crossover operations on the candidate solutions; performing one or more mutation operations on the additional candidate solutions; selecting as a solution one of the candidate solutions that has a best fitness score, wherein a fitness score for a candidate solution is calculated based on the distribution of resources resulting from and number of migrations needed for the candidate solution; and repeating the iteration of the rebalancing computation an additional number of times.

First claim

What is claimed is:

1. A method in a server end station coupled to one or more hosts for rebalancing one or more services running on the one or more hosts, the method comprising:
receiving a rebalance request message;
performing an iteration of a rebalancing computation by:
selecting a set of one or more service sets for rebalancing, wherein each service set includes one or more services running on one of the one or more hosts, and wherein the selecting the set of one or more service sets is based on one or more service set constraints and one or more host constraints;
generating one or more candidate solutions, wherein each of the one or more candidate solutions includes a randomized one-to-one mapping of each of the one or more service sets to one of the one or more hosts, and wherein the one or more generated candidate solutions adhere to the one or more service set constraints and the one or more host constraints;
performing one or more crossover operations by randomly selecting a pair of candidate solutions from the one or more generated candidate solutions to generate additional candidate solutions;
performing one or more mutation operations on the additional candidate solutions; and
selecting as a solution, one of the one or more generated candidate solutions and the additional candidate solutions that has a best fitness score, wherein a fitness score for a candidate solution is calculated based on the distribution of resources resulting from and number of migrations needed for the candidate solution; and

repeating the iteration of the rebalancing computation an additional number of times, wherein each time the selecting the set of one or more service sets is based on the mapping of the selected solution from the previous iteration; and
migrating the one or more service sets to the one or more hosts based on the solution from a final rebalancing computation.

2. The method of claim 1 , wherein the one or more service set constraints comprises one or more anti-affinity constraints, and wherein two service sets that have an anti-affinity constraint with each other cannot run on a same host.

3. The method of claim 1 , wherein each service in each of the one or more service sets has an affinity constraint with at least one other service in the same service set, and wherein two services that have the affinity constraint with each other must run on the same host.

4. The method of claim 1 , wherein the one or more host constraints comprise residual processor resources and residual memory resources, wherein a service set can only run on a host that has more residual processor resources than the service set requires and has more residual memory resources than the service set requires.

5. The method of claim 1 , wherein the one or more mutation operations randomly change the one of the one or more hosts that is mapped to a service set in one more of the additional candidate solutions.

6. The method of claim 2 , wherein the set of one or more service sets for rebalancing is one or more subsets of service sets running on one or more over-utilized hosts in the one or more hosts, wherein each subset is a predetermined fraction of the service sets of that host that have a least number of anti-affinity constraints and uses a least amount of processor and memory resources on their respective host.

7. The method of claim 2 , wherein a split point for the one or more crossover operations splits each candidate solution in the selected pair of candidate solutions between those mappings in each candidate solution having service sets with anti-affinity constraints, and those mappings in each candidate solution having service sets with no anti-affinity constraints.

8. The method of claim 4 , wherein the best fitness score for a candidate solution is a fitness score that, among the one or more candidate solutions, has the minimum amount of differences between the residual processor and residual memory among all the one or more hosts, and that has the minimum number of migrations needed to achieve the mapping in the candidate solution.

9. A server end station coupled to one or more hosts for rebalancing one or more services running on the one or more hosts, comprising:
a processor and a memory, said memory containing instructions executable by the processor whereby the network controller is operative to:
receive a rebalance request message;
perform an iteration of a rebalance computation by:
selecting a set of one or more service sets for rebalancing, wherein each service set includes one or more services running on one of the one or more hosts, and wherein the selecting the set of one or more service sets is based on one or more service set constraints and one or more host constraints;
generating one or more candidate solutions, wherein each of the one or more candidate solutions includes a randomized one-to-one mapping of each of the one or more service sets to one of the one or more hosts, and wherein the one or more generated candidate solutions adhere to the one or more service set constraints and the one or more host constraints;
performing one or more crossover operations by randomly selecting a pair of candidate solution from the one or more generated candidate solutions to generate additional candidate solutions;
performing one or more mutation operations on the additional candidate solutions; and
selecting as a solution, one of the one or more generated candidate solutions and the additional candidate solutions that has a best fitness score, wherein a fitness score for a candidate solution is calculated based on the distribution of resources resulting from and number of migrations needed for the candidate solution; and
repeating the iteration of the rebalancing computation an additional number of times, wherein each time the selecting the set of one or more service sets is based on the mapping of the selected solution from the previous iteration; and
migrating the one or more service sets to the one or more hosts based on the solution from a final rebalancing computation.

10. The server end station of claim 9 , wherein the one or more service set constraints comprises one or more anti-affinity constraints, and wherein two service sets that have an anti-affinity constraint with each other cannot run on a same host.

11. The server end station of claim 9 , wherein each service in each of the one or more service sets has an affinity constraint with at least one other service in the same service set, and wherein two services that have the affinity constraint with each other must run on the same host.

12. The server end station of claim 9 , wherein the one or more host constraints comprise residual processor resources and residual memory resources, wherein a service set can only run on a host that has more residual processor resources than the service set requires and has more residual memory resources than the service set requires.

13. The server end station of claim 9 , wherein the one or more mutation operations randomly change the one of the one or more hosts that is mapped to a service set in one more of the additional candidate solutions.

14. The server end station of claim 10 , wherein the set of one or more service sets for rebalancing is one or more subsets of service sets running on one or more over-utilized hosts in the one or more hosts, wherein each subset is a predetermined fraction of the service sets of that host that have a least number of anti-affinity constraints and uses a least amount of processor and memory resources on their respective host.

15. The server end station of claim 10 , wherein a split

Assignees

• Ericsson Telefon Ab L M
• ERICSSON TELEFON AB L M (publ)

Inventors

• Sundararajan Priya Krishnan
• Feller Eugen
• Forgeat Julien

Classifications

• G06F9/5088 Primary

  involving task migration · CPC title

• H04L67/1008

  based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30) · CPC title

• G06F9/5083 Primary

  Techniques for rebalancing the load in a distributed system · CPC title