# Cooperative Game-Based Virtual Machine Resource Allocation Algorithms in Cloud Data Centers

Authors: Sungwook Kim
Journal: Mobile Information Systems
 (2020)

---

## Abstract

With the growing demand of cloud services, cloud data centers (CDCs) can provide flexible resource provisioning in order to accommodate the workload demand. In CDCs, the virtual machine (VM) resource allocation problem is an important and challenging issue to provide efficient infrastructure services. In this paper, we propose a unified resource allocation scheme for VMs in the CDC system. To provide a fair-efficient solution, we concentrate on the basic concept ofShapley value and adopt its variations to effectively allocate CDC resources. Based on the characteristics of value solutions, we develop novel CPU, memory, storage, and bandwidth resource allocation algorithms. To practically implement our algorithms, application types are assumed as cooperative game players, and different value solutions are applied to optimize the resource utilization. Therefore, our four resource allocation algorithms are jointly combined as a novel fourfold game model and take various benefits in a rational way through the cascade interactions while solving comprehensively some control issues. To ensure the growing demand of cloud services, this feature can leverage the full synergy of different value solutions. To check the effectiveness and superiority of our proposed scheme, we conduct extensive simulations. The simulation results show that our algorithms have significant performance improvement compared to the existing state-of-the-art protocols. Finally, we summarize our cooperative game-based approach and discuss possible major research issues for the future challenges about the cloud-assisted DC resource allocation paradigm.


---

## Body

## 1. Introduction

Nowadays, Internet of Things (IoT) has created many exciting applications, and they generate big volume of data. Therefore, there is a strong need to conduct analysis on the big data to support various data-driven services. To meet the ever-increasing demand of applications and services, cloud computing has recently been brought into focus in both academia and industry. The advent of cloud computing has given rise to new and exciting prospects for individuals, small- and medium-sized enterprises, and large organizations who can flexibly lease processing, storage, and network resources on-demand. Due to their temporal needs of cloud services, we have witnessed the rapid growth of cloud data centers (CDCs) in the past few years, and expect the number of CDCs will triple by 2020 [1, 2].To handle the rapid increment of computation requirements, CDCs provide unparalleled large-scale computational capability and ubiquitous data accessibility, which can make service more acceptable. Conventionally, CDCs are warehouses that host tens of thousands of servers, providing data-processing service and enabling communications among large amounts of computing resources. These servers may be used to provide different services to individual users over the Internet and to benefit from economy of scale to reduce computational costs. Therefore, CDC infrastructures, which are maintained and managed at scale by local as well as global operators such as Amazon, Rackspace, Microsoft, and Google, are widely used to offer as-a-services such as data-intensive applications, including query, web service, and big data analytics [2, 3].The properties of CDCs and the mechanisms for limited resource allocations largely define the operation and performance of the CDC system. In order to be sustainable, the significant capital outlay required for building a CDC makes maximization of Return on Investment (RoI) crucial, which in turn necessitates efficient and adaptive CDC resource usage. Moreover, the economic viability of a CDC greatly depends on running the CDC at acceptable performance levels and allowing users and applications to highly utilize and share its infrastructure and resources. In summary, the performance of CDCs is directly associated with how to improve the resource usability. However, the average CDC resource utilization has found to be low, typically ranging from 10 to 20 percent. Therefore, it is necessary to increase the resource utilization for the CDC system efficiency [2, 4, 5].Recently, virtualization technology has been touted as a revolutionary technology to tackle the low-utilization problem in CDCs. Initially, virtualization began in the 1960s, as a method of creating a virtual version of something, including virtual computer hardware platforms, storage devices, and computer network resources. Since then, the meaning of the term has broadened. In CDCs, different physical resources are logically partitioned and multiplexed among different applications. Through virtualization technology, virtual machines (VMs) are created according to users’ demands, and users execute their applications on the VMs that are indeed running on physical machines (PMs). Usually, multiple VMs can be created on a PM using the virtualization software. Therefore, PM resource distribution for VMs is a hot research topic to improve the PM utilization. With multiple resource requests, finding an optimal solution of PM resource distribution problem will thus create a lot of challenges to the researchers. However, under a complicated scenario, traditional resource allocation approach suffers from extremely high computational complexity and control overhead. Therefore, we need a new control paradigm to effectively mediate between the implementation practicality and the system optimality [5, 6].


### 1.1. Cooperative Game-Based Value Solutions

Game theory is a theoretical framework for conceiving situations among competing players. In some respects, game theory is the science of strategy, or at least the optimal decision-making of independent and competing players in a strategic setting. Game theory has two major subdivisions: noncooperative and cooperative game theory. In cooperative game theory, rational players will find ways to commit themselves to the agreement and enjoy the benefits that arise from the agreement. Indeed, one possibility is that a group of players may cooperate to exploit another player or group of players. Thevalue is a central solution concept in the cooperative game theory. In 1953, the basic concept of value was introduced by Shapley for the study of cooperative games. And then, the idea of value solutions has been extended in different ways; some of the most notable values solutions are developed by Harsanyi and Shapley [7].Recently,value-based cooperative game approaches have been widely investigated to solve the resource allocation problems. In this study, we design a new VM resource allocation scheme based on four value solutions; Shapley value (SV), weighted Shapley value (WSV), proportional Shapley value (PSV), and weighted-egalitarian Shapley value (WESV). They exhibit a number of interesting axiomatic properties and can be supported from a game-theoretic perspective. To effectively distribute four different CDC infrastructure resources, i.e., CPU, memory, storage, and bandwidth, these four solutions can be individually applied to ensure mutual advantages, and they are integrated into a fourfold game model to reach an effective solution. During the resource allocation process, CDC control agents make their control decisions to achieve a globally desirable system performance while effectively balancing between efficiency and fairness.


### 1.2. Main Research Objectives

To provide a fair-efficient solution for the VM resource allocation problem in the CDC system, we concentrate on the cooperative game-basedvalue solutions. Our major research objectives are summarized as follows:(i)
According to the cooperative game theory, we explore the main concepts ofvalue-based solutions to solve the VM resource allocation problem in CDCs.(ii)
By using the SV, WSV, PSV, and WESV solutions, we develop novel CPU, memory, storage, and bandwidth resource allocation algorithms for each PM. Therefore, the CDC’s resource allocation problem is divided into four component parts, and our developed algorithms work together and act cooperatively with each other to enhance the system performance.(iii)
We create a new collaborative fourfold game model by jointly employing four different resource allocation algorithms. Our integrated fourfold game approach can achieve mutual advantages through attractive axiomatic properties.(iv)
We can effectively strike the appropriate performance balance between contradictory requirements based on the synergy effect, which is a consequence of the reciprocal combination of differentvalue solutions.(v)
We conduct experiments on extensive simulations and analyze empirical results to demonstrate the effectiveness of our fourfold game approach. By discussing and analyzing the simulation results, we can confirm the superiority of our proposed scheme compared with the existing state-of-the-art protocols.


### 1.3. Organization

The remainder of this paper is organized as follows. In Section2, we discuss and summarize the related work followed by the objective of resource allocations in CDCs. Section 3 introduces the overall infrastructure of CDCs and provides background preliminaries about the SV, WSV, PSV, and WESV. And then, we outline the main steps of proposed algorithms and formulate our fourfold game model to design our CDC resource allocation scheme. Section 4 presents the experimental setup, simulation results, and performance evaluation. To validate the effectiveness of our approach, experiments are described while comparing our proposed scheme against the existing protocols. Finally, we conclude this study and discuss the future research directions in Section 5.


## 1.1. Cooperative Game-Based Value Solutions

Game theory is a theoretical framework for conceiving situations among competing players. In some respects, game theory is the science of strategy, or at least the optimal decision-making of independent and competing players in a strategic setting. Game theory has two major subdivisions: noncooperative and cooperative game theory. In cooperative game theory, rational players will find ways to commit themselves to the agreement and enjoy the benefits that arise from the agreement. Indeed, one possibility is that a group of players may cooperate to exploit another player or group of players. Thevalue is a central solution concept in the cooperative game theory. In 1953, the basic concept of value was introduced by Shapley for the study of cooperative games. And then, the idea of value solutions has been extended in different ways; some of the most notable values solutions are developed by Harsanyi and Shapley [7].Recently,value-based cooperative game approaches have been widely investigated to solve the resource allocation problems. In this study, we design a new VM resource allocation scheme based on four value solutions; Shapley value (SV), weighted Shapley value (WSV), proportional Shapley value (PSV), and weighted-egalitarian Shapley value (WESV). They exhibit a number of interesting axiomatic properties and can be supported from a game-theoretic perspective. To effectively distribute four different CDC infrastructure resources, i.e., CPU, memory, storage, and bandwidth, these four solutions can be individually applied to ensure mutual advantages, and they are integrated into a fourfold game model to reach an effective solution. During the resource allocation process, CDC control agents make their control decisions to achieve a globally desirable system performance while effectively balancing between efficiency and fairness.


