# Efficient Dynamic Deployment of Simulation Tasks in Collaborative Cloud and Edge Environments
## 4 Design of Pool
### Reassigning of Tasks
At this time, tasks can be assigned in a traditional way without the consideration of task migration based on _unScheList_ and the updated flow \(f^{\tau+1}\) (see Line 35 in Algorithm 1). As this procedure is similar to other flow-based schedulers, it is not described in detail for simplicity. ### Time Complexity of Pool

In each iteration of Pool, two procedures are needed, namely obtaining the optimal flow incrementally and reassigning the tasks based on both the newly obtained optimal flow and the assignments of tasks in the last iteration. For the first procedure, all the tasks and hosts change in the worst scenario and thus the time complexity equals to solving MCMF problems from draft. Since network simplex is adopted as the MCMF solver, the time complexity is \(O(NM^{2}CU)\), where N denotes the number of nodes, M the number of arcs, C the maximum value of arc cost, and U the maximum value of arc capacity. In the second procedure, there exists two extreme situations. If all tasks have been assigned to some hosts in the last iteration (See line 4 in Algorithm 1), the time complexity in this procedure can be denoted as \(O(|\mathbb{T}|\cdot\log(|\mathbb{T}|))+|\mathbb{T}|\cdot(O(1)+O(|\mathbb{C}| +|\mathbb{E}|))=O(|\mathbb{T}|\cdot\log(|\mathbb{T}|))\). Otherwise, the assignments of tasks should be extracted greedily from the optimal flow, which may incur \(O(|\mathbb{T}|\cdot|\mathbb{H}|)\) time complexity. Thus, the time complexity of procedure 2 is \(\max(O(|\mathbb{T}|\cdot\log(|\mathbb{T}|)),O(|\mathbb{T}|\cdot|\mathbb{H}|))\). Considering that \(M>N>|\mathbb{T}|>|\mathbb{H}|\), the overall time complexity of Pool is \(O(NM^{2}CU)\). ## 5 Experiments and Analysis

In this section, performance of Pool is analyzed and evaluated. We mainly focus on scheduling tasks efficiently when the status of tasks and hosts changes frequently. Thus, two evaluation indicators are adopted, namely time performance and deployment quality. Time performance is quantified by the time span between the changing of tasks and hosts to the completion of task assignments. Deployment quality is expressed by the overall communication cost of tasks according to Equation (1). As described in Section 2.2, various algorithms can be adopted to schedule tasks. Since the superiority of flow-based scheduler has been verified in previous studies [17; 18; 19], we mainly evaluate whether it still works well when the status of tasks and hosts changes frequently. In the design of Pool, optimal flow \(f^{\tau+1}\) is calculated based on incremental MCMF algorithms and task assignments are determined with the consideration of task migration cost. This strategy is called Pool_Inc in the latter parts. For comparison, Pool_nInc is designed, in which \(f^{\tau+1}\) is calculated from the draft and tasks are assigned at time \(\tau+1\) based on only the optimal flow \(f^{\tau+1}\) and current assignments \(\mathcal{F}^{\tau}\) without the consideration of task migration cost. For simplicity, Pool_Inc and Pool_nInc are abbreviated as Inc and nInc, respectively. ### Parameter Settings

In our experiments, Alibaba cluster trace [44] was adopted to generate resource requirements of tasks, as well as resource supplies of hosts. It consists of 13,654 hosts and 116,418 tasks, which are highly heterogeneous and rich in runtime information. In this paper, only number of CPU cores and volume of memory of tasks and hosts were derived from the trace. To evaluate the performance of Pool in different problem scales, the numbers of hosts were set at 13,654 and 1000, which were also called big and small problem scale, respectively. For each scale, different load levels called _Low_, _Medium_, and _High_ were adopted. Details about the number of tasks and hosts are given in Table 1.

However, information about network topology of computation nodes and the communication patters between tasks are not recorded in Alibaba trace. In our experiments, these values were generated randomly.