# Efficient Dynamic Deployment of Simulation Tasks in Collaborative Cloud and Edge Environments
## 4 Design of Pool
### Basic Framework of Flow-Based Scheduling  
Flow-based scheduling was first proposed in [PERSON] [17], in which the mapping between tasks and hosts is converted to a MCMF optimization problem over a flow network. A flow network is essential a directed graph \(G=(V,E)\), where \(V\) and \(E\) are the sets of nodes and arcs, respectively. Each node \(i\in V\) has a corresponding supply \(b_{i}\) and nodes are called sources or sinks according to whether their supplies are positive or negative. Each arc \((i,j)\in E\) is attached with three attributes, namely unit flow cost \(c_{ij}\), upper capacity \(u_{ij}\), and flow \(f_{ij}\). Thus, the goal of MCMF problem can be expressed as Equations (7)-(9).  
\[\text{Minimize}\quad\sum_{(i,j)\in E}c_{ij}\cdot f_{ij}\quad\text{ subject to} \tag{7}\]  
\[\sum_{k:(j,k)\in E}f_{jk}-\sum_{i:(i,j)\in E}f_{ij}=b_{j},\ \forall j\in V \tag{8}\]  
\[0\leq f_{ij}\leq u_{ij},\ \forall(i,j)\in E \tag{9}\]  
When applying it in scheduling scenarios, nodes can be seen as tasks or computation facilities while arcs are used to express the placement preferences of tasks and capacity constraints of hosts. A feasible path from task \(i\) to host \(h\) means that task \(i\) can be assigned to host \(h\). In general, flow-based scheduling has four main steps: (1) constructing the network; (2) setting the parameter values of nodes and arcs; (3) solving the MCMF problem  
Figure 1: Work flow in Pool.  
to obtain the optimal flow \(f\); (4) extracting the deployment decisions based on \(f\) and some heuristics rules.  
A typical flow network for task scheduling includes at least two kinds of nodes, namely task nodes and hosts nodes. In this situation, task nodes are sources and host nodes are sinks. In our scheduler, we introduce a virtual node \(t\) as the unique sink node. Additionally, task aggregator nodes \(TA\), host aggregator node \(HA\), data center node \(X\) and edge node \(Y\) are also adopted to reduce the total number of arcs. Tasks belonging to the same \(TA\) should share the similar resource requirements, communication patterns, and located regions of their corresponding users. Similarly, hosts belonging to the same \(HA\) should have the comparable resource capacities. Network structure in Pool is illustrated in Figure 2.  
After determining the structure of network in Pool, we need to set supply value \(b_{i}\) for node \(i\), cost value \(c_{ij}\), and upper capacity \(u_{ij}\) for arc \((i,j)\). Since tasks and hosts are all highly heterogeneous, it is improper to set \(b_{i}\) at 1 just as Quincy and Firmament. In this paper, CPU is considered as the dominated resource type. \(b_{i}\) is set according to how many CPU cores task \(i\) requires. \(u_{ij}\) is set based on the total number of CPU cores on node \(j\). Only arcs from \(HA\) to \(X\) or \(Y\) has nonzero \(c_{ij}\) and this value is used to express the corresponding communication cost.  
By saving the above information about nodes and arcs in a DIMACS [36] file, MCMF algorithms can be adopted to solve such a network optimization problem. The final task assignment decisions can then be extracted from the generated optimal flow \(f\).