## 1.2. Main Research Objectives

To provide a fair-efficient solution for the VM resource allocation problem in the CDC system, we concentrate on the cooperative game-basedvalue solutions. Our major research objectives are summarized as follows:(i)
According to the cooperative game theory, we explore the main concepts ofvalue-based solutions to solve the VM resource allocation problem in CDCs.(ii)
By using the SV, WSV, PSV, and WESV solutions, we develop novel CPU, memory, storage, and bandwidth resource allocation algorithms for each PM. Therefore, the CDC’s resource allocation problem is divided into four component parts, and our developed algorithms work together and act cooperatively with each other to enhance the system performance.(iii)
We create a new collaborative fourfold game model by jointly employing four different resource allocation algorithms. Our integrated fourfold game approach can achieve mutual advantages through attractive axiomatic properties.(iv)
We can effectively strike the appropriate performance balance between contradictory requirements based on the synergy effect, which is a consequence of the reciprocal combination of differentvalue solutions.(v)
We conduct experiments on extensive simulations and analyze empirical results to demonstrate the effectiveness of our fourfold game approach. By discussing and analyzing the simulation results, we can confirm the superiority of our proposed scheme compared with the existing state-of-the-art protocols.


## 1.3. Organization

The remainder of this paper is organized as follows. In Section2, we discuss and summarize the related work followed by the objective of resource allocations in CDCs. Section 3 introduces the overall infrastructure of CDCs and provides background preliminaries about the SV, WSV, PSV, and WESV. And then, we outline the main steps of proposed algorithms and formulate our fourfold game model to design our CDC resource allocation scheme. Section 4 presents the experimental setup, simulation results, and performance evaluation. To validate the effectiveness of our approach, experiments are described while comparing our proposed scheme against the existing protocols. Finally, we conclude this study and discuss the future research directions in Section 5.


## 2. Related Work

Different resource allocation in CDCs has become a compelling topic and has been widely studied in the literature. Until now, state-of-the-art literature studies have discussed the CDC resource allocation problem in various aspects, including resource utilization, cost, scalability, overhead, and system performance. In [8], authors propose two algorithms to enhance the multicast capacity. Both algorithms utilize the SDN-based controller system to handle multicast routing. The key motivation for this paper is the transition happening in the uncompressed video transport technologies from legacy non-IP format based on Serial Digital Interface (SDI) to transport based on IP. Major efforts are underway in the standard bodies to define standards and relevant encapsulations [8].The paper [9] proposes a network-aware VM relocation algorithm, which optimizes the distribution of the VMs running on the DC in order to conserve energy in both servers and network switches. It targets the communicated VMs and places them closer to each other while reducing the traffic overhead between any communicating VMs. This approach also increases the VMs consolidation to some servers while leaving other servers idle [9]. In [10], Wardat et al. propose a new holistic view how to ensure the increasing demands for cloud services while guaranteeing the maximum revenue. They include the power usage optimization technique using a server consolidation approach through a formulation of the problem taking into account the need for DC expansion while reducing the total operational cost. The server consolidation is achieved by powering off the underutilized servers without impacting the system ability to satisfy the customers’ service requirements [10].TheTwo-Tiered Resource Allocation (TTRA) scheme proposes a two-tiered on-demand resource allocation mechanism to find a dynamic resource allocation solution [1]. To solve the problem of on-demand resource provision for VMs, the TTRA scheme is consisting of the local and global resource allocation methods to improve the efficiency of CDCs. On each server, the local on-demand resource allocation method optimizes the resource allocation to VMs while considering the allocation threshold. The global on-demand resource allocation method optimizes the resource allocation among applications at the macro level by adjusting the allocation threshold of each local resource allocation. Local and global resource schedulers reallocate resources by evaluating the arriving workloads. To guide the design of the on-demand resource allocation algorithms, the TTRA scheme dynamically allocates CDC resources to VMs according to the time-varying capacity demands and the quality requirements of applications [1].In the paper [6], the Multiobjective Resource Allocation (MORA) scheme is a new Euclidean distance-based multiobjective resource allocation method for CDCs [6]. This scheme mainly focuses on the key goals of multiobjective VM allocation on PMs in CDCs in terms of energy efficiency and minimization of resource wastage. In particular, a hybrid mechanism based on genetic algorithm (GA), particle swarm optimization (PSO), and Euclidean distance is developed to achieve an optimal point of energy efficiency and resource utilization. The core idea of this scheme is to apply the GA for the generation of initial VMs allocation on PMs and then apply the PSO for the improvement of the initial solution. Finally, the hybrid approach can get the near global optimal solution of the VM allocation problem. The main objectives of the MORA scheme are (i) to formulate the VM allocation problem as a multiobjective multidimensional combinatorial optimization problem and (ii) to adaptively allocate the multiple resources of VMs while minimizing the resource wastage at CDCs [6].Dai et al. propose theVirtual Scheduling-based Resource Allocation (VSRA) scheme by considering the placement of VMs onto the servers in CDCs intelligently [11]. The VM placement problem is formulated as an integer programming problem, and authors in [11] explore two greedy approximation algorithms: the minimum energy VM scheduling (MinES) algorithm and the minimum communication VM scheduling (MinCS) algorithm. The main goal of MinES and MinCS is to achieve a good feasible solution. In particular, the MinES algorithm avoids powering up extra servers and networking devices by placing VMs on active servers. The MinCS algorithm attempts to allocate the VMs to decrease the total energy consumption on both network and servers. Both algorithms start from the solution of the relaxed original integer program and attempt to round the solution intelligently to achieve the minimum energy consumption. The search for the solution in both heuristic algorithms is guided by a relaxed version of the original problem [11].There is also much work done on the resource allocation methods related to the VM placement in CDCs. Especially, the TTRA, MORA, and VSRA schemes have attracted a lot of attentions, recently; they have introduced unique challenges to efficiently solve the resource allocation problem in the CDC system. Compared to these existing schemes in [1, 6, 11], we demonstrate that our proposed scheme attains a better performance during the CDC resource allocation operations.


## 3. Proposed CDC Resource Allocation Scheme

In this section, we introduce the infrastructure of the CDC system. Afterward, the basic ideas of SV, WSV, PSV, and WESV solutions are demonstrated to design our CDC resource allocation scheme. And then, the proposed protocol is presented in detail based on the fourfold game model. Finally, we describe concretely the proposed scheme in the nine-step procedures.


### 3.1. Cloud-Based DC System Infrastructure

