An optimal resource allocation scheme for virtual machine placement of deploying enterprise applications into the cloud

1.   Introduction

Cloud computing is the integration of computer technologies such as distributed computing, network storage, utility computing, virtualization computing, load balancing, and modern network technologies. The cloud computing platform presents a variety of services by centralizing the pool of computing resources connected to the network, such as IaaS (Infrastructure as a Service), PaaS (Platform as a Service), and SaaS (Software as a Service). Regarding the definition of cloud computing, the literature ^[1] defines the hardware and software of the data center as "cloud", and defines the service as "utility computing", and the sum of software services and utility computing becomes cloud computing. According to the National Institute of Standards and Technology (NIST) definition ^[2], cloud computing is a method to access computing resources (including networks, servers, storage, applications, services, etc.) in a convenient, pay-as-you-go manner over a network. It takes advantage of the decentralized resources to support the flexibility of resource sharing and access. Cloud computing enables users to take advantage of the computing resources of the cloud data center as a service, rather than to deploy those resources costly by themselves, and does not require the end users to calculate their exact values of the required resources, which can be calculated and granted by the cloud service providers according to the need of users ^[3]. Due to the attractive features of cloud computing, more and more enterprises migrate and deploy their applications into the cloud so as to reduce their own IT investments, and some interesting resource allocation schemes are also presented and implemented from the social welfare point of view ^[4,5].

Data Center (DC) is used to host servers in the cloud and connects these servers through dedicated links and switches. A large number of distributed processing applications (such as cloud applications, search engines, social applications) are typically run in large data centers ^[6]. Data centers have become an important choice for data-intensive applications. Companies can reduce their own hardware deployment and maintenance costs, and achieve great revenue. Due to the different resource requirements of applications, many physical machines (PMs) in the data center are in low utilization at most of the time. A large number of running PMs are not being fully used, but at the same time they are occurring large management and maintenance costs, resulting in serious waste of resources. Virtualization is one of the most feasible ways to enhance data center utilization. Virtualization technologies can allocate resources of a single physical machine to multiple virtual machines (VMs) to improve scalability and resource utilization ^[7]. Virtualization technologies not only enable performance isolation between applications sharing the same computing node, but also enable dynamic or offline migration technology to migrate virtual machines from one node to another. In the actual environment, users are almost unaware of the impact of VM migration. On the other hand, real-time virtual machine reallocation can achieve dynamic load consolidation, so that virtual machines can be merged onto a smaller number of physical machines, thereby turning idle nodes into energy-saving mode. Virtualizing a physical machine can improve resource utilization, however, concentrating workloads on a subset of the physical machines can cause hot spots, and even degrade the actual performance of each application. Thus, how to achieve efficient VM placement has become a critical problem in the cloud ^[8]. Reasonable resource allocation for virtual machines can also reduce traffic transmission and management and maintenance costs.

Due to the importance of the placement of virtual machines on physical machines in the cloud computing environment, the efficient resource allocation for virtual machine has received a lot of research attention. Each virtual machine placement scenario has one or more targets or goals that are to achieve by designing placement algorithms. For example, some virtual machine placement schemes attempt to reduce network traffic and power consumption in the data center. In addition, the ideal VM placement scheme should reduce unnecessary migration of future VMs ^[9] and improve the utilization and availability of DC resources. The current research mainly focuses on optimal allocation of virtual machine resources in the cloud environment, so as to reduce energy consumption ^[10,11], or achieve the goal of maximizing utility ^[4,12]. At the same time, some researchers have concentrated their research on green cloud computing ^[13,14,15], minimizing the problem of data transmission time ^[16,17], improving the scalability of the system ^[18], and achieving the fairness of network resource allocation ^[19,20].

In this paper we consider enterprise applications deployment into the cloud for reducing its own IT investment, propose an optimization model for virtual machine resource allocation in the cloud environment, and present an optimal resource allocation algorithm. We try to place the virtual machines into the most suitable physical machines and realize the optimal resource allocation for these virtual machines under the constraints of physical machine resources, so as to achieve the goal of maximizing applications utility. We analyze the performance of the proposed resource allocation scheme by applying Lyapunov stability theory and find that all the trajectories along the scheme eventually converge to the optimum of the resource allocation problem. The simulation results show that the scheme can converge to the optimal resource allocation within a limited number of iteration times.

