Resource Optimization In Cloud-Edge Collaborative Computing

Nowadays,various interactive application services based on cloud data centers have become an indispensable part of people’s daily life and the whole society.Edge computing provides users with high-bandwidth,low-latency,and high-security services by deploying computing and storage resources at the edge of the network close to mobile devices,effectively expanding the coverage of cloud computing.Since the resources of edge servers are usually limited,it is necessary to design mechanisms to allocate resources,and leverage cloud-edge collaboration to enhance the capabilities of edge devices to better meet the growing user requirements.However,the computing resources,storage resources and network resources are usually unevenly distributed in cloud-edge collaborative systems,users’ requests arrive online,and the optimization goals,resource usages,and patterns of different requests can be different,which poses many challenges to the design of resource allocation and scheduling algorithms in cloud-edge collaborative systems.Focusing on several key issues of resource optimization in cloud-edge collaboration,this paper systematically studies job scheduling,file caching,and complex flow transmission problem in cloud-edge collaboration scenario.Reasonable job scheduling and file caching strategies can reduce redundant transmission in the system.File caching strategies can optimize the collection of edge servers that can process requests in job scheduling.And data flow transmission strategies can reduce the network bottleneck and further improve the overall operating efficiency of the cloud-edge collaboration system,thereby reducing the response time of requests of jobs and files.This paper proposes a series of algorithms with theoretical performance guarantees to efficiently utilize the computing,storage and network resources scattered in the system,and improve the effectiveness and reliability of the cloud-edge collaborative system.The specific research works of this paper are as follows:(1)Job scheduling in cloud-edge collaborative 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.Previous studies in edge computing mainly focused on optimizing a single utility function across all jobs,e.g.,linear,sigmoid,or the hard deadline.This paper proposes online job dispatching and scheduling strategies in which different jobs can be categorized by different utility functions and the goal is to maximize the total utility of all scheduled jobs.This paper first proves that no online deterministic algorithm could achieve a competitive ratio better than the lower bound(?)under the(1+ε)-speed augmentation model.Then,this paper proposes an online algorithm,named as O4A,for handling jobs with heterogeneous utilities and proves that O4A is O(1/ε2)-competitive.This paper implements O4A on an edge computing testbed running deep learning inference jobs.With the production trace from Google Cluster,the 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 its distributed version is only 2%compared with the original O4A with a small communication overhead involved.(2)File caching in cloud-edge collaborative computing.In latency-sensitive file caching systems such as Mobile Edge Computing(MEC),the latency of fetching a missing file to the local cache can be significant.Recent studies have revealed that successive requests of the same missing file before the fetching completes could still suffer latency(so-called delayed hits).This paper studies the online general file caching problem with delayed hits and bypassing,i.e.,a request may be bypassed and processed directly at the remote data center.The objective is to minimize the total request latency.This paper first gives the lower bounds Ω(ZK)and Ω(Z log K)of any deterministic and randomized online algorithms,respectively,where Z is the maximum fetching latency of any file and K is the cache size.Then this paper shows a general reduction that turns a traditional file caching algorithm to one that can handle delayed hits,which can be proved with competitive ratio O(Z3/2K)and O(Z3/2 log K)for the deterministic and randomized version,respectively.Extensive simulations based on the production data trace from Google and the Yahoo benchmark illustrate that CaLa can reduce the latency by up to 9.42%compared with the state-of-the-art method dealing with delayed hits,and this reduction increases to 32.01%if bypassing is allowed.(3)Complex flow transmission in cloud-edge collaborative computing.During the process of job scheduling and file storage management in cloud-edge collaboration,a large number of complex data flows will be generated in the network.Due to the special semantics of the application layer,some data flows may share the same optimization goal.Therefore,in order to improve the data efficiency of the application layer,it is necessary to transmit flows through a higher perspective,that is so-called coflow scheduling.A coflow is defined as a collection of parallel data flows that share the same optimization goal.As the gathering place of computing resources in the cloud-edge collaborative system,there are a large number of coflows in the data center.This paper investigates coflow scheduling in data centers,and derives a novel operation called regularization that can be efficiently implemented and reduce the circuit reconfiguration frequency of optical circuit switch(OCS)and coflow completion time(CCT)dramatically.This paper first proposes a 2-approximation algorithm,called Reco-Sin,for single coflow scheduling.For multiple coflows,this paper derives two algorithms RecoMul and Reco-Mul+,which can transform any non-preemptive multi-coflow scheduling in packet switches to a scheduling scheme in OCS.Reco-Mul can achieve a constant approximation under the assumption that no tiny flows will be transmitted in OCS,and Reco-Mul+has an approximation ratio of O(M)with no assumption.Here,M is the total number of coflows.Extensive simulations based on Facebook data traces show that single coflow can be finished 97%faster with Reco-Sin when the transmission matrices are dense,and the performance improvement of Reco-Mul and Reco-Mul+are at least 46%and 100%,respectively.