## 4 Label Setting Based Heuristic
### Notations  
We report in Table 1 the main notations. Let us represent the cloud/network infrastructure with the graph \(G_{o}=(V_{s},L_{o})\) where \(V_{s}\) is the node set and \(L_{o}\) is the network link set. \(V_{s}\) is given by the union of the sets \(V_{o}\) and \(V_{NFVI-PoP}\). \(V_{o}\) is the set of optical switches while \(V_{NFVI-PoP}\) is the set of NFVI-PoPs in which the VMs are executed. The main parameters of the optical network and their definitions are the following: \(L_{e}\) is the fiber length of the link \(e\in L\); \(c_{b}\) is the bandwidth cost unit expressed in \((\$/GHzZmhour)\); \(\Psi\) is the set of the network paths; \(B_{FS}\) is the bandwidth (Hz) of a Frequency Slot (FS). The VMs supporting the Service Functions (SF) are executed in the NFVI-PoPs. We assume that \(K\) types of VMs can be executed according to the corresponding SF. The type \(h\)-th \((h=1,\cdots,K)\) VM is characterized by the maximum processing capacity \(C_{p,h}\)\((h=1,\cdots,K)\) and the allocation of \(n_{h}^{c}\)\((h=1,\cdots,K)\) cores. We also assume that the VMs can be migrated between NFVI-PoPs and that, when the traffic decreases, vertical scaling techniques can be applied by linearly reducing the VM processing capacity and proportionally the number of allocated cores. We also introduce the parameter \(c_{v}^{core}\) defined as the cost of renting a VM for one hour in the NFVI-PoP \(v\in V_{NFVI-PoP}\). The support of a given number of Service Function Chains (SFC) involve the construction of the Virtual Network Function Forwarding Graph (VNFFG) \(G_{v}=(V_{VM},L_{v})\)[28], a virtual graph where \(V_{VM}\) is a set of VMs to be instantiated in NFVI-PoPs and \(L_{v}\) is a set of virtual links to be supported by network paths. Let \(\gamma_{h,v}\) be a binary parameter assuming the value \(1\) if the VM \(v\in V_{VM}\) is of \(k\)-th type, otherwise its value is \(0\). In the traffic state \(S\) the VNFFG is characterized by the following parameters: \(f_{v}(S)\) is the bandwidth requested by the virtual node \(v\in V_{VM}\) in the traffic state \(S\); \(f_{l}(S)\) is the bandwidth requested by the virtual link \(l\in L_{v}\) in the traffic state \(S\). The proposed heuristic has the objective of evaluating in each traffic state \(S\) an embedding \(\Gamma\) that determines in which NFVI-PoPs and network paths, the nodes \(v\in V_{VM}\) and link \(l\in L_{v}\) have to be supported respectively. The embedding is characterized by the following parameters: \(x_{vw}^{\Gamma}(S)\) assumes the value \(1\) if the VM \(w\in V_{VM}\) is executed in the NFVI-PoP \(v\in V_{NFVI-PoP}\), otherwise its value is \(0\) \begin{table}
\begin{tabular}{l l} \hline \hline
**Parameter** & **Definition** \\ \hline \(V_{o}\) & Set of optical switches \\ \(V_{NFVI-PoP}\) & Set of NFVI-PoPs \\ \(L_{o}\) & Set of Network Links \\ \(L_{e}\) & Length of the link \(e\in L_{o}\) \\ \(c_{b}\) & Bandwidth Cost Unit \\ \(\Psi\) & Set of network paths \\ \(B_{FS}\) & Bandwidth of a Slot Frequency \\ \(F\) & Number of Service Functions (SF) types that can be executed in the NFVI-PoP \\ \(C_{p,h}\) & Maximum processing capacity of the i-\(th\) type VM \\ \(n_{h}^{c}\) & Number of cores to be allocated to a i-\(th\) type VM \\ \(c_{v}^{core}\) & Cost unit of renting for one hour one processing core in the NFVI-PoP \(v\in V_{NFVI-PoP}\) \\ \(V_{VM}\) & Set of VMs \\ \(L_{o}\) & Set of Virtual Links \\ \(f_{v}(S)\) & Bandwidth requested by the virtual node \(v\in V_{VM}\) in the traffic state \(S\) \\ \(f_{l}(S)\) & Bandwidth requested by the virtual link \(l\in L_{v}\) in the traffic state \(S\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: NFVI-PoP Infrastructure and network Parameters. \(y_{pl}^{\Gamma}(S)\) assumes the value \(1\) if the virtual link \(l\in L_{v}\) is routed on the network path \(p\in\Psi\), otherwise its value is \(0\). The choice of one embedding leads to the consumption of cloud and bandwidth resources.