Online Approximation Scheme for Scheduling Heterogeneous Utility Jobs in Edge Computing
Chi Zhang, Haisheng Tan, Haoqiang Huang, Zhenhua Han, Shaofeng H.-C. Jiang, Guopeng Li, Xiang‐Yang Li · IEEE/ACM Transactions on Networking · 2022
Edge computing systems typically handle a wide variety of applications that exhibit diverse degrees of sensitivity to job latency. Therefore, a multitude of utility functions of the job response time need to be considered by the underlying job dispatching and scheduling mechanism. Nonetheless, previous studies in edge computing mainly focused on optimizing a single utility function across all jobs, e.g., linear, sigmoid, or the hard deadline. In this paper, we design online job dispatching and scheduling strategies in which different jobs can be categorized by different non-increasing utility functions. Our goal is to maximize the total utility of all scheduled jobs. We first prove that no online deterministic algorithm could achieve a competitive ratio better than the lower bound$\Omega \left({\frac {1}{\sqrt {\epsilon }}}\right)$under the$(1+\epsilon)$-speed augmentation model. We proceed to propose an online algorithm, named asO4A, for handling jobs with heterogeneous utilities. We prove thatO4Ais$O\left({\frac {1}{\epsilon ^{2}}}\right)$-competitive. We also design its distributed version, i.e.,DO4A. We implementO4AandDO4Aon an edge computing testbed running deep learning inference jobs. With the production trace from Google Cluster, our experimental and large-scale simulation results indicate thatO4Acan increase the total utility by up to 50% compared with state-of-the-art methods. Besides, the performance loss ofDO4Ais only 2% compared withO4Awith a small communication overhead involved. Moreover, both of our algorithms are robust to estimation errors in job processing time and transmission delay.