计算机科学 ›› 2022, Vol. 49 ›› Issue (11): 250-258.doi: 10.11896/jsjkx.211200234

• 计算机网络 • 上一篇    下一篇

多云工作流调度综述

于浩雯1, 刘波1, 周娜琴2, 林伟伟3, 柳鹏1   

  1. 1 华南师范大学计算机学院 广州 510631
    2 广州大学网络空间先进技术研究院 广州 510006
    3 华南理工大学计算机科学与工程学院 广州 510006
  • 收稿日期:2021-12-21 修回日期:2022-05-20 出版日期:2022-11-15 发布日期:2022-11-03
  • 通讯作者: 刘波(liugubin@sohu.com)
  • 作者简介:(me@yuhaowen.com)
  • 基金资助:
    广东省重点领域研发计划(2021B0101420002,20200704002);国家自然科学基金面上项目(62002078,61872084);广东省基础与应用基础研究基金(2019B030302002);广州市开发区国际合作项目(2020GH10,2021GH10)

Survey of Multi-cloud Workflow Scheduling

YU Hao-wen1, LIU Bo1, ZHOU Na-qin2, LIN Wei-wei3, LIU Peng1   

  1. 1 School of Computer Science,South China Normal University,Guangzhou 510631,China
    2 School of Computer Science and Network Engineering,Guangzhou University,Guangzhou 510006,China
    3 School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,China
  • Received:2021-12-21 Revised:2022-05-20 Online:2022-11-15 Published:2022-11-03
  • About author:YU Hao-wen,born in 1997,postgra-duate.Her main research interests include cloud computing and resource scheduling.
    LIU Bo,born in 1968,Ph.D,professor,is a member of China Computer Federation.His main research interests include cloud computing,big data technology and distributed security technology.
  • Supported by:
    Key Research and Development Program of Guangdong Province(2021B0101420002,20200704002),General Project of National Natural Science Foundation of China(62002078,61872084),Basic and Applied Basic Research Foundation of Guangdong Province(2019B030302002) and Guangzhou Development Zone International Cooperation Project(2020GH10,2021GH10).

摘要: 传统的云供应商单独为用户提供服务,这导致了本地云资源不足和扩展费用较高等问题。而新兴的多云组合地理位置不同的云供应商的服务,为用户提供了更多的选择,逐渐成为了研究的热点。同时,工作流调度又是多云研究的关键问题之一。为此,文中首先对多云环境下的工作流调度技术做了深入的调查和分析,然后将多云下的工作流调度方法进行分类和比较,重点阐述了面向成本、面向完工时间的单目标优化工作流调度,面向成本和完工时间,面向响应时间和成本,面向可靠性、成本和完工时间的多目标优化工作流调度,以及面向其他多目标优化的多云工作流调度。最后,在此基础上讨论了多云环境下工作流调度的未来研究方向:不确定性工作流调度、能耗与其他目标的联合调度优化、与边缘服务器协同的调度优化、虚拟机和Serverless平台混合调度。

关键词: 多云, 工作流, 资源调度

Abstract: Traditional cloud providers provide services solely for users,which has problems of insufficient local cloud resources and high expansion costs.While the emerging multi-cloud combines services of cloud providers with different geographical locations providing users with more choices and has gradually become a research hotspot.At the same time,workflow scheduling is one of the key problems in multi-cloud research.Therefore,this paper firstly makes a thorough investigation and analysis on workflow scheduling technology in multi-cloud environment,then compares and classifies the workflow scheduling method inclu-ded.This paper focuses on single objective workflow scheduling optimization problem for cost and completion time,multi-objective optimization workflow scheduling problem for cost and completion time,for response time and cost,for reliability,cost and completion time,and for other multi-objective optimization.Finally,the future research directions of workflow scheduling in the multi-cloud environment are discussed,including uncertain workflow scheduling,joint scheduling optimization of energy consumption and other objectives,scheduling optimization with edge servers,and hybrid scheduling of virtual machine and Serverless platform.

Key words: Multi-cloud, Workflow, Scheduling of resources

中图分类号: 

  • TP393
