Online Approximation Scheme for Scheduling Heterogeneous Utility Jobs in Edge Computing

作     者：Zhang, Chi Tan, Haisheng Huang, Haoqiang Han, Zhenhua Jiang, Shaofeng H-C Li, Guopeng Li, Xiang-Yang 

作者机构：Univ Sci & Technol China LINKE Lab Hefei 230027 Peoples R China Univ Sci & Technol China CAS Key Lab Wireless Opt Commun Hefei 230027 Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China Microsoft Res Asia MSRA Shanghai 200232 Peoples R China Peking Univ Ctr Frontiers Comp Studies Beijing 100871 Peoples R China 

出 版 物：《IEEE-ACM TRANSACTIONS ON NETWORKING》 (IEEE ACM Trans Networking)

年 卷 期：2023年第31卷第1期

页      面：352-365页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Key Research and Development Program of China [2018YFB0803400] NSFC Key Research Program of Frontier Sciences (CAS) [QYZDYSSW-JSC002] Fundamental Research Funds for the Central Universities at China Peking University 

主　　题：Approximation algorithms scheduling edge computing 

摘      要：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(1/root epsilon) under the (1 + epsilon)-speed augmentation model. We proceed to propose an online algorithm, named as O4A, for handling jobs with heterogeneous utilities. We prove that O4A is O(1/epsilon(2))-competitive. We also design its distributed version, i.e., DO4A. We implement O4A and DO4A on an edge computing testbed running deep learning inference jobs. With the production trace from Google Cluster, our experimental and large-scale simulation results indicate that O4A can increase the total utility by up to 50% compared with state-of-the-art methods. Besides, the performance loss of DO4A is only 2% com pared with O4A with a small communication overhead involved. Moreover, both of our algorithms are robust to estimation errors in job processing time and transmission delay.