DAG Scheduling in Mobile Edge Computing

In Mobile Edge Computing, edge servers have limited storage and computing resources which can only support a small number of functions. Meanwhile, mobile applications are becoming more complex, consisting of multiple dependent tasks, modeled as a Directed Acyclic Graph (DAG). When a request arrives, typically in an online manner with a deadline specified, we need to configure the servers and assign the dependent tasks for efficient processing. This work jointly considers the problem of dependent task placement and scheduling with on-demand function configuration on edge servers, aiming to meet as many deadlines as possible. For a single request, when the configuration on each edge server is fixed, we derive

to find the optimal task placement and scheduling. When the on-demand function configuration is allowed, we propose , a novel approximation algorithm, and analyze its additive error from the optimal theoretically. For multiple requests, we derive , an online algorithm easy to deploy in practice. Our extensive experiments show that  outperforms state-of-the-art baselines in processing 86.14% of these unique applications, and reduces their average completion time by at least 24% . The number of deadlines that can satisfy is at least 1.9 × of that of the baselines.