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

张潇璐; 刘曦; 李伟东; 张学杰

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 基于共享资源量的动态多资源公平分配策略
- Dynamic fair allocation of multi-resources based on shared resource quantity
- 通信学报 2016年37卷第7期页码：151-160
- 作者机构：
  
  云南大学信息学院，云南昆明 650091
- 作者简介：
  
  [ "张潇璐（1983-），女，山东淄博人，云南大学博士生，主要研究方向为资源分配调度、云计算能耗、大数据处理。" ]
  [ "刘曦（1987-），男，云南昆明人，云南大学博士生，主要研究方向为智能算法、资源分配调度、大数据处理。" ]
  [ "李伟东（1981-），男，河南郑州人，博士，云南大学副教授，主要研究方向为组合优化算法、复杂性分析、分布式计算。" ]
  [ "张学杰（1965-），男，云南昆明人，云南大学教授、博士生导师，主要研究方向为高性能计算、云计算、大数据、分布式计算。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61170222);国家自然科学基金资助项目(11301466);云南省教育厅科学研究基金资助项目(2015J007);云南省科技厅应用基础研究面上基金资助项目(2013FB010)
- DOI：10.11959/j.issn.1000-436x.2016144
  中图分类号： TP301
- 网络出版日期：2016-07，
  
  纸质出版日期：2016-07-25
- 稿件说明：
移动端阅览
张潇璐, 刘曦, 李伟东, 等. 基于共享资源量的动态多资源公平分配策略[J]. 通信学报, 2016,37(7):151-160.

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.
张潇璐, 刘曦, 李伟东, 等. 基于共享资源量的动态多资源公平分配策略[J]. 通信学报, 2016,37(7):151-160. DOI： 10.11959/j.issn.1000-436x.2016144.

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

浏览量

2076

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

云环境下协同作业的密码服务优化调度算法

M-RSF：面向Unikernel的一种多级反馈队列任务调度机制

基于强化学习的在线离线混部云环境下的调度框架

云计算中基于时间和隐私保护的可撤销可追踪的数据共享方案

公有云中身份基多源IoT终端数据PDP方案