Virtual machine placement against the non-proportional resource consumption in cloud computing

LUO Xiang-yu，XIN Gang,GUI Xiao-lin

(1.College of Computer Science and Engineering,Xi’an University of Science and Technology,Xi’an 710054,China； 2.Faculty of Electronic and Information Engineering，Xi’an Jiaotong University，Xi’an 710049，China; 3.AVIC Computing Technique Research Institute，Xi’an 710119，China)

Abstract：Virtual machine placement is a basic problem in cloud computing.By consolidating several virtual machines onto one single physical machine，cloud computing reduces both resource costs and energy consumption.One of the optimization objectives of virtual machine placement is to use a minimum number of physical machines to accommodate all the virtual machines requested by customers.The challenge lies in that the multi-dimensional resources required by a virtual machine are typically not proportional to that provided by a physical machine.Once a single dimension of resource is exhausted in a physical machine，the rest of all the other dimensions of resources will stay unutilized，leading to a great amount of resource waste.This paper proposes a new virtual machine placement algorithm that mixes multiple kinds of physical machines to tackle the problem of unsufficientresource utilization.Firstly，virtual machines are divided into several subsets.For each subset as a whole，different dimensions of resources requested are approximately proportional to that provided by a kind of physical machine.Secondly，virtual machines in each subset are separately placed onto the corresponding kind of physical machines.Experimental results show that the proposed algorithm coordinates the utilization of different types of resources and achieves power reduction ranging from 13.0% to 57.6%.

Key words：virtual machine placement；non-proportional resource consumption；cloud computing；power reduction；multidimensional resources

0 INTRODUCTION

Nowadays cloud computing is a popular way of offering computation services.It enables customers to enjoy computation services as conveniently as they enjoy electricity and water[1].Customers are typically served by virtual machines.By consolidating several virtual machines onto one single physical machine，the whole cloud computing system achieves both more efficient utilization of resources and lower power consumption.

A cloud computing system is a large-scale distributed system composed of thousands of or even more physical machines[2].A basic problem is how to place the virtual machines such that the number of the consumed physical machines can be minimized while satisfying multiple resource constraints.

To accommodate several virtual machines，a physical machine is required to provide available CPU，memory and other resources no less than that requested by the virtual machines.Once a single dimension of resource is exhausted in a physical machine，all the rest of the other dimensions of resources on it will stay unutilized[3].Therefore，an ideal virtual machine placement algorithm should assign each physical machine with several virtual machines that just use up each dimension of resource on it.

However，the challenge lies in that different dimensions of resources required by a virtual machine are typically not proportional to that provided by a physical machine.Existing studies mainly aim to make the best-effort optimization of resource utilization under the assumption that the candidate physical machines are deterministic and unchangeable.They rarely investigate how to adaptively adjust the candidate physical machines’ configuration according to the virtual machines’ requirements to make further improvements.In the situations that the virtual machines differ significantly with the physical machines in the proportions of the multiple dimensions of resources，the best-effort optimization is usually unsatisfactory.

Our contributions mainly include the following three aspects.Firstly，we redefine the virtual machine placement problem and divide it into two sub-problems.One is how to adaptively adjust the configuration of the physical machines according to the requirements of the virtual machines.The other is how to map the virtual machines to the candidate physical machines.Secondly，we propose an algorithm,namely CORE(COordinating multiple REsources)，to resolve the problem.Finally，extensive experiments have been conducted to evaluate the efficiency of the algorithm.The results show that it can achieve power reduction ranging from 13.0% to 57.6%.

The paper is organized as follows.Section 1 summarizes the related work.Section 2 explains the motivations of our work.Section 3 redefines the virtual machine placement problem.Section 4 elaborates the CORE algorithm.Section 5 gives the experimental results and Section 6 concludes the whole paper.

1 RELATED WORK

The virtual machine placement algorithm greatly affects the performance and the efficiency of clouds and attracts many researchers’ attention[4].

According to the assumption for the resources，existing virtual machine placement algorithms could be classified into single dimensional resource oriented and multi-dimensional resource oriented algorithms.F.Pan et al.proposed a single resource oriented algorithm that only considers the CPU resource[5].L.Chen et al.proposed a multi-dimensional resource oriented algorithm RIAL that considers CPU，memory and the network resources[6].It assigns different weights to different resources and calculates the resource intensity of each physical machine based on the weights.By this way，the multi-dimensional problem is transformed into a single dimensional one.R.Li et al.proposed a true multidimensional solution which aims to keep balanced usage of each dimensional resource[7].However，the physical machines were assumed to be determined in advance and only best-effort utilization was provided.Besides，the relationships among the resource utilization，the characteristics of virtual machine requirements and the configuration of the physical machines were not investigated.

