# Policy-Based Composition and Embedding of Extended Virtual Networks and SFCs for IIoT
## 4 Methodology
### Complexity of the Proposed Methods  
We first make the following assumptions to estimate the complexity of the proposed algorithms:  
* Neglecting the operations applied by the rule on only a small subset of the EVN entities.
* Considering that the maximum size of the final EVN (nodes M, links L) is known and used to estimate the complexity even for intermediate EVNs.
* (D, D) is the size of the dependency graph. We consider that, in NFV, a function typically has one dependency, so the number of edges in the dependency graph can be approximated to the number of VNFs. The size of the dependency graph is considered the size of each VNF demand.
* We consider that finding one topological sorting of the VNF demand (one FG) is enough, since we do not yet classify the resulting FGs or trying to select the best FG based on a specific criteria.
* P is the diameter of the SN graph (the number of edges in the shortest path between the most distant vertices). We use this worst-case value as the length of the shortest path on which the chain will be embedded.
* We are calculating the complexities in the worst cases without considering locations and domains that might reduce the search space for node and link mapping, in particular, in specific topologies, like in our use case.  
We estimate first the complexity of each step in our system model:  
Figure 5: Proactive FG embedding example.  
* Redundancy--O(L): checking the redundancy demand of all EVN links and copying them when needed.
* Node types--O(N.M): comparing certain properties of SNos and VNos and adding the required entities to the EVN with their demands.
* Security--O(L): comparing the source and destination locations/domains of the EVN links and adding the required VNFs.
* Low latency--O(L): checking the latency demand of the EVN links and adding the TAS VNF where needed.
* Bandwidth--O(L): checking the bandwidth demand of each VLi and adjusting it based on the bandwidth demands of the incoming edges to its source VNo.
* CPU--O(M): adjusting the CPU demand of all EVN nodes based on the incoming bandwidth, cloning certain nodes, and then adding load balancing function.
* Total complexity of the transformations: O(4L+M (1+N)) = O(L + M.N) when considering that \(N\gg 1\).
* Topological sorting--O(L.D) = O(L): the complexity of finding one topological sorting is O(D+D) = O(D). We assume here that D is small and fixed and that we need to calculate a FG for each VLi.
* Node mapping--O (N.M): finding the SNo with the matching ID, properties, or resources of each VNo.
* Chain embedding--O (2P)=O(P): when mapping a VNF is tried on a SNo, the demands are compared to the resources. A VNF can be mapped on the latest SNo used from the path or any other following node. In the worst case, all path SNos are checked twice for each placed VNF and next VNF that cannot be placed on the same SNo, so a following one is checked. The P value varies with the SN size.
* Link mapping: the complexity of the k-shortest path algorithm is O(E+N.log N)) [21]. This algorithm is used for mapping all VLis. We assume for the worst case that all VLis have VNF demands for which chain embedding will be performed. The total complexity of link mapping is O(L.(E+N.log N+P)).  
The total complexity of the solution is: O(L+N.M+L+N.M+L.(E+N.log N+P)) = O(N.M+L(E+N.log N+P)).