## 6 Modified Priority-Based Greedy Heuristic
As pointed out in [13], as few MDCs as possible should be activated because the corresponding cost of activating MDCs is far higher than the other costs. Taking into account both considerations, the ModPG-VNFr merging algorithm is defined as shown in Algorithm 2. With the aim of reducing the cost of activating MDCs, the set of MDCs is sorted in increasing order considering the number of mapped VNFrs (Line 2 in Algorithm 2), and they are processed next (Line 3 in Algorithm 2). To reduce the complexity of the process, the implemented merging algorithm tries to empty the MDCs that host complete SFCrs (Line 7 in Algorithm 2). The moving of a sub-chain (a partial number of VNFrs belonging to an SFCr) involves not only the MDC to be emptied and the potential new destination MDCs, but also the MDCs that host the rest of the sub-chain. If all the SFCrs mapped on the processed MDC can be potentially moved to other MDCs (or distributed to various MDCs) fulfilling all the resource, delay, and bandwidth requirements and constraints (Line 14 Algorithm 2), the new proposed mapping solution \(R_{2}^{temporal}\) is considered as valid if the total cost is reduced (Lines 16-17 in Algorithm 2). ### Complexity Analysis

In this part, the time complexity of the ModPG is analyzed. Firstly, for Algorithm 1, the time complexity of Procedure 1 is \(|\Gamma|\cdot|R|\cdot 2\cdot|R|\cdot log|R|\), in which \(|R|\cdot log|R|\) is the time complexity of the Dijkstra algorithm. Then, for Lines 2-19 in Algorithm 1, all the SFCrs (\(|\Gamma|\)) are traversed in order to identify the SFCr with the smallest set of possible MDCs (\(\gamma_{x}\)). Next, this set is ordered, and in the worst case, three loops are traversed. Thus, the total time complexity is \(|\Gamma|\cdot|R|\cdot 2\cdot|R|\cdot log|R|+|\Gamma|\cdot|R|\cdot log|R|+| \Gamma|\cdot|R|\cdot 4\). The first term comes from Procedure 1. The second term corresponds to the sorting process in Line 7. The last term derives from the minimum operator in Line 3 and the for-loops in Line 9, Line 16, and Line 18. Therefore, the complexity is at the level of O(\(|\Gamma|\cdot|R^{2}|\cdot log|R|\)). Regarding Algorithm 2, for Line 2, the time complexity is \(|R_{1}|\cdot log|R_{1}|\). Then, for Lines 3-17, all MDCs (\(|R_{1}|\)) are traversed. Generally speaking, (\(R>R_{1}\)). Therefore, the total time complexity of ModPG is O(\(|\Gamma|\cdot|R^{2}|\cdot log|R|\)). ## 7 Performance Evaluation

In this section, we evaluate the performance of the proposed ModPG heuristic and compare the results to the original approach. Both solutions were coded in Python. All experiments were performed on a computer with one Intel(R) Core(R) i5-7300U CPU 2.60 GHz and 8 GB of RAM. ### Simulation Setup

The substrate network topology used to evaluate the proposed ModPG heuristic is the same topology used in [13]. There are 100 SARs, 50 MDCs, and 1 CDC. The topology containing the 100 SARs is generated by BRITE[22] based on a Waxman model [23], and then, the 50 MDCs are added to the topology based on a K-means algorithm [24]. The K-means clustering algorithm is used to obtain K clusters of SARs and then to place the K MDCs into their centers to minimize the within-cluster sum of squares. The propagation delay on each link obeys a uniform distribution of (0,2). Similarly to the PG evaluation in [13], in order to obtain the total substrate resource cost Equation (1), all the weighted factors are equally balanced, that is \(\alpha\), \(\beta\), \(\rho\), and \(\varsigma\) are set to one. Different parameter settings for the proposed solution will be evaluated in a future work. Replicating the setting used in [13], each SFCr is composed of four network functions that have to be hosted in MDCs.