Citation: | Tang Xuhao, Liu Fagui, Wang Bin, Li Chao, Jiang Jun, Tang Quan, Chen Weiming, He Fengwen. Survey on Task Scheduling in Inter-Cloud Environment[J]. Journal of Computer Research and Development, 2023, 60(6): 1262-1275. DOI: 10.7544/issn1000-1239.202220021 |
As cloud computing technology advances continuously, there are a growing number of enterprises and organizations choosing the inter-cloud approach to apply on IT delivery. Inter-cloud environments can efficiently solve problems such as low resource utilization, resource limitation, and vendor lock-in in traditional single-cloud environments, and manage cloud resources in an integrated model. Due to the heterogeneity of resources in the inter-cloud environment, which will complicate the scheduling of inter-cloud tasks. Based on the current status, how to logically schedule user tasks and allocate them to the most suitable inter-cloud resources for execution has developed to be an important issue to be solved in the inter-cloud environment. From the perspective of the inter-cloud environment, we discuss the progress and future challenges of research on the task of scheduling algorithms under this environment. Firstly, combined with the characteristics of an inter-cloud environment, cloud computing is divided into federated cloud and multi-cloud environments and introduced in detail. Meanwhile, the existing task scheduling types are reviewed and their advantages and disadvantages are analyzed. Secondly, based on the classification and current research procedure, representative documents are selected to analyze the algorithms for task scheduling on inter-cloud. Finally, shortcomings in research on algorithms for task scheduling in inter-cloud and future research trends are discussed, which provide a reference for further research on inter-cloud task scheduling.
[1] |
陈海波,夏虞斌,糜泽羽. 跨云计算的机遇、挑战与研究展望[J]. 中国计算机学会通讯,2017,13(3):30−34
Chen Haibo, Xia Yubin, Mi Zeyu. Opportunities, challenges and research prospects of inter-cloud computing[J]. Communications of the CCF, 2017, 13(3): 30−34 (in Chinese)
|
[2] |
Srinivasan A, Quadir M A, Vijayakumar V. Era of cloud computing: A new insight to hybrid cloud[J]. Procedia Computer Science, 2015, 50: 42−51 doi: 10.1016/j.procs.2015.04.059
|
[3] |
Linthicum D S. Emerging hybrid cloud patterns[J]. IEEE Cloud Computing, 2016, 3(1): 88−91 doi: 10.1109/MCC.2016.22
|
[4] |
Chauhan S S, Pilli E S, Joshi R C. A broker based framework for federated cloud environment[C/OL] //Proc of 2016 Int Conf on Emerging Trends in Communication Technologies (ETCT). Piscataway, NJ: IEEE, 2016 [2021-06-15]. https://ieeexplore.ieee.org/abstract/document/7882979
|
[5] |
Petcu D. Multi-cloud: Expectations and current approaches[C] //Proc of 2013 Int Workshop on Multi-Cloud Applications and Federated Clouds. New York: ACM, 2013: 1−6
|
[6] |
IDC, Inc. The content of hybrid architecture continues to enrich, and cloud management software has a lot to offer [EB/OL]. (2020-05-31) [2021-06-11]. https://www.idc.com/getdoc.jsp?containerId=prCHC46448320
|
[7] |
Armbrust M, Fox A, Griffith R, et al. Above the clouds: A Berkeley view of cloud computing[R]. Berkeley: University of California, 2009
|
[8] |
Armbrust M, Fox A, Griffith R, et al. A view of cloud computing[J]. Communications of the ACM, 2010, 53(4): 50−58 doi: 10.1145/1721654.1721672
|
[9] |
Toosi A N, Calheiros R N, Buyya R. Interconnected cloud computing environments: Challenges, taxonomy, and survey[J]. ACM Computing Surveys , 2014, 47(1): 1-47
|
[10] |
Houidi I, Mechtri M, Louati W, et al. Cloud service delivery across multiple cloud platforms[C] //Proc of 2011 IEEE Int Conf on Services Computing. Piscataway, NJ: IEEE, 2011: 741−742
|
[11] |
Ferrer A J, Hernández F, Tordsson J, et al. OPTIMIS: A holistic approach to cloud service provisioning[J]. Future Generation Computer Systems, 2012, 28(1): 66−77 doi: 10.1016/j.future.2011.05.022
|
[12] |
Grozev N, Buyya R. Inter-Cloud architectures and application brokering: Taxonomy and survey[J]. Software: Practice and Experience, 2014, 44(3): 369−390 doi: 10.1002/spe.2168
|
[13] |
Mell P, Grance T. The NIST definition of cloud computing [EB/OL]. (2011-09-01)[2021-06-15]. https://csrc.nist.gov/publications/detail/sp/800-145/final
|
[14] |
Bessani A, Kapitza R, Petcu D, et al. A look to the old-world_sky: EU-funded dependability cloud computing research[J]. ACM SIGOPS Operating Systems Review, 2012, 46(2): 43−56 doi: 10.1145/2331576.2331584
|
[15] |
Celesti A, Tusa F, Villari M, et al. How to enhance cloud architectures to enable cross-federation[C] //Proc of the 3rd Int Conf on Cloud Computing. Piscataway, NJ: IEEE, 2010: 337−345
|
[16] |
Brikman Y. Terraform: Up & Running: Writing Infrastructure as Code[M]. Sebastopol: O'Reilly Media, 2019
|
[17] |
Cuadrado F, Navas A, Duenas J C, et al. Research challenges for cross-cloud applications[C] //Proc of 2014 IEEE Conf on Computer Communications Workshops (INFOCOM WKSHPS). Piscataway, NJ: IEEE, 2014: 19−24
|
[18] |
Wang Huaimin, Shi Peichang, Zhang Yiming. Jointcloud: A cross-cloud cooperation architecture for integrated internet service customization[C] //Proc of the 37th Int Conf on Distributed Computing Systems (ICDCS). Piscataway, NJ: IEEE, 2017: 1846−1855
|
[19] |
史佩昌,尹浩,沃天宇,等. 软件定义的云际计算基础理论和方法研究进展[J]. 中国基础科学,2019,21(6):54−60 doi: 10.3969/j.issn.1009-2412.2019.06.08
Shi Peichang, Yin Hao, Wo Tianyu, et al. Research progress on the basic theory and method of the software-defined jointcloud computing[J]. China Basic Science, 2019, 21(6): 54−60 (in Chinese) doi: 10.3969/j.issn.1009-2412.2019.06.08
|
[20] |
Jena T, Mohanty J R. GA-based customer-conscious resource allocation and task scheduling in multi-cloud computing[J]. Arabian Journal for Science and Engineering, 2018, 43(8): 4115−4130
|
[21] |
田倬璟,黄震春,张益农. 云计算环境任务调度方法研究综述[J]. 计算机工程与应用,2021,57(2):1−11 doi: 10.3778/j.issn.1002-8331.2006-0259
Tian Zhuojing, Huang Zhenchun, Zhang Yinong. Review of task scheduling methods in cloud computing environment[J]. Computer Engineering and Applications, 2021, 57(2): 1−11 (in Chinese) doi: 10.3778/j.issn.1002-8331.2006-0259
|
[22] |
马小晋,饶国宾,许华虎. 云计算中任务调度研究的调查[J]. 计算机科学,2019,46(3):1−8 doi: 10.11896/j.issn.1002-137X.2019.03.001
Ma Xiaojin, Rao Guobin, Xu Huahu. Research on task scheduling in cloud computing[J]. Computer Science, 2019, 46(3): 1−8 (in Chinese) doi: 10.11896/j.issn.1002-137X.2019.03.001
|
[23] |
Mármol F G, Pérez G M. Towards pre-standardization of trust and reputation models for distributed and heterogeneous systems[J]. Computer Standards & Interfaces, 2010, 32(4): 185−196
|
[24] |
胡海洋,刘润华,胡华. 移动云计算环境下任务调度的多目标优化方法[J]. 计算机研究与发展,2017,54(9):1909−1919 doi: 10.7544/issn1000-1239.2017.20160757
Hu Haiyang, Liu Runhua, Hu Hua. Multi-objective optimization for task scheduling in mobile cloud computing[J]. Journal of Computer Research and Development, 2017, 54(9): 1909−1919 (in Chinese) doi: 10.7544/issn1000-1239.2017.20160757
|
[25] |
王亚文, 郭云飞, 刘文彦, 等. 面向云工作流安全的任务调度方法[J]. 计算机研究与发展, 2018, 55(6): 66-75
Wang Yawen, Guo Yunfei, Liu Wenyan, et al. A task scheduling method for cloud workflow security[J]. Journal of Computer Research and Development, 2018, 55(6): 66-75(in Chinese)
|
[26] |
Liu Juefu, Liu Peng. The research of load imbalance based on min-min in grid[C/OL] //Proc of 2010 Int Conf on Computer Design and Applications. Piscataway, NJ: IEEE, 2010 [2021-06-17]. https://ieeexplore.ieee.org/abstract/document/5541399
|
[27] |
Etminani K, Naghibzadeh M. A min-min max-min selective algorithm for grid task scheduling[C/OL] //Proc of the 3rd IEEE/IFIP Int Conf in Central Asia on Internet. Piscataway, NJ: IEEE, 2007 [2021-06-17]. https://ieeexplore.ieee.org/abstract/document/4401694
|
[28] |
Dorigo M, Caro G D. Ant colony optimization: A new meta-heuristic[C] //Proc of 1999 Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 1999: 1470−1477
|
[29] |
Dorigo M, Stützle T. The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances[M]. Berlin: Springer, 2003: 250−285
|
[30] |
Bratton D, Kennedy J. Defining a standard for particle swarm optimization[C] //Proc of 2007 IEEE Swarm Intelligence Symp. Piscataway, NJ: IEEE, 2007: 120−127
|
[31] |
Poli R, Kennedy J, Blackwell T. Particle swarm optimization[J]. Swarm Intelligence, 2007, 1(1): 33−57 doi: 10.1007/s11721-007-0002-0
|
[32] |
高海兵,周驰,高亮. 广义粒子群优化模型[J]. 计算机学报,2005,28(12):1980−1987 doi: 10.3321/j.issn:0254-4164.2005.12.004
Gao Haibing, Zhou Chi, Gao Liang. General particle swarm optimization model[J]. Chinese Journal of Computers, 2005, 28(12): 1980−1987 (in Chinese) doi: 10.3321/j.issn:0254-4164.2005.12.004
|
[33] |
Omara F A, Arafa M M. Genetic Algorithms for Task Scheduling Problem[M]. Berlin: Springer, 2009: 479−507
|
[34] |
Zhao Chenhong, Zhang Shanshan, Liu Qingfeng et al. Independent tasks scheduling based on genetic algorithm in cloud computing[C/OL] //Proc of the 5th Int Conf on Wireless Communications, Networking and Mobile Computing. Piscataway, NJ: IEEE, 2009 [2021-06-17]. https://ieeexplore.ieee.org/abstract/document/5301850
|
[35] |
陈黄科,祝江汉,朱晓敏,等. 云计算中资源延迟感知的实时任务调度方法[J]. 计算机研究与发展,2017,54(2):446−456 doi: 10.7544/issn1000-1239.2017.20151123
Chen Huangke, Zhu Jianghan, Zhu Xiaomin, et al. Resource-delay-aware scheduling for real-time tasks in clouds[J]. Journal of Computer Research and Development, 2017, 54(2): 446−456 (in Chinese) doi: 10.7544/issn1000-1239.2017.20151123
|
[36] |
Shroff P, Watson D W, Flann N S, et al. Genetic simulated annealing for scheduling data-dependent tasks in heterogeneous environments[C] //Proc of the 5th Heterogeneous Computing Workshop (HCW’96). Los Alamitos, CA: IEEE Computer Society 1996, 970: 98−117
|
[37] |
Gan Guoning, Huang Tinglei, Gao Shuai. Genetic simulated annealing algorithm for task scheduling based on cloud computing environment[C] //Proc of 2010 Int Conf on Intelligent Computing and Integrated Systems. Piscataway, NJ: IEEE, 2010: 60−63
|
[38] |
Glover F. Tabu search-part I[J]. ORSA Journal on Computing, 1989, 1(3): 190−206 doi: 10.1287/ijoc.1.3.190
|
[39] |
Liaqat M, Chang V, Gani A, et al. Federated cloud resource management: Review and discussion[J]. Journal of Network and Computer Applications, 2017, 77: 87−105 doi: 10.1016/j.jnca.2016.10.008
|
[40] |
Petri I, Diaz-Montes J, Zou Mengsong, et al. Market models for federated clouds[J]. IEEE Transactions on Cloud Computing, 2015, 3(3): 398−410 doi: 10.1109/TCC.2015.2415792
|
[41] |
Palmieri F, Buonanno L, Venticinque S, et al. A distributed scheduling framework based on selfish autonomous agents for federated cloud environments[J]. Future Generation Computer Systems, 2013, 29(6): 1461−1472 doi: 10.1016/j.future.2013.01.012
|
[42] |
Holt C A, Roth A E. The Nash equilibrium: A perspective[J]. Proceedings of the National Academy of Sciences, 2004, 101(12): 3999−4002 doi: 10.1073/pnas.0308738101
|
[43] |
de Oliveira G S S, Ribeiro E, Ferreira D A, et al. Acosched: A scheduling algorithm in a federated cloud infrastructure for bioinformatics applications[C] //Proc of the 7th IEEE Int Conf on Bioinformatics and Biomedicine. Piscataway, NJ: IEEE, 2013: 8−14
|
[44] |
Coutinho R C, Drummond L M A, Frota Y. Optimization of a cloud resource management problem from a consumer perspective[C] //Proc of European Conf on Parallel Processing. Berlin: Springer, 2013: 218−227
|
[45] |
Coutinho R C, Drummond L M A, Frota Y, et al. Optimizing virtual machine allocation for parallel scientific workflows in federated clouds[J]. Future Generation Computer Systems, 2015, 46: 51−68 doi: 10.1016/j.future.2014.10.009
|
[46] |
Van den Bossche R, Vanmechelen K, Broeckhove J. Cost-optimal scheduling in hybrid IaaS clouds for deadline constrained workloads[C] //Proc of the 3rd Int Conf on Cloud Computing. Piscataway, NJ: IEEE, 2010: 228−235
|
[47] |
Tejaswi T T, Azharuddin M, Jana P K. A GA based approach for task scheduling in multi-cloud environment[J]. arXiv preprint, arXiv: 1511. 08707, 2015
|
[48] |
Lin Bin, Guo Wenzhong, Chen Guolong, et al. Cost-driven scheduling for deadline-constrained workflow on multi-clouds[C] //Proc of the 29th IEEE Int Parallel and Distributed Processing Symp Workshop. Piscataway, NJ: IEEE, 2015: 1191−1198
|
[49] |
Heilig L, Lalla-Ruiz E, Voß S. A cloud brokerage approach for solving the resource management problem in multi-cloud environments[J]. Computers & Industrial Engineering, 2016, 95: 16−26
|
[50] |
Zhang Miao, Liu Li, Liu Songtao. Genetic algorithm based QoS-aware service composition in multi-cloud[C] //Proc of the 1st IEEE Int Conf on Collaboration and Internet Computing (CIC). Piscataway, NJ: IEEE, 2015: 113−118
|
[51] |
Simarro J L L, Moreno-Vozmediano R, Montero R S, et al. Dynamic placement of virtual machines for cost optimization in multi-cloud environments[C] //Proc of the 9th Int Conf on High Performance Computing & Simulation. Piscataway, NJ: IEEE, 2011: 1−7
|
[52] |
Li Jiayin, Qiu Meikang, Ming Zhong, et al. Online optimization for scheduling preemptable tasks on IaaS cloud systems[J]. Journal of Parallel and Distributed Computing, 2012, 72(5): 666−677 doi: 10.1016/j.jpdc.2012.02.002
|
[53] |
Panda S K, Jana P K. A multi-objective task scheduling algorithm for heterogeneous multi-cloud environment[C] //Proc of 2015 Int Conf on Electronic Design, Computer Networks & Automated Verification (EDCAV). Piscataway, NJ: IEEE, 2015: 82−87
|
[54] |
Hu Haiyang, Li Zhongjin, Hu Hua, et al. Multi-objective scheduling for scientific workflow in multicloud environment[J]. Journal of Network and Computer Applications, 2018, 114: 108−122 doi: 10.1016/j.jnca.2018.03.028
|
[55] |
Tang Xiaoyong. Reliability-aware cost-efficient scientific workflows scheduling strategy on multi-cloud systems[J/OL]. IEEE Transactions on Cloud Computing, 2021 [2021-06-15]. https://ieeexplore.ieee.org/abstract/document/9349203
|
[56] |
Cai Xingjuan, Geng Shaojin, Wu Di, et al. A multi-cloud model based many-objective intelligent algorithm for efficient task scheduling in Internet of things[J]. IEEE Internet of Things Journal, 2020, 8(12): 9645−9653
|
[57] |
Wen Zhenyu, Garg S, Aujla G S, et al. Running industrial workflow applications in a software-defined multi-cloud environment using green energy aware scheduling algorithm[J]. IEEE Transactions on Industrial Informatics, 2020, 17(8): 5645−5656
|
[58] |
Karaja M, Ennigrou M, Said L B. Budget-constrained dynamic bag-of-tasks scheduling algorithm for heterogeneous multi-cloud environment[C/OL] //Proc of 2020 Int Multi-Conf on Organization of Knowledge and Advanced Technologies (OCTA). Piscataway, NJ: IEEE, 2020 [2021-06-15]. https://ieeexplore.ieee.org/abstract/document/9151737
|
[59] |
Grozev N, Buyya R. Multi-cloud provisioning and load distribution for three-tier applications[J]. ACM Transactions on Autonomous and Adaptive Systems, 2014, 9(3): 1-21
|
[60] |
Frincu M E, Craciun C. Multi-objective meta-heuristics for scheduling applications with high availability requirements and cost constraints in multi-cloud environments[C] //Proc of the 4th IEEE Int Conf on Utility and Cloud Computing. Piscataway, NJ: IEEE, 2011: 267−274
|
[61] |
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]. Journal of Parallel and Distributed Computing, 2018, 113: 1−16 doi: 10.1016/j.jpdc.2017.10.006
|
[62] |
Cui Jieqi, Chen Pengfei, Yu Guangba. A learning-based dynamic load balancing approach for microservice systems in multi-cloud environment[C] //Proc of the 26th IEEE Int Conf on Parallel and Distributed Systems (ICPADS). Piscataway, NJ: IEEE, 2020: 334−341
|
[63] |
Van den Bossche R, Vanmechelen K, Broeckhove J. Online cost-efficient scheduling of deadline-constrained workloads on hybrid clouds[J]. Future Generation Computer Systems, 2013, 29(4): 973−985 doi: 10.1016/j.future.2012.12.012
|
[64] |
Bittencourt L F, Madeira E R M. HCOC: A cost optimization algorithm for workflow scheduling in hybrid clouds[J]. Journal of Internet Services and Applications, 2011, 2(3): 207−227 doi: 10.1007/s13174-011-0032-0
|
[65] |
Chopra N, Singh S. Deadline and cost based workflow scheduling in hybrid cloud[C] //Proc of the 2nd Int Conf on Advances in Computing, Communications and Informatics (ICACCI). Piscataway, NJ: IEEE, 2013: 840−846
|
[66] |
Zhou Junlong, Wang Tian, Cong Peijin, et al. Cost and makespan-aware workflow scheduling in hybrid clouds[J/OL]. Journal of Systems Architecture, 2019 [2021-06-17]. https://www.sciencedirect.com/science/article/pii/S1383762119302954
|
[67] |
Wang Bo, Wang Changhai, Huang Wanwei, et al. Security-aware task scheduling with deadline constraints on heterogeneous hybrid clouds[J]. Journal of Parallel and Distributed Computing, 2021, 153: 15−28 doi: 10.1016/j.jpdc.2021.03.003
|
[68] |
Yuan Haitao, Bi Jing, Zhou Mengchu. Temporal task scheduling of multiple delay-constrained applications in green hybrid cloud[J]. IEEE Transactions on Services Computing, 2018, 14(5): 1558−1570
|
[69] |
Fan Yuanyuan, Liang Qingzhong, Chen Yunsong, et al. Executing time and cost-aware task scheduling in hybrid cloud using a modified DE algorithm[C] //Proc of the 7th Int Symp on Computational Intelligence and Intelligent Systems. Berlin: Springer, 2015: 74−83
|
[70] |
赵梓铭,刘芳,蔡志平,等. 边缘计算:平台、应用与挑战[J]. 计算机研究与发展,2018,55(2):327−337 doi: 10.7544/issn1000-1239.2018.20170228
Zhao Ziming, Liu Fang, Cai Zhiping, et al. Edge computing: Platforms, applications and challenges[J]. Journal of Computer Research and Development, 2018, 55(2): 327−337 (in Chinese) doi: 10.7544/issn1000-1239.2018.20170228
|
[71] |
苏命峰,王国军,李仁发. 边云协同计算中基于预测的资源部署与任务调度优化[J]. 计算机研究与发展,2021,58(11):2558−2570 doi: 10.7544/issn1000-1239.2021.20200621
Su Mingfeng, Wang Guojun, Li Renfa. Resource deployment with prediction and task scheduling optimization in edge cloud collaborative computing[J]. Journal of Computer Research and Development, 2021, 58(11): 2558−2570 (in Chinese) doi: 10.7544/issn1000-1239.2021.20200621
|
[1] | He Xin, Gui Xiaolin, An Jian. A Distributed Area Coverage Algorithm Based on Delayed Awakening in Wireless Sensor Networks[J]. Journal of Computer Research and Development, 2011, 48(5): 786-792. |
[2] | Xu Jia, Feng Dengguo, Su Purui. Research on Network-Warning Model Based on Dynamic Peer-to-Peer Overlay Hierarchy[J]. Journal of Computer Research and Development, 2010, 47(9): 1574-1586. |
[3] | Xiong Wei, Xie Dongqing, Jiao Bingwang, Liu Jie. A Structured Peer to Peer File Sharing Model with Non-DHT Searching Algorithm[J]. Journal of Computer Research and Development, 2009, 46(3): 415-424. |
[4] | Li Xiaolong, Lin Yaping, Hu Yupeng, Liu Yonghe. A Subset-Based Coverage-Preserving Distributed Scheduling Algorithm[J]. Journal of Computer Research and Development, 2008, 45(1): 180-187. |
[5] | Hu Jinfeng, Hong Chunhui, Zheng Weimin. Granary: An Architecture of Object Oriented Internet Storage Service[J]. Journal of Computer Research and Development, 2007, 44(6): 1071-1079. |
[6] | Zhang Sanfeng and Wu Guoxin. A Fault-Tolerant Asymmetric DHT Method Towards Dynamic and Heterogeneous Network[J]. Journal of Computer Research and Development, 2007, 44(6): 905-913. |
[7] | Cao Jia, Lu Shiwen. Research on Topology Discovery in the Overlay Multicast[J]. Journal of Computer Research and Development, 2006, 43(5): 784-790. |
[8] | Mao Yingchi, Liu Ming, Chen Lijun, Chen Daoxu, Xie Li. A Distributed Energy-Efficient Location-Independent Coverage Protocol in Wireless Sensor Networks[J]. Journal of Computer Research and Development, 2006, 43(2): 187-195. |
[9] | Wen Yingyou, Zhao Jianli, Zhao Linliang, and Wang Guangxing. A Study of the Relationship Between Performance of Topology-Based MANET Routing Protocol and Network Coverage Density[J]. Journal of Computer Research and Development, 2005, 42(4): 684-689. |
[10] | Zhou Jin and Li Yanda. A Peer-to-Peer DHT Algorithm Based on Small-World Network[J]. Journal of Computer Research and Development, 2005, 42(1): 109-117. |