The CDC architecture is a well-known multitier system infrastructure, which is composed of routers, switches, and a large number of PMsℙ=PM1,PM2,…,PMn. Each PM has four different resources, and the resource of PM1≤i≤n is characterized by a tuple ℝPMi⟶=ℝPMiC,ℝPMiM,ℝPMiS,ℝPMiB, indicating the available resource capacities of PMi in terms of CPU power capacity ℝPMiC, memory size ℝPMiM, storage space ℝPMiS, and communication bandwidth ℝPMiB, respectively. To monitor the available resources, an intelligent agent (IA) is deployed in each PM and periodically adjusts its ℝPM⟶. Each IA distributes its associated PM’s resources according to the currently updated ℝPM⟶ information [6, 11, 12].To implement the CDC management paradigm, the time axis is partitioned into equal intervals of lengthunit_time Δt. At each Δt, application tasks are received in the CDC, and VMs are generated to support the requested tasks. In this study, we assume four different application types I,II,III,IV. Based on the application types, execution of VMs requires different resource amounts with diversified preferences. For a given VMj∈V=VM1,VM2,…, the required resource specification and preference are described by ℛVMj⟶=ℛVMjC,ℛVMjM,ℛVMjS,ℛVMjB and αVMj⟶=αTVMjC,αTVMjM,αTVMjS,αTVMjB, respectively, where TVMj∈I,II,III,IV is the application type of VMj. During the CDC operation, V⋟ℙ and ℛVM⟶ and αVM⟶ are differently decided for each VM. Therefore, multiple VMs are nested in each PM [6, 11, 12]. The utility function UVMjℛVMj⟶,αVMj⟶ of VMj is defined based on the allocated resources of associated PM; UVM· maps service quality of the target to a benefit value:(1)UVMjℛVMj⟶,αVMj⟶,TVMj,X=∑X∈C,M,S,BαTVMjX×11+expAVMjX/ℛVMjX−β,where AVMjC, AVMjM, AVMjS, and AVMjB are the allocated CPU, memory, storage, and bandwidth resources, respectively, from the associated PM. β is a control parameter to calculate the UVM·. When a new application is arrived at the CDC, the corresponding VM is generated. And then, it should be assigned a specific PM by the CDC controller. In the proposed scheme, we design a novel VM placement method by considering the PM’s resource availability. From a commonsense standpoint, our VM placement approach can be interpreted as a compromise solution between the weighted proportionality and the utilitarian solution. According to (2), the new VMj is matched the selected PMi∈M where the PMi is the most adaptable PM to nest the VMj:(2)MATVMj,TVMj,PMi≔maxPMi∈ℙ∑X∈C,M,S,BαTVMjX×ℝPMiX−ℛVMjX.At each PM, the IA monitors and distributes its resources for assigned VMs. To effectively share the limited resources, we adopt the cooperative game approach. In this paper, we assume that each PM has four different resourcesC,M,S,B. Therefore, four different cooperative games are developed individually and independently for each resource distribution in a PM. At each Δt, these games are executed in a dispersive and parallel manner. Therefore, we can effectively reduce the computation complexity. At each game model, each application type TVM∈I,II,III,IV of VM is assumed as an individual game player, i.e., PI, PII, PIII, and PIV, and utility functions for players are formulated. First, in the PMi, the utility functions for the CPU capacity C, i.e., UIC, UIIC, UIIIC, and UIVC, are defined as follows:(3)UICℛVMk⟶,αVMk⟶=∑VMk∈PMilogℛVMkC+γαIC×ℛVMkC,UIICℛVMk⟶,αVMk⟶=∑VMk∈PMilogℛVMkC+γαIIC×ℛVMkC,UIIICℛVMk⟶,αVMk⟶=∑VMk∈PMilogℛVMkC+γαIIIC×ℛVMkC,UIVCℛVMk⟶,αVMk⟶=∑VMk∈PMilogℛVMkC+γαIVC×ℛVMkC,where γ is a control factor to calculate the UI∼IVC·. And then, as the same manner as the UI∼IVC, utility functions for other PM resources such as M, S, and B, i.e., UI∼IVM, UI∼IVS, and UI∼IVB, are defined, respectively. At each Δt, UI∼IVC, UI∼IVM, UI∼IVS, and UI∼IVB are examined periodically by the IA, and the C, M, S, and B resources in each individual PM are distributed for its corresponding VMs.


### 3.2. Main Concepts of Value-Based Cooperative Solutions

In 1953, the concept ofvalue in cooperative games was introduced by Shapley. It is the most eminent allocation rule for cooperative games with transferable utility. His initial idea was to answer the question of what a player may reasonably expect from playing a game. As a normative tool to achieve efficiency and symmetry, the SV has received considerable attention in numerous fields and applications. Many axiomatic characterizations have helped to understand the mechanisms underlying the SV. In 1959, the concept of dividend was introduced by Harsanyi; it can be defined inductively. The dividend of the empty set is zero and the dividend of any other possible coalition of a player set equals the worth of the coalition minus the sum of all dividends of proper subsets of that coalition. Therefore, the dividend identifies the surplus that is created by a coalition of players in a cooperative game, and it can be interpreted as the pure contribution of cooperation in a game. Harsanyi shows that the SV coincides with the payoff that results from the equal division of dividends within each coalition [13, 14].In 1953, Shapley did consider the possibility for symmetric players to be treated differently. This asymmetric version of the SV is obtained by introducing exogenous weights in order to cover asymmetries. The concept of WSV was introduced as an allocation rule based on weighted contributions, and it had been axiomatized by Kalai and Samet in 1987. Simply, the SV splits equally thedividend of each coalition among its members, but the WSV splits the Harsanyi dividends in proportional to the exogenously given weights of its members. Weights are given by the stand-alone worths of the players, and the value associated with positive weights turns out to result from a weighted division of dividends within each coalition. Thus, it coincides with the SV whenever all such worths are equal [14].PSV is another value solution. It is similar in spirit to the WSV. Therefore, the PSV inherits many of the properties of the WSV. However, contrary to the WSV, the PSV reserves the equal treatment property; it is a well-defined solution for games in which the worths of all singleton coalitions have the same sign. Based on the proportional principle, the PSV satisfies proportional aggregate monotonicity, but does not satisfy the classical axioms of linearity and consistency [13].After the introduction of SV-related solutions, many other axiomatic foundations for the rule were intensively studied. Usually, the SV is an efficient rule that satisfiesstrong monotonicity and symmetry. As redistribution rules, these two properties focus on each player’s contributions in a game to determine their rewards. Therefore, the SV can be thought of as an allocation rule completely based on each player’s performance. Recently, we face the following question: what allocation rule reconciles performance-based evaluation with a solidarity principle and takes players’ heterogeneity into consideration? To answer this question, a new solution, called WESV, was introduced based on the combination of the SV and the weighted division. This solution satisfies weaker monotonicity; this property does not require each player’s evaluation to depend only on his contribution but rather allows it to depend also on the worth of the grand coalition to reflect a solidarity principle [15].To characterize the basic concepts ofvalue-based solutions, we preliminarily define some mathematical expressions. ℝℝ+,ℝ++ denote the set of all (nonnegative, positive) real numbers. ℕ will denote the set of positive integers. Let U⊆ℕ be a fixed and infinite universe of players. Denote by U the set of all finite subsets of U is denoted by U. A cooperative game is a pair N,v where N∈U and v:2N⟶ℝ such that v∅=0. For a game N,v, we write S,v for the subgame of N,v induced by S⊆N by restricting vto 2S; the real number vS is the worth of S, which the members of the coalition S can distribute among themselves. Let ℝNℝ+N,ℝ++N be the N-fold Cartesian product of ℝℝ+,ℝ++. A game N,v is individually positive if vi>0 for all i∈N and individually negative if vi<0 for all i∈N [13].DefineC as the class of all games with a finite player set N. Let N,v∈C, and the Harsanyi dividends ΔN,vS, where S⊆N, are defined inductively as follows [13, 16]:(4)ΔN,vS=vS−∑T⊂SΔN,vT,ifS∈2N,0,ifS=∅,s.t.,vS=∑T⊆SΔN,vT.This formula shows thatdividends uniquely determine the characteristic function. Another well-known formula of the dividends is given for all S⊆N and S≠∅, by the following equation [17]:(5)ΔN,vS=∑T⊆S−1s−t×vTi.e.,Δvi=viΔvi,j=vi,j−vi−vjΔvi,j,k=vi,j,k−vi,j−vi,k−vj,k+vi+vj+vk⋮In terms of the distribution of the Harsanyidividends, the SV is the value ϕ on Cdefined as follows [13]:(6)ϕiN,v=∑S∈2N;i∈S1S×ΔN,vS,s.t.,∀N,v∈C,∀i∈N.The WSV with weightsw, where w=wi∈ℝ++i∈N and ∑i∈Nwi=1, is the value ϕw on C defined as follows [13]:(7)ϕiwN,v=∑S∈2N;i∈Swi∑j∈Swj×ΔvS,s.t.,∀N,v∈C,∀i∈N.The PSV is the valueϕP on C defined as follows [13]:(8)ϕiPN,v=∑S∈2N;i∈Svi∑j∈Svj×ΔsS,s.t.,∀N,v∈C,∀i∈N.The WESV is the valueϕw−E on C defined as follows [15]:(9)ϕiw−EN,v=δ×ϕiN,v+1−δ×wi×vNs.t.,∀N,v∈C,∀i∈N,δ∈0,1,wi∈N∈ℝ++.Ifδ=1, the ϕiw−EN,v values coincides with the SV and distributes the surplus vN based only on the players’ contributions. If δ=0, the ϕiw−EN,v coincides with the weighted division [15].All the value-based solutions are characterized by a collection of desirable axioms—Homogeneity, Monotonicity, Weak Monotonicity, Symmetry, Balanced Contributions, Efficiency, Proportional Balanced Contributions, w-Balanced Contributions, Dummy Player Out, Ratio Invariance for Null Players, Proportional Aggregate Monotonicity, Proportional Standardness, Standardness, Weak Linearity, Consistency, Weak Consistency, Weak Differential Marginality for Symmetric Players, and Nullity [13, 15]. To explain these axioms, we need some prior definitions. A value on C is a function f that assigns a payoff vector fN,v∈ℝN to any N,v∈C and S∈2N\∅. Let QA denote the class of all quasiadditive games. In a quasiadditive game, the worths of all coalitions are additive except, possibly, for the grand coalition for which there can be some surplus or loss compared to the sum of the stand-alone worths of its members. Based on the S and f, the reduced game S,vSf is defined for all ∈2S [13]:(10)vSfT=vT∪N\S−∑i∈N\SfiT∪N\S,v.The concept of the reduced game is used to define the axiomconsistency. If f satisfies the axiom efficiency, vSfT=∑i∈TfiT∪N\S,v [13]:(i)
Homogeneity (H): for allN,v∈C,i∈N, and α∈ℝ, we have fiN,αυ=αfiN,υ.(ii)
Monotonicity (M): for allN,v∈C and i∈N such that(11)fiυ≥fiυ′,s.t.,υS=υ′S,forS⊊N,υS≥υ′S,forS=N.(iii)
Weak Monotonicity (WM): for allN,v,N,v′∈C with vN≥v′N, if vS−vS\i≥v′S−v′S\i for all S⊆N with i∈S, then fiv≥fiv′.(iv)
Symmetry (Sym): for allN,v∈C and i,j∈N such that i and j are symmetric in N,υ, we have fiN,υ=fjN,υ.(v)
Balanced Contributions (BC): for allN,v∈C and all i,j∈N,(12)fiN,v−fiN\j,v=fjN,v−fjN\i,v.(vi)
Efficiency (E): for allN,v∈C, we have ∑i∈NfiN,v=vN.(vii)
Proportional Balanced Contributions (PBC): for allN,v∈C and all i,j∈N,(13)fiN,v−fiN\j,vvi=fjN,v−fjN\i,vvj.(viii)
w-Balanced Contributions (w-BC): for all w=wii∈U with wi∈ℝ++ for all i∈U, all N,v∈C, and all i,j∈N,(14)fiN,v−fiN\j,vwi=fjN,v−fjN\i,vwj.(ix)
Dummy Player Out (DPO): for allN,v∈C, if i∈N is a dummy player in N,v, then for all j∈N\i,fjN,v=fjN\i,v.(x)
Ratio Invariance for Null Players (RIN): for allN,v,N,v′∈C and i,j∈N such that i and j are null players in v,v′, we have fiv×fjv′=fiv′×fjv.(xi)
Proportional Aggregate Monotonicity (PAM): for allb∈ℝ and all N,v∈C such that n≥2, and all i,j∈N,(15)fiN,v−fiN,v+buNvi=fjN,v−fjN,v+buNvj.(xii)
Proportional Standardness (PS): for alli,j,v∈C,(16)fii,j,v=vivi+vj×vi,j.(xiii)
Standardness (S): for alli,j,v∈C, fii,j,v=vi+1/2vi,j−vi−vj.(xiv)
Weak Linearity (WL): for alla∈ℝ++N, all b∈ℝ, and all N,v,N,w∈C, if N,bv+w∈C, then fN,bv+w=bfN,v+fN,w.(xv)
Consistency (C): for allN,v∈C, all ∈2N, and all i∈S,fiN,v=fiS,vSf.(xvi)
Weak Consistency (WC): for allN,v∈QA, all S∈2N such that S,vSf∈QA, and all i∈S, fiN,v=fiS,vSf.(xvii)
Weak Differential Marginality for Symmetric Players (WDMSP): for allN,v,N,v′∈C and i,j∈N such that i and j are null players in v, if i,j are symmetric in v′ and vN=v′N, then fiv−fiv′=fjv−fjv′.(xviii)
Nullity (NY): letΘ be the null game. For any i∈N,fiΘ=0.The main notable difference between PBC andw-BC is that the weights are endogenous, i.e., they can vary across games. The consequence is that the system of equations generated by PBC together with E is not linear. Nevertheless, it gives rise to a unique nonlinear value. WL is combined with the axioms E and DPO. WM states that a player’s payoff weakly increases as his marginal contributions and the total value weakly increase. In contrast with M, WM does not insist that each player’s evaluation totally depends on his contributions but rather allows that it can depend on the total value. RIN requires that as long as some players say i,j and contribute zero in both games v and v′, the ratio of their payoffs, fiv/fjv, does not vary. N is a weak feasibility condition, which requires that every player receives nothing if every coalition’s worth is zero [13, 15]. In conclusion, SV can be characterized by axioms—BC, S, Sym, E, C, H, M, DPO, WL, and WC. The WSV can satisfy the axioms E, H, M, w-BC, DPO, and WL for all possible weights w. The PSV is the unique value on C that satisfies E, H, M, DPO, PAM, PS, WL, WC, and PBC. The WESV satisfies the axioms E, Sym, WM, RIN, WDMSP, and N [13, 15].


### 3.3. PM Resource Allocation Algorithms for VMs

In general, the limited CDC resource distribution problem mathematically corresponds to a bankruptcy game situation. A standard bankruptcy game is given by a finite game player setN, a real positive estate number E, and a nonnegative claim vector d=d1,…,dn∈ℝN while satisfying ∑i∈Ndi≽E. In the analysis of bankruptcy situation, the main objective is to obtain a satisfactory mechanism for distributing the estate while verifying two properties: the estate has to be completely distributed among the game players, and each player has to obtain a nonnegative quantity not greater than their demand. A bankruptcy rule is a map f which assigns to a payoff vector fN,E;d∈ℝN such that [18](17)∑i∈Nxi=E,s.t.,0≼xi≼difor alli∈N.For the bankruptcy problemN,E;d, a corresponding cooperative bankruptcy game N,vE;d can be defined as follows [18]:(18)vE;dS=max0,E−∑j∉Sdj.For the SV, WSV, PSV, and WESV, the above bankruptcy rule can be applied to calculate the characteristic functionν for the coalition S (νS). From the viewpoint of PMi, the IA of PMi observes its resource distribution status and adjusts its tuple ℝPMi⟶ at each Δt. If the PMi’s available resources are not sufficient to support the corresponding VMs’ requests, the limited resources must be shared intelligently taking into account differences of application types.In this study, we adopt thevalue-based cooperative solutions to design our PM resource allocation algorithms. For each PM, its ℝPMC,ℝPMM,ℝPMS, and ℝPMB resources are shared by game players PI∼IV, which represent application types. According to (3), each player has its own utility function UX with X∈C,M,S,B where UX represents the amount of satisfaction of a player toward the outcome of resource distribution. The higher the value of the utility, the higher the satisfaction of the player for that outcome. To calculate the characteristic function vS of each coalition S, we use the PI∼IV’ claim vector dX=dIX,dIIX,dIIIX,dIVX where dIX=UIXℛVM⟶,αVM⟶, dIIX=UIIXℛVM⟶,αVM⟶, dIIIX=UIIIXℛVM⟶,αVM⟶, and dIVX=UIVXℛVM⟶,αVM⟶.For thePMi, we individually develop the ℝPMiC,ℝPMiM,ℝPMiS, and ℝPMiB resource allocation algorithms. First, to design the ℝPMiC resource allocation algorithm, we consider the features of CPU computation and emphasize the characteristics of S and C axioms. Therefore, we adopt the SV idea as a solution. Based on the UI∼IVCℛVM⟶,αVM⟶, the players’ claim vector dC is defined, and vS values are obtained using the bankruptcy rule. And then, the players PI∼IV share the limited ℝPMiC resource according to (6). Therefore, the ℝPMiC is divided at the rate of ϕ values, and the assigned ℝPMiC for the PICPIPMi is given by(19)CPIPMi=ϕPIN,v∑i∈NϕiN,v×ℝPMiC,s.t.,N=PI,PII,PIII,PIV,ℝPMC=∑i∈NCiPMi.Finally, theCPIPMi should be distributed to the type I VMs in the PMi. In our proposed algorithm, the utilitarian idea is taken. In the viewpoint of efficiency, this idea attempts to maximize the sum of VMs’ effectiveness:(20)argmax…,AVMjC,…∑VMj∈PMiUVMjℛVMj⟶,αVMj⟶,TVMj,C,s.t.,CPIPMi=∑VMj∈PMiAVMjC.To design theℝPMM resource allocation algorithm, we consider the features of memory space and emphasize the characteristics of w-BC axiom. Therefore, we adopt the WSV idea as a solution to develop the ℝPMM resource allocation algorithm, and the weight w of each player is assigned as his preference αTM. And then, the players PI∼IV share the limited ℝPMM resource according to (7), and the assigned ℝPMM for each player is distributed among the same-type individual VMs by using the utilitarian idea as the same manner as the ℝPMC resource allocation algorithm.To design theℝPMS resource allocation algorithm, we consider the features of PM storage and emphasize the characteristics of PAM, PS, and PBC axioms. Therefore, we adopt the PSV idea as a solution to develop the ℝPMS resource allocation algorithm. The players PI∼IV share the limited ℝPMS resource according to (8), and the assigned ℝPMS for each player is distributed among the same-type individual VMs as the same manner as the ℝPMC and ℝPMM resource allocation algorithms. To design the ℝPMB resource allocation algorithm, we consider the features of PM communication bandwidth and emphasize the characteristics of RIN, WDMSP, and N axioms. Therefore, we adopt the WESV idea as a solution to develop the ℝPMB resource allocation algorithm, and the players PI∼IV share the limited ℝPMB resource according to (9), and the assigned ℝPMB for each player is distributed among the same-type individual VMs as the same manner as the ℝPMC, ℝPMM, and ℝPMS resource allocation algorithms.


