Fair and Eﬃcient Multi-Resource Allocation for Cloud Computing Xiaohui Bei1 Zihao Li1 and Junjie Luo2

2025-04-27 0 0 1008.46KB 37 页 10玖币

侵权投诉

Fair and Eﬃcient Multi-Resource Allocation

for Cloud Computing

Xiaohui Bei1, Zihao Li1, and Junjie Luo2

1Nanyang Technological University, Singapore

2Beijing Jiaotong University, Beijing, China

xhbei@ntu.edu.sg; zihao004@e.ntu.edu.sg; jjluo1@bjtu.edu.cn

Abstract. We study the problem of allocating multiple types of resources to agents with

Leontief preferences. The classic Dominant Resource Fairness (DRF) mechanism satisﬁes

several desired fairness and incentive properties, but is known to have poor performance

in terms of social welfare approximation ratio. In this work, we propose a new approxi-

mation ratio measure, called fair-ratio, which is deﬁned as the worst-case ratio between

the optimal social welfare (resp. utilization) among all fair allocations and that by the

mechanism, allowing us to break the lower bound barrier under the classic approximation

ratio. We then generalize DRF and present several new mechanisms with two and multiple

types of resources that satisfy the same set of properties as DRF but with better social

welfare and utilization guarantees under the new benchmark. We also demonstrate the

eﬀectiveness of these mechanisms through experiments on both synthetic and real-world

datasets.

Keywords: Fair Division ·Mechanism Design ·Cloud Computing.

1 Introduction

In order to oﬀer ﬂexible resources and economies of scale, in cloud computing systems, a fun-

damental problem is to eﬃciently allocate heterogeneous computing resources, such as CPU

time and memory, to agents with diﬀerent demands. This resource allocation problem presents

several signiﬁcant challenges from a technical perspective. For example, how to balance the ef-

ﬁciency of the system and fairness among users? How to incentivize agents to participate and

truthfully reveal their private information? These are all delicate issues that need to be carefully

considered when designing a resource allocation algorithm.

One of the most widely used mechanisms for multi-type resource allocation is the Dominant

Resource Fairness (DRF) mechanism proposed by [6]. This work assumes that agents in the

system have Leontief preferences, which means they demand to receive resources of each type

in ﬁxed proportions. Under such preferences, the proposed DRF mechanism generalizes the

max-min allocation by equalizing the share of the most demanded resource, called dominant

share, for all agents. [6] show that DRF satisﬁes a set of desirable properties. These include

fairness properties: (i) share incentive (SI), all agents should be at least as happy as if each

resource is equally allocated to all agents, and (ii) envy-freeness (EF), no agent should prefer

the allocation of another agent; eﬃciency properties: (iii) Pareto optimality (PO), it is impossible

to increase the allocation of one agent without decreasing the allocation of another agent; as well

as incentive properties: (iv) strategy-proofness (SP), no agent can beneﬁt from reporting a false

demand. Consequently, DRF has received signiﬁcant attention with many variants proposed to

tackle diﬀerent restrictions occurred in practice.

Despite the above attractive properties, however, DRF is known to have poor performance

in terms of utilitarian social welfare, which is deﬁned as the sum of utilities of all agents. Many

arXiv:2210.05237v1 [cs.GT] 11 Oct 2022

2 X. Bei et al.

alternative mechanisms have then been proposed to tackle this issue and balance the trade-oﬀ

between fairness and eﬃciency [12,1,2,9,10,21,22,7]. Most of these mechanisms still satisfy SI,

EF, and PO. However, none of them satisfy SP. Recently, [9] propose the so called 2-dominant

resource fairness (2-DF) to balance fairness and eﬃciency. Diﬀerent from other mechanisms, 2-

DF satisﬁes SP and PO, but does not satisfy SI and EF generally. On the other hand, [18] justify

this worst-case performance of DRF by showing that any mechanism satisfying any of the three

properties SI, EF, and SP cannot guarantee more than 1

mof the optimal social welfare, which is

also what DRF can achieve. Here mdenotes the number of resource types. This characterization

seems to suggest that from a worst-case viewpoint, DRF has the best possible social welfare

guarantee among all fair or truthful mechanisms.

In this work, we aim to design new mechanisms that satisfy the same set of properties with

DRF but with better eﬃciency guarantees. In order to get around the theoretical barrier set

by [18], we ﬁrst propose and justify a new benchmark to measure the social welfare guarantee

of a mechanism. Note that [18] and many other works use the approximation ratio, which is

deﬁned as the worst-case ratio between the optimal social welfare among all allocations and the

mechanism’s social welfare, as the performance measure of a mechanism. However, since SI and

EF are both fairness properties that place signiﬁcant constraints on feasible allocations, it is

not surprising that any allocation satisfying SI or EF would incur a large approximation ratio

of m. On the other hand, one can show that any mechanism satisfying SI has approximation

ratio at most m. This means all mechanisms satisfying SI and EF will have the same worst-

case approximation ratio, which renders the approximation ratio notion meaningless in systems

where these fairness conditions are hard constraints that must be satisﬁed. Since fairness is a

hard constraint in many practical applications, we argue that it is more reasonable to compare

the mechanism’s social welfare to the optimal social welfare among all allocations that satisfy SI

and EF. To this end, we modify the approximation ratio deﬁnition and propose this according

variant. The new deﬁnition allows us to get pass the lower bound barrier from [18] and design

mechanisms with better social welfare approximation ratio guarantees.

1.1 Our results

We design new resource allocation mechanisms that satisfy properties such as SI, EF, PO, and

SP, and at the same time achieve high eﬃciency. The eﬃciency is measured by two objectives:

social welfare, deﬁned as the sum of utilities of all agents, and utilization, deﬁned as the minimum

utilization rate among all resources. Social welfare is an indicator commonly used to measure

eﬃciency, while improving utilization rate is also an important goal for cloud providers for

cost-saving (see, e.g., Amazon3, IBM4). In academia, utilization has been studied by [15,12,11].

For the performance measure, we deﬁne fair-ratio for social welfare (resp. utilization) of a

mechanism as the worst-case ratio between the social welfare (resp. utilization) achieved by the

optimal mechanism satisfying SI and EF and that by the mechanism. See formal deﬁnitions in

Section 2.

We ﬁrst focus on the setting where all agents’ dominant resources fall into two types. This

is the most basic and arguably also the most important setting in cloud computing and other

application domains such as high performance computing. For example, most existing commer-

cial cloud computing services, such as Azure, Amazon EC2, and Google Cloud, work with only

two (dominant) resources: CPU and memory. Two-resource setting can also be used to model

the coupled CPU-GPU architectures where CPU and GPU are integrated into a single chip

to achieve high performance computing [21]. In this setting, we present three new mechanisms

3https://aws.amazon.com/blogs/aws/cloud-computing-server-utilization-the-environment/

4https://www.ibm.com/cloud/learn/cloud-computing

Fair and Eﬃcient Multi-Resource Allocation for Cloud Computing 3

Table 1. Fair-ratio results for m= 2 resources overview.

Social Welfare Utilization

DRF (Lemma 1) 2 (2 −α)∞(1

α)

UNB (Theorem 1) 3

2(1 + α) 2 ( 1

1−α)

BAL (Theorem 2) 4

3(4−2α

3−α) 2 ( 2

1+α)

BAL∗(Theorem 3) h4−2α

3−α,4−2α

3−α−1

ni h 2

1+α,2

1+α−1

Table 2. Price of SP results overview.

Social Welfare Utilization

m= 2 (Theorem 6) [1,3−√3 + 1

2n] [1,3

2−1

]

m= 3 (Theorem 7) [2,3] ∞

m≥4(Theorem 7) m∞

UNB,BAL, and BAL∗, all with better fair-ratio guarantees than DRF. Diﬀerent from DRF

which equalizes the dominant share of all agents, the idea behind our new mechanisms is to

partition all agents into two groups according to their dominant resources and carefully increase

the share of agents with the smallest fraction of their non-dominant resource in each group.

Mechanism UNB satisﬁes all four properties (SI, EF, PO, and SP) and has a fair-ratio of 3

2for

social welfare and 2for utilization. Mechanism BAL further improves the fair-ratio for social

welfare to 4

3. However, BAL satisﬁes SI, EF, and PO, but not SP. Finally, we generalize BAL

to a new mechanism BAL∗which satisﬁes all the four properties and has the same asymptotic

fair-ratio as BAL when the number of agents ngoes to inﬁnity. We further provide a more

ﬁne-grained analysis of the fair-ratio parameterized by a minority population ratio parameter

