# Efficient Dynamic Deployment of Simulation Tasks in Collaborative Cloud and Edge Environments
## 1 Introduction
As all the information about tasks and hosts is needed, this kind of scheduler requires more a priori knowledge and usually more time is consumed to solve such a combinational optimization problem. Considering the frequent message transmissions between simulation tasks, they should be deployed jointly to avoid degrading the performance of simulation applications. Thus, scheduling simulation tasks with a batching-based scheduler is a better choice. To solve such an NP-hard problem, many algorithms are also proposed. Some researchers adopted meta-heuristics to find approximate optimal solutions. These algorithms are usually inspired by natural phenomena [14], such as the predation behaviors of birds (particle swarm optimization, PSO) and ants (ant colony optimization, ACO). Although they are easy to perform well in some optimization problems with complicated constraints, they tend to be time-consuming and non-deterministic even if all the parameters keep unchanged. To improve the time performance of the scheduler, heuristics were also utilized by some scholars, such as dominant resource fairness [15] and shortest job first [16]. As a trade-off, the deployment quality of tasks is not always satisfying and it is prone to fall into local minimum for these algorithms. By relaxing some constraints and converting the task scheduling problem into a min-cost max-flow problem, tasks can be scheduled jointly in polynomial time, which is called flow-based scheduling [17; 18; 19]. In this method, tasks and computation nodes are modeled as nodes and the feasible deployment solutions are modeled as arcs. By setting the cost value and upper capacity of each arc properly, the final assignment decisions can be extracted from the generated optimal flow. However, current flow-based schedulers cannot deploy tasks efficiently, especially when the status of tasks and hosts changes frequently. In this paper, we propose a new scheduler called Pool to cope with this issue. Firstly, the network optimization problem is solved efficiently using incremental MCMF algorithms in Pool. Then, tasks are rescheduled with the consideration of migration cost of tasks. In such a way, tasks are deployed properly with the aim of minimizing the communication cost of all tasks, as well as reducing the overall migration cost when the status of tasks and hosts changes. Compared to the existing flow-based schedulers, Pool can achieve almost 5.8 times faster time performance with a small proportion of changing tasks and hosts. In summary, the main contributions of this paper can be stated as follows:  
* We formulate the problem of scheduling simulation tasks in collaborative cloud and edge environments as a MCMF problem and incremental MCMF algorithms are adopted to find the optimal flow quickly when the status of tasks and hosts changes;
* We propose a new heuristic method to reschedule tasks efficiently based on both the newly generated optimal flow and the current deployment decisions of all tasks to minimize both the overall communication cost and the migration cost of all tasks;
* Extensive experiments on Alibaba cluster trace are conducted to illustrate the effectiveness of Pool. The rest of this paper is organized as follows: Section 2 reviews the related work about task scheduling. Section 3 states the problem background and models it as a MCMF problem. Section 4 details the design of our incremental task scheduler. Section 5 evaluates the performance of Pool, and conclusions and possibilities of future works are given in Section 6.