# Policy-Based Composition and Embedding of Extended Virtual Networks and SFCs for IIoT
## 4 Methodology
### Creating FGs using Topological Sorting  
In the chain composition stage, the possible FGs are calculated. The authors in [3] introduce a context-free grammar to formalize the request. Topological sorting is a known graph method to sort a directed acyclic graph. This method is used in several works on SFC composition, such as [6] and [19], in order to generate the FG. Our proposed approach is also based on topological sorting, but we calculate all possible FGs. Based on [20], the topological ordering of a graph \(G=(V,E)\): \(ord:V\to 1...n\) for \(n=|V|\) exists, if \(\forall(v,w)\in E\): \(ord(v)<ord(w)\). For every non-cyclic graph, a topological ordering exists, and every graph that has a topological ordering is non cyclic.  
Using topological sorting for the chain composition enables us to prove whether the VNF request is cycle free and if a possible FG can be calculated. It might happen that the dependencies among VNFs are not defined correctly by the service provider leading to cyclic VNF requests. For example, for a VNF request including encryption and decryption, where both functions depend on each other, no valid chaining is applicable due to the dependency loop. A simplified approach for calculating the topological ordering is to iterate over all VNos and taking a VNo v in each iteration, where \(inDegree(v)=0\) and adding it to an array. Afterwards, \(v\) and its outgoing edges are removed from the graph. This operation is repeated until there is no VNo left with \(inDegree=0\). If the graph is empty, then a topological ordering exists, otherwise it is not cycle free. The associated pseudo-code, which is based on [20], is presented in Algorithm 2. In the context of chain composition, it is important to calculate all possible sortings for a given graph \(G\). For this purpose, the above mentioned pseudo-code has to be adapted in order to calculate another ordering when the graph has multiple VNos where the \(inDegree=0\). Algorithm 3 represents a pseudo-code for calculating all of the possible sortings for a given graph.  
```
1 ordering[];
2 TopologicalSort(G)
3 index=0;
4 whileG has at least one node n where inDegree(n) = 0 do
5 ordering[index]:=n;
6 index++;
7G:=G-[n];//RemovenodeanditsoutgoingedgesfromG
```  
**Algorithm 2**Topological sorting  
The extended Algorithm 3 recursively calculates all possible orderings for a given graph G. The algorithm iterates over all VNos in the graph. For each VNo, if \(indegree=0\), then it is added to the tentative result and removed with all outgoing edges from the graph. If the graph is not empty, the function is recursively called until all VNos are visited or the graph is empty, then the tentative result is assumed to be a valid ordering and is added to the result.  
```
1 ordering[];
2 AllTopologicalSort(\(G\), tentativeResult)
3G' = copy(G);
4 while\(G\)' has at least one node \(n\) where inDegree(\(n\)) = 0 do
5 tentativeResult' = tentativeResult;
6 tentativeResult'.add(n);
7G':= G'- {n};
8 if\(G\)' = 0 then
9 ordering \(\cup\) tentativeResult'
10 else
11 AllTopologicalSort(\(G\)', tentativeResult)
12
```  
**Algorithm 3**Finding all topological sortings