1 Introduction

Recently, the most organizations and corporations have started to invest on cloud computing, leveraging the advantages of service virtualization [1]. In fact, the aim of cloud computing is to optimize the aggregation of resources based on the concept of infrastructures as a service or in abbreviation IaaS. On the other hand, service virtualization is used as a supplementary technology in datacenter (DC) in order to reach a better utilization of network resources. Using virtualization approaches, the resources locating on physical hosts could serve multiple virtual machines (VMs). In fact, virtualization is the heart of cloud computing and has a lot of benefits such as resource utilization, system security capability, near to full efficiency, simple management, and so on [2]. In cloud-based DCs, the controlling operation in order to associate VMs to the appropriate physical hosts is carried out by a central entity, namely broker. Also, the information concerning physical hosts is stored in another entity, namely cloud service provider (CSP). This resource management process is called VM placement and is one of the most crucial issues in context of cloud computing. Interested readers can refer to [3] for a comprehensive survey on cloud brokerage.

Resource management in a typical cloud network includes two major steps: The first step comprises scheduling and workflow operations concerning the task which are submitted by users. As is the case in real-world cloud datacenters, the workload originated from each user is fed into the DC. Each user (known as cloudlet) is bound to a VM. This operation is done by cloud broker. Our research in this paper is not relevant to scheduling step. Interested readers can refer to [4, 5] to study more on this topic. The second step, itself comprises “resource reservation” and “VM placement” operations in which potential players are VMs and physical hosts. Concerning the resource reservation step, a large number of research activities have been carried out in the literature. The goal of many of these researches is to maximize the utilization of resources [6]. Recently, pricing approaches have attracted significant attention of researchers for managing the resource reservation step [7,8,9,10,11,12,13,14,15,16,17]. Any economic-inspired mechanism should address the way in which users’ demands (equivalently VMs’ demands) are met. Here, the goal is to provide maximum welfare for VMs, taking into account minimum power consumption in the DC. The most significant metrics in the context of pricing approaches are economic parameters such as revenue, cost, profit, fairness, economic equilibrium, and so on.

Concerning the VM placement step, significantly, heuristic and metaheuristic approaches have attracted the most attention of researchers [7,8,9, 18,19,20,21,22]. The VM placement is a crucial task and if is done improperly, may degrade the performance of the cloud network. So, almost all researchers have investigated the effects of their modeling on key performance indicators of the DC such as the level of consumed power, latency, CPU usage, memory, bandwidth, and so on.

Actually, the scope of our research in this paper is the second step of cloud computing, namely resource reservation and VM placement. We believe that the mathematical theories of microeconomics are good candidates in order to model the dynamics of VMs in the resource reservation step. To this end, we model the interactions between users and the DC using a pricing approach leveraging the theory of producer–consumer and particularly, the concept of Walrasian equilibrium.

Our contribution is two-fold: First, subject to the resource reservation step, we design a price-based microeconomic mechanism which maximizes the social welfare of VMs by applying the theory of producer–consumer. In the proposed approach, users (or equivalently, VMs associated with users) are considered as consumers of the economic market, and the physical hosts are considered as producers. Also, the bandwidth of requested services plays the role of market commodities. Roughly speaking, by assuming the players as price-taker agents and also by equating the amount of demand and supply, we get the amount of resource (bandwidth) which should be reserved for each VM. In Sect. 3, we will prove that the aggregated utility of all users (the users’ social welfare in microeconomics terminology) could reach to global maximum, known as Pareto efficient point. Then, in the second step, leveraging the identified reserved bandwidth rates in the first step, VMs should be placed on appropriate physical hosts. The placement is done with the aim of minimizing the consumed power. Since the VM placement problem has been proven to be NP-hard, we have used metaheuristic cuckoo search optimization (CSO) algorithm to optimize the placement problem.

To the best of our knowledge, this research is the first work in which the theory of producer–consumer (and the concept of Walrasian equilibrium) has been used in order to optimize the reserved bandwidth in cloud networks. We summarize the main contributions of our research as following:

  • We model the resource reservation phase of cloud network based on producer–consumer theory of microeconomics. All reserved allocations have Walrasian equilibrium property which will be discussed in depth in Sect. 3.

  • For each VM, we consider real-world necessary conditions in order to attain Pareto efficiency concerning the reserved resources.

  • Based on identified reserved resources, our algorithm finds a low-power low-overhead placement solution for VMs.

Due to self-organizing nature of our proposed approach, from industry point of view, it can be used by the owners of cloud providers, especially for long-live services. For example, the users in cloud gaming can be charged based on this approach. Note that in cloud gaming, each gamer session may last for tens of minutes.

The organization of this paper is as follows: In Sect. 2, significant studies related to priced-based approaches and also placement algorithms are described; in Sect. 3, the proposed mechanism is presented and discussed in detail; in Sect. 4, the simulation of this mechanism on the CloudSim testbed and the evaluation results are elaborated; finally, Sect. 5 provides the conclusions and sketches future research directions.

2 Related researches

So far, many studies have been performed on resource reservation and VM placement in cloud networks. In this section, at first, we will review research works related to the subject of resource reservation, and then we will review the works related to VM placement. Some research works have tried to apply pricing approaches, taking into account CSPs and also the geographical location of DCs [23, 24]. Also, interested readers can refer to [7, 14, 15] for comprehensive surveys on pricing approaches in cloud computing. Generally, these pricing mechanisms fail to consider significant factors such as external stakeholders of the market, pricing strategies of other DCs, and the payment tendencies of clients. In cloud networks, “differential pricing” approach is used for allocating bandwidth among some groups of users with different demands in order to maximize profit [8]. This approach is unfair because some users might pay more than the others. Dabbagh et al. [9], proposed a pricing scheme in which the goal is to maximize the profit of a given VM subject to the available budget, while minimizing energy consumption. The proposed approach suffers the lack of considering market competition for determining the price. Wanis et al. [25] used Ramsey pricing to maximize the social welfare of users with respect to this limitation that the profit should not be less than a predetermined threshold value. This pricing scheme has been proposed for allocating virtualized resources in DCs. In some researches like [18], non-cooperative game theory approaches, for example auctions, has been used for maximizing the profit of CSPs. Since Nash equilibrium prerequisite is not guaranteed in all times, investigating the essential conditions of such non-cooperative games is a challenging issue. In the literature, other game-theoretic approaches such as “Stackelberg” games and “bargaining” games have been used for allocating the bandwidth to VMs and satisfying users’ demands [19, 26]. In these categories of games, various bidding approaches such as English, Dutch and Vickrey–Clarke–Groves (VCG) auctions have been used for resource management. The most important disadvantage of these auction-based methods is that they merely consider the satisfaction of one player against the other players, without taking into account the network capacity constraints! Mohammadi and Rezvani [20] are the first who applied the microeconomics theory to model the interactions between VMs and the physical hosts in cloud networks. Their idea, in contrast to game-theoretic approaches, falls into the category of non-strategic economic mechanisms in the sense that the actions of VMs associated with the users do not affect by the actions of other VMs. One of the significant works in the context of pricing is presented by Wu et al. [13]. They proposed a value-based pricing model, namely hedonic pricing model which takes into account both imposed service cost to CSP and willingness of customers to pay. Interested readers can refer to [11, 12, 16, 17] to see other researches in the context of cloud pricing schemes.

Now, we proceed to review the major related works subject to VM placement. The ever-increasing growth of modern DCs turns the VM placement problem a fundamental challenge in the context of cloud computing. According to the previous researches, the VM placement problem falls into the category of NP-hard problems. In the literature, there exist numerous heuristic and metaheuristic approaches for solving these types of problems. For example, in first-fit decreasing (FFD) algorithm, which is presented in [27], the VMs are ordered in descending manner based on requirements and then the host with the least consumed power is selected for placing VMs on it. Jamali et al. [28] used imperialist competitive algorithm to place VMs. In this approach, any possible solution is considered as a country. Imperialist countries will overcome the colonies according to the intermediate countries. The most challenging disadvantage of this metaheuristic scheme is its complexity for selecting initial possible solutions and also the complexity for setting up parameters. Also, Tavakoli-Someh and Rezvani [29] proposed a VM placement solution based on non-dominated sorting genetic algorithm II (NSGA-II) to maximize utilization and minimize energy. As stated in the previous section, the CSO algorithm is an interesting metaheuristic approach which is used for solving VM placement problem. In general, the performance of CSO is better than those of particle swarm optimization (PSO) and genetic algorithm (GA) [27]. Sait et al. [30] used the CSO algorithm for reducing the consumed power and improving the resource utilization of physical hosts. Inspiring Levy flight of cuckoos, the VMs located on physical hosts may migrate to new locations in a best-fit (BF) manner. However, a major weak point of the CSO scheme is its slow convergence speed to find the optimal solution. In order to mitigate this limitation, we have combined CSO with simulated annealing (SA) approach. We will explain details of this, later in Sect. 3.

In the literature, some authors have paid attention to the role of energy considerations in solving the VM placement problem. However, they have not been discussed here in detail due to space limitations. Interested readers can refer to [31,32,33,34] to study more on this topic.

Eventually, it is worth mentioning that in this paper, we have not pay attention to security issues at all. Clearly, the mechanism could be enhanced if such real-world requirements are considered. For example, Feng et al. [35] proposed a joint pricing and security model for insurance cloud networks. Also, Negi et al. [36] proposed a filtering method for cloud computing environments to prevent some kinds of attacks. Interested readers can refer to [37,38,39,40,41] to study more on this topic.

3 Proposed method

3.1 VM bandwidth reservation problem

In this section, we propose the microeconomics-based modeling of interactions in the DC. We use one of the most significant theories in “competitive markets” of microeconomics, known as “producer–consumer theory.” The main characteristic of the competitive economy is that the behaviors of players of the market, i.e., producers and consumers, are influenced by their selfishness. The consumers in this economy have no predetermined tendency to buy the commodities. In other words, the market players accept the price of commodities as they are. It means that they cannot change the prices themselves. In microeconomics terminology, this fact can be expressed as follows: “in competitive economic, the potential players of the market are price-takers not price-setters [42].” Clearly, the competitive economy model is disturbed in nature. As stated before, the producer–consumer theory falls into the category of “non-strategic” mechanisms in the sense that each consumer has complete knowledge about current prices and ignores the demand rates of the other consumers. In other words, the consumer pursues only his/her own optimal demand according to his/her budget constraints. In fact, consumers assure that the commodities are sufficiently available in the market. Similarly, producers have complete knowledge of current prices concerning commodities and are ignoring the demand rate issued by the other producers. Roughly speaking, the producers only choose the levels of production which may create maximum profit for them. The producers believe that commodities will eventually be sold. Regard to the aforementioned discussions, it can be said that the competitive economy has a distributed nature, so that any agent looks for his/her desires and ignores others preferences. In this research, we model interactions of the DC as a competitive economy. In our modeling, physical hosts of the DC are considered as producers of the market. In a similar manner, users (or equivalently, VMs associated with the users) are considered as consumers and the bandwidth unit (bps) of the requested services is considered as the commodities. We name our proposed microeconomic mechanism as “Cloud Network with Competitive Economic,” or in abbreviation CNCE. We summarize the main assumptions of our model as following:

  • Upon joining the network, each customer is endowed a fix amount of budget.

  • The cloud network provides multiple services simultaneously.

  • For each service, the price of bandwidth unit is a predetermined value. These prices are set by service owners.

  • The physical hosts of the DC play the role of producers.

  • The users (VMs) play the role of consumers.

  • The bandwidth unit of each service plays the role of commodity.

Table 1 shows the description of mathematical symbols and notations which are used in this section. We denote the set of VMs by \(\text{VM} = \{ \text{vm}_{1} ,\text{vm}_{2} , \ldots ,\text{vm}_{{N_{{\text{VM}}} }} \}\) in which \(N_{{\text{VM}}}\) represents the total number of VMs. Similarly, the set of physical hosts is denoted by \(H = \{ h_{1} ,h_{2} , \ldots ,h_{{N_{\text{H}} }} \}\) in which \(N_{\text{H}}\) represents the total number of physical hosts. Also, the set of services provided in CNCE is denoted by \(S = \{ s_{1} ,s_{2} , \ldots ,s_{{N_{\text{S}} }} \}\) in which \(N_{\text{S}}\) represents the total number of services. Also, function \(u_{{\text{vm}_{i} }}\) denotes the preferences of every VM in domain \({\mathbb{R}}_{ + }^{N}\). The \(u_{{\text{vm}_{i} }}\) function reveals the utility of virtual machine \(\text{vm}_{i}\) concerning its demanded services. This function meets the conditions in Assumption 1.

Table 1 Mathematical symbols and notations used in reservation step
Full size table

Assumption 1

(Social welfare of VMs) Function \(u_{{\text{vm}_{i} }}\) is continuous, strictly increasing and quasi-concave [42].

In order to meet conditions of Assumption 1, we have designed \(u_{{\text{vm}_{i} }}\) as a logarithmic function. This type of utility function is another form of increasing and concave function called Cobb–Douglas function. Cobb–Douglas function is the most commonly used function in microeconomics and is influenced by demanded bandwidth rate of each consumer. The utility function of virtual machine \(\text{vm}_{i}\) is in the form of Eq. (1). It is equal to weighted sum of utilities resulted from reservation rates of virtual machine \(\text{vm}_{i}\) subject to its demanded services:

$$u_{{{\text{vm}}_{{_{i} }} }} = \sum\limits_{j = 1}^{{N_{\text{S}} }} {w_{{{\text{vm}}_{i} }}^{{s_{j} }} \times \text{Ln}(1 + d_{{{\text{vm}}_{i} }}^{{s_{j} }} )} ,\quad 1 \le i \le N_{{\text{VM}}}$$
(1)

In the above equation, \(w_{{{\text{vm}}_{i} }}^{{s_{j} }}\) denotes the weight (importance) of service \(s_{j}\) for each virtual machine \(\text{vm}_{i}\). These weights are determined by the network owner and are generally application-specific. Clearly, for each virtual machine \(\text{vm}_{i}\), it must be that \(\sum\nolimits_{j = 1}^{{N_{\text{S}} }} {w_{{{\text{vm}}_{i} }}^{{s_{j} }} } = 1\). Also, \(d_{{{\text{vm}}_{i} }}^{{s_{j} }}\) denotes the rate of service \(s_{j}\) which is demanded by virtual machine \(\text{vm}_{i}\).

As mentioned above, each physical host \(h_{l}\) plays the role of producer in CNCE. Let \(g_{{h_{\,l} }}^{{s_{j} }}\) denote the rate of service \(s_{j}\) which is generated by physical host \(h_{l}\). It is clear that the domain of generated services for each host \(h_{l}\) is \({\mathbb{R}}^{{N_{\text{S}} }}\). Also, we assume that each host \(h_{l}\) has a possible service set. The characteristics of possible service set will be introduced later in Assumption 2.

Now, we proceed to formulate the optimization problem of VMs in the CNCE. As explained in Eq. (2), our problem is to maximize the aggregation of utilities concerning all VMs. In microeconomics terminology, it means that we want to maximize the social welfare of VMs. This problem is expressed in Eq. (2) subject to constraints of Eqs. (3)–(5):

$${\text{Max}}\,\,f_{1} = \sum\limits_{i = 1}^{{N_{\text{VM}} }} {u_{{\text{vm}_{i} }} } ,$$
(2)
$${\text{s}}.{\text{t}}.\sum\limits_{j = 1}^{{N_{\text{S}} }} {\left( {d_{{{\text{vm}}_{i} }}^{{s_{j} }} \times p_{{s_{j} }} } \right)} \le \mathop b\nolimits_{{{\text{vm}}_{i} }} ,\quad 1 \le i \le N_{\text{VM}}$$
(3)
$$d_{\rm{min} }^{{s_{j} }} \le d_{{vm_{i} }}^{{s_{j} }} \le d_{\rm{max} }^{{s_{j} }} ,\quad 1 \le j \le N_{\text{S}}$$
(4)
$$\sum\limits_{i = 1}^{{N_{\text{VM}} }} {d_{{{\text{vm}}_{i} }}^{{s_{j} }} } \le \sum\limits_{l = 1}^{{N_{H} }} {g_{{h_{l} }}^{{s_{j} }} } ,\quad 1 \le j \le N_{\text{S}}$$
(5)

The expression in Eq. (3) represents the budget constraint of virtual machine \(\text{vm}_{i}\). The condition in left-hand side of Eq. (3) represents expenditure of virtual machine \(\text{vm}_{i}\) which is the multiplication of rates of its demanded services by the prices of those services. This equation simply states that the expenditure of virtual machine \(\text{vm}_{i}\) should not exceed its budget, \(\mathop b\nolimits_{{\text{vm}_{i} }}\). For each virtual machine \(\text{vm}_{i}\), the budget \(\mathop b\nolimits_{{\text{vm}_{i} }}\) and the demand bandwidth rate \(d_{{\text{vm}_{i} }}^{{s_{j} }}\) are determined a priori. These two parameters are determined by the users in the cloud network. Equation (4) is an application-specific constraint. It states that for each virtual machine \(\text{vm}_{i}\), rates of the demand for each service \(\mathop s\nolimits_{j}\) should be in a range between a minimum and maximum. Equation (5) states that for each service \(\mathop s\nolimits_{j}\), total demands issued by VMs (actually the users) should not exceed the total supply of the hosts. Clearly, the possible areas concerning constraints in Eqs. (3)–(5) are compact. Therefore, the above nonlinear optimization problem will have a global optimum solution. The solution of optimization problem of Eq. (2) is the optimum rates of the demanded services for all virtual machines, i.e., \(\{ d_{{\text{vm}_{i} }}^{{s_{j} }} ,1 \le j \le N_{\text{S}} \}\). These types of problems can be easily solved by optimization approaches such as gradient methods using Kahn–Tucker conditions and by means of common mathematical software tools such as JOM [43].

Now, we proceed to explain the producer problem. The characteristics of possible service set were introduced in Assumption 2.

Assumption 2

(Characteristics of possible service set) Let \(g_{{h_{\,l} }}^{{s_{j} }}\) denote the rate of service \(s_{j}\) which is provided by physical host \(h_{l}\). Then, the possible service supply, \(g_{{h_{\,l} }}^{{s_{j} }}\), should have properties as following [42]:

  1. (a)

    \({\mathbf{0}} \in g_{{h_{l} }}^{{s_{j} }} \subseteq {\mathbb{R}}^{{N_{\text{S}} }}\)

  2. (b)

    \(g_{{h_{\,l} }}^{{s_{j} }}\) is closed and bounded.

  3. (c)

    \(g_{{h_{\,l} }}^{{s_{j} }}\) is convex.