The remainder of this paper is organized as follows: Section 2 introduces the relevant research on virtual machine resource allocation; Section 3 presents the virtual machine resource allocation model and gives the corresponding analysis; Section 4 proposes the resource allocation algorithm and investigates its performance and implementation steps; Section 5 further discusses the utility functions for achieving fair resource allocation and presents the extended resource allocation scheme; Section 6 gives the simulation results of the proposed virtual machine resource allocation algorithm as well as the optimal solutions obtained by LINGO software; Section 7 finally summarizes this paper.

2.   Related work

In recent years, cloud computing technologies have received a lot of research attention from academic and industrial researcher, and have been found to be useful and further implemented in many scenarios, such as ubiquitous industrial networks ^[21,22], power Internet of Things ^[23,24], social vehicular networks ^[25,26], 5G networks ^[27,28], space-terrestrial integrated networks ^[29,30], et al. In many cloud computing systems servers are typically underutilized, resulting in a large amount of resources being idle. Therefore, placing more VMs to fewer PMs is an effective way to reduce power consumption and improve resource utilization. The basic principle of VM placement is to allocate as many VMs as possible on the physical machines while meeting the various constraints specified in the system requirements. VM placement is the process of mapping VMs to the most appropriate location and number of PMs based on the actual needs of users. The existing virtual machine placement algorithms can be divided into two categories according to the targets: one is based on energy consumption, these methods mainly consider server-side constraints; the other is based on application service quality and users' needs, the purpose is to maximize the satisfaction of users. Several virtual machine placement algorithms are presented recently, including constraint programming ^[31,32], simulated annealing, boxing algorithm, stochastic programming ^[33], mixed integer linear programming ^[34,35], genetic algorithm ^[36,37,38], ant colony algorithm ^[39,40], et al., some of which involve virtual machine dynamic migration, while other algorithms only consider static placement.

The goal of the boxing approach is to minimize the number of PMs in operation, treating the VM as an object and the PM as a container, and the goal is to package those objects into as few containers as possible. Although traditional online boxing heuristics (such as Best Fit, BF) have been used to reduce the number of PMs used, there are problems with low utility. Wang et al. ^[41] established an energy consumption model in a cloud computing environment. Based on the analysis of energy consumption in the model, the online packing algorithm was improved, and the energy efficiency of a cloud computing environment composed of virtual machines was proposed. The new energy-aware approach not only improves resource utilization, but also makes the data center more energy efficient. Kaaouache et al. ^[42] considered a one-dimensional packing problem and proposed a new method based on correcting infeasible chromosomes to prevent package overflow. The application of the proposed chromosome to genetic algorithms helps to reduce execution time and minimize energy consumption in cloud data centers. This optimization is done by VM placement, resulting in the use of a minimum number of physical machines and another server that can be turned to sleep or shut down.

For the case where multiple targets are considered, Xu et al. ^[43] defined the VM placement problem as a multi-objective optimization problem, and proposed an improved genetic algorithm based on fuzzy multi-objective evaluation to minimize the total resource loss, energy consumption and heat dissipation costs. Dörterler et al. ^[44] formulated the VM placement problem as a multi-objective ant colony optimization algorithm to minimize SLA collisions, total resource loss, and power consumption. Jayasinghe et al. ^[45] proposed a structural constraint-aware virtual machine placement scheme that supports the constraints of requirements, communication, and availability, and effectively improves the performance and availability of services hosted on the IaaS cloud. Based on the analysis of data center topology characteristics and traffic patterns, Fang et al. ^[46] proposed a new virtual data center network power consumption reduction method to shut down as many unnecessary network nodes as possible, thereby saving power.

In addition, some scholars investigate VM placement and resource allocation by applying queuing theory and game theory. Guo et al. ^[47] used the queuing theory to establish a comprehensive optimization model for cloud computing, which is to optimize the average waiting time, average queue length and number of customers of the cloud system. Xiao et al. ^[48] proposed a new algorithm based on evolutionary game theory. By dynamically adjusting the resource allocation of virtual machines, energy consumption can be effectively reduced. Song et al. ^[49] studied the energy-saving and scalability issues of modern data centers based on convex optimization theory, and proposed a new virtual machine placement scheme. The scheme takes into account the inherent dependencies and traffic between virtual machines, reduces the cost of communication between virtual machines and increases the efficiency and scalability of the data center.

3.   Resource allocation for virtual machine placement

3.1.   Background

In the cloud computing architecture, virtualization technologies are used to realize the flexibility and scalability of resources in the cloud data center. Virtualization technologies can map a virtual machine to one or more physical machines to meet the user's flexible demand for resources ^[49]. At the same time, multiple virtual machines can also parallelly reside on the same physical machine and each virtual machine occupies only part of physical resources, so as to make rational use of the resources of physical machines.