According to the assumption for the characteristic of the workload，existing virtual machine placement algorithms can be classified into static and dynamic ones.Static algorithms assume that the workload of each virtual machine is constant.Many approximation algorithms for bin packing can be used for static virtual machine placement[8].Besides，genetic or other intelligent optimization algorithms can also work[9].Dynamic algorithms[10-11]migrate virtual machines from one physical machine to another as the workload changes.

From the point of view of the optimization objectives，existing virtual machine placement algorithms can be classified into single-objective oriented and multi-objective oriented ones.The optimization objects include minimizing SLA violation，maximizing resource utilization，minimizing energy consumption，etc[12-13].W.Wang et al.proposed a single objective oriented algorithm that aims for energy minimization[14].J.Xu and J.Fortes proposed an algorithm that simultaneously minimizes resource wastage，power consumption and thermal dissipation costs[15].H.Zhao proposed an algorithm that ensures both low power consumption and high performance guarantee[16].

Besides,the state-of-art research also addresses the virtual machine placement problem in edge cloud systems[17-19].

However，to the best of our knowledge，existing literatures mainly concentrate on virtual machine placement optimization under the assumption that the candidate physical machines are determined in some artificial way.There is no solution that automatically changes the candidate physical machines according to the virtual machines’ resource requirements.

2 MOTIVATIONS

For economic and environmental reasons，cloud computing aims to employ a minimum number of physical machines to accommodate the virtual machines requested by customers，reducing both resource costs and power consumption.For a given set of virtual machines，both the resource costs and the power consumption are affected by not only the virtual machine placement algorithm itself，but also the configuration of the physical machines.

Suppose that there are 500 virtual machines.For half of them，each one requires 3 cores CPU and 0.5 GB RAM.For the other half，each one requires 1 core CPU and 1.5 GB RAM.Therefore，the total amount of CPU required by the virtual machines equals 1 000 cores，and the total amount of required RAM equals 500 GB.With the physical machines configured with 4 cores CPU and 8 GB RAM，the least number of the powered-on physical machines cannot be smaller than 250 and the utilization efficiency of RAM cannot be greater than 25%，whatever virtual machine placement algorithm is adopted.However，with the physical machines configured with 4 GB RAM and 8 cores CPU，only 125 physical machines need to be powered on and both the two types of resources can be sufficiently utilized.

For the above scenario，changing the physical machine’s configuration leads to more efficient resource utilization and lower power consumption.However，it is not always practical to do so in reality.Virtual machines are created and removed dynamically，and each of them may have different resource requirements.Hence the optimal physical machine configuration changes frequently.It is not practical to alter the physical machine’s configuration all the time.

Therefore，we mix several kinds of physical machines to mimic physical machines with arbitrary kind of configuration.We assume that the cloud providers purchase several kinds of physical machines with different resource configurations and the number of each kind of physical machines is large enough.For a given set of virtual machines，the placement algorithm automatically adjusts the number of each kind of physical machines to power on，ensuring that the multiple resources provided by the whole powered-on physical machines always proportional to that requested by the whole virtual machines.For cloud providers，the most important thing is not to purchase but to power on the least number of physical machines，because the budget for power consumption is much higher than the infrastructure costs.

In a word，for a given set of virtual machines，the efficiency of resource utilization is greatly affected by the physical machines’ configuration.With unsuitable physical machine configuration，resource waste is inevitable，whatever placement algorithm is adopted.We aim to mix several kinds of physical machines to keep the mimic configuration always suitable to the virtual machines，so that the placement results can be improved compared with those obtained with a deterministic configuration.

3 PROBLEM STATEMENT

Suppose that there areKkinds of physical machines with different resource configurations.The number of each kind of physical machine is large enough for accommodating an arbitrary set of virtual machines.Theith kind of physical machine is represented with a vectorpicomposed ofCelements with each elementpijcorresponding to the amount of thejth type of resource provided by theith kind of physical machine.There areNvirtual machines to be placed onto the physical machines.Each virtual machine is expressed with a vectorvi′also composed ofCelements，with each elementvi′jrepresenting the amount of thejth type of resource requested by thei′ th virtual machine.Here 1≤i≤K，1≤i′≤N，1≤j≤C，K，NandCare known numbers.

The virtual machine placement problem is divided into two sub-problems.Firstly，for accommodating a given set of virtual machines，how many each kind of physical machines should be powered on? Secondly，how to map the virtual machines to the powered-on physical machines? The optimization objective is to minimize the total number of the powered-on physical machines while satisfying each virtual machine’s resource requirements.

4 THE CORE ALGORITHM

4.1 Basic idea

Letnidenote the number of the powered-on physical machines with theith kind of configuration andVSidenote the set of the virtual machines mapped to theith kind of physical machines.Hence {VSi|1 ≤i≤K} defines a partitioning on the whole set of the virtual machines.

Once we obtain a proper partitioning of the virtual machines，through placing the virtual machines in each subsetVSito the ith kind of physical machines，nican be figured out.Therefore，the partitioning of the virtual machines is at the heart of the problem.

The CORE algorithm works in three steps.Firstly，it partitions the whole virtual machine set intoKsubsets ensuring that each subsetVSiconsumes the multiple resources proportionally to the provisioning of the ith kind of physical machines.Secondly，it separately calculates the mappings between the virtual machines in each subsetVSiand the ith kind of physical machines.Thirdly，it merges the results of the second step，the number of each kind of physical machines to be powered on(i.e.，ni)is obtained，and the mappings between the whole virtual machines and the whole powered-on physical machines are also figured out.

4.2 Elaboration of the algorithm

The CORE algorithm is depicted in Algorithm 1.In the algorithm，there are two inputsPSandVS.PSis the set of physical machine types with each elementpirepresenting the configuration of theith type of physical machine，andVSis the set of virtual machines with each elementvi′representing the resource requirements of thevi′th virtual machine.Bothpiandvi′are vectors composed ofCelements.Thejth element ofpidenoted bypijrepresents the amount of thejth type of resource provided by theith kind of a single physical machine，and thejth element ofvi′denoted byvi,jrepresents the amount of thejth type of resource requested by thei′th virtual machine.There are two outputsNSandMS.NSis a set of numbers with each elementnirepresenting the number of the powered-on physical machines with theith kind of configuration.MSis a set of tuples with each element indicating that thei′ th virtual machine is placed on thes(i′) th physical machine with thek(i′) th kind of configuration.Herek(i′) is a integer between 1 andK，ands(i′) is an integer between 1 andnk(i′).Recall thatnk(i′)represents the number of the powered-on physical machines with thek(i′) th kind of configuration.

Data:Set of physical machine configurations:

PS={pi|1≤i≤K};

Set of virtual machine requirements:

VS={vi′|1≤i′≤N}

Result:Set of numbers of the powered-on physical machines:

NS={ni|1≤i≤K};

Setp of mappings:

MS={|1≤i′≤N}

Call the partitioning sub-algorithm withPSandVS

Store the partitioning results as π={VSi|1≤i≤K}

i:=1

Whileiis between 1 andKdo

end

Call the merging sub-algorithm with {MSi|1≤i≤K}

Store the mapping results intoMS

Algorithm 1:The CORE algorithm

The main body of the algorithm calls three sub-algorithms as shown in Algorithm 1.The partitioning sub-algorithm is responsible for partitioning the virtual machine setVSintoKsubsets，the placement sub-algorithm is responsible for placing the virtual machines in a subsetVSito theith kind of physical machines，and the merging sub-algorithm is responsible for combining the placement results to obtain the number of the powered-on physical machine for each kind of configuration，and the mappings between the whole virtual machines and the whole powered-on physical machines.In the algorithm description，π represents the partition onVSand π={VSi|1 ≤i≤K}.MSirepresents the mapping of the virtual machines in subsetVSiand theith kind of physical machines.

4.2.1 The partitioning sub-algorithm

As discussed in the subsection 4.1，the partitioning of the virtual machines is at the heart of the problem.For the virtual machines as a whole，the multiple resources requested may be not proportional to any kind of the existing physical machines.With proper partitioning，the multiple resources requested by each virtual machine subset could be proportional to a certain kind of physical machines.

