Deadline Constrained MapReduce Jobs Scheduling for Cloud Computing

doi:10.3969/j.issn.1006-2475.2018.11.010

Abstract

Abstract: This paper proposes a deadline constrained MapReduce jobs scheduling approach for cloud computing. A weighted bipartite graph is used to model the problem of scheduling MapReduce jobs. Map jobs and reduce jobs are organized as two isolated sets, and the weights of edges connecting two sets represent the executing time to execute jobs. Furthermore, an integral linear programming method is used to solve the problem of matching the bipartite graph with the least weight. The proposed scheduling approach considers heterogeneous servers in cloud computing, where different servers have different task execution time. This paper online predicts and adjusts the deadlines of different tasks, so improves the performance of processing MapReduce jobs significantly. The experimental results demonstrate that the proposed approach reduces the time of accessing data and the jobs which violates the deadline.

Key words: job scheduling, deadline constraint, cloud computing, performance management

CLC Number:

TP393

ZHOU Bo1， LI Ya-qiong1， LIU Yong-bo1， LI Shou-chao1， SONG Yun-kui2. Deadline Constrained MapReduce Jobs Scheduling for Cloud Computing[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2018.11.010.

References

［1］ MELL P. "The NIST definition of cloud computing," Version 15［J］. Communications of the ACM, 2009,53(6):50.
［2］ DEAN J, GHEMAWAT S. MapReduce: Simplified data processing on large clusters［J］. Communications of the ACM, 2008,51(1):107-113.
［3］ ZAHARIA M, BORTHAKUR D, SARMA J S, et al. Job Scheduling for Multi-user MapReduce Clusters: UCB/EECS-2009-55 ［R］. Electrical Engineering and Computer Sciences University of California at Berkeley, 2009.
［4］ LIU Z, SQUILLANTE M S, WOLF J L. On maximizing service-level-agreement profits［J］. ACM Sigmetrics Performance Evaluation Review, 2001,29(3):43-44.
［5］ POLO J, BECERRA Y, CARRERA D, et al. Deadline-based MapReduce workload management［J］. IEEE Transactions on Network & Service Management， 2013,10(2):231-244.
［6］ DONG X, WANG Y, LIAO H. Scheduling mixed real-time and non-real-time applications in MapReduce environment［C］// Proceedings of IEEE the 17th International Conference on Parallel Distributed Systems. 2011:9-16.
［7］ CHO B， RAHMAN M， CHAJED T， et al. Natjam: Design and evaluation of eviction policies for supporting priorities and deadlines in MapReduce clusters［C］// Proceedings of the 4th Annual Symposium on Cloud Computing. ACM,2013:1-17.
［8］ MATTESS M， CALHEIROS R N， BUYYA R. Scaling MapReduce applications across hybrid clouds to meet soft deadlines［C］// Proceedings of IEEE 27th International Conference on Advanced Information Networking and Applications. 2013:629-636.
［9］ XIE J, MENG F J, WANG H L, et al. Research on scheduling scheme for Hadoop clusters［J］. Procedia Computer Science, 2013,18,2468-2471.
［10］SUN M M, ZHUANG H, ZHOU X H, et al. HPSO: Prefetching based scheduling to improve data locality for MapReduce Clusters［C］// International Conference on Algorithms and Architectures for Parallel Processing. Springer, 2014:82-95.
［11］ZHANG X H, ZHONG Z Y, FENG S Z, et al. Improving data locality of MapReduce by scheduling in homogeneous computing environments［C］// IEEE the 9th International Symposium on Parallel and Distributed Processing with Applications. 2011:120-126.
［12］SEO S, JANG I, WOO K, et al. HPMR: Prefetching and pre-shuffling in shared MapReduce computation environment［C］// IEEE International Conference on Cluster Computing and Workshops. 2009:1-8.
［13］SURESH S, GOPALAN N. Delay scheduling based replication scheme for Hadoop distributed file system［J］. Information Technology and Computer Science, 2015(4):73-78.
［14］WANG W, ZHU K, YING L, et al. Map task scheduling in Mapreduce with data locality: Throughput and heavy-traffic optimality［C］// INFOCOM’13. IEEE, 2013:1609-1617.
［15］MADNI S H H, LATIFF M S A, COULIBALY Y, et al. Resource scheduling for infrastructure as a service (IaaS) in cloud computing: Challenges and opportunities［J］. Journal of Network & Computer Applications, 2016,68(C):173-200.
［16］NAYAK S C, TRIPATHY C. Deadline sensitive lease scheduling in cloud computing environment using AHP［J］. Journal of King Saud University(Computer and Information Sciences), 2018,30(2):152-163.
［17］WERF J M, DONGEN B F, HURKENS C A, et al. Process discovery using integer linear programming［C］// Proceedings of the 29th International Conference on Applications and Theory of Petri Nets. 2008:368-387.

[1]	HE Yu-peng, TAO Yong, WANG Bing-heng, ZHAO Ying-nan. Research Status and Prospect of Edge Computing in Smart Distribution Network [J]. Computer and Modernization, 2023, 0(08): 87-92.
[2]	YANG Bo, XU Sheng-chao. Security Protection Method of Cloud Network Special Line Scenarios Based on SRv6#br# Service Chain [J]. Computer and Modernization, 2023, 0(08): 107-111.
[3]	MAO Ming-yang, XU Sheng-chao. Communication Terminal Attack Behavior Identification Algorithm Based on Trusted Cloud Computing#br# [J]. Computer and Modernization, 2022, 0(11): 37-42.
[4]	CAO Yu, LI Xiao-hui, LIU Zhong-lin, JIA He, FEI Zhi-wei. Review of Big Data Workflow Orchestration and Management System in Cloud Environment [J]. Computer and Modernization, 2022, 0(01): 41-53.
[5]	ZHANG Xiao-min. An Attribute-based Multi-keyword Searchable Scheme Based on Bloom Filters [J]. Computer and Modernization, 2021, 0(08): 104-111.
[6]	DENG Bin-tao, XU Sheng-chao. A Differential Evolution K-mediods Clustering Algorithm Based on Dynamic Gemini Population [J]. Computer and Modernization, 2021, 0(07): 54-59.
[7]	WU Jun-cai, LIU Xue-fang . Digital Resource Allocation Based on Cloud Computing and Deep Belief Network [J]. Computer and Modernization, 2021, 0(05): 78-82.
[8]	LU Ge-hao, YANG Dan-ni. Development Status and Prospect of Blockchain as a Service [J]. Computer and Modernization, 2020, 0(10): 31-35.
[9]	LIANG Ci1, CHEN Shi-ping2. Packet Drift Strategy Based on Packet Cluster Mapping Architecture [J]. Computer and Modernization, 2019, 0(11): 112-.
[10]	DING Shun1, CHEN Shi-ping2. Construction and Application of Experimental Platform #br# Based on Packet Cluster Mapping Mechanism [J]. Computer and Modernization, 2019, 0(11): 120-.
[11]	WEN Ting-ting, LI Hong-zhe. Elastic Load Balancing Algorithm for Cloud Computing Service [J]. Computer and Modernization, 2019, 0(10): 28-.
[12]	YUAN Min-fu, LI Yin， CHEN Sheng-jian， ZHENG Xiang-wei. Cloud platform Based Blockchain Networking and Data Storage Mechanism [J]. Computer and Modernization, 2019, 0(09): 46-.
[13]	WANG Shao-qiang, WANG Yu. New Data Processing System Based on Edge Computing [J]. Computer and Modernization, 2019, 0(07): 15-.
[14]	WANG Xu1,2, NI Hong2, HAN Rui2. Auction-based Resource Match Algorithm in Data Centers [J]. Computer and Modernization, 2018, 0(10): 114-.
[15]	CHEN Fang, ZHAO Yang. Mobile Health Monitoring System Based on Cloud Computing [J]. Computer and Modernization, 2017, 0(7): 68-71+90.