ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (7): 1534-1544.doi: 10.7544/issn1000-1239.2019.20180798

• 软件技术 • 上一篇    下一篇

一种基于共享公平和时变资源需求的公平分配策略

李杰1,张静1,李伟东2,张学杰1   

  1. 1(云南大学信息学院 昆明 650500);2(云南大学数学与统计学院 昆明 650500) (lj@mail.ynu.edu.cn)
  • 出版日期: 2019-07-01
  • 基金资助: 
    国家自然科学基金项目(61662088,61762091);云南大学青年英才培育计划项目;云南省高校科技创新团队支持计划项目;云南省教育厅科学研究基金项目(2017ZZX228)

A Fair Distribution Strategy Based on Shared Fair and Time-Varying Resource Demand

Li Jie1, Zhang Jing1, Li Weidong2, Zhang Xuejie1   

  1. 1(School of Information Science and Engineering, Yunnan University, Kunming 650500);2(School of Mathematics and Statistics, Yunnan University, Kunming 650500)
  • Online: 2019-07-01

摘要: 在云计算系统中,有效和公平地分配多种类型的资源是非常关键的,而通过资源共享的方式在云计算系统中分配计算和存储资源,是一种提高系统资源利用率的有效方式.而现有的研究多是基于用户需求的任务数无限制而且需求不会变化的前提下进行的.为了解决云计算资源共享系统中用户有多组数量有限的时变任务资源需求的资源分配问题,提出了一种基于资源共享公平概念的多资源公平分配机制.该机制根据用户不同时刻的有限任务资源需求和用户共享资源量建立规划模型,使全局累计占优资源份额向量满足字典序最优,证明了在这种机制下,用户所得分配满足4个属性:激励共享、帕累托最优、无嫉妒、可信性.进而在具体分配问题上,提出一种启发式算法,通过用户共享系数概念设计了分配策略,可以保证分配满足公平性的同时,用户不发生共享缺损.理论和实验结果表明:所提出资源分配机制在资源共享用户提出多组时变资源需求时,在保证用户资源分配公平和保证较高资源利用率方面取得了很好的效果.

关键词: 云计算, 资源共享, 时变资源需求, 共享公平, 字典序最大最小最优

Abstract: It is critical to allocate multiple types of resources efficiently and fairly in a cloud computing system. Allocating computing and storage resources through resource sharing has emerged as an effective way to improve the resources utilization. While in reality users’ resource requirements may change at any time, previous work has studied mostly based on the premise that the number of tasks required by users is unlimited and the demand does not change. In order to solve the resource allocation problem that users have limited time-varying resource requirements, we propose a multi-resource fair distribution mechanism based on the concept of resource sharing fairness. Firstly, on the conceptual level, we develop a linear programming model according to users’ dynamic limited tasks resource requirements and the amount of resources shared by users. This mechanism is further proved which satisfies four significant fairness properties: Sharing incentive, Pareto efficiency, Envy fairness, Truthfulness. Secondly, on the specific allocation problem, a heuristic algorithm is proposed. This algorithm is designed by the concept of user sharing coefficient, which can ensure the fairness of distribution and the user does not share loss. The theoretical and experimental results show that the proposed resource allocation mechanism achieves good results in ensuring the fairness of user resource allocation and ensuring high resource utilization when users propose multiple sets of time-varying resource requirements.

Key words: cloud computing, resource sharing, time-varying resource requirements, sharing fairness, lexicographically max-min-optimal

中图分类号: