一种面向不可分任务需求和部署约束的动态多维资源公平分配机制

李杰; 汪建洲

doi:10.11959/j.issn.2096-3750.2024.00447

您当前的位置：

首页 >

文章列表页 >

一种面向不可分任务需求和部署约束的动态多维资源公平分配机制

专题：算力物联网 | 更新时间：2025-01-20

- 一种面向不可分任务需求和部署约束的动态多维资源公平分配机制
- A fair multi-resource allocation mechanism for time-varying discrete jobs with placement constraints
- 物联网学报 2024年8卷第4期页码：98-109
- 作者机构：
  
  1.昆明理工大学信息工程与自动化学院，云南昆明 650504
  2.昆明理工大学云南省计算机技术应用重点实验室，云南昆明 650504
- 作者简介：
  
  [ "李杰（1987‒ ），男，博士，昆明理工大学信息工程与自动化学院讲师、硕士生导师，主要研究方向为基于算法博弈论的端边云协同资源分配与定价机制设计。" ]
  [ "汪建洲（1999‒ ），男，昆明理工大学信息工程与自动化学院硕士生，主要研究方向为边缘计算与机制设计。" ]
- 基金信息：
  
  国家自然科学基金资助项目(62362043;62262034);云南省计算机应用技术重点实验室开放基金资助项目(2022201);昆明理工大学人培基金资助项目(KKZ3202403168)
- DOI：10.11959/j.issn.2096-3750.2024.00447
  中图分类号：
- 纸质出版日期：2024-12-10，
  
  收稿日期：2024-10-15，
  
  修回日期：2024-12-09，
- 稿件说明：
移动端阅览
李杰, 汪建洲. 一种面向不可分任务需求和部署约束的动态多维资源公平分配机制[J]. 物联网学报, 2024,8(4):98-109.

LI JIE, WANG JIANZHOU. A fair multi-resource allocation mechanism for time-varying discrete jobs with placement constraints. [J]. Chinese journal on internet of things, 2024, 8(4): 98-109.
李杰, 汪建洲. 一种面向不可分任务需求和部署约束的动态多维资源公平分配机制[J]. 物联网学报, 2024,8(4):98-109. DOI： 10.11959/j.issn.2096-3750.2024.00447.

LI JIE, WANG JIANZHOU. A fair multi-resource allocation mechanism for time-varying discrete jobs with placement constraints. [J]. Chinese journal on internet of things, 2024, 8(4): 98-109. DOI： 10.11959/j.issn.2096-3750.2024.00447.

摘要

如何公平、高效地将多维资源分配给需求变化的用户是云计算资源共享的关键问题。该场景下的动态资源分配通常面临着用户任务最小粒度资源需求难以再被分割、任务需求与服务器配置不匹配等问题。现有资源公平分配机制多基于用户任务需求无限可分或任务执行与服务器配置均匹配的理想前提，难以保证分配可行。通过深入分析时变不可分任务需求和任务部署约束的特点，设计了一种基于累计任务份额公平的时变任务份额公平分配机制，以保证资源分配的公平性和效率。理论结果表明，该机制满足激励共享、相差一个任务资源的无嫉妒和帕累托最优属性。基于阿里云数据集的实验结果表明，与现有的公平分配机制相比，该方法有效地减少了用户的等待、作业排队和作业完成时间。

Abstract

A key issue in resource sharing in cloud computing is how to fairly and efficiently allocate the multi-resources to users with dynamic demand. Multi-resource fair allocation in a cloud computing system usually faces problems

such as subdividing the minimum granularity of users' resource requirements

and the mismatch between task requirements and server configurations. Most of the existing mechanisms for multi-resource fair allocation are based on the ideal assumption that the task demands of user are infinitely divisible or that the task execution and server configuration are matched

which makes it difficult to guarantee that the allocation is feasible. By analyzing the characteristics of time-varying indivisible task demands and task placement constraints

a time-varying task share fairness allocation mechanism based on cumulative task share fairness was designed to ensure the fairness and efficiency of resource allocation. Theoretical analysis shows that the TV-TSF mechanism satisfies the sharing incentive

envy-freeness up to one item

and Pareto optimal properties. Simulation results based on the Alibaba cluster dataset show that

compared with the existing fair allocation mechanisms

the TV-TSF mechanism proposed can effectively reduce the waiting time

job queuing time

and job completion time of users.

关键词

动态多维资源分配不可分任务需求任务部署约束累计任务份额公平

Keywords

dynamic multi-resource allocationindivisible task demandtask placement constraintcumulative task share fairness

references

AHMED Y N, MOHIDEEN S P. Workload characteristics in cloud data centers: a computational study from alibaba cloud[C]//Proceedings of the 2021 International Conference on Information Science and Communications Technologies (ICISCT). Piscataway: IEEE Press, 2021: 1-5.

GUO H, LI W D. Dynamic multi-resource fair allocation with elastic demands[J]. Journal of Grid Computing, 2024, 22(1): 35.

HINDMAN B, KONWINSKI A, ZAHARIA M, et al. Mesos: a platform for fine-grained resource sharing in the data center[C]// Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation. New York: ACM, 2011: 295-308.

VAVILAPALLI V K, MURTHY A C, DOUGLAS C, et al. Apache Hadoop YARN: yet another resource negotiator[C]//Proceedings of the 4th Annual Symposium on Cloud Computing. New York: ACM Press, 2013: 1-16.

