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

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

Abstrakti

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.

AlkuperäiskieliEnglanti
OtsikkoMobiHoc 2020 - Proceedings of the 2020 International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
KustantajaAssociation for Computing Machinery (ACM)
Sivut101-110
Sivumäärä10
ISBN (elektroninen)9781450380157
DOI - pysyväislinkit
TilaJulkaistu - 11 lokakuuta 2020
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaACM International Symposium on Mobile Ad Hoc Networking and Computing - Virtual, Online, Yhdysvallat
Kesto: 11 lokakuuta 202014 lokakuuta 2020
Konferenssinumero: 21

Julkaisusarja

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

Conference

ConferenceACM International Symposium on Mobile Ad Hoc Networking and Computing
LyhennettäMobiHoc
MaaYhdysvallat
KaupunkiVirtual, Online
Ajanjakso11/10/202014/10/2020

Sormenjälki Sukella tutkimusaiheisiin 'Online dispatching and scheduling of jobs with heterogeneous utilities in edge computing'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä