面向WaaS平台的多工作流容错调度策略

doi:10.19665/j.issn1001-2400.20241005

Abstract

Abstract:

As the complexity of scientific computation increases,workflows have become an essential model for automating scientific computations.Workflow as a Service(WaaS) platforms rent virtual machines from Infrastructure as a Service(IaaS) providers to offer users the service of running scientific workflow computations.However,current researches on workflow scheduling in WaaS platforms do not consider the potential for virtual machine downtime to lead to task failures and the delays in virtual machine provisioning.To address this issue,this paper proposes a multi-workflow fault-tolerant scheduling strategy for WaaS platforms.First,considering that WaaS platforms do not schedule hardware resources but operate at the level of virtual machines and containers,we establish a workflow scheduling model suitable for WaaS platforms,taking into account the impact of virtual machine provisioning delays on scheduling.Second,we propose a multi-workflow fault-tolerant scheduling strategy for WaaS platforms,which includes preprocessing,fault-tolerance selection method,task scheduling,and resource adjustment.This involves designing an improved deadline division algorithm for determining the scheduling order,creating a fault-tolerance selection algorithm that combines replication and resubmission,considering task attributes and virtual machine provisioning delays for virtual machine selection and task allocation,and designing a resource adjustment algorithm for avoiding the waiting time for the provisioning delay of virtual machines or containers by deploying resources in advance for the upcoming tasks.Finally,by comparing the proposed scheduling strategy under different virtual machine downtime probabilities,workloads,and deadlines with other algorithms,we demonstrate the effectiveness of the proposed fault-tolerant scheduling strategy for WaaS platforms.

Key words: multi-workflow, fault tolerance scheduling algorithm, WaaS platforms, resource provisioning delay

CLC Number:

TP301.6

ZHI Wentao, ZHAO Hui, MENG Fanxin, WANG Jing, WAN Bo, WANG Quan. Multi-workflow fault-tolerant scheduling strategy for WaaS platforms[J].Journal of Xidian University, 2025, 52(1): 181-195.

Figures/Tables 18

符号	符号名称	符号	符号名称
W	所有工作流集合	type(vm_k)	虚拟机k所对应的类型
Wⁱ	工作流i	pc(vmt_i)	类型为i的虚拟机的性能
Tⁱ	工作流i任务的集合	VM_available	所有可用虚拟机集合
$t j i$	工作流i的第j个任务	avgpc	所有可用虚拟机的平均性能
$t e n t r y i$	工作流i的入口任务	VM_idle	所有空闲虚拟机集合
$t e x i t i$	工作流i的出口任务	Cⁱ	可以处理Wⁱ中任务的容器集合
pred( $t j i$ )	任务 $t j i$ 的前驱任务集合	$c j i$	可以处理Wⁱ的第j个容器
succ( $t j i$ )	任务 $t j i$ 的后继任务集合	vtc(vm_k)	虚拟机vm_k上部署的容器
data( $t j i$ , $t k i$ )	$t j i$ 与 $t k i$ 之间的数据传输量	pt( $t j i$ ,vm_k)	任务 $t j i$ 在vm_k上的处理时间
ftwⁱ	工作流Wⁱ的完成时间	lp $t j i$	$t j i$ 在最高性能虚拟机上处理时间
VM	所有租用过的虚拟机集合	avgp $t j i$	$t j i$ 的平均处理时间
vm_i	租用的虚拟机i	cost( $t j i$ ,vm_k)	任务 $t j i$ 在vm_k上的处理成本
vm_fast	最高性能虚拟机	cost(vm_k)	vm_k的总成本
VMT	所有虚拟机类型集合	est( $t j i$ ,vm_k)	任务 $t j i$ 在vm_k上的最早开始时间
vmt_i	虚拟机类型i	eft( $t j i$ ,vm_k)	任务 $t j i$ 在vm_k上的最早完成时间

References 19

