Online DAG Scheduling with On-Demand Function Configuration in Edge Computing

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.