Collaborative learning-based inter-dependent task dispatching and co-location in an integrated edge computing system^☆

Abstract

Recently, several edge deployment types, such as on-premise edge clusters, Unmanned Aerial Vehicles (UAV)-attached edge devices, telecommunication base stations installed with edge clusters, etc., are being deployed to enable faster response time for latency-sensitive tasks. One fundamental problem is where and how to offload and schedule multi-dependent tasks so as to minimize their collective execution time and to achieve high resource utilization. Existing approaches randomly dispatch tasks naively to available edge nodes without considering the resource demands of tasks, inter-dependencies of tasks and edge resource availability. These approaches can result in the longer waiting time for tasks due to insufficient resource availability or dependency support, as well as provider lock-in. Therefore, we present EdgeColla, which is based on the integration of edge resources running across multi-edge deployments. EdgeColla leverages learning techniques to intelligently dispatch multi-dependent tasks, and a variant bin-packing optimization method to co-locate these tasks firmly on available nodes to optimally utilize them. Extensive experiments on real-world datasets from Alibaba on task dependencies show that our approach can achieve optimal performance than the baseline schemes.

Keywords

Edge computing / Collaborative learning / Resource utilization / Execution time / Edge federation / Gang scheduling

References

[1] U. Bokhari Mohammad, Q. Makki, Y.K. Tamandani, A survey on cloud computing, in: V. B. Aggarwal, V. Bhatnagar, K. Mishra, Eds.), Durgesh (Big Data Analytics, Springer, Singapore, 2018, pp. 149-164.

[2] U. Awada, J. Zhang, Edge federation: a dependency-aware multi-task dispatching and co-location in federated edge container-instances, in: 2020 IEEE International Conference on Edge Computing (EDGE), IEEE, 2020, pp. 91-98.

[3] H. Guo, J. Liu, Uav-enhanced intelligent offloading for Internet of things at the edge, IEEE Trans. Ind. Inform. 16 (4) (2020) 2737-2746.

[4] Z. Yu, Y. Gong, S. Gong, Y. Guo, Joint task offloading and resource allocation in uav-enabled mobile edge computing, IEEE Int. Things J. 7(4) (2020) 3147-3159.

[5] X. Cao, G. Tang, D. Guo, Y. Li, W. Zhang, Edge federation: towards an integrated service provisioning model, IEEE/ACM Trans. Netw. 28 (3) (2020) 1116-1129.

[6] U. Awada, J. Zhang, S. Chen, S. Li, Air-to-air collaborative learning: a multi-task orchestration in federated aerial computing, in: 2021 IEEE 14th International Con-ference on Cloud Computing (CLOUD), IEEE, 2021, pp. 671-680.

[7] U. Awada, J. Zhang, S. Chen, S. Li, Airedge: a dependency-aware multi-task or-chestration in federated aerial computing, IEEE Trans. Veh. Technol. 71 (1) (2022) 805-819.

[8] G. Faraci, C. Grasso, G. Schembra, Fog in the clouds: UAVs to provide edge comput-ing to iot devices, ACM Trans. Internet Technol. 20 (3) (2020) 1-26.

[9] J. Ren, H. Wang, T. Hou, S. Zheng, C. Tang, Federated learning-based computation offloading optimization in edge computing-supported Internet of things, IEEE Access 7 (2019) 69194-69201.

[10] R. Yu, P. Li, Toward resource-efficient federated learning in mobile edge computing, IEEE Netw. 35 (1) (2021) 148-155.

[11] Q. Wu, K. He, X. Chen, Personalized federated learning for intelligent iot applica-tions: a cloud-edge based framework, IEEE Open Journal of the Computer Society 1 (2020) 35-44.

[12] R. Urgaonkar, S. Wang, T. He, M. Zafer, K. Chan, K.K. Leung, Dynamic service mi-gration and workload scheduling in edge-clouds, Perform. Eval. 91 (2015) 205-228.

[13] L. Tong, Y. Li, W. Gao,A hierarchical edge cloud architecture for mobile comput-ing, in: IEEE INFOCOM 2016 -The 35th Annual IEEE International Conference on Computer Communications, IEEE, 2016, pp. 1-9.

[14] Z. Han, H. Tan, S.H.-C. Jiang, X. Fu, W. Cao, F.C. Lau,Scheduling placement-sensitive bsp jobs with inaccurate execution time estimation, in: IEEE INFOCOM 2020 - IEEE Conference on Computer Communications, IEEE, 2020, pp. 1053-1062.

[15] C. Anderson, Docker [software engineering], IEEE Softw. 32 (3) (2015) 102-c3.

[16] Q. Ren, K. Liu, L. Zhang, Multi-objective optimization for task offloading based on network calculus in fog environments, Digital Communications and Networks 8( 5)(2022) 825-833.

[17] U. Awada, A. Barker, Resource efficiency in container-instance clusters, in: Proceed-ings of the Second International Conference on Internet of Things, Data and Cloud Computing, ACM, 2017, pp. 1-5.

[18] U. Awada, A. Barker, Improving resource efficiency of container-instance clusters on clouds, in: Proceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, IEEE, 2017, pp. 929-934.

[19] R. Grandl, G. Ananthanarayanan, S. Kandula, S. Rao, A. Akella, Multi-resource pack-ing for cluster schedulers, in: Proceedings of the 2014 ACM Conference on SIG-COMM, ACM, 2014, pp. 455-466.

[20] Z. Hu, J. Tu, B. Li, Spear: Optimized dependency-aware task scheduling with deep reinforcement learning, in: 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), IEEE, 2019, pp. 2037-2046.

