# Policy-Based Composition and Embedding of Extended Virtual Networks and SFCs for IIoT
## 4 Methodology
### Chain Embedding Heuristic  
In [6], the authors assume that each SNo on the path can host one VNF. The algorithm that is presented in [5] is based on backtracking and, in the case of rejection, tries a different combination starting from the last successfully embedded VNo. Finding a path where the number of hops exactly matches or is greater than the number of VNFs might not be possible or efficient for all FGs, in particular with our use case. Our proposed embedding algorithm tries to find a solution independently from the FG or path length. It is assumed that a SNo can host multiple VNFs when the resource capacity allows. Based on this assumption, a path with less hops than the FG can be utilized. On the other hand, for a path longer than the FG, we can try the next hop on the path in case of lack of resources. Algorithm 4 represents the pseudo-code for our proposed algorithm. As input, a path connecting two VNos embedded onto different SNos and the FG are given. Initially, the algorithm takes the first nodes in the FG and the path. If the target VNF can be allocated on the current SNo, then the algorithm verifies if the number of residual VNFs is smaller or equal to the residual hops on the path. If possible, the algorithm tries to embed multiple VNFs on a target SNo when the residual path length is less than the residual FG length. This is intended to find a valid embedding to avoid backtracking. If available, the next FG's node and the next hop on the path are verified. If the verification is successful, then the target SNo is set to the successor of the current one. This proactive verification is intended in this context to prevent setting the target SNo to the next SNo if it might not be able to fulfill the requirements. If the residual FG is shorter than the residual target substrate path, we try a balanced embedding over all SNos on the path to avoid consolidation. However, because the path might include SNos from different domains or can not host the next VNF, it is necessary to verify whether the next SNo is able to provide enough resources and fulfills the domain requirements of the next FG element. In the next step, the algorithm takes the next VNo in the FG and verifies whether a successful allocation is possible. In case of no possible allocation, it tries to verify whether the next SNo on the path can fulfill the requirements and, otherwise, it tries the next SNo until the last SNo is reached. In addition to VNo verification, the links inside FGs are verified against the SLis. When the last VNF is not mapped to the destination SNo on the path, then the outgoing data rate \(dr_{out}\) of the last VNF has to be verified over the residual path. Figure 5 presents an example of the FG embedding. The initial FG contains four VNos (C1, C2, C3, C4) and the target substrate path has four SNos (S1, S2, S3, S4). Resources and demands are assigned to nodes and links in both the FG and substrate path. Nodes and links currently under investigation are dotted. The embedding starts by checking whether \(C1\) can be hosted on \(S1\). Because enough resources are available, the assignment is made here and the new target SNo is set to \(S2\). Again, the algorithm verifies whether C2 can be embedded on \(S2\) and performs the assignment. The target SNo remains \(S2\) since the link bandwidth demand between C2 and C3 cannot be fulfilled on the link between \(S2\) and \(S3\). In the next step, VNo \(C3\) is assigned to \(S2\) and the target SNo is set to \(S3\). Next, the algorithm verifies whether \(C4\) can be hosted on the target SNo \(S3\). In this case, it is not possible, since \(S3\) has no enough CPU resource. Therefore, the algorithm keeps \(C4\) as the target FG VNo and verifies whether the next SNo on the path \(S4\) provides sufficient resources. \(S4\) provides enough resources and the assignment is performed. Because all FG VNos are embedded, the algorithm returns true and terminates. For simplicity, this example considers resource capacities and not domains.