## 3 The Proposed Exact Scheme
### Problem Formulation
#### 3.4.3 Constraints of the Problem  
**1. Decomposition Constraint:** Only one decomposition of the service request should be embedded as expressed in Equation (12) below:  
\[\sum_{dc\in s_{dc}}X_{dc}=1 \tag{12}\]  
**2. Virtual Network Function Constraint:** The constraint in Equation (13) is to prevent embedding virtual network functions more than once. It also guarantees that only the nodes from the selected decomposition will be embedded. \[\sum_{f\in F}Y_{N_{u}}^{f}=X_{dc}. \tag{13}\]  
**3. Physical Node Constraint:** If there are two virtualization types \(t,t1\in T\) in the network, then it is not allowed to map a virtual function \(f^{t}\) of the type \(t1\) on physical node \(N_{u}^{tl}\) if \(t\
eq t1\). In addition, the sum of allocated resources \(R_{f}^{k}\) of the type \(k\) for all virtual functions \(f\) that are mapped on \(N_{u}\) must be less than, or equal to, the available resources \(R_{N_{u}}^{k}\) in \(N_{u}\). The constraints in (14) and (15) express that, it is possible to embed any number of virtual functions \(f^{t}\) on physical node \(N_{u}^{tl1}\) only if \(N_{u}\) has enough resources and the function has the same virtualization type of the physical node \(t=t1\). \[ \begin{cases}\sum\limits_{f^{t}\in F}Y_{N_{u}^{tl}}^{f^{t}}=0&;t\
eq t1.\\ \sum\limits_{f^{t}\in F}Y_{N_{u}^{tl}}^{f^{t}}\geq 0&;t=t1.\end{cases} ; \forall N_{u}^{tl1}\in N,\forall dc\in s_{dc},\forall t,t1\in T. \tag{14}\]  
\[\sum\limits_{f\in F}R_{f}^{k}\times Y_{N_{u}}^{f}\leq R_{N_{u}}^{k}\ ; \forall N_{u}\in N,\forall dc\in s_{dc},\forall k\in K. \tag{15}\]  
**4. Path Length Constraint:** For mobile network, the connections between the virtual functions of service might traverse through transmission mediums, which might be with high cost. The path length embedding constraint in Equation (16) determines if it is allowed to embed end-to-end paths on physical paths longer than required. One of the reasons behind high embedding cost is the mapping of virtual links to more than one hub physical link. In the other hand, mapping virtual links to more than one hub physical link might improve the acceptance ratio. This trade-off between the embedding cost and the acceptance ratio can be controlled by the network operator through determining the value of \(h|h\in\{0,1,2,\dots\}\) in Equation (16), where \(h\) value should be equal to the maximum allowed additional hubs to the virtual path length. \[\sum_{e_{ij}\in p}Z_{L_{uv}}^{e_{ij}}\leq len(p)+h;\forall dc\in s_{dc}, \forall p\in P_{e2e},\forall L_{uv}\in L \tag{16}\]  
where \(len(p)\) is the number of virtual links in \(p\). In case, there is a link in \(p\) where both nodes at the two ends of that link have the same virtualization type, both can be embedded to the same physical node. Then, the embedding will be in number of physical links less than \(len(p)\). **5. Unsplitable Path Flow Constraint:** When a virtual link is mapped to more than one physical link, the traffic on that link should not be split in more than one path. Then, if we assume that the outgoing link from a node to next node has a positive sign and the opposite incoming link has a negative sign.