# Scheduling for Media Function Virtualization
## 4 System Model and Algorithm
### Problem Complexity  
Next, we analyze the complexity of the VMF-FG scheduling problem and show its NP-completeness. To this end, we formulate an instance of the VMF-FG scheduling problem as an ILP model. As the simpler instance of the problem is hard to solve, it can be inferred that the complete VMF-FG scheduling problem would be much harder to solve. Figure 3: An overview of the VMF-FG scheduling problem. Let us consider a VMF-FG with a total of \(|\mathcal{L}|\) virtual links where a virtual link is denoted by \((f_{i},f_{j})\). The following is the ILP formulation for the VMF-FG scheduling problem instance. \begin{table}
\begin{tabular}{p{113.8 pt} p{113.8 pt}} \hline
**Notation** & **Description** \\ \hline \(\mathcal{G}=(\mathcal{F},\mathcal{L})\) & VMF-FG representation of a media service, where \(\mathcal{F}\) and \(\mathcal{L}\) are the set of VMF and virtual links, respectively. \\ \hline \(G^{I}=(N,E)\) & Directed graph representation of the MFVi network infrastructure, where \(N\) is the set of nodes and \(E\) is the set of physical links between the nodes. \\ \hline \(R_{frame}\) & Number of frames transmitted per second on a media stream. \\ \hline \(T_{c}\) & Cycle time. \\ \hline \(N_{c}\) & Set of all server nodes (\(N_{c}\subset N\)), i.e., nodes with compute resources. \\ \hline \(C\) & The set of all cycles in a hypercycle. \\ \hline \(bw_{n_{u},n_{v},c}^{f_{i},f_{j},p}\) & The decision variable of the ILP formulation denotes the amount of bandwidth (in bytes) allocated to virtual link \((f_{i},f_{j})\) on physical link \((n_{u},n_{v})\) of path \(p\) during cycle \(c\). \\ \hline \(x_{p}^{f_{i},f_{j}}\) & The decision variable of the ILP formulation indicates if virtual link \((f_{i},f_{j})\) is mapped to a physical path or not. \\ \hline \(bw_{n_{u},n_{v},c}\) & Available bandwidth (in bytes) on physical link \((n_{u},n_{v})\in E\) during cycle \(c\in C\). \\ \hline DwstrNbrs \((\mathcal{G},f)\) & The procedure returns a list of all downstream neighbors of \(f\) in VMF-FG \(\mathcal{G}\). \\ \hline UpstrNbrs \((\mathcal{G},f)\) & The procedure returns a list of all downstream neighbors of \(f\) in VMF-FG \(\mathcal{G}\). \\ \hline Pths \((G^{I},n_{1},n_{2},K)\) & The procedure returns \(K\) shortest paths between \(n_{1}\) and \(n_{2}\) in \(G^{I}\). \\ \hline PthDel \((G^{I},p)\) & The procedure returns the delay along \(p\) in \(G^{I}\). \\ \hline CpuSch \((f,n,t_{1},t_{2})\) & The procedure returns a core, if free, on node \(n\) where \(f\) can be scheduled between \(t_{1}\) and \(t_{2}\). \\ \hline GridAlloc \((bw,\omega,n_{1},n_{2},t)\) & The procedure returns the CSQF schedule for physical link \((n_{1},n_{2})\) and the possible start and end cycle in the schedule; the bandwidth requirement is \(bw\) and the maximum end cycle is \(t\). \\ \hline PthSch \((s_{link},p)\) & The procedure checks if schedule \(s_{link}\) on link \(lnk\) is compatible with other links in path \(p\); if yes, it returns the schedule for the full path. \\ \hline \(\alpha\) & The variable denotes the node and core assignment of VMFs. \\ \hline \(\gamma\) & The variable denotes the physical path assignment of virtual links. \\ \hline \(\omega\) & The variable denotes the schedule assignment of virtual links. \\ \hline \end{tabular}
\end{table} 
Table 1: Description of the notations used for different parameters and variables involved in the system model. \[\max_{p\in\texttt{Pthhs}(G^{l},n(f_{j}),n(f_{j}),K)}x_{p}^{f_{i}f_{j}}\] \[st:\sum_{ \begin{subarray}{c}\forall(f_{i},f_{j})\in\mathcal{L}\\ p\in\texttt{Pths}(G^{l},n(f_{i}),n(f_{j}),K)\\ \langle n_{u},n_{v}\rangle\in p\end{subarray}