Lihua Zhao, Minghui Du*, Lin Chen
1 School of Electronic and Information Engineering, South China University of Technology, Guangzhou 510641, China
2 Lab. Recherche Informatique (LRI-CNRS UMR 8623)Univ. Paris-Sud, Orsay 91405, France
* The corresponding author, Minghui Du email:ecmhdu@scut.edu.cn
Fair allocation of computational resources among a set of users is a fundamental yet challenging problem in any shared computing system. An example is allocating CPU, memory,and bandwidth in cloud computing platforms.Various fairness concepts have been proposed from different perspectives over the past several years, e.g., [1],[2]. In particular, one of the most popular allocation policies proposed so far is Max-min fairness (MMF) [3], which maximizes the minimum allocation received by a user in the system. The attractiveness of max-min fairness stems from its generality; consequently, considerable work has been devoted to fair allocation based on MMF [4], [5], [6].
Despite the vast amount of work on fair allocation, the focus has so far been on the allocation of a single resource type, e.g., link bandwidth [7],[8] and CPU time [9], [6]. For multi-resource allocation, thanks to Ghodsi et al., who proposed a mechanism called Dominant Resource Fairness (DRF) in [10], known as the state-of-the-art generalization of Max-Min Fairness [3]. The core idea behind DRF is to equalize a user’s dominant share across all users in a multi-resource environment. DRFhas attractive fairness properties, namely,Sharing Incentive (SI), Envy-freeness (EF),Pareto Efficiency (PE) and Strategy-proofness(SP). DRF quickly attracted much attention;speci fially, a great quantity of work on fair allocation such as [11], [12], [13], [14] extended DRF in many different ways. While most of these approaches have tried to seek better fairness in a multiple resources environment, they have ignored the tradeoffs between fairness and resource utilization, which easily leads to degradation of the efficiency of multi-resource fair allocation.
This paper addresses multi-resource fair allocation: a fundamental research topic in cloud computing.
In [11], Bottleneck-based fairness (BBF)was proposed based on bottlenecked resources,which is equivalent to saturated resources in DRF in a global system. They assume a scenario in which each user has a weight on multiple continuously divisible resources. The BBF focuses on the bottleneck and aims to enforce resource allocations and improve resource utilization. Its main contributions lie in a constructive proof for the existence of fair allocation according to their fairness de finition.
More recently, another related work on fair allocation of bottlenecked resources is Bottleneck-Aware Allocation (BAA), proposed by Hui Wang et al. [15]. This study dealt with the problem of the fair division of multiple resources in tiered storage systems. The idea behind BAA is that allocation to a user should be determined by the user’s hit ratio or miss ratio. In addition, BAA tried to fid a tension between fairness and resource utilization in tiered storage systems with multiple resources and maximized system utilization subject to well-studied fairness properties such as SI,EF and SP. However, BAA requires users to submit their multi-resource requirements by a form of hit ratio or miss ratio. Moreover,all the requirements of a user are in the simplex, that is, the sum of the resources of each requirement is 1. Because different resources such as CPU, memory and bandwidth have different quanti fiers in a cloud computing environment, it is impractical to insist that a user needs 20% CPU and 80% memory respectively in the same quanti fier.
Viewed in this light, in this paper we deal with the problem within the framework of BAA for multi-resource allocation settings as in [10], where users submit their heterogeneous requirements by the demand vector.In particular, we propose Dominant Resource with Bottlenecked Fairness (DRBF), a generalization of Bottleneck-Aware Allocation for multi-resource allocation in computer systems.We divide all users into different queues,which are based on capturing each user’s dominant resource; the allocation of a user should be determined by the user’s queue. We define fair shares as the baseline to equalize the allocation on a user’s dominant resource.Users in the same queue receive allocations proportional to their fair shares, while for users in different queues, no prede fined weights exist between their allocations.This flexibility can be highly useful, from both the perspective of the individual users and the perspective of resource efficiency. The objective of DRBF is to maximize the resource efficiency subject to well-recognized fairness properties such as SI, EF, PE, and SP. The strength of DRBF is that the scheme can achieve high resource utilization while meeting the optimal fairness guarantee as does DRF.
The rest of this paper is organized as follows. Section II discusses the related works.Section III gives a motivating example and discusses the problem of multi-resource allocation. Section IV describes our model and four well-studied fairness properties. Section V introduces DRBF and presents its scheduling algorithm. Formal proofs are presented in Section VII. We conclude in Section IX.
We brie flreview related work in computer science.
Due to the heterogeneity of multiple types resources in cloud computing, the fundamental problem is how to divide resources fairly among a set of users with different resource requirements. The vast majority of state-ofthe-art methods in computer science have mainly focused on the allocation of a single resource e.g., [7], [9], [8], [6]. Ghodsi et al. [10]proposed a multi-resource allocation mechanism known as the DRF mechanism, which is a generalized form that extends a single resource allocation to the allocation of multiple types of resources. The strength of DRF is that it equalizes a user’s dominant share across all the users, and it provides several attractive fairness properties: SI, EF, PE and SP.
Since its introduction, DRF has attracted considerable at-tention and has been extended to many dimensions [4], [16], [17], [18], [19],[20]. Notably, Dolev et al.[11] proposed an alternative notion of fairness for multi-resource allocation, called Bottleneck-Based Fairness(BBF). This scheme guarantees that each user receives at least its entitlement on some bottlenecked resource. Gutman and Nisan[21]considered the scenario of DRF with a more general family of utilities, applying the Norm-Fair: no justi fied complaints. They introduced polynomial-time algorithms to compute fair allocations for both this extended notion and the orthogonal notion of justi fied complaints.They also established the connection between the question of BBF and Fisher Market equilibrium.
Joe-Wong et al.[22] generalized the DRF mechanism and absorbed it into a unifying framework that captured the trade-offs between fair allocation and system efficiency.Another study that deals with the efficiency comparison between proportional fairness and DRF is by Youngmi Jin et al. [23], who investigated the situation in which there are two different type resources and only one resource is bottlenecked in the system. They showed that proportional fairness more efficiently uses resources than does DRF. In addition,they provided conditions in which proportional fairness has higher throughput than DRF.Wang et al.[24] proposed DRFH, a generalization of DRF to an environment with multiple servers, which equalizes the global dominant share assigned to each user and proves that it satis fies PE, EF, and SP as well as other interesting properties. In recent work, Parkes et al.[25] extended DRF in several ways. For example, they considered the zero demands for some resources, users with weights for certain resources, and studied the case of indivisible tasks. For the property of strategy-proofness,they proved that DRF actually satis fis ”group strategy-proofness (GSP).” Chowdhury et al. [26] proposed an optimal allocation algorithm called High Utilization with Guarantees(HUG), which extends DRF from static and fied demands to elastic demands. In addition,they proved that there is a strong tradeoff between the optimal isolation guarantee and work conservation under elastic demands in public cloud networks.
More recently, Zarchy et al.[27] developed a framework for fair resource allocation from both a user perspective and a global resource utilization perspective, where users are allowed to submit multiple resource demands and each demand denotes one of the forms of the task implementations. Note that DRF and its extensions focus on de fining the meaning of fairness in a multi-resource environment;these approaches tend to ignore the effects on resource utilization.
The conception of fairness that plays an important role in our work is proportional fairness, which is the most-widely used notion of fairness, e.g., in Weighted Fair Queuing(WFQ)[28] and proportional resource sharing[29]. The core idea of proportional fairness is that resources are allocated in proportion to users’ weights. Recently, a work arguing the merits of proportional fairness (PF) on efficiency and fairness compared with DRF was completed by Thomas Bonald et al. in the context of a shared network bandwidth system. In [30], they argued that PF is preferable to DRF.
It is worth noting that Hui Wang et al. [15]proposed the BAA policy, a new allocation model that captures trade-offs between fairness and system utilization in multi-tiered storage systems. BAA is based on the notion of local queues, and it divides users into different user sets. For the well-studied fairness properties, the proposed BAA policy meets a set of desirable properties such as sharing incentives, envy-freeness, and Pareto efficiency.However, it is unlike the environment in storage systems, because in the settings of DRF,e.g., a system includes CPU, memory or bandwidth, while different resources have different dimensions. As to the total amount of allocations, they cannot be added directly. Viewed in this light, our work makes two contributions.First, it suggests using the allocation of the dominant resource as a baseline to equalize users’ utility, which means that all users in a same queue will receive identical throughput on the dominant resource on the basis of the local-fairness. Second, we prove that this scheme can achieve high resource utilization while meeting the optimal fairness guarantee similar to DRF.
Other related works include fair-division problems that have been studied within the framework of game theory in the micro-economic literature. The favorable method of fair division in microeconomics is competitive equilibrium from equal incomes (CEEI) [31],[32]. Recently, Zahedi et al. [33] applied the concept of (CEEI) in the case of Cobb-Douglas utilities and showed that their allocation mechanism can provide properties similar to DRF.They empirically showed that these utilities are very suitable for modeling user preferences over cache capacity and memory bandwidth. In addition, Nash Bargaining (NB) coincides with the well-studied notion of proportional fairness for a large class of utility functions [34]. However, the main drawbacks of CEEI and NB are that they are not strategy-proof. As a result,users can manipulate the allocation mechanism by lying about their true resource demands.More recently, a truthful mechanism that approximates the Nash Bargaining solution was proposed by Cole et al. [35].
One of the most popular fair allocation policies is DRF, which mainly deals with the problem of multi-resource allocation for users with heterogeneous resource demands in a cluster.The core idea of DRF is to equalize each user’s dominant share in the system. Specially,DRF always picks the user whose dominant share is the smallest as the fist priority. Then,it picks the second smallest one, and so on.While DRF pays considerable attention to the de finition of multi-resource fairness, it ignores the effect of system utilization. To show how the choice affects resource utilization, we illustrate this issue by using a simple example.
We consider the example given in [10].Suppose that a system has 9 CPUs and 18 GB RAM. The system is shared by user 1 and user 2 with demand vectors D1= (1 CPUs, 4 GB)and D2= (3 CPUs, 1 GB), respectively.
In the above scenario, user 1’s dominant resource is memory, while user 2’s dominant resource is CPU. Given the demand vectors of these users, we assume N1and N2are the number of tasks allocated to user 1 and 2, respectively. By applying the DRF policy, user 1 receives N1=3 tasks with 3 CPUs and 12 GB,while user 2 receives N2=2 tasks with 6 CPUs and 2 GB. Note that in this example, the utilization of memory is only approximately 78%.In other words, the optimal fairness guarantee in DRF does not necessarily mean optimal utilization of resources.
Figure 1 shows the set of allocation ratios between users by DRF. Although meeting some sense of fairness, it may lead to poor system utilization.
To improve system utilization, Wang et al.[15] proposed the BAA mechanism, whose strength is that it provides both fairness and high efficiency for multi-tiered storage systems. Such systems are composed of hard disks (HDs) and solid-state drives (SSDs),where the resource requirements of users can be described by hit ratios or miss ratios. Because the target of each requirement of a user can be full filed by a form of an access to the SSD or the HD in storage system, the hit ratios and the miss ratios have the same quanti fiers.Moreover, all the requirements of a user are in the simplex, that is, the sum of resources of each requirement is 1. (for more details, see[15] ).
In fact, the environment of multi-resource allocation in cloud computing is unlike the settings of the BAA in multi-tiered storage systems. Because different resources have different quanti fiers, it is impractical to simply add two different types of resources together to characterize the requirements of the user. In this paper, we focus on extending the BAA idea to the settings of the DRF. We seek a tradeoff between the optimal fairness guarantee and high resource utilization for multi-resource allocation. The key point lies in strategy-proofness: the optimal fairness guarantee requires it, while high utilization repels it. In the next section, we elaborate on the assumptions and notations used in this paper.Then, we introduce the four desirable fairness properties: sharing incentive, envy-freeness,Pareto efficiency and strategy-proofness for multi-resource allocation across a set of users.
Fig. 1. Optimal allocations with DRF. A resource pool consists of 9 CPUs, 18 GB memory and two users with demand vectors D1 = (1, 4), D2 = (3, 1). The optimal solution by DRF in this example is (3CP Us, 12GB) for user 1 (yellow) and (6CP Us, 2GB) for user 2 (blue). We note that memory utilization is only about 78%, as shown above.
For ?i∈U, r∈R, we de fine
as the fractional demand and denote bythe fractional demand vector of user i. We say resourceiis the dominant resource of user i if its fractional demand dis the largest one in all dir.
In this section, we model multi-resource allocation in the context of cloud computing,where users have heterogeneous demands. We formalize a set of desirable properties that are well-studied for fair allocation in cloud computing environ-ments.
We consider a cloud cluster, where a pool of resources is assumed to be in fiitely divisible throughout this paper. Let R={1,…,m} be the set of m resources, e.g, CPU, memory, network, etc. We denote by Crthe total amount of resources r available in the entire pool.
Let U={1,…,n} be the set of users sharing the resource pool. We assume users have an in fiite number of tasks to be run and that all tasks are divisible [10], [21], [24], [25]. Each task is characterized by a demand vector. Letbe the resource demand vector of user i, where Dirspeci fies the amount of resource r required by the user i. For simplicity, we assume positive demands, i.e.,Dir?0 for all user i and resource r.
Let N={N1,…,Nn} be the set of the numbers of tasks allocated to the users, and let Nidenote the number of tasks of user i.
Under some resource allocation mechanisms, the amount of resource r user i receives is expressed by NiDir. All computed allocations must be feasible in the sense that they must satisfy the capacity constraints:
Where r=1,..., m.
In this section, following DRF [10], we consider the following properties of fairness: sharing incentive, envy-freeness, Pareto efficiency,and strategy-proofness. These desirable properties are deemed important for guiding the development of a fair allocation policy with multi-resource.
Sharing Incentive (SI):No user is worse off sharing the resource pool than by dividing each resource equally among all the users.This property is important in any sharing system so that users will share their resources willingly. Sharing incentive has been demonstrated to signi ficantly improve resource efficiency and to fairly bene fit users sharing the resource pool. Without SI, resources may be misallocated, leading to a reduction in resource efficiency and—in turn—users with lower utility pro fit.
Envy-freeness (EF):No user would prefer to trade his or her allocation with any other user. In other words, envy-freeness implies that users will not be jealous of each other.Such allocations are considered equitable;from the point view of game theory, equity means fairness [36].
Pareto Efficiency (PE):No users can increase their allocations without decreasing the allocations of other users.PE serves as another important property for evaluating system utilization because it implies that the allocation result is unique and cannot be improved to achieve the highest system utilization.
Strategy-proofness (SP):An allocation mechanism is strategy-proof when users cannot increase their allocation of a dominant resource by misreporting their resource demands. In other words, the allocation mechanism is strategy-proof in the sense that the owner of a task cannot get a larger share by lying about its actual resource demand.
For now, our objective is to design an allocation mechanism that ensures all the properties de fined above.
In this section, we describe the DRBF mechanism, a generalization of BAA in a cloud computing environment where different resources have different quanti fiers. We introduce the logical block diagram of the DRBF and its optimization model.
It is common that one resource is mostly contended by every user in a cloud computing system. According to the DRF (see[10]), when such situation arises, the solution should reduce to max-min fairness for that resource. Dolev et al.[11] call the contended resource a bottlenecked resource. Because the bottlenecked resource constrains system performance, an important manifestation of this result is that in a queueing network, most users will always be concentrated in the queue of the bottlenecked resource.
To address bottlenecked resources in the multi-resource allocation problem, we propose the DRBF mechanism. To make the analysis theoretically complete, before formally presenting our mechanism, we de fine the following terms used in this paper.
De finition 1.We de fine Sas the set of users that are bottlenecked on the dominant resource. For ?i∈U, we classify user i into a certain queue based on that user’s dominant resource.
De finition 2.We de fine the fair share of a user i to be the amount of its dominant resource that user receives. This amount can be calculated by dividing the resourceequally among all the users. We denote the fair share of user i by f.
De finition 3. Let Nfidenote the minimum number of tasks assigned to user i under its fair share f, where fir~=NfiD.
De finition 4.Letbe the resource allocation vector, where Airis the amount of a resource r allocated to user i.
Different users may have different dominant resources. For example, the dominant resource of a user with CPU-intensive jobs is CPU, while the dominant resource of another user with I/O-intensive jobs is bandwidth.Therefore, we fist focus on the dominant resource of every user and then classify different users into different queues. Each queue’s users are bottlenecked on the same dominant resource. Our DRBF mechanism seeks to max-imize resource utilization without sacri ficing the attractive fairness properties of DRF. To achieve the highest utilization, we advocate that there is no prede fined weight between the allocations of users in different queues, while users in the same queue will receive allocations in proportion to their fair share.
Specially, our fairness policy is represented by the following rules.
Our Fairness Policy
1. Fairness between any two users i, j in a same queue. Letand defineto be the ratio of the number of tasks of user i to that user’s minimum number of tasks under its fair share, i∈S.
2. Fairness between any two users i, j,Suppose that the dominant resources of user i and user j areand, respectively. Then, for
Rule (1) states that the number of tasks between any two users that are bottlenecked on the same dominant resource are in proportion to the minimum number of tasks under their fair share. Rule (2) states that allocations between any pair of users in different queues should be envy-free. In other words, no user should receive a higher allocation quantity of every resource than other users.
Intuitively, a user prefers more tasks be allocated, which is implied here in Rule (1):λ>1. Rule 2 is an enforced constraint that ensures the envy-free property is satis fied between any pair of users belonging to different sets.
Remark.Note that, for Rule (2), if a user has more than two dominant resources, i.e., whenwe assign the user into queue Sr1or Sr2using the de finition of the dominant resource.
These linear constraints will be included in a linear programming (LP) optimization model in the section 5.3.
The logical block diagram of DRBF is shown in Figure 2. It mainly consists of two components, namely, Resource Classifier and Resource Allocator. The Resource Classifier accepts information about resource demands from the resource pool and divides the users into different queues by capturing the dominant resources of different users. Guided by the queues obtained from resource classifier,the Resource Allocator assigns the available resources in the resource pool to users according to our fairness policy (more details are provided in the subsection 5.1. The details of the scheduling procedure based on our fairness policy are provided in Algorithm 1 (more information is given in subsection 6.1 to maximize resource utilization given the well-studied fairness level de fined in Section 4.2.
Fig. 2. Sketch of DRBF. A resource pool consists of multiple types of resources,e.g., CPU, memory and storage. When users are sharing the resource pool with heterogeneous resource demands, each user has a task to run, and each task is characterized by a demand vector. The main components of our DRBF mechanism are called the Resource Classi fier and the Resource Allocator.
In this section, to express the optimization of multi-resource allocation for our proposed mechanism, we consider a cloud computing data center, which consists of m different types of resources. The goal of the optimization is to employ our resource allocation strategy, which maximizes resource utilization constrained by the well-accepted fairness properties as de fined in Section 4.2.
For any pair of users i≠j we use auxiliary variablesandde fined in Section V-A to characterize the relationship between that user’s number of tasksNiand the minimum number of tasks Nfiunder its fair share according to our fairness policy, whereandare the dominant resources of user i and user j,respectively.
Formally, we present our optimization model as an LP formulation with m variables,and m constraints based on the total available resources in a resource pool. Together with an enforced condition, this model ensures that envy-freeness is satis fied between any two users in different queues.
Next, we formulate our objective function and constraints in terms of the auxiliary variable
The total quantity of allocations of resourceis:
The total number of tasks for all users is:
Fairness Rule 2 states that:
Representing Niby Nfi, we havewhereis de fined in the previous section.
Because there are m resources, there should be m queues according to our DRBF mechanism. The final optimization model is shown below.
Optimization Model for Multi-resource Allocation
subject to:
The model is expressed as an m-variable LP with variables {λ1,…,λm}, and 2 linear constraints between them. Inequality (2) is the capacity constraint of resource r for any feasible allocation mechanism. This constraint ensures that the total amount of resourceassigned to all users cannot exceed the total resource capacity. Inequality (3) is an enforced constraint of envy-freeness, which ensures that any pair of users in different queues are envy-free. Moreover, according to our fairness policy, users in the same queue who are bottlenecked on the same resource will automatically be envy-free.
In this section, we present the scheduling algorithm for the DRBF mechanism; then, we provide an example to illustrate DRBF compared to the DRF method.
The m-variable linear programming described in Section 5.3 calculates the number of tasks allocated to each user based on that user’s demand vector and the available resource capacities. After establishing the formulation of our optimization model, we are now ready to present the scheduling algorithm for our DRBF mechanism (see Algorithm 1).
Algorithm 1 captures each user’s dominant resource. Then, we sort users into different queues according to their dominant resources.After completing the classifying work, we calculate auxiliary variables by solving the LP problem described in Section 5.3. In the next stage, we compute upper bounds to restrict how much of a resource a user can acquire under the resource capacity constraints. Finally. we obtain the number of tasks allocated to each user.
In Algorithm 1, users’ demand vectors form the weights to a proportional share scheduler.The total resource allocations are proportional to the ratios of their fair shares, as de fined in Section 5.1.
We illustrate DRBF allocation policy using the following concrete example:
Consider a resource pool with ofCC=18CPUsandCm=36GB RAM. Four users a, b, c, and d , share the resource pool and have demand vectors ofDa=(3CPUs,1GB),Db=(5CPUs,3GB),Dc=(1CPUs,4GB),Dd=(2CPUs,7GB), respectively.
In this case, the dominant resources of users a and b are CPU, while the dominant resource of users c and d are memory. That is,usera,b∈SC~and userc,d∈Sm~.
DRBF will complete multi-resource allocations using the steps below :
- Compute the fair share of dominant resources for four users. In this case, the fair share
- Apply the result of the step above to calculate the minimum number of tasks allocated to four users. Here, we haveNfa=4.5/3,Nfb=4.5/5 andNfc=9/4,Nfd=9/7, respectively.
- Apply the result of the step above to express the number of tasks allocated to four users using the minimum number of tasks. Here, we haveNb=λC~Nfb=0.9λC~,Nc=λm~Nfc=9/4λm~,Nd=λm~Nfd=9/7λm~, respectively.
- Obtain the allocations assigned to four users. Here, user a receives (3NaCPUs,NaGB), user b receives (5NbCPUs, 3NbGB),user c receives (NcCPUs, 4NcGB), and user d receives (2NdCPUs, 3NdGB).
- Apply the result of step above and write the 2-variable LP problem with unknownsandas follows:
subject to:
Algorithm 1: DRBF pseudo-code Input: Resource types RmrR=…?∈{1,,},; User set Un={1,…,}; CCC={,…,},1 m?C ∈C r; Each user i with a demand vector DDDiU iiim=…?∈{,,},1;Output: The number of tasks of user i Ni and corresponding allocation Ai;1: While U≠? do 2: Divide users into different queues based on their dominant resource ;3: De fine the minimal number of tasks of user i be Nfi=nD Ci;4: Let NN irfi=λ~ (where λ is a weight constant);5: Solve the LP Problem (1) in Constraints (2), (3) to obtain the solution λ;6: Obtain Ni and AN D iii= ;7: end while
Table I. The comparison of DRBF allocation policy and DRF
Solving this problem yields=1.07 and=1.75.
Hence, Na=1.6, Nb=1, Nc=3.9, and Nd=2.3. Thus, user a gets (4.8 CPUs, 1.6 GB), user b gets (5 CPUs, 3 GB), user c gets(3.9 CPUs, 15.6 GB), and user d gets (4.6 CPUs, 16.1 GB). Note that, by DRBF policy,the utilizations of CPU and memory are almost 100%.
Because users a and b are bottlenecked on CPU, they both receive equal amounts of CPU time (27% of the total CPU time each,as shown in Figure 3 ). In contrast, users c and d are bottlenecked on memory; they each receive equal amounts of the available memory(44% of the total memory each, as shown in Figure 3).
Given the allocation results above, this example explain our fairness policy. However, what do the fairness constraints mean for the system in the example above? Rule(1) means that the CPU-bound users a and b should receive a number of tasks in the ratio of 1.6:1 (corresponding to their fair shares of CPU), i.e.,Na/Nb=1.6. Similarly, the memory-bound users c and d should receive a number of tasks in the ratio i.e.,Nfc:Nfd=1.7:1,i.e.,Nc/Nd=1.7...
Fig. 3. Allocation by DRBF for four users. A resource pool consists of 18CPUs, 36 GB memory, four users with their demand vectors The optimal allocations for users a, b, c,and d by DRBF are (4.8CPUs, 1.6GB), (5CPUs, 3GB), (3.9CPUs, 15.6GB), and(4.6CPUs, 16.1GB), respectively. This example shows that DRBF can satisfy SI,EF, and PE while maintaining CPU and memory utilization of 100%.
Fig. 4. Allocation by DRF for four users. A resource pool consists of 18CPUs, 36 GB memory, four users with their demand vectors The optimal allocations for users a, b, c,and d by DRF are (6CPUs, 2GB), (5CPUs, 3GB), (3CPUs, 12GB), and (4CPUs,14GB), respectively. Note that by DRF policy, utilization of memory is approximately 86%, as shown above.
Next, to compare different allocation policies, we can use the DRF method, given Na, Nb, Nc, and Ndas the number of tasks allocated to users a, b, c, and d,respectively. DRF will equalize the users’ dominant shares, which means that 3Na/18=5Nb/18=4Nc/36=7Nd/36.
The final allocation results are as follows:Na=2,Nb=1,Nc=3, and Nd=2.
At the end of the DRF allocation, user a gets (6 CPUs, 2 GB), user b gets (5 CPUs, 3 GB), user c gets (3 CPUs, 12 GB) and user d gets (4 CPUs, 14 GB). In this case, we note that utilization of memory is approximately 86% (see Figure 4). In other words, the DRF policy has room for memory resource utilization improvement.
Table I illustrates the users’ initial resource demands and their final allocations under different allocation mechanisms for this example.
In this section, we will discuss which of the fairness properties presented in section 4.2 are provided by DRBF.
Table II summarizes the meanings of different symbols.
Lemma 1. Given the user set U={1,…,n},n users share the resource pool. Thenwhere resourceis the dominant resource of user i.
Proof. For ?i∈U, we assign user i into a queuebased on that user’s dominant resource. Hereis the minimum guarantee of the number of tasks corresponding to its fair share. Hence, the amount of dominant resource user i receives is at leastThe demand vector of user ihence, the fraction of the dominant resourcerequired by user i is. Therefore, we have, and thus
Lemma 2. All users in the same queue receive equal allocations on the dominant resource.Speci fically, all users in a same queue receivefrom the dominant resource
Proof. For ?i∈U, from our fairness policy (1) and Lemma 1,The amount of dominant resourceallocated to user i is therefore
Now, we are in a position to prove the DRBF fairness properties, which are the well-recognized fair properties: EF, PE, SI,and SP.
We first show that the DRBF allocation policy provides the EF property. To prove EF for any pair of users i, j∈U, we consider two cases in the proof.
Theorem 1. DRBF satis fies envy-freeness and Pareto efficiency.
Proof. By construction, DRBF satis fies Pareto efficiency.
Now we are ready to prove that DRBF satis fies envy-freeness. The simplest case is that all users are in the same queue. From our fairness policy (1) and Lemma 2, because all users receive an equal allocation of the dominant resource they will automatically be envy-free.We are done.
Another case is that for any pair of users in different queues, from our fairness policy (2), the enforced constraintexactly completes the proof.
Theorem 2. DRBF satis fies the sharing incentive property.
Proof. We prove the theorem using two cases.
Case 1: This is the simple case where all users are in the same queue. For any user i and i∈, it is clear that that the user’s dominant resourceis the system’s bottlenecked resource (i.e., its utilization is 100%).
In this case, from lemma 2, the allocations of the dominant resource to all users in a same queue are equal. Since, we suppose that the dominant resourceis 100% used, given the total capacity ofis. Hence, every user i receives a allocation on the resourcemust be at least
Table II. List of symbols and their meanings
Case 2: For any pair of users i, j,We assume that the dominant resource of user i and user j areand r?, respectively.
Assume that the bottleneck resource in the system is resource r? and its utilization is 100%. The resourcehas a utilization of less than 100%. For user i∈, we will show that user i still receives an allocation on his or her dominant resourcethat is at least
By hypothesis, resource r? is 100% used,while resourceuser i’s dominant resource but not the system’s bottleneck. From our fairness policy (2), it follows from the enforced constraint that users in different queues satisfy envy-freeness. In other words, ?i∈, the received resource allocation r? must be no more thanthe allocation on the resource r? for any user in the queue
We express this relationship mathematically, as follows.
Given that resource r? is the system’s bottleneck and resourceis used at less than 100%, we are now ready to prove that we try to make the allocations to users in queueas large as possible, before the fairness property EF prevents further increases. In other words,we will let parameterbe as large as possible.
The result is that every user i∈receives its allocation on the dominant resourcefrom Lemma 2 as. Because>1, in Case 2, DRBF also satis fies the sharing incentive property .
A symmetrical proof holds in the other case. □
Theorem 3. DRBF satisfies Strategy-Proofness.
Proof. Consider a resource pool that holds two different resources,and. The capacity constraints areand, respectively.For any pair of users i≠ j, assume user i’s dominant resource is resource, while user j’s dominant resource is resource?. According to our DRBF mechanism, we divide the two users into different queues. That is, i∈andAssume that the demand vector for any pair of users i≠j are Diand Dj, respectively. Therefore, each element in the demand vector specifies the amount of each resource required by the user.
To prove this theorem, we approach the DRBF mechanism from the perspective of some arbitrary user i .
Suppose user i misreports her resource demand, takinginstead of the true demand. Given that resourceis user i’s dominant resource, letdenote the amount of the dominant resource that user i receives, whereis the number of tasks assigned to user i by the DRBF mechanism.
In [10], the utility that a user obtains from her allocation is simply her dominant share.In this paper, the utility of the user is derived from the amount of the dominant resource each user receives, which is the criterion that we employ to judge user’s utility. That is,when a user is allocated more of her dominant resource, we say she gains the greatest utility,and vice versa.
To prove that DRBF meets the strategy-proofness, we need to show thatwherecorresponds to the number of tasks allocated to user i when user i misreports her demand.
Now we are ready to prove that the inequalityholds from the perspective of the change of the user j’s allocation on its dominant resource. That is, for any user(j≠i), the amount of the dominant resource of user j is
To compute NjDjr?, following Lemma 2,we havewhere onlyis the variable de fined in Section 5.1 is the scalar of the queueIn other words, the amount of the dominant resource of user j is determined by the scalar
We are interested in the question: What is the link between the user i’s misreporting and the scalar? The value of the scalarcan be computed by solving the LP problem described in the section 5.3. If we obtain the expression of the scalarthen we can check whether a link exists between the use i’s misreporting and the scalarthus, we can obtain the answer to the question.
Next, we will analyze how the scalarwill change if user i misreports its resource demand, that is, user i chooses to useinstead of its true demand
For now, we will solve the LP problem to obtain the value of theMoreover, we need to solve the following questions:
* Are there optimal solutions for the LP problem described in the section 5.3?
* If optimal solutions for the LP problem exists, is there a unique solution?
Next, we are ready to answer the two questions above.
We use the DRBF optimization model expressed by equations (1) to (3) in the above section 5.3, whereanddenote the scalar of the queuesandrespectively.
Then, we turn our attention to solving the LP problem. In the following step, we simplify to obtain a condensed expression of the LP problem.
Given that the objective function of the LP of our DRBF mechanism is described by equa-
Now, we can simplify equations (8), (9),(10), (13) and (14) by replacing the introduced variables with some parameters to obtain the following condensed expressions:
subject to tion (1), we divide the users set U={1,…,n}into two queuesandbased on our DRBF mechanism. From Lemma 1,and
As shown above, we finally obtain the condensed expression LP formulation with 2 variables and 4 constraints, wherecan be denoted byrespectively.
Now, rewriting the objective function equation, we have:
There are two queues in this scenario;therefore, equation (2) is decomposed into two resource capacity constraints as shown below:
Next, we transform equation (3) shown in Section 5.3 into the two inequalities, which are the enforced envy-free conditions proposed by our mechanism. For any user, the amount of the dominant resource allocated to user i must be larger than user j’s allocation of that resource, that is:
Similarly, for the symmetrical case of any user i∈S, we have:
Employing Rule (1) of our fairness policy and following from Lemma 1, we can rewrite and reduce the inequities in (11) and (12), obtaining the new expressions shown below:
Remark. Note that K1actually represents the total amount of dominant resourcefor all users in the queue, and K2is the total amount of resource r? for all users in queue, while resource r? is the dominant resource of queue. Similarly, K4represents the total amount of the dominant resource r? for all users in queue, and K3is the total amount of resourcefor all users in queuewhile resourceis the dominant resource of queue
Because user i’s dominant resource is resource, from the de finition of the dominant resource, we know that K7<1. For user j,because its dominant resource is resource r?,>1.
All the above parameters (K1, K2, K3, and K4) are constrained by the users’ fair shares,because we can observe from the expression that each parameter contains 1/n share of the total resource capacity, which implies that users in the same queue each have a fair share.
To prove that the optimal solution of the LP problem described above is unique, we use the following Lemma 3.
Lemma 3. Given the objective function and the constraints of the LP expressed by equation (15) to (19), there exists a unique optimal solution for the LP problem.
Proof. Assume that the feasible region of the LP problem is Φ. On one hand, without the two capacity constraints (16) and (17), it is straightforward to see that the feasible region of the LP problem Φ is non-empty. On the other hand, under the capacity constraints (16) and (17), it can easily be verified that the enforced constraints(18) and (19) are compatible with the two capacity constraints. Recall that conditions (18) and(19) enforce the envy-free condition de fined by our DRBF mechanism, which implies that these two conditions are the bounded constraints of the LP problem. That is, the feasible region is the intersection of the two enforced conditions and the two capacity constraints.
After adding constraints (18) and (19), we find that the new feasible region of the LP problem is actually a subset of the original feasible region Φ, and it is a polyhedral. In other words, the feasible region is non-empty and one or more optimal solutions exist for the LP problem above.
Next, we will discuss the problem of whether a unique optimal solution exists for the LP problem. We assume that each equation of the constraints represents a line. Let l1, l2, l3and l4denote the corresponding lines of the linear constraints (16) to (19), respectively. Let l5denote the line of the objective function of the LP problem. Next, we will check whether the slope of l5is equal to any of the four lines.First, it is easy to see that the slopes are not equal for any two pairs of lines in equations(16) to (19). In addition, it is also straightforward to see that the slope of l5is not equal to any of the constraint lines described by equations (16) to (19).
As discussed above, the feasible region of the LP problem is non-empty and the slope of the objective function is not equal to the any other line of the constraint. Therefore,a unique optimal solution for the linear programming above must exist. Furthermore, the unique optimal solution of the LP problem can be found in a vertex of the polyhedral.
This completes the proof. □
Therefore, following Lemma 3, we have answered the question above: there indeed exists a unique optimal solution for the LP problem described in Section 5.3.
Finally, by solving the linear equations (15)to (19), we obtain the expression ofandas shown below:
Remark.K1K4?K2K3actually represents the difference between the product of the total amount of the dominant resource and the product of the total amount of the non-dominant resource.
Notice that user i’s resource demand affects only the value of K2. By combining the above analysis, we can answer the question of whether user i’s misreporting will affect the change of the scalar
Now, we can analyze how user i’s demand influences the value of the K2. We state the following lemma, which will be useful in subsequent proofs and analysis.
Lemma 4. The expression of the scalargiven by equation (21), assume that K2is the variable, while K1, K3and K4are constants.Thus,is a linear fractional function of the variable K2. Assuming the interval of domain of the fractional function is Θ, then the following property holds:
Recall that in equation (21), becauseis the linear fractional function of the variablecan be computed by the derivative formula of the fractional function.
This completes the proof. □
For now, we analyze how user i’s demand in fluences the way that K2changes.
Using Lemma 4, we are then able to answer the question proposed above.
Conversely, it increases resourceallocations to users in queue, except user i. Recall that we mainly consider the utility derived from the amount of the dominant resource a user gets. Because user i misreported her resource demands, she was assigned to a different queuetherefore, although user i receives more allocation for resource, she receives fewer allocation on her true dominant resource. Thus, lying cannot be bene ficial.Instead, it can actually harm user i’s resource allocation.
In contrast, it decreases resourceallocations to users in queue---including that of user i. Because user i is lying about her resource demand, she receives a lower allocation of her true dominant resource. The final result is that there is no bene fit for user i.
To sum up, reporting the true demand vector is the dominant strategy for every user i. Therefore, we can completed the proof:holds by the analysis of the change of user j’s allocation on its dominant resource.
Thus we completes the proof of the Theorem3, that is DRBF satis fies strategy-proofness.
In this section, we evaluate the performance of DRBF with respect to dominant resource fairness [10]. Specifically, we care about improving resource utilization subject to the well-recognized fairness properties: sharing incentive, envy-freeness, Pareto efficiency,and strategy-proofness.
We conduct two experiments, the former experiment with six users is to analyze for the reader how DRBF satisfies the well-recognized fairness properties de fined in Section 5.1, the latter one extends the scale of users to simulate multi-user and multi-resource situation in cloud computing. Both experiments using three types of resources to compare resource efficiency performances. For simplicity, we assume positive demands, i.e., Dir>0 for all users i and resources r [10]. We start by presenting the verified experiment with 6 users and analyzing the experimental results in terms of constraints of the fairness properties de fined in Section 8.1. In Section 8.2 we use cloud simulation software CloudSim3.0.0 to compare DRBF and the DRF in terms of resource utilizations and total number of tasks.
Fig. 5. Allocation for resource 1 with DRF and DRBF.
In this section, we show how DRBF dynamically adjusts the fair shares of the users and how DRBF mechanism allocation meets the well-recognized fairness properties compared to DRF. For simplicity, we assume that the resource capacity of the three types of resources is 100. Six users share the resource pool,and every user has a task to implement. Each task is characterized by a demand vector that specifying the amount of each resource that task requires. The resource demands of the six users in this experiment areD1=(4,1,3),D2=(5,3,2),D3=(3,6,2),D4=(3,5,1),D5=(2,1,4), andD6=(1,2,5).
DRF operates by applying the dominant resource shares approach from [10] to allocate resources to users. Its scheduling algorithm is the progressive filling algorithm. DRBF is the approach proposed in this paper. In this experiment, all resources are assumed to be in finitely divisible.
In this scenario, the first step of our fairness policy is to divide users into different queue based on each user’s dominant resource.Given the demand vectors of the six users,we have three queues:S1={1,2},S2={3,4},S3={5,6}. In this case, that means the six users are bottlenecked on the resource 1, 2 and 3, respectively.
Figures 5--8 show the allocation results of the two schedulers.
In Figures 5--7, we can compare the amount of each of the resource allocated to each user under the DRF and DRBF approaches, while Figure 8 compares the resource utilization corresponding to each scheduler.
Note that the allocations of users 1 and 2 are little better under DRF than under DRBF.Only a slight gap exists between the two schedulers. In contrast, the allocations of users 3 and user 4 are obviously better under DRBF than under DRF. That is, DRBF does extremely well in this scenario, and users 3 and 4 are able to obtain higher allocations of their dominant resource. The allocation of user 5 is the same for both schedulers; however the allocation of user 6 under DRF is notably lower with both schedulers.
Next, we evaluate the fairness properties of the allocations de fined in the section 4.2.
Table III lists the exact amount of each resource allocated to the six users under the DRBF scheduler. The second column shows the minimum fair share of each resource that each user should receive. The remaining columns show the portions of each resource received by each user.
Firstly, we verify that users in the same queue get equal allocations of their dominant resources. As shown in Table 3, users in the same queue receive equal amounts of their dominant resource. For example, for resource 1, the bottlenecked users 1 and 2 receive greater allocations (23 each) than the other users. Similarly, for resource 2, the bottlenecked users 3 and 4 receive greater allocations (31 each) than the other users. Hence, under our fair policy, users bottlenecked on the same resource will automatically be envy-free.
As shown in Figures 5--7, the amount of the dominant resource allocated to each user in the same queue is larger than their fair share 17%, where 17% (see column 1 of Table III)corresponds to dividing each resource equally among the six users. In contrast, we can observe from column 2 and the remaining columns that each user obtains more than the minimum fair share of its dominant resource.That is, DRBF also meets the sharing incentive property.
Figure 8 shows the resource utilization of both schedulers under the same resource demands. We see that DRBF achieves better performance compared to DRF. As can be seen, under DRF, only resource 1 has 100%used; the utilization of resource 2 is only approximately 88%. In contrast, under DRBF, as shown in Figure 8, all the resources are 100%utilized. The underlying reason for this change is that according to our allocation policy, users in the same queue receive allocations in proportion to their fair share, while for users in different queues there are no predefinedweights exist between their allocations.
Fig. 6. Allocation for resource 2 with DRF and DRBF.
Fig. 7. Allocation for resource 3 with DRF and DRBF.
In order to evaluate DRBF at a larger scale users, we conduct a experiment with 100 users and we use a cloud simulation software CloudSim3.0.0 to compare DRBF with DRF.We assume that there are three types resources provided by the resource pool. We compare resource utilizations and total number of tasks of all users for both schedulers DRF and DRBF.
Fig. 8. Resource utilization comparison with DRF and DRBF.
In Figures 9--11, we evaluate the resource utilizations for three types resources under the two schedulers DRF and DRBF. We compare average resource utilizations using the data of 10 randomly extracted data, they are the calculation results of scheduling algorithms by taking 10 times every 100 times in the 1000 times experiments. Where for each experiment computing resource utilizations of three types resources, then getting the average of resource utilizations of 10 times experiments. As shown in Figure 9, for resource 1, there are a slight gap exists between the two schedulers DRF and DRBF. Apparently, however, for resource 2 and resource 3, as shown in Figures 10--11, DRBF has higher resource utilizations than DRF.
Figure 12 shows the total number of tasks under DRF and DRBF.We compare total number of tasks using the data of 10 randomly extracted data, they are the calculation results of scheduling algorithms by taking 1 times every 100 times and taking 10 times in the 1000 times experiments. As can be seen form Figure 12 that the DRBF-based scheduler obtains more total number of tasks compared to the DRF-basedscheduler.
The underlying reason for this change is that because of the underlying resource requirements are heterogeneous, hence the tasks of different users may bottleneck on different resources. In this paper, we advocate dividing users into different queues based on their dominant resource: in fact, our fair policy is based on bottleneck fairness. Note that bottleneck fairness is described in [10] as only a secondary criterion for the fairness properties.They de fine bottleneck fairness only when all users have the same dominant resources, i.e.,their solution reduces to max-min fairness for a single bottleneck case. However, our work extend this to multiple bottlenecked resources,that is where our fair policy differs from the DRF proposed by Ghodsi et al.
Overall, the experimental results demonstrate that DRBF allocation mechanism achieves better performance both in resource utilizations and total number of tasks. That means there exists a tradeoff between fair allocation and resource efficiency for multi-resource allocation in cloud computing.
In this paper, we introduced Dominant Resource with Bottlenecked Fairness (DRBF),a generalization of Bottleneck-aware Allocation (BAA) [15] to multi-resource allocation settings as in DRF [10]. We addressed the problem of fairly allocating multiple resources across a set of users and captured the tradeoffs between fair allocation and resource utilization subject to the well-recognized fairness properties e.g., sharing incentive, envy-freeness, Pareto efficiency and strategy-proofness.
DRBF advocates the idea of local bottleneck fairness by dividing users into different queues based on their dominant resources.Users in the same queue receive allocations that are proportional to the fair shares of their dominant resources, while for users in different queues, allocation ratios are set to maximize resource utilization within the fairness constraints. DRBF satis fies the set of desirable properties provided by DRF. With DRBF,no user is worse off when sharing resources than if resources are divided equally across all users; no user would prefers to receive another user’s allocation; no user can improve their own allocation without decreasing the allocation of others; and no user can benefit by misreporting their resource demands. Our allocation policy provides both high resource efficiency and fairness.
There are two interesting directions for further research. First, it is to better understand fairness and efficiency tradeoffs within a suitable theoretical framework and explore other possible allocation polices for multi-resource allocation, but one where as many tasks as possible must be allocated subject to the well-studied fairness properties. A second direction is interesting because it considers more complex scenarios; e.g., if users were allowed to submit multiple resource demands such as the settings in the context of [27], the multi-resource allocation problem would become more complicated.
Fig. 10. Utilization for resource 2 with DRF and DRBF.
Fig. 11. Utilization for resource 3 with DRF and DRBF.
We are grateful for the financial support of the Oversea Study Program of the Guangzhou Elite Project (GEP). This work is supported by the National Natural Science Foundation of China under Grant 61471173 and Guangdong Science Technology Project(no:2017A010101027).
Fig. 12. Total number of tasks with DRF and DRBF.
[1] C. E. Koksal, H. Kassab, and H. Balakrishnan, “An analysis of shortterm fairness in wireless media access protocols (poster session),” in ACM SIGMETRICS Performance Evaluation Review, vol.28, pp. 118–119, ACM, 2000.
[2] T. Lan, D. Kao, M. Chiang, and A. Sabharwal, An axiomatic theory of fairness in network resource allocation. IEEE, 2010.
[3] S. Keshav, “An engineering approach to computer networking: Atm networks, the internet,and the telephone network,” Reading MA, vol.11997, 1997.
[4] L. Popa, G. Kumar, M. Chowdhury, A. Krishnamurthy, S. Ratnasamy, and I. Stoica, “Faircloud:sharing the network in cloud computing,” in Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication, pp. 187–198, ACM, 2012.
[5] S. Radhakrishnan, R. Pan, A. Vahdat, G. Varghese, et al., “Netshare and stochastic netshare:predictable bandwidth allocation for data centers,” ACM SIGCOMM Computer Communication Review, vol. 42, no. 3, pp. 5–11, 2012.
[6] S. K. Baruah, N. K. Cohen, C. G. Plaxton, and D.A. Varvel, “Proportionate progress: A notion of fairness in resource allocation,” Algorithmica,vol. 15, no. 6, pp. 600–625, 1996.
[7] J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Transactions on Networking (ToN), vol. 8, no. 5,pp. 556–567, 2000.
[8] Y. Liu and E. Knightly, “Opportunistic fair scheduling over multiple wireless channels,” in INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies, vol. 2, pp. 1106–1115,IEEE, 2003.
[9] J. M. Blanquer and B. Ozden, “Fair queuing for aggregated multiple ¨links,” ACM SIGCOMM Computer Communication Review, vol. 31, no.4, pp. 189–197, 2001.
[10] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica, “Dominant resource fairness: Fair allocation of multiple resource types.,” in NSDI, vol. 11, pp. 24–24, 2011.
[11] D. Dolev, D. G. Feitelson, J. Y. Halpern, R. Kupferman, and N. Linial,“No justified complaints:On fair sharing of multiple resources,” in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 68–75, ACM,2012.
[12] A. Ghodsi, V. Sekar, M. Zaharia, and I. Stoica,“Multi-resource fair queueing for packet processing,”ACM SIGCOMM Computer Communication Review, vol. 42, no. 4, pp. 1–12, 2012.
[13] I. Kash, A. D. Procaccia, and N. Shah, “No agent left behind: Dynamic fair division of multiple resources,” Journal of Arti ficial Intelligence Research, pp. 579–603, 2014.
[14] A. D. Procaccia, “Cake cutting: not just child’s play,” Communications of the ACM, vol. 56, no.7, pp. 78–87, 2013.
[15] H. Wang and P. J. Varman, “Balancing fairness and efficiency in tiered storage systems with bottleneck-aware allocation.,” in FAST, pp. 229–242, 2014.
[16] X. Xu and H. Yu, “A game theory approach to fair and efficient resource allocation in cloud computing,” Mathematical Problems in Engineering, vol. 2014, 2014.
[17] R. Grandl, G. Ananthanarayanan, S. Kandula, S.Rao, and A. Akella,“Multi-resource packing for cluster schedulers,” in ACM SIGCOMM Computer Communication Review, vol. 44, pp. 455–466,ACM, 2014.
[18] Z. Niu, S. Tang, and B. He, “Gemini: An adaptive performance-fairness scheduler for data-intensive cluster computing,” in 2015 IEEE 7th International Conference on Cloud Computing Technology and Science (CloudCom), pp. 66–73,IEEE, 2015.
[19] T. T. Tran, P. Y. Zhang, H. Li, D. G. Down, and J. C.Beck, “Resourceaware scheduling for data centers with heterogenous servers,” 2015.
[20] W. Wang, B. Li, B. Liang, and J. Li, “Towards multi-resource fair allocation with placement constraints,” in Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science,pp. 415–416, ACM, 2016.
[21] A. Gutman and N. Nisan, “Fair allocation without trade,”in Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, pp. 719–728, In-ternational Foundation for Autonomous Agents and Multiagent Systems, 2012.
[22] C. Joe-Wong, S. Sen, T. Lan, and M. Chiang,“Multiresource allocation: Fairness–efficiency tradeoあs in a unifying framework,” Networking,IEEE/ACM Transactions on, vol. 21, no. 6, pp.1785–1798, 2013.
[23] Y. Jin and M. Hayashi, “Efficiency comparison between proportional fairness and dominant resource fairness with two different type resources,” in 2016 Annual Conference on Information Science and Systems (CISS), pp.643–648, IEEE, 2016.
[24] W. Wang, B. Li, and B. Liang, “Dominant resource fairness in cloud computing systems with heterogeneous servers,” in INFOCOM,2014 Proceedings IEEE, pp. 583–591, IEEE, 2014.
[25] D. C. Parkes, A. D. Procaccia, and N. Shah, “Beyond dominant resource fairness: extensions,limitations, and indivisibilities,” ACM Transactions on Economics and Computation, vol. 3,no. 1, p. 3, 2015.
[26] M. Chowdhury, Z. Liu, A. Ghodsi, and I. Stoica,“Hug: Multi-resource fairness for correlated and elastic demands,” in 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16), pp. 407–424, 2016.
[27] D. Zarchy, D. Hay, and M. Schapira, “Capturing resource tradeoあs in fair multi-resource allocation,”IEEE Computer Communications, pp.1062-1070, 2015. .
[28] A. Demers, S. Keshav, and S. Shenker, “Analysis and simulation of a fair queueing algorithm,”in ACM SIGCOMM Computer Communication Review, vol. 19, pp. 1–12, ACM, 1989.
[29] C. A. Waldspurger and W. E. Weihl, “Lottery scheduling: Flexible proportional-share resource management,” in Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p. 1, USENIX Association,1994.
[30] T. Bonald and J. Roberts, “Enhanced cluster computing performance through proportional fairness,” Performance Evaluation, vol. 79, pp.134–145, 2014.
[31] H. P. Young, Equity: in theory and practice.Princeton University Press, 1995.
[32] H. Moulin, Fair division and collective welfare.MIT press, 2004.
[33] S. M. Zahedi and B. C. Lee, “Ref: Resource elasticity fairness with sharing incentives for multiprocessors,” ACM SIGARCH Computer Architecture News, vol. 42, no. 1, pp. 145–160, 2014.
[34] H. R. Varian, “Equity, envy, and eきciency,” Journal of economic theory, vol. 9, no. 1, pp. 63–91,1974.
[35] R. Cole, V. Gkatzelis, and G. Goel, “Mechanism design for fair division: allocating divisible items without payments,” in Proceedings of the fourteenth ACM conference on Electronic commerce, pp. 251–268, ACM, 2013.