# Policy-Based Composition and Embedding of Extended Virtual Networks and SFCs for IIoT
## 2 Related Work  
Traditional VNE [1] and NFV resource allocation problems deal with relatively fixed VNs and SFCs. To the best of our knowledge, there is no approach that combines both resource allocation problems and generates a virtual topology that meets multiple policies. Because the VNE problem has been extensively studied, we focus in this section on SFC composition and embedding. In [2],the authors provide an extensive survey on NFV resource allocation. They highlight the fact that most of the contributions focus on the chain embedding and use linear programming to optimize the solution for a certain objective, such as runtime, end-to-end latency, and deployment cost. However, several researchers studied the SFC composition problem. The authors in [3] introduce a model that is based on a context-free language to formalize the VNF requests and a heuristic to compose the SFCs. SFC allocation is formulated as an optimization problem with different objectives. The authors highlight the fact that placing SFCs is complex, in particular for different, possibly conflicting, allocation objectives, such as used number of Substrate Nodes (SNos) or latency. An optimal SFC composition approach that is based on integer linear programming is introduced in [4]. The objective is to find SFCs with minimal bandwidth requirements for a predefined VNF request. The evaluation for small VNF requests shows that this solution outperforms the SFC composition heuristic from [3]. In [5], the authors introduce a heuristic coordinated approach, CoordVNF, which tackles the chain composition and embedding problems with the objective of minimizing the bandwidth utilization. The approach uses backtracking in case of an invalid embedding to find a valid solution starting from the last successfully embedded VNF. The authors compare their heuristic to the previous approach from [3]. For the evaluation, they used a randomly generated SN with 50 SNos and 10 VNF requests. Each VNF request has five randomly connected VNFs. The evaluation for small VNF requests shows that the proposed heuristic is slightly faster and that the residual bandwidth capacity after the embedding is similar for both approaches. In [6], an approach, referred to as LightChain, creates a directed acyclic graph for a VNF request and performs topological sorting to generate a single SFC. This SFC is then embedded on the shortest path between source and destination devices based on the assumption that a path of length \(n\) can host \(n\) VNFs. This means that each SNo can only host a single VNF. If the current path is consumed, another shortest path is calculated for placing the remaining VNFs. In [7], the authors make a classification of the SFC deployment problems according to the option of sharing VNF instances. An optimization problem and a heuristic solution are presented in order to find the best SFC composition scheme that achieves minimal demand of link resources and improves the VNF instance utilization. The stages of SFC composition, placement, and assignment are combined. For the evaluation, the authors use a random topology and the average link consumption as a metric In [8], the authors present a solution for placing VNFs in cloud data centers. They focus on the placement of multi-tenant VNFs that are shared among multiple SFCs to achieve an efficient utilization of network resources in contrast to traditional VNF placement strategies. In [9], a SFC composition framework, called Automatic Composition Toolkit, is introduced. It tries to automatically detect the dependencies and conflicts among the network functions and model their behavior. The authors define topology and processing dependencies, and action and processing conflicts. In [10], the authors present a typical three-stage coordinated optimization model for NFV resource allocation, which considers CAPEX, OPEX, and link costs. Extensive simulations are performed on three typical random network topologies for obtaining a series of optimal solutions.