α∈(0,1

2], which is deﬁned as the fraction of agents in the smaller group classiﬁed by their dom-

inant resources. Table 1 lists a summary of the fair-ratios of diﬀerent mechanisms in the worst

case and in terms of α. We also compare our mechanisms with DRF by conducting experiments

on both synthetic and real-world data. Our results match well with the theoretical bounds of

fair-ratios and show that both UNB and BAL∗achieve better social welfare and utilization than

DRF.

Next we move to the general situation with m≥2resources. We ﬁrst give a family Fof

mechanisms, containing DRF as a special case, that satisfy all the four properties. This answers

the question posed by [6] that “whether DRF is the only possible strategy-proof policy for multi-

resource fairness, given other desirable properties such as Pareto eﬃciency”. Unfortunately, as

we will see in the next part, for general mall mechanisms that satisfy the four properties

will have the same fair-ratio as DRF. Nevertheless, we show that a generalization of UNB still

satisﬁes the four properties and its fair-ratio is always weakly better than DRF.

Finally, we investigate the eﬃciency loss caused by incentive constraints. We deﬁne the price

of strategyproofness (Price of SP) for social welfare (resp. utilization) as the best fair-ratio for

social welfare (resp. utilization) among all mechanisms which satisfy SI, EF, PO, and SP. Our

results are summarized in Table 2. For the case with m= 2 resources, we show that the price

4 X. Bei et al.

of SP is at most 3−√3 + 1

2nfor social welfare, and at most 3

2−1

for utilization. When m= 3,

the price of SP is between 2and 3for social welfare and ∞for utilization. Finally, when m≥4,

the price of SP is mfor social welfare and ∞for utilization, which implies that in the general

setting all mechanisms that satisfy the four properties have the same fair-ratio as DRF.

1.2 Related work

Since its introduction by [6], DRF has been extended in multiple directions, including the setting

with weighted agents or indivisible tasks [18], the setting when resources are distributed over

multiple servers with placement constraints [20,24] or without placement constraints [4,23], a

dynamic setting when agents arrive at diﬀerent times [13] and the case when agents’ demands

are limited [15,16]. In contrast to these works, we consider the original setting and aim to design

mechanisms with better eﬃciency guarantees than DRF. Notably, [15] generalize DRF to the

limited demand setting, and study the approximation ratio of the generalized mechanism by

comparing it with the optimal allocation satisfying PO, SI and EF. Essentially, their results

implies that for two resources, the fair-ratio of DRF is 2 for social welfare and ∞for utilization,

which can be seen as a special case of our more ﬁne-grained result in Lemma 1 parameterized

by α. [3] advocate a diﬀerent fairness notion called Bottleneck Based Fairness (BBF) for multi-

resource allocation with Leontief preferences and show that a BBF allocation always exists. [8]

extend DRF and BBF for a larger family of utilities and give a polynomial time algorithm to

compute a BBF solution. Characterization of mechanisms satisfying a set of desirable properties

under Leontief preferences has been studied in economics literature [17,5,14]. However, they

consider diﬀerent properties than what we consider.

2 Preliminaries

2.1 Multi-resource allocation

We start by introducing the formal model of multi-resource allocation. The notations are mainly

adopted from [18]. Given a set of agents N={1,2, . . . , n}and a set of resources Rwith |R|=m,

each agent ihas a resource demand vector Di={Di1, Di2, . . . , Dim}, where Dir is the ratio

between the demand of agent ifor resource rto complete one task and the total amount of that

resource. The dominant resource of an agent iis the resource r∗

isuch that r∗

i∈arg maxr∈RDir.

For simplicity, we assume that all agents have positive demands, i.e., Dir >0,∀i∈N, ∀r∈R.

For each agent iand each resource r, deﬁne dir =Dir

Dir∗

i∈(0,1] as the normalized demand and

denote the normalized demand vector of agent iby di={di1, di2, . . . , dim}. An instance of the

multi-resource allocation problem with nagents and mresource is a matrix Iof size n×mwith

each row representing a normalized demand vector.

To help better understand these notions, consider a cloud computing scenario where two

agents share a system with 9 CPUs and 18 GB RAM. Each task agent 1 runs require h1 CPUs,4 GBi,

and each task agent 2 runs require h3 CPUs,1 GBi. Since each task of agent 1 demands 1

9of the

total CPU and 2

9of the total RAM, the demand vector for agent 1 is D1={1

9,2

9}, with RAM

being its dominant resource, and the corresponding normalized demand vector is d1={1

2,1}.

Similarly, for agent 2 we have D2={1

3,1

18 },d2={1,1

6}, and its dominant resource is CPU.

Given problem instance I, an allocation Ais a matrix of size n×mwhich allocates a fraction

Air of resource rto agent i. We assume all resources are divisible. An allocation Ais feasible if

no resource is required more than available, i.e., Pi∈NAir ≤1,∀r∈R. We assume agents have

Leontief preferences and the utility of an agent with its allocation vector Aiis deﬁned as

ui(Ai) = max{y∈R+:∀r∈R, Air ≥y·dir}.

Fair and Eﬃcient Multi-Resource Allocation for Cloud Computing 5

We say an allocation is non-wasteful if for each agent i∈Nthere exists y∈R+such that Air =

y·dir,∀r∈R. In words, for each agent, the amount of allocated resources are proportional to its

normalized demand vector. The dominant share of an agent iunder a non-wasteful allocation

Ais Air∗

i, where r∗

iis i’s dominant resource.

Denote the set of all instances by I, and the set of all feasible allocations by A. A mechanism

is a function f:I → A that maps every instance to a feasible allocation. We use fi(I)to denote

the allocation vector to agent iunder instance I. A mechanism is non-wasteful if the allocation

of the mechanism on any instance is non-wasteful. We only consider non-wasteful mechanisms.

2.2 Dominant Resource Fairness (DRF)

The DRF mechanism [6] works by maximizing and equalizing the dominant shares of all agents,

subject to the feasible constraint. Let xbe the dominant share of each agent, DRF solves the

following linear program:

maximize x

subject to X

i∈N

x·dir ≤1,∀r∈R

This linear program can be rewritten as x∗=1

maxr∈RPi∈Ndir . Then, for agent ithe allocation

Ai=x∗·di.

2.3 Properties of mechanisms

In this work we are interested in the following properties of a resource allocation mechanism.

Deﬁnition 1 (Share Incentive (SI)). An allocation Ais SI if ui(Ai)≥1

n,∀i∈N. A

mechanism fis SI if for any instance I∈ I the allocation f(I)is SI.

Deﬁnition 2 (Envy Freeness (EF)). An allocation Ais EF if ui(Ai)≥ui(Aj),∀i, j ∈N.

A mechanism fis EF if for any instance I∈ I the allocation f(I)is EF.

Deﬁnition 3 (Pareto Optimality (PO)). An allocation Ais PO if it is not dominated by

another allocation A0, i.e., there is no A0such that ∃i0∈N:ui0(A0

i0)> ui0(fi0(I)) and

∀i∈N:ui(A0

i0)≥ui(fi(I)). A mechanism fis PO if for any instance I∈ I the allocation f(I)

is PO.

Deﬁnition 4 (Strategyproofness (SP)). A mechanism fis SP if no agent can beneﬁt by

reporting a false demand vector, i.e., ∀I∈ I,∀i∈N, ∀d0

i, ui(fi(I)) ≥ui(fi(I0)), where I0is the

resulting instance by replacing agent i’s demand vector by d0

Notice that SI, EF, and PO are deﬁned for both allocations and mechanisms, while SP is

only deﬁned for mechanisms. It is easy to verify that a non-wasteful mechanism satisﬁes PO if

and only if at least one resource is used up in the allocation returned by the mechanism.

[6] shows that DRF satisﬁes all of these desirable properties.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

FairandEcientMulti-ResourceAllocationforCloudComputingXiaohuiBei1,ZihaoLi1,andJunjieLuo21NanyangTechnologicalUniversity,Singapore2BeijingJiaotongUniversity,Beijing,Chinaxhbei@ntu.edu.sg;zihao004@e.ntu.edu.sg;jjluo1@bjtu.edu.cnAbstract.Westudytheproblemofallocatingmultipletypesofresourcestoagentswit...

展开>> 收起<<

Fair and Eﬃcient Multi-Resource Allocation for Cloud Computing Xiaohui Bei1 Zihao Li1 and Junjie Luo2.pdf

共37页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Fair and Eﬃcient Multi-Resource Allocation for Cloud Computing Xiaohui Bei1 Zihao Li1 and Junjie Luo2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: