Online job dispatching and scheduling in edge-clouds

TLDR

Edge‑cloud computing places servers near mobile devices to offload jobs with low latency, but the critical challenge is dispatching and scheduling jobs to minimize their response time. The study aims to minimize the total weighted response time of jobs offloaded to edge servers. The authors formulate a general model with arbitrary job arrivals, upload/download delays, and latency‑sensitive weights, and design the OnDisc algorithm that operates in a speed‑augmentation framework. OnDisc achieves (1+ε)-speed O(1/ε)-competitiveness, is easily deployable in distributed systems, and simulation on a Google data trace shows a dramatic reduction in weighted response time compared with heuristic baselines.

Abstract

In edge-cloud computing, a set of edge servers are deployed near the mobile devices such that these devices can offload jobs to the servers with low latency. One fundamental and critical problem in edge-cloud systems is how to dispatch and schedule the jobs so that the job response time (defined as the interval between the release of a job and the arrival of the computation result at its device) is minimized. In this paper, we propose a general model for this problem, where the jobs are generated in arbitrary order and times at the mobile devices and offloaded to servers with both upload and download delays. Our goal is to minimize the total weighted response time over all the jobs. The weight is set based on how latency sensitive the job is. We derive the first online job dispatching and scheduling algorithm in edge-clouds, called OnDisc, which is scalable in the speed augmentation model; that is, OnDisc is (1 + ε)-speed O(1/ε)-competitive for any constant ε ϵ (0,1). Moreover, OnDisc can be easily implemented in distributed systems. Extensive simulations on a real-world data-trace from Google show that OnDisc can reduce the total weighted response time dramatically compared with heuristic algorithms.