# Efficient Dynamic Deployment of Simulation Tasks in Collaborative Cloud and Edge Environments
## 4 Design of Pool
### Obtaining Optimal Flow Incrementally
#### 4.2.2 Solving MCMF Incrementally  
As stated in Section 4.2, influences of the changes of tasks and hosts on the flow network can be summed up as 7 types: (1) nodes are added; (2) nodes are deleted; (3) supply values \(b_{i}\) of some tasks change; (4) arcs are added; (5) arcs are deleted; (6) cost values \(c_{ij}\) of some arcs change; and (7) upper capacities \(u_{ij}\) of some arcs change. Generally, algorithms on MCMF problems can be categorized into three types, namely primal, dual, and primal-dual methods [37]. Primal methods, such as _cycle cancelling_[38] and _network simplex_[39], try to reduce the overall cost on all arcs by increasing flow along the negative cost loops iteratively. During the process, feasibility of flow \(f\) in each iteration is ensured while the optimality is continuously improved until no negative cost loop can be found. On the contrary, dual methods, such as _relaxation_[40] and _successive shortest path_[41], optimize the dual problem iteratively based on Lagrangian duality. Optimal flow \(f\) can be obtained by keeping the so-called _complementary slackness optimality_. In this process, reduced cost optimality is maintained while feasibility is improved. Cost scaling [42] is a typical primal-dual method, which has been seen as the most efficient MCMF algorithm. During iterations, both feasibility and optimality are maintained by introducing a new concept called _\(\epsilon\)-complementary slackness optimality_. Since changes on the network usually take place locally, the solving process can be significantly accelerated when MCMF problems are solved incrementally. As stated above, different kinds of algorithms should keep some specific features during an iteration. For primal and primal-dual methods, the feasibility of flow should be ensured in each iteration. On the contrary, complementary slackness is maintained in dual algorithms. As  
Figure 3: Influences of changing tasks on the network structure. these features are always destroyed after changing the network, these features need to be restored first before reoptimizing the problem. In general, three steps are needed when solving MCMF problems incrementally, namely (1) updating network and the associated data structures; (2) restoring the features of algorithms; and (3) reoptimizing. Time performance about these algorithms has been studied widely and cost scaling (CS) and network simplex (NS) are recognized as the two most efficient algorithms [37]. To have a more complete analysis, relaxation algorithm together with CS and NS are discussed in detail. In relaxation, flow is increased along an _augmenting path_ to improve the feasibility of \(f\). Destruction on complementary slackness can be easily restored by adjusting flow. In CS, feasibility is maintained and flow \(f\) is improved by scaling down \(\epsilon\), which can be seen as the error. The smaller \(\epsilon\) is, the faster CS executes. However, \(\epsilon\) may change significantly even if only a few arcs change. Experiments in Hapi [43] show that runtime of CS is unpredictable with large variance. In NS, a tree data structure is adopted which can be used to preserve past information. To solve problems incrementally, changes on network need to be reflected on the modification the tree. Time performance on solving MCMF problems incrementally has been verified in Firmament [18], where only CS2 (a version of CS) and RelaxIV (a version relaxation) were compared. In this paper, CS2, RelaxIV and network simplex are all implemented and compared. In our experiments, the numbers of tasks and hosts are set at 3200 and 1000, respectively. Percentage of changed tasks and hosts increases from 0.001 to 0.2 with a step of 0.001. Experiment results depicted in Figure 4 show that runtime of RelaxIV and NS is proportional to the percentage of changed nodes and arcs. When the percentage is relatively small, significant speed-up can be obtained. Compared to RelaxIV, runtime of NS has a much lower growth rate.