Abstract
Modern applications in mobile computing become increasingly complex and computation intensive. Task offloading from mobile devices to the cloud is more and more frequent. Edge Computing, deploying relatively small-scale edge servers close to users, is a promising cloud computing paradigm to reduce the network communication delay. Due to the limited capability, each edge server can be configured with only a small amount of functions to run corresponding tasks. Moreover, a mobile application might consist of multiple dependent tasks, which can be modeled and scheduled as Directed Acyclic Graphs (DAGs). When an application request arrives online, typically with a deadline specified, we need to configure the edge servers and assign the dependent tasks for processing. In this work, we jointly tackle on-demand function configuration on edge servers and DAG scheduling to meet as many request deadlines as possible. Based on list scheduling methodologies, we propose a novel online algorithm, named OnDoc, which is efficient and easy to deploy in practice. Extensive simulations on the data trace from Alibaba (including more than 3 million application requests) demonstrate that OnDoc outperforms state-of-the-art baselines consistently on various experiment settings.
The first two authors have equal contribution.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Chun, B.G., Ihm, S., Maniatis, P., Naik, M., Patti, A.: Clonecloud: elastic execution between mobile device and cloud. In: ACM Proceedings of the Sixth Conference on Computer Systems, pp. 301–314 (2011)
Zhao, Y., Liu, X., Qiao, C.: Job scheduling for acceleration systems in cloud computing. In: IEEE ICC, pp. 1–6 (2018)
Satyanarayanan, M., Bahl, P., Caceres, R., Davies, N.: The case for VM-based cloudlets in mobile computing. IEEE Pervasive Comput. 4, 14–23 (2009)
Garcia Lopez, P., Montresor, A., Epema, D., Datta, A., Higashino, T., Iamnitchi, A., et al.: Edge-centric computing: vision and challenges. ACM SIGCOMM CCR 45(5), 37–42 (2015)
Tan, H., Han, Z., Li, X.Y., Lau, F.C.: Online job dispatching and scheduling in edge-clouds. In: IEEE INFOCOM, pp. 1–9 (2017)
Topcuoglu, H., Hariri, S., Wu, M.: Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE TPDS 13(3), 260–274 (2002)
Neto, J.L.D., Yu, S.Y., Macedo, D.F., Nogueira, M.S., Langar, R., Secci, S.: ULOOF: a user level online offloading framework for mobile edge computing. IEEE TMC 17(11), 2660–2674 (2018)
Sundar, S., Liang, B.: Offloading dependent tasks with communication delay and deadline constraint. In: IEEE INFOCOM, pp. 37–45 (2018)
Zhang, W., Wen, Y., Wu, D.O.: Energy-efficient scheduling policy for collaborative execution in mobile cloud computing. In: IEEE INFOCOM, pp. 190–194 (2013)
Guo, H., Liu, J., Zhang, J.: Efficient computation offloading for multi-access edge computing in 5G HetNets. In: IEEE ICC, pp. 1–6 (2018)
Palis, M.A., Liou, J.C., Wei, D.S.L.: Task clustering and scheduling for distributed memory parallel architectures. IEEE TPDS 7(1), 46–55 (1996)
Darbha, S., Agrawal, D.P.: Optimal scheduling algorithm for distributed-memory machines. IEEE TPDS 9(1), 87–95 (1998)
Sakellariou, R., Zhao, H.: A hybrid heuristic for DAG scheduling on heterogeneous systems. In: IEEE IPDPS, pp. 111 (2004)
Deng, M., Tian, H., Fan, B.: Fine-granularity based application offloading policy in cloud-enhanced small cell networks. In: IEEE ICC, pp. 638–643 (2016)
He, K., Meng, X., Pan, Z., Yuan, L., Zhou, P.: A novel task-duplication based clustering algorithm for heterogeneous computing environments. IEEE TPDS 30(1), 2–14 (2019)
Shin, K., Cha, M., Jang, M., Jung, J., Yoon, W., Choi, S.: Task scheduling algorithm using minimized duplications in homogeneous systems. Elsevier JPDC 68(8), 1146–1156 (2008)
Liu, G.Q., Poh, K.L., Xie, M.: Iterative list scheduling for heterogeneous computing. Elsevier JPDC 65(5), 654–665 (2005)
Ali, J., Khan, R.Z.: Optimal task partitioning model in distributed heterogeneous parallel computing environment. AIRCC Int. J. Adv. Inf. Technol. 2(6), 13 (2012)
He, K., Zhao, Y.: A new task duplication based multitask scheduling method. In: IEEE Grid and Cooperative Computing(GCC), pp. 221–227 (2006)
Azure Functions. https://azure.microsoft.com/en-us/services/functions
Alibaba trace (2018). https://github.com/alibaba/clusterdata
Acknowledgments
This work is supported partly by the National Key R&D Program of China 2018YFB0803400, China National Funds for Distinguished Young Scientists No. 61625205, NSFC Grants 61772489, 61751211, Key Research Program of Frontier Sciences (CAS) No. QYZDY-SSW-JSC002, NSF ECCS-1247944, NSF CNS 1526638, and the Fundamental Research Funds for the Central U.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Liu, L., Huang, H., Tan, H., Cao, W., Yang, P., Li, XY. (2019). Online DAG Scheduling with On-Demand Function Configuration in Edge Computing. In: Biagioni, E., Zheng, Y., Cheng, S. (eds) Wireless Algorithms, Systems, and Applications. WASA 2019. Lecture Notes in Computer Science(), vol 11604. Springer, Cham. https://doi.org/10.1007/978-3-030-23597-0_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-23597-0_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-23596-3
Online ISBN: 978-3-030-23597-0
eBook Packages: Computer ScienceComputer Science (R0)