As shown in Figure 1, the VM scheduler is considered as a manager, which continuously monitors the physical resource mapping status provided by the hardware layer to the application service layer, thereby enabling efficient deployment of virtual machines for cloud applications. Generally, in order to improve the utilization of resources, the architecture sets the maximum and minimum thresholds. When the resource utilization of a physical machine is less than the minimum threshold, the physical machine will be shut down to save power consumption and move its virtual machines to other physical machines; when the resource utilization of a physical machine is greater than the maximum threshold, the architecture will no longer place a new virtual machine to the physical machine to ensure that the quality of service does not drop. The task of the resource monitor is to solve the problem of matching the requirements of the application service with the virtual machine resources, obtain the optimal resource allocation for virtual machines, and communicate VM scheduler to place the virtual machine on a suitable physical machine or perform dynamic virtual machine migration. Then, how to allocate the resources of these physical machines is a key issue to improve server utilization and reduce costs. This paper proposes an optimization model for virtual machine resource allocation and introduce a resource allocation scheme to achieve the optimum.

3.2.   Model description

An enterprise user intends to reduce its own system infrastructure investment and maintenance cost, and wants to deploy its applications into the cloud. Indeed, each application is composed of a number of distributed components, generally including three functional tiers: A front-end tier, a business-logic tier, and a back-end tier ^[50]. A front-end tier mainly handles user requests such as web requests and consists of a number of components. A business-logic tier mainly performs specialized application logic. And a back-end tier generally stores some important operation data of an application, and comprises of various databases servers. In some scenarios the components of the back-end tier may not be deployed into the cloud and operate in enterprise local data center for data security consideration.

Consider there is a set $P$ of physical machines in the cloud data center. Virtual machines will be effectively placed in the physical machines through the resource scheduler. Introduce the set $S$ of applications that an enterprise user intends to deploy into the cloud and the set $R$ of application components. Each application $s\in S$ is composed of a set $R(s)$ of components. Here we assume each component resides in one virtual machine. Multiple virtual machines can simultaneously reside on the same physical machine so as to improve the resource utilization. Let $P(r)$ be the set of physical machines that provide resource for the corresponding virtual machine of component $r$. Introduce the set $S(p)$ of applications whose components reside on the physical machine $p$ and obtain resource allocation for the virtual machines from physical machine $p$.

Define $x_{srp}^{CPU}$, $x_{srp}^{ram}$ and $x_{srp}^{sto}$ be the CPU, memory and storage resources offered by physical machine $p$ to component $r$ of application $s$, respectively. And denote $y_{s}^{CPU}$, $y_{s}^{ram}$ and $y_{s}^{sto}$ as the total CPU, memory and storage resources obtained by application $s$, respectively, that is, the summation of all its components for each type of resource. Introduce $U_s(\cdot)$ be the deployment utility of application $s$ which is a continuously differentiable and bounded function with respect to its variables. Let $C_{p}^{CPU}$, $C_{p}^{ram}$ and $C_{p}^{sto}$ be the maximum capacity of CPU, memory and storage of resource provider $p$, respectively.

When an enterprise deploys its applications into the cloud, the goal of resource allocation for virtual machine placement in the cloud is indeed to maximize the agammaegated deployment utility of all applications, so as to achieve effective utilization of the resources of physical machines. Then, we establish the following resource allocation optimization model for virtual machine placement in the cloud.

We investigate the resource allocation for virtual machines placement when enterprise applications are deployed into the cloud. Typically, tightly packing virtual machines onto a small number of working physical machines and turning off other idle machines is an effective way to maximize physical machine utilization and reduce energy consumption. However, concentrating workloads on a subset of the physical machines can cause hot spots, and even degrade the actual performance of each application resided and deployed in the cloud. An effective resource allocation strategy should achieve the tradeoffs between energy efficiency and fairness. Thus we adopt the fairness utility proposed for resource allocation in traditional IP Networks ^[51] and further in per-to-peer networks ^[52], which has the following logarithmic form.

where $w_s$ is the payment that the enterprise user is willing to pay to its resource provider for its application $s$ when the application $s$ is deployed into the cloud.

We find that the application deployment utility function $U_s(\cdot)$ is the summation of deployment utilities from CPU, memory and storage resources, i.e., $U_s(y_{s}^{CPU})+U_s(y_{s}^{ram})+U_s(y_{s}^{sto})$. Then the resource allocation model (3.2) for virtual machines placement when applications are deployed into the cloud can be decomposed into three independent sub-problems for CPU, memory and storage resource allocation, respectively. For simplicity, in the following analysis, we do not further differentiate among the specic types of resource, and generalize these three sub-problems into the following one form

3.3.   Model analysis

For the generalization-form resource allocation model (3.3), the objective function is a strict concave function with respect to variable $y_s$ but not a strict concave function with respect to variable $x_{srp}$. At the same time, the constraints are linear, so the constraint set for this optimization problem is convex. Therefore, the following results can be obtained based on the convex optimization theory.

Theorem 1 When the enterprise user deploys its application into the cloud, the resource allocation model (3.3) for virtual machines placement is a convex optimization problem. The optimal resource allocation $x^* = (x_{srp}^{*}, r\in R, s\in S, p\in P)$ offered to each virtual machine that the component of an application resides on exists but is not unique. The optimal resource allocation $y^* = (y_s^*, s\in S)$ for each application exists and is unique.

In order to get the optimal solution of the resource allocation model, we firstly give the Lagrangian of this nonlinear optimization problem

where $\lambda = (\lambda_s, s\in S)$ is the price vector with element $\lambda_s\geq 0$, which can be considered as the price per unit cloud resource paid by the enterprise user for its application $s$; $\mu = (\mu_p, p\in P)$ is the price vector with element $\mu_p\geq 0$, which can be considered as the price per unit cloud resource charged by physical machine $p$.

We can also rewrite (3.4) with the following form

It can be noted that the first expression in (3.5) is separable in variable $y_s$, and the second expression is separable in variables $x_{srp}$. Thus the objective function of the dual problem can be written as:

where

In equation (3.7), the enterprise user tries to maximize its own deployment utility for its applications, which depends on the total obtained resource $y_s$ of application $s$. $\lambda_s$ is the price per unit resource that the enterprise user pays for application $s$, then $\lambda_s y_s$ is the total payment that the user provides to the resource providers for its application deployment into the cloud. In equation (3.8), component $r$ of application $s$ obtains the resource allocation $x_{srp}$ from physical machine $p$, then $x_{srp} \lambda_s$ is the cost of the enterprise user paying for the physical machine $p$ in the cloud deployment for the application $s$. Since $\mu_p$ is the price per unit resource charged by the physical machine $p$, then $x_{srp} \mu_p$ is the cost of physical machine $p$ when offered resource $x_{srp}$ to component $r$ of application $s$, so equation (3.8) means that each physical machine is to maximize its own revenue.

Hence, the dual problem is

The original resource allocation problem (3.1) or its generalization form (3.3) is to maximize the agammaegation of deployment utility of applications when deployed into the cloud under the constraints of physical machines capacity, and the dual problem (3.9) is to minimize the overall price of the cloud computing data center.

3.4.   Optimize resource allocation

In order to obtain the optimal resource allocation for virtual machine placement when the applications are deployed into the cloud, let $({\bf{x}}^*, {\bf{y}}^*, \lambda^*, \mu^*)$ be the optimal solution to the generalization-form problem (3.3) and the dual problem (3.9). Let $\partial L({\bf{x}}, {\bf{y}}; \lambda, \mu)/\partial y_s = 0$, we can obtain

Substituting (3.10) into (3.4), we obtain

Let $\partial\widetilde{L}({\bf{x}}; \lambda, \mu)/\partial\lambda_s = 0$, then we obtain

Substituting (3.12) into (3.11), we obtain

Assume that the virtual machine corresponding to the component $r$ of application $s$ obtains a certain amount of resource allocation from physical machine $p$, that is $x_{srp} > 0$, then let $\partial\widehat{L}({\bf{x}}; \mu)/\partial x_{srp} = 0$, we can obtain the optimal resource allocation

Then we can obtain the following result.

Theorem 2 For the resource allocation optimization model (3.1) or its generalization form (3.4) for virtual machines placement, if there are two components of an application residing on two different physical machines and obtaining non-zero resource allocations from these machines, then the prices charged by these physical machines are both equal to the price paid by the enterprise user for this application. That is, if $x_{sr_1p_1}^{*} > 0, p_1\in P(r_1)$ and $x_{sr_2p_2}^{*} > 0, p_2\in P(r_2)$, then $\mu_{p_1}^* = \mu_{p_2}^* = \lambda_s^*$.

Actually, from (3.14) we can find

Therefore, a bipartite graph consisting of physical machines $P$ and applications $S$ can be constructed. Each edge represents the relationship between a physical machine and an application, indicating that the physical machine provides resources for the virtual machine of the application to complete the cloud deployment. If the graph is fully connected, then $\mu_{p_1}^* = \mu_{p_2}^* = \mu^*$, otherwise, it can be divided into multiple connected subetaaphs for analysis. In the following discussion, we assume $\mu_{p_1}^* = \mu_{p_2}^* = \mu^*$. Then let $\partial\widehat{L}({\bf{x}}; \mu)/\partial\mu = 0$, we can obtain

Substituting (3.16) into (3.14),

It can be found from (3.17) that when an enterprise application $s$ is deployed into a cloud, the optimal resource allocation $y_s^*$ obtained by the virtual machines in which the components of this application are located depends on the total capacity of its physical machines, and the total payment of all applications that are hosted by the physical machines weighted by the payment $w_s$ for application $s$. At the same time, it can be seen that the total resource allocation $y_s^*$ for each application $s$ is unique, which has been discussed in Theorem 1.

4.   Resource allocation algorithm

4.1.   Resource allocation algorithm description

In order to enable enterprise users to deploy applications into the cloud, the virtual machines in which the components of each application are located should be provisioned with optimal resource allocation. Then this paper proposes the following resource allocation algorithm. Each physical machine $p$ updates its resource allocation $x_{srp}(t)$ for component $r$ of application $s$ according to the following rule

The price per unit resource that an enterprise user should pay to physical machine $p$ when deploying application $s$ into the cloud is

where $\kappa > 0$ is the step size of the algorithm, $\varepsilon > 0, \eta > 0$ are small constants to ensure the allocated resources $x_{srp}(t)$ not lower than $\varepsilon$ and the price $\lambda_s(t)$ not higher than $w_s/\eta$. Here $a = (b)_c^+$ means $a = b$ if $c > 0$ and $a = \max\{0, b\}$ if $c = 0$. In the above algorithm, $\xi_p(t)$ can be regarded as the expected price when the physical machine $p$ provides resources for virtual machines to host components of applications, and at the optimal resource allocation, the expected price $\xi_p^*$ of the physical machine $p$ will be equal to the actual paid price $\lambda_s^*$ of the enterprise user for its applications.

4.2.   Equilibrium

Now we study the proposed resource allocation scheme (4.1)–(4.4) and analyze its equilibrium. By substituting (4.2) into (4.1) and setting (4.1) to zero, we can obtain the equilibrium $(x^*, \lambda^*)$, that is,

Meanwhile, from (4.3) (4.4), at the equilibrium

Then

where (a) and (b) follow from (4.6). Thus the total resource allocation for application $s$ is

and from (4.6) the price paid by the enterprise user for application $s$ is

It is very important to emphasize that the optimal price paid by the enterprise user has no relationship with each application, but only depends on the ratio of the total payment of the enterprise user to the total capacity of physical machines. It is also equal to the optimal price charged by each physical machine. In the following stability analysis, we use $\lambda_s^* = \lambda^*$ and $\mu_p^* = \mu^*$ for simplicity.

Obviously, the equilibrium (4.7), (4.8) is equal to the optimum (3.16), (3.17) of the generalization-form resource allocation problem (3.3). At the same time, we can also find at the equilibrium point the following equality holds

Then, the summation of the allocated resources by each physical machine to the virtual machines of applications is exactly the resource capacity of the physical machine, which also indicates that the resources provided by the physical machine are fully utilized at the equilibrium of the dynamic system described by the algorithm.

4.3.   Stability

From the analysis above, we know that the equilibrium point of the dynamic systems (4.1)-(4.4) described by the algorithm is consistent with the optimal resource allocation of the resource allocation problem (3.3). Based on the asymptotic stability of the continuous dynamic system of Lyapunov stability theory, we can obtain the following result.

Theorem 3 The equilibrium point (4.7), (4.8) of the dynamic systems (4.1)–(4.4) described by the proposed algorithm is asymptotically stable. Therefore, all the trajectories along (4.1)–(4.4) eventually converge to the optimum of the resource allocation problem (3.3).

Proof

Define the following Lyapunov function

where $\psi_p(t) = \sum_{s\in S(p)}\sum_{r\in R(s)}x_{srp}(t), p\in P$, and $\lambda^* = \lambda_s^*, \forall s\in S$.

Since $y_s(t)\ge 0$, $y_s^*\ge 0$, the first part of the Lyapunov function is

Obviously, $V_1(t) = 0$ if and only if $y_s(t) = y_s^*$ (i.e., $\lambda_s(t) = \lambda_s^* = \lambda^*$). Meanwhile, the second part of the Lyapunov function is $V_2(t)\ge 0$ since $\psi_p(t) = \sum_{s\in S(p)}\sum_{r\in R(s)}x_{srp}(t)\le C_p$, and $V_2(t) = 0$ if and only if $\psi_p(t) = \sum_{s\in S(p)}\sum_{r\in R(s)}x_{srp}^* = C_p$. Thus, the Lyapunov function $V(t)$ is a positive definite function, and it is zero only at the equilibrium point $(x^*, \lambda^*)$ (i.e., $\lambda_s(t) = \lambda_s^* = \lambda^*$, $\psi_p(t) = \sum_{s\in S(p)}\sum_{r\in R(s)}x_{srp}^* = C_p$).

The derivative of $V(t)$ along the trajectories of the dynamic system (4.1)–(4.4) is

Add $\sum\limits_{s\in S} \sum\limits_{r\in R(s)} \sum\limits_{p\in P(r)}{\kappa}{\lambda_s^2(t)}x_{srp}(t)\frac{1}{C_p}\sum\limits_{j\in S(p)\setminus\{s\}}\sum\limits_{i\in R(j)}x_{jip}(t)$ to the first part of the derivative above, and subtract the same term from the second part, then

Hence

Thus, $dV(t)/dt\le 0$ since $\sum_{j\in S(p)}\sum_{i\in R(j)}x_{jip}(t)\le C_p, p\in P$, and $dV(t)/dt = 0$ if and only if $\lambda_s(t) = \lambda_j(t) = \lambda^*$, $\sum_{j\in S(p)}\sum_{i\in R(j)}x_{jip}^* = C_p$ (i.e., the equilibrium point $(x^*, \lambda^*)$). Therefore, from the Lyapunov stability theory ^[53] the equilibrium point (4.7), (4.8) of the dynamic system (4.1)–(4.4) is asymptotically stable. All the trajectories along (4.1)–(4.4) eventually converge to the optimum of the resource allocation problem (3.3). The result is obtained.

4.4.   Implementation

In the practical implementation, the resource allocation scheme is updated according to the discrete form of the proposed algorithm. That is, at time $t = 1, 2...$, each physical machine $p$ updates its resource allocation for component $r$ of application $s$ according to the following expression.

Here, we introduce an augmented variable $\widetilde{x}_{srp}[t]$, which is considered to be the optimal allocation estimation for resource allocation $x_{srp}[t]$. Therefore, a low-pass filtering scheme is added to the original algorithm, where $\theta$ is the low-pass filtering parameter. By applying low-pass filtering approach, the augmented variable is assisted to remove possible oscillation due to the fact that the model is not strictly concave and optimal resource allocation is not necessarily unique, but not to change optimal resource allocation.

The price paid by the enterprise user for each application follows the rule

The practical implementation of the proposed resource allocation algorithm is summarized as follows:

Step 1: Initialize variables and parameters. Select step size parameter $\kappa$ and small constants $\varepsilon, \eta$. At time $t$, initialize the resource allocation $x_{srp}[t]$ for component $r$ of application $r$ by physical machine $p$.

Step 2: Calculate the price that the enterprise user should pay to the physical machine $p$. At time $t$, application $s$ obtains the total resource allocation $y_s[t]$ for all its components from its available physical machines, and calculates the price $\lambda_s[t]$ that should be paid for using the resource $y_s[t]$.

Step 3: Calculate the expected price of each physical machine. At time $t$, physical machine $p$ calculates its expected price $\xi_p[t]$.

Step 4: Update the resource allocation. At time $t+1$, physical machine $p$ updates its resource allocation $x_{srp}[t+1]$ for component $r$ of application $s$.

Step 5: Set the stop criteria. When the algorithm reaches equilibrium, the iterative process can be stopped to obtain the optimal resource allocation.

In each iteration, the enterprise user separately calculates the price it should pay for each application when obtaining resources from its physical machines and communicates the price to the resource scheduler. Each physical machine updates its resource allocation based on the price paid by the enterprise for each application and reports the optimal resource allocation to the resource scheduler. The iterative process described above is repeated many times until the equilibrium is finally reached.

5.   Further discussion

5.1.   Utility functions and resource allocation

In this section we consider other forms of utility functions and discuss the proposed resource allocation scheme. We follow the well known $\alpha$-fairness utility functions used for resource allocation in IP wired and wireless networks ^[54], which are summarized as the following form

where $\alpha$ is the well known fairness parameter. If we choose different value of parameter $\alpha$, we can achieve different objective of fair resource allocation. For example, we have achieved proportional fairness of resource allocation among applications when choosing $\alpha = 1$. We can also achieve harmonic mean fairness if we choose $\alpha = 2$. And, if $\alpha\rightarrow \infty$, max-min fairness for resource allocation of the physical machines can be achieved when the enterprise user deploys its applications into the cloud.

As for the generalization-form resource allocation model (3.3) with the above utility functions, the objective is also concave but not strictly concave with respect to variables $x_{srp}$, thus the optimal resource allocation can also be obtained by following the aforementioned analysis approach. In details, the optimal resource allocation $y_s^*$ for each application $i$ is

and the optimal price $\mu_p^*$ charged by each physical machine $p$ is also equal to the optimal price $\lambda_s^*$ paid by the enterprise user for its physical machines, that is,

Then the optimal resource allocation depends not only on the total payment for applications and the total resource capacity of all physical machines, but also on the the fairness parameter $\alpha$, i.e., other fairness goals of resource allocation can also be achieved if we choose different fairness parameters accordingly.

5.2.   Extended resource allocation scheme

As for the extended form of utility function (5.1), we modify the original resource allocation scheme and propose an improved resource allocation algorithm. When an enterprise user deploys its applications into the cloud, each physical machine $p$ updates its resource allocation for component $r$ of application $s$ with the following rule

And the price that the enterprise user pays to the physical machines is

Substituting (5.5) into (5.4) and setting (5.4) to zero, we can obtain the equilibrium of the dynamic system described by the improved algorithm, which is also equal to optimum (5.2), (5.3) of the generalization-form resource allocation model with the extended form of utility function (5.1). Furthermore, by applying the asymptotic stability approach for the continuous dynamic system, we also deduce that the equilibrium (5.1), (5.3) of the dynamic systems (5.4)–(5.7) described by the proposed algorithm is also asymptotically stable. All the trajectories along (5.4)–(5.7) eventually converge to the optimum of the resource allocation problem (3.3) with utility functions (5.1).

6.   Numerical examples and analysis

In this section we will analyze the performance of the proposed resource allocation scheme for virtual machines placement. We first consider a simple scenario and discuss the performance of resource allocation scheme, then we will further investigate the performance in some large scale scenarios.

6.1.   A simple scenario

Consider an enterprise user deploying its four applications into a cloud data center, where application 1 and application 3 are both composed of only one component, and application 2 and application 4 both consist of two components. Each component of an application is packaged separately into a virtual machine. There are two physical machines in the cloud data center to complete the deployment of virtual machines.

We all know that CPU is an critical resource of each physical machine. Therefore, we consider the performance of the resource allocation scheme by taking the CPU resource of the physical machines as an example. Assume that the CPU resource capacity of the physical machines is $C = (C_1, C_2) = (1600, 3200)$MIPS, where MIPS (million instructions per second) is an indicator of CPU operation speed. The payment of this enterprise user for its four applications to deploy into the cloud is $w = (w_1, w_2, w_3, w_4) = (1000, 1500, 2000, 2500)$. The step size of the resource allocation scheme is $\kappa = 0.2$, the filtering parameter is $\theta = 0.2$, and the positive constants are $\eta = \varepsilon = 0.01$.

Here we consider the proportional fairness (i.e., $\alpha = 1$) of resource allocation among applications, and depict the performance of the proposed resource allocation scheme in Figure 2. It is not hard to find that the resource allocation scheme can converge to the equilibrium within a certain number of iterations, which is also verified through theoretical analysis in Theorem 3. The optimal prices that the enterprise user has to pay for the physical machines when placing virtual machines and obtaining resource are also illustrated in this figure. We can find they are all equal to the optimal price that each physical machine charges, which has been discussed in Theorem 2. Indeed, the optimal price obtained from this scheme is also equal to the value which is derived from the equation (3.16) (i.e., $\mu^* = {\sum_{s\in S}w_s}/{\sum_{p\in P}C_p} = 7000/4800 = 1.4583$).

Meanwhile, we give the equilibrium value obtained by the resource allocation scheme in Table 1. We also list the optimal solution solved by nonlinear programming software LINGO in the table. We can observe that the proposed scheme is efficient to achieve the optimal resource allocation for virtual machines placement into the cloud data center.

