吉林大学学报(工学版) ›› 2021, Vol. 51 ›› Issue (4): 1349-1357.doi: 10.13229/j.cnki.jdxbgxb20190854

• 计算机科学与技术 • 上一篇    

地理分布数据中心的工作流经济高效资源分配

魏晓辉1,2(),汤钫宇1,李洪亮1,2()   

  1. 1.吉林大学 计算机科学与技术学院,长春 130012
    2.吉林大学 符号计算与知识工程教育部重点实验室,长春 130012
  • 收稿日期:2019-09-01 出版日期:2021-07-01 发布日期:2021-07-14
  • 通讯作者: 李洪亮 E-mail:weixh@jlu.edu.cn;lihongliang@jlu.edu.cn
  • 作者简介:魏晓辉(1972-),男,教授,博士生导师.研究方向:分布式计算,集群计算和网络安全.E-mail:weixh@jlu.edu.cn
  • 基金资助:
    国家重点研发计划项目(2017YFC1502306);国家自然科学基金项目(61602205)

Cost-efficient resource allocation algorithm for scientific workflow accross geo-distributed data centers

Xiao-hui WEI1,2(),Fang-yu TANG1,Hong-liang LI1,2()   

  1. 1.College of Computer Science and Technology,Jilin University,Changchun 130012,China
    2.Key Laboratory of Symbolic Computation and Knowledge Engineering,Jilin University,Changchun 130012,China
  • Received:2019-09-01 Online:2021-07-01 Published:2021-07-14
  • Contact: Hong-liang LI E-mail:weixh@jlu.edu.cn;lihongliang@jlu.edu.cn

摘要:

针对工作流作业跨数据中心传输产生高额流量费用的场景,对跨地理分布数据中心工作流作业资源分配问题进行了分析并建模,使用启发的贪心思想提出了MCCD算法,并将本文算法与常见的几种资源分配算法进行了对比。实验的结果验证了本文算法在跨地理分布数据中心的工作流作业中,可以有效降低用户通信流量资费平均达40%,对于降低用户跨地理分布数据中心的通信资费有明显的帮助。

关键词: 云计算, 地理分布式, 工作流调度, 经济高效, 启发式算法

Abstract:

Cloud operators charge bandwidth fees for data from user jobs that are transferred between data centers, and this accounts for a large percentage of user spending. It is of practical significance for users to reduce the communication overhead of the submitted job significantly without affecting the completion of the job through reasonable assignment of tasks and resources when determining the leased resources. This paper analyzes and models the traffic cost problem across data centers when workflow tasks are distributed in geographically distributed data centers, and proposes a heuristic algorithm for solving the problem. Several sets of experiments are carried out on the proposed algorithm, and the results are compared with that of the resource allocation algorithms commonly used in the current practice.. The experimental results verify that the heuristic algorithm proposed in this paper can effectively reduce the user communication traffic cost by at least 9.75% in the workflow operation across the geo-distributed data center, which serves to reduce the communication fee between users across geo-distributed data centers.

Key words: cloud computing, geo-distributed, workflow scheduling, cost efficient, heuristic algorithm

中图分类号: 

  • TP399

图1

工作流作业部署在跨地理分布式的数据中心"

图2

跨地理分布式数据中心的云计算模型"

表1

模型中各变量含义"

变量名称变量代表意义
T租赁的节点数目/提交作业的子任务数目
taskii个子任务的名称
Dbataska发往taskb的数据量
N租赁资源涉及的数据中心数目
nii个数据中心的名称
Rii个数据中心上租赁的节点数目
taskLocai子任务taski是否部署在了数据中心na
UPa数据中心na向外的流量带宽单价
BwCjitaskitaskj发送数据的流量带宽费用
BwC工作流作业的整体流量带宽费用

图3

算法思路说明示例"

图4

工作流的DAG结构[17]"

表2

对比算法"

算法名称算法简介
顺序分配策略ABS大部分工作流作业没有合理的资源分配策略,用户将各个任务上传至云平台后,按顺序为其分配租赁的计算资源,这种策略就是顺序分配策略(Allocate?ByNumbers?Strategy,ABS)。
最早完成时间策略EFT最早完成时间策略(Earliest?Finish?Time,EFT )18 是一种常用的作业资源分配策略。目的是让工作流作业的完成时间最短,其思路是将工作流作业的任务按完成时间排序进入队列,然后按照队列中任务的顺序分配资源。
最小数据量策略MBD最小数据量策略(Minium?Bandwidth?Data,MBD)是Li等11工作的内容。其主要思路是将作业资源分配问题抽象为混合整数线性规划问题,通过CPLEX求解器得出一个跨数据中心之间数据传输量最优的解。

表3

工作流作业的特征"

工作流结构作业规模任务数目边数目

平均作业内任务数据

传输总量/GB

Montage501083 586.8
10023573 850.9
400984301 382.2
Epigenomics505415 776.6
10012281 938.1
400470288 345.5
CyberShake50465 177.9
10096110 446.3
400396434 251.3
Sipht50563 288.9
10010954 472.7
400439232 937.5
Inspiral506019 407.9
10012339 175.8
400500158 730.5

图5

跨数据中心流量费用实验结果(单位:USD)"

