DAG Scheduling In Edge Computing

With the rapid development of the loT and Al,the number and computation needs of various end devices have increased dramatically,and computation-intensive applica-tions such as autonomous driving and VR are increasingly latency-sensitive.The long propagation delay of massive data,limited Internet bandwidth,and unstable networking environment makes the traditional cloud computing hard to meet the QoS requirements of those applications.As an essential supplement to cloud computing,edge comput-ing is proposed to deploy relatively small-scale edge servers at the edge of the Internet,which can cooperate with the remote cloud to provide low-latency,high-bandwidth,and high-performance computing services.However,compared with the remote cloud,each edge server is relatively constrained in computation and storage,so that it can only configure a subset of the functions at the same time to execute corresponding tasks.Meanwhile,complex applications usually consist of a set of dependent functions.Each request for some application can be modeled as a directed acyclic graph(DAG),where each node represents a task that needs to execute a specific function,and the di-rected edges represent precedence constraints between tasks.In the edge system,when an application request arrives online,we need to place and schedule its tasks onto edge servers or the remote cloud to meet its deadline as much as possible.Before execut-ing,all tasks must satisfy their precedence constraints and configure the corresponding function on-demand on the servers assigned.Therefore,we here investigate the DAG scheduling problem in the realistic sce-nario above,and our objective is to meet as many application request deadlines as pos-sible.The main work of this thesis is summarized as follows:·For the single application scheduling problem,we derive an algorithm to find the optimal task placement and scheduling efficiently for the special case when the configuration on each edge server is fixed.When the on-demand function configuration is allowed,we propose a novel approximation algorithm,named GenDoc,and analyze its additive error from the optimal solution theoretically.·For the multiple applications scheduling online problem,we propose a novel on-line algorithm,named OnDoc,based on list scheduling methodologies.More-over,it is efficient and easy to deploy in practice.By maintaining multiple task scheduling lists and improving the resource utilization of servers,OnDoc makes more requests completed before their deadlines.·Extensive simulations on the data-trace from Alibaba demonstrate that GenDoc and OnDoc outperform their baselines and perform well consistently on various settings of critical parameters,respectively.Specifically,compared with baseline algorithms,GenDoc reduces the average completion time by at least 24%(and up to 54%).And the number of requests satisfying their deadline by OnDoc can be at least 1.9x that of the baselines.