基于共享资源量的动态多资源公平分配策略

doi:10.11959/j.issn.1000-436x.2016144

摘要/Abstract

摘要：

针对云计算共享系统中多资源分配问题，提出一种基于共享资源量的动态多资源公平分配策略。该策略根据不同用户资源需求和共享资源量建立一个线性规划模型，同时证明该模型满足公平分配的4个重要属性：动态帕累托最优、激励共享、动态无嫉妒性和防止策略性操作，而且给出一种改进的动态多资源公平分配算法来提高算法运行效率。实验结果表明，所提动态多资源公平分配策略能够在满足任务资源需求的同时，尽可能保证公平分配下最大化占优资源份额，并且改进的分配算法能够有效地提高资源的分配效率。

关键词: 云计算, 多资源公平分配, 占优资源, 共享资源量

Abstract:

A dynamic fair allocation of multi-resources was proposed based on shared resource quantity for multi-resoures allocation problem in cloud shared computing system. Firstly, a linear programming model was given based on resource requirements and quantity of shared resource and this model was further proved which satisfies four fairness properties such as DPO, SI, DEF and SP. Secondly, an improved dynamic multi-resources fair allocation algo-rithm was introduced for the allocation efficiency. Finally, theoretical analysis and experiments demonstrate that this strategy can satisfy the demands as well as maximize the dominant share on the base of approaching fairness and the im-proved algorithm increases the allocation efficiency in the dynamic system.

Key words: cloud computing, multi-resources fairness allocation, dominant share, shared resource quantity

张潇璐,刘曦,李伟东,张学杰. 基于共享资源量的动态多资源公平分配策略[J]. 通信学报, 2016, 37(7): 151-160.

Xiao-lu ZHANG,Xi LIU,Wei-dong LI,Xue-jie ZHANG. Dynamic fair allocation of multi-resources based on shared resource quantity[J]. Journal on Communications, 2016, 37(7): 151-160.

图/表 8

图1

图2

图3

图4

图5

图6

图7

图8

参考文献 26

[1]	Max-min fairness[EB/OL]. .
[2]	GHODSI A , ZAHARIA M , HINDMAN B , et al. Dominant resource fairness: fair allocation of multiple resource types[C]// The 8th USENIX Conference on Networked Systems Design and Implementation. c2011:24.
[3]	Hadoop[EB/OL]. .
[4]	Mesos[EB/OL]. .
[5]	KASH I , PROCACCIA A D , SHAH N . No agent left behind: dynamic fair division of multiple resources[J]. Journal of Artificial Intelligence Research, 2013(1):351-358.
[6]	JAIN R , CHARNY A , CLARK D . Congestion control with explicit rate indication[C]// 1995 IEEE International Conference on Communications. c1995:1954-1963.
[7]	GOYAL P , VIN H M , CHEN H . Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks[C]// ACM Sigcomm Computer Communication Review. c1996:157-168.
[8]	STOICA I , SHENKER S , ZHANG H . Core-stateless fair queueing:achieving approximately fair bandwidth allocations in high speed net-works[C]// The ACM Sigcom. c1998:118-130.
[9]	CAPRITA B , CHAN W C , NIEH J , et al. Group ratio round-robin: O(1) proportional share scheduling for uniprocessor and multiprocessor systems[C]// Usenix Technical Conference. c2005:337-352.
[10]	KELLY F . Charging and rate control for elastic traffic[J]. European Transactions on Telecommunications, 1997,8(1):33-37.
[11]	MASSOULIE L , ROBERTS J . Bandwidth sharing: objectives and algo-rithms[C]// 18th Joint Conference of the IEEE Computer and Communications Societies(INFOCOM '99). New York. c1999:1395-1403.
[12]	ZUKERMAN M , TAN L , WANG H , et al. Efficiency-fairness tradeoff in telecommunications networks[J]. IEEE Communications Letters, 2005,9(7):643-645.
[13]	LAN B T , KAO D , CHIANG M , et al. An axiomatic theory of fairness in network resource allocation[C]// IEEE Infocom. c2010:1-9.
[14]	DOLEV D , FEITELSON D G , HALPERN J Y , et al. No justified complaints: on fair sharing of multiple resources[C]// The 3rd Innova-tions in Theoretical Computer Science Conference. c2012:68-75.
[15]	GUTMAN A , NISAN A . Fair allocation without trade[C]// The 11th International Conference on Autonomous Agents and Multiagent Systems. c2012:719-728.
[16]	BHATTACHARYA A A , CULLER D , FRIEDMAN E , et al. Hierar-chical scheduling for diverse datacenter workloads[C]// The 4th Symposium on Cloud Computing (SOCC'13). c2013:1-15.
[17]	WANG W , LIANG B , LI B . Multi-resource fair allocation in hetero-geneous cloud computing systems[J]. Parallel and Distributed Systems, 2015,26(10):2822-2835.
[18]	JOE-WONG C , SEN S , LAN T , et al. Multiresource allocation: fair-ness–efficiency tradeoffs in a unifying framework[J]. IEEE/ACM Transactions on Networking, 2013,21(6):1785-1798.
[19]	PSOMAS C A , SCHWARTZ J . Beyond beyond dominant resource fairness: Indivisible resource allocation in clusters[R]. Technology Report, Berkeley, 2013.
[20]	PARKES D C , PROCACCIA A D , SHAH N . Beyond dominant resource fairness: extensions, limitations, and indivisibilities[J]. ACM Transactions on Economics and Computation, 2015,3(1).
[21]	ZELDES Y , G.FEITELSON D . On-line fair allocations based on bot-tlenecks and global priorities[C]// The 4th ACM/SPEC International Conference on Performance Engineering. c2013:229-240.
[22]	LI W D , LIU X , ZHANG X L , et al. Multi-resource fair allocation with bounded number of tasks in cloud computing systems[J]. Eprint Arxiv, 2014.
[23]	LI W , LIU X , ZHANG X , et al. Dynamic fair allocation of multiple resources with bounded number of tasks in cloud computing systems[J]. Multiagent and Grid Systems, 2016,11(4):245-257.
[24]	BARBANEL J B , BRAMS S J . Two-person cake-cutting: the optimal number of cuts[J]. Mathematical Inteuigencer, 2011,36(3):23-35.
[25]	LI J , XUE J . Egalitarian division under leontief preferences[J]. Economic Theory, 2013,54(3):597-622.
[26]	WILES J , REISS C . Google cluster data 2011_2[EB/OL]. .