LetRijdenote the amount of thejth type of resource requested by the virtual machines of the subsetVSi.VSisatisfies proportional resource consumption means that for eachjbetween 1 andC，Rij/pijis almost the same.We defineθto measure the degree of proportionality，withθ=min{Rij/pij|1≤j≤C}/max{Rij/pij|1≤j≤C}.θis a number between 0 and 1.A largerθmeans a higher degree of proportionality.It should be noted that max{Rij/pij|1≤j≤C} is a lower bound of the number of the ith kind of physical machines to power on.

The partitioning sub-algorithm aims to guarantee that each virtual machine subsetVSisatisfies proportional resource consumption，and the lower bound of the whole powered-on physical machines，i.e.，∑1≤i≤K(max{Rij/pij|1≤j≤C})，is minimized.The partitioning sub-algorithm adopts a greedy strategy described in Algorithm 2.For each virtual machine，the algorithm assigns it to the subset that makes the least increase of ∑1≤i≤K(max{Rij/pij|1≤j≤C}).

4.2.2 The placement sub-algorithm

The placement sub-algorithm is responsible for placing the virtual machines in a subsetVSito the ith kind of physical machines.Although other placement strategies also work，we adopt the FirstFit strategy for simplicity.Since the partitioning sub-algorithm ensures that the multiple resources requested by the virtual machine subsetVSiare approximately proportional to that provided by the ith kind of physical machines，even if the FirstFit strategy is qualified to generate ideal placement results.Experimental results also validate the conjecture，as exposed in Section 5.The placement sub-algorithm is described in Algorithm 3.In the description， means that thekth virtual machine inVSiis placed onto thes(k)th physical machine with theith kind of configuration satisfying 1≤k≤|VSi| and 1≤s(k)≤ni.

Data:Set of physical machine configurations:

PS={pi|1≤i≤K};

Set of virtual machine requirements:

VS={vi′|1≤i′≤N}

Result:A partitioning ofVS:π={VSi|1≤i≤K}.

Initialization:VSi:=φ,1≤i≤K;

Rij:=0,1≤i≤K,1≤j≤C.

i′:=1Whileiis betweenIanNdo

end

Algorithm 2：The partitioning sub-algorithm

4.2.3 The merging sub-algorithm

The merging sub-algorithm merges the results of the placement sub-algorithm for each virtual machine subset and is described in Algorithm 4.In the description， means that thei′ th virtual machine is placed onto thes(i′) th physical machine with thet(i′) th kind of configuration，satisfying 1≤i′≤N，1≤t(i′)≤Kand 1≤s(i′)≤nt(i′).

5 EXPERIMENTAL RESULTS

5.1 Experimental setup

In order to evaluate the performance of the CORE algorithm，we conducted simulation studies with CloudSim[20]running on a 2.5 GHz Intel Xeon PC with 6 GB of RAM.

Data:Virtual machine subsctVSi:

Physical machine configurationpi

Result:Number of powered-on physical machinesni

Set of mappings:

MSi={|1≤k≤|VSi|}

ni:=0

PSi:=φ

k:=1

Whileiis betweenIan |VSi|do

end

Algorithm 3：The placement sub-algorithm

We design a synthetic virtual machine generator which can produce a requested number of tuples with each one representing the resource requirements of a virtual machine.The tuple consists of two members：the amount of CPU measured in cores and the amount of RAM measured in GB.The two members are respectively drawn fromIU(a1，b1)andIU(a2，b2).IU(a，b) returns an integer from the range[a，b]uniformly.

Data:{MSi|1≤i≤K};

Result:Set of mappings:

MS={|1≤i≤N}.

MS:=φ

i:=0;

Whileiis betweenIan |MSi|do

end

Algorithm 4：The merging sub-algorithm

We assume that there are three kinds of physical machines that share equivalent energy consumption ratew.The first one is configured with 8 cores of CPU and 128 GB of RAM，the second one is configured with 16 cores of CPU and 64 GB of RAM，and the third one is configured with 32 cores of CPU and 32 GB of RAM.The first configuration is most suitable to data-intensive applications，the third one is most suitable to computation-intensive applications，and the second one is in the middle.For convenience，we list them is TABLE I.

Table Ⅰ Configurations of physical machines

5.2 Impacts of physical machine configurations

For the same set of virtual machines，different physical machine configurations lead to different resource utilization and power consumption.