[1]LEE K.Comments on Secure Data Sharing in Cloud Computing Using Revocable-Storage Identity-Based Encryption[J].IEEE Transactions on Cloud Computing,2020,8(4):1299-1300.
[2]CUI J,ZHANG X,ZHONG H,et al.Extensible conditional privacy protection authentication scheme for secure vehicular networks in a multi-cloud environment [J/OL].IEEE Transactions on Information Forensics and Security,2019,15:1654-1667.https://ieeexplore.ieee.org/abstract/document/8865553.
[3]ZHANG B,ZENG Z,SHI X,et al.A novel cooperative resource provisioning strategy for Multi-Cloud load balancing [J/OL].Journal of Parallel and Distributed Computing,2021,152:98-107.https://www.sciencedirect.com/science/article/abs/pii/S0743731521000241.
[4]Multicloud.[EB/OL].(2021-08-09).[2021-11-08].https://www.ibm.com/cloud/learn/multicloud.
[5]HEILIG L,LALLA-RUIZ E,VO S.Modeling and solvingcloud service purchasing in multi-cloud environments [J/OL].Expert Systems with Applications,2020,147:113165.https://www.sciencedirect.com/science/article/abs/pii/S0957417419308826.
[6]GHAHRAMANI M H,ZHOU M C,HON C T.Toward cloud computing QoS architecture:Analysis of cloud systems and cloud services[J].IEEE/CAA Journal of Automatica Sinica,2017,4(1):6-18.
[7]KANG S,VEERAVALLI B,AUNG K M M.Dynamic scheduling strategy with efficient node availability prediction for handling divisible loads in multi-cloud systems [J/OL].Journal of Parallel and Distributed Computing,2018,113:1-16.https://www.sciencedirect.com/science/article/abs/pii/S0743731517302824.
[8]Global Cloud Computing Market Size & Share Will Reach USD 1025.9 Billion by 2026:Facts &Factors[EB/OL].(2021-01-22)[2021-02-28].https://www.globenewswire.com/news.
[9]IRANMANESH A,NAJI H R.DCHG-TS:a deadline-constrai-ned and cost-effective hybrid genetic algorithm for scientific workflow scheduling in cloud computing [J].Cluster Computing,2021,24(2):667-681.
[10]TOMARCHIO O,CALCATERRA D,DI MODICA G.Cloud resource orchestration in the multi-cloud landscape:a systematic review of existing frameworks [J].Journal of Cloud Computing,2020,9(1):1-24.
[11]HOSSEINZADEH M,GHAFOUR M Y,HAMA H K,et al.Multi-objective task and workflow scheduling approaches in cloud computing:a comprehensive review [J/OL].Journal of Grid Computing,2020:1-30.https://link.springer.com/article/10.1007/s10723-020-09533-z.
[12]ARUNARANI A R,MANJULA D,SUGUMARAN V.Taskscheduling techniques in cloud computing:A literature survey [J/OL].Future Generation Computer Systems,2019,91:407-415.https://www.sciencedirect.com/science/article/abs/pii/S0167739X17321519.
[13]KUMAR M,SHARMA S C,GOEL A,et al.A comprehensive survey for scheduling techniques in cloud computing [J/OL].Journal of Network and Computer Applications,2019,143:1-33.https://www.sciencedirect.com/science/article/abs/pii/S1084804519302036.
[14]MASDARI M,ZANGAKANI M.Efficient task and workflow scheduling in inter-cloud environments:challenges and opportunities [J].The Journal of Supercomputing,2020,76(1):499-535.
[15]ALALUNA M,VIAL E,NEVES N,et al.Secure multi-cloud network virtualization [J/OL].Computer Networks,2019,161:45-60.https://www.sciencedirect.com/science/article/abs/pii/S1389128618312155.
[16]WANG G,NG T S E.The impact of virtualization on network performance of amazon ec2 data center[C]//2010 Proceedings IEEE INFOCOM.IEEE,San Diego,CA,USA,2010:1-9.
[17]REDKAR T,GUIDICI T,MEISTER T.Windows azure plat-form[M].New York:Apress,2009.
[18]ZHU Q H,TANG H,HUANG J J,et al.Task Scheduling for Multi-Cloud Computing Subject to Security and Reliability Constraints [J].IEEE/CAA Journal of Automatica Sinica,2021,8(4):848-865.
[19]LIU J,REN J,DAI W,et al.Online Multi-Workflow Scheduling under Uncertain Task Execution Time in IaaS Clouds [J/OL].IEEE Transactions on Cloud Computing,2019:1-1.https://ieeexplore.ieee.org/abstract/document/8669862.
[20]CHEN W,XIE G,LI R,et al.Efficient task scheduling for bu-dget constrained parallel applications on heterogeneous cloud computing systems [J/OL].Future Generation Computer Systems,2017,74:1-11.https://www.sciencedirect.com/science/article/abs/pii/S0167739X16304411.
[21]CAO B,ZHAO J,GU Y,et al.Security-Aware Industrial Wireless Sensor Network Deployment Optimization[J].IEEE Transa-ctions on Industrial Informatics,2020,16(8):5309-5316.
[22]ROSA M J F,RALHA C G,HOLANDA M,et al.Computatio-nal resource and cost prediction service for scientific workflows in federated clouds[J/OL].Future Generation Computer Systems,2021,125:844-858.https://www.sciencedirect.com/science/article/abs/pii/S0167739X21002922.
[23]PAKNEJAD P,KHORSAND R,RAMEZANPOUR M.Chaotic improved PICEA-g-based multi-objective optimization for workflow scheduling in cloud environment [J/OL].Future Generation Computer Systems,2021,117:12-28.https://www.scien-cedirect.com/science/article/abs/pii/S0167739X20330260.
[24]FAKHFAKH F,KACEM H H,KACEM A H.Workflowscheduling in cloud computing:a survey[C]//2014 IEEE 18th International Enterprise Distributed Object ComputingConfe-rence Workshops and Demonstrations.IEEE,Ulm,Germany,2014:372-378.
[25]MING T,OTA K,DONG M X.DSARP:dependable scheduling with active replica placement for workflow applications in cloud computing [J/OL].IEEE Transactions on Cloud Computing,2016:1069-1078.https://ieeexplore.ieee.org/abstract/document/7742980.
[26]MOHAMMADI S,POURKARIMI L,PEDRAM H.Integer li-near programming-based multi-objective scheduling for scientific workflows in multi-cloud environments[J].The Journal of Supercomputing,2019,75(10):6683-6709.
[27]ZHOU J L,WANG T,CONG P J,et al.Cost and makespan-aware workflow scheduling in hybrid clouds [J/OL].Journal of Systems Architecture,2019,100:101631.https://www.scien-cedirect.com/science/article/pii/S1383762119302954.
[28]BUGINGO E,ZHANG D,CHEN Z,et al.Towards decomposition based multi-objective workflow scheduling for big data processing in clouds [J].Cluster Computing,2021,24(1):115-139.
[29]GU Y,BUDATI C.Energy-aware workflow scheduling and optimization in clouds using bat algorithm [J/OL].Future Generation Computer Systems,2020,113:106-112.https://www.scien-cedirect.com/science/article/abs/pii/S0167739X19317066.
[30]ZHANG L,LI K,LI C,et al.Bi-objective workflow scheduling of the energy consumption and reliability in heterogeneous computing systems[J/OL].Information Sciences,2017,379:241-256.https://www.sciencedirect.com/science/article/abs/pii/S0020025516305722.
[31]JIANG F,FERRITER K,CASTILLO C.PIVOT:Cost-AwareScheduling of Data-Intensive Applications in a Cloud-Agnostic System [R/OL].Technical Report TR-19-02.RENCI,University of North Carolina at Chapel Hill.8 pages.https://renci.org/technical-reports/tr-19-02,2019.
[32]JIANG F,FERRITER K,CASTILLO C.A cloud-agnosticframework to enable cost-aware scheduling of applications in a multi-cloud environment[C]//2020 IEEE/IFIP Network Operations and Management Symposium(NOMS 2020).IEEE,Budapest,Hungary,2020:1-9.
[33]XU S J,LIU G G.A Novel Scheduling Algorithm for Scientific Workflow in Multi-cloud Environment[J].Journal of Minjiang University,2018,39(5):63-72.
[34]HEIDSIECK G,OLIVEIRA D D,PACITTI E,et al.Cache-aware scheduling of scientific workflows in a multisite cloud[J/OL].Future Generation Computer Systems,2021,122(7).https://www.sciencedirect.com/science/article/abs/pii/S0167739X21000923.
[35]LIU J,PACITTIE,VALDURIE Z P,et al.Multi-objectivescheduling of Scientific Workflows in multisite clouds [J].Future Generation Computer Systems,2016,63(oct.):76-95.
[36]SENTURK I F,BALAKRISHNAN P,ABU-DOLEH A,et al.A resource provisioning framework for bioinformatics applications in multi-cloud environments [J/OL].Future Generation Computer Systems,2018,78:379-391.https://www.sciencedirect.com/science/article/abs/pii/S0167739X16301911.
[37]ULABEDIN Z,NAZIR B.Replication and data management-based workflow scheduling algorithm for multi-cloud data centre platform [J/OL].The Journal of Supercomputing,2021:1-30.https://link.springer.com/article/10.1007/s11227-020-03541-2.
[38]TAO S, MA H,CHEN G.A genetic-based approach to location-aware cloud service brokering in multi-cloud environment[C]//2019 IEEE International Conference on Services Computing(SCC).IEEE,2019.
[39]MA H,DA SILVA A S,KUANG W.NSGA-II with local search for multi-objective application deployment in multi-cloud[C]//2019 IEEE Congress on Evolutionary Computation(CEC).IEEE,Wellington,New Zealand,2019:2800-2807.
[40]ZHANG Q.Knowledge Incorporation in Evolutionary Computation [Book Review][J].IEEE Computational Intelligence Magazine,2006,1(4):58-59.
[41]SHI T,MA H,CHEN G.Seeding-Based Multi-Objective Evolutionary Algorithms for Multi-Cloud Composite Applications Deployment[C]//2020 IEEE International Conference on Services Computing(SCC).IEEE,Beijing,China,2020:240-247.
[42]POOLA D,RAMAMOHANARAO K,BUYYA R.Enhancingreliability of workflow execution using task replication and spot instances [J].ACM Transactions on Autonomous and Adaptive Systems(TAAS),2016,10(4):1-21.
[43]SINGH A,CHATTERJEE K.Cloud security issues and challenges:A survey[J/OL].Journal of Network and Computer Applications,2017,79:88-115.https://www.sciencedirect.com/science/article/abs/pii/S1084804516302983.
[44]HU H,LI Z,HU H,et al.Multi-objective scheduling for scientific workflow in multicloud environment [J/OL].Journal of Network and Computer Applications,2018,114:108-122.https://www.sciencedirect.com/science/article/abs/pii/S1084804518301152.
[45]FARID M,LATIP R,HUSSIN M,et al.Scheduling ScientificWorkflow Using Multi-Objective Algorithm With Fuzzy Resource Utilization in Multi-Cloud Environment [J/OL].IEEE Access,2020.https://ieeexplore.ieee.org/abstract/document/8976136.
[46]MENDELJ M.Fuzzy logic systems for engineering:a tutorial[J].Proceedings of the IEEE,1995,83(3):345-377.
[47]TANG X.Reliability-Aware Cost-Efficient Scientific Workflows Scheduling Strategy on Multi-Cloud Systems [J/OL].IEEE Transactions on Cloud Computing,2021.https://ieeexplore.ieee.org/abstract/document/9349203.
[48]MISHRA S K,MISHRA S,ALSAYAT A,et al.Energy-aware task allocation for multi-cloud networks [J/OL].IEEE Access,2020,8:178825-178834.https://ieeexplore.ieee.org/abstract/document/9205994.
[49]BARIKA M,GARG S,CHAN A,et al.Scheduling algorithmsfor efficient execution of stream workflow applications in multicloud environments [J].IEEE Transactions on Services Computing,2022,15(2):860-875.
[50]CHEN Z,LIN K,LIN B,et al.Adaptive Resource Allocation and Consolidation for Scientific Workflow Scheduling in Multi-Cloud Environments [J/OL].IEEE Access,2020,8:190173-190183.https://ieeexplore.ieee.org/document/9233315.
[51]MANAM S,MOESSNER K,VURAL S.A Cost-Aware Strategy for Deadline Constrained Scientific Workflows[J].Journal of Physics:Conference Series,2020,1577(1):012036.
[52]SHI T,MA H,CHEN G,et al.Location-aware and budget-constrained service deployment for composite applications in multi-cloud environment [J].IEEE Transactions on Parallel and Distributed Systems,2020,31(8):1954-1969.
[53]WEN Z,GARG S,AUJLA G S,et al.Running Industrial Workflow Applications in a Software-Defined Multicloud Environment Using Green Energy Aware Scheduling Algorithm [J].IEEE Transactions on Industrial Informatics,2020,17(8):5645-5656.
[54]LI R,WU C Q,HOU A,et al.On scheduling of high-throughput scientific workflows under budget constraints in multi-cloud environments[C]//2018 IEEE International Conference on Parallel & Distributed Processing with Applications,Ubiquitous Computing & Communications,Big Data & Cloud Computing,Social Computing & Networking,Sustainable Computing & Communications(ISPA/IUCC/BDCloud/SocialCom/SustainCom).IEEE,Melbourne,VIC,Australia,2018:1087-1094.
[55]CALZAROSSA M C,DELLA VEDOVA M L,MASSARI L,et al.Multi-Objective Optimization of Deadline and Budget-Aware Workflow Scheduling in Uncertain Clouds [J/OL].IEEE Access,2021,9:89891-89905.https://ieeexplore.ieee.org/abstract/document/9461757.
[56]CHEN H,ZHU X,LIU G,et al.Uncertainty-Aware OnlineScheduling for Real-Time Workflows in Cloud Service Environment [J/OL].IEEE Transactions on Services Computing,2018.https://ieeexplore.ieee.org/abstract/document/8443134.
[57]ZHANG X D.Multi-objective optimization of workflow scheduling in uncertain cloud environment[J/OL].Computer Enginee-ring and Design,2021,42(7):9.https://www.cnki.com.cn/Article/CJFDTotal-SJSJ202107021.htm.
[58]XIE Y,ZHU Y,WANG Y,et al.A novel directional and non-local-convergent particle swarm optimization based workflow scheduling in cloud-edge environment[J/OL].Future Generation Computer Systems,2019,97:361-378.https://www.scien-cedirect.com/science/article/abs/pii/S0167739X18321332.
[59]XU X,CAO H,GENG Q,et al.Dynamic resource provisioning for workflow scheduling under uncertainty in edge computing environment [J/OL].Concurrency and Computation:Practice and Experience,2020.https://onlinelibrary.wiley.com/doi/abs/10.1002/cpe.5674.
[60]DAS A,LEAF A,VARELA C A,et al.Skedulix:Hybrid Cloud Scheduling for Cost-Efficient Execution of Serverless Applications[C]//2020 IEEE 13th International Conference on Cloud Computing(CLOUD).IEEE,Beijing,China,2020:609-618.
[61]BAARZI A F,KESIDIS G,JOE-WONG C,et al.On Merits and Viability of Multi-Cloud Serverless[C]//Proceedings of the ACM Symposium on Cloud Computing.Seattle,WA,USA,2021:600-608.
[62]MA Z H,LIU B,LIN W W,et al.A Survey of resource scheduling for serverless plantform[J].Computer Science,2021,48(4):261-267.
[1] 柳鹏, 刘波, 周娜琴, 彭心怡, 林伟伟.
混合云工作流调度综述
Survey of Hybrid Cloud Workflow Scheduling
计算机科学, 2022, 49(5): 235-243. https://doi.org/10.11896/jsjkx.210300303
[2] 林潮伟, 林兵, 陈星.
边缘环境下基于模糊理论的科学工作流调度研究
Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment
计算机科学, 2022, 49(2): 312-320. https://doi.org/10.11896/jsjkx.201000102
[3] 宋海宁, 焦健, 刘永.
高速公路中的移动边缘计算研究
Research on Mobile Edge Computing in Expressway
计算机科学, 2021, 48(6A): 383-386. https://doi.org/10.11896/jsjkx.200900212
[4] 宁玉辉, 姚喜.
一种应急指挥系统的设计与实现
Design and Implementation of Emergency Command System
计算机科学, 2021, 48(6A): 613-618. https://doi.org/10.11896/jsjkx.201000136
[5] 窦帅, 李子扬, 朱家佳, 李晓辉, 李雪松, 米琳, 杨光, 李传荣.
基于jBPM的科学试验管理系统的设计与实现
Design and Implementation of Scientific Experiment Management System Based on jBPM
计算机科学, 2021, 48(6A): 658-663. https://doi.org/10.11896/jsjkx.200600158
[6] 马泽华, 刘波, 林伟伟, 李加伟.
无服务器平台资源调度综述
Survey of Resource Scheduling for Serverless Platforms
计算机科学, 2021, 48(4): 261-267. https://doi.org/10.11896/jsjkx.200800023
[7] 何亨, 蒋俊君, 冯可, 李鹏, 徐芳芳.
多云环境中基于属性加密的高效多关键词检索方案
Efficient Multi-keyword Retrieval Scheme Based on Attribute Encryption in Multi-cloud Environment
计算机科学, 2021, 48(11A): 576-584. https://doi.org/10.11896/jsjkx.201000026
[8] 刘漳辉, 赵旭, 林兵, 陈星.
混合云环境下基于模糊理论的科学工作流数据布局策略
Data Placement Strategy of Scientific Workflow Based on Fuzzy Theory in Hybrid Cloud
计算机科学, 2021, 48(11): 199-207. https://doi.org/10.11896/jsjkx.200900009
[9] 马堉银, 郑万波, 马勇, 刘航, 夏云霓, 郭坤银, 陈鹏, 刘诚武.
一种基于深度强化学习与概率性能感知的边缘计算环境多工作流卸载方法
Multi-workflow Offloading Method Based on Deep Reinforcement Learning and ProbabilisticPerformance-awarein Edge Computing Environment
计算机科学, 2021, 48(1): 40-48. https://doi.org/10.11896/jsjkx.200900195
[10] 张龙信, 周立前, 文鸿, 肖满生, 邓晓军.
基于异构云计算的成本约束下的工作流能量高效调度算法
Energy Efficient Scheduling Algorithm of Workflows with Cost Constraint in Heterogeneous Cloud Computing Systems
计算机科学, 2020, 47(8): 112-118. https://doi.org/10.11896/jsjkx.200300038
[11] 孙敏, 陈中雄, 叶侨楠.
云环境下基于HEDSM的工作流调度策略
Workflow Scheduling Strategy Based on HEDSM Under Cloud Environment
计算机科学, 2020, 47(6): 252-259. https://doi.org/10.11896/jsjkx.190400047
[12] 简琤峰, 平靖, 张美玉.
面向边缘计算的Storm边缘节点调度优化方法
Edge Computing-oriented Storm Edge Node Scheduling Optimization Method
计算机科学, 2020, 47(5): 277-283. https://doi.org/10.11896/jsjkx.190600048
[13] 徐飞, 王少昌, 杨卫霞.
基于博弈论的云资源调度算法
Cloud Resource Scheduling Algorithm Based on Game Theory
计算机科学, 2019, 46(6A): 295-299.
[14] 汪晨欣, 杨家海, 庄奕, 罗念龙.
未来网络试验设施的节点资源调度算法
Node Resource Scheduling for Future Network Experimentation Facility
计算机科学, 2019, 46(12): 95-100. https://doi.org/10.11896/jsjkx.190400106
[15] 赵鹏, 吴礼发, 洪征.
基于经纪人的多云访问控制模型研究
Research on Broker Based Multicloud Access Control Model
计算机科学, 2019, 46(11): 123-129. https://doi.org/10.11896/jsjkx.190300112
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!