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

doi:10.13229/j.cnki.jdxbgxb20190854

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

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

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

魏晓辉^1,²(),汤钫宇¹,李洪亮^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 WEI^1,²(),Fang-yu TANG¹,Hong-liang LI^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

摘要/Abstract

摘要：

针对工作流作业跨数据中心传输产生高额流量费用的场景，对跨地理分布数据中心工作流作业资源分配问题进行了分析并建模，使用启发的贪心思想提出了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

魏晓辉,汤钫宇,李洪亮. 地理分布数据中心的工作流经济高效资源分配[J]. 吉林大学学报(工学版), 2021, 51(4): 1349-1357.

Xiao-hui WEI,Fang-yu TANG,Hong-liang LI. Cost-efficient resource allocation algorithm for scientific workflow accross geo-distributed data centers[J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(4): 1349-1357.

图/表 8

图1

图2

表1

模型中各变量含义"

变量名称	变量代表意义
$T$	租赁的节点数目/提交作业的子任务数目
$t a s k i$	第i个子任务的名称
$D b a$	$t a s k a$ 发往 $t a s k b$ 的数据量
$N$	租赁资源涉及的数据中心数目
$n i$	第i个数据中心的名称
$R i$	第i个数据中心上租赁的节点数目
$t a s k L o c a i$	子任务 $t a s k i$ 是否部署在了数据中心 $n a$ 上
$U P a$	数据中心 $n a$ 向外的流量带宽单价
$B w C j i$	$t a s k i$ 向 $t a s k j$ 发送数据的流量带宽费用
$B w C$	工作流作业的整体流量带宽费用

表1

图3

图4

表2

表3

图5

参考文献 18

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.

相关文章 15

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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

工作流结构	作业规模	任务数目	边数目	平均作业内任务数据传输总量/GB
Montage	小	50	108	3 586.8
	中	100	235	73 850.9
	大	400	984	301 382.2
Epigenomics	小	50	54	15 776.6
	中	100	122	81 938.1
	大	400	470	288 345.5
CyberShake	小	50	46	5 177.9
	中	100	96	110 446.3
	大	400	396	434 251.3
Sipht	小	50	56	3 288.9
	中	100	109	54 472.7
	大	400	439	232 937.5
Inspiral	小	50	60	19 407.9
	中	100	123	39 175.8
	大	400	500	158 730.5

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

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

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 18

相关文章 15

Metrics

本文评价

推荐阅读 0