# A Game-Theoretic Based Resource Allocation Strategy for Cloud Computing Services

Authors: Wang Yan; Wang Jinkuan; Sun Jinghao
Journal: Scientific Programming
 (2016)

---

## Abstract

We propose an economics-oriented cloud computing resources allocation strategy with the use of game theory. Then we develop a resource allocation algorithm named NCGRAA (noncooperative game resource allocation algorithm) to search the Nash equilibrium solution that makes the utility of various resource providers achieve optimum. We also propose an algorithm named BGRAA (bargaining game resource allocation algorithm) to further increase the overall revenue with the constraints of efficiency and fairness. Based on numerical results, we discuss the influence of NCGRAA and BGRAA for the utility of resource on the system performance. It shows that the choice of parameters of the two algorithms is significant in improving the system performance and converging to the Nash equilibrium and Nash bargaining.


---

## Body

## 1. Introduction

Cloud service is the commercial implementation of computing resources and essentially a producers-consumers model. From the perspective of economics, the service is as the valuable economic goods that providers produce and lease to consumers. Cloud users can purchase goods from the provider according to their own needs in global scope and in a certain paying mode.Advancement in cloud resource allocation is urgently needed to satisfy service-specific QoS (Quality of Service) requirements. At the same time, system performance must be mathematically analyzed and numerically evaluated for design of the strategies. The generally accepted view is that typical cloud computing resource allocation strategies are mainly based on multistage resource pool of rent-borrow theory, the random integer programming optimal resource strategy, and economics resource strategy.Our research on cloud computing resources provisioning strategy is based on the market economic model and the advantages of game theory in resource management. First, we establish a noncooperative resource provision model and a corresponding game algorithm. The aim of the algorithm is to provide resources strategy by solving equilibrium so that each utility function could achieve optimum to obtain a reasonable strategy. Meanwhile, in order to further increase the overall revenue, the strategy is proposed by taking the efficiency and fairness constraints in noncooperative bargaining game into account. The according algorithm achieves higher collective utility by solving bargaining problem. Finally, experiment verifies the effectiveness and superiority of the two algorithms.In Section2, we analyze the related work. In Section 3, we analyze the framework of cloud resources based on game theory and establish the market model of resources provided. In Section 4, we propose an algorithm named NCGRAA to solve the Nash equilibrium in order to obtain reasonable resource allocation strategy. In Section 5, we propose an algorithm named BGRAA to search the Nash bargaining solution in order to make higher utility of resources. In Section 6, based on simulation, we evaluate the performance of the two algorithms. Finally, concluding remarks are given in Section 7.


## 2. Related Work

Researchers [1, 2] used a random integer programming method to optimize resource allocation and introduced two ways which are in advance order and pay-as-you-go to provide users with resources. This strategy can provide dynamic resource allocation methods, considering the cost of various stages resources. However the uncertain resource prediction accuracy needs to be improved.Then the cloud resource management model [2, 3] was designed based on SLA (Service Layer Agreement). Although the perspective of economics has been taken into account, this strategy is still lacking factors like the resources and the price dynamic. Literature [4] had studied the resource management system based on QoS.In recent years, various resource management methods with different policies and principles were proposed in some literatures [5–14]. But most literatures were relevant to complex cloud based on applications consisting of multiple subtasks. Therefore collaboration between tasks should be considered. Meanwhile, existing algorithms were obviously too conservative without considering the communications among tasks. As we know, the dependent task scheduling problem is NP-hard [15–17]. Thus some heuristic algorithms were proposed for near-optimal solution [18, 19]. Simultaneously, numerous methods were proposed to solve the optimization problem with game theory [20, 21]. Moreover, game theory can be divided into noncooperative game theory and cooperation game theory [22]. Typical noncooperative game solution is the Nash equilibrium.Based on the Nash equilibrium, numerous works were proposed. For instance, Kwok et al. [23] proposed a level game model under the environment of multiple administrative domains. It studied the selfish behavior of resource for the influence of user task execution. However, the research does not put the relationship between the resource providers into consideration. In literature [24], a distributed actively noncooperative abandon model was presented. The model reduced the task execution time considering the selfish and priority of resource allocation. Ghosh et al. [25] proposed a pricing strategy solving the Nash bargaining problem based on game theory. But the uniqueness of Nash equilibrium solution was not discussed.Existing works generally consider the relationship between the user and resource provider, but the resource provider is neglected as rational body when the relationship between competition and cooperation on the result of final resources is provided. Researchers proposed resource management on the basis of the principle of market economics [26] and focused on how to improve the benefits of resource provider with the constraints of efficiency and fairness.To the best of our knowledge, although the resource allocation strategies have been studied in previous works, allocation strategy aims at achieving the optimal allocation of resources that has been less proposed. Therefore, we focus on giving the dynamic change among supply-demand, resource load, and congestion by prices floating reflections and also focus on achieving the optimal resources allocation by equilibrium theory. Thus we propose the supply strategy for cloud computing resources based on market economics model in this paper and two resources allocation algorithms for increasing both efficiency and fairness. Inspecting our experimental results, the proposed algorithms improve the resource allocation performance effectively. The experimental results indicate that the resources allocation problems that are solved by noncooperative theory could converge to the Nash equilibrium solution. The utility of the resource provider is optimal. While bargaining, noncooperative game analysis with Pareto improvements is made on the basis of satisfying the efficiency and fairness. Moreover, two algorithms are effective to improve the efficiency of resource allocation.


## 3. The Game Theory for Resource Allocation Strategy

As utility computing, cloud computing has a lot of economy features, including market features of computing resource, the scale of the cloud market economy, and the provider paid features of resources. One of the advantages of using economics principle to solve the cloud resource allocation is the market mechanism. The market mechanism is well known as that commodity prices floating reflections resource load, congestion, and the dynamic change of supply or demand condition. Therefor it can achieve the optimal allocation of resources with equilibrium theory. This dynamic coordination of resources allocation provides a mechanism that is suitable for dynamic characteristic of the cloud computing environment. Each participant in the market is in pursuit of maximizing individual interests. That makes the whole resource allocation gradually tend to optimum condition. It is one of the traditional resources allocation methods pursued but difficult to achieve.Hence we analyze the situation above and give the architecture based on economics. The cloud architecture is shown in Figure1. It has four parts: the users, resource consumers, resource market, and resource providers.Figure 1
The cloud architecture based on economics.(1  ) Users. We mean the users who use cloud computing resources. Cloud users put forward their own requirements from their agent to the cloud market, including the required QoS description. And this requires many aspects to complete the task, such as CPU type, the number of the CPU, memory size, operating system, and its version number.(2) Resource Consumers. Private cloud is as a resource consumer, even though it provides users with resources. When it cannot meet users’ need, it still gets resources from the public cloud.(3) Resource Market. Resource market is the core of this architecture module. It is the management for users, it calculates risk, and it is autonomous. The market is the interface for data center/cloud service providers and the user/agent, using some kind of negotiation mechanism to coordinate the two requirements. It mainly includes the following six kinds of mechanisms.Permission control mechanisms for service request: when a service request is submitted for the first time, the mechanism submits request for QoS explanation before determining whether to accept or reject the request. Pricing mechanism: pricing as a basic mechanism manages the resources allocation and demand of data center. Pricing mechanism decides the price of service request. Audit mechanism: audit mechanism records the actual use of the requested resources, in order to make the final cost that can be calculated and credited for the user. VM (Virtual Machine) monitoring mechanism: monitoring mechanism monitors VM available. Scheduler: it allots and executes the service requests. Monitoring system for service request: the service request monitoring mechanism monitors the implementation of the service request.(4) Resource Providers. The public cloud is represented.We build the system model with theM/M/n/n+l queue. The model has some features: the model is a mixed queue model. Tasks arrive at the queue in accordance with the parameter λ of the Poisson flow and service time for each task obeys the negative exponential distribution with parameter μ. The order of the service is in accord with First Come First Served. Length of the queue is n+l and l is the length of buffer. If task arrives at the system, when the queue has not been occupied, it enters the queue to wait for service or it waits in the buffer. Parameters of the model are shown in Parameters section.(1) Response Time. It has proved that when the communication intensity ρ<1, there is a stable equilibrium state in system [12, 13]. Therefore, we consider the queue for ρ<1. Probability πk of queue length isk: πk=limt→∞⁡PNt=k.Typically, we measure response time with the percentageφ, which is in response to a predetermined percentage of the time. In the SLA (Service Layer Agreement), performance indicator of response time is described as follows:(1)∫0ΔTftdt≥φ,where the f(x) is a random function and is also the probability density function. ΔT represents the period during which task uses the service.Equation (1) represents the probability of response time; when the response time is less than the period ΔT, then the probability must be equal to or more than φ. For example, in M/M/1 queuing model, the probability density function of the response time is f(t)=μ(1-ρ)e-μ(1-ρ)t. Thus we can give the equation as follows: (2)μ≥-ln⁡1-φΔT+λ.From (2), we know that, when the arrival rate λ is constant, the time period ΔT is unchanged. If we improve the probability of response time φ, service rate will increase. We must deploy more computing resources.InM/M/n/n+l queue model, system transition probability between states is as follows: (3)πk=nρkk!π0,0≤k<nnnρkn!π0,n≤k≤n+l.When∑i=1n+lπi=1, we obtain π0 as follows: (4)π0=∑k=0n-1nρkk!+nρn1-ρl+1n!1-ρ-1,ρ<1,where π0 means the probability that all hosts are idle and there is no task in system.Response time is the sum of waiting time and service time. Waiting time can be calculated in the following manner method: When a task arrives, if the buffer queue is not full, the user can enter the queue to wait.qi represents the steady probability that the number of tasks waiting for service is i. qi is given as follows: (5)qi=PNt=iPl≠0Pl≠0=πi1-πn+l,i=0,1,…,n+l-1.When the buffer queue is not full, hosts service the tasks immediately; then the probability distribution at this time is as follows:(6)Wat=q0+q1+q2+⋯+qn-1=∑i=1n-1πi1-πn+l.When a task arrives at the buffer, if there are tasks already in the queue, the newly arriving task has to wait until its front tasks have been completed. Distribution of exit tasks stream for each host is following negative exponential distribution with parameterμ. When the number of the hosts is n, the system distribution for exit tasks stream is subject to negative exponential distribution with parameter nμ. In these circumstances, we derive the Erlang distribution as follows:(7)Wat=Wa0+∑i=nn+l-1P0<Wa≤t=Wa0+∑i=nn+l-1qi∫0tnμnμxi-ni-n!e-nμxdx=∑i=1n-1πi1-πn+l+∑i=nn+l-1qi∫0tnμnμxi-ni-n!e-nμxdx.Response time is equal to the waiting time and the service time; consider the following:(8)Wt=PW≤t=∫0tPWa≤t-xμe-μtdx=∫0tWatμe-μtdx.By responding to the distribution function of time, the relationship between the percentage of the number of servers and QoS can be obtained. If the response time in the percentage ofΔT is φ, then W≥φ; consider T<0.05; it indicates that the response time is less than 0.05 seconds.(2) The Average Queue Length. Depending on the desired definition, the average queue length in the buffer can be written as follows:(9)Na¯=∑k=nn+lk-nπk=nnρn+1π0n!1-ρ21-l+1ρl+lρl+1,ρ<1.The average queue length is equal to the queued requests waiting for service and the sum of the number of requests. The average queue length is as follows:(10)N¯=Na¯+Ns¯=Na¯+ρ1-πn+l=nnρn+1π0n!1-ρ21-l+1ρl+lρl+1+nρ1-nnρn+lπ0n!=nnρn+1π01-l+1ρl+lρl+1n!1-ρ2+nρ1-nnρn+lπ0n!.According to queuing model proposed above, when all hosts in private cloud have been fully allocated, VM manager buys VMs resources. For this situation, we give the system benefits function as follows:(11)Fc,h′=δN′-εWa+ch′-n+En,where c represents the price of buying VMs in the market. h′ represents the number of hosts being demanded. δ and ε represent constant factors. N′ represents the throughput of processing tasks. E represents the cost of energy of provided VMs in a private cloud.The goal of this paper is to solve the provisioning strategy to ensure the best interests of resource providers in different relations, based on the assumption of considering the market as a whole.Resource consumer demandFc is a function of the price c. Demand function is as follows: (12)Fc=arg⁡max⁡Fc,h′.For the resource requirements of a private cloud, the demand function is as follows:(13)Fdc=∑k=0Ihd,k′χΞd,kc=∑k=0Ihd,k′,c∈Ξd,k0,otherwise,where I indicates the total number of steps. hd,k′ represents the number of VMs that buyer needs at the stage of step k. Ξ is the price range at step k. Ξd,k=(Φd,k-1,Φd,k], where Φd,k is the right margin. d is the number of buyers. For d∈[1,2,…,D], Ξd,0=0, Ξd,1=(0,Φd,1]. χΞi,k is the index function of demand. (14)χΞc=1,c∈Ξ0,otherwiseΦi=Φd^,k^h′=∑d=1DFc,h′Φis.t.d^,k^=arg⁡minΦi,k′∈Qk⁡Φi,k′Qk=Φi,k′∣Φi,k′>Φk-1.Therefore, the total consumer demand is(15)Fc=∑k=0Ihk′χΞkc.From the above analysis, we get the total demand price function. That is an inversion of the consumer demand function, given as follows:(16)F-1c′=∑k=0IΦI-1χΞkc′=∑k=0IΦI-1,c′∈Ξk0,otherwise,where Φ0=0, Ξk=(Φk-1,Φk], ΞI=(ΦI-1,∞], and χΞ(c′) is the index function of price: (17)χΞc′=1,c′∈Ξ0,otherwise.


## 4. Noncooperative Game Based NCGRAA

In the market, the situation that multiple cloud resource providers compete with each other may be noncooperative game model. Noncooperative game theory is perfectly rational in the context of the strategy with interdependence interaction theory. Particularly, noncooperative game theory focuses on solving the problem for rational stakeholders from multiple rows cooperative game resources, mutual influence, and effect arising from the analysis of the resources. The most excellent choice is a function that all other competitors selected. Nash equilibrium strategies seek to optimize the effectiveness of the time optimized configuration of resources.We express resource providers providing VMs as space strategy. In cloud computing market, the behavior of all the resources providers can be represented as Cartesian productS=S1×S2×⋯×So, where So represents a resource providero’s strategy set.Utility represents obtained satisfaction by providing a service or a resource rent and each resource provider’s expected revenue is represented by the utility function, that is,{Uo}={U1,U2,…,UO},o∈{1,2,…,O}. s is the choice strategy of the resource providers in the game. If the game participant o is with the strategy so, so′ is the representation of selection strategy by all other resource providers except o and so′=s-so. Then the participant utility is expressed as Uo(s).In the cloud computing market, all the resource providers want to obtain the most optimal strategy according to price function. Considering the case of a single resource provider, the returns function is as follows:(18)us=sFc,h′-1s-Fcs.Among them, the right first term indicates the total income provided by the VMs. Introducing cost function can improve the system performance and it is defined as follows:(19)Fcs=sFuf-Ff,where Fuf is the variable costs of resource providers providing VMs and it includes the cost of the buffer. Ff is the fixed costs of resource providers providing VMs.Strategic optimization can be formalized as(20)s+=arg⁡maxs⁡us.According to (20), benefits of single resource provider are as follows: (21)u+s=s+Fc,h′-1s+-Ff-s+Fuf,where price function is nonincreasing step function. The number of steps is finite and it can be solved by enumeration method.For a cloud resource market with resource providerso, given other resource providers VMs, the strategy of VMs providing of resource provider o is optimal. For all resources providers, the following equation is given: (22)Uoso+,so′≥Uoso,so′.There is the following optimization problem solution:(23)so+∈arg⁡maxso∈So⁡Uoso,so′.Suppose resource providers provide alternatives with fixed costs and there is variable cost. Marginal cost is zero. The utility function is(24)Uo=sFc,h′-1s-Ffo-sFufo,where Ff(o) is fixed cost and Fuf(o) is variable cost.In order to obtain Nash equilibrium strategy, we describe Nash equilibrium as follows: we find out the best solution for each player in game and then figure out strategy combination composed of the best strategy for each player.Optimal response strategy means that the strategy is optimal among the given strategies of all other resource providers.(25)so+=arg⁡max⁡Uoso,so′,where Uo(so,so′)=soF(c,h′)-1(so+so′)-Ff(o)-sFuf(o).As the price function is nonincreasing step function, we obtain that(26)so+=hk+′-so′j+=argmaxj∈1,2,…,j′Φkhk′-so′-Ffo-hk′-so′Fufos.t.j′=argminhk′∈Zhk′Z=hk′∣hk′>so′.Using the optimal response, Nash equilibrium is defined as(27)so′+=fso′+→so′+→=s1+,s2+,…,so-1+,so+1+,…,sO+T,where so′+→ represents the optimal response vector.At this time, utility function with Nash equilibrium strategy of resource providero represents the receipts of noncooperation market resulting as follows: (28)RMR+=Uoso+,so′+→.Theorem 1.
If a task selects a VM which is not in the possible set of optional VMs, the task scheduling scheme is not a Nash equilibrium solution.Proof.
The current task number is greater than or equal to the VMs set, so there is no task that can be chosen, except the set of VMs. The number of tasks is less than that of the VMs, assuming that a taski is scheduled to VM except the possible set. Then according to the possible set of VMs, besides i task, the number of rest tasks is assigned as N-1. According to the principle of Nash, there must be at least one VM which may not be assigned, so, for this task, Ui>Uoth. Ui is the benefit for the reason that the task i is scheduled to the possible VM and Uoth is the benefit for the reason that the task i is scheduled to the VM not in the possible set.
Because Nash equilibrium is defined under the condition of invariable environment, the entire individual cannot achieve higher yields by changing its own strategy. The formula below is tenable:(29)∀k,fs1,…,si,…,sn≥fs1,…,sk,…,sn,where si is the strategy for the task i and f(s1,…,si,…,sn) is the benefit at the strategy si.
It is at odds with the definition of Nash equilibrium solutions, so if taski selects the possible VMs, the task scheduling scheme is not Nash equilibrium solution of the scheduling problem.Theorem 2.
In the noncooperative game with a finite number of players model, foro∈{1,2,…,O}, sufficient conditions for the existence of Nash equilibrium are the following: (1)
Strategy space{So} is a nonempty compact convex set in Euclidean space.(2)
Utility functionUo(s) is continuous in {So} and is quasi-concave function.Proof.
As the number of VMs available is limited for each resource provider in terms of a single integer point set, its strategy space for real axis is clearly a nonempty compact convex set in Euclidean space. Because the number of VMs is an integer number and greater than zero, the price function is as the number of linearly decreasing functions at this time. The utility function is continuous in space strategy map.(30)∂Uoso,so′→∂so=Fc,h′-1so+s∂Fc,h′-1so∂so-∂Fs∂so∂2Uoso,so′→∂so2=2∂Fc,h′-1so∂so+∂2Fc,h′-1so∂so2,where the price function is a decreasing linear function and ∂2Uo(so,so′→)/∂so2<0. Then Uo(s) is concave in the strategy space.
By Theorem2, it shows that there is Nash equilibrium strategy for cloud resources provided in a competitive market. (31)∂Uoso,so′→∂so=0⟹so=-Fc,h′-1so+∂Fs/∂so∂Fc,h′-1so/∂so.
By the above formula, Nash equilibrium can be represented as a matrix form.(32)Es=Cs-+Z,where E(s) represents a mapping from the space RO to RO. C and Z are zero-order matrixes.
Nash equilibrium is to prove that the uniqueness ofE(s) is a standard function that satisfies the following:(1)
Positive:E(s)>0.(2)
Monotonic: ifx<y, then E(x)≥E(y).(3)
Scalability: for anyω>1, there is ωE(x)≥E(ωx).
Since each cloud resource provider in the market obtains certain benefits through the VMs providing, namely,E(s)>0, that meets (1). Proving the existence of the process, because the price is understood to be a linear decreasing function, we can see that the nature (2) is satisfied. For a linear function, a function of the nature (3) scalability is satisfied.
To sum up,E(s) is a standard function and, for a standard function, fixed point is unique. Therefore, Nash equilibrium of NCGRAA algorithm is unique.
The process of algorithm of NCGRAA is as follows.
Step 1. When there is a set of a new request arriving, it makes this set of VMs have the maximum profit and minimum completion time of the VMs.(a)
According to the system running state and the tasks users submit, compute the running time and make sure that each task has the profit of each VM.(b)
Sort each task profit and find out each set for the task.(c)
Summarize set.
Step 2. Find all possible task groups with the intersection and generate the corresponding conflict task group. Perform the noncooperative game analysis and then identify Nash equilibrium for all conflict task groups and generate for each conflict task group the Nash equilibrium solution. Generate Nash equilibrium solution set for all conflict task groups, the Nash equilibrium solution for task scheduling problem and optimal Nash equilibrium solution.(a)
Analyze the task groups. After that, find out the tasks with intersection and generate the corresponding conflict task group.(b)
For each conflict set, find out the Nash equilibrium solution and generate the Nash equilibrium solution set and the Nash equilibrium solution for the corresponding task scheduling problem.(c)
According to the system revenue for Nash equilibrium solution to the current task scheduling problem and the overall completion time for task, find out the optimal Nash equilibrium solution for the current task scheduling problem.
Step 3. According to the task scheduling result with the optimal Nash equilibrium, each task is assigned to the selected VM. The allocation results are recorded in task scheduling log.(a)
According to the task scheduling result with the optimal Nash equilibrium, determine the service VM and perform the task.(b)
Record the task scheduling results in the log.
Step 4. Continue monitoring a user action, running the task scheduling algorithm for the next set of task scheduling requests.


## 5. Bargaining Game Based BGRAA

Although NCGRAA makes resource provider optimal profit, it is not the biggest gain. If resource providers can mutually agree, it will have more collective gains. The kind of bargain in the market resource provider of income will be greater than or equal to the cooperative competition in the market returns.In a negotiated market, resource providers improve their income by the way of negotiating. Market can benefit from the bargaining game model. The resource providers can mutually agree to bargain to get the satisfaction, which has the two aspects, both efficiency and fairness of the VM provided on the basis of strategy. Efficiency requirements can contain Pareto efficiency and the overall revenue maximization. The solution is defined as Nash bargaining equilibrium of bargaining game.


### 5.1. Nash Bargaining Game Model for Resource Allocation

Definition 3.
All the resource providers in the cloud computing market environment are defined as the game participants, expressed asRPo, o∈{1,2,…,O}.Definition 4.
B is the set of VM bargaining problem, F∈RO is the set space of resource provider, and Γ is the minimum expected value for earnings. Γ=(RMR1∗,…,RMRo∗,…,RMR(O)∗).Definition 5.
WhenRbar(o)∈F∣Rbar(o)≥RMR(o)∗,∀o is not empty bounded set, F,Γ∈B is the bargaining game problem.
A bargaining solution is to put each bargaining problem(F,Γ)∈B linked with a special result Rbar∗=ψ(F,Γ) as a function, named ψ:B→RO.
Axiom 1. Feasibility of axioms: Rbar∗∈F.
Axiom 2. Individual rational axiom: Rbar≥RNE∗,∀o.
Axiom 3. Pareto efficiency axiom: Rbar≥Rbar∗=ψ(F,Γ)⇒Rbar=Rbar∗=ψ(F,Γ).Axiom 2 shows that in addition to the bargaining solution there is no other way for Pareto improvement. We can derive the following axiom.Axiom 4. The invariance of the linear transformation axiom: Rbar∗∈F; for any linear transformation ϕ, there is ϕψ(F,Γ)=ψϕF,ϕΓ.Axiom 5. Independence of the axiom of choice: to any convex set E there is a subset F, and it is given as follows: (33)Rbar∗∈E⊆F⟹ψE,Γ=ψF,Γ.Axiom 6. Symmetry axiom: for any (F,Γ), there is RMR(i)∗=RMR(j)∗, (Rbar(i),Rbar(j))∈F. It means that, for any (Rbar(i),Rbar(j))∈F, Rbar(i)∗=Rbar(j)∗∈ψ(F,Γ) must satisfy Rbar(i)∗=Rbar(j)∗.Nash bargaining solution: Nash bargaining solution refers as the Nash equilibrium solution that the participants gain their interests in a game, when they have many times of bargaining and gradually eliminating the Nash solution.Introduction of Pareto evolutionary method is to obtain the optimal solution of BGRAA.We give a multiobjective optimization problem and make a feasible solution set as the optimization goal. If there is a feasible solution, for each solution, it would be either the global optimal solution or the global extreme value point.Evolving any two different individuals in population, if there is dominance, it must meet the following two conditions: there is at least one target and the subgoals are not bad.Theorem 6.
Meeting axioms 1 to 6, the only solution of bargaining problem is the utility of vector that maximizes the product Nash bargaining solution. Namely, solutions meet the following constrained optimization problem:(34)ψF,Γ∈arg⁡max∏o=1ORbaro∗-RMRo∗s.t.Rbar∗∈FRbaro∗≥RMRo∗.
Considering the resource of resource providersmax and the limitation of lowest income of resource provider in noncooperative game, the optimization goal is to give the effective control to the resource provider and achieve the goal of utility optimization. The selection of the utility function U is given as follows:(35)U=∏o=1ORbaro∗-RMRo∗s.t.Rbar∗∈FRbaro∗≥RMRo∗so≤smax.


### 5.2. Solution for Bargaining Game Problem of BGRAA

The solution of (35) is needed to be divided into two kinds of solution as follows.(a)
Nash solution for bargaining for two people in the game is considered.Wheno=2, (35) can be represented as(36)Rbari∗,Rbarj∗=ψF,Γ=arg⁡max⁡Rbari-RMRi∗Rbarj-RMRj∗.The resources provisioning algorithm wheno=2 is as follows:Step 1. Initialize the parameters si=siinit, sj=sjinit.Step 2. Select the increment step length I, where si(k+1)=si(k)+I, sj(k+1)=sj(k)+I, and calculate the Pareto optimal point between [0,simax], [0,sjmax].Step 3. From (Rbar(i)-RMR(i)∗)×(Rbar(j)-RMR(j)∗)=C, calculate the corresponding strategy si, sj, and the earnings of resource providers in NBS.IFsi and sj reach convergenceTHEN
Return to Step 2.ELSERecord each convergence value.si and sj are the optimal solution of the system.Or calculate content conditions:π=arg⁡max⁡Rbar(i)+Rbar(j)/si+sjRbar(i)-Rbar(j), then return si and sj.ENDIF(b)
Nash solution for bargaining when the number of people iso in the game.By Hungary algorithm, the problem can be converted intoo=2 bargaining problems, so as to provide the optimal system resources. Bargaining algorithm is shown as follows.Step 1. Obtain the parameters from the provider and demand ones in the cloud market environment.Step 2.IF the number of the resource provider is even numberTHEN
Go to the Step3.ENDIFIF the number of the resource provider is odd numberTHEN
Give an provider with none resource.ENDIFStep 3. Using the Hungarian method to make the resource provider into two groups.Step 4. Through bargaining algorithm, return to the two bargaining Nash standard solution, and compute si, sj, Rbar(i), Rbar(j).Step 5. Go to Steps 3 and 4, until the NBS cannot be effective, return the parameters: si, sj, Rbar(i), Rbar(j).


