Dynamic fair allocation of multi-resources based on shared resource quantity

Xiao-lu ZHANG; Xi LIU; Wei-dong LI; Xue-jie ZHANG

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

您当前的位置：

首页 >

文章列表页 >

Dynamic fair allocation of multi-resources based on shared resource quantity

Academic paper | 更新时间：2024-06-05

- Dynamic fair allocation of multi-resources based on shared resource quantity
- Journal of Communications Vol. 37, Issue 7, Pages: 151-160(2016)
- 作者机构：
  
  云南大学信息学院，云南昆明 650091
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61170222);The National Natural Science Foundation of China(11301466);Scientific Research Foundation of Yunnan Provincial Department of Education(2015J007);Natural Science Foundation of Yunnan Province(2013FB010)
- DOI：10.11959/j.issn.1000-436x.2016144
  CLC： TP301
- Online First：2016-07，
  
  Published：25 July 2016
- 稿件说明：
移动端阅览
Xiao-lu ZHANG, Xi LIU, Wei-dong LI, et al. Dynamic fair allocation of multi-resources based on shared resource quantity[J]. Journal of Communications, 2016, 37(7): 151-160.
DOI：

Xiao-lu ZHANG, Xi LIU, Wei-dong LI, et al. Dynamic fair allocation of multi-resources based on shared resource quantity[J]. Journal of Communications, 2016, 37(7): 151-160. DOI： 10.11959/j.issn.1000-436x.2016144.

摘要

针对云计算共享系统中多资源分配问题，提出一种基于共享资源量的动态多资源公平分配策略。该策略根据不同用户资源需求和共享资源量建立一个线性规划模型，同时证明该模型满足公平分配的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

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.

关键词

Keywords

references

Max-min fairness [EB/OL ] . http://en.wikipedia.org/wiki/Max-min_fairness http://en.wikipedia.org/wiki/Max-min_fairness .

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 . c 2011 : 24 .

Hadoop [EB/OL ] . http://hadoop.apache.org/ http://hadoop.apache.org/ .

Mesos [EB/OL ] . http://mesos.apache.org/ http://mesos.apache.org/ .

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 .

JAIN R , CHARNY A , CLARK D . Congestion control with explicit rate indication [C ] // 1995 IEEE International Conference on Communications . c 1995 : 1954 - 1963 .

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 . c 1996 : 157 - 168 .

STOICA I , SHENKER S , ZHANG H . Core-stateless fair queueing:achieving approximately fair bandwidth allocations in high speed net-works [C ] // The ACM Sigcom . c 1998 : 118 - 130 .

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 . c 2005 : 337 - 352 .

KELLY F . Charging and rate control for elastic traffic [J ] . European Transactions on Telecommunications , 1997 , 8 ( 1 ): 33 - 37 .

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 . c 1999 : 1395 - 1403 .

ZUKERMAN M , TAN L , WANG H , et al . Efficiency-fairness tradeoff in telecommunications networks [J ] . IEEE Communications Letters , 2005 , 9 ( 7 ): 643 - 645 .

LAN B T , KAO D , CHIANG M , et al . An axiomatic theory of fairness in network resource allocation [C ] // IEEE Infocom . c 2010 : 1 - 9 .

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 . c 2012 : 68 - 75 .

GUTMAN A , NISAN A . Fair allocation without trade [C ] // The 11th International Conference on Autonomous Agents and Multiagent Systems . c 2012 : 719 - 728 .

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) . c 2013 : 1 - 15 .

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 .

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 .

PSOMAS C A , SCHWARTZ J . Beyond beyond dominant resource fairness: Indivisible resource allocation in clusters [R ] . Technology Report , Berkeley , 2013 .

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 ).

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 . c 2013 : 229 - 240 .

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 .

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 .

BARBANEL J B , BRAMS S J . Two-person cake-cutting: the optimal number of cuts [J ] . Mathematical Inteuigencer , 2011 , 36 ( 3 ): 23 - 35 .

LI J , XUE J . Egalitarian division under leontief preferences [J ] . Economic Theory , 2013 , 54 ( 3 ): 597 - 622 .

WILES J , REISS C . Google cluster data 2011_2 [EB/OL ] . https://code.google.com/p/googleclusterdata/ https://code.google.com/p/googleclusterdata/ .

Views

2814

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Cryptographic service optimization scheduling algorithm for collaborative jobs in cloud environment

M-RSF: a multilevel feedback queue task scheduling mechanism for Unikernel

Scheduling framework based on reinforcement learning in online-offline colocated cloud environment

Time-based and privacy protection revocable and traceable data sharing scheme in cloud computing

Identity-based provable data possession scheme for multi-source IoT terminal data in public cloud

Related Author

CAO Xiaogang

LI Fenghua

GENG Kui

LI Zifu

KOU Wenlong

DONG Bonan

YANG Qiusong

LI Mingshu

Related Institution

Institute of Information Engineering, Chinese Academy of Sciences

School of Cyber Security, University of Chinese Academy of Sciences

Key Laboratory of Cyberspace Security Defense

University of Chinese Academy of Sciences

National Engineering Research Center for Fundamental Software, Institute of Software Chinese Academy of Sciences

AI问答

⁰