The condition (a) guarantees the boundedness of service production rate from below, i.e., zero boundedness. The condition (b) guarantees the continuity of service production by physical host \(h_{l}\). The condition (c) assures that the provided service from physical host \(h_{l}\) is unique. Therefore, every physical host \(h_{l}\) forms a convex solution area.

As stated before, \(\sum\nolimits_{l = 1}^{{N_{\text{H}} }} {g_{{h_{l} }}^{{s_{j} }} }\) denotes the total supply of hosts concerning the service \(s_{j}\) in which \(N_{\text{H}}\) denotes the number of physical hosts and \(1 \le j \le N_{\text{S}}\). Now, let us formulate the optimization problem of physical hosts, as producers of the market:

$${\text{Max}}\,\,\text{Re} {\text{v}} = \sum\limits_{j = 1}^{{N_{\text{S}} }} {\sum\limits_{l = 1}^{{N_{\text{H}} }} {\left( {g_{{h_{l} }}^{{s_{j} }} \times p_{{s_{j} }} } \right)} }$$
(6)
$${\text{s}}.{\text{t}}.\,\,\sum\limits_{j = 1}^{{N_{\text{S}} }} {g_{{h_{l} }}^{{s_{j} }} } \le g_{{h_{l} }}^{\rm{max} }$$
(7)

The expression in Eq. (6) represents the total revenue earned by producers concerning \(N_{\text{S}}\) services. Equation (7) states that for each physical host \(h_{l}\), the total production bandwidth rate of all services should not exceed the host’s maximum permissible production, \(g_{{h_{\,l} }}^{\rm{max} }\). Here, \(g_{{h_{\,l} }}^{\rm{max} }\) denotes uploading bandwidth of host \(h_{l}\). The solution for optimization problem in Eq. (6) represents the optimum bandwidth rates concerning the generated services by all hosts, i.e., \(\{ g_{{h_{l} }}^{{s_{j} }} ,\quad 1 \le j \le N_{\text{S}} \}\).

As stated before, in equilibrium point of competitive economy, the demands of consumers are met and also the supplied commodities are sold completely. Therefore, for every agent, movements of the other agents can be ignored, and hence the only information the consumer and the producer need is the current price of the market. This fact is the core of Walrasian equilibrium theory. Leon Walras (1834–1910), a French mathematical economist, presented the Walrasian supply and demand equilibrium theory for the first time. The general equilibrium theory attempts to find a vector of prices at which the total demand rates of each commodity is equal to its total supply rates. In the following, we will prove that any reservation in Walrasian equilibrium is a Pareto efficient solution for CNCE and, hence may lead to optimization of VMs’ rates [42].

It is common in microeconomics to show the difference between total demand and total supply of any commodity by a function, named “excess demand.” Before proceed, let us denote the vector of service prices by \({\mathbf{P}} = (p_{{s_{1} }} ,p_{{s_{2} }} , \ldots ,p_{{s_{{N_{\text{S}} }} }} )\). As mentioned before, the number of services provided by the cloud is denoted by \(N_{\text{S}}\). Clearly, the price vector \({\mathbf{P}}\) is \(N_{\text{S}}\)-dimensional. Now, the excess demand of service \(s_{j}\) can be represented as following:

$${\text{ED}}_{{s_{j} }} ({\mathbf{P}}) = \sum\limits_{i = 1}^{{N_{\text{VM}} }} {d_{{\text{vm}_{i} }}^{{s_{j} }} ({\mathbf{P}})} - \sum\limits_{l = 1}^{{N_{\text{H}} }} {g_{{h_{l} }}^{{s_{j} }} ({\mathbf{P}})} ,\quad 1 \le j \le N_{\text{S}}$$
(8)

If \({\text{ED}}_{{s_{j} }} ({\mathbf{P}}) > 0\), then we have extra demand for bandwidth of service \(s_{j}\) and if \({\text{ED}}_{{s_{j} }} ({\mathbf{P}}) < 0\), then we will have extra supply for bandwidth of service \(s_{j}\). In microeconomic, extra demand and extra supply are considered as instability of market. The Walrasian equilibrium price, \({\mathbf{P}}^{*}\) occurs when \({\text{ED}}_{{s_{j} }} ({\mathbf{P}}^{*} ) \gg 0\) for all \(1 \le j \le N_{\text{S}}\). Here, the notation \(\gg\) means “equal or very close to.” According to Assumptions 1 and 2, the existence of equilibrium price vector \({\mathbf{P}}^{*}\) is guaranteed by the following theorem [42]:

Theorem 1

(Walrasian equilibrium in CNCE) If any virtual machine\(\text{vm}_{i}\)meets Assumption (1) and any physical host\(h_{l}\)meets conditions in Assumption (2), then there exists at least one price vector\({\mathbf{P}}^{*}\)in which\({\text{ED}}_{{s_{j} }} ({\mathbf{P}}^{*} ) \gg 0\) for all \(1 \le j \le N_{\text{S}}\).

Proof

Before we proceed, let us emphasize on two important facts. The first is that although Cobb–Douglas utility function is not strongly increasing on \({\mathbb{R}}_{ + }^{{N_{\text{S}} }}\), it guarantees the existence of Walrasian equilibrium. Second, when utilities satisfy Assumption 1, the excess demand vector will be homogeneous of degree zero. Interested readers can refer to pages 204–212 of [42] to see the proof of these theories. The key importance of homogeneity is that only relative prices matter in VMs’ choices. Thus, subject to homogeneity property, we will have \({\text{ED}}_{{s_{j} }} ({\mathbf{P}}^{*} ) = {\text{ED}}_{{s_{j} }} (\lambda \cdot {\mathbf{P}}^{*} ) = {\mathbf{0}}\) for all \(\lambda > 0\). So, should there exist some set of prices at which all markets clear. Also, any price vector which is obtained from multiplying that price by \(\lambda\) will also clear the CNCE market. This fact can simplify the calculations.□

Example 1

Let us consider a two-person two-service CNCE and solve it to get a Walrasian equilibrium. We assume that VMs (users) \({\text{vm}}_{1}\) and \({\text{vm}}_{2}\) have identical utility functions,

$$u_{{{\text{vm}}_{i} }} \left( {d_{{{\text{vm}}_{i} }}^{{s_{1} }} ,d_{{{\text{vm}}_{i} }}^{{s_{2} }} } \right) = \left( {\mathop {d_{{{\text{vm}}_{i} }}^{{s_{1} }} }\nolimits^{\rho } + \mathop {d_{{{\text{vm}}_{i} }}^{{s_{2} }} }\nolimits^{\rho } } \right)^{{\frac{1}{\rho }}} \quad i = 1,2,$$
(9)

where \(0 < \rho < 1\). In microeconomics, the above function is known as constant elasticity of substitution (CES) utility function. It can easily be verified that Eq. (9) is strictly monotonic and strictly convex. Suppose there be 1 unit of each service and each consumer owns all of one service, so initial endowments concerning the consumers are \({\mathbf{e}}_{{{\text{vm}}_{{_{1} }} }} (1,0)\) and \({\mathbf{e}}_{{{\text{vm}}_{{_{2} }} }} (0,1)\). Because the total endowment of each service is strictly positive and Eq. (9) is strongly increasing and strictly quasi-concave on \({\mathbb{R}}_{ + }^{{N_{\text{S}} }}\) when \(0 < \rho < 1\), the requirements of Theorem 1 are satisfied, so we make sure that a Walrasian equilibrium exists in this economy. Now in order to obtain the demand functions concerning users, let us define the following optimization problem inspiring from Eqs. (2)–(3):

$${\text{Max}}\,u_{{{\text{vm}}_{{_{i} }} }} \left( {d_{{{\text{vm}}_{i} }}^{{s_{1} }} ,d_{{{\text{vm}}_{i} }}^{{s_{2} }} } \right) = \left( {\mathop {d_{{{\text{vm}}_{i} }}^{{s_{1} }} }\nolimits^{\rho } + \mathop {d_{{{\text{vm}}_{i} }}^{{s_{2} }} }\nolimits^{\rho } } \right)^{{\frac{1}{\rho }}} \quad i = 1,2$$
(10)
$${\text{s}}.{\text{t}}.\,\,d_{{{\text{vm}}_{i} }}^{{s_{1} }} \cdot p_{{s_{1} }} + d_{{{\text{vm}}_{i} }}^{{s_{2} }} \cdot p_{{s_{2} }} \le \mathop b\nolimits_{{{\text{vm}}_{i} }} \quad i = 1,2$$
(11)

To solve the above nonlinear optimization problem, at first, we define Lagrangian function:

$$L\left( {d_{{{\text{vm}}_{i} }}^{{s_{1} }} ,d_{{{\text{vm}}_{i} }}^{{s_{2} }} ,\lambda } \right) = \left( {\mathop {d_{{{\text{vm}}_{i} }}^{{s_{1} }} }\nolimits^{\rho } + \mathop {d_{{{\text{vm}}_{i} }}^{{s_{2} }} }\nolimits^{\rho } } \right)^{{\frac{1}{\rho }}} - \lambda \cdot \left( {d_{{{\text{vm}}_{i} }}^{{s_{1} }} \cdot p_{{s_{1} }} + d_{{{\text{vm}}_{i} }}^{{s_{2} }} \cdot p_{{s_{2} }} - \mathop b\nolimits_{{{\text{vm}}_{i} }} } \right)$$
(12)

Now, we form the first-order Lagrangian Kuhn–Tucker conditions as following:

$$\frac{\partial L}{{\partial d_{{{\text{vm}}_{i} }}^{{s_{1} }} }} = \left( {\mathop {d_{{{\text{vm}}_{i} }}^{{s_{1} }} }\nolimits^{\rho } + \mathop {d_{{{\text{vm}}_{i} }}^{{s_{2} }} }\nolimits^{\rho } } \right)^{{\frac{1}{\rho } - 1}} \cdot \mathop {d_{{{\text{vm}}_{i} }}^{{s_{1} }} }\nolimits^{\rho - 1} - \lambda \cdot p_{{s_{1} }} = 0,$$
(13)
$$\frac{\partial L}{{\partial d_{{{\text{vm}}_{i} }}^{{s_{2} }} }} = \left( {\mathop {d_{{{\text{vm}}_{i} }}^{{s_{1} }} }\nolimits^{\rho } + \mathop {d_{{{\text{vm}}_{i} }}^{{s_{2} }} }\nolimits^{\rho } } \right)^{{\frac{1}{\rho } - 1}} \cdot \mathop {d_{{{\text{vm}}_{i} }}^{{s_{2} }} }\nolimits^{\rho - 1} - \lambda \cdot p_{{s_{2} }} = 0,$$
(14)
$$\frac{\partial L}{\partial \lambda } = p_{{s_{1} }} \cdot d_{{{\text{vm}}_{i} }}^{{s_{1} }} + p_{{s_{2} }} \cdot d_{{{\text{vm}}_{i} }}^{{s_{2} }} - \mathop b\nolimits_{{{\text{vm}}_{i} }} = 0,$$
(15)

As is evident, we have three equations in three unknowns. After rearranging and simplifying Eqs. (13)–(15), we have:

$$d_{{{\text{vm}}_{i} }}^{{s_{1} }} = d_{{{\text{vm}}_{i} }}^{{s_{2} }} \cdot \left( {\frac{{p_{{s_{1} }} }}{{p_{{s_{2} }} }}} \right)^{{\frac{1}{\rho - 1}}} ,$$
(16)
$$\mathop b\nolimits_{{{\text{vm}}_{i} }} = p_{{s_{1} }} \cdot d_{{{\text{vm}}_{i} }}^{{s_{1} }} + p_{{s_{2} }} \cdot d_{{{\text{vm}}_{i} }}^{{s_{2} }} ,$$
(17)

After substituting Eq. (16) in Eq. (17), we have:

$$\begin{aligned} \mathop b\nolimits_{{{\text{vm}}_{i} }} & = p_{{s_{1} }} \cdot d_{{{\text{vm}}_{i} }}^{{s_{1} }} \cdot \left( {\frac{{p_{{s_{1} }} }}{{p_{{s_{2} }} }}} \right)^{{\frac{1}{\rho - 1}}} + p_{{s_{2} }} \cdot d_{{{\text{vm}}_{i} }}^{{s_{2} }} , \\ & = d_{{{\text{vm}}_{i} }}^{{s_{2} }} \left( {p_{{s_{1} }}^{{\frac{\rho }{\rho - 1}}} + p_{{s_{2} }}^{{\frac{\rho }{\rho - 1}}} } \right) \cdot p_{{s_{2} }}^{{\frac{ - 1}{\rho - 1}}} \\ \end{aligned}$$
(18)

By solving Eq. (18) for \(d_{{{\text{vm}}_{i} }}^{{s_{2} }}\), we have:

$$d_{{{\text{vm}}_{i} }}^{{s_{2} }} = \frac{{p_{{s_{2} }}^{{\frac{1}{\rho - 1}}} \cdot \mathop b\nolimits_{{{\text{vm}}_{i} }} }}{{p_{{s_{1} }}^{{\frac{\rho }{\rho - 1}}} + p_{{s_{2} }}^{{\frac{\rho }{\rho - 1}}} }},$$
(19)

Now, substituting from (19) into (16) gives us \(d_{{{\text{vm}}_{i} }}^{{s_{1} }}\):

$$d_{{{\text{vm}}_{i} }}^{{s_{1} }} = \frac{{p_{{s_{1} }}^{{\frac{1}{\rho - 1}}} \cdot \mathop b\nolimits_{{{\text{vm}}_{i} }} }}{{p_{{s_{1} }}^{{\frac{\rho }{\rho - 1}}} + p_{{s_{2} }}^{{\frac{\rho }{\rho - 1}}} }},$$
(20)

Equations (19) and (20) are known as Marshallian demand functions. By defining \(r = \rho /(\rho - 1)\), we can rewrite the final Marshallian demands regard to two VMs, namely \({\text{vm}}_{1}\) and \({\text{vm}}_{2}\) as:

$$d_{{{\text{vm}}_{i} }}^{{s_{1} }} ({\mathbf{P}},\mathop b\nolimits_{{{\text{vm}}_{i} }} ) = \frac{{p_{{s_{1} }}^{r - 1} \cdot \mathop b\nolimits_{{{\text{vm}}_{i} }} }}{{p_{{s_{1} }}^{r} + p_{{s_{2} }}^{r} }},$$
(21)
$$d_{{{\text{vm}}_{i} }}^{{s_{2} }} ({\mathbf{P}},\mathop b\nolimits_{{{\text{vm}}_{i} }} ) = \frac{{p_{{s_{2} }}^{r - 1} \cdot \mathop b\nolimits_{{{\text{vm}}_{i} }} }}{{p_{{s_{1} }}^{r} + p_{{s_{2} }}^{r} }},$$
(22)

As can be seen from the above equations, the solution to the problem of each consumer \({\text{vm}}_{i}\) in CNCE only depends on the prices of services, namely \(p_{{s_{1} }}\), \(p_{{s_{2} }}\), and also the initial budget of customer, namely \(\mathop b\nolimits_{{{\text{vm}}_{i} }}\).Now, let us assume that the budget of each user is equal to the market value of the endowment, so \(\mathop b\nolimits_{{{\text{vm}}_{1} }} = {\mathbf{P}} \cdot \mathop {\mathbf{e}}\nolimits_{{{\text{vm}}_{1} }} = p_{{s_{1} }}\) and \(\mathop b\nolimits_{{{\text{vm}}_{2} }} = {\mathbf{P}} \cdot \mathop {\mathbf{e}}\nolimits_{{{\text{vm}}_{2} }} = p_{{s_{2} }}\). Recall from Theorem 1 that there exists an equilibrium in which all prices are strictly positive. Taking this into account and also regard to this fact that only relative prices matter, leads us to choose a convenient normalization to simplify calculations. Let \({\bar{\mathbf{P}}} \equiv (1/p_{{s_{2} }} ) \cdot {\mathbf{P}}\). Here, \(\bar{p}_{{s_{1} }} \equiv p_{{s_{1} }} /p_{{s_{2} }}\) and \(\bar{p}_{{s_{2} }} \equiv 1\). So, \(p_{{s_{1} }}\) is just the relative price of the service \(s_{1}\). Because each consumer’s demand at \({\mathbf{P}}\) is the same as the demand at \({\bar{\mathbf{P}}}\), our problem is equivalent with problem of finding an equilibrium set of relative prices, \({\bar{\mathbf{P}}}\). Now, consider the market for service \(s_{1}\). Assuming an interior solution, the necessary condition to establish the equilibrium is that the total supply equates the total demand at price \({\bar{\mathbf{P}}}^{*}\). In other words, we must have

$$d_{{{\text{vm}}_{1} }}^{{s_{1} }} ({\bar{\mathbf{P}}}^{*} ,{\bar{\mathbf{P}}}^{*} \cdot \mathop {\mathbf{e}}\nolimits_{{{\text{vm}}_{1} }} ) + d_{{{\text{vm}}_{2} }}^{{s_{1} }} ({\bar{\mathbf{P}}}^{*} ,{\bar{\mathbf{P}}}^{*} \cdot \mathop {\mathbf{e}}\nolimits_{{{\text{vm}}_{2} }} ) = e_{{{\text{vm}}_{1} }}^{{s_{1} }} + e_{{{\text{vm}}_{2} }}^{{s_{1} }} ,$$
(23)

Considering Eqs. (21)–(22) and the above discussion, this requires

$$\frac{{\mathop {\bar{p}_{{s_{1} }}^{*} }\nolimits^{r - 1} \cdot \bar{p}_{{s_{1} }}^{*} }}{{\mathop {\bar{p}_{{s_{1} }}^{*} }\nolimits^{r} + 1}} + \frac{{\mathop {\bar{p}_{{s_{1} }}^{*} }\nolimits^{r - 1} }}{{\mathop {\bar{p}_{{s_{1} }}^{*} }\nolimits^{r} + 1}} = 1,$$
(24)

Solving, we obtain \(\bar{p}^{*}_{{s_{1} }} = 1\). We conclude that any vector \({\mathbf{P}}^{*}\) where \(p^{*}_{{s_{1} }} = p^{*}_{{s_{2} }}\), equates demand and supply in market \(s_{1}\). By Walras’ law, those same prices must equate demand and supply in market \(s_{2}\), so we are done.□

Based on above explanations, in order to reach the Walrasian equilibrium price vector \({\mathbf{P}}^{*}\), the controller of CNCE should increase the price of each service \(s_{j}\) gradually when \({\text{ED}}_{{s_{j} }} ({\mathbf{P}}) > 0\). In contrast, the controller should decrease the price of each service \(s_{j}\) gradually when \({\text{ED}}_{{s_{j} }} ({\mathbf{P}}) < 0\). In this way, after finite number of iterations the market will reach to equilibrium price vector \({\mathbf{P}}^{*}\) in which \({\text{ED}}_{{s_{j} }} ({\mathbf{P}}^{*} ) \gg 0\) for all \(1 \le j \le \,N_{\text{S}}\).

Definition 1

(Walrasian Equilibrium Allocations (WEAs)) Let \({\mathbf{P}}^{*}\) be a Walrasian equilibrium for CNCE with initial endowments \({\mathbf{e}}\), and let

$${\mathbf{d}}({\mathbf{P}}^{*} ) \equiv \left( {{\mathbf{d}}_{{{\text{vm}}_{1} }} \left( {{\mathbf{P}}^{*} ,{\mathbf{P}}^{*} \cdot {\mathbf{e}}_{{{\text{vm}}_{1} }} ,{\mathbf{d}}_{{{\text{vm}}_{2} }} ({\mathbf{P}}^{*} ,{\mathbf{P}}^{*} \cdot {\mathbf{e}}_{{{\text{vm}}_{2} }} } \right), \ldots ,{\mathbf{d}}_{{{\text{vm}}_{{N_{\text{VM}} }} }} \left( {{\mathbf{P}}^{*} ,{\mathbf{P}}^{*} \cdot {\mathbf{e}}_{{{\text{vm}}_{{N_{\text{VM}} }} }} } \right)} \right),$$
(25)

where each element \({\mathbf{d}}_{{{\text{vm}}_{i} }} ({\mathbf{P}}^{*} ,{\mathbf{P}}^{*} \cdot \mathop {\mathbf{e}}\nolimits_{{{\text{vm}}_{i} }} )\) denotes the demand of virtual machine \({\text{vm}}_{i}\) subject to \(N_{\text{S}}\) services at prices \({\mathbf{P}}^{*}\). The term \({\mathbf{d}}({\mathbf{P}}^{*} )\) in Eq. (25) denotes a Walrasian equilibrium allocation, or WEA.

Now, let us assume that CNCE is a competitive economy with initial endowments e as following:

$${\mathbf{e}} \equiv ({\mathbf{e}}_{{{\text{vm}}_{1} }} ,{\mathbf{e}}_{{{\text{vm}}_{2} }} , \ldots ,{\mathbf{e}}_{{{\text{vm}}_{{N_{\text{VM}} }} }} )$$
(26)

Also, let \(F({\mathbf{e}})\) denote feasible allocations in CNCE:

$$F({\mathbf{e}}) \equiv \left\{ {{\mathbf{d}}\left| {\sum\limits_{i = 1}^{{N_{\text{VM}} }} {{\mathbf{d}}_{{{\text{vm}}_{i} }} } = \sum\limits_{i = 1}^{{N_{\text{VM}} }} {{\mathbf{e}}_{{{\text{vm}}_{i} }} } } \right.} \right\}$$
(27)

Now, we outline two significant lemmas without proof. These lemmas will be used in proof of Pareto optimality later.

Lemma 1

Let\({\mathbf{P}}^{*}\)be a Walrasian equilibrium for CNCE with initial endowments\({\mathbf{e}}\)as defined in Eq. (26). Also, let\({\mathbf{d}}({\mathbf{P}}^{*} )\)be the WEA of CNCE as defined in Eq. (25). Then\({\mathbf{d}}({\mathbf{P}}^{*} ) \in F({\mathbf{e}})\).

Lemma 2

Suppose the demand function of virtual machine\({\text{vm}}_{i}\), namely\(u_{{{\text{vm}}_{{_{i} }} }}\), is well-defined at\({\mathbf{P}} \ge {\mathbf{0}}\)and is strictly increasing on\({\mathbb{R}}_{ + }^{{N_{\text{S}} }}\). Also suppose that it is equal to\({\hat{\mathbf{d}}}_{{{\text{vm}}_{i} }}\), and that\({\mathbf{d}}_{{{\text{vm}}_{i} }} \in {\mathbb{R}}_{ + }^{{N_{\text{S}} }}\).

  1. 1.

    if \(u_{{{\text{vm}}_{{_{i} }} }} ({\mathbf{d}}_{{{\text{vm}}_{i} }} ) > u_{{{\text{vm}}_{{_{i} }} }} ({\hat{\mathbf{d}}}_{{{\text{vm}}_{i} }} )\), then \({\mathbf{P}} \cdot {\mathbf{d}}_{{{\text{vm}}_{i} }} > {\mathbf{P}} \cdot {\hat{\mathbf{d}}}_{{{\text{vm}}_{i} }}\).

  2. 2.

    if \(u_{{{\text{vm}}_{{_{i} }} }} ({\mathbf{d}}_{{{\text{vm}}_{i} }} ) \ge u_{{{\text{vm}}_{{_{i} }} }} ({\hat{\mathbf{d}}}_{{{\text{vm}}_{i} }} )\), then \({\mathbf{P}} \cdot {\mathbf{d}}_{{{\text{vm}}_{i} }} \ge {\mathbf{P}} \cdot {\hat{\mathbf{d}}}_{{{\text{vm}}_{i} }}\).

In microeconomics, the WEAs include allocations of services to users that lie on the core of those economies. Our goal at this moment is to prove that WEAs have this property in arbitrary economies such as CNCE. Let \(C({\mathbf{e}})\) denote the set of allocations in the core.

Theorem 2

(Core and Equilibria in Competitive CNCE Economies) Consider an exchange economy\((u_{{{\text{vm}}_{{_{i} }} }} ,{\mathbf{d}}_{{{\text{vm}}_{i} }} ),\quad 1 \le i \le N_{\text{VM}}\). If each user’s utility function,\(u_{{{\text{vm}}_{{_{i} }} }}\), is strictly increasing on\({\mathbb{R}}_{ + }^{{N_{\text{S}} }}\), then every WEA is in the core. Formally speaking,

$$W({\mathbf{e}}) \subset C({\mathbf{e}})$$
(28)

Proof

Simply speaking, the theorem says that if \({\mathbf{d}}({\mathbf{P}}^{*} )\) is a WEA for equilibrium prices \({\mathbf{P}}^{*}\), then \({\mathbf{d}}({\mathbf{P}}^{*} ) \in C({\mathbf{e}})\). To prove it, we use proof by contradiction. So, let us suppose \({\mathbf{d}}({\mathbf{P}}^{*} )\) is a WEA, and \({\mathbf{d}}({\mathbf{P}}^{*} ) \notin C({\mathbf{e}})\). Since \({\mathbf{d}}({\mathbf{P}}^{*} )\) is a WEA, from Lemma 1 it must be that \({\mathbf{d}}({\mathbf{P}}^{*} ) \in F({\mathbf{e}})\), so \({\mathbf{d}}({\mathbf{P}}^{*} )\) is feasible. However, because \({\mathbf{d}}({\mathbf{P}}^{*} ) \notin C({\mathbf{e}})\), we can find a coalition \(S\) and a new allocation \({\mathbf{d^{\prime}}}\) such that

$$\sum\limits_{i \in \,S} {{\mathbf{d}}_{{{\text{vm}}_{i} }}^{{\prime }} } = \sum\limits_{i \in S} {{\mathbf{e}}_{{{\text{vm}}_{i} }} }$$
(29)

And,

$$u_{{{\text{vm}}_{{_{i} }} }} ({\mathbf{d}}_{{{\text{vm}}_{i} }}^{{\prime }} ) \ge u_{{{\text{vm}}_{{_{i} }} }} ({\mathbf{d}}_{{{\text{vm}}_{1} }} ({\mathbf{P}}^{*} ,{\mathbf{P}}^{*} \cdot \mathop {\mathbf{e}}\nolimits_{{{\text{vm}}_{1} }} ),\quad i \in S$$
(30)

Equation (29) implies

$${\mathbf{P}}^{*} \cdot \sum\limits_{i \in S} {{\mathbf{d}}_{{{\text{vm}}_{i} }}^{{\prime }} } = {\mathbf{P}}^{*} \cdot \sum\limits_{i \in S} {{\mathbf{e}}_{{{\text{vm}}_{i} }} }$$
(31)

Now from Eq. (30) and Lemma 2, we know that for each \(i \in S\), we must have

$${\mathbf{P}}^{*} \cdot {\mathbf{d}}_{{{\text{vm}}_{i} }}^{{\prime }} \ge {\mathbf{P}}^{*} \cdot {\mathbf{d}}_{{{\text{vm}}_{1} }} ({\mathbf{P}}^{*} ,{\mathbf{P}}^{*} \cdot \mathop {\mathbf{e}}\nolimits_{{{\text{vm}}_{1} }} ) = {\mathbf{P}}^{*} \cdot \mathop {\mathbf{e}}\nolimits_{{{\text{vm}}_{1} }} .$$
(32)

Integrating over all users in S, we have

$${\mathbf{P}}^{*} \cdot \sum\limits_{i \in S} {{\mathbf{d}}_{{{\text{vm}}_{i} }}^{{\prime }} } > {\mathbf{P}}^{*} \cdot \sum\limits_{i \in S} {{\mathbf{e}}_{{{\text{vm}}_{i} }} }$$
(33)

Equation (33) contradicts Eq. (31). Thus, assuming the proposition to be false leads to a contradiction. Finally, it is concluded that \({\mathbf{d}}({\mathbf{P}}^{*} ) \in C({\mathbf{e}})\) and the theorem is proved.□

Now, we proceed to state the most important theory which proves that the competitive outcomes, such as CNCE, are Pareto efficient! In microeconomics, this is known as First Welfare Theorem.

Theorem 3

(First Welfare Theorem) Under the hypotheses of Theorem2, every WEA is Pareto efficient.

Proof

In Theorem 2, we proved that every WEA is in the core. Taking this into account and also with respect to this fact that all core allocations are Pareto efficient, immediately proves the theorem!□

Figure 1 demonstrates the CNCE architecture along with the main activities in microeconomic-based bandwidth reservation scheme. As is evident in Fig. 1, in order to control the CNCE market, we have used an entity, named “broker.” The broker node is responsible for computing Walrasian equilibrium price and informing that price to all physical hosts and all VMs. To this end, the broker at first gathers the required information concerning VMs and hosts. This information includes the service demand, budget, and downloading capacity of VMs. Note that the information concerning physical hosts is typically sored on broker. After calculating Walrasian equilibrium Pareto efficient bandwidth rates, the broker sends the demand reservation rates back to VMs.

Fig. 1
figure 1

Major activities in the CNCE architecture

Full size image

We now proceed to explain the messaging of the proposed algorithm. Figure 2 shows the primitives and transferred messages between network entities in resource reservation step of CNCE (see upper half of the figure). In summary, it can be said that in the first step of mechanism, the optimal reserved bandwidth rate for every VM is obtained based on the concept of Walrasian general equilibrium. Table 2 represents the bandwidth reservation messages in CNCE with their description and direction among VMs, broker and physical hosts. Also contents of messages are shown in Table 3. As stated before, every virtual machine has a demand rate function which is based on service price. Every virtual machine \(\text{vm}_{i}\) sends a VJR message to the broker. A VJR message contains parameters like service demand, budget, and downloading capacity of virtual machine \(\text{vm}_{i}\). On the other hand, CSP node sends a PJR message to the broker. As is the case in real-world cloud datacenters, the CSP node stores all required parameters of physical hosts. A PJR message contains parameters like the aggregation of production functions subject to all physical hosts. From this point forward, the broker identifies the characteristics of VMs and hosts and indeed can compute the Walrasian general equilibrium optimum price for demands of VMs and hosts. The broker sends the calculated demands to all nodes using WPM message and also modifies the price vector for upcoming requests using the excess demand, as described before in Eq. (8). The CSP, in turn, will send the equilibrium price and other required information back to physical hosts. At this point, the bandwidth reservation step is finished. From this point forward, the VM placement routine will be started.

Fig. 2
figure 2

Primitives of CNCE in both steps: bandwidth reservation step and VM placement step

Full size image
Table 2 Description and direction of CNCE messages in bandwidth reservation step
Full size table
Table 3 Contents of CNCE messages in bandwidth reservation step
Full size table

3.2 VM placement problem

We now proceed to describe the VM placement step and its protocol. As discussed before, the bandwidth reservation step uses the producer–consumer theory and also leverages the concept of Walrasian equilibrium. This process determines the optimal demands of bandwidth rates for all VMs. Now, in second step, we aim to place VMs on appropriate hosts in such a way that the consumed power in the DC is minimized. In order to solve the VM placement problem, we use the approach of [28] with some modifications. The description of mathematical symbols and notations which are used in this section is given in Table 4.

Table 4 Mathematical symbols and notations used in VM placement step
Full size table

Let \(\eta_{i}\) denote the CPU utilization concerning the physical host \(h_{\,i}\). Similar to [28], we can compute \(\eta_{i}\) as following:

$$\eta_{i} = \frac{{\sum\nolimits_{j = 1}^{{N_{\text{VM}} }} {x_{ij} \cdot {\text{cpu}}_{j} } }}{{{\text{cpu}}_{i}^{\rm{max} } }},\quad x_{ij} \in \{ 0,1\} ,\quad 1 \le i \le N_{\text{H}},$$
(34)

where \(x_{ij}^{{}}\) denotes a binary variable which equals 1 if virtual machine \(\text{vm}_{j}\) is placed on the physical host \(h_{\,i}\) and is zero otherwise. Simply, Eq. (34) aggregates the total CPU usage of all VMs running on physical host \(h_{\,i}\), and then divides the total CPU usage by maximum affordable CPU in host \(h_{\,i}\).

Previous studies, for example [28], have shown that the consumed power of a real-world server scales linearly with CPU utilization. So, we define the consumed power of physical host \(h_{\,i}\) with the following equation:

$${\text{pow}}_{i} = \left( {{\text{pow}}_{i}^{\text{busy}} - {\text{pow}}_{i}^{\text{idle}} } \right) \cdot \eta_{i} + {\text{pow}}_{i}^{\text{idle}}$$
(35)

where \({\text{pow}}_{i}^{\text{busy}}\) and \({\text{pow}}_{i}^{\text{idle}}\) denote consumed power of physical host \(h_{\,i}\) in active mode and passive mode, respectively.

Now, we outline the power-aware VM placement problem:

$${\text{Min}}\,\, f_{2} = \sum\limits_{i = 1}^{{N_{\text{H}} }} {y_{i} \cdot {\text{pow}}_{i} }$$
(36)
$${\text{s}}.{\text{t}}. \quad \sum\limits_{j = 1}^{{N_{\text{VM}} }} {x_{ij} } = 1,\quad 1 \le i \le N_{\text{H}}$$
(37)
$$\sum\limits_{j = 1}^{{N_{\text{VM}} }} {x_{ij} \cdot {\text{cpu}}_{j} } \le y_{i} \cdot {\text{cpu}}_{i}^{\rm{max} } ,\quad 1 \le i \le N_{\text{H}}$$
(38)
$$\sum\limits_{j = 1}^{{N_{\text{VM}} }} {x_{ij} \cdot {\text{mem}}_{j} } \le y_{i} \cdot {\text{mem}}_{i}^{\rm{max} } ,\quad 1 \le i \le N_{\text{H}}$$
(39)
$$\sum\limits_{j = 1}^{{N_{\text{VM}} }} {x_{ij} \cdot \sum\limits_{k = 1}^{{N_{\text{S}} }} {d_{{\text{vm}_{j} }}^{{s_{k} }} } } \le y_{i} \cdot bw_{i}^{\rm{max} } ,\quad 1 \le i \le N_{\text{H}}$$
(40)
$$x_{ij} ,y_{i} \in \{ 0,1\} ,\quad 1 \le i \le N_{\text{H}} ,\quad 1 \le j \le N_{\text{VM}}$$
(41)

The problem defined in Eq. (36) seeks to minimize the aggregation consumed power of all selected physical hosts. As stated before, \(x_{ij}^{{}}\) denotes a binary variable which equals 1 if any virtual machine \(\text{vm}_{j}\) is placed on the physical host \(h_{\,i}\) and is zero otherwise. Similarly,\(y_{i}^{{}}\) denotes a binary variable which equals 1 if the physical host \(h_{\,i}\) is selected, and is zero otherwise. The constraint in Eq. (37) guarantees that each VM is merely placed on exactly one physical host. The constraint in Eq. (38) refers to the CPU usage limitation. The left-hand side expression in Eq. (38) calculates the aggregation of CPU usages subject to all virtual machines which are placed on the same physical host \(h_{\,i}\). The right-hand side expression represents the maximum CPU which is affordable by the designated host \(h_{\,i}\). Constraints in Eqs. (39) and (40) are similar to Eq. (38), but subject to memory usage and demanded bandwidth, respectively. The term \(\sum\nolimits_{k = 1}^{{N_{\text{S}} }} {d_{{{\text{vm}}_{j} }}^{{s_{k} }} }\) in Eq. (40) calculates the aggregation of required bandwidth which is demanded by virtual machine \(\text{vm}_{j}\) concerning all services. In order to remember the explanations about \(d_{{\text{vm}_{j} }}^{{s_{k} }}\), refer to Sect. 3.1 and Eqs. (2)–(5).

It has been proven previously that the VM placement problem is NP-hard [44]. Metaheuristic approaches are used extensively to reduce the time complexity of NP-hard problems. In the previous researches like [30], the advantages of cuckoo search optimization (CSO) algorithm, as an efficient metaheuristic approach have been investigated. Authors in [27] showed that the performance of CSO is better than PSO and GA approaches [27]. Therefore, we have used CSO algorithm to solve the VM placement step. As explained in detail in Sect. 3.1, the major contribution of this research is in designing microeconomics-based bandwidth reservation mechanism. However, our minor contribution is modifications which we have applied to CSO for the VM placement step. Due to space limitations, we omit detailed descriptions of VM placement with CSO. Interested readers can refer to [30] to see the full procedure. Here, we only highlight the modifications which we have made to VM placement with CSO. In the CSO algorithm, determination of initial radius of cuckoos (VMs) for oviparity in nests (hosts) is carried out in random space. The randomness of initial radius of cuckoos’ nests may force them not to place their eggs in a uniform search space. Therefore, it is likely for a group of cuckoos to locate in the same radius, which in turn, results in slow convergence of the CSO algorithm. We have made some modifications in initial random selection of cuckoos’ nests which results in more fairness in distribution of the nests. For this purpose, at first, we determine the number of cuckoos at bootstrap. Then, we divide the search space by the number of initial cuckoos in order to determine the radius for cuckoo oviparity. Using Eq. (42), the difference between upper bound and lower bound is obtained and is divided by the number of cuckoos.

$${\text{Dist}} = \left( {{\text{UB}}_{\text{old}} - {\text{LB}}_{\text{old}} } \right)/{\text{Num}}\,{\text{Cuckoos}}$$
(42)

The search space should be changed using the oviparity distance obtained from Eq. (42). Note that the lower bound threshold should not be changed but the upper bound threshold will be equal to lower bound plus the oviparity radius. So, we have:

$${\text{LB}}_{\text{New}} = {\text{LB}}_{\text{old}}$$
(43)
$${\text{UB}}_{\text{New}} = {\text{LB}}_{\text{New}} + {\text{Dist}}$$
(44)

As shown in Fig. 3, for new coming cuckoos, the calculated distance will be added to the upper bound and the lower bound thresholds:

Fig. 3
figure 3

Illustration of the proposed idea for fair distribution of cuckoo eggs across search space before oviparity

Full size image
$${\text{LB}}_{\text{New}} = {\text{LB}}_{\text{New}} + {\text{Dist}}$$
(45)
$${\text{UB}}_{\text{New}} = {\text{UB}}_{\text{New}} + {\text{Dist}}$$
(46)

Based on the CSO algorithm, VMs are fairly distributed in search space and after oviparity, some of eggs are destroyed. One of the important sections of the CSO algorithm is levy flight of cuckoos for immigration after eggs maturation. Authors in [44] proposed an approach which combines GA with simulated annealing (SA) in order to minimize the energy consumption of the cloud datacenter. This algorithm falls into the category of metaheuristic approaches. Typically, metaheuristic optimization approaches help to avoid trapping in local optima. The main concept of SA has been inspired from annealing process of metals in metallurgy [44]. Figure 4 demonstrates the modifications which we have made in CSO by SA algorithm in order to place VMs optimally.

Fig. 4
figure 4

Flowchart of modified cuckoo search optimization (CSO&SA) algorithm combined with simulated annealing (SA) for VM placement step

Full size image

Some examples of placements in levy flight are demonstrated in Figs. 5 and 6 based on SA algorithm. In each figure, the upper array is resulted from previous steps of CSO algorithm (the number of eggs, oviparity radius and nest selection). In this array, the index of each cell represents the identification of associated VM. Also, the content of each cell shows the identification of physical host.

Fig. 5
figure 5

Random placement and migration using “transition” operator with modified CSO algorithm

Full size image
Fig. 6
figure 6

Random placement and migration using “swap” operator with modified CSO algorithm

Full size image
  1. (a)

    VM migration based on transition operator as is shown in Fig. 5, by applying transition operator in the modified CSO algorithm, at first, one of VMs located on physical machine “1” is migrated to physical machine “2,” and then one of VMs located on physical machine “3” is migrated to physical machine “1.”

  2. (b)

    VM migration based on swap operator: as it is shown in Fig. 6, by applying swap operator in the modified CSO algorithm, physical machines “3” and “5” swap VMs located on themselves with each other. This placement comes up when these two physical machines do not have enough resources (e.g., capacity) to admit new virtual machines. The only benefit of swap operation in this state is reducing the consumed power of physical hosts.

We now proceed to explain our modifications to CSO algorithm: if the value of fitness function in the new physical host is better than that of the previous location, the correspondent array will be fed into the levy flight step of CSO algorithm. In this way, the likelihood of attaining global optimum placements will be raised and CSO algorithm won’t be trapped in local optima.

We explained the reservation step of the mechanism, before, in Sect. 3.1 (upper half of Fig. 2). Now, in the lower half of Fig. 2, we represent primitives and transferred messages between network entities in placement step of CNCE. Note that in the second step of the mechanism, each VM can find its appropriate place on physical machines using modified CSO placement algorithm. From now on, we refer to the modified algorithm as CSO&SA. The description of messages transferred between entities in placement step of CNCE is shown in Table 5. Also, the contents of the messages are shown in Table 6. As shown in Fig. 6, in the placement step, the cloud service provider sends HAD messages to VMs. These messages contain the addresses of appropriate physical hosts subject to the optimization goals. Now, each VM refers to the corresponding physical host by GSV message. This message contains the amount of demanded service. The Walrasian equilibrium allocation (resource reservation) and VM placement operations in CNCE are shown in Algorithm 1.

figure a
Table 5 Description and direction of CNCE messages in VM placement step
Full size table
Table 6 Contents of CNCE messages in VM placement step
Full size table

4 Performance evaluation

In this section, the performance evaluation of the proposed microeconomics-based system is explained using the well-known CloudSim tool (version 3.03) running on a 64-bit Intel® Core™ i5-8269U Processor with 6 MB Cache, 4 Cores, 4.20 GHz CPU frequency, and 8 GB RAM. The CloudSim was first developed with the aim of modeling and simulating cloud computing systems in Melbourne University [45]. As stated before in Sect. 3, the proposed CNCE system comprises two steps: in the first step the bandwidth reservation is carried out and in the second step, the placement of VMs on physical hosts is carried out. In order to simulate the first and second steps, we use the simulation settings which were introduced before in [8, 27], respectively. The number of physical hosts in our simulation is fixed at 10. The number of VMs varies according to four scenarios as 20, 30, 45, and 65 virtual machines. The CPU processing rate of each VM varies using a uniform distribution in the interval (400, 700) MIPS. The required memory is chosen as 512 Mega Bytes. The physical hosts of cloud are considered heterogeneous in nature and uniformly distributed in the interval (9000, 10,000) MIPS. Also, the provided bandwidth of physical hosts is considered uniformly distributed in the interval (4000, 5000) bps. Since the CloudSim is a Java-based simulator, we imported Java Optimization Modeler (JOM) library [43] into the CloudSim to solve the above-mentioned optimization problem.

One of the significant metrics in microeconomics is the social welfare of the users (or equivalently the welfare of VMs). In fact, the concept of social welfare reflects the level of quality of service (QOS) in CNCE system. Equation (47) represents the aggregate social welfare (\({\text{ASW}}\)) of VMs:

$${\text{ASW}} = f_{1} = \sum\limits_{i = 1}^{{N_{\text{VM}} }} {u_{{\text{vm}_{i} }} } ,$$
(47)

Clearly, the social welfare of each VM depends on its utility value which in turn, depends on its reserved bandwidth. By dividing \({\text{ASW}}\) to the total number of VMs, we can obtain the mean social welfare (\({\text{MSW}}\)) of VMs in CNCE as the following:

$${\text{MSW}} = \frac{\text{ASW}}{{N_{\text{VM}} }}$$
(48)

As stated before in Sect. 2, our proposal falls into the category of non-strategic pricing models in the sense that the action of a particular VM in a given time does not affect the actions of other VMs. Clearly, it is better to compare the performance of the proposed method with the research activities carried out in non-strategic scope. For this purpose, we compare the performance of the system with that of CloudSim simulator. This simulator has not any predetermined mechanism for pricing the cloud resources. In Fig. 7, the value of \({\text{ASW}}\) of VMs in CNCE has been compared with that of the non-priced approach of CloudSim using Eq. (47). According to the figure, it is obvious that the value of \({\text{ASW}}\) of VMs increases as the number of VMs increases.

Fig. 7
figure 7

Aggregate social welfares of VMs in CNCE in comparison with that of non-priced case

Full size image

In Fig. 8, the value of \({\text{MSW}}\) of VMs in CNCE has been compared with that of the non-priced approach using Eq. (48). As is evident in Fig. 8, the amount of social welfare is remarkable using CNCE method. The interesting thing in the figure is that the value of \({\text{MSW}}\) in CNCE decreases slightly after a pick with 30 VMs! From the viewpoint of producer–consumer theory, the reason behind this phenomenon is quite clear: Since resources on physical hosts (actually, the producers in CNCE) are limited, when the number of VMs (the consumers in CNCE) exceeds 30, the economic system slightly enters into the saturation state where the resources are no longer sufficient to serve VMs with initial levels of qualities. This, in turn, results in decreasing the demanded bandwidth rates of VMs and decreasing their utility level subject to Eq. (1). Also, regard to Eq. (8) it is clear that as the number of VMs increases, the service prices will experience a gradual rise too. In order to make a better sense of what CNCE mechanism does, in Fig. 9 we have depicted the service price against VMs’ social welfare in the form of radar diagram. As is evident in the figure, when settings of 45 and 65 virtual machines are used, the price of services drastically rises (red color) while, changes in VMs’ social welfare are not noticeable (green color). In other words, CNCE mechanism is scalable in the sense that the system performance does not degrade drastically with the increase in traffic load.

Fig. 8
figure 8

Average social welfares of VMs in CNCE in comparison with that of non-priced case

Full size image
Fig. 9
figure 9

Scalability of CNCE: system performance does not degrade drastically with the increase in traffic load

Full size image

In statistics, Mann–Whitney U is a rank-order test. This test is used for assessing the distribution of two independent experimental approaches. It merges two independent dataset and ranks data elements in ascending order, irrespective of their original group. In this manner, the Mann–Whitney U test could determine the location and range of each data element within the merged dataset [46]. We have used the well-known SPSS, statistical software tool (version 22), in order to analyze the simulation results [47]. Figure 10 shows the mean rank for two approaches. Note that for each approach, we have run the experiments 40 times on CloudSim simulator. As is evident in Fig. 10, CNCE has higher mean rank compared to non-priced case. It means that CNCE has a positive and remarkable effect on social welfare of users and succeeds to get more shares.

Fig. 10
figure 10

Mann–Whitney U test: CNCE gets more shares of social welfare compared to non-priced case

Full size image

Figure 11 shows the aggregate revenue of hosts in CNCE in comparison with that of non-priced approach for different number of VMs. Recall from Eq. (6) that physical hosts have the role of producers in CNCE. Clearly, CNCE attains considerably large amounts of revenue compared to that of non-priced case. This is in accordance with Eqs. (6)–(7), where the providers in CNCE try to regulate their production level in such a way that leads to maximization in their revenue.

Fig. 11
figure 11

Aggregate revenue of hosts in CNCE in comparison with those of the non-priced case for different number of VMs

Full size image

Now, let us evaluate the fairness (or distributive justice) in CNCE. Literature survey in microeconomics shows that there exist numerous definitions subject to fairness. Here, we use a simple definition of fairness. For this purpose, at first we define the variance of social welfare concerning virtual machines in CNCE as following:

$$\delta^{2} = \frac{1}{{N_{\text{VM}} }}\sum\limits_{i = 1}^{{N_{\text{VM}} }} {(u_{{\text{vm}_{i} }} - {\text{MSW}})^{2} } ,$$
(49)

Clearly, the less is \(\delta^{2}\) value, the more justice there exists in the society. In other words, fairness in CNCE indicates the amount of variations of VMs’ social welfare from the average social welfare. Regarding the dependence of this parameter to the rate of social welfare, it can be compared with other mechanisms like Ramsey pricing [25]. Figure 12 shows \(\delta^{2}\) value obtained from CNCE in comparison with those of the non-priced and Ramsey mechanisms for different number of VMs. As it can be seen from the figure, the proposed method has the least variance in all settings. It is worth mentioning that in Ramsey pricing, there are different prices and hence, the social welfare of VMs have more fluctuations.

Fig. 12
figure 12

Variance of social welfares (fairness) in CNCE in comparison with those of the non-priced and Ramsey mechanisms for different number of VMs

Full size image

Results which we have presented until now belong to the first step of the proposed system. Now, we proceed to discuss the simulation results concerning the second step, namely VM placement. We defined the power-aware VM placement problem, before, in Eqs. (36)–(41). The consumed power of each physical host is considered to be 1000 W and 400 W in active and passive modes, respectively. Figure 13 shows the comparison of average power consumption for different number of VMs and different placement strategies. It is worth mentioning that the developers of CloudSim implemented the instrument using a number of VM placement approaches, the most famous of which are first-fit decreasing (FFD) and best-fit decreasing (BFD) schemes. FFD starts with the most active host and tries to pack every VM in it before going to the next host. If no suitable space is found for the VM, the following host is selected to be put in the new space. Like FFD, BFD arranges VMs in non-increasing order. Subsequently, it picks up a bin that entails minimum empty space once the VM is packed [48]. We have compared our proposed placement approach (CSO&SA) with original CSO as well as FFD and BFD approaches. Note that since metaheuristic approaches find extensive Pareto efficient solution points in different runs, we have sketched the figure by averaging over 40 runs of the algorithms. The simulation results show that our proposed placement algorithm has less consumed power in comparison with other approaches for all settings of VMs. As discussed before in Sect. 3-2, the reason lies in good distribution of cuckoos as well as creating new opportunities due to applying the SA scheme.

Fig. 13
figure 13

Comparison of mean power consumption for different number of VMs and different placement strategies

Full size image

In statistics, analysis of variances (ANOVA) test is used to determine the significant difference between the averages of multiple (more than two) experimental approaches. The SPSS uses default value of 95% confidence interval. So, if significance value (abbreviated “Sig.”) is larger than .05 we accept null (basic) hypothesis \(H_{0}\). The null hypothesis indicates that the averages of all four approaches (FFD, BFD, CSO, and CSO&SA) are almost equal. Table 7 shows the descriptive statistics of the ANOVA analysis subject to power consumption.

Table 7 The ANOVA table for power consumption
Full size table

Since Sig. value is greater than .05, the hypothesis \(H_{0}\) is rejected. It means that there exists at least one approach which its average power consumption differs from that of other approaches! Now, we refer to Table 8, namely Post Hoc analysis. The Post Hoc analysis in Table 8 represents pairwise comparisons among four approaches. Here, we have used Fisher’s least significant difference (LSD) method which is one of Post Hoc test methods [49]. In the first row of Table 8, the FFD approach is denoted by I and other approaches are denoted by J. As is evident from the first row of Table 8, the value of I − J (I minus J) is positive for all comparisons. So, it is concluded that the FFD approach consumes more power compared to other approaches.

Table 8 LSD pairwise comparisons subject to consumed power for different approaches: FFD, BFD, CSO, and CSO&SA (Dependent variable: Power consumption, LSD)
Full size table

Figure 14 shows the average power consumption for all approaches. As is evident from the figure, the proposed approach has the least value of consumed power among all.

Fig. 14
figure 14

Average power consumption for different approaches: FFD, BFD, CSO, and CSO&SA

Full size image

Figure 15 shows the Pareto front diagram subject to two objective functions, f1 and f2 for different number of VMs and different placement strategies. Recall from Eqs. (2) and (36) that f1 and f2 represent the aggregate social welfare and the consumed power, respectively. As is evident from Fig. 15, our proposed method succeeds to find more Pareto optima points in comparison with other approaches. Also, note that the consumed power decreases with decreasing the number of VMs. The reason behind this phenomenon is that when the number of VMs decreases, the system probably needs to switch on fewer numbers of physical hosts.

Fig. 15
figure 15

Pareto front for different number of VMs and different placement strategies

Full size image

Figure 16 shows the comparison of number of required migrations for different number of VMs. As it can be seen from the figure, the proposed placement approach requires fewer numbers of migrations in order to converge to optimum points.

Fig. 16
figure 16

Comparison of number of required migrations for different number of VMs

Full size image

Finally, we present our last evaluation subject to the proposed algorithm. Figure 17 shows the comparison of time complexity for different number of VMs. As it can be seen from the figure, the proposed placement approach has less time complexity in order to converge to optimum points. This type of complexity is based on the time required by each mechanism such as creating initial population and updating solution. The most evolutionary algorithms (EAs) have, at each iteration, a complexity of  \(O(d \cdot s + c \cdot s)\), where \(d\) is the dimension of the problem,  \(s\) is the population size, and  \(c\)  is the cost of the objective function. The time complexity of the most objective functions is \(O(d)\) or even higher. So, usually is the second term which plays the significant role to determine the total time complexity. Furthermore, EAs usually perform  \(e\) iterations, where \(e\)  is the maximum number of evaluations performed by the objective function. Thus, the time complexity becomes \(O(d \cdot e + c \cdot e)\). Once again, the second term tends to determine the total time complexity. That’s why in EAs, the quality of an algorithm is frequently measured by the amount of evaluations it performs. As discussed previously, we made some modifications in CSO algorithm which reduces the parameters \(c\) and \(e\). That is why our proposed approach attains lower time complexity in Fig. 17.

Fig. 17
figure 17

Comparison of time complexity for different number of VMs

Full size image

5 Concluding remarks and future trends

In this paper, we targeted one of the most practical concepts of cloud computing, namely the resource management. This process, itself comprises “resource reservation” and “VM placement” operations in which potential players are VMs and physical hosts. We made a comprehensive review of previous research activities as well as outlining their goals, limitations and criteria. We formulated the resource reservation problem using the theory of producer–consumer of microeconomics. The designed mechanism at first identifies the required bandwidth of VMs subject to Walrasian equilibrium concept, and then tries to find a near-optimal placement for each VM over physical hosts using metaheuristic approach. We proved that the aggregation of users’ social welfare is Pareto efficient. The proposed economic system results in maximizing the users’ welfare and minimizing the consumed power in physical hosts. The proposed economic system falls into the category of non-strategic economic mechanisms in the sense that the actions of VMs associated with the users do not affect by the actions of other VMs.

In microeconomics, there exist other interesting and challenging non-strategic pricing mechanisms. One of the possible lines of research is to model the interactions between VMs, brokers, and physical hosts by the theory of “exchange economy.” Another important field of research in the future is attention to the type of VMs. This will lead to more realistic modeling of cloud entities.