### 3.4. Main Steps of the Proposed CDC Resource Allocation Scheme

The advent of cloud computing is looking forward to leasing out multiple instances of data centers. In addition, CDC resources can be shared amongst multiple users by using the virtualization technology while preventing hard resource commitment and low system utilization. VMs can be dynamically allocated over a DC infrastructure in order to improve application performance for the users and at the same time efficiently utilize the CDC’s physical resources. In this study, we focus on the main ideas of SV, WSV, PSV, and WESV solutions to solve the resource allocation problem for VMs in the CDC system. As we have asserted throughout this study, the proposed fourfold cooperative game approach is effectively advantageous under different and diversified CDC system situations.Our fourfold cooperative game approach can be analyzed in two different ways. From a theoretical point of view, each solution for separate resource allocation process can be featured by different axioms; they characterize each solution concept and provide a sound theoretical basis. From a practical point of view, our main concern is to reduce the computation complexity. Usually, traditional optimal solutions need huge computational overheads according to their complicated and complex computation formulas. Therefore, they are impractical in real-time process. In our game model, game players are not individual applications, but application types; it can effectively reduce the computational load. The principle novelties of our approach are a judicious mixture of differentvalue-based solutions and its adaptability, flexibility, and practicality to current system conditions of the CDC infrastructure. The main steps of the proposed scheme are described as follows:Step 1: at the initial time, system factors and control parameters are determined by a simulation scenario (refer to simulation assumptions and Table1 in Section 4).Step 2: at eachΔt, application tasks are received in the CDC, and VMs are generated as one of four types I,II,III,IV. Each VM has the resource specification ℛVM⟶ and preference αVM⟶. The utility function of VM is defined according to (1).Step 3: using (2), the new VM is nested to the most adaptable PM. In each PM, there are four resources ℝPMC,ℝPMM,ℝPMS,ℝPMB, and multiple VMs are placed. To design a game model, VM types are assumed as players, who compete with each other for the limited resources.Step 4: each game player’s utility functions for four resources are defined based on equation (3). At each Δt, they are examined periodically by each individual IA in a dispersive and parallel manner.Step 5: for theℝPMC resource allocation, the SV idea is adopted, and the limited ℝPMC is shared among game players according to (6). By using (20), the assigned ℝPMC for each player is distributed to the same-type individual VMs in the associated PM.Step 6: for theℝPMM resource allocation, the WSV idea is adopted, and the limited ℝPMM is shared among game players according to (7). By using the same manner as the ℝPMC resource allocation algorithm, the assigned ℝPMM for each player is distributed to the same-type individual VMs in the associated PM.Step 7: for theℝPMS resource allocation, the PSV idea is adopted, and the limited ℝPMS is shared among game players according to (8). By using the same manner as the ℝPMC and ℝPMM resource allocation algorithms, the assigned ℝPMS for each player is distributed to the same-type individual VMs in the associated PM.Step 8: for theℝPMB resource allocation, the WESV idea is adopted, and the limited ℝPMB is shared among game players according to (9). By using the same manner as the ℝPMC, ℝPMM, and ℝPMS resource allocation algorithms, the assigned ℝPMB for each player is distributed to the same-type individual VMs in the associated PM.Step 9: at each time period, each PM’sℝPM⟶ and utility functions of VMs are dynamically estimated in an online manner. Constantly, each IA in PM is self-monitoring, and proceed to Step 2 for the next fourfold cooperative game iteration.Table 1
System parameters used in the simulation experiments.
Type
ℛ
C
ℛ
M
ℛ
S
ℛ
B
α
I
C
,
α
II
M
,
α
III
S
,
α
IV
B
Execution duration average
I
1.2 GHz
350 MB
15 GB
35 Mbps
{0.3, 0.3, 0.2, 0.2}
120unit_time Δt
II
1.8 GHz
250 MB
20 GB
30 Mbps
{0.2, 0.4, 0.3, 0.1}
200unit_time Δt
III
2.5 GHz
150 MB
10 GB
45 Mbps
{0.1, 0.2, 0.3, 0.4}
150unit_time Δt
IV
3.3 GHz
100 MB
12 GB
25 Mbps
{0.4, 0.1, 0.2, 0.3}
250unit_time Δt
Parameter
Value
Description
n
12
Number of PMs in the CDC system
β
0.5
A control parameter to calculate theUVM·
γ
1
A control factor to calculate theUC·
δ
0.5
A control parameter to calculate theϕw−E·
ℝ
PM
C
100 THz
Initial CPU capacity for each PM
ℝ
PM
M
100 GMB
Initial memory size for each PM
ℝ
PM
S
1 PMB
Initial storage space for each PM
ℝ
PM
B
1.5 Gbps
Initial communication bandwidth for each PM


## 3.1. Cloud-Based DC System Infrastructure

The CDC architecture is a well-known multitier system infrastructure, which is composed of routers, switches, and a large number of PMsℙ=PM1,PM2,…,PMn. Each PM has four different resources, and the resource of PM1≤i≤n is characterized by a tuple ℝPMi⟶=ℝPMiC,ℝPMiM,ℝPMiS,ℝPMiB, indicating the available resource capacities of PMi in terms of CPU power capacity ℝPMiC, memory size ℝPMiM, storage space ℝPMiS, and communication bandwidth ℝPMiB, respectively. To monitor the available resources, an intelligent agent (IA) is deployed in each PM and periodically adjusts its ℝPM⟶. Each IA distributes its associated PM’s resources according to the currently updated ℝPM⟶ information [6, 11, 12].To implement the CDC management paradigm, the time axis is partitioned into equal intervals of lengthunit_time Δt. At each Δt, application tasks are received in the CDC, and VMs are generated to support the requested tasks. In this study, we assume four different application types I,II,III,IV. Based on the application types, execution of VMs requires different resource amounts with diversified preferences. For a given VMj∈V=VM1,VM2,…, the required resource specification and preference are described by ℛVMj⟶=ℛVMjC,ℛVMjM,ℛVMjS,ℛVMjB and αVMj⟶=αTVMjC,αTVMjM,αTVMjS,αTVMjB, respectively, where TVMj∈I,II,III,IV is the application type of VMj. During the CDC operation, V⋟ℙ and ℛVM⟶ and αVM⟶ are differently decided for each VM. Therefore, multiple VMs are nested in each PM [6, 11, 12]. The utility function UVMjℛVMj⟶,αVMj⟶ of VMj is defined based on the allocated resources of associated PM; UVM· maps service quality of the target to a benefit value:(1)UVMjℛVMj⟶,αVMj⟶,TVMj,X=∑X∈C,M,S,BαTVMjX×11+expAVMjX/ℛVMjX−β,where AVMjC, AVMjM, AVMjS, and AVMjB are the allocated CPU, memory, storage, and bandwidth resources, respectively, from the associated PM. β is a control parameter to calculate the UVM·. When a new application is arrived at the CDC, the corresponding VM is generated. And then, it should be assigned a specific PM by the CDC controller. In the proposed scheme, we design a novel VM placement method by considering the PM’s resource availability. From a commonsense standpoint, our VM placement approach can be interpreted as a compromise solution between the weighted proportionality and the utilitarian solution. According to (2), the new VMj is matched the selected PMi∈M where the PMi is the most adaptable PM to nest the VMj:(2)MATVMj,TVMj,PMi≔maxPMi∈ℙ∑X∈C,M,S,BαTVMjX×ℝPMiX−ℛVMjX.At each PM, the IA monitors and distributes its resources for assigned VMs. To effectively share the limited resources, we adopt the cooperative game approach. In this paper, we assume that each PM has four different resourcesC,M,S,B. Therefore, four different cooperative games are developed individually and independently for each resource distribution in a PM. At each Δt, these games are executed in a dispersive and parallel manner. Therefore, we can effectively reduce the computation complexity. At each game model, each application type TVM∈I,II,III,IV of VM is assumed as an individual game player, i.e., PI, PII, PIII, and PIV, and utility functions for players are formulated. First, in the PMi, the utility functions for the CPU capacity C, i.e., UIC, UIIC, UIIIC, and UIVC, are defined as follows:(3)UICℛVMk⟶,αVMk⟶=∑VMk∈PMilogℛVMkC+γαIC×ℛVMkC,UIICℛVMk⟶,αVMk⟶=∑VMk∈PMilogℛVMkC+γαIIC×ℛVMkC,UIIICℛVMk⟶,αVMk⟶=∑VMk∈PMilogℛVMkC+γαIIIC×ℛVMkC,UIVCℛVMk⟶,αVMk⟶=∑VMk∈PMilogℛVMkC+γαIVC×ℛVMkC,where γ is a control factor to calculate the UI∼IVC·. And then, as the same manner as the UI∼IVC, utility functions for other PM resources such as M, S, and B, i.e., UI∼IVM, UI∼IVS, and UI∼IVB, are defined, respectively. At each Δt, UI∼IVC, UI∼IVM, UI∼IVS, and UI∼IVB are examined periodically by the IA, and the C, M, S, and B resources in each individual PM are distributed for its corresponding VMs.


## 3.2. Main Concepts of Value-Based Cooperative Solutions

In 1953, the concept ofvalue in cooperative games was introduced by Shapley. It is the most eminent allocation rule for cooperative games with transferable utility. His initial idea was to answer the question of what a player may reasonably expect from playing a game. As a normative tool to achieve efficiency and symmetry, the SV has received considerable attention in numerous fields and applications. Many axiomatic characterizations have helped to understand the mechanisms underlying the SV. In 1959, the concept of dividend was introduced by Harsanyi; it can be defined inductively. The dividend of the empty set is zero and the dividend of any other possible coalition of a player set equals the worth of the coalition minus the sum of all dividends of proper subsets of that coalition. Therefore, the dividend identifies the surplus that is created by a coalition of players in a cooperative game, and it can be interpreted as the pure contribution of cooperation in a game. Harsanyi shows that the SV coincides with the payoff that results from the equal division of dividends within each coalition [13, 14].In 1953, Shapley did consider the possibility for symmetric players to be treated differently. This asymmetric version of the SV is obtained by introducing exogenous weights in order to cover asymmetries. The concept of WSV was introduced as an allocation rule based on weighted contributions, and it had been axiomatized by Kalai and Samet in 1987. Simply, the SV splits equally thedividend of each coalition among its members, but the WSV splits the Harsanyi dividends in proportional to the exogenously given weights of its members. Weights are given by the stand-alone worths of the players, and the value associated with positive weights turns out to result from a weighted division of dividends within each coalition. Thus, it coincides with the SV whenever all such worths are equal [14].PSV is another value solution. It is similar in spirit to the WSV. Therefore, the PSV inherits many of the properties of the WSV. However, contrary to the WSV, the PSV reserves the equal treatment property; it is a well-defined solution for games in which the worths of all singleton coalitions have the same sign. Based on the proportional principle, the PSV satisfies proportional aggregate monotonicity, but does not satisfy the classical axioms of linearity and consistency [13].After the introduction of SV-related solutions, many other axiomatic foundations for the rule were intensively studied. Usually, the SV is an efficient rule that satisfiesstrong monotonicity and symmetry. As redistribution rules, these two properties focus on each player’s contributions in a game to determine their rewards. Therefore, the SV can be thought of as an allocation rule completely based on each player’s performance. Recently, we face the following question: what allocation rule reconciles performance-based evaluation with a solidarity principle and takes players’ heterogeneity into consideration? To answer this question, a new solution, called WESV, was introduced based on the combination of the SV and the weighted division. This solution satisfies weaker monotonicity; this property does not require each player’s evaluation to depend only on his contribution but rather allows it to depend also on the worth of the grand coalition to reflect a solidarity principle [15].To characterize the basic concepts ofvalue-based solutions, we preliminarily define some mathematical expressions. ℝℝ+,ℝ++ denote the set of all (nonnegative, positive) real numbers. ℕ will denote the set of positive integers. Let U⊆ℕ be a fixed and infinite universe of players. Denote by U the set of all finite subsets of U is denoted by U. A cooperative game is a pair N,v where N∈U and v:2N⟶ℝ such that v∅=0. For a game N,v, we write S,v for the subgame of N,v induced by S⊆N by restricting vto 2S; the real number vS is the worth of S, which the members of the coalition S can distribute among themselves. Let ℝNℝ+N,ℝ++N be the N-fold Cartesian product of ℝℝ+,ℝ++. A game N,v is individually positive if vi>0 for all i∈N and individually negative if vi<0 for all i∈N [13].DefineC as the class of all games with a finite player set N. Let N,v∈C, and the Harsanyi dividends ΔN,vS, where S⊆N, are defined inductively as follows [13, 16]:(4)ΔN,vS=vS−∑T⊂SΔN,vT,ifS∈2N,0,ifS=∅,s.t.,vS=∑T⊆SΔN,vT.This formula shows thatdividends uniquely determine the characteristic function. Another well-known formula of the dividends is given for all S⊆N and S≠∅, by the following equation [17]:(5)ΔN,vS=∑T⊆S−1s−t×vTi.e.,Δvi=viΔvi,j=vi,j−vi−vjΔvi,j,k=vi,j,k−vi,j−vi,k−vj,k+vi+vj+vk⋮In terms of the distribution of the Harsanyidividends, the SV is the value ϕ on Cdefined as follows [13]:(6)ϕiN,v=∑S∈2N;i∈S1S×ΔN,vS,s.t.,∀N,v∈C,∀i∈N.The WSV with weightsw, where w=wi∈ℝ++i∈N and ∑i∈Nwi=1, is the value ϕw on C defined as follows [13]:(7)ϕiwN,v=∑S∈2N;i∈Swi∑j∈Swj×ΔvS,s.t.,∀N,v∈C,∀i∈N.The PSV is the valueϕP on C defined as follows [13]:(8)ϕiPN,v=∑S∈2N;i∈Svi∑j∈Svj×ΔsS,s.t.,∀N,v∈C,∀i∈N.The WESV is the valueϕw−E on C defined as follows [15]:(9)ϕiw−EN,v=δ×ϕiN,v+1−δ×wi×vNs.t.,∀N,v∈C,∀i∈N,δ∈0,1,wi∈N∈ℝ++.Ifδ=1, the ϕiw−EN,v values coincides with the SV and distributes the surplus vN based only on the players’ contributions. If δ=0, the ϕiw−EN,v coincides with the weighted division [15].All the value-based solutions are characterized by a collection of desirable axioms—Homogeneity, Monotonicity, Weak Monotonicity, Symmetry, Balanced Contributions, Efficiency, Proportional Balanced Contributions, w-Balanced Contributions, Dummy Player Out, Ratio Invariance for Null Players, Proportional Aggregate Monotonicity, Proportional Standardness, Standardness, Weak Linearity, Consistency, Weak Consistency, Weak Differential Marginality for Symmetric Players, and Nullity [13, 15]. To explain these axioms, we need some prior definitions. A value on C is a function f that assigns a payoff vector fN,v∈ℝN to any N,v∈C and S∈2N\∅. Let QA denote the class of all quasiadditive games. In a quasiadditive game, the worths of all coalitions are additive except, possibly, for the grand coalition for which there can be some surplus or loss compared to the sum of the stand-alone worths of its members. Based on the S and f, the reduced game S,vSf is defined for all ∈2S [13]:(10)vSfT=vT∪N\S−∑i∈N\SfiT∪N\S,v.The concept of the reduced game is used to define the axiomconsistency. If f satisfies the axiom efficiency, vSfT=∑i∈TfiT∪N\S,v [13]:(i)
Homogeneity (H): for allN,v∈C,i∈N, and α∈ℝ, we have fiN,αυ=αfiN,υ.(ii)
Monotonicity (M): for allN,v∈C and i∈N such that(11)fiυ≥fiυ′,s.t.,υS=υ′S,forS⊊N,υS≥υ′S,forS=N.(iii)
Weak Monotonicity (WM): for allN,v,N,v′∈C with vN≥v′N, if vS−vS\i≥v′S−v′S\i for all S⊆N with i∈S, then fiv≥fiv′.(iv)
Symmetry (Sym): for allN,v∈C and i,j∈N such that i and j are symmetric in N,υ, we have fiN,υ=fjN,υ.(v)
Balanced Contributions (BC): for allN,v∈C and all i,j∈N,(12)fiN,v−fiN\j,v=fjN,v−fjN\i,v.(vi)
Efficiency (E): for allN,v∈C, we have ∑i∈NfiN,v=vN.(vii)
Proportional Balanced Contributions (PBC): for allN,v∈C and all i,j∈N,(13)fiN,v−fiN\j,vvi=fjN,v−fjN\i,vvj.(viii)
w-Balanced Contributions (w-BC): for all w=wii∈U with wi∈ℝ++ for all i∈U, all N,v∈C, and all i,j∈N,(14)fiN,v−fiN\j,vwi=fjN,v−fjN\i,vwj.(ix)
Dummy Player Out (DPO): for allN,v∈C, if i∈N is a dummy player in N,v, then for all j∈N\i,fjN,v=fjN\i,v.(x)
Ratio Invariance for Null Players (RIN): for allN,v,N,v′∈C and i,j∈N such that i and j are null players in v,v′, we have fiv×fjv′=fiv′×fjv.(xi)
Proportional Aggregate Monotonicity (PAM): for allb∈ℝ and all N,v∈C such that n≥2, and all i,j∈N,(15)fiN,v−fiN,v+buNvi=fjN,v−fjN,v+buNvj.(xii)
Proportional Standardness (PS): for alli,j,v∈C,(16)fii,j,v=vivi+vj×vi,j.(xiii)
Standardness (S): for alli,j,v∈C, fii,j,v=vi+1/2vi,j−vi−vj.(xiv)
Weak Linearity (WL): for alla∈ℝ++N, all b∈ℝ, and all N,v,N,w∈C, if N,bv+w∈C, then fN,bv+w=bfN,v+fN,w.(xv)
Consistency (C): for allN,v∈C, all ∈2N, and all i∈S,fiN,v=fiS,vSf.(xvi)
Weak Consistency (WC): for allN,v∈QA, all S∈2N such that S,vSf∈QA, and all i∈S, fiN,v=fiS,vSf.(xvii)
Weak Differential Marginality for Symmetric Players (WDMSP): for allN,v,N,v′∈C and i,j∈N such that i and j are null players in v, if i,j are symmetric in v′ and vN=v′N, then fiv−fiv′=fjv−fjv′.(xviii)
Nullity (NY): letΘ be the null game. For any i∈N,fiΘ=0.The main notable difference between PBC andw-BC is that the weights are endogenous, i.e., they can vary across games. The consequence is that the system of equations generated by PBC together with E is not linear. Nevertheless, it gives rise to a unique nonlinear value. WL is combined with the axioms E and DPO. WM states that a player’s payoff weakly increases as his marginal contributions and the total value weakly increase. In contrast with M, WM does not insist that each player’s evaluation totally depends on his contributions but rather allows that it can depend on the total value. RIN requires that as long as some players say i,j and contribute zero in both games v and v′, the ratio of their payoffs, fiv/fjv, does not vary. N is a weak feasibility condition, which requires that every player receives nothing if every coalition’s worth is zero [13, 15]. In conclusion, SV can be characterized by axioms—BC, S, Sym, E, C, H, M, DPO, WL, and WC. The WSV can satisfy the axioms E, H, M, w-BC, DPO, and WL for all possible weights w. The PSV is the unique value on C that satisfies E, H, M, DPO, PAM, PS, WL, WC, and PBC. The WESV satisfies the axioms E, Sym, WM, RIN, WDMSP, and N [13, 15].


