Performance analysis of backup-task scheduling with deadline time in cloud computing

Previous Article
Modeling the signaling overhead in Host Identity Protocol-based secure mobile architectures
JIMO Home
This Issue
Next Article
A novel active DRX mechanism in LTE technology and its performance evaluation

July 2015, 11(3): 867-886. doi: 10.3934/jimo.2015.11.867

Performance analysis of backup-task scheduling with deadline time in cloud computing

Kyosuke Hashimoto ^1, , Hiroyuki Masuyama ^1, , Shoji Kasahara ^2, and Yutaka Takahashi ^1,

1.	Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan
2.	Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara 630-0192

Received October 2013 Revised May 2014 Published October 2014

Abstract
Related Papers

In large-scale parallel job processing for cloud computing, a huge task is divided into subtasks, which are processed independently on a cluster of machines called workers. Since the task processing lasts until all the subtasks are completed, a slow worker machine makes the overall task-processing time long, degrading the task-level throughput. In order to alleviate the performance degradation, MapReduce conducts backup execution, in which the master node schedules the remaining in-progress subtasks when the whole task operation is close to completion. In this paper, we investigate the effect of backup tasks on the task-level throughput. We consider the backup-task scheduling in which a backup subtask for a worker starts when the subtask-processing time of the worker reaches the deadline time. We analyze the task-level processing-time distribution by considering the maximum subtask-processing time among workers. The task throughput and the amount of all the workers' processing times are derived when the worker-processing-time (WPT) follows a hyper-exponential, Weibull, and Pareto distribution. We also propose an approximate method to derive performance measures based on extreme value theory. The approximations are validated by Monte Carlo simulation. Numerical examples show that the performance improvement by backup tasks significantly depends on workers' processing time distribution.

Keywords: extreme value theory, backup task, deadline time, Cloud computing, performance evaluation..

Mathematics Subject Classification: 62G32, 60H3.

Citation: Kyosuke Hashimoto, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of backup-task scheduling with deadline time in cloud computing. Journal of Industrial and Management Optimization, 2015, 11 (3) : 867-886. doi: 10.3934/jimo.2015.11.867

References:

[1]	S. Ali, B. Eslamnour and Z. Shah, A case for on-machine load balancing, Journal of Parallel and Distributed Computing, 71 (2011), 556-564. doi: 10.1016/j.jpdc.2010.11.003.
[2]	L. A. Barroso and U. Hölzle, The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines, Morgan & Claypool, 2009. doi: 10.2200/S00193ED1V01Y200905CAC006.
[3]	W. Cirne, D. Paranhos, F. Brasileiro and L. F. W. Góes, On the efficacy, efficiency and emergent behavior of task replication in large distributed systems, Parallel Computing, 33 (2007), 213-234. doi: 10.1016/j.parco.2007.01.002.
[4]	J. Dean and S. Ghemawat, MapReduce: Simplified data processing on large clusters, Communications of the ACM, 51 (2008), 107-113. doi: 10.1145/1327452.1327492.
[5]	M. Dobber, R. V. D. Mei and G. Koole, Dynamic load balancing and job replication in a global-scale grid environment: A comparison, IEEE Transactions on Parallel and Distributed Systems, 20 (2009), 207-218. doi: 10.1109/TPDS.2008.61.
[6]	P. Embrechets, C. Klüppelberg and T. Mikosch, Modelling Extremal Events for Insurance and Finance, Springer, Berlin, 1997. doi: 10.1007/978-3-642-33483-2.
[7]	T. Hirai, H. Masuyama, S. Kasahara and Y. Takahashi, Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing, Journal of Industrial and Management Optimization, 10 (2014), 113-129. doi: 10.3934/jimo.2014.10.113.
[8]	W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical Recipes in C, 2nd edition, Cambridge University Press, 1992.
[9]	S. Resnick, Extreme Values, Regular Variation and Point Processes, Springer Series in Operations Research and Financial Engineering. Springer, New York, 2008.
[10]	T. White, Hadoop: The Definitive Guide, 2nd edition, O'reilly Media, California, 2008.
[11]	K. Wolter, Stochastic Models for Fault Tolerance: Restart, Rejuvenation, and Checkpointing, With a foreword by Aad van Moorsel. Springer, Heidelberg, 2010. doi: 10.1007/978-3-642-11257-7.

show all references

References:

[1]	S. Ali, B. Eslamnour and Z. Shah, A case for on-machine load balancing, Journal of Parallel and Distributed Computing, 71 (2011), 556-564. doi: 10.1016/j.jpdc.2010.11.003.
[2]	L. A. Barroso and U. Hölzle, The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines, Morgan & Claypool, 2009. doi: 10.2200/S00193ED1V01Y200905CAC006.
[3]	W. Cirne, D. Paranhos, F. Brasileiro and L. F. W. Góes, On the efficacy, efficiency and emergent behavior of task replication in large distributed systems, Parallel Computing, 33 (2007), 213-234. doi: 10.1016/j.parco.2007.01.002.
[4]	J. Dean and S. Ghemawat, MapReduce: Simplified data processing on large clusters, Communications of the ACM, 51 (2008), 107-113. doi: 10.1145/1327452.1327492.
[5]	M. Dobber, R. V. D. Mei and G. Koole, Dynamic load balancing and job replication in a global-scale grid environment: A comparison, IEEE Transactions on Parallel and Distributed Systems, 20 (2009), 207-218. doi: 10.1109/TPDS.2008.61.
[6]	P. Embrechets, C. Klüppelberg and T. Mikosch, Modelling Extremal Events for Insurance and Finance, Springer, Berlin, 1997. doi: 10.1007/978-3-642-33483-2.
[7]	T. Hirai, H. Masuyama, S. Kasahara and Y. Takahashi, Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing, Journal of Industrial and Management Optimization, 10 (2014), 113-129. doi: 10.3934/jimo.2014.10.113.
[8]	W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical Recipes in C, 2nd edition, Cambridge University Press, 1992.
[9]	S. Resnick, Extreme Values, Regular Variation and Point Processes, Springer Series in Operations Research and Financial Engineering. Springer, New York, 2008.
[10]	T. White, Hadoop: The Definitive Guide, 2nd edition, O'reilly Media, California, 2008.
[11]	K. Wolter, Stochastic Models for Fault Tolerance: Restart, Rejuvenation, and Checkpointing, With a foreword by Aad van Moorsel. Springer, Heidelberg, 2010. doi: 10.1007/978-3-642-11257-7.

