Online Shuffling with Task Duplication in Cloud

doi:10.3969/j.issn.1673-5188.2017.04.005

ZTE Communications ›› 2017, Vol. 15 ›› Issue (4): 38-42.DOI: 10.3969/j.issn.1673-5188.2017.04.005

收稿日期:2017-06-23 出版日期:2017-10-25 发布日期:2019-12-02

Online Shuffling with Task Duplication in Cloud

ZANG Qimeng¹, GUO Song²

^1. School of Computer Science and Engineering, The University of Aizu, Aizu-Wakamatsu 965-0006, Japan
^2. Department of Computing, The Hong Kong Polytechnic University, Hong Kong SAR 852, China

Received:2017-06-23 Online:2017-10-25 Published:2019-12-02
About author:ZANG Qimeng (zangqm.uoa@gmail.com) is a graduate student in the department of Computer Science and Engineering, The University of Aizu, Japan. His research interests mainly include big data, cloud computing and RFID system.|GUO Song (song.guo@polyu.edu.hk) received his Ph.D. in computer science from University of Ottawa, Canada. He is currently a full professor at Department of Computing, The Hong Kong Polytechnic University (PolyU), China. Prior to joining PolyU, he was a full professor with The University of Aizu, Japan. His research interests are mainly in the areas of cloud and green computing, big data, wireless networks, and cyber-physical systems. He has published over 300 conference and journal papers in these areas and received multiple best paper awards from IEEE/ACM conferences. His research has been sponsored by JSPS, JST, MIC, NSF, NSFC, and industrial companies. Dr. GUO has served as an editor of several journals, including IEEE TPDS, IEEE TETC, IEEE TGCN, IEEE Communications Magazine, and Wireless Networks. He has been actively participating in international conferences serving as general chairs and TPC chairs. He is a senior member of IEEE, a senior member of ACM, and an IEEE Communications Society Distinguished Lecturer.

摘要/Abstract

Abstract:

Task duplication has been widely adopted to mitigate the impact of stragglers that run much longer than normal tasks. However, task duplication on data pipelining case would generate excessive traffic over the datacenter networks. In this paper, we study minimizing the traffic cost for data pipelining task replications and design a controller that chooses the data generated by the first finished task and discards data generated later by other replications belonging to the same task. Each task replication communicates with the controller when it finishes a data processing, which causes additional network overhead. Hence, we try to reduce the network overhead and make a trade-off between the delay of data block and the network overhead. Finally, extensive simulation results demonstrate that our proposal can minimize network traffic cost under data pipelining case.

Key words: cloud computing, big data, shuffling, task duplication, traffic

. [J]. ZTE Communications, 2017, 15(4): 38-42.

ZANG Qimeng, GUO Song. Online Shuffling with Task Duplication in Cloud[J]. ZTE Communications, 2017, 15(4): 38-42.

图/表 7

Figure 1. The MapReduce model.

Figure 2. Non-overlapping data block transmitting.

Table 1 Symbols and variables

Notations	Description
M	A set of machines to generate intermediate data
R	A set of machines to receive intermediate data
$v x$	Data volume of an intermediate record produced by machine x
$c xy$	The traffic cost from machine x ∈ M to machine y ∈ R
$c c$	The cost caused by communication with the controller
$c t i$	The total cost of transmitting group i
$c d i$	The delay cost of group i
$d xy$	The distance between two machines x and y

Table 1 Symbols and variables

Notations	Description
M	A set of machines to generate intermediate data
R	A set of machines to receive intermediate data
$v x$	Data volume of an intermediate record produced by machine x
$c xy$	The traffic cost from machine x ∈ M to machine y ∈ R
$c c$	The cost caused by communication with the controller
$c t i$	The total cost of transmitting group i
$c d i$	The delay cost of group i
$d xy$	The distance between two machines x and y

Figure 3. Total cost vs. the number of key-value pairs.

Figure 4. Total cost vs. the number of tasks.

Figure 5. Total cost vs. the number of task duplications.

Figure 6. Total cost vs. weight of delay.

参考文献 14

[1]	S. Zou, X. Wen, K. Chen , et al., “Virtualknotter: online virtual machine shuffling for congestion resolving in virtualized datacenter,” Computer Networks, vol. 67, pp. 141-153, 2014. doi: 10.1109/ICDCS.2012.25.
[2]	G. Ananthanarayanan, A. Ghodsi, S. Shenker, I. Stoica , “Effective straggler mitigation: attack of the clones,” in 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI’13), Lombard,USA, 2013, pp. 185-198.
[3]	G. Ananthanarayanan, M. C.-C Hung, X. Ren ., et al., “Grass: trimming stragglers in approximation analytics,” in 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI’14), Seattle,USA, 2014, pp. 289-302.
[4]	C.-Y Hong, S. Kandula, R. Mahajan , et al., “Achieving high utilization with software-driven WAN,” in SIGCOMM’13, Hong Kong, China, 2013, pp. 15-26. doi: 10.1145/2534169.2486012.
[5]	J. Dean and S. Ghemawat , “MapReduce: simplified data processing on large clusters,” in Proc. 6th USENIX Symposium on Operating Systems Design and Implementation (OSDI’04), San Francisco, USA, 2004, vol. 6, pp. 10-10.
[6]	The Apache Software Foundation. (2017, Mar. 29). Apache Hadoop [Online]. Available:
[7]	T. Condie, N. Conway, P. Alvaro , et al., “Mapreduce online,” in Proc.7th USENIX Conference on Networked Systems Design and Implementation (NSDI’10), San Jose,USA, 2010, pp. 21-21.
[8]	G. D. Ghare and S. T. Leutenegger , “Improving speed up and response times by replicating parallel programs on a snow,” in 11th International Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP), Cambridge, USA, 2005, pp. 264-287.
[9]	M. Zaharia, A. Konwinski, A. D. Joseph, R. Katz, I. Stoica , “Improving MapReduce performance in heterogeneous environments,” in Proc. 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI’08), San Diego, USA, 2008, pp. 29-42.
[10]	M. Isard, M. Budiu, Y. Yu, A. Birrell, D. Fetterly , “Dryad: distributed data-parallel programs from sequential building blocks,” in Proc. 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems, Lisbon,Portugal, 2007, pp. 59-72. doi: 10.1145/1272996.1273005.
[11]	G. Ananthanarayanan, S. Kandula, A. Greenberg , et al., “Reining in the outliers in map- reduce clusters using mantri,” in Proc. 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI’10), Vancouver, Canada, 2010, pp. 265-278.
[12]	A. Baratloo, M. Karaul, Z. M. Kedem, P. Wijckoff , “Char- lotte: metacomputing on the Web,” Future Generation Computer Systems, vol. 15, no.5-6, pp. 559-570, 1999.
[13]	M. C. Rinard and P. C. Diniz , “Commutativity analysis: A new analysis framework for parallelizing compilers,” in Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Philadelphia,USA, 1996, pp. 54-67.
[14]	Q. Zang, H. Y. Chan, P. Li, S. Guo , “Software-defined data shuffling for big data jobs with task duplication,” in 45th International Conference on Parallel Processing Workshops (ICPPW), Philadelphia, USA, 2016, pp. 403-407. doi: 10.1109/ICPPW.2016.62.

Online Shuffling with Task Duplication in Cloud

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 14

相关文章 0

编辑推荐

Metrics