Cost-Effective Task Scheduling for Collaborative Cross-Edge Analytics

doi:10.12142/ZTECOM.202102003

ZTE Communications ›› 2021, Vol. 19 ›› Issue (2): 11-19.DOI: 10.12142/ZTECOM.202102003

• Special Topic • Previous Articles Next Articles

Cost-Effective Task Scheduling for Collaborative Cross-Edge Analytics

ZHAO Kongyange¹, GAO Bin², ZHOU Zhi¹()

^1.Sun Yat-sen University, Guangzhou 510275, China
^2.National University of Singapore, Singapore 119077, Singapore

Received:2021-04-09 Online:2021-06-25 Published:2021-07-27
About author:ZHAO Kongyange received the B.E. degree from the South China University of Technology, China in 2020. He is currently pursuing his master’s degree in Sun Yat-sen University, China. His research interests include edge computing, edge intelligence, and serverless computing.|GAO Bin is now a research assistant of School of Computing in National University of Singapore (NUS). Before this, he received the master’s degree and bachelor’s degree from Huazhong University of Science and Technology (HUST), China in 2017 and 2020, respectively. His research interests include operation system, mobile edge computing, cloud computing, and geo-distributed data analytics.|ZHOU Zhi (zhouzhi9@mail.sysu.edu.cn) received the B.S., M.E., and Ph.D. degrees in 2012, 2014, and 2017, respectively, all from the School of Computer Science and Technology at Huazhong University of Science and Technology (HUST), China. He is currently an associate professor in the School of Computer Science and Engineering at Sun Yat-sen University, China. In 2016, he was a visiting scholar at University of Goettingen, Germany. He was nominated for the 2019 CCF Outstanding Doctoral Dissertation Award, the sole recipient of the 2018 ACM Wuhan & Hubei Computer Society Doctoral Dissertation Award, and a recipient of the Best Paper Award of IEEE UIC 2018. His research interests include edge computing, cloud computing, and distributed systems.
Supported by:
the National Natural Science Foundation of China(61802449);the Guangdong Natural Science Funds(2021A1515011912)

Abstract

Abstract:

Collaborative cross-edge analytics is a new computing paradigm in which Internet of Things (IoT) data analytics is performed across multiple geographically dispersed edge clouds. Existing work on collaborative cross-edge analytics mostly focuses on reducing either analytics response time or wide-area network (WAN) traffic volume. In this work, we empirically demonstrate that reducing either analytics response time or network traffic volume does not necessarily minimize the WAN traffic cost, due to the price heterogeneity of WAN links. To explicitly leverage the price heterogeneity for WAN cost minimization, we propose to schedule analytic tasks based on both price and bandwidth heterogeneities. Unfortunately, the problem of WAN cost minimization underperformance constraint is shown non-deterministic polynomial (NP)-hard and thus computationally intractable for large inputs. To address this challenge, we propose price- and performance-aware geo-distributed analytics (PPGA) , an efficient task scheduling heuristic that improves the cost-efficiency of IoT data analytic jobs across edge datacenters. We implement PPGA based on Apache Spark and conduct extensive experiments on Amazon EC2 to verify the efficacy of PPGA.

Key words: collaborative cross-edge analytics, Internet of Things, task scheduling

ZHAO Kongyange, GAO Bin, ZHOU Zhi. Cost-Effective Task Scheduling for Collaborative Cross-Edge Analytics[J]. ZTE Communications, 2021, 19(2): 11-19.

Figures/Tables 8

Figure 1 Illustration of collaborative cross-edge analytics

Table 1 Price heterogeneity (in US dollar per GB) of outgoing WAN bandwidth usage at different regions of Amazon EC2

Location	Price
Frankfurt	0.02
Iceland	0.02
London	0.02
Northern California	0.02
Northern Virginia	0.02
Ontario	0.02
Oregon	0.02
Tokyo	0.02
Mumbai	0.086
Seoul	0.09
Singapore	0.09
Sydney	0.09
Sao Paulo	0.16

Figure 2 Usage price of outgoing WAN bandwidth versus the average outgoing WAN bandwidth of 5 Amazon EC2 regions

Table 2 Pair-wise bandwidth (in Mbit/s) between 5 different EC2 regions

City	Singapore	Oregon	Sydney	Sao Paulo	Mumbai
Singapore	46 028.8	116	140	63.5	390
Oregon	123	46 284.8	137	110	100
Sydney	144	124	46 592	69.0	106
Sao Paulo	66.6	109	74.5	46 899.2	79.3
Mumbai	390	103	106	73.7	46 694.4

Table 3 Price (in US dollar per GB) of outgoing WAN bandwidth usage

City	Singapore	Oregon	Sydney	Sao Paulo	Mumbai
Price	0.09	0.02	0.14	0.16	0.086

Figure 3 Data transfer costs of WordCount， PageRank and TeraSort

Figure 4 WordCount, PageRank and TeraSort’s shuffle bandwidth usage across datacenters

Figure 5 Application completion times of WordCount, PageRank and TeraSort

References 13