1 Enterprise Customer Success Stories - Amazon Web Services [DB/OL]. [2019-08-10].
2 Introduction to Cloud Economics_AA(final).pdf [DB/OL]. [2019-08-10].
3 Yao G, Ding Y, Hao K, et al. Using imbalance characteristic for fault-tolerant workflow scheduling in cloud systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(12): 3671-3683.
4 Zhou X, Wang K, Jia W, et al. Reinforcement learning-based adaptive resource management of differentiated services in geo-distributed data centers[C]∥ International Symposium on Quality of Service(IWQoS), Vilanova I La Geltru, Spain, 2017: 1-6.
5 Hu Z, Li B, Qin Z, et al. Job scheduling without prior information in big data processing systems[C]∥IEEE 37th International Conference on Distributed Computing Systems(ICDCS), Atlanta, GA, USA, 2017: 572-582.
6 Hu Z, Li B, Luo J, et al. Flutter:scheduling tasks closer to data across geo-distributed datacenters[C]∥The 35th Annual IEEE International Conference on Computer Communications, San Francisco, CA, USA, 2016: 1-9.
7 Hu Z, Li B, Luo J, et al. Time- and cost-efficient task scheduling across geo-distributed data centers[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 29(3): 705-718.
8 Apache Spark™ — unified analytics engine for big data[DB/OL]. [2019-08-10].
9 Hadoop Apache. [DB/OL]. [2019-08-10].
10 Rimal B P, Maier M. Workflow scheduling in multi-tenant cloud computing environments[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(1): 290-304.
11 Li P, Guo S, Miyazaki T, et al. Traffic-Aware geo-distributed big data analytics with predictable Job completion time[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(6): 1785-1796.
12 Mei J, Li K, Tong Z, et al. Profit maximization for cloud brokers in cloud computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(1): 190-203.
13 EC2instance pricing-amazon web services (AWS). [DB/OL]. [2019-08-10]. .
14 Stoer M, Wagner F. A simple min-cut algorithm[J]. Journal of the ACM(JACM), 1997, 44(4): 585-591.
15 Juve G, Chervenak A, Deelman E, et al. Characterizing and profiling scientific workflows[J]. Future Generation Computer Systems, 2013, 29(3): 682-692.
16 Deelman E, Vahi K, Juve G, et al. Pegasus, a workflow management system for science automation[J]. Future Generation Computer Systems, 2015, 46: 17-35.
17 WorkflowGenerator - Pegasus - Pegasus Workflow management system [DB/OL].[2019-08-10].
18 Lee Y C, Han H, Zomaya A Y, et al. Resource-efficient workflow scheduling in clouds[J]. Knowledge-Based Systems, 2015, 80: 153-162.
[1] 李晓会,陈潮阳,伊华伟,李波. 基于云计算和大数据分析的大规模网络流量预测[J]. 吉林大学学报(工学版), 2021, 51(3): 1034-1039.
[2] 宋元,周丹媛,石文昌. 增强OpenStack Swift云存储系统安全功能的方法[J]. 吉林大学学报(工学版), 2021, 51(1): 314-322.
[3] 金顺福,郄修尘,武海星,霍占强. 基于新型休眠模式的云虚拟机分簇调度策略及性能优化[J]. 吉林大学学报(工学版), 2020, 50(1): 237-246.
[4] 焦玉玲, 徐良成, 王占中, 张鹏. 基于有向网络的双U型装配线平衡实验与分析[J]. 吉林大学学报(工学版), 2018, 48(2): 454-459.
[5] 王旭, 欧阳继红, 陈桂芬. 基于多重序列所有公共子序列的启发式算法度量多图的相似度[J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[6] 赵伟, 曲慧雁. 基于云计算Map-Reduce模型的快速碰撞检测算法[J]. 吉林大学学报(工学版), 2016, 46(2): 578-584.
[7] 李琦,马建峰,熊金波,张涛,刘西蒙. 云中基于常数级密文属性基加密的访问控制机制[J]. 吉林大学学报(工学版), 2014, 44(3): 788-794.
[8] 刘国奇, 刘慧, 高宇, 刘莹, 朱志良. 基于效用的云计算动态资源计费策略[J]. 吉林大学学报(工学版), 2013, 43(06): 1631-1637.
[9] 杨庆芳, 梅朵, 韩振波, 张彪. 基于云计算的蚁群算法求解城市路网最短路径[J]. 吉林大学学报(工学版), 2013, 43(05): 1210-1214.
[10] 孟超, 孙知信, 刘三民. 基于云计算的病毒多执行路径[J]. 吉林大学学报(工学版), 2013, 43(03): 718-726.
[11] 欧阳丹彤, 耿雪娜, 郭劲松, 王晓宇. 基于矩阵计算极小碰集的启发式算法[J]. 吉林大学学报(工学版), 2013, 43(01): 106-110.
[12] 郭平, 但光祥. 云计算中的混合加密算法[J]. 吉林大学学报(工学版), 2012, 42(增刊1): 327-331.
[13] 张华, 彭来湖, 胡旭东, 王献美. 一种应用于纺织加工业的企业云制造模型[J]. 吉林大学学报(工学版), 2012, 42(增刊1): 337-340.
[14] 陈龙, 李俊中. 支持不同粒度运算的远程数据完整性验证[J]. 吉林大学学报(工学版), 2012, 42(增刊1): 295-299.
[15] 聂雄丁, 韩德志, 毕坤. 云计算数据安全[J]. 吉林大学学报(工学版), 2012, 42(增刊1): 332-336.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!