DU L, WO T Y, YANG R Y, et al. Cider: a rapid docker container deployment system through sharing network storage[C]//Proceedings of the 2017 IEEE 19th International Conference on High Performance Computing and Communications;IEEE 15th International Conference on Smart City; IEEE 3rd International Conference on Data Science and Systems (HPCC/SmartCity/DSS). Piscataway: IEEE Press, 2017: 332-339.

SHARMA B, CHUDNOVSKY V, HELLERSTEIN J L, et al. Modeling and synthesizing task placement constraints in Google compute clusters[C]//Proceedings of the 2nd ACM Symposium on Cloud Computing. New York: ACM Press, 2011: 1-14.

REISS C, TUMANOV A, GANGER G R, et al. Heterogeneity and dynamicity of clouds at scale: google trace analysis[C]//Proceedings of the Third ACM Symposium on Cloud Computing. New York: ACM Press, 2012: 1-13.

FIKIORIS G, AGARWAL R, TARDOS É. Incentives in dominant resource fair allocation under dynamic demands[M]//SCHÄFER G, VENTRE C, eds. Lecture Notes in Computer Science. Cham: Springer Nature Switzerland, 2024: 108-125.

MESKAR E, LIANG B. Fair multi-resource allocation in heterogeneous servers with an external resource type[J]. IEEE/ACM Transactions on Networking, 2023, 31(3): 1244-1262.

LI B Y. Fair scheduling for time-dependent resources[J]. Advances in Neural Information Processing Systems. New York: ACM Press, 2021, 34: 21744-21756.

ZHANG J X, CHI L X, XIE N, et al. Strategy-proof mechanism for online resource allocation in cloud and edge collaboration[J]. Computing, 2022, 104(2): 383-412.

BEI X H, LI Z H, LUO J J. Fair and efficient multi-resource allocation for cloud computing[C]//Proceedings of the 18th International Conference of Web and Internet Economics. New York: ACM Press, 2022: 169-186.

DENG B, LI W D. Maximin share based mechanisms for multi-resource fair allocation with divisible and indivisible tasks[M]//Communications in Computer and Information Science. Singapore: Springer Nature Singapore, 2022: 263-272.

GHODSI A, ZAHARIA M, HINDMAN B, et al. Dominant resource fairness: fair allocation of multiple resource types[C]//Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation. New York: ACM Press, 2011: 323-336.

DOLEV D, FEITELSON D G, HALPERN J Y, et al. No justified complaints: on fair sharing of multiple resources[C]//Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. New York: ACM Press, 2012: 68-75.

PARKES D C, PROCACCIA A D, SHAH N. Beyond dominant resource fairness[J]. ACM Transactions on Economics and Computation, 2015, 3(1): 1-22.

Gutman A, Nisan N. Fair allocation without trade[C]//Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems. New York: ACM Press, 2012: 719-728.

JOE-WONG C, SEN S, LAN T, et al. Multi-resource allocation: fairness-efficiency tradeoffs in a unifying framework[C]//2012 Proceedings of the IEEE INFOCOM. Piscataway: IEEE Press, 2012: 1206-1214.

LI W D, LIU X, ZHANG X L, et al. Multi-resource fair allocation with bounded number of tasks in cloud computing systems[M]//Communications in Computer and Information Science. Singapore: Springer Nature Singapore, 2017: 3-17.

GHODSI A, ZAHARIA M, SHENKER S, et al. Choosy: max-min fair sharing for datacenter jobs with constraints[C]//Proceedings of the 8th ACM European Conference on Computer Systems. New York: ACM Press, 2013: 365-378.

BINOIS M, PICHENY V, TAILLANDIER P, et al. The Kalai-Smorodinsky solution for many-objective Bayesian optimization[J]. Journal of Machine Learning Research, 2020, 21: 1-42.

WANG W, LI B C, LIANG B, et al. Multi-resource fair sharing for datacenter jobs with placement constraints[C]//Proceedings of the SC '16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. Piscataway: IEEE Press, 2016: 1003-1014.

ZHOU W, WHITE K P, YU H F. Eunomia: a performance-variation-aware fair job scheduler with placement constraints for heterogeneous datacenters[C]//Proceedings of the 2018 IEEE 24th International Conference on Parallel and Distributed Systems (ICPADS). Piscataway: IEEE Press, 2018: 1034-1039.

LI X X, HU G Q, LI W D, et al. Fair multiresource allocation with access constraint in cloud-edge systems[J]. Future Generation Computer Systems, 2024, 159: 395-410.

TANG S J, NIU Z J, HE B S, et al. Long-term multi-resource fairness for pay-as-you use computing systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 29(5): 1147-1160.

SADOK H, CAMPISTA M E M, COSTA L H M K. Stateful DRF: considering the past in a multi-resource allocation[J]. IEEE Transactions on Computers, 2021, 70(7): 1094-1105.

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

FIKIORIS G, AGARWAL R, TARDOS É. Incentives in dominant resource fair allocation under dynamic demands[M]//Lecture Notes in Computer Science. Cham: Springer Nature Switzerland, 2024: 108-125.

LI W D, LIU X, ZHANG X L, 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.

Alibaba Group Holding Limited. Alibaba Server Configuration[EB]. 2022.

浏览量

下载量

CSCD

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

提交

工具集

关联资源

暂无数据