## 5 Shortcomings of the Priority-Based SFCr Mapping Algorithm in the PG Heuristic  
As its name implies, the priority-based greedy heuristic makes use of the concept of priority to define and implement a VNF placement solution. This solution is based on two stages: firstly,an SFCr mapping algorithm is executed, and then, a VNFr merging algorithm is applied. The concept of priority is employed in the first stage, the SFCr mapping algorithm, the of which objective is to map all the VNFrs of an SFCr on a particular MDC and the CDC (only one CDC is considered in the system model). The concept of priority is used to establish a mapping order. An expected solution would have been to associate the term \"priority\" directly with the SFCrs, obtaining an ordered list of the full set of SFCrs before being mapped. However, in the PG heuristic, the \"priority\" parameter is employed to indicate in which order the MDCs are going to be processed with the aim of the \"greedy\" use of its resources to map all possible SFCrs. Before starting the mapping process, the total set of SFCrs is processed to identify the subset of MDCs to which each SFCrs could be mapped, taking into account the delay restrictions. Considering a particular SFCr, the substrate network, and its SAR, the SFCr is assigned as a potentially mapped SFCr to a particular MDC if the latency requirement \(D_{\gamma}^{M}\) is met. As a result of this procedure, an SFCr might be assigned to just one MDC (if only one MDC fulfills the latency requirement) or to more than one MDC. As can be seen in the example shown in Figure 2a, SFC\({}_{A}\) is assigned as the potentially mapped SFCr to MDC1, MDC2, MDC3, and MDC4, while SFC\({}_{3}\) is only attached to MDC1. Based on the number of candidate MDCs, the SFCrs are cataloged as Poor SFCrs (P-SFCrs) or Rich SFCrs (R-SFCrs): a poor SFCr only has a candidate MDC, while a rich SFcr has more than one candidate. Once the set of potentially mapped SFCrs assigned to each MDC is obtained and the SFCrs have been classified as P-SFCrs or R-SFCrs, this information is used to establish the order of priority for MDCs to be processed. This processing priority value is obtained according to the number of P-SFCrs:  
Figure 2: Example of priority-based mapping algorithm execution. Five MDCs and a set of 30 SFCrs are considered. It is assumed that the MDCs have CPU and memory resources to accommodate seven SFCs at most. (**a**) shows the assignment of possibly mapped SFCrs to each MDC taking into account the delay restrictions. The SFCrs that are only assigned to one possible MDC (P-SFCrs) are shown in blue and the R-SFCrs in green. (**b**) shows the MDC processing priority order (from left to right). Finally, (**c**) shows the result of the mapping algorithm. The SFCrs with a number on the left are mapped ones. The SFCrs without a number and that are not crossed out are pending SFCrs that will be considered in subsequent MDCs, and crossed out SFCrs indicate SFCrs that have been already mapped in previous MDCs. the more P-SFCrs, the higher the processing order. Figure 2b shows the MDC process order, from left to right. For each processed MDC, the potentially mapped P-SFCrs are mapped in the first place. Next, the R-SFCrs are mapped, using the minimum distance from the SAR to the MDC as the selection parameter. If more than one R-SFCr coincides on this parameter, the R-SFCr whose VNFrs have less difference from the existing VNFs in the MDC is chosen to be mapped firstly. The R-SFCrs that cannot be mapped on the current MDC due to the shortage of resources are left to be mapped on any subsequent MDC. However, it is also important to emphasize that, in this case, the R-SFCrs will be processed in a subsequent MDC with equal priority as the P-SFCrs in that MDC. According to this redefinition, the pending R-SFCrs of an already processed MDC will be mapped as soon as possible. However, this introduces a penalty to the R-SFCs of the currently processed MDC, as described below.