## 4 Problem Statement
### SFC Request  
An SFC request (SFCr) consists of a set of VNF requests (VNFr): a set of VNFs that have to be placed in MDCs and a set of VNFs that have to be placed in the CDC. A six-tuple \((p_{\gamma},\Phi_{\gamma},\Psi_{\gamma},E_{\gamma}^{\gamma},D_{\gamma}^{MDC},D _{\gamma}^{CDC})\) is used to define an SFCr \(\gamma\), where \(p_{\gamma}\) indicates the SAR of SFCr, \(\Phi_{\gamma}\) indicates the part of the SFCr that should be placed in MDCs, and \(\Psi_{\gamma}\) indicates the part of the SFCr that should be in CDC. \(E_{\gamma}^{\gamma}\) indicates the logical links (that is, the order) between the VNFrs, and \(D_{\gamma}^{MDC}\) is a latency constraint that limits the tolerated propagation latency from SAR to MDC, while \(D_{\gamma}^{CDC}\) is the latency constraint that limits the tolerated propagation latency from SAR to CDC. \begin{table}
\begin{tabular}{l l} \hline \((P,R,G,E^{5})\) & 4-tuple substrate network \\ \hline \(n_{u}^{S}\) & A substrate node in the substrate network \\ \hline \((n_{\
u}^{S},n_{\
u}^{S})\) & The substrate link between the substrate nodes \(n_{u}^{S}\) and \(n_{\
u}^{S}\) \\ \hline \(d_{n_{u}^{S},n_{\
u}^{S}}\) & The propagation delay of substrate link \((n_{\
u}^{S},n_{\
u}^{S})\) \\ \hline \(C_{link}^{(n_{\
u}^{S},n_{\
u}^{S})}\) & The link capacity of substrate link \((n_{\
u}^{S},n_{\
u}^{S})\) \\ \hline \(C_{CPU}^{n_{u}^{S}}C_{mem}^{n_{u}^{S}}\) & The CPU and memory resources of substrate node \(n_{u}^{S}\) \\ \hline \(\Gamma\) & The SFCr set \\ \hline \multirow{4}{*}{\((p_{\gamma},\Phi_{\gamma},\Psi_{\gamma},E_{\gamma}^{\gamma},D_{\gamma}^{ MDC},D_{\gamma}^{CDC})\)} & 6-tuple description: \(p_{\gamma}\) indicates the SAR of SFCr; \(\Phi_{\gamma}\) indicates the part of the SFCr that should be placed in MDCs; \(\Psi_{\gamma}\) indicates the part of the SFCr that should be in CDC; \(E_{\gamma}^{\gamma}\) indicates the logical links (that is, the order) between the VNFrs; \(D_{\gamma}^{MDC}\) is a latency constraint that limits the tolerated propagation latency from SAR to MDC; and \(D_{\gamma}^{CDC}\) is the latency constraint that limits the tolerated propagation latency from SAR to CDC \\ \hline \(n_{i}^{p}\) & A VNFr involved in an SFCr that demands CPU and memory resources \\ \hline \((n_{i}^{p},n_{\
u}^{p})\) & The logical link between \(n_{i}^{p}\) and \(n_{\
u}^{p}\), two consecutive VNFrs in an SFCr \\ \hline \(CPU_{\gamma,n_{\
u}^{p}},mem_{\gamma,n_{\
u}^{p}}\) & The CPU and memory consumption of VNFr \(n_{i}^{p}\) in SFCr \(\gamma\) \\ \hline \(BRC_{i}^{CPU},BRC_{\lambda}^{mem}\) & The CPU and memory BRCs when instantiating a new VNF \\ \hline \multirow{4}{*}{\(\lambda\) on one MDC or CDC} \\ \cline{2-2}  & \(\lambda\) on one MDC or CDC \\ \cline{2-2}  & \\ \end{tabular}
\end{table} 
Table 1: Notations. The problem statement only considers propagation delay. As pointed out in [13], other delays such as queueing and processing delays, defining the time needed by the packets related to a VNFr to pass through a VNF instance, could be included in the formulation. Moreover, an adequate modeling and parameter setting of these times needs to be included in the proposed heuristics. The recent work [20] surveyed the literature about delay-aware resource allocation in NFV. The inclusion of this technical aspect will be considered in future versions of this work. Each VNFr \(n_{i}^{p}\) involved in an SFCr \(\gamma\) demands computing resources in terms of CPU and memory: \(CPU_{\gamma,n_{i}^{e}}\), \(mem_{\gamma,n_{i}^{p}}\), respectively. This work assumes multi-tenancy software technology. A substrate node, which can host different types of VNFs, can also host multiple VNFs of the same type. To run a particular VNF type in a node, some basic resources are needed. These Basic Resource Consumptions (BRCs) when instantiating a VNF type in a node are considered fixed and independent of the number of VNFrs of this type. The CPU and memory BRCs when instantiating a new VNF \(\lambda\) on one MDC or CDC are \(BRC_{\lambda}^{CPU}\) and \(BRC_{\lambda}^{mem}\), respectively.