[1]	RATHI S, MEHROTRA D, NAGPAL R, et al. Dynamic Multi-Workflow Scheduling:A Comparative Analysis of Real-time Data[C]//Proceedings of the 2024 IEEE Congress on Evolutionary Computation(CEC). Piscataway:IEEE, 2024:1-6.
[2]	TANG X Y, CAO W B, TANG H Y, et al. Cost-Efficient Workflow Scheduling Algorithm for Applications with Deadline Constraint on Heterogeneous Clouds[J]. IEEE Transactions on Parallel and Distributed Systems, 2022, 33(9):2079-2092.
[3]	单晓杭, 章衡, 谢毅. 基于二维编码两阶段协同进化遗传算法的云工作流调度优化[J]. 计算机集成制造系统, 2023, 29(2):568-580.
	SHAN Xiaohang, ZHANG Heng, XIE Yi. Two Stage Coevolutionary Genetic Algorithm with Two Dimensional Coding for Cloud Workflow Scheduling[J]. Computer Integrated Manufacturing Systems, 2023, 29(2):568-580.
[4]	马学森, 许雪梅, 蒋功辉, 等. 混合自适应粒子群工作流调度优化算法[J]. 计算机应用, 2023, 43(2):474. doi: 10.11772/j.issn.1001-9081.2022010001
	MA Xuesen, XU Xuemei, JIANG Gonghui, et al. Hybrid Adaptive Particle Swarm Optimization Algorithm for Workflow Scheduling[J]. Computer Applications and Software, 2023, 43(2):474.
[5]	MIKRAM H, El K S, SAADI Y. HEPGA:A New Effective Hybrid Algorithm for Scientific Workflow Scheduling in Cloud Computing Environment[J]. Simulation Modelling Practice and Theory, 2024, 130:102864.
[6]	向鹏, 林兵, 俞宏杰, 等. 多vCPU环境中基于容器的科学工作流调度策略[J]. 华南师范大学学报(自然科学版), 2023, 55(1):102-112.
	XIANG Peng, LIN Bing, YU Hongjie, et al. Container-driven Scheduling Strategy for Scientific Workflows in Multi-vCPU Environments[J]. Journal of South China Normal University(Natural Science Edition), 2023, 55(1):102-112.
[7]	SHIN J, ARRAYO D, TANTAWI A, et al. Cloud-Native Workflow Scheduling Using a Hybrid Priority Rule and Dynamic Task Parallelism[C] // Proceedings of the 13th Symposium on Cloud Computing(SoCC’22). New York: ACM, 2022:72-77.
[8]	RAJASEKAR P, PLANAICHAMY Y. Scheduling Multiple Scientific Workflows Using Containers on IaaS Cloud[J]. Journal of Ambient Intelligence and Humanized Computing, 2021, 12(7):7621-7636.
[9]	TAHERI H, ABRISHAMI S, NAGHIBZADEH M. A Cloud Broker for Executing Deadline-Constrained Periodic Scientific Workflows[J]. IEEE Transactions on Services Computing, 2023, 16(5):3089-3100.
[10]	LI Z J, CHANG V, HU H Y, et al. Real-Time and Dynamic Fault-Tolerant Scheduling for Scientific Workflows in Clouds[J]. Information Sciences, 2021, 568:13-39.
[11]	YAO G S, REN Q, LI X P, et al. A Hybrid Fault-Tolerant Schedulingfor Deadline-Constrained Tasks in Cloud Systems[J]. IEEE Transactions on Services Computing, 2020, 15(3):1371-1384.
[12]	MARAHATTA A, XIN Q, CHI C, et al. PEFS:AI-driven Prediction Based Energy-Aware Fault-Tolerant Scheduling Schemefor Cloud Data Center[J]. IEEE Transactions on Sustainable Computing, 2020, 6(4):655-666.
[13]	党伟超, 武婷玉. 基于注意力时空卷积和A2C的虚拟机主动容错优先迁移决策[J]. 计算机应用研究, 2023, 40(12):3606-3613.
	DANG Weichao, WU Tingyu. Active Fault-Tolerant Priority Migration Decision Model for Virtual Machines Based on Attentional Spatio-Temporal Convolution and A2C[J]. Application Research of Computers, 2023, 40(12):3606-3613.
