## 2 System Model and Problem Statement
Each VNF \(f\in\mathcal{F}\) is described by the tuple \(f\triangleq(T_{f},\pi_{f},w_{f},\tau_{f})\), where \(T_{f}\) is an identifier of the VNF's functionality (e.g., NAT etc. ), \(\pi_{f}>0\) is the data processing capacity of the VNF (in Mbps), \(w_{f}>0\) is the amount of CPU resources (in GFLOPS) required for the VNF's operation, and \(\tau_{f}>0\) is the data processing **delay** experienced by an individual data packet as it passes through the VNF. To ensure proper service endpoints, we also introduce the set \(\mathcal{F}_{dum}\triangleq\{f_{dum1},f_{dum2}\}\) of two \"dummy\" VNFs and include it into \(\mathcal{F}\). The VNFs \(f\in\mathcal{F}_{dum}\subseteq\mathcal{F}\) are characterized by \(\pi_{f}=\infty\), \(w_{f}=0\), \(\tau_{f}=0\), which implies that the \"dummy\" VNFs work transparently, w.r.t., our model. Let \(\mathcal{C}\) be the set of SFCs, where SFC \(\rho\in\mathcal{C}\) is described by the **ordered** sequence \(\rho\triangleq\langle f_{dum1},f_{1}^{(\rho)},\dots,\)\(f_{N_{\rho}}^{(\rho)},f_{dum2}\rangle\), where \(N_{\rho}\) is the number of non-dummy VNFs in \(\rho\) and \(f_{i}^{(\rho)}\in\mathcal{F}\setminus\mathcal{F}_{dum}\). The traffic of \(\rho\) is **properly served only if** it passes through the VNFs in \(\rho\)**exactly matching the specified order**. We also write \(f\rightsquigarrow\rho\) to state that VNF \(f\) is contained in \(\rho\) and define \(\mathcal{R}_{\rho}\triangleq\{f\in\mathcal{F}:f\rightsquigarrow\rho\}\). An equivalent description for \(\rho\) is via a **directed** graph \(\mathcal{G}^{(\rho)}(\mathcal{V}^{(\rho)},\mathcal{E}^{(\rho)})\) with the virtual node set \(\mathcal{V}^{(\rho)}\triangleq\{f_{dum1},f_{1}^{(\rho)},f_{2}^{(\rho)},\dots, f_{N_{\rho}}^{(\rho)},f_{dum2}\}\) (i.e., each VNF \(f\rightsquigarrow\rho\) is a node of \(\mathcal{V}^{(\rho)}\)) and the virtual edge set \(\mathcal{E}^{(\rho)}=\left\{\left(f_{dum1},f_{1}^{(\rho)}\right),\left(f_{i} ^{(\rho)},f_{i+1}^{(\rho)}\right)_{1\leq i\leq N_{\rho}-1}\left(f_{N_{\rho}}^ {(\rho)},f_{dum2}\right)\right\}\) describing the relative order of the VNFs (see bottom part of Figure 2 for an example of such a virtual graph). For any virtual edge \(e^{\prime}\in\mathcal{E}^{(\rho)}\), we denote with \(h(e^{\prime})\), \(t(e^{\prime})\in\mathcal{F}\) the respective VNFs at the head and tail of \(e^{\prime}\). Figure 2: Embedding of virtual network (bottom part) into the physical network (top part). For illustration, 2 distinct SFCs are shown (in green and red) corresponding to 2 different UE requests, and each SFC is described by its own virtual network. \(\mathcal{G}^{(\rho_{1})}\) (green color) contains 6 virtual nodes and 5 virtual edges, whereas \(\mathcal{G}^{(\rho_{2})}\) contains 5 virtual nodes and 4 virtual edges. The virtual nodes will be mapped to actual physical nodes, while the virtual edges will be mapped to actual paths in the physical network. Each UE \(j\in\mathcal{J}\) requests a service type \(q_{j}\in\mathcal{Q}\), with \(q_{j}\triangleq(s_{q_{j}},r_{q_{j}},\delta_{q_{j}},\rho_{q_{j}})\), where \(s_{q_{j}}\in\mathcal{V}\) is the \"source\" node of the service (the \"destination\" node of service \(q_{j}\) is UE \(j\)), \(r_{q_{j}}>0\) is the E2E required throughput, \(\delta_{q_{j}}>0\) is the E2E maximum allowed latency, and \(\rho_{q_{j}}\in\mathcal{C}\) is the required SFC. We explicitly allow for sharing a VNF instance among two (or more) different SFCs, provided the VNF can meet the requirements imposed by the aggregate traffic of the services sharing this VNF. Furthermore, for each UE \(j\), we use our knowledge (or estimates) of the Signal to Interference plus Noise Ratio (SINR) \(\sigma_{a,j}\) of link \((a,j)\in\mathcal{E}_{AN}\) and the requested service rate \(r_{q_{j}}\) to compute the number of RBs \(N_{a,j}^{(RB)}\) needed to achieve this rate on link \((a,j)\). Assuming frequency-flat slow fading [25], we consider the simple case of uniform BS power allocation among the RBs, so that each RB is assigned a power of \(p_{a}^{(RB)}\).