## 5 Shortcomings of the Priority-Based SFCr Mapping Algorithm in the PG Heuristic
The priority-based SFCr mapping algorithm of the PG heuristic assumes that, although the memory and CPU capacities of the substrate nodes are limited, there will always be an available MDC that allows the fulfillment of the latency restrictions with enough resources to locate any SFCr of the total set. However, this assumption is rather unrealistic in real scenarios. There may be resources available on the network, but none of them meet the delay restrictions. The non-fulfillment of this assumption, the priority order definition focused on MDCs, and the redefinition of the priority of pending R-SFCrs affect the probability of SFCr mapping failure. An SFCr is marked as poor if the number of possible MDCs is equal to one or rich if this number is higher than one, without considering the number of possible MDCs. Thus, an originally marked R-SFCr with a high number of possible MDCs may be mapped before an R-SFCr with a low number of possible MDCs (which has fewer options to be mapped), only because the priority of the MDC of the former R-SFCrs was higher due to the number of P-SFCrs. Figure 2c illustrates the situation described above. Although the amount of SFCrs that can be mapped on an MDC depends on the MDC resources and the requested resources demanded by the VNFrs composing the SFCrs, by way of example, we consider that MDCs have the CPU and memory resources to accommodate seven SFCs at most. This assumption is used in order to simplify the scenario and to facilitate the problem identification and description. Firstly, MDC2 is processed: five P-SFCrs and two of the six R-SFCrs (SFC\({}_{E}\) and SFC\({}_{K}\)) are mapped on it. The rest of the R-SFCrs (SFC\({}_{A}\), SFC\({}_{B}\), SFC\({}_{G}\), and SFC\({}_{F}\)) have to be mapped on other MDCs. Next, MDC4 is processed: After four P-SFCrs are mapped, the following mapped one is SFC\({}_{A}\). Although it is at the end of the possibly mapped list, it is treated with the same priority as the poor SFCrs (and consequently, with more priority than rich SFCrs of this MDC) because it is a pending SFCr of a previously processed MDC (in this case, MDC2). Finally, SFC\({}_{N}\) and SFC\({}_{I}\) are mapped on MDC2. Following the same procedure, the rest of the MDCs are processed. It can be seen that, at the end of the mapping process, SFC\({}_{D}\) and SFC\({}_{G}\) are not mapped on any MDC. In detail, SFC\({}_{D}\) (a rich SFCr, but with only two possible MDCs) could have been mapped on MDC4, but SFC\({}_{A}\) (a rich SFCr with four possible MDCs) was mapped instead because of the priority redefinition of pending requests. However, SFC\({}_{A}\) could have been mapped on MDC1 or MD3, which have available resources, allowing the mapping of SFC\({}_{D}\). Coming back to the PG heuristic, once the priority-based SFCr mapping algorithm finishes, a second stage called the VNFr merging algorithm is executed. In summary, starting from the mapping result of the first stage, the VNFr merging algorithm tries to move and merge VNFrs of the same type to reduce the number of VNF instances and consequently BRCs. During this second stage, the movement of VNFrs is done if the delay and resource restrictions of SFCrs are fulfilled, link and node resources are not violated, and the total cost is reduced.