# VNF Placement Optimization at the Edge and Cloud +
## 4 Algorithm Design
### Mixed Integer Programming (MIP) Formulation  
In order to jointly minimize all the set of requirements (e.g., deployment cost, delay, resource utilization, etc.), we introduce a Mixed Integer Programming (MIP) formulation. Two variables are defined:  
\(x_{u}^{s_{k}^{i}}\): a binary variable set to \(1\) if the VNF \(s_{k}^{i}\) is allocated on the server \(u\in N\).  
\(y_{uv}^{s_{k}^{i}s_{k^{\prime}}^{i}}\): the amount of traffic that flows between the \(s_{k}^{i},s_{k^{\prime}}^{i}\) VNFs that is routed over the link \((u,v)\in E\).  
_Objective:_  
\[\begin{split} min\_\{x,y\}:\sum_{s_{k}^{i}\in S^{i}}\sum_{n\in N }A_{n}\cdot x_{n}^{s_{k}^{i}}+\\ \sum_{s_{k}^{i}\in S^{i}}\sum_{k^{\prime}>k,s_{k^{\prime}}^{i} \in S^{i}}\sum_{(u,v)\in E}B_{uv}\cdot y_{uv}^{s_{k}^{i}s_{k^{\prime}}^{i}}+ \\ \sum_{s_{k}^{i}\in S^{i}}\sum_{n\in N}(d_{pr}(s_{k}^{i})+d_{q}( n))\cdot x_{n}^{s_{k}^{i}}+\\ \sum_{s_{k}^{i}\in S^{i}}\sum_{k^{\prime}>k,s_{k^{\prime}}^{i} \in S^{i}}\sum_{(u,v)\in E}(d_{p}(u,v)+d_{tr}(u,v))\cdot y_{uv}^{s_{k}^{i}s_{ k^{\prime}}^{i}}.\end{split} \tag{1}\]  
The goal of the Objective \(1\) is as follows:  
* Regarding the first two terms, it tries to minimize the number of computational and communication resources for placing the SC. This way, the overall deployment cost will be minimized.
* The weights \(A_{n}\) and \(B_{uv}\) are included to guarantee load balancing among the available resources and are set equal to the inverse values of the available capacity of the servers \(n\) and links \((u,v)\). To this end, we will avoid selecting only MEC resources that will lead to lower costs and appropriately offload traffic to the Cloud.
* For the third and fourth term, it tries to minimize the total delay experienced in the SC paths by selecting VNFs with minimum queuing and processing delays and links with minimum transmission and propagation delays.  
The objective function is minimized subject to the following constraints. First of all, we need to ensure that the MEC and Cloud resources will not be oversubscribed (Equations (2) and (3)):  
\[\sum_{s_{k}^{i}\in S^{i}}\mathbf{D}(s_{k}^{i})\cdot x_{n}^{s_{k}^{i}}\leq \mathbf{R}(n),\forall n\in N, \tag{2}\]  
\[\sum_{s_{k}^{i}\in S^{i}}\sum_{k^{\prime}>k,s_{k^{\prime}}^{i}\in S^{i}}(y_{ uv}^{s_{k}^{i}s_{k^{\prime}}^{i}}+y_{uu}^{s_{k}^{i}s_{k^{\prime}}^{i}})\leq b(u,v), \forall(u,v)\in E^{\prime}. \tag{3}\]  
The next constraint respects flow conservation conditions, where the sources and sinks of the flows are considered, the servers that host consecutive VNFs (Equation (4)). We need to mention that the particular constraint allows path splitting towards providing a more efficient load balancing approach:  
\[\begin{split}\sum_{v\in V}y_{uv}^{s_{k}^{i}s_{k^{\prime}}^{i}}- \sum_{v\in V}y_{vu}^{s_{k}^{i}s_{k^{\prime}}^{i}}=w(S^{i})\cdot z(s_{k}^{i}) \cdot(x_{n}^{s_{k}^{i}}-x_{n}^{s_{k^{\prime}}^{i}}),\\ \forall s_{k}^{i},s_{k^{\prime}}^{i}\in S^{i},\forall u\in V.\end{split} \tag{4}\]Finally, we need to ensure that each VNF will be placed at only one node (Equation (5)), provided that the specific node is a server (Equation (6)) and satisfies the location constraint of the VNF (Equation (7)):  
\[\sum_{v\in V}x_{v}^{i}=1,\forall s_{k}^{i}\in S^{i}, \tag{5}\] \[\sum_{q\in Q}x_{q}^{s_{k}}=0,\forall s_{k}^{i}\in S^{i},\] (6) \[\sum_{v\
otin T}x_{v}^{s_{k}}=0,\forall s_{k}^{i}\in S^{i}. \tag{7}\]