A Novel Hybrid Model for Task Dependent Scheduling in Container-based Edge Computing Tingting Lu*,Fanping Zeng*,Guozhu Chen*,Wenjuan Shu*,Jingfei Shen*and Weikang Zhang* *School of Computer Science and Technology.University of Science and Technology of China,Hefei,Anhui,China 120c TAnhui Province Key Lab of Software in Computing and Communication,Hefei,Anhui,PR China ftingtlu,chengz18,shuwj.ericjeff,buttman@mail.ustc.edu.cn,billzeng@ustc.edu.cn 330085 Abstract-In traditional edge computing,the task from the configured in the edge server.That is to say,if a task is planned Internet of Things (IoT)is usually offloaded to edge server.It on an edge server that has no corresponding container,the will be uploaded to the remote cloud if the edge server cannot server can configure the container which is downloaded from process it.A task can be processed on the server,only if the server has configured the corresponding function program.However, the remote cloud.After the container has been configured,their each edge server can only configure a small number of functions server can process the task.Therefore,it is a key challenge to due to the limited computing,storage,and bandwidth resources. design a task scheduling algorithm that considers the container Moreover,modern tasks from IoT devices become more and more configuration in EC. diverse,which are also accompanied by complex dependencies Second,the application (also called a job)from IoT de- 3331 It increases the processing time overhead to the task processed in remote cloud due to huge transmission delay.In this paper,we vice consists of some tasks that have complex dependencies design a container-based edge computing system,where a task each of which needs a suitable container.Specifically,the can be executed on a server only if the server has configured the communication among servers will occur between dependent corresponding container,if not the server can fetch it from other 10000.1/0001007820-1-86 tasks when they are allocated on different servers respectively. edge servers or remote cloud.Based on the system,we propose a Furthermore,because of the dependency relationship,the start novel hybrid model,called CBASGA,with the aim to minimize the job complete time,which combines Chaos-based Beetle time of task will be limited by its direct predecessors.In other Antennae Search and Genetic Algorithm.Our experimental words,a task can only be executed after all of its direct prede- results show that the designed system reduces the average job cessors have been completed.So how to deal with the complex completion time by 4.2%compared with the comparison system, inter-task dependency is another challenge in EC.There have and CBASGA reduces the average job completion time by at been many researches on task scheduling and related server least 21.7%compared with baselines. Index Terms-Task scheduling,Container configuration,Edge configuration (e.g.,[6,71).But they consider either scheduling computing the whole job individually [7,8]or configuring the related (sdo servers independently [9]. I.INTRODUCTION In this paper,we first propose a container-based edge system in which containers can be transferred between edge servers. Edge computing (EC)provides resource services (e.g.,com- The edge servers have limited resources and each server puting,storage,bandwidth,etc)to nearby users by deploying has a different performance.We then propose an efficient small servers (called edge server)in the edge of the network approximation algorithm,named CBASGA.The algorithm [1].Nearby users can offload their tasks or jobs to edge combines Chaos-based Beetle Antennae Search (CBAS)and server for processing,so that the data transmission time can Genetic Algorithm (GA)in addition to heuristic initialization be greatly reduced. to optimize the tradeoff between task dependency and con- Due to that the application pre-configured by the developer tainer configuration.Finally,we adopt a cluster trace from in edge server is limited,the edge server can only process a Alibaba to evaluate CBASGA.The simulation results show few tasks.It can not take full advantage of edge computing. that the designed system is efficient to process dependent tasks So some scholars have proposed containerizing the applica- and CBASGA has excellent performance. tions required for IoT devices,which can be automatically The remainder of the paper is organized as follows.Section obtained from the cloud when there is no corresponding II expounds our edge system model.The task scheduling containerized application for processing task[2].Furthermore, and correlation allocation algorithms are shown in section III. Martin Fowler and James Lewis jointly propose the concept Section IV presents the performance evaluation for CBASGA. of microservices and define a microservice as a small service We conclude this paper in section V. composed of a single application,which can be deployed, II.SYSTEM MODEL AND PROBLEM FORMULATION scaled,and tested independently [3].Many works have applied the idea of microservices to edge computing [4,5].But there A.Edge System Model are still many challenges in applying microservices to EC. The edge system consists of K heterogeneous edge servers First,the storage and computing resources of edge services and one remote cloud,denoted as S={so,s1,...,sK,where are limited.Only a few containers (i.e.,microservices)can be so depicts the remote cloud.We use rkas the data transfer 978-1-7281-9441-721/S31.0002021EEE Authorized licensed use limited to:University of Science Technology of China.Downloaded on July 14.2021 at 02:23:40 UTC from IEEE Xplore.Restrictions apply
A Novel Hybrid Model for Task Dependent Scheduling in Container-based Edge Computing Tingting Lu∗, Fanping Zeng∗†, Guozhu Chen∗, Wenjuan Shu∗, Jingfei Shen∗ and Weikang Zhang∗ ∗School of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui, China †Anhui Province Key Lab of Software in Computing and Communication, Hefei, Anhui, PR China {tingtlu, chengz18, shuwj, ericjeff, buttman}@mail.ustc.edu.cn, billzeng@ustc.edu.cn Abstract—In traditional edge computing, the task from the Internet of Things (IoT) is usually offloaded to edge server. It will be uploaded to the remote cloud if the edge server cannot process it. A task can be processed on the server, only if the server has configured the corresponding function program. However, each edge server can only configure a small number of functions due to the limited computing, storage, and bandwidth resources. Moreover, modern tasks from IoT devices become more and more diverse, which are also accompanied by complex dependencies. It increases the processing time overhead to the task processed in remote cloud due to huge transmission delay. In this paper, we design a container-based edge computing system, where a task can be executed on a server only if the server has configured the corresponding container, if not the server can fetch it from other edge servers or remote cloud. Based on the system, we propose a novel hybrid model, called CBASGA, with the aim to minimize the job complete time, which combines Chaos-based Beetle Antennae Search and Genetic Algorithm. Our experimental results show that the designed system reduces the average job completion time by 4.2% compared with the comparison system, and CBASGA reduces the average job completion time by at least 21.7% compared with baselines. Index Terms—Task scheduling, Container configuration, Edge computing I. INTRODUCTION Edge computing (EC) provides resource services (e.g., computing, storage, bandwidth, etc) to nearby users by deploying small servers (called edge server) in the edge of the network [1]. Nearby users can offload their tasks or jobs to edge server for processing, so that the data transmission time can be greatly reduced. Due to that the application pre-configured by the developer in edge server is limited, the edge server can only process a few tasks. It can not take full advantage of edge computing. So some scholars have proposed containerizing the applications required for IoT devices, which can be automatically obtained from the cloud when there is no corresponding containerized application for processing task [2]. Furthermore, Martin Fowler and James Lewis jointly propose the concept of microservices and define a microservice as a small service composed of a single application, which can be deployed, scaled, and tested independently [3]. Many works have applied the idea of microservices to edge computing [4, 5]. But there are still many challenges in applying microservices to EC. First, the storage and computing resources of edge services are limited. Only a few containers (i.e., microservices) can be configured in the edge server. That is to say, if a task is planned on an edge server that has no corresponding container, the server can configure the container which is downloaded from the remote cloud. After the container has been configured, their server can process the task. Therefore, it is a key challenge to design a task scheduling algorithm that considers the container configuration in EC. Second, the application (also called a job) from IoT device consists of some tasks that have complex dependencies, each of which needs a suitable container. Specifically, the communication among servers will occur between dependent tasks when they are allocated on different servers respectively. Furthermore, because of the dependency relationship, the start time of task will be limited by its direct predecessors. In other words, a task can only be executed after all of its direct predecessors have been completed. So how to deal with the complex inter-task dependency is another challenge in EC. There have been many researches on task scheduling and related server configuration (e.g., [6, 7]). But they consider either scheduling the whole job individually [7, 8] or configuring the related servers independently [9]. In this paper, we first propose a container-based edge system in which containers can be transferred between edge servers. The edge servers have limited resources and each server has a different performance. We then propose an efficient approximation algorithm, named CBASGA. The algorithm combines Chaos-based Beetle Antennae Search (CBAS) and Genetic Algorithm (GA) in addition to heuristic initialization to optimize the tradeoff between task dependency and container configuration. Finally, we adopt a cluster trace from Alibaba to evaluate CBASGA. The simulation results show that the designed system is efficient to process dependent tasks and CBASGA has excellent performance. The remainder of the paper is organized as follows. Section II expounds our edge system model. The task scheduling and correlation allocation algorithms are shown in section III. Section IV presents the performance evaluation for CBASGA. We conclude this paper in section V. II. SYSTEM MODEL AND PROBLEM FORMULATION A. Edge System Model The edge system consists of K heterogeneous edge servers and one remote cloud, denoted as S = {s0, s1, ..., sK}, where s0 depicts the remote cloud. We use rk,k as the data transfer 978-1-7281-9441-7/21/$31.00 ©2021 IEEE 2021 IEEE International Conference on Communications Workshops (ICC Workshops) | 978-1-7281-9441-7/20/$31.00 ©2021 IEEE | DOI: 10.1109/ICCWorkshops50388.2021.9473877 Authorized licensed use limited to: University of Science & Technology of China. Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore. Restrictions apply
rate between server sk and s,and assume rk.'=rk'.k. Therefore,the transmission time of w unit data from sk to sk ⊙⊙ Hidden mand Containe (isIf the transmission time is set to. Tasks that is,r.=o,as the communication time between tasks Demand Containe within the server is usually very small. Link betwee Configure from EC Each server has a different maximum number of container configurations simultaneously,which is called Data Transfe the server capacity,denoted as C={co,c1,...,cK},where between Tasks co depicts the maximum number of containers owned by the remote cloud simultaneously,other c;(1,2.....K) represents the maximum number of containers owned by the i-th edge server simultaneously.In particular,when the number of containers configured by a server reaches its maximum,the server can use a policy to free up some of the resources occu- pied by the existing containers to configure the new containers. Fig.1:System Model The policy is the least recently used(LRU)algorithm in our paper. To better illustrate our system model,we present the de- the hidden exit task implies the completion of a job.We model signed edge system in Fig.1.The system consists of three them as directed acyclic graph (DAG),denoted as G(V,E,W). edge servers,each of which is responsible for job requests Here,V={vo,v1,...,J+),each node represents a task.An in its own domain,and one cloud.The capacity of each edge directed link e=indicates that there is a dependency server is set to two,whereas the cloud has all containers.A job between vi and vj,that is,the task vj cannot be processed request consists of two hidden tasks (virtual task created for until task v;has completed.E is the set of all directed links scheduling convenience)and five ordinary tasks(actual task The link weight wj are determined by the amount of data to be processed)are sent to server s2 for execution.After transferred from v:to vj.W is the set of all link weight.The scheduling,two hidden tasks (task 0 and task 6)and two processing time of a task vj on server sk is denoted as pj.k. ordinary tasks (task 2 and task 5)are place on s2,task 1 Considering that redeploying a task can be consuming a lot and 3 are on s3.and task 4 are on s1.Specifically,s2 is not of time,we don't allow a task to preempt the server to avoid configured the container that can process task 5,so it fetches additional processing costs. the corresponding container from edge server s1 which holds the container.Since hidden task 0 and task 2 are on the same C.Container Configuration server which has the container needed for task 2,so task 2 can In this paper,we assume that each type of task has one be executed immediately.As the initial data is sent from s2 to and only one container that can execute it.We define a task s3.s3 can process task 1 after configuring the corresponding container map function,map(),to represent the container container from the cloud.As there is no precedence constraint needed for the task.In other words,if the task vj is processed between task 1 and 2,they can be processed in parallel.After on a server sk.it must have configured the corresponding receiving the outputs of task 2,task 3 and 4 can be executed on container Ti=map(v;).If not,the server has to suffer s1 and s2 respectively.After obtaining the processing results configuration time Ar,.k,which depends largely on the for task 1,3 and 4,s2 can execute task 5 and generate the final container transfer time over the network to fetch the container result to the hidden exit task 6.It is worth noting that the two from surrounding edge server or the cloud s.. tasks with dependencies (such as task 2 and task 3)are not processed on the same server because the scheduler estimates III.ALGORITHM that the two tasks can be completed earlier if performed Before introducing the algorithm,let's explain the encoding separately. method of the scheduling solution.Our encoding solution indicates each task of a job is allocated to which servers.For B.Request and Job example,Fig.2 shows the encoded solution of the tasks of the The job request from the device is first submitted to the job.We take the encoded solution in the upper left corner of nearest edge server,called the local server,and then sent the figure as an example,the value of to and t6 is 1 presents to the edge system.The job consists of a set of dependent the hidden tasks are allocated to local server s1.The value of tasks,denoted as [v,v2,..v).Specifically,the entry task t2 and t is 2 indicates task 2 and 4 are assigned to server s2 is a task without any predecessor task and the exit task is a and so on. task without any successor tasks.In order to facilitate unified The proposed algorithm includes three important parts.The scheduling,we add a hidden entry task (vo)and a hidden first part is a heuristic algorithm for initialization.The second exit task (vJ+1).Let the hidden entry task connect to each part is the automatic gene combination realized by CBAS. actual entry task and the hidden exit task connect to each The third part is CBASGA algorithm which improve GA with actual exit task.It's important to note that the completion of results from the first and second parts Authorized licensed use limited to:University of Science Technology of China.Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore.Restrictions apply
rate between server sk and sk , and assume rk,k = rk ,k. Therefore, the transmission time of ω unit data from sk to sk (k = k ) is ω rk,k . If k = k , the transmission time is set to 0, that is, rk,k = +∞, as the communication time between tasks within the server is usually very small. Each server has a different maximum number of container configurations simultaneously, which is called the server capacity, denoted as C = {c0, c1, ..., cK}, where c0 depicts the maximum number of containers owned by the remote cloud simultaneously, other ci (i = 1, 2, ..., K) represents the maximum number of containers owned by the i-th edge server simultaneously. In particular, when the number of containers configured by a server reaches its maximum, the server can use a policy to free up some of the resources occupied by the existing containers to configure the new containers. The policy is the least recently used (LRU) algorithm in our paper. To better illustrate our system model, we present the designed edge system in Fig. 1. The system consists of three edge servers, each of which is responsible for job requests in its own domain, and one cloud. The capacity of each edge server is set to two, whereas the cloud has all containers. A job request consists of two hidden tasks (virtual task created for scheduling convenience) and five ordinary tasks (actual task to be processed) are sent to server s2 for execution. After scheduling, two hidden tasks (task 0 and task 6) and two ordinary tasks (task 2 and task 5) are place on s2, task 1 and 3 are on s3, and task 4 are on s1. Specifically, s2 is not configured the container that can process task 5, so it fetches the corresponding container from edge server s1 which holds the container. Since hidden task 0 and task 2 are on the same server which has the container needed for task 2, so task 2 can be executed immediately. As the initial data is sent from s2 to s3, s3 can process task 1 after configuring the corresponding container from the cloud. As there is no precedence constraint between task 1 and 2, they can be processed in parallel. After receiving the outputs of task 2, task 3 and 4 can be executed on s1 and s2 respectively. After obtaining the processing results for task 1, 3 and 4, s2 can execute task 5 and generate the final result to the hidden exit task 6. It is worth noting that the two tasks with dependencies (such as task 2 and task 3) are not processed on the same server because the scheduler estimates that the two tasks can be completed earlier if performed separately. B. Request and Job The job request from the device is first submitted to the nearest edge server, called the local server, and then sent to the edge system. The job consists of a set of dependent tasks, denoted as {v1, v2, ..., vJ }. Specifically, the entry task is a task without any predecessor task and the exit task is a task without any successor tasks. In order to facilitate unified scheduling, we add a hidden entry task (v0) and a hidden exit task (vJ+1). Let the hidden entry task connect to each actual entry task and the hidden exit task connect to each actual exit task. It’s important to note that the completion of Internet Job Request 0 1 2 3 4 5 6 2 5 1 4 3 Various Containers 0 6 1 2 3 4 5 Tasks in a Job Links to Access the Internet Data Transfer between Tasks Demand Container Configure from EC 0 6 Hidden Tasks Link between Edge Servers Demand Container Configure from Cloud Cloud Edge Servers Containers configured by Edge/Cloud server s1 s2 s3 Fig. 1: System Model the hidden exit task implies the completion of a job. We model them as directed acyclic graph (DAG), denoted as G(V,E,W). Here, V = {v0, v1, ..., vJ+1}, each node represents a task. An directed link e = indicates that there is a dependency between vi and vj , that is, the task vj cannot be processed until task vi has completed. E is the set of all directed links. The link weight wij are determined by the amount of data transferred from vi to vj . W is the set of all link weight. The processing time of a task vj on server sk is denoted as pj,k. Considering that redeploying a task can be consuming a lot of time, we don’t allow a task to preempt the server to avoid additional processing costs. C. Container Configuration In this paper, we assume that each type of task has one and only one container that can execute it. We define a task container map function, map(·), to represent the container needed for the task. In other words, if the task vj is processed on a server sk, it must have configured the corresponding container τj = map(vj ) . If not, the server has to suffer configuration time ∆τj ,k,x, which depends largely on the container transfer time over the network to fetch the container from surrounding edge server or the cloud sx. III. ALGORITHM Before introducing the algorithm, let’s explain the encoding method of the scheduling solution. Our encoding solution indicates each task of a job is allocated to which servers. For example, Fig. 2 shows the encoded solution of the tasks of the job. We take the encoded solution in the upper left corner of the figure as an example, the value of t0 and t6 is 1 presents the hidden tasks are allocated to local server s1. The value of t2 and t4 is 2 indicates task 2 and 4 are assigned to server s2 and so on. The proposed algorithm includes three important parts. The first part is a heuristic algorithm for initialization. The second part is the automatic gene combination realized by CBAS. The third part is CBASGA algorithm which improve GA with results from the first and second parts. Authorized licensed use limited to: University of Science & Technology of China. Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore. Restrictions apply
A.Initial Task Allocation Algorithm 1 Initial Task Allocation Procedure During the initialization phase,we greedily select the server Input:G(V,E,W),S with configured containers,local for each task,which allows the earliest completion of a task server s among all servers.Specifically,the assigned sever of the Output:initial solution hidden exit (entry)task is the local server in our system.The 1:assume vo,v1,..J+1 are the task precedence of G. details of the initial task allocation are shown in Algorithm 1. 2:F,k=+oo for0≤j≤J+1and0≤k≤K. Specifically,a job G is released to local server s.The two 3:let Fo,:=0. hidden tasks (vo and vJ+1)will be placed and executed on 4:for j=1 to J do s.Before the initialization starts,we need to prioritize the 5: for k=0 to K do tasks.So we first find the longest directed path from the task 6 find Pj,Pj={(vi,sy)vi is a direct predecessor concerned to the exit task,and calculate the sum of the task task of vj,sy is the server to which vi is assigned} processing time and the communication time between tasks on 1 if server sk with container map(vj)then the longest path [10].Then,according to the decreasing order FA=maxe,e马{Eg++P巧} of the calculation result,we can prioritize these tasks (Line 1). 9: else The earliest finish time of task v;on server sk is denoted as 10: findap)ap)ss is the server Fj.k,which is set to +o initially (Line 2).The value of Fo.t with container map(vj)in edge server or cloud). is 0 because task vo is virtual (Line 3).With corresponding 11 Bk=max(e马eew{Bg++ container configuration,for each direct predecessor task v;of P5,k十△map(e)k,2} task vj,the value of Fik is equal or greater than the sum 12: end if of the finish time of v:,the communication time between 13: end for vi and vj and the processing time of vj on sk,where we 14 letu=arg mino:≤k≤KFf,k make Fi.k equal to the aforementioned maximum sum (Line 8).Without corresponding container configuration,we need 15: assign task vj to server s to add additional container configuration time from the server 16:end for with the corresponding container to sk(Line 11).We place 17:F3+1!=max(F) task vj on the server with minimum Fi..after one iteration 18:construct the initial solution from FJ+1. (Line 14-15).With the acquisition of the earliest completion 19:return initial solution time of each task,we end up with FJ+1,which also is the earliest completion time of the job.From this process,we can know where each task is assigned,and then encode it to get where o is the size of the search step:sign()represents a the initial solution. sign function;f)is a function to be optimized.Our goal is to minimize job completion time (i.e.,makespan),so we use B.Chaos-based Beetle Antennae Search Algorithm the reciprocal of the makespan as the function. The original Beetle Antennae Search Algorithm (BAS)[11] 1 algorithm has good optimization performance and convergence f(r）=makespan( (5) in continuous space,but it's not suitable for discrete space.To solve this problem,we discretize the model and then propose With iteration,the step size gradually decreases for a more the Chaos-based Beetle Antennae Search Algorithm.For a job, refined search and the distance vector is adjusted with it,they we first generate a random direction vector(i.e.,a scheduling are shown as follows: solution)in the given system as follows: 6t=h6t-1 (6) b=rndi(K,J) (1) '=6/c (7) where rndi(K,/)represents a function.The function can ran- where h is coefficient of the step size,c is a constant preferably domly generate an /-dimensional vector,each dimension of between 2 to 10. which is an integer value not exceeding K.After obtaining Note that some vectors are operated to be non-integer,such the scheduling solution b.the position of the left-tentacles and as xi and r,in order to make them operate in f,we deal with right-tentacles are defined as below: them as follows: xI=xt-d'b (2) x'=x'mod K (8) Ir =z'+d'b (3)the formula is to convert the non-integer number x'into an where zt is the position after the t-th fly of beetle.dt is the integer number that can indicate server identification. sensing length of antennae.Then,we further generate iterative The details of the CBAS are shown in Algorithm 2.More model which determines the direction and distance of the importantly,the performance of BAS after discretization is beetle at the next time,as follows: poor,so we alleviate it by adding a logistic chaotic map in the first iter/2 iterations (Line 8-12)[12].Specially,the purpose xt=xt-1+86.sign(f()-f(I)) (4) of generating the chaos value from a deterministic nonlinear Authorized licensed use limited to:University of Science Technology of China.Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore.Restrictions apply
A. Initial Task Allocation During the initialization phase, we greedily select the server for each task, which allows the earliest completion of a task among all servers. Specifically, the assigned sever of the hidden exit (entry) task is the local server in our system. The details of the initial task allocation are shown in Algorithm 1. Specifically, a job G is released to local server sl. The two hidden tasks (v0 and vJ+1) will be placed and executed on sl. Before the initialization starts, we need to prioritize the tasks. So we first find the longest directed path from the task concerned to the exit task, and calculate the sum of the task processing time and the communication time between tasks on the longest path [10]. Then, according to the decreasing order of the calculation result, we can prioritize these tasks (Line 1). The earliest finish time of task vj on server sk is denoted as Fj,k, which is set to +∞ initially (Line 2). The value of F0,l is 0 because task v0 is virtual (Line 3). With corresponding container configuration, for each direct predecessor task vi of task vj , the value of Fj,k is equal or greater than the sum of the finish time of vi, the communication time between vi and vj and the processing time of vj on sk, where we make Fj,k equal to the aforementioned maximum sum (Line 8). Without corresponding container configuration, we need to add additional container configuration time from the server with the corresponding container to sk (Line 11). We place task vj on the server with minimum Fj,· after one iteration (Line 14-15). With the acquisition of the earliest completion time of each task, we end up with FJ+1,l, which also is the earliest completion time of the job. From this process, we can know where each task is assigned, and then encode it to get the initial solution. B. Chaos-based Beetle Antennae Search Algorithm The original Beetle Antennae Search Algorithm (BAS) [11] algorithm has good optimization performance and convergence in continuous space, but it’s not suitable for discrete space. To solve this problem, we discretize the model and then propose the Chaos-based Beetle Antennae Search Algorithm. For a job, we first generate a random direction vector (i.e., a scheduling solution) in the given system as follows: b = rndi(K, J) (1) where rndi(K,J) represents a function. The function can randomly generate an J-dimensional vector, each dimension of which is an integer value not exceeding K. After obtaining the scheduling solution b, the position of the left-tentacles and right-tentacles are defined as below: xl = xt − dtb (2) xr = xt + dtb (3) where xt is the position after the t-th fly of beetle. dt is the sensing length of antennae. Then, we further generate iterative model which determines the direction and distance of the beetle at the next time, as follows: xt = xt−1 + δtb · sign(f(xr) − f(xl)) (4) Algorithm 1 Initial Task Allocation Procedure Input: G(V,E,W), S with configured containers, local server sl Output: initial solution 1: assume v0, v1, ..., vJ+1 are the task precedence of G. 2: Fj,k := +∞ for 0 ≤ j ≤ J + 1 and 0 ≤ k ≤ K. 3: let F0,l := 0. 4: for j = 1 to J do 5: for k = 0 to K do 6: find Pj , Pj = {(vi, sy)| vi is a direct predecessor task of vj , sy is the server to which vi is assigned} 7: if server sk with container map(vj ) then 8: Fj,k = max(vi,sy)∈Pj {Fi,y + ωi,j ry,k + pj,k} 9: else 10: find S map(vj ), S map(vj ) = {sz| sz is the server with container map(vj ) in edge server or cloud}. 11: Fj,k = max(vi,sy)∈Pj ,sz∈S map(vj ) {Fi,y + ωi,j ry,k + pj,k + ∆map(vj ),k,z} 12: end if 13: end for 14: let u = arg min0≤k≤K k Fj,k 15: assign task vj to server su 16: end for 17: Fj+1,l = max(vi,sy)∈Pj+1 {Fi,y + ωi,j ry,l } 18: construct the initial solution from FJ+1,l. 19: return initial solution where δ is the size of the search step; sign(·) represents a sign function; f(·) is a function to be optimized. Our goal is to minimize job completion time (i.e., makespan), so we use the reciprocal of the makespan as the function. f(x) = 1 makespan(x) (5) With iteration, the step size gradually decreases for a more refined search and the distance vector is adjusted with it, they are shown as follows: δt = hδt−1 (6) dt = δt /c (7) where h is coefficient of the step size, c is a constant preferably between 2 to 10. Note that some vectors are operated to be non-integer, such as xl and xr, in order to make them operate in f, we deal with them as follows: x = |x | mod K (8) the formula is to convert the non-integer number x into an integer number that can indicate server identification. The details of the CBAS are shown in Algorithm 2. More importantly, the performance of BAS after discretization is poor, so we alleviate it by adding a logistic chaotic map in the first iter/2 iterations (Line 8-12) [12]. Specially, the purpose of generating the chaos value from a deterministic nonlinear Authorized licensed use limited to: University of Science & Technology of China. Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore. Restrictions apply.
system is to locally adjust x regularly (Line 11-12).From the experiment,we find that the algorithm is non-convergence. cross point Fortunately,it doesn't affect the purpose of obtaining a better to ti ta ts ta ts te solution.Finally,we update the current optimal scheduling. 1123211 1122130 to ti t红tsttt Algorithm 2 CBAS 1322131 13232110 Input:G(V,E,W),K,J,the number of iteration iter,f Output::Φ cross point 1:generate integer solution x using (1) 2:Let o be the the current maximum value of the function Fig.2:An example of two chromosomes crossing f,and set =0 3:for t in iter do 4: update b using (1) at the crossover point.For example,there are two parent 5 update the variable 6,dt via (6).(7) chromosomes,which are two encoding solution of scheduling 6: compute z,r following (2)(3),and Convert them of the job with five tasks on the left side of Fig.2.They using (8) are crossing at cross-point that is between t2 and t3,and the 7: compute xt via (4) right side of the figure is the result of crossing.The crossed 8: if tΦthen In automated gene combination,we call CBAS with related 15 Φ←x parameters.Its steps have been detailed in the previous part. 16: 中←f(x) After the operation,it only obtains one chromosome,but the 17: end if chromosome has a high fitness.Adding the chromosome with 18:end for relatively high fitness to each generation of the algorithm,it i9:returnΦ can gradually improve the fitness of the whole population. The evaluation operation is to evaluate the fitness value of each chromosome by the fitness function to provide an C.CBASGA Algorithm indicator for the selection operation.In the same way,we still In this part,the task allocation solutions are called chro- use the formula (5)as the fitness function.This means the mosomes.The details of the CBASGA is shown in Algo- goal of the algorithm is to find the minimum job completion rithm 3.We get a better chromosome from the initialization time. phase.But the basis of genetic operators is population,we randomly generate N-1 chromosomes.Then,we perform IV.PERFORMANCE EVALUATION T generations,each of which comprises five operations (i.e., In this section.we use the job information data collected selection,crossover,mutation,automated gene combination, by the Alibaba cluster trace program over 8 days from 4,000 and evaluation). heterogeneous machines as our data set source [13].Without The selection operation is an important part from the loss of generality,we randomly choose 1000 jobs from it, previous generation to the next generation.Before the t- each of which has between 2 and 59 tasks.Then,we use it to th generation,the populationD are given fitness evaluate the designed system and CBASGA algorithm values obtained in the previous generation or initialization, A.Experiment Settings which directly impact the probability that each chromosome will survive the selection process.We perform a proportionate a)Edge and Cloud Clusters:Our simulations are carried roulette wheel selection to determine which chromosome sur- out in an edge-cloud cluster,where there are 4 edge servers vives.The selection probability function is defined as follows: and a remote cloud.The number of containers of each server can hold is limited,which is set to 3 by default.Similar to [14],we generate values for data transmission time among Pselect(Dt.n）= fitness(Dtn) ∑1 fitness(Dm (9) edge servers uniformly from the interval [5,100]ms.Similarly, the processing time of each task is drawn uniformly from the For the crossover operation,the two paternal chromosomes interval [10,200].Considering that the data transmission to the are selected with probability pe,and then the crossover points cloud can consume a lot of latency,we set it in the range of are randomly selected on them.It can produce two new 100,2000 ms.The container configuration times from the chromosomes when the two paternal chromosomes are crossed edge are set in [300,700]ms.In view of that configuring Authorized licensed use limited to:University of Science Technology of China.Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore.Restrictions apply
system is to locally adjust xt regularly (Line 11-12). From the experiment, we find that the algorithm is non-convergence. Fortunately, it doesn’t affect the purpose of obtaining a better solution. Finally, we update the current optimal scheduling. Algorithm 2 CBAS Input: G(V,E,W), K, J, the number of iteration iter, f Output: Φ 1: generate integer solution x using (1) 2: Let φ be the the current maximum value of the function f, and set ϕ = 0 3: for t in iter do 4: update b using (1) 5: update the variable δ, dt via (6),(7) 6: compute xl, xr following (2)(3), and Convert them using (8) 7: compute xt via (4) 8: if t φ then 15: Φ ← xt 16: φ ← f(xt ) 17: end if 18: end for 19: return Φ C. CBASGA Algorithm In this part, the task allocation solutions are called chromosomes. The details of the CBASGA is shown in Algorithm 3. We get a better chromosome from the initialization phase. But the basis of genetic operators is population, we randomly generate N − 1 chromosomes. Then, we perform T generations, each of which comprises five operations (i.e., selection, crossover, mutation, automated gene combination, and evaluation). The selection operation is an important part from the previous generation to the next generation. Before the tth generation, the population {Dt−1,n}N n=1 are given fitness values obtained in the previous generation or initialization, which directly impact the probability that each chromosome will survive the selection process. We perform a proportionate roulette wheel selection to determine which chromosome survives. The selection probability function is defined as follows: Pselect(Dt,n) = f itness(Dt,n) N n=1 f itness(Dt,n) (9) For the crossover operation, the two paternal chromosomes are selected with probability pc, and then the crossover points are randomly selected on them. It can produce two new chromosomes when the two paternal chromosomes are crossed 濄濄濅濆濅濄濄 W W W W W W W 濄濆濅濅濄濆濄 W W W W W W W 濄濄濅濅濄濆濄 濄濆濅濆濅濄濄 Fig. 2: An example of two chromosomes crossing at the crossover point. For example, there are two parent chromosomes, which are two encoding solution of scheduling of the job with five tasks on the left side of Fig. 2. They are crossing at cross-point that is between t2 and t3, and the right side of the figure is the result of crossing. The crossed chromosomes are new allocation solutions, which have new fitness value respectively. From the crossed chromosomes, the mutant chromosomes are selected with a probability pm. Then the mutation operation randomly changes the mutational site of the chromosome from one to another, trying new possibilities while keeping the good traits. In automated gene combination, we call CBAS with related parameters. Its steps have been detailed in the previous part. After the operation, it only obtains one chromosome, but the chromosome has a high fitness. Adding the chromosome with relatively high fitness to each generation of the algorithm, it can gradually improve the fitness of the whole population. The evaluation operation is to evaluate the fitness value of each chromosome by the fitness function to provide an indicator for the selection operation. In the same way, we still use the formula (5) as the fitness function. This means the goal of the algorithm is to find the minimum job completion time. IV. PERFORMANCE EVALUATION In this section, we use the job information data collected by the Alibaba cluster trace program over 8 days from 4,000 heterogeneous machines as our data set source [13]. Without loss of generality, we randomly choose 1000 jobs from it, each of which has between 2 and 59 tasks. Then, we use it to evaluate the designed system and CBASGA algorithm. A. Experiment Settings a) Edge and Cloud Clusters: Our simulations are carried out in an edge-cloud cluster, where there are 4 edge servers and a remote cloud. The number of containers of each server can hold is limited, which is set to 3 by default. Similar to [14], we generate values for data transmission time among edge servers uniformly from the interval [5, 100] ms. Similarly, the processing time of each task is drawn uniformly from the interval [10, 200]. Considering that the data transmission to the cloud can consume a lot of latency, we set it in the range of [100, 2000] ms. The container configuration times from the edge are set in [300, 700] ms. In view of that configuring Authorized licensed use limited to: University of Science & Technology of China. Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore. Restrictions apply.
Algorithm 3 CBASGA Input:G(V.E,W),S with configured containers,local server s,the number of generations T,the number of Container from the cloud or edge rom the clou chromosomes in each generation N and the crossover and mutation probabilities Pe and pm 1:get Do.1 from Algorithm 1,and initialize population Do2 by randomly assigning tasks to each server 1.0 according to the G task precedence 0.8 2:while t<T do 0.6 3: Selection:select a new generationD with a 0.4 proportionate roulette wheel 0. Crossover:for each pair(DnD per- form crossover with probability pe at selected crossover OnDoc GA BA5 Different Algorithms point 5: Mutation:for each crossover (Dn).make muta- Fig.3:Comparison of completion time in different scenes tion with probability pm at selected mutation point 6: Automated Gene Combination:product a chromosome with high fitness from CBAS see that our CBASGA algorithm has excellent performance 7: Evaluation:evaluate the fitness of the population in both our system and the comparison system.Table I 3N+1 by calculating the makespan of the sched- {Dt.nin=i shows that CBASGA can reduce 47.3%,21.7%,54.8%of the ule completion time on average compared to OnDoc,GA and BAS 8:end while respectively in designed system(46.9%,22.4%,55.3%in the 9:return the schedule with the highest fitness comparison system).Although GA and BAS are both bionic algorithms,the discretized BAS which is not convergent has lower performance.CBASGA's percentage of completed job the container from the cloud suffers a long latency,so by is consistently above the three baselines. default we set it as 20 times of the configuration time between two edge servers.The cloud has all containers and thus the TABLE I:Comparison of OnDoc,GA,BAS and CBASGA configuration time is 0 there.The processing time in the cloud server is set 0.75 times(on average)of the processing time in Time (s) Scheduler Min Max Mean edge servers,as the cloud generally provides more computing OnDoc 0.381 3.153 1.346 resources than edge servers.For the comparison system,we GA 0.204 5.663 0.906 BAS 0.222 6.927 1.568 restrict it to configuring the container only from the cloud. CBASGA 0.164 1.763 0.709 b)Comparison Baselines:According to the previous section,we can know CBASGA is a hybrid algorithm,which contains three common policies (the earliest completion time, 2)Flexibility Analysis:Here,we analyze CBASGA's flex- CBAS and GA.To examine the performance of CBASGA,we ibility to the effect of multiple factors:the container config- compare CBASGA with them respectively.Specially,for the uration time,the capacity of the edge server,CCR,and the earliest completion time policy,we use OnDoc [15].But it is number of the edge servers. not suitable for containers to be configured from the edge,we a)Effect of the Container Configuration Time:To ex- modify it to adapt our system. plore the effect of the different scale of container configuration time,we scale the configuration time from 0.2x to 4.0x of the B.Experiment Results original value while keeping the other parameters unchanged. In this part,we first exhibit the simulated results of overall The job completion times under different configuration time performance based on the 1000 jobs.Then,we conduct are shown in Fig.4.As the configuration time increases,so flexibility experiments using three specific DAGs [14],to study does the completion time on the whole.The OnDoc has the the effect of container configuration time,the capacity of the worst performance,because the simple greedy strategy only edge server,the communication computation ratio (CCR)and considers the current optimal and loses sight of the other the number of edge servers. possible better solutions.GA's performance is generally better 1)The Overall Performance:Fig.3 shows the average than BAS,because the discretized BAS is equivalent to a completion time in our system and the comparison system random selection algorithm.CBASGA is the least effected during the execution of the four algorithms respectively. algorithm compared to the other algorithms. Compared to the system which configures containers only b)Effect of the Capacity of Edge Server:Fig.5 presents from the cloud,the job completion times of using four the completion time of the four algorithms at different edge algorithms are less in designed system,which reduces the server capacity.Except for CBASGA,none of the other three average job completion by 4.02%.In addition,we can also algorithms shows a significant decrease in the completion time Authorized licensed use limited to:University of Science Technology of China.Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore.Restrictions apply
Algorithm 3 CBASGA Input: G(V,E,W), S with configured containers, local server sl, the number of generations T, the number of chromosomes in each generation N and the crossover and mutation probabilities pc and pm 1: get D0,1 from Algorithm 1, and initialize population {D0,n}N n=2 by randomly assigning tasks to each server according to the G task precedence 2: while t<T do 3: Selection: select a new generation {Dt,n}N n=1 with a proportionate roulette wheel 4: Crossover: for each pair {(Dt,2n−1, Dt,2n)} N/2 n=1 , perform crossover with probability pc at selected crossover point 5: Mutation: for each crossover {Dt,n}N n=1, make mutation with probability pm at selected mutation point 6: Automated Gene Combination: product a chromosome with high fitness from CBAS 7: Evaluation: evaluate the fitness of the population {Dt,n}3N+1 n=1 by calculating the makespan of the schedule 8: end while 9: return the schedule with the highest fitness the container from the cloud suffers a long latency, so by default we set it as 20 times of the configuration time between two edge servers. The cloud has all containers and thus the configuration time is 0 there. The processing time in the cloud server is set 0.75 times (on average) of the processing time in edge servers, as the cloud generally provides more computing resources than edge servers. For the comparison system, we restrict it to configuring the container only from the cloud. b) Comparison Baselines: According to the previous section, we can know CBASGA is a hybrid algorithm, which contains three common policies (the earliest completion time, CBAS and GA. To examine the performance of CBASGA, we compare CBASGA with them respectively. Specially, for the earliest completion time policy, we use OnDoc [15]. But it is not suitable for containers to be configured from the edge, we modify it to adapt our system. B. Experiment Results In this part, we first exhibit the simulated results of overall performance based on the 1000 jobs. Then, we conduct flexibility experiments using three specific DAGs [14], to study the effect of container configuration time, the capacity of the edge server, the communication computation ratio (CCR) and the number of edge servers. 1) The Overall Performance: Fig. 3 shows the average completion time in our system and the comparison system during the execution of the four algorithms respectively. Compared to the system which configures containers only from the cloud, the job completion times of using four algorithms are less in designed system, which reduces the average job completion by 4.02%. In addition, we can also Fig. 3: Comparison of completion time in different scenes see that our CBASGA algorithm has excellent performance in both our system and the comparison system. Table I shows that CBASGA can reduce 47.3%, 21.7%, 54.8% of the completion time on average compared to OnDoc, GA and BAS respectively in designed system (46.9%, 22.4%, 55.3% in the comparison system). Although GA and BAS are both bionic algorithms, the discretized BAS which is not convergent has lower performance. CBASGA’s percentage of completed job is consistently above the three baselines. TABLE I: Comparison of OnDoc, GA, BAS and CBASGA Scheduler Time (s) Min Max Mean OnDoc 0.381 3.15 1.346 GA 0.204 5.663 0.906 BAS 0.222 6.927 1.568 CBASGA 0.164 1.763 0.709 2) Flexibility Analysis: Here, we analyze CBASGA’s flexibility to the effect of multiple factors: the container configuration time, the capacity of the edge server, CCR, and the number of the edge servers. a) Effect of the Container Configuration Time: To explore the effect of the different scale of container configuration time, we scale the configuration time from 0.2× to 4.0× of the original value while keeping the other parameters unchanged. The job completion times under different configuration time are shown in Fig. 4. As the configuration time increases, so does the completion time on the whole. The OnDoc has the worst performance, because the simple greedy strategy only considers the current optimal and loses sight of the other possible better solutions. GA’s performance is generally better than BAS, because the discretized BAS is equivalent to a random selection algorithm. CBASGA is the least effected algorithm compared to the other algorithms. b) Effect of the Capacity of Edge Server: Fig. 5 presents the completion time of the four algorithms at different edge server capacity. Except for CBASGA, none of the other three algorithms shows a significant decrease in the completion time Authorized licensed use limited to: University of Science & Technology of China. Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore. Restrictions apply
eral Oata Pro dlex Date Analys 7. Confguration Tme ss Confauration Tme is) the Number of Edge Servers the Number of Edge Servers Fig.4:Completion time of different container configuration Fig.7:Completion time of different number of edge servers time offsets this randomness.That is to say,the more tasks there leoc Data are,the more likely there are to match the container of a new edge server.OnDoc fluctuates a lot because it only considers the earliest completion of the current task,and the appearance of a new edge server will affect it,resulting in changes in the final job completion.GA and BAS fluctuate under the influence of random initialization and parameters.Compared Fig.5:Completion time of different capacity of edge servers to them,CBASGA presents the best performance among the three DAGs V.CONCLUSION In this work,we propose a container-based edge system, which can reduce significantly container configuration time by obtaining containers from nearby servers.Then,we propose a novel hybrid model to schedule tasks within independent task constraint and server capacity constraints.By purpose- Fig.6:Completion time of different communication compu- ful initialization and automated gene combination,CBASGA tation ratio can evolve directionally in a highly adaptable initialization population.Based on the real cluster trace from Alibaba,the experimental results show that the proposed algorithm can efficiently reduce the job completion time in a variety of with the increase of capacity.Since the increased capacity is matched with random containers in our experiment,the scenarios compared with baselines.Although we used CBAS increased capacity may not be used by the task (on account with low time complexity to construct a genetic combination. of the task is executed by configuring the corresponding the overall time complexity of CBASGA is still relatively high.A feasible solution is to separate the calculation process container).Therefore,there is no significant reduction. of CBAS from CBASGA and make CBASGA and CBAS c)Effect of the Communication Computation Ratio: execute concurrently.Furthermore,the task dependencies in Similar to study the effect of the container configuration time,we scale the CCR from 0.2x to 4.0x of the original the experiment come from Alibaba's data-trace and how to value to explore the effect of CCR.As shown in Fig.6, decompose and extract the dependencies from the actual job is a new challenge in the future. while increasing the CCR,the completion times of using three baselines are increasing gradually except CBASGA.This ACKNOWLEDGMENT is due to the increased proportion of communication time, resulting in increased data transfer and container configuration This work is supported partly by the National Key R&D time.Compared to the three algorithms,CBASGA shows that Program of China 2018YFB2100303.2018YFB0803400 and the job completion time increases little with the increase of the National Natural Science Foundation of China (NSFC)under communication computation ratio,so it is the most efficient grant61772487 That is because CBASGA tends to try to place tasks on different servers to find a better scheduling REFERENCES d)Effect of the Number of Edge Servers:Fig.7 shows [1]W.Shi,J.Cao,Q.Zhang.Y.Li,and L.Xu,"Edge the completion time of the four algorithms as the number of computing:Vision and challenges,"IEEE internet of edge servers grows.In our experiment,the container configu- things journal,vol.3,no.5,pp.637-646,2016. ration of the new edge server is also random,which make it [2]A.Mseddi,W.Jaafar,H.Elbiaze,and W.Ajib,"Joint unlikely that the new edge server could be used by the task. container placement and task provisioning in dynamic In complex data analysis,we can see an overall downward fog computing,"IEEE Internet of Things Journal,vol.6, trend.As the large number of tasks in complex jobs partially no.6,Pp.10028-10040,2019. Authorized licensed use limited to:University of Science Technology of China.Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore.Restrictions apply
Fig. 4: Completion time of different container configuration time Fig. 5: Completion time of different capacity of edge servers Fig. 6: Completion time of different communication computation ratio with the increase of capacity. Since the increased capacity is matched with random containers in our experiment, the increased capacity may not be used by the task (on account of the task is executed by configuring the corresponding container). Therefore, there is no significant reduction. c) Effect of the Communication Computation Ratio: Similar to study the effect of the container configuration time, we scale the CCR from 0.2× to 4.0× of the original value to explore the effect of CCR. As shown in Fig. 6, while increasing the CCR, the completion times of using three baselines are increasing gradually except CBASGA. This is due to the increased proportion of communication time, resulting in increased data transfer and container configuration time. Compared to the three algorithms, CBASGA shows that the job completion time increases little with the increase of the communication computation ratio, so it is the most efficient. That is because CBASGA tends to try to place tasks on different servers to find a better scheduling. d) Effect of the Number of Edge Servers: Fig. 7 shows the completion time of the four algorithms as the number of edge servers grows. In our experiment, the container configuration of the new edge server is also random, which make it unlikely that the new edge server could be used by the task. In complex data analysis, we can see an overall downward trend. As the large number of tasks in complex jobs partially Fig. 7: Completion time of different number of edge servers offsets this randomness. That is to say, the more tasks there are, the more likely there are to match the container of a new edge server. OnDoc fluctuates a lot because it only considers the earliest completion of the current task, and the appearance of a new edge server will affect it, resulting in changes in the final job completion. GA and BAS fluctuate under the influence of random initialization and parameters. Compared to them, CBASGA presents the best performance among the three DAGs. V. CONCLUSION In this work, we propose a container-based edge system, which can reduce significantly container configuration time by obtaining containers from nearby servers. Then, we propose a novel hybrid model to schedule tasks within independent task constraint and server capacity constraints. By purposeful initialization and automated gene combination, CBASGA can evolve directionally in a highly adaptable initialization population. Based on the real cluster trace from Alibaba, the experimental results show that the proposed algorithm can efficiently reduce the job completion time in a variety of scenarios compared with baselines. Although we used CBAS with low time complexity to construct a genetic combination, the overall time complexity of CBASGA is still relatively high. A feasible solution is to separate the calculation process of CBAS from CBASGA and make CBASGA and CBAS execute concurrently. Furthermore, the task dependencies in the experiment come from Alibaba’s data-trace and how to decompose and extract the dependencies from the actual job is a new challenge in the future. ACKNOWLEDGMENT This work is supported partly by the National Key R&D Program of China 2018YFB2100303, 2018YFB0803400 and National Natural Science Foundation of China (NSFC) under grant 61772487. REFERENCES [1] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge computing: Vision and challenges,” IEEE internet of things journal, vol. 3, no. 5, pp. 637–646, 2016. [2] A. Mseddi, W. Jaafar, H. Elbiaze, and W. Ajib, “Joint container placement and task provisioning in dynamic fog computing,” IEEE Internet of Things Journal, vol. 6, no. 6, pp. 10 028–10 040, 2019. Authorized licensed use limited to: University of Science & Technology of China. Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore. Restrictions apply
[3]J.Thones,"Microservices,"IEEE software,vol.32,no.1, Pp.116-116,2015. [4]A.Samanta and J.Tang,"Dyme:Dynamic microservice scheduling in edge computing enabled iot,"IEEE Internet of Things Journal,2020. [5]"Edgex foundry,"https://www.edgexfoundry.org/. [6]M.Chen and Y.Hao,"Task offloading for mobile edge computing in software defined ultra-dense network," IEEE Journal on Selected Areas in Communications, vol.36,no.3,pp.587-597,2018. [7]H.Tan,Z.Han,X.-Y.Li,and F.C.Lau,"Online job dispatching and scheduling in edge-clouds,"in IEEE INFOCOM 2017-IEEE Conference on Computer Com- munications.IEEE,2017,pp.1-9. [8]J.Meng,H.Tan,C.Xu,W.Cao,L.Liu,and B.Li, "Dedas:Online task dispatching and scheduling with bandwidth constraint in edge computing,"in IEEE IN- FOCOM 2019-IEEE Conference on Computer Commu- nications.IEEE,2019,pp.2287-2295. [9]R.Urgaonkar,S.Wang,T.He,M.Zafer,K.Chan,and K.K.Leung,"Dynamic service migration and workload scheduling in edge-clouds,"Performance Evaluation, vol.91,pp.205-228,2015. [10]K.Shin,M.Cha,M.Jang.J.Jung,W.Yoon,and S.Choi, "Task scheduling algorithm using minimized duplications in homogeneous systems,"Journal of Parallel and Dis- tributed Computing,vol.68,no.8,pp.1146-1156,2008. [11]X.Jiang and S.Li,"Bas:beetle antennae search algorithm for optimization problems,"arXiv preprint arXi:1710.10724.2017. [12]B.Alatas,E.Akin,and A.B.Ozer,"Chaos embedded particle swarm optimization algorithms,"Chaos,Solitons &Fractals,vol.40no.4,Pp.1715-1734,2009. [l3]“Alibaba trace,”htps:l∥github.com/alibaba/clusterdata,. 2018. [14]L.Liu,H.Tan,S.H.-C.Jiang,Z.Han,X.-Y.Li,and H.Huang,"Dependent task placement and scheduling with function configuration in edge computing,"in Pro- ceedings of the International Symposium on Quality of Service.Association for Computing Machinery,2019. [15]L.Liu,H.Huang,H.Tan,W.Cao,P.Yang,and X.-Y.Li, "Online dag scheduling with on-demand function con- figuration in edge computing,"in International Confer- ence on Wireless Algorithms,Systems,and Applications. Springer,2019,pp.213-224. Authorized licensed use limited to:University of Science Technology of China.Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore.Restrictions apply
[3] J. Thones, “Microservices,” ¨ IEEE software, vol. 32, no. 1, pp. 116–116, 2015. [4] A. Samanta and J. Tang, “Dyme: Dynamic microservice scheduling in edge computing enabled iot,” IEEE Internet of Things Journal, 2020. [5] “Edgex foundry,” https://www.edgexfoundry.org/. [6] M. Chen and Y. Hao, “Task offloading for mobile edge computing in software defined ultra-dense network,” IEEE Journal on Selected Areas in Communications, vol. 36, no. 3, pp. 587–597, 2018. [7] H. Tan, Z. Han, X.-Y. Li, and F. C. Lau, “Online job dispatching and scheduling in edge-clouds,” in IEEE INFOCOM 2017-IEEE Conference on Computer Communications. IEEE, 2017, pp. 1–9. [8] J. Meng, H. Tan, C. Xu, W. Cao, L. Liu, and B. Li, “Dedas: Online task dispatching and scheduling with bandwidth constraint in edge computing,” in IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019, pp. 2287–2295. [9] R. Urgaonkar, S. Wang, T. He, M. Zafer, K. Chan, and K. K. Leung, “Dynamic service migration and workload scheduling in edge-clouds,” Performance Evaluation, vol. 91, pp. 205–228, 2015. [10] K. Shin, M. Cha, M. Jang, J. Jung, W. Yoon, and S. Choi, “Task scheduling algorithm using minimized duplications in homogeneous systems,” Journal of Parallel and Distributed Computing, vol. 68, no. 8, pp. 1146–1156, 2008. [11] X. Jiang and S. Li, “Bas: beetle antennae search algorithm for optimization problems,” arXiv preprint arXiv:1710.10724, 2017. [12] B. Alatas, E. Akin, and A. B. Ozer, “Chaos embedded particle swarm optimization algorithms,” Chaos, Solitons & Fractals, vol. 40, no. 4, pp. 1715–1734, 2009. [13] “Alibaba trace,” https://github.com/alibaba/clusterdata, 2018. [14] L. Liu, H. Tan, S. H.-C. Jiang, Z. Han, X.-Y. Li, and H. Huang, “Dependent task placement and scheduling with function configuration in edge computing,” in Proceedings of the International Symposium on Quality of Service. Association for Computing Machinery, 2019. [15] L. Liu, H. Huang, H. Tan, W. Cao, P. Yang, and X.-Y. Li, “Online dag scheduling with on-demand function con- figuration in edge computing,” in International Conference on Wireless Algorithms, Systems, and Applications. Springer, 2019, pp. 213–224. Authorized licensed use limited to: University of Science & Technology of China. Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore. Restrictions apply