## 3.3. PM Resource Allocation Algorithms for VMs

In general, the limited CDC resource distribution problem mathematically corresponds to a bankruptcy game situation. A standard bankruptcy game is given by a finite game player setN, a real positive estate number E, and a nonnegative claim vector d=d1,…,dn∈ℝN while satisfying ∑i∈Ndi≽E. In the analysis of bankruptcy situation, the main objective is to obtain a satisfactory mechanism for distributing the estate while verifying two properties: the estate has to be completely distributed among the game players, and each player has to obtain a nonnegative quantity not greater than their demand. A bankruptcy rule is a map f which assigns to a payoff vector fN,E;d∈ℝN such that [18](17)∑i∈Nxi=E,s.t.,0≼xi≼difor alli∈N.For the bankruptcy problemN,E;d, a corresponding cooperative bankruptcy game N,vE;d can be defined as follows [18]:(18)vE;dS=max0,E−∑j∉Sdj.For the SV, WSV, PSV, and WESV, the above bankruptcy rule can be applied to calculate the characteristic functionν for the coalition S (νS). From the viewpoint of PMi, the IA of PMi observes its resource distribution status and adjusts its tuple ℝPMi⟶ at each Δt. If the PMi’s available resources are not sufficient to support the corresponding VMs’ requests, the limited resources must be shared intelligently taking into account differences of application types.In this study, we adopt thevalue-based cooperative solutions to design our PM resource allocation algorithms. For each PM, its ℝPMC,ℝPMM,ℝPMS, and ℝPMB resources are shared by game players PI∼IV, which represent application types. According to (3), each player has its own utility function UX with X∈C,M,S,B where UX represents the amount of satisfaction of a player toward the outcome of resource distribution. The higher the value of the utility, the higher the satisfaction of the player for that outcome. To calculate the characteristic function vS of each coalition S, we use the PI∼IV’ claim vector dX=dIX,dIIX,dIIIX,dIVX where dIX=UIXℛVM⟶,αVM⟶, dIIX=UIIXℛVM⟶,αVM⟶, dIIIX=UIIIXℛVM⟶,αVM⟶, and dIVX=UIVXℛVM⟶,αVM⟶.For thePMi, we individually develop the ℝPMiC,ℝPMiM,ℝPMiS, and ℝPMiB resource allocation algorithms. First, to design the ℝPMiC resource allocation algorithm, we consider the features of CPU computation and emphasize the characteristics of S and C axioms. Therefore, we adopt the SV idea as a solution. Based on the UI∼IVCℛVM⟶,αVM⟶, the players’ claim vector dC is defined, and vS values are obtained using the bankruptcy rule. And then, the players PI∼IV share the limited ℝPMiC resource according to (6). Therefore, the ℝPMiC is divided at the rate of ϕ values, and the assigned ℝPMiC for the PICPIPMi is given by(19)CPIPMi=ϕPIN,v∑i∈NϕiN,v×ℝPMiC,s.t.,N=PI,PII,PIII,PIV,ℝPMC=∑i∈NCiPMi.Finally, theCPIPMi should be distributed to the type I VMs in the PMi. In our proposed algorithm, the utilitarian idea is taken. In the viewpoint of efficiency, this idea attempts to maximize the sum of VMs’ effectiveness:(20)argmax…,AVMjC,…∑VMj∈PMiUVMjℛVMj⟶,αVMj⟶,TVMj,C,s.t.,CPIPMi=∑VMj∈PMiAVMjC.To design theℝPMM resource allocation algorithm, we consider the features of memory space and emphasize the characteristics of w-BC axiom. Therefore, we adopt the WSV idea as a solution to develop the ℝPMM resource allocation algorithm, and the weight w of each player is assigned as his preference αTM. And then, the players PI∼IV share the limited ℝPMM resource according to (7), and the assigned ℝPMM for each player is distributed among the same-type individual VMs by using the utilitarian idea as the same manner as the ℝPMC resource allocation algorithm.To design theℝPMS resource allocation algorithm, we consider the features of PM storage and emphasize the characteristics of PAM, PS, and PBC axioms. Therefore, we adopt the PSV idea as a solution to develop the ℝPMS resource allocation algorithm. The players PI∼IV share the limited ℝPMS resource according to (8), and the assigned ℝPMS for each player is distributed among the same-type individual VMs as the same manner as the ℝPMC and ℝPMM resource allocation algorithms. To design the ℝPMB resource allocation algorithm, we consider the features of PM communication bandwidth and emphasize the characteristics of RIN, WDMSP, and N axioms. Therefore, we adopt the WESV idea as a solution to develop the ℝPMB resource allocation algorithm, and the players PI∼IV share the limited ℝPMB resource according to (9), and the assigned ℝPMB for each player is distributed among the same-type individual VMs as the same manner as the ℝPMC, ℝPMM, and ℝPMS resource allocation algorithms.


## 3.4. Main Steps of the Proposed CDC Resource Allocation Scheme

