# Policy-Based Composition and Embedding of Extended Virtual Networks and SFCs for IIoT
## 3 Problem Description
### System Model  
Our main system model (Figure 2) includes a system user who provides the AR and SN definition, the transformation patterns and rules, and VNFs' dependencies. The AR is an abstraction level that only defines the application entities and its high-level requirements. It is used to avoid involving the application user in the definition of all required details to realize the application from the networking perspective. The AR can be defined as a directed acyclic graph with VNos and VLis \(AR(N_{AR},E_{AR})\), where \(N_{AR}\) is the set of nodes and \(E_{AR}\) is the set of edges. The demands are represented as \(n^{i}_{AR}\textit{demandName}\) and \(e^{ij}_{AR}\textit{demandName}\), where \(n^{i}_{AR}\in N_{AR}\) and \(e^{ij}_{AR}\in E_{AR}\). The properties are also represented as \(n^{i}_{AR}\textit{:propertyName}\) and \(e^{ij}_{AR}\textit{:propertyName}\). We use the same notation for the EVN that results from extending the AR. The SN can be defined as a directed acyclic graph with SNos and Substrate Links (SLis) \(SN(N_{SN},E_{SN})\), where \(N_{SN}\) is the set of nodes and \(E_{SN}\) is the set of edges. The resources are represented as \(n^{i}_{SN}\textit{:resourceName}\) and \(e^{ij}_{SN}\textit{:resourceName}\), where \(n^{i}_{SN}\in N_{SN}\) and \(e^{ij}_{SN}\in E_{SN}\). The properties are also represented as \(n^{i}_{SN}\textit{:propertyName}\) and \(e^{ij}_{SN}\textit{:propertyName}\). The AR is transformed into an EVN that might include additional application VNos, VLis, and a VNF request per VLi, where needed. The VNF request defines the required VNFs and their dependencies that represent a mandatory order of VNFs, such as encryption before decryption. The dependencies are predefined in a general VNF graph that defines all available VNFs and their dependencies. Figure 2: System model. The proposed approach is based on graph transformation [16] in the network virtualization context. The transformation logic applies certain operations (rules) to generate the EVN from a given AR. The transformation is a formalization of a certain policy that is defined by the service provider. It is composed from a pattern and a set of rules. The pattern is a set of conditions to be checked on the input networks, and the rules are the operations to be applied on network entities that match the pattern. Examples of these operations are adding, deleting, and updating specific VNos, VLis, VNFs, and demands in the AR and intermediate EVNs. We apply one transformation function per pattern in a predefined order of patterns. A transformation function can take the SN, a pattern P, AR, and intermediate EVN as inputs and return the intermediate/final EVN as output. After the transformation, we use topological sorting to create all possible FGs for each VNF request based on the VNF dependencies. The FG is also modeled as an acyclic directed graph \(FG=(N_{FG},E_{FG})\) with VNFs \(n_{FG}^{i}\), and edges that represent data flow \(e_{FG}^{ij}\). Usually, multiple FGs are possible, but one FG is selected for each VLi. The embedding logic first maps the application VNos on selected SNos. Subsequently, it maps each VNF request holding VLi using the proactive chain embedding heuristic, and each simple VLi by verifying its demands. The problem definition is summarized in the following list and Algorithm 1. The transformations, EVN embedding, and FG embedding are detailed in Section 4:  
* A physical topology \(SN(N_{SN},E_{SN})\) is defined by the service provider. * The application requirements \(AR(N_{AR},E_{AR})\) are defined by the user. * A set of policies (defined by the service provider), where each policy is composed of:
* A pattern P: conditions on the \(SN\) and \(EVN\) for checking and comparison of properties, demands, and resources. * Transformation T: if P match is found, then perform \(T(EVN_{i-1},SN)=EVN_{i}\), where \(EVN_{0}=AR\), and T is a set of rules. * A rule R adds or copies virtual links or nodes, adds or changes the properties or demands, or adds VNFs to the VNF demand of a VLi.