Dependent task placement and scheduling with function configuration in edge computing

Liuyan Liu, Haisheng Tan, Shaofeng H.C. Jiang, Zhenhua Han, Xiang Yang Li, Hong Huang

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

8 Citations (Scopus)

Abstract

In Mobile Edge Computing (MEC), each edge server can be configured with only a small number of functions due to the limited capacity of various resources. Meanwhile, mobile applications become more complicated, consisting of multiple dependent tasks which are typically modeled as a Directed Acyclic Graph (DAG). In edge computing, when an application arrives, we need to place and schedule its tasks onto edge servers and/or the remote cloud, where the functions to execute the tasks are configured. In this work, we jointly consider the problem of dependent task placement and scheduling with on-demand function configuration on servers. Our objective is to minimize the application completion time. Specifically, for the special case when the configuration on each edge server is fixed, we derive an algorithm to find the optimal task placement and scheduling efficiently. When the on-demand function configuration is allowed, we propose a novel approximation algorithm, named GenDoc, and analyze theoretically its additive error from the optimal solution. Our extensive experiments on the cluster trace from Alibaba (including 20365 unique applications with DAG information) show that GenDoc outperforms state-ofthe- art baselines in processing 86.14% of these unique applications, and reduces their average completion time by at least 24% (and up to 54%). Moreover, GenDoc consistently performs well on various settings of key parameters.

Original languageEnglish
Title of host publicationProceedings of the International Symposium on Quality of Service, IWQoS 2019
PublisherACM
ISBN (Electronic)9781450367783
DOIs
Publication statusPublished - 24 Jun 2019
MoE publication typeA4 Article in a conference publication
EventInternational Workshop on Quality of Service - Phoenix, United States
Duration: 24 Jun 201925 Jun 2019

Publication series

NameProceedings of the International Symposium on Quality of Service, IWQoS 2019

Workshop

WorkshopInternational Workshop on Quality of Service
Abbreviated titleIWQoS
CountryUnited States
CityPhoenix
Period24/06/201925/06/2019

Keywords

  • Edge Computing
  • Function Configuration
  • Task Scheduling

Fingerprint

Dive into the research topics of 'Dependent task placement and scheduling with function configuration in edge computing'. Together they form a unique fingerprint.

Cite this