[21] R. Grandl, S. Kandula, S. Rao, A. Akella, J. Kulkarni, Graphene: packing and dependency-aware scheduling for data-parallel clusters,in:Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, USENIX As-sociation, USA, 2016, pp. 81-97.

[22] T.-P. Pham, J.J. Durillo, T. Fahringer, Predicting workflow task execution time in the cloud using a two-stage machine learning approach, IEEE Trans. Cloud Comput. 8(1) (2020) 256-268.

[23] F. Nadeem, D. Alghazzawi, A. Mashat, K. Faqeeh, A. Almalaise, Using machine learning ensemble methods to predict execution time of e-science workflows in het-erogeneous distributed systems, IEEE Access 7 (2019) 25138-25149.

[24] M.H. Hilman, M.A. Rodriguez, R. Buyya, Task runtime prediction in scientific work-flows using an online incremental learning approach, in: 2018 IEEE/ACM 11th Inter-national Conference on Utility and Cloud Computing (UCC), IEEE, 2018, pp. 93-102.

[25] W. Xiao, R. Bhardwaj, R. Ramjee, M. Sivathanu, N. Kwatra, Z. Han, P. Patel, X. Peng, H. Zhao, Q. Zhang, F. Yang, L. Zhou, Gandiva: introspective cluster scheduling for deep learning,in:Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation, USENIX Association, USA, 2018, pp. 595-610.

[26] S. Venkataraman, Z. Yang, M. Franklin, B. Recht, I. Stoica, Ernest: Efficient per-formance prediction for large-scale advanced analytics,in:Proceedings of the 13th Usenix Conference on Networked Systems Design and Implementation, USENIX As-sociation, 2016, pp. 363-378.

[27] Y. Peng, Y. Bao, Y. Chen, C. Wu, C. Guo, Optimus: an efficient dynamic resource scheduler for deep learning clusters, in: Proceedings of the Thirteenth EuroSys Con-ference, ACM, 2018, pp. 1-14.

[28] C. Delimitrou, C. Kozyrakis, Quasar: resource-efficient and qos-aware cluster man-agement, SIGPLAN Not. 49 (4) (2014) 127-144.

[29] Z. Guo, K. Yu, N. Kumar, W. Wei, S. Mumtaz, M. Guizani, Deep-distributed-learning-based poi recommendation under mobile-edge networks, IEEE Int. Things J. 10 (1)(2023) 303-317.

[30] R.-A. Cherrueau, A. Lebre, D. Pertin, F. Wuhib, J.M. Soares, Edge computing resource management system: a critical building block! Initiating the debate via OpenStack,in:USENIX Workshop on Hot Topics in Edge Computing (HotEdge 18), USENIX Association, 2018.

[31] V.S. Marco, B. Taylor, B. Porter, Z. Wang, Improving spark application throughput via memory aware task co-location: a mixture of experts approach,in:Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference, ACM, 2017, pp. 95-108.

[32] Y. Li, D. Sun, B.C. Lee, Dynamic colocation policies with reinforcement learning, ACM Trans. Archit. Code Optim. 17 (1) (2020) 1-25.

[33] C. Shu, Z. Zhao, Y. Han, G. Min, H. Duan, Multi-user offloading for edge computing networks: a dependency-aware and latency-optimal approach, IEEE Int. Things J. 7(3) (2020) 1678-1689.

[34] J. Liu, H. Shen, Dependency-aware and resource-efficient scheduling for heteroge-neous jobs in clouds, in: 2016 IEEE International Conference on Cloud Computing Technology and Science (CloudCom), IEEE, 2016, pp. 110-117.

[35] J. Lee, H. Ko, J. Kim, S. Pack, Data: dependency-aware task allocation scheme in distributed edge clouds, IEEE Trans. Ind. Inform. 16 (12) (2020) 7782-7790.

[36] Y. Liu, S. Wang, Q. Zhao, S. Du, A. Zhou, X. Ma, F. Yang, Dependency-aware task scheduling in vehicular edge computing, IEEE Int. Things J. 7(6) (2020) 4961-4971.

[37] Z. Ji, L. Chen, N. Zhao, Y. Chen, G. Wei, F.R. Yu, Computation offloading for edge-assisted federated learning, IEEE Trans. Veh. Technol. 70 (9) (2021) 9330-9344.

[38] J. Konečný, H.B. McMahan, F.X. Yu, P. Richtarik, A.T. Suresh, D. Bacon, Federated learning: strategies for improving communication efficiency,in:NIPS Workshop on Private Multi-Party Machine Learning, Curran Associates, Inc., 2016, pp. 5-10.

[39] Y. Chen, X. Sun, Y. Jin, Communication-efficient federated deep learning with layer-wise asynchronous model update and temporally weighted aggregation, IEEE Trans. Neural Netw. Learn. Syst. 31 (10) (2020) 4229-4238.

[40] Z. Chen, W. Liao, K. Hua, C. Lu, W. Yu, Towards asynchronous federated learn-ing for heterogeneous edge-powered Internet of things, Digital Communications and Networks 7( 3) (2021) 317-326.

[41] Y. Li, T. Wang, Y. Wu, W. Jia, Optimal dynamic spectrum allocation-assisted latency minimization for multiuser mobile edge computing, Digital Communications and Networks 8( 3) (2022) 247-256.

[42] U. Awada, J. Zhang, S. Chen, S. Li, S. Yang, Edgedrones: co-scheduling of drones for multi-location aerial computing missions, J. Netw. Comput. Appl. 215 (2023) 103632.

[43] H. Tan, Z. Han, X.-Y. Li, F.C. Lau,Online job dispatching and scheduling in edge-clouds, in: IEEE INFOCOM 2017 - IEEE Conference on Computer Communications, IEEE, 2017, pp. 1-9.

[44] S. Rampersaud, D. Grosu, Sharing-aware online virtual machine packing in heteroge-neous resource clouds, IEEE Trans. Parallel Distrib. Syst. 28 (7) (2017) 2046-2059.

[45] J. Guo, Z. Chang, S. Wang, H. Ding, Y. Feng, L. Mao, Y. Bao, Who limits the re-source efficiency of my datacenter: an analysis of alibaba datacenter traces, in: 2019 IEEE/ACM 27th International Symposium on Quality of Service (IWQoS), IEEE, 2019, pp. 1-10.

[46] H. Wu, W. Zhang, Y. Xu, H. Xiang, T. Huang, H. Ding, Z. Zhang, Aladdin: opti-mized maximum flow management for shared production clusters, in: 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2019, pp. 696-707.

[47] F. Li, B. Hu, Deepjs: job scheduling based on deep reinforcement learning in cloud data center,in:Proceedings of the 2019 4th International Conference on Big Data and Computing, ACM, 2019, pp. 48-53.

[48] U. Awada, J. Zhang, S. Chen, S. Li, S. Yang, Resource-aware multi-task offloading and dependency-aware scheduling for integrated edge-enabled iov, J. Syst. Archit. 141 (2023) 102923.

[49] W. Huang, Z. Zeng, N.N. Xiong, S. Mumtaz, Joet: sustainable vehicle-assisted edge computing for iot devices, J. Syst. Archit. 131 (2022) 102686.