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

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

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

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.
Citation: Kyosuke Hashimoto, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of backup-task scheduling with deadline time in cloud computing. Journal of Industrial & 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. 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. 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. 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. doi: 10.1109/TPDS.2008.61.

[6]

P. Embrechets, C. Klüppelberg and T. Mikosch, Modelling Extremal Events for Insurance and Finance,, Springer, (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. 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, (1992).

[9]

S. Resnick, Extreme Values, Regular Variation and Point Processes,, Springer Series in Operations Research and Financial Engineering. Springer, (2008).

[10]

T. White, Hadoop: The Definitive Guide,, 2nd edition, (2008).

[11]

K. Wolter, Stochastic Models for Fault Tolerance: Restart, Rejuvenation, and Checkpointing,, With a foreword by Aad van Moorsel. Springer, (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. 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. 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. 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. doi: 10.1109/TPDS.2008.61.

[6]

P. Embrechets, C. Klüppelberg and T. Mikosch, Modelling Extremal Events for Insurance and Finance,, Springer, (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. 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, (1992).

[9]

S. Resnick, Extreme Values, Regular Variation and Point Processes,, Springer Series in Operations Research and Financial Engineering. Springer, (2008).

[10]

T. White, Hadoop: The Definitive Guide,, 2nd edition, (2008).

[11]

K. Wolter, Stochastic Models for Fault Tolerance: Restart, Rejuvenation, and Checkpointing,, With a foreword by Aad van Moorsel. Springer, (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 & Management Optimization, 2014, 10 (1) : 113-129. doi: 10.3934/jimo.2014.10.113

[2]

Maxim Sølund Kirsebom. Extreme value theory for random walks on homogeneous spaces. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4689-4717. doi: 10.3934/dcds.2014.34.4689

[3]

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 & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019036

[4]

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 & Management Optimization, 2009, 5 (3) : 511-524. doi: 10.3934/jimo.2009.5.511

[5]

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

[6]

Jinsong Xu. Reversible hidden data access algorithm in cloud computing environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1219-1232. doi: 10.3934/dcdss.2019084

[7]

Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance optimization of parallel-distributed processing with checkpointing for cloud environment. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1423-1442. doi: 10.3934/jimo.2018014

[8]

Shunfu Jin, Wuyi Yue, Zhanqiang Huo. Performance evaluation for connection oriented service in the next generation Internet. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 749-761. doi: 10.3934/naco.2011.1.749

[9]

Shunfu Jin, Wuyi Yue, Chao Meng, Zsolt Saffer. A novel active DRX mechanism in LTE technology and its performance evaluation. Journal of Industrial & Management Optimization, 2015, 11 (3) : 849-866. doi: 10.3934/jimo.2015.11.849

[10]

Keiji Tatsumi, Masashi Akao, Ryo Kawachi, Tetsuzo Tanino. Performance evaluation of multiobjective multiclass support vector machines maximizing geometric margins. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 151-169. doi: 10.3934/naco.2011.1.151

[11]

Tuan Phung-Duc, Wouter Rogiest, Sabine Wittevrongel. Single server retrial queues with speed scaling: Analysis and performance evaluation. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1927-1943. doi: 10.3934/jimo.2017025

[12]

Maria José Pacifico, Fan Yang. Hitting times distribution and extreme value laws for semi-flows. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5861-5881. doi: 10.3934/dcds.2017255

[13]

Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097

[14]

Shunfu Jin, Wuyi Yue. Performance analysis and evaluation for power saving class type III in IEEE 802.16e network. Journal of Industrial & Management Optimization, 2010, 6 (3) : 691-708. doi: 10.3934/jimo.2010.6.691

[15]

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 & Management Optimization, 2018, 14 (3) : 1219-1249. doi: 10.3934/jimo.2018007

[16]

Shunfu Jin, Wuyi Yue, Xuena Yan. Performance evaluation of a power saving mechanism in IEEE 802.16 wireless MANs with bi-directional traffic. Journal of Industrial & Management Optimization, 2011, 7 (3) : 717-733. doi: 10.3934/jimo.2011.7.717

[17]

Yuan Zhao, Wuyi Yue. Performance evaluation and optimization of cognitive radio networks with adjustable access control for multiple secondary users. Journal of Industrial & Management Optimization, 2019, 15 (1) : 1-14. doi: 10.3934/jimo.2018029

[18]

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 & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2018196

[19]

Jianping Liu, Shunfu Jin. An imperfect sensing-based channel reservation strategy in CRNs and its performance evaluation. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-21. doi: 10.3934/jimo.2018197

[20]

Stéphane Chrétien, Sébastien Darses, Christophe Guyeux, Paul Clarkson. On the pinning controllability of complex networks using perturbation theory of extreme singular values. application to synchronisation in power grids. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 289-299. doi: 10.3934/naco.2017019

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (14)
  • HTML views (0)
  • Cited by (0)

[Back to Top]