[14]	ALAEI M, KHORSAND R, RAMEZANPOUR M. An Adaptive Fault Detector Strategy for Scientific Workflow Scheduling Based on Improved Differential Evolution Algorithm in Cloud[J]. Applied Soft Computing, 2021, 99:106895.
[15]	MATANI A, NAJI H R, MATALLEBI H. A Fault-Tolerant Workflow Scheduling Algorithm for Grid with Near-Optimal Redundancy[J]. Journal of Grid Computing, 2020, 18(3):377-394.
[16]	WEN Z Y, QASA R, LI Z K, et al. Dynamically Partitioning Workflow over Federated Clouds for Optimising the Monetary Cost and Handling Run-Time Failures[J]. IEEE Transactions on Cloud Computing, 2020, 8(4):1093-1107.
[17]	MASOUMI M, MOTALLEBI H. A Structure-Aware Algorithm for Fault-Tolerant Scheduling of Scientific Workflows[J]. The Journal of Supercomputing, 2022, 78(15):17348-17377.
[18]	DONG T T, XUE F, TANG H L, et al. Deep Reinforcement Learning for Fault-Tolerant Workflow Scheduling in Cloud Environment[J]. Applied Intelligence, 2022, 53(9):9916-9932.
[19]	YAO G, DING Y, HAO K. Using Imbalance Characteristic for Fault-Tolerant Workflow Scheduling in Cloud Systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(12):3671-3683.

类型	性能/MIPS	价格/(美元·h^-1)
Small	2	1
Medium	4	2
Large	8	4
Extra-large	16	8

宕机概率/%	工到达率/(个·min^-1)	截止时间系数
0	0.5	1.1
5	1	1.3
10	2	1.5
15	6	1.7
20	12	1.9

算法	虚拟机宕机概率/%
算法	0	5	10	15	20
FCVD	94.0	92.9	89.3	88.8	87.4
OSAR	82.9	79.6	76.3	74.8	74.2
ICFWS	33.2	31.7	34.1	34.4	28.7
SRPSM-FV	84.1	83.2	79.9	78.7	75.4

算法	工作流到达率/(个·min^-1)
算法	0.5	1.0	2.0	6.0	12.0
FCVD	88.4	89.7	89.2	82.9	80.1
OSAR	74.1	79.2	77.2	77.9	80.0
ICFWS	41.0	40.5	35.0	16.1	4.8
SRPSM-FV	83.1	81.5	81.1	79.4	80.5

算法	工作流到达率/(个·min^-1)
算法	0.5	1.0	2.0	6.0	12.0
FCVD	25 745	27 367	40 000	83 581	139 115
OSAR	26 096	31 184	37 488	80 720	131 208
ICFWS	60 589	55 098	79 023	167 987	273 676
SRPSM-FV	47 200	70 592	117 440	240 360	365 488

Multi-workflow fault-tolerant scheduling strategy for WaaS platforms

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 18

References 19

Related Articles 15

Metrics

Comments

Recommended 0

算法	截止时间系数
算法	1.1	1.3	1.5	1.7	1.9
FCVD	63.8	89.3	92.6	95.5	95.8
OSAR	63.8	78.4	80.5	90.7	95.5
ICFWS	5.7	3.2	41.3	44.9	41.3
SRPSM-FV	67.1	79.0	82.3	90.1	97.0

算法	截止时间系数
算法	1.1	1.3	1.5	1.7	1.9
FCVD	41 265	40 562	41 163	35 707	34 782
OSAR	36 840	366 48	37 280	36 352	37 320
ICFWS	83 259	74 264	69 320	62 749	71 603
SRPSM-FV	141 048	117 648	113 640	95 192	86 856