The advent of cloud computing is looking forward to leasing out multiple instances of data centers. In addition, CDC resources can be shared amongst multiple users by using the virtualization technology while preventing hard resource commitment and low system utilization. VMs can be dynamically allocated over a DC infrastructure in order to improve application performance for the users and at the same time efficiently utilize the CDC’s physical resources. In this study, we focus on the main ideas of SV, WSV, PSV, and WESV solutions to solve the resource allocation problem for VMs in the CDC system. As we have asserted throughout this study, the proposed fourfold cooperative game approach is effectively advantageous under different and diversified CDC system situations.Our fourfold cooperative game approach can be analyzed in two different ways. From a theoretical point of view, each solution for separate resource allocation process can be featured by different axioms; they characterize each solution concept and provide a sound theoretical basis. From a practical point of view, our main concern is to reduce the computation complexity. Usually, traditional optimal solutions need huge computational overheads according to their complicated and complex computation formulas. Therefore, they are impractical in real-time process. In our game model, game players are not individual applications, but application types; it can effectively reduce the computational load. The principle novelties of our approach are a judicious mixture of differentvalue-based solutions and its adaptability, flexibility, and practicality to current system conditions of the CDC infrastructure. The main steps of the proposed scheme are described as follows:Step 1: at the initial time, system factors and control parameters are determined by a simulation scenario (refer to simulation assumptions and Table1 in Section 4).Step 2: at eachΔt, application tasks are received in the CDC, and VMs are generated as one of four types I,II,III,IV. Each VM has the resource specification ℛVM⟶ and preference αVM⟶. The utility function of VM is defined according to (1).Step 3: using (2), the new VM is nested to the most adaptable PM. In each PM, there are four resources ℝPMC,ℝPMM,ℝPMS,ℝPMB, and multiple VMs are placed. To design a game model, VM types are assumed as players, who compete with each other for the limited resources.Step 4: each game player’s utility functions for four resources are defined based on equation (3). At each Δt, they are examined periodically by each individual IA in a dispersive and parallel manner.Step 5: for theℝPMC resource allocation, the SV idea is adopted, and the limited ℝPMC is shared among game players according to (6). By using (20), the assigned ℝPMC for each player is distributed to the same-type individual VMs in the associated PM.Step 6: for theℝPMM resource allocation, the WSV idea is adopted, and the limited ℝPMM is shared among game players according to (7). By using the same manner as the ℝPMC resource allocation algorithm, the assigned ℝPMM for each player is distributed to the same-type individual VMs in the associated PM.Step 7: for theℝPMS resource allocation, the PSV idea is adopted, and the limited ℝPMS is shared among game players according to (8). By using the same manner as the ℝPMC and ℝPMM resource allocation algorithms, the assigned ℝPMS for each player is distributed to the same-type individual VMs in the associated PM.Step 8: for theℝPMB resource allocation, the WESV idea is adopted, and the limited ℝPMB is shared among game players according to (9). By using the same manner as the ℝPMC, ℝPMM, and ℝPMS resource allocation algorithms, the assigned ℝPMB for each player is distributed to the same-type individual VMs in the associated PM.Step 9: at each time period, each PM’sℝPM⟶ and utility functions of VMs are dynamically estimated in an online manner. Constantly, each IA in PM is self-monitoring, and proceed to Step 2 for the next fourfold cooperative game iteration.Table 1
System parameters used in the simulation experiments.
Type
ℛ
C
ℛ
M
ℛ
S
ℛ
B
α
I
C
,
α
II
M
,
α
III
S
,
α
IV
B
Execution duration average
I
1.2 GHz
350 MB
15 GB
35 Mbps
{0.3, 0.3, 0.2, 0.2}
120unit_time Δt
II
1.8 GHz
250 MB
20 GB
30 Mbps
{0.2, 0.4, 0.3, 0.1}
200unit_time Δt
III
2.5 GHz
150 MB
10 GB
45 Mbps
{0.1, 0.2, 0.3, 0.4}
150unit_time Δt
IV
3.3 GHz
100 MB
12 GB
25 Mbps
{0.4, 0.1, 0.2, 0.3}
250unit_time Δt
Parameter
Value
Description
n
12
Number of PMs in the CDC system
β
0.5
A control parameter to calculate theUVM·
γ
1
A control factor to calculate theUC·
δ
0.5
A control parameter to calculate theϕw−E·
ℝ
PM
C
100 THz
Initial CPU capacity for each PM
ℝ
PM
M
100 GMB
Initial memory size for each PM
ℝ
PM
S
1 PMB
Initial storage space for each PM
ℝ
PM
B
1.5 Gbps
Initial communication bandwidth for each PM


## 4. Simulation Results and Discussion

In this section, the performance of our proposed scheme is evaluated via simulation, and compared with that of the existing TTRA, MORA, and VSRA schemes [1, 6, 11]. First of all, we introduce the scenario setup of the simulation, and simulation parameters are listed in Table 1.(i)
Simulated DC system consists of one DC controller andn PMs. This structure can be extended hierarchically and recursively.(ii)
In order to represent application tasks, four different applications types —I, II, III, and IV—are assumed. Application tasks are randomly received in the CDC system from these four types.(iii)
Application tasks generate their corresponding VMs, which have different resource requirementsℛVM⟶=ℛVMC,ℛVMM,ℛVMS,ℛVMB and their preferences αVM⟶=αTVMC,αTVMM,αTVMS,αTVMB for four PM resources.(iv)
Durations of VM execution are exponentially distributed with different means for different application types.(v)
The arrival process for offered number of applications (task generation rate) is Poisson processρ. The offered rate range is varied from 0 to 3.(vi)
Each PM’s initial resources are 100 THz forℝPMC, 100 GMB for ℝPMM, 1 PMB for ℝPMS, and 1.5 Gbps for ℝPMB.(vii)
The CDC system performance measures obtained on the basis of 100 simulation runs are plotted as functions of the offered task generation rateρ.According to the simulation metrics, the CDC system throughput, normalized application payoff, and average CDC resource utilization are mainly evaluated to demonstrate the validity of the proposed approach. The simulation parameters are presented in Table1. Each parameter has its own characteristics.In Figure1, we compare the system throughput in the CDC environment. In this study, system throughput is the rate of successful VM execution in the CDC system. Typically, throughput is a measure of how many tasks a system can process in a given amount of time. From the viewpoint of the system operator, it is a main criterion on the performance evaluation. In Figure 1, it is observed that our proposed approach performs better at all levels of task generation rate, although the gain is very little profit at lower task rates. Note that our fourfold cooperative game model can effectively allocate the four different CDC resources while improving the system throughput. Therefore, it is easy to confirm that we can accommodate the increased application tasks in the CDC system and maintains the stable performance superiority under different task load intensities compared to the existing TTRA, MORA, and VSRA schemes.Figure 1
CDC system throughput.Figure2 shows the normalized application payoff with different task generation rates. From the viewpoint of end users, it is a major factor in the performance analysis. Usually, as the task generation rate increases, the VM execution delay may occur. Therefore, normalized application payoff decreases gradually. However, in our proposed scheme, each IA in PM periodically monitors its available resources and adaptively distributes the limited PM resources based on the value-based solutions. In our fourfold game approach, each resource is intelligently shared among different-type VMs while attempting to maximize the sum of same-type VMs’ effectiveness. Therefore, we can exhibit consistently better performance in application payoff compared to the existing schemes.Figure 2
Normalized application payoff.Figure3 presents a comparison of performances for the average CDC resource utilization. As can be observed, all schemes have many similarities with the performance of system throughput. Traditionally, resource utilization is strongly related to system throughput. When the offered application load increases, the utilization of PM resources also increases. It is intuitively correct. In the proposed scheme, each IA adaptively intervenes to maximize the resource utilization according to the viewpoint of utilitarian idea, and different application types reach binding commitments for each PM resource distribution. Therefore, individual PM’s resources are strategically distributed in the step-by-step interactive online manner while satisfying desirable features, which are defined as axioms of value-based solutions.Figure 3
Average CDC resource utilization.The simulation results displayed in Figures1–3 demonstrate that the actual outcome of our scheme is fairly dealt out compared to the existing schemes, and our fourfold game approach can attain an appropriate performance balance between the viewpoints of system operator and end users; conversely, the TTRA, MORA, and VSRA schemes cannot offer such an attractive outcome under widely different CDC application load intensities.


## 5. Summary and Conclusions

Modern CDCs need to tackle efficiently the increasing demand for different resources and address the system efficiency challenge. Therefore, it is essential to develop efficient resource allocation policies that are aware of VM characteristics and applicable in dynamic scenarios. This study highlights thevalue-based cooperative game approach and formulates the CDC resource allocation algorithms based on the SV, WSV, PSV, and WESV solutions. To effectively distribute the CPU, memory, storage, and bandwidth resources, individual cooperative game models are designed separately. They exhibit a number of interesting axiomatic properties and can be supported from a game-theoretic perspective. According to the developed fourfold game model, different resources in each PM are assigned for corresponding VMs to achieve a “win-win” situation under dynamic CDC environments. Compared to the existing protocols, the extensive simulations show that our proposed scheme delivers near-optimal CDC resource efficiency with various different application demands while other TTRA, MORA, and VSRA schemes cannot provide such a well-balanced system performance.Given the extensiveness of the CDC resource allocation methods, it is also concluded that more rigorous investigations are required with greater attentions. Therefore, there will be different open issues and practical challenges for the future study. First, we will further explore the VM migration issue among PMs in CDCs and moreover, we will develop more metrics to measure the quality of related algorithms. Second, we will also investigate the network topology of CDCs and the different network capabilities among them. Another important factor is the network topology. Running VMs may need to communicate with each other due to the workload dependencies. Therefore, by monitoring the VM’s communications, we will develop an efficient VM allocation method to decrease the overhead of data communications. Last but not least, we are keen to implement our protocol to real test-bed and analyze the CDC performance, which is hopeful to achieve valuable experience for practitioners.



---

*Source: 9840198-2020-03-16.xml*