## 6 Modified Priority-Based Greedy Heuristic
### ModPG-SFCr Mapping Algorithm

The PG heuristic is based on the definition of a set of clusters to which the SFCrs will be assigned, and then, the features of each cluster determine the order in which the SFCrs are mapped to MDCs. In contrast to the PG, the mapping order of the SFCrs is determined by their own SFCrs and the set of possible MDCs that are associated with each one (Line 1 in Algorithm 1). In Procedure 1 (Algorithm 2), the SAR, the location of MDCs, the CDC in the substrate network, and the delay requirements of each SFCr are considered to check if the SFCr could be mapped on a particular MDC. For each SFCr, the propagation delay from its SAR to each MDC and the propagation delay from a certain MDC to the CDC are calculated using the shortest path algorithm (Lines 5-6 in Procedure 1). If the selection of a particular MDC fulfills the delay requirements, the MDC is considered a possible MDC to map the SFCr (Line 9 in Procedure 1). ```
1 Procedure 1:\(\text{classify}(\Gamma)\) ;
2 for\(\gamma\)in\(\Gamma\)do
3 set_possible_MDC(\(\gamma\))=empty ;
4 for\(MDC_{j}\)in\(R\)do
5 obtain \(\text{delay}(SAR_{\gamma},MDC_{j})\) using Dijkstra alg. ;
6 obtain \(\text{delay}(MDC_{j},CDC)\) using Dijkstra alg. ;
7 total_delay=delay(\(SAR_{\gamma},MDC_{j}\))+delay(\(MDC_{j},CDC\));
8 if\(\text{delay}(SAR_{\gamma},MDC_{j}\))<\(D_{\gamma}^{MDC}\)and total_delay<\(D_{\gamma}^{CDC}\)then
9 add (\(MDC_{j}\),total_delay) to set_possible_MDC(\(\gamma\)) ;
```

**Procedure 1:** SFCr classification procedure. After obtaining the sets of possible MDCs associated with each SFCr, the SFCr mapping process begins. The SFCr with the minimum set of potential MDCs is selected (Line 3 in Algorithm 1). It is referred to as \(\gamma_{x}\). \(\textit{set\_possible\_MDC}(\gamma_{x})\) is ordered from smallest to highest total propagation delay (Line 7 in Algorithm 1), and then, the first potential MDC with enough CPU and memory resources for mapping the SFCr is selected (Lines 9-14 in Algorithm 1). If necessary, new VNFs will be instantiated in the selected MDC (\(n_{i}^{S}\)) (Line 11 in Algorithm 1). As described in Section 5, the PG mapping algorithm in [13] was defined assuming that there is always a potential MDC with enough available resources to host all the VNFs of the SFCr that fulfills the delay requirements. The ModPG algorithm does not adopt this strong assumption. Therefore, if the SFCr being processed cannot be mapped on one of the potential MDCs entirely, the possibility of mapping the VNFs on multiple MDCs is considered (Lines 15-18 in Algorithm 1). In this process, the resource availability of potential MDCs in \(\textit{set\_possible\_MDC}(\gamma_{x})\) is analyzed, and then, the MDC that maximizes the number of consecutive VNFs of \(\gamma_{x}\) that can be mapped is selected. Next, taking into account the topology and delay restrictions imposed by the SFCr, additional MDCs that allow the mapping of the remaining VNFs are located. In order to minimize the BRC cost, this process is executed in two stages. Firstly (Line 16 in Algorithm 1), only MDCs where required VNFs are already instantiated are considered. If the mapping process fails, then this restriction is removed (Line 18 in Algorithm 1), and VNFs are instantiated if required. Once the set of SFCrs (\(\Gamma\)) is processed, the total cost of the resulting mapping solution (\(TC_{1}\)) is obtained by applying Equation (1) (Line 19 in Algorithm 1). ### ModPG-VNFr Merging Algorithm

Due to the fact that the mapping algorithm tries to minimize the delay and bandwidth cost by mapping, all the VNFrs of an SFCr are mapped on the same MDC whenever possible (Lines 8-14 in Algorithm 1) or on a reduced number of MDCs (Lines 15-18 in Algorithm 1). As a consequence, multiple instantiations of the same type of VNF are distributed in the network. That is, the volume of BRCs is not optimal. In addition, the result of the mapping algorithm does not optimize another relevant cost, the cost due to the activation of MDCs (the last term in Equation (1)).