Algorithm

Real-time computing

Scheduling (production processes)

Operating system

Telecommunications

Economics

Scalability

Computer science

Mathematical optimization

Distributed computing

Computer network

Latency (audio)

Task (project management)

Upper and lower bounds

Testbed

Mathematics

Management

Enhanced Data Rates for GSM Evolution

Processor scheduling

Mathematical analysis

Online algorithm

Operations management

Artificial intelligence

Edge computing

Competitive analysis

Resource (disambiguation)

IEEE Transactions on Parallel and Distributed Systems

In this article, we study online deadline-aware task dispatching and scheduling in edge computing. We jointly considerthe management of the networking and computing resources to meet the maximum number of deadlines. We propose an online algorithm, named Dedas, which greedily schedules newly arriving tasks and considers whether to replace some existing tasks in order to make the new deadlines satisfied. We derive a non-trivial competitive ratio of Dedas theoretically, and our analysis is asymptotically tight. Besides, we implement a distributed approximation D - Dedas with a better scalability and less than 10 percent performance loss compared with the centralized algorithm Dedas. We then build DeEdge, an edge computing testbed installed with typical latency-sensitive applications such as IoT sensor monitoring and face matching. We adopt a real-world data trace from the Google cluster for large-scale emulations. Extensive testbed experiments and simulations demonstrate that the deadline miss ratio of Dedas is stable for online tasks, which is reduced by up to 60 percent compared with state-of-the-art methods. Moreover, Dedas performs well in minimizing the average task completion time.

Online Deadline-Aware Task Dispatching and Scheduling in Edge Computing