算法	工作流到达率/(个·min^-1)
算法	0.5	1.0	2.0
FCVD	63.5	75.7	89.2
OSAR	13.7	33.0	58.7
ICFWS	24.9	48.4	85.2
SRPSM-FV	26.2	35.3	37.5

[1]	HAN Jiaxi, ZHAO Hui, FENG Nanzhi, WANG Jing, WAN Bo, WANG Quan. Cluster-oriented semi-online task scheduling method in the edge computing platform [J]. Journal of Xidian University, 2024, 51(6): 104-116.
[2]	ZHANG Chao, ZHAO Hui, ZHANG Zhifeng, WANG Jing, WAN Bo, WANG Quan. Task scheduling method for minimizing completion time in edge collaborative environment [J]. Journal of Xidian University, 2024, 51(4): 114-127.
[3]	GAO Weifeng, WANG Qiong, LI Hong, XIE Jin, GONG Maoguo. Research on the multi-objective algorithm of UAV cluster task allocation [J]. Journal of Xidian University, 2024, 51(2): 1-12.
[4]	HAN Hui,MU Jianjun,JIAO Xiaopeng,ZHAO Zhanzhan. Construction and encoding/decoding methods for the permutation codes correcting a single adjacent transposition error [J]. Journal of Xidian University, 2023, 50(3): 105-111.
[5]	LIU Tianyu,CAO Lei. Many-objective evolutionary algorithm based on the multitasking mechanism [J]. Journal of Xidian University, 2022, 49(4): 134-143.
[6]	SUN Xiyan,SONG Shaojie,JI Yuanfa,LIANG Weibin,LI Youming. Novel unambiguous tracking algorithm for BOC and its derivative signals [J]. Journal of Xidian University, 2022, 49(2): 58-66.
[7]	DU Ruizhong,WANG Yi,TIAN Junfeng. Support dynamic and verifiable scheme for ciphertext retrieval [J]. Journal of Xidian University, 2022, 49(1): 35-46.
[8]	ZHAO Hui,FENG Nanzhi,WANG Quan,WAN Bo,WANG Jing. Dynamic semi-online task scheduling method for the edge computing platform [J]. Journal of Xidian University, 2021, 48(6): 8-15.
[9]	YAN Qunmin,MA Ruiqing,MA Yongxiang,WANG Junjie. Adaptive simulated annealing particle swarm optimization algorithm [J]. Journal of Xidian University, 2021, 48(4): 120-127.
[10]	LIU Tianyu,WANG Zhu. Diversity controlled multiobjective particle swarm optimization [J]. Journal of Xidian University, 2021, 48(3): 106-114.
[11]	ZHANG Hua,GAO Haoran,YANG Xingguo,LI Wenmin,GAO Fei,WEN Qiaoyan. TargetedFool:an algorithm for achieving targeted attacks [J]. Journal of Xidian University, 2021, 48(1): 149-159.
[12]	LI Han,ZHANG Chen,HUANG Hejiao,GUO Yu. Algorithm for encrypted search with forward secure updates and verification [J]. Journal of Xidian University, 2020, 47(5): 48-56.
[13]	LIU Naian,CHEN Zhihao,LIU Guokun,LI Yang. Mechanism for proof-of-reputation consensus for blockchain validator nodes [J]. Journal of Xidian University, 2020, 47(5): 57-62.
[14]	WANG Yudong,GUO Jichang,WANG Tianbao. Algorithm for foggy-image pedestrian and vehicle detection [J]. Journal of Xidian University, 2020, 47(4): 70-77.
[15]	XIAO Lijun,GUO Jichang,GU Xiangyuan. Algorithm for selection of features based on dynamic weights using redundancy [J]. Journal of Xidian University, 2019, 46(5): 155-161.