## 5.1. Nash Bargaining Game Model for Resource Allocation

Definition 3.
All the resource providers in the cloud computing market environment are defined as the game participants, expressed asRPo, o∈{1,2,…,O}.Definition 4.
B is the set of VM bargaining problem, F∈RO is the set space of resource provider, and Γ is the minimum expected value for earnings. Γ=(RMR1∗,…,RMRo∗,…,RMR(O)∗).Definition 5.
WhenRbar(o)∈F∣Rbar(o)≥RMR(o)∗,∀o is not empty bounded set, F,Γ∈B is the bargaining game problem.
A bargaining solution is to put each bargaining problem(F,Γ)∈B linked with a special result Rbar∗=ψ(F,Γ) as a function, named ψ:B→RO.
Axiom 1. Feasibility of axioms: Rbar∗∈F.
Axiom 2. Individual rational axiom: Rbar≥RNE∗,∀o.
Axiom 3. Pareto efficiency axiom: Rbar≥Rbar∗=ψ(F,Γ)⇒Rbar=Rbar∗=ψ(F,Γ).Axiom 2 shows that in addition to the bargaining solution there is no other way for Pareto improvement. We can derive the following axiom.Axiom 4. The invariance of the linear transformation axiom: Rbar∗∈F; for any linear transformation ϕ, there is ϕψ(F,Γ)=ψϕF,ϕΓ.Axiom 5. Independence of the axiom of choice: to any convex set E there is a subset F, and it is given as follows: (33)Rbar∗∈E⊆F⟹ψE,Γ=ψF,Γ.Axiom 6. Symmetry axiom: for any (F,Γ), there is RMR(i)∗=RMR(j)∗, (Rbar(i),Rbar(j))∈F. It means that, for any (Rbar(i),Rbar(j))∈F, Rbar(i)∗=Rbar(j)∗∈ψ(F,Γ) must satisfy Rbar(i)∗=Rbar(j)∗.Nash bargaining solution: Nash bargaining solution refers as the Nash equilibrium solution that the participants gain their interests in a game, when they have many times of bargaining and gradually eliminating the Nash solution.Introduction of Pareto evolutionary method is to obtain the optimal solution of BGRAA.We give a multiobjective optimization problem and make a feasible solution set as the optimization goal. If there is a feasible solution, for each solution, it would be either the global optimal solution or the global extreme value point.Evolving any two different individuals in population, if there is dominance, it must meet the following two conditions: there is at least one target and the subgoals are not bad.Theorem 6.
Meeting axioms 1 to 6, the only solution of bargaining problem is the utility of vector that maximizes the product Nash bargaining solution. Namely, solutions meet the following constrained optimization problem:(34)ψF,Γ∈arg⁡max∏o=1ORbaro∗-RMRo∗s.t.Rbar∗∈FRbaro∗≥RMRo∗.
Considering the resource of resource providersmax and the limitation of lowest income of resource provider in noncooperative game, the optimization goal is to give the effective control to the resource provider and achieve the goal of utility optimization. The selection of the utility function U is given as follows:(35)U=∏o=1ORbaro∗-RMRo∗s.t.Rbar∗∈FRbaro∗≥RMRo∗so≤smax.