We use the synthetic virtual machine generator to obtain 1 000 virtual machines’ resource requirements.The parameters are set as follows：a1=1，b1=7，a2=1 andb2=31.In the experiment，the total amount of CPU requirementR1equals 3 962 cores and the total amount of RAM requirementR2equals 16 190 GB.

For the physical machines with theith kind of configuration，the lower bound of the number of the consumed physical machines is calculated as：nmin(i)= max{R1/pi1，R2/pi2}，and the degree of proportionality is calculated as：θ(i)= min{R1/pi1，R2/pi2}/max{R1/pi1，R2/pi2}.We list the results in TABLE Ⅱ.

Table Ⅱ Proportionality analysis with three configurations

The table shows thatR1/p21is near toR2/p22，θ(2)is the biggest one among the three andnmin(2)is the smallest one among the three.Therefore，the given set of virtual machines approximately satisfies the proportional resource consumption when the physical machines with the 2nd configuration are adopted.

For each configuration，we employ the FirstFit algorithm to place the virtual machines onto the physical machines.The resource utilization efficiency and the power consumption is listed in TABLE Ⅲ.

Table Ⅲ Efficiency comparison with different configurations

The results indicate that，the 2nd configuration can lead to high utilization of the two types of resources as well as low power consumption.Moreover，the number of the consumed physical machines(.i.e.，266)is very near tonmin(i.e.，253).Therefore，as long as the configuration of the physical machines is suitable to the virtual machines，even if the First Fit algorithm can generate near-optimal placement results.More complex placement algorithms are not very necessary.

The results also indicate that，with unsuitable configuration，at least one type of resource generates a great amount of waste.Meanwhile，there is little room for further optimization by improving placement strategy，since the number of physical machines consumed already approaches the lower bound nmin.With the 1st configuration，the number of the consumed physical machines equals 507 whilenminequals 496.With the 3rd configuration，the number of the consumed physical machines equals 530 whilenminequals 506.Whatever virtual machine placement algorithm is adopted，the reduction of the number of the consumed physical machines cannot be greater than 4.5%.

In summary，compared to the placement strategy，the configuration of the physical machine really matters.The most important thing is to make the configuration always suitable to the virtual machines.Once the configuration is determined，there is little room for further optimization whatever placement strategy is adopted.Meanwhile，the requirements of the virtual machines are dynamic，and any single kind of physical machine configuration can not always meet the virtual machines’ requirements.Therefore，the CORE algorithm adaptively adjusts the number of each kind of physical machines powered on to make the different kinds of physical machines as a whole always suitable to the requirements of the virtual machines.

5.3 Evaluation of CORE’s performance

In the experiment，we use the synthetic virtual machine generator to obtain 1 000 virtual machines’ resource requirements.The parameters are set as follows：a1=1，b1=7，a2=1 andb2=19.In the experiment，the total amount of CPU requirement equals 4 046 cores，and the total amount of RAM requirement equals 9 887 GB.

We adopt the First Fit algorithm to place the virtual machines onto the physical machines with each kind of configuration respectively and adopt the CORE algorithm to place them onto the three kinds of physical machines as well.Besides，we calculate the optimal value of the power consumption and the resource utilization for the three configurations.The results are shown in TABLE Ⅳ.

The results show that，through properly mixing the three kinds of physical machines，the CORE algorithm reduces the power consumption and improves the resource utilization efficiency.The power consumption reduction ranges from 13.0% to 57.6%.

Table Ⅳ Comparison results

For further analysis，we calculate the degree of proportionalityθ.We haveθ(1)=0.15，θ(2)=0.61 andθ(3)=0.41 respectively with the three different configurations.It means that the second configuration fits the requirements of the virtual machines best，while the first configuration is the worst.Therefore，the situation where only the physical machines with the first configuration are adopted leads to the maximum power consumption，and the CORE reduces the power consumption with the highest ratio(i.e.，57.6%).

6 CONCLUSION

The efficiency of virtual machine placement is affected by not only the placement strategy itself but also the configuration of the physical machines.The improper configuration leads to a waste of both resource costs and energy consumption.This paper proposes the idea of mixing several kinds of physical machines to mimic a new kind of configuration that properly fits the resource requirements of the virtual machines.Furthermore，we devise the algorithm CORE to realize the idea.It divides the virtual machines into several subsets，with each subset satisfying proportional resource consumption to a certain kind of physical machines.Experimental studies show that the algorithm achieves 13.0% to 57.6% energy reduction compared with those adopt any single kind of physical machines.