## 3 The Proposed Exact Scheme
### Path Identification  
Path identification has two purposes: (1) to minimize the number of candidate physical links in the input of the placement algorithm in order to enhance the execution time; and (2) to avoid mapping virtual links to long physical paths in order to minimize and control the embedding cost. Therefore, path identification is formulated as follows.  
A physical edge between two adjacent nodes \(N_{u}\) and \(N_{v}\), where \(u,v\in m\) is denoted by \(E_{uv}\). Then, a simple path between \(N_{u}\) and \(N_{v}\) is denoted by \(P_{uv}\). If \(N_{v}\) is not adjacent to \(N_{u}\), the path between them will be a sequence of edges from source to destination as expressed in Equation (1) below:  
\[P_{uv}=[E_{ux_{1}},E_{x_{1}x_{2}},\ldots,E_{x_{n-1}x_{n}},E_{x_{nv}}], \tag{1}\]  
where \(u,x_{1},x_{2},x_{n-1},x_{n},v\in m\). While the edge \(E_{uv}\) can be expressed as a tuple of nodes at both ends of the edges, so it can be expressed by \(E_{uv}=(N_{u},N_{v})\) and \(P_{uv}\) as in Equation (2).  
\[P_{uv}=[N_{u},N_{x_{1}},N_{x_{2}},\ldots,N_{x_{n-1}},N_{n},N_{v}]. \tag{2}\]  
Whenever physical nodes have constant attributes, it is possible to identify simple paths using those constant attributes. One of the attributes (that are shared between physical nodes and virtual nodes of service requests) is the virtualization technique type. Thus, the virtualization technique type of each node in path \(P_{uv}\) as expressed in Equation (2) is used to identify that path, which is denoted by \(I_{uv}\) and expressed as in Equation (3).  
\[I_{uv}=[t_{u},t_{x_{1}},t_{x_{2}},\ldots,t_{x_{n-1}},t_{n},t_{v}], \tag{3}\]  
where \(t_{u}\), \(t_{x_{1}}\), \(t_{x_{2}}\), \(t_{x_{n-1}}\), \(t_{n}\), and \(t_{v}\) are the virtualization technique types of \(N_{u}\), \(N_{x_{1}}\), \(N_{x_{2}}\), \(N_{x_{n-1}}\), \(N_{n}\), and \(N_{v}\), respectively.  
It is important to know that the path identification is a unique entry while the contents of those unique entries are not, where one identification can retrieve a set of all simple paths that have the same path length and the same ordered sequence of virtualization technique types. For example, the identification \(I_{Path}=[t_{1},t_{2},t_{3}]\) can be an address in a data set for many simple physical paths \(P_{1},P_{2},\ldots,P_{n}\) that have the length of three nodes, which have the same sequence of virtualization types \(t_{1},t_{2},t_{3}\) in the same order.  
The data set of path identifications is denoted by \(C_{P}\). Each entry of \(C_{P}\) contains a data set of all paths, which have the same path identification of the entry as expressed in Equation (4) below:  
\[C_{P}(I_{path})=C_{P}([t_{1},t_{2},t_{3}])=[P_{1},P_{2},\ldots,P_{n}], \tag{4}\]  
where \(I_{path}\) can be any unique sequence of available virtualization types with variable length in the range of 2 nodes to the number of nodes in the longest simple path in the physical network. If \(a\) is the maximum number of available unique path identifications, the data set of \(C_{P}\) is expressed as in Equation (5):  
\[C_{P}=(I_{Path1},I_{Path2},\ldots,I_{Patha}) \tag{5}\]  
To realize the proposed path mapping approach on NFV, we suggest to implement \(C_{P}\) as a catalogue in the NFVI repository under the name of \"catalogue of physical paths.\" Figure 2 shows an example of implementing \(I_{p1}\) and \(I_{p2}\), which are used to get the path list by calling Equation (4). Then, a candidate group is built by selecting one path \(P_{x}\) from each list we retrieved from Equation (4).