## 5.2. Solution for Bargaining Game Problem of BGRAA

The solution of (35) is needed to be divided into two kinds of solution as follows.(a)
Nash solution for bargaining for two people in the game is considered.Wheno=2, (35) can be represented as(36)Rbari∗,Rbarj∗=ψF,Γ=arg⁡max⁡Rbari-RMRi∗Rbarj-RMRj∗.The resources provisioning algorithm wheno=2 is as follows:Step 1. Initialize the parameters si=siinit, sj=sjinit.Step 2. Select the increment step length I, where si(k+1)=si(k)+I, sj(k+1)=sj(k)+I, and calculate the Pareto optimal point between [0,simax], [0,sjmax].Step 3. From (Rbar(i)-RMR(i)∗)×(Rbar(j)-RMR(j)∗)=C, calculate the corresponding strategy si, sj, and the earnings of resource providers in NBS.IFsi and sj reach convergenceTHEN
Return to Step 2.ELSERecord each convergence value.si and sj are the optimal solution of the system.Or calculate content conditions:π=arg⁡max⁡Rbar(i)+Rbar(j)/si+sjRbar(i)-Rbar(j), then return si and sj.ENDIF(b)
Nash solution for bargaining when the number of people iso in the game.By Hungary algorithm, the problem can be converted intoo=2 bargaining problems, so as to provide the optimal system resources. Bargaining algorithm is shown as follows.Step 1. Obtain the parameters from the provider and demand ones in the cloud market environment.Step 2.IF the number of the resource provider is even numberTHEN
Go to the Step3.ENDIFIF the number of the resource provider is odd numberTHEN
Give an provider with none resource.ENDIFStep 3. Using the Hungarian method to make the resource provider into two groups.Step 4. Through bargaining algorithm, return to the two bargaining Nash standard solution, and compute si, sj, Rbar(i), Rbar(j).Step 5. Go to Steps 3 and 4, until the NBS cannot be effective, return the parameters: si, sj, Rbar(i), Rbar(j).


## 6. Performance Evaluation

Considering three types of resources, the CPU, memory, and hard disk, we use Google Cluster Trace workload reference data source as the data center, including user information, task types, task number, the number of subtasks, the subtasks resource request parameters, and resource utilization. Local clusters are composed of four computers and each computer is configured to CPU Intel (R) Core (TM) 2 Duo E8200 2.66 GHz, 3 GB memory, and 160 GB hard drive. These nodes are interconnected by a 1 Gbps bandwidth switch. Amazon EC2 environment consists of 80 small instances, which are configured to Inter Xeon CPU E5430 2.66 GHz, 1.7 GB memory, and 146.77 GB hard drive.First, we show the performance of the algorithm itself. Then, we compare the performance with HM (Hadoop Mechanism) and GM (Google Management Mechanism) individually, in the aspect of fair distribution, average utility, and the system throughput. Finally, we compare the algorithms NCGRAA, BGRAA, and GEA (General Equilibrium Algorithm) at the average utility, system throughput, and fairness.In simulation, considering the length of the buffer and the queue, whenn=100, n=200, and n=400, the diversification of average queue length in the system is shown in Figure 2.Figure 2
Influence ofl on the average of length of queue.
(a)
n = 50 (b)
n = 100 (c)
n = 200In Figure2, in M/M/50/50+l model, the average queue length curve with increasing buffer changes smoothly. In M/M/100/100+l, then, the average queue length slowly increases. In M/M/200/200+l, the change of the buffer size does not affect the average queue length. From Figure 2, we can provide a buffer to ease the pressure on scarce resources in the system, while it will not cause big losses. In terms of shared resources in cloud computing system, equitable distribution of resources is especially important. Thus, the establishment of a buffer can reduce the load on the system to some extent, and it improves the overall performance of the system.Figure3 shows the influence of different task arrival rate on resource consumer revenue.Figure 3
Influence between the number of VMs and revenue of resource consumers.Task arrival rate is defined as the number of tasks when tasks arrive per minute. For fixed task arrival rate, the revenue increases with an increasing number of VMs. The lesser the request of the number of VMs, the longer the waiting time and the higher the loss for users. Thus performance degradation speed is fast. As the request of the number of VMs increases, the price of resource consumers paying the provider will also increase. The change of revenue is from increase to decrease; at this situation, the optimal number of VMs can maximize resources consumer revenue.We set different number of resource providers, to make a research on the influence between the different size of the market resources and the convergence property. We give the number of resource providers from 3 to 6. With these numbers of resources providers, Figures4(a) and 4(b) show how the utility changes with the number of iterations at the NCGRAA algorithm.Figure 4
Influence on the utility with NCGRAA.
(a) (b)In Figures4(a) and 4(b), initially, the resource providers constantly adjust strategy, to seek the best Nash equilibrium solution for resources provided. Subsequently, utility tends to be steady, and the resources reach equilibrium. At the same time, the lesser the number of resource providers is, the faster the NCGRAA algorithm can converge. As the number of resource providers increases, more iteration is needed to achieve utility state of stability. The overall situation is that the strategy can get a good convergence.The results above indicate the robustness and convergence of the NCGRAA algorithm. In convergence condition, the number of the VMs to provide is the focus problem in Nash equilibrium strategy for resource provider; therefore, the cooperation in the market resource provider can timely adjust the strategy to achieve Nash equilibrium.The third set of experiments investigates the performance of several algorithms, including the average utility, system throughput, and fairness.Figures5(a) and 5(b) show the changes of utility with BGRAA algorithm under different size of the market, the initial parameters, and size of the market that is the same to NCGRAA algorithm’s.Figure 5
Influence on the utility with BGRAA.
(a) (b)It can be seen in Figures5(a) and 5(b) that, with the increase of number of resource providers, more iteration is needed to achieve Nash bargaining equilibrium strategies. Namely, the Nash bargaining solution is in the Pareto optimal set which makes the products of the utility maximize. When utility has reached the convergence, then Pareto optimal solution reaches the border part of the negotiation strategy sets. At this point, the corresponding negotiation strategies and the corresponding utility for all resource providers are fair.Figure6 shows the influence of the amount of resources consumers on the average utility of the resource provider. It can be seen in Figure 6, with the increase of number of consumers, that utility increases. This is due to the increase of resource request. In addition, for the same resource consumer number, the effectiveness of the algorithm BGRAA is always higher than or equal to the utility of NCGRAA algorithm. This is because in bargaining negotiation among resources providers can reduce the number of VMs but enhance the utility of resource prices. In the market competition, resource providers compete against each other for more VMs. The disadvantage of this issue is that the resource price is low. Then the overall effect cannot achieve the maximum, but it can achieve the optimal value. Each HM or GM adjusts resource prices, based on general equilibrium without considering the relationship between competition and cooperation. Thus the average utility of HM and GM is lower than the ones of NCGRAA and BGRAA.Figure 6
Influence of resource provider number on the system average utility.Figure7 shows the change of system throughput. It can be seen in Figure 7 that as the number of resource providers increases the number of tasks per unit time also increases. Therefore, the system throughput has increased continuously. The throughput of BGRAA algorithm is the biggest of these algorithms by reducing resource price offering more VMs. In NCGRAA algorithm, when the total utility increases at the same time, the throughput increases. Although the HM and GM without the game theory are effective, they are not suitable for the system with some market parameters.Figure 7
Influence of resource provider number on the system throughput.Figure8 shows the fairness of the comparison results. The fairness of the allocation of resources in the cloud computing is significantly important. In BGRAA algorithm, performance parameter π is related to fairness and the throughput. It can be seen from Figure 8, along with the increase of the number of resource providers, that the change trend of HM and GM is bigger than that of NCGRAA and BGRAA algorithms. HM and GM algorithms ignore the mutual relationship between resource providers and resource allocation. The NBS of BGRAA algorithm encourages devotion to their utility. In NCGRAA algorithm, the utility is optimal and fairness principle is stable.Figure 8
Influence of resource provider number on the fairness.As shown in Figure9, it can be seen that with the increasing number of consumers utility increases, because of the number of requested resources. As can be seen from Figure 9, the effectiveness of the algorithm is always higher than or equal to the utility algorithms. This is because in the negotiable market consultations between the resource providers can reduce the number of VMs and reach higher resource prices and utility. In noncooperative market competition, the resource providers provide more VMs competing for more market sharing. However, with lower resource prices, the overall effectiveness only achieves mutual optimum. GEA algorithm does not consider competition and cooperation between providers of resources. And the resources are adjusted according to consumers’ needs. That is bounded to affect the individual income.Figure 9
Comparison of average utility in different algorithms.Figure10 shows the changes in system throughput; it can be seen that with the increased number of resource providers the number of tasks processed per unit of time also increases, so system throughput increases. NCGRAA by reducing resource prices provides more VMs and obtains the maximum throughput. On the contrary, the total utility increases with the loss of some throughput. GEA’s throughput improvement curve is lower than the algorithms without considering cooperation competition between resources and users.Figure 10
Comparison of throughput in different algorithms.Figure11 shows a fair comparison of the three algorithms. In the algorithm BGRAA, the parameter π is involved in fairness and throughput. As can be seen from the figure, as the number of resource providers increases, trends of NCGRAA and BGRAA are significantly greater than the GEA, which ignores the interaction between resource providers and lacks fairness. The welfare of bargaining between the two sides attaches great importance. It does not encourage the two sides to pursue their own utility while ignoring the other utilities.Figure 11
Comparison of fairness in different algorithms.


## 7. Conclusion

The high efficiency and stable resources mechanism is needed for study of cloud computing resources management. Therefore, NCGRAA and BGRAA algorithms were proposed in this paper to solve this problem. The algorithms made competing resource allocation converge to the Nash equilibrium strategy. Meanwhile, algorithms bring resource competitors optimal benefits and improved collective benefits. Based on the numerical results of some key performance measures, we discussed the influence of NCGRAA and BGRAA algorithms. These algorithms not only ensured fair constraints, but also improved the efficiency of resource allocation. Meanwhile, it also shows that NCGRAA and BGRAA algorithms result in the slight increase of consumption.In this work, we only focus on the resource allocation in the cloud computing. As a future work, we will extend the research by considering data transmission in other specific circumstances and security transaction in the negotiation process.



---

*Source: 1629893-2016-10-30.xml*