## 4 Label Setting Based Heuristic
### Heuristic Description  
Given the complexity of the optimization problem, which allows us to solve the problem only for small network scenarios, we defined a heuristic composed of two procedures applied in sequence. A first procedure, called NFV/Optical Resource Reconfiguration (NORR) heuristic, and a second procedure, called Optical Network Remapping Costs and Reconfigurations Aware (ONRCRA) heuristic. The objective of the NORR heuristic, described in [16], is to find in each h-th (\(h=0,\cdots,T-1\)) SI an embedding \(\Gamma^{(h)}\) of the VNFFG, so that the total processing and bandwidth cost \(C^{(h)}\) is minimized. In this first phase, the reconfiguration costs of transition from one embedding to another are not taken into account. The ONRCRA heuristic takes the embeddings of the set \(\Theta=\{\Gamma^{(0)},\Gamma^{(1)},\cdots,\Gamma^{(T-1)}\}\) calculated by the NORR procedure, and creates a multistage graph, of which two examples are given in Figure 2a,c. Each node of the graph represents an embedding belonging to the set \(\Theta\) that is admissible for that particular SI, and is labeled with the associated cost, calculated in the first step. Each edge represents the transition from one embedding to another and is labeled with the number of reconfigurations to be performed on the optical switches, whose value is calculated by ONRCRA heuristic. Once the multistage graph has been created, the final objective of the ONRCRA heuristic is to calculate on it the sequence \(\Sigma^{opt}=\{\Psi_{0},\Psi_{1},\cdots,\Psi_{T-1}\}\) of embeddings to be applied in the entire time interval, such that the total cost (which is the sum of the costs of the chosen embeddings) is minimized, but not exceeding the preset number of reconfigurations. In finding the solution, therefore, the ONRCRA heuristic will take into account that the transition from a certain embedding to another could cause many reconfigurations of the optical paths and therefore a high bit loss; for this reason, embeddings with the lowest cost will not necessarily be selected in the final solution. The resolution of this problem is identified in literature as Weight Constrained Shortest Path Problem (WCSPP) [17]: given a directed graph which has cost and a weight associated to each edge, the WCSPP consists of finding the least-cost path between two specified nodes, such that the total sum of weights is less than a specified value. The algorithm chosen for the WCSPP solution is the Label Setting Algorithm [17], an implicit enumeration algorithm which leads to an optimal solution, generalized from the one given by [PERSON]. Its name derives from the fact that it is an algorithm that uses labels to iteratively explore the graph keeping track of the possible paths that respect the constraint on the maximum number of reconfigurations. Each label contains two values: the total cost, equal to the sum of the costs of the embeddings selected up to that point, and the number of reconfigurations, the sum of all the reconfigurations determined by the path considered. Starting from a single label in the first node, at each iteration the minimum-cost label is expanded in the direction of the next SI, and the procedure is repeated until the last SI is reached; if the number of reconfigurations exceeds the maximum allowed value, the label is discarded (and along with it the associated path). The label that reaches one of the nodes of the last SI, will be the one that identifies the path at minimum cost and such that the constraint on the number of reconfigurations is respected. Two examples of execution of the Label Setting algorithm are described for the multi-stage graphs illustrated in Figure 2a,c respectively. The steps of the algorithm are described in Figure 2b,d respectively. The darker label is the one selected to be extended in next iteration of the algorithm and the thick lines are the directions of extension in the graph. The maximum number of switch reconfigurations is assumed to be 10 for both scenarios.