We know there are also some efficient VM placement methods for cloud data centers by applying genetic algorithms. For example, in ^[37] the authors present an energy-efficient VM placement method for cloud data centers by using a hybrid genetic algorithm. We also investigate the resource allocation for VM placement in the cloud center using Particle Swarm Optimization (PSO), a genetic algorithm which was first proposed by Kennedy and Eberhart ^[55]. In the PSO-based resource allocation scheme, the fitness function can be formed by the objective of the resource allocation model and its constraints, which is similar to that in ^[56]. The PSO strategy parameters are chosen as $c1 = c2 = 2$ and $\omega = 1$ so as to guarantee the convergence ^[57].

In order to compare the performance, we first discuss the performance of the proposed resource allocation algorithm, obtain the simulation results with different step sizes, and depict them in the Figure 3(a). It is not difficult to find that as the step size of the proposed scheme increases, the convergence speed increases significantly. Indeed, the convergence performance of the proposed scheme mainly depends on the step size not the number of applications or physical machines. Similarly, we also select different particle swarm sizes and analyze the performance of the PSO-based resource allocation scheme, as shown in Figure 3(b). We can find that the PSO-based scheme converges faster at the beginning, but converges slower near the optimal value. At the same time, as the swarm size increases from 10 to 40, although the convergence speed of the scheme increases, it still cannot effectively converge to the global optimal value within a certain number of iterations.

6.2.   Large scale scenarios

Following the scenario above, we assume the four applications are all composed of two components. The first one component of these four applications is separately packaged into a virtual machine residing on physical machine 1, the second component of applications 1 and 2 is packaged into the corresponding virtual machine residing on physical machine 2, and the second component of applications 3 and 4 is packaged into the virtual machine residing on physical machine 3. The three physical machines have a capacity $C = (C_1, C_2, C_3) = (2400, 1600, 1600)$MIPS of CPU resource to complete the deployment of virtual machines. The resource allocation scheme has the same algorithm parameters as the aforementioned simple scenario. the simulation results are illustrated in Figure 4. We can observe that the optimal resource allocation can be also achieved within a certain number of iterations.

We also analyze the performance of the proposed scheme with different step sizes, and depict the simulation results in Figure 5(a). We find that the convergence speed of the proposed scheme increases significantly as the step size increases. Meanwhile, we also study the performance of PSO-based resource allocation scheme with different swarm sizes and depict the simulation results in Figure 5(b). Similar to Figure 3, the PSO-based scheme converges faster at the beginning, but converges slower when it approaches the optimal value as it is compared with our scheme.

Now we consider the performance of the proposed resource allocation scheme for virtual machines placement of applications in the cloud data center in large scale scenarios, e.g., large numbers of applications as well as physical machines. Here, we assume each application is composed of two components. Each component is packaged into a separate virtual machine which is then placed into the physical machines in the cloud data center. We also take the CPU resource of the physical machines as an example to investigate the performance of the scheme. Each physical machine has a capacity 1600MIPS of its CPU resource. The applications are classified into four categories. The resource allocation scheme has the same parameters as the aforementioned simple scenario. We depict the evolution of agammaegated utility of applications in Figure 6. We observe that the size of applications or physical machines in the cloud data center has no obvious affect on the convergence of the proposed resource allocation scheme. The optimal objective (i.e., the agammaegated utility) increases with the number of applications or physical machines but, in all scenarios, the optimal value is obtained within almost the same number of iterations (e.g., 100 iterations).

7.   Conclusions

With rapid development of the Internet and computer technology, the convenience and cost advantages brought by cloud computing have been adopted by more and more enterprises. At the same time, the resource allocation for virtual machine has become an important key to improve the efficiency and utilization of physical machines. Then, in this paper we establish a resource allocation for virtual machines placement in the cloud data center, deduce the expression of optimal resource allocation for each application, and propose a heuristic algorithm to achieve the optimal resource allocation within a certain number of iterations. We discuss the performance of the proposed resource allocation scheme through theoretical approach and further confirm it with simulation results.

Acknowledgements

The authors would like to thank the support from the National Natural Science Foundation of China (Nos.71971188, 71671159), the Humanity and Social Science Foundation of Ministry of Education of China (No.16YJC630106), the China Postdoctoral Science Foundation (No.2018T110205), the Natural Science Foundation of Hebei Province (Nos.G2018203302, G2020203005), and the project Funded by Hebei Education Department (No.BJ2017029).

Conflict of interest

The authors declare no conflict of interest.