Online dispatching and scheduling of jobs with heterogeneous utilities in edge computing

Chi Zhang, Haisheng Tan*, Haoqiang Huang, Zhenhua Han, Shaofeng H.C. Jiang, Nikolaos Freris, Xiang Yang Li

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

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 works in edge computing mainly focused on either one kind of utility function (e.g., linear, sigmoid, or the hard deadline) or different kinds of utilities separately. In this paper, we investigate online job dispatching and scheduling strategies under the setting of coexistence of heterogeneous utilities, i.e., various coexisting jobs can employ different non-increasing utility functions. The goal is to maximize the total utility over all jobs in an edge system. Besides heterogeneous utilities, we here adopt a practical online model where the unrelated machine model and the upload and download delay are considered. We proceed to propose an online algorithm, O4A, to dispatch and schedule jobs with heterogeneous utilities. Our theoretical analysis shows that O4A is O(1/?2)-competitive under the (1 + ?)-speed augmentation model, where ? is a small positive constant. We implement O4A 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 39.42% compared with state-of-the-art utility-agnostic methods. Moreover, O4A is robust to estimation errors in job processing time and transmission delay.

Original languageEnglish
Title of host publicationMobiHoc 2020 - Proceedings of the 2020 International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
PublisherAssociation for Computing Machinery (ACM)
Pages101-110
Number of pages10
ISBN (Electronic)9781450380157
DOIs
Publication statusPublished - 11 Oct 2020
MoE publication typeA4 Article in a conference publication
EventACM International Symposium on Mobile Ad Hoc Networking and Computing - Virtual, Online, United States
Duration: 11 Oct 202014 Oct 2020
Conference number: 21

Publication series

NameProceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)

Conference

ConferenceACM International Symposium on Mobile Ad Hoc Networking and Computing
Abbreviated titleMobiHoc
Country/TerritoryUnited States
CityVirtual, Online
Period11/10/202014/10/2020

Keywords

  • edge computing
  • heterogeneous utility function
  • job scheduling
  • online approximation

Fingerprint

Dive into the research topics of 'Online dispatching and scheduling of jobs with heterogeneous utilities in edge computing'. Together they form a unique fingerprint.

Cite this