[1]	Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing. Journal of Industrial and Management Optimization, 2014, 10 (1) : 113-129. doi: 10.3934/jimo.2014.10.113
[2]	Shunfu Jin, Haixing Wu, Wuyi Yue, Yutaka Takahashi. Performance evaluation and Nash equilibrium of a cloud architecture with a sleeping mechanism and an enrollment service. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2407-2424. doi: 10.3934/jimo.2019060
[3]	Maxim Sølund Kirsebom. Extreme value theory for random walks on homogeneous spaces. Discrete and Continuous Dynamical Systems, 2014, 34 (11) : 4689-4717. doi: 10.3934/dcds.2014.34.4689
[4]	Serap Ergün, Bariş Bülent Kırlar, Sırma Zeynep Alparslan Gök, Gerhard-Wilhelm Weber. An application of crypto cloud computing in social networks by cooperative game theory. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1927-1941. doi: 10.3934/jimo.2019036
[5]	Xuena Yan, Shunfu Jin, Wuyi Yue, Yutaka Takahashi. Performance analysis and system optimization of an energy-saving mechanism in cloud computing with correlated traffic. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021106
[6]	Yannan Chen, Jingya Chang. A trust region algorithm for computing extreme eigenvalues of tensors. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 475-485. doi: 10.3934/naco.2020046
[7]	Zhanqiang Huo, Wuyi Yue, Naishuo Tian, Shunfu Jin. Performance evaluation for the sleep mode in the IEEE 802.16e based on a queueing model with close-down time and multiple vacations. Journal of Industrial and Management Optimization, 2009, 5 (3) : 511-524. doi: 10.3934/jimo.2009.5.511
[8]	Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance optimization of parallel-distributed processing with checkpointing for cloud environment. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1423-1442. doi: 10.3934/jimo.2018014
[9]	Jinsong Xu. Reversible hidden data access algorithm in cloud computing environment. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1219-1232. doi: 10.3934/dcdss.2019084
[10]	Weidong Bao, Haoran Ji, Xiaomin Zhu, Ji Wang, Wenhua Xiao, Jianhong Wu. ACO-based solution for computation offloading in mobile cloud computing. Big Data & Information Analytics, 2016, 1 (1) : 1-13. doi: 10.3934/bdia.2016.1.1
[11]	Shunfu Jin, Wuyi Yue, Zhanqiang Huo. Performance evaluation for connection oriented service in the next generation Internet. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 749-761. doi: 10.3934/naco.2011.1.749
[12]	Shunfu Jin, Wuyi Yue, Chao Meng, Zsolt Saffer. A novel active DRX mechanism in LTE technology and its performance evaluation. Journal of Industrial and Management Optimization, 2015, 11 (3) : 849-866. doi: 10.3934/jimo.2015.11.849
[13]	Keiji Tatsumi, Masashi Akao, Ryo Kawachi, Tetsuzo Tanino. Performance evaluation of multiobjective multiclass support vector machines maximizing geometric margins. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 151-169. doi: 10.3934/naco.2011.1.151
[14]	Tuan Phung-Duc, Wouter Rogiest, Sabine Wittevrongel. Single server retrial queues with speed scaling: Analysis and performance evaluation. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1927-1943. doi: 10.3934/jimo.2017025
[15]	Maria José Pacifico, Fan Yang. Hitting times distribution and extreme value laws for semi-flows. Discrete and Continuous Dynamical Systems, 2017, 37 (11) : 5861-5881. doi: 10.3934/dcds.2017255
[16]	Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097
[17]	Shunfu Jin, Wuyi Yue. Performance analysis and evaluation for power saving class type III in IEEE 802.16e network. Journal of Industrial and Management Optimization, 2010, 6 (3) : 691-708. doi: 10.3934/jimo.2010.6.691
[18]	Omer Faruk Yilmaz, Mehmet Bulent Durmusoglu. A performance comparison and evaluation of metaheuristics for a batch scheduling problem in a multi-hybrid cell manufacturing system with skilled workforce assignment. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1219-1249. doi: 10.3934/jimo.2018007
[19]	Yuan Zhao, Wuyi Yue. Performance evaluation and optimization of cognitive radio networks with adjustable access control for multiple secondary users. Journal of Industrial and Management Optimization, 2019, 15 (1) : 1-14. doi: 10.3934/jimo.2018029
[20]	Zhanyou Ma, Wenbo Wang, Linmin Hu. Performance evaluation and analysis of a discrete queue system with multiple working vacations and non-preemptive priority. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1135-1148. doi: 10.3934/jimo.2018196

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Kyosuke Hashimoto Hiroyuki Masuyama Shoji Kasahara Yutaka Takahashi
on Google Scholar
Kyosuke Hashimoto Hiroyuki Masuyama Shoji Kasahara Yutaka Takahashi

[Back to Top]