1	ANANTHANARAYANAN G, BAHL P, BODÍK P, et al. Real⁃time video analytics: the killer App for edge computing [J]. Computer, 2017, 50(10): 58–67. DOI: 10.1109/MC.2017.3641638 DOI
2	JAIN S, ZHANG X, ZHOU Y H, et al. Spatula: Efficient cross⁃camera video analytics on large camera networks [C]//2020 IEEE/ACM Symposium on Edge Computing (SEC). San Jose, USA: IEEE, 2020: 110–124. DOI: 10.1109/SEC50012.2020.00016 DOI
3	JIANG J C, ANANTHANARAYANAN G, BODIK P, et al. Chameleon: scalable adaptation of video analytics [C]//2018 Conference of the ACM Special Interest Group on Data Communication. Budapest, Hungary: ACM, 2018: 253–266. DOI: 10.1145/3230543.3230574 DOI
4	ZHOU Z, CHEN X, LI E, et al. Edge intelligence: paving the last mile of artificial intelligence with edge computing [J]. Proceedings of the IEEE, 2019, 107(8): 1738–1762. DOI: 10.1109/JPROC.2019.2918951 DOI
5	JIN H, JIA L, ZHOU Z. Boosting edge intelligence with collaborative cross⁃edge analytics [J]. IEEE Internet of Things journal, 2021, 8(4): 2444–2458. DOI: 10.1109/JIOT.2020.3034891 DOI
6	PU Q F, ANANTHANARAYANAN G, BODIK P, et al. Low latency geo⁃distributed data analytics [C]//Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. London, United Kingdom: ACM, 2015: 421–434. DOI: 10.1145/2785956.2787505 DOI
7	KLOUDAS K, MAMEDE M, PREGUIÇA N, et al. Pixida [J]. Proceedings of the VLDB endowment, 2015, 9(2): 72–83. DOI: 10.14778/2850578.2850582 DOI
8	VULIMIRI A, CURINO C, GODFREY PB, et al. Global analytics in the face of bandwidth and regulatory constraints [C]//The 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI). Oakland, USA: USENIX, 2015:323–336. DOI: 10.1109/TST.2016.7442496 DOI
9	MAO H Z, SCHWARZKOPF M, VENKATAKRISHNAN S B, et al. Learning scheduling algorithms for data processing clusters [C]//The ACM Special Interest Group on Data Communication. Beijing, China: ACM, 2019: 270–288. DOI: 10.1145/3341302.3342080 DOI
10	HU Z M, LI B C, LUO J. Flutter: Scheduling tasks closer to data across geo⁃distributed datacenters [C]//The 35th Annual IEEE International Conference on Computer Communications. San Francisco, USA: IEEE, 2016: 1–9. DOI: 10.1109/INFOCOM.2016.7524469 DOI
11	PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: bringing order to the Web. Technical report [R]. 1919
12	O’MALLEY O. Terabyte sort on apache Hadoop [EB/OL]. [2021⁃01⁃04].
13	RABKIN A, ARYE M, SEN S, et al. Aggregation and degradation in JetStream: streaming analytics in the wide area [C]//Usenix Conference on Networked Systems Design & Implementation. Seattle, USA: USENIX Association, 2014

[1]	ZHOU Yiheng, ZENG Wei, ZHENG Qingfang, LIU Zhilong, CHEN Jianping. A Survey on Task Scheduling of CPU-GPU Heterogeneous Cluster [J]. ZTE Communications, 2024, 22(3): 83-90.
[2]	CUI Ziqi, WANG Gongpu, WANG Zhigang, AI Bo, XIAO Huahua. Symbiotic Radio Systems: Detection and Performance Analysis [J]. ZTE Communications, 2022, 20(3): 93-98.
[3]	YANG Bo, MITANI Tomohiko, SHINOHARA Naoki, ZHANG Huaiqing. High-Power Simultaneous Wireless Information and Power Transfer: Injection-Locked Magnetron Technology [J]. ZTE Communications, 2022, 20(2): 3-12.
[4]	TAN Jie, SHA Xiubin, DAI Bo, LU Ting. Analysis of Industrial Internet of Things and Digital Twins [J]. ZTE Communications, 2021, 19(2): 53-60.
[5]	LIANG Junrui, LI Xin, YANG Hailiang. Kinetic Energy Harvesting Toward Battery-Free IoT: Fundamentals, Co-Design Necessity and Prospects [J]. ZTE Communications, 2021, 19(1): 48-60.
[6]	ZHANG Gengxin, DING Xiaojin, QU Zhicheng. Space‑Terrestrial Integrated Architecture for Internet of Things [J]. ZTE Communications, 2020, 18(4): 3-9.
[7]	FU Shousai, ZHANG Hesheng, CHEN Jinghe. Time Sensitive Networking Technology Overview and Performance Analysis [J]. ZTE Communications, 2018, 16(4): 57-64.
[8]	Mahyar Shirvanimoghaddam, Sarah J. Johnson. Multiple Access Technologies for Cellular M 2M Communications [J]. ZTE Communications, 2016, 14(4): 42-49.
[9]	Christian Jacquenet, Mohamed Boucadair. A Software-Defined Approach to IoT Networking [J]. ZTE Communications, 2016, 14(1): 61-68.
[10]	Somayya Madakam, Ramaswamy Ramachandran. Barcelona Smart City: The Heaven on Earth (Internet of Things: Technological God) [J]. ZTE Communications, 2015, 13(4): 3-9.
[11]	Didier El Baz, Julien Bourgeois. Smart Cities in Europe and the ALMA Logistics Project [J]. ZTE Communications, 2015, 13(4): 10-15.
[12]	Jie Li, Eitan Altman, Corinne Touati. A General SDN-Based IoT Framework with NVF Implementation [J]. ZTE Communications, 2015, 13(3): 42-45.
[13]	Xuemeng Li, Yongyi Wang, Fan Shi, Wenchao Jia. Crawler for Nodes in the Internet of Things [J]. ZTE Communications, 2015, 13(3): 46-50.
[14]	Fuji Ren, Yu Gu. Using Artificial Intelligence in the Internet of Things [J]. ZTE Communications, 2015, 13(2): 1-2.
[15]	Yixin Zhong. I²oT: Advanced Direction of the Internet of Things [J]. ZTE Communications, 2015, 13(2): 3-6.

Cost-Effective Task Scheduling for Collaborative Cross-Edge Analytics

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 13

Related Articles 15

Recommended Articles

Metrics