## Chengli Mei , Jiayi Liu , Jinyan Li , Lei Zhang and Menghan Shao## |

[TeX:] $$G_{I}, N_{I}, E_{I}$$ | Physical network, physical nodes and physical links |
---|---|

[TeX:] $$n_{u}^{\prime}, e_{u v}^{I}$$ | One physical node, one physical link |

[TeX:] $$C_{u}^{I}, B_{u v}^{I}, L_{u v}^{I}$$ | Physical node resource, link bandwidth and delay |

[TeX:] $$N S R_{k}$$ | The kth NSR, [TeX:] $$k \in[1, K]$$ |

[TeX:] $$G_{S}^{k}, N_{S}^{k}, E_{S}^{k}$$ | [TeX:] $$N S R_{k} \text { 's }$$ virtual network, virtual nodes, virtual links |

[TeX:] $$n_{i k}^{S}, e_{i j k}^{S}$$ | [TeX:] $$N S R_{k} \text { 's }$$ one virtual node and one virtual link |

[TeX:] $$B_{i j k}^{S}, L_{i j k}^{S}$$ | [TeX:] $$N S R_{k} \text { 's }$$ virtual link bandwidth and delay |

[TeX:] $$F, f, F_{s}$$ | VNF types set, one VNF type, sharable VNF types |

[TeX:] $$T\left(n_{i k}^{S}\right)$$ | the VNF type of virtual node [TeX:] $$n_{i k}^{S}$$ |

[TeX:] $$N_{k f}^{S}$$ | Virtual nodes in [TeX:] $$N S R_{k}$$ with VNF type f |

[TeX:] $$C_{f}$$ | Instantiation resource requirement of VNF type f |

[TeX:] $$C_{i k}^{S}$$> | Running resource requirement of [TeX:] $$n_{i k}^{S}$$ |

[TeX:] $$\operatorname{loc}_{i k}^{u}$$ | Location specification parameter |

[TeX:] $$x_{i k}^{u}, y_{i j k}^{u v}$$ | Node and link mapping decision variables |

scribe the underlying physical infrastructure model. The physical infrastructure network is owned by one InP. Then, we model NS requests. The NS requests are issued by tenants based on their service and SLA requirements. Especially, we consider the scenario in which some specific VNF types could be shared among NSs to improve the network resource utilization ratio. Further, we formulate the problem of allocating physical network nodes and links resources to implement these coupled NSs as an ILP. For ease of understanding, a table of notation is summarized in Table 1.

The physical infrastructure network is modeled by a graph [TeX:] $$G_{I}\left(N_{I}, E_{I}\right)$$ where [TeX:] $$N_{I}$$ denotes for the physical network nodes and [TeX:] $$E_{I}$$ stands for physical communication links. One physical network node is denoted by [TeX:] $$n_{u}^{I} \in N_{I}.$$ We consider the C-RAN architecture in the RAN side, such that remote radio unit (RRU) and base band unit (BBU) are seperated, and the BBU can be virtualized. Hence, we distinguish four kinds of physical nodes:

The physical RRU nodes set [TeX:] $$N_{I}^{R}$$ is allowed to host virtual RRUs.

The access nodes set [TeX:] $$N_{I}^{A},$$ such as BBU hotels and edge data centers (DCs) are capable for accommodating virtual BBU and virtual mobile edge computing (MEC) servers.

The transport network nodes set [TeX:] $$N_{I}^{T}$$ which denotes TN optical switches.

The core network nodes set [TeX:] $$N_{I}^{c},$$ which includes core DCs for CN data plane and control plane VNFs virtualization.

and we have [TeX:] $$N_{I}=N_{I}^{R} \cup N_{I}^{A} \cup N_{I}^{T} \cup N_{I}^{C}.$$ Without loss of generality, we assume that [TeX:] $$N_{I}^{R}$$ nodes can only host virtual RRUs; [TeX:] $$N_{I}^{A}$$ and [TeX:] $$N_{I}^{C}$$ nodes are suitable for accommodating multiple other types of virtualized VNFs for the flexible deployment of NSs. Moreover, each physical node [TeX:] $$n_{u}^{I} \in N_{I}^{4} \cup N_{I}^{C}$$ is characterized by its capacity [TeX:] $$C_{u}^{I}$$ which represents the physical resources of the node (such as computing resources).

Physical communication links are represented by [TeX:] $$E_{I},$$ with [TeX:] $$e_{u v}^{I} \in E_{I}$$ denote the physical link connecting two physical nodes [TeX:] $$n_{u}^{I} \text { and } n_{v}^{I}.$$ Especially, RRUs are connected to the C-RAN central locations via common public radio interface (CPRI) fronthaul transport, and the other types of links (including backhaul and TN CN links) are based on IP transportation. For each link [TeX:] $$e_{u v}^{I} \in E_{I},$$ we denote by [TeX:] $$B_{u v}^{I}$$ the bandwidth capacity of the link, and [TeX:] $$L_{u v}^{I}$$ the transmission delay of the link.

Network slices are service oriented. Different services requires various different composition of network functions to form the specific service system. In order to describe all kinds of network slice requests (NSRs), we follow the general way to represent a 5G E2E network slice by a VN, and model it by an undirected graph. For example, as shown in Fig. 2, we depict a 5G E2E NS for providing ICN services. The NS contains the following VNFs:

ICN-CR: The ICN cache enabled router.

ICN-GW: The ICN gateway, for ICN-IP interworking.

The MME, SDN-Controller and virtual network infrastructure orchestrator (VNIO), etc., which are sharable among multiple NSs.

Clearly, the topology of the NS is a mesh based VN, which is represented by an undirected graph.

We consider [TeX:] $$K \text { NSRs. }$$ Each network slice request [TeX:] $$N S R_{k}$$ is represented by a virtual network and modeled as a graph [TeX:] $$G_{S}^{k}\left(N_{S}^{k}, E_{S}^{k}\right), k \in[1, K], \text { with } N_{S}^{k}$$ denotes for the virtual network nodes in [TeX:] $$N S R_{k}, \text { and } E_{S}^{k}$$ stands for virtual links connecting the virtual nodes. One virtual network node is denoted by [TeX:] $$n_{i k}^{S} \in N_{S}^{k}.$$ Each virtual network node represents a virtual VNF instance, such as virtual RRU, virtual BBU, virtual MEC server, virtual encoder (for mobile video service slices) and virtual gateway, etc. Due to the specific position requirement of virtual RRU, we denote by [TeX:] $$N_{S}^{R k}$$ the set of virtual RRU nodes. Then, we denote by [TeX:] $$C_{i k}$$ the physical resource requirement of the virtual node [TeX:] $$n_{i k}^{S}.$$ A virtual link is represented by [TeX:] $$e_{i j k}^{S} \in E_{S},$$

with [TeX:] $$B_{i j k}^{S}$$ denoting its bandwidth requirement and [TeX:] $$L_{i j k}^{S}$$ the link delay requirement.

Specifically, we consider the scenario in which some types of VNFs can be shared among these [TeX:] $$K \text { NSs. }$$ The sharing policy depends on the InP’s and tenants’ requirements. In this case, an instance of the VNF can participate into multiple [TeX:] $$\text { NSs, }$$ to avoid redundantly instantiate more VNFs and to improve the utilization of the underlying physical network resources. Assume that the [TeX:] $$\text { VNFs }$$ can be classified into F types, and each type is denoted by [TeX:] $$f \in F.$$ A subset of these types, noted as [TeX:] $$F_{s} \subseteq F$$ are defined as sharable VNF types. For a virtual node [TeX:] $$n_{i k}^{S}$$, its corresponding VNF type is denoted as [TeX:] $$T\left(n_{i k}^{S}\right),$$ consequently, if [TeX:] $$T\left(n_{i k}^{S}\right) \in F_{s},$$ this virtual node can be co-localized with other virtual nodes with the same sharable type. We define the set [TeX:] $$N_{k f}^{S}=\left\{n_{i k}^{S} \mid T\left(n_{i k}^{S}\right)=f\right\},$$ s the set of virtual nodes with VNF type [TeX:] $$f \text { in } N S R_{k}.$$

We define the basic operational resource requirement to instantiate a VNF of type [TeX:] $$f \text { by } C_{f}.$$ The afore-defined resource requirement [TeX:] $$C_{i k}^{S}$$ of virtual node [TeX:] $$n_{i k}^{S}$$ is actually the additive resource requirement to run the VNF for the corresponding network services, which is related to the workload of the virtual node. By this definition, for a non-sharable VNF, the instantiation resource requirement is always [TeX:] $$C_{f}+C_{i k}^{S};$$ whereas for a sharable VNF, the first instance on one physical node requires [TeX:] $$C_{f}+C_{i k}^{S},$$ the subsequent virtual nodes with the same type allocated to this physical node just requires the additive resource part [TeX:] $$C_{i k}^{S}.$$

Deploying these NSs correspond to mapping the K virtual networks towards the physical infrastructure. We define two sets of binary variables:

The node map decision variable [TeX:] $$x_{i k}^{u}$$ takes the value 1 if the virtual node [TeX:] $$n_{i k}^{S}$$ is placed on the physical node [TeX:] $$n_{u}^{I},$$ and takes the value 0 otherwise.

The link map decision variable [TeX:] $$y_{i j k}^{u v}$$ takes the value 1 if the virtual link [TeX:] $$e_{i j k}^{S}$$ is deployed through the physical link [TeX:] $$e_{\mathrm{uv}}^{I},$$ and takes the value 0 otherwise.

We first formulate the 5G network topology related constraints. In the 5G network, VNFs are position specific. For example, the virtual RRU can only be deployed on physical [TeX:] $$\text { RRUs }$$ to provide wireless transmission in a certain area. In MEC service scenarios, the related VNFs should be placed on the edge of the network. To describe such location specification, we define a binary location parameter [TeX:] $$\operatorname{loc}_{i k}^{u}$$ which takes value 1 if the corresponding virtual node [TeX:] $$n_{i k}^{S}$$ can be placed on the corresponding physical node [TeX:] $$n_{u}^{I},$$ and 0 otherwise. Hence, we introduce a location constraints in (1).

Especially, the location parameter [TeX:] $$\operatorname{loc}_{i k}^{u}$$ should be properly defined. The position and traffic requirements of virtual RRUs can be determined by analysing the spatial temporal traffic pattern of each NSs. Each virtual RRU is anchored toward one specific physical RRU node, and the corresponding loc parameter is set to 1. Hence, [TeX:] $$\sum_{u} \operatorname{loc}_{i k}^{u}=1, \forall k \text { and } n_{i k}^{S} \in N_{S}^{R k}.$$ Moreover, for access VNFs, [TeX:] $$\left[o c_{i k}^{u}=0, \forall n_{u}^{I} \in N_{I}^{R} \cup N_{I}^{T} \cup N_{I}^{C}\right.;$$ for core VNFs, [TeX:] $$l o c_{i k}^{u}=0, \forall n_{u}^{I} \in N_{I}^{R} \cup N_{I}^{A} \cup N_{I}^{T}.$$

Then, we formulate the resource constraints for the sharable VNFs from (2) to (4). For the K coupled NSRs, a specific constraint is the physical node resource constraint which bounds the number of placed virtual nodes. First, we count the physical resource consumed by sharable VNFs placed on a physical node:

where [TeX:] $$1\left\{x_{i k}^{u}>0\right\}$$ is the indicator function which takes value 1 if [TeX:] $$x_{i k}^{u}>0, \text { and } 0$$ otherwise. Then, we compute the physical resource required by non-sharable VNFs placed on a physical node:

Clearly, the physical resource constraint is represented as:

Finally, we formulate the VNE embedding constraints for each NSR from Constraint (5) to (9). Firstly, each virtual nodes must be mapped to one physical node.

With the location Constraint (1), this constraint ensures that the virtual RRU is deployed on its specific position, and each virtual node of the NSR is properly deployed. Then, the sharable VNFs could save some physical node resources, however, the bandwidth requirements can not be reduced. Hence, the physical link resource constraint should be respected.

The mapped physical links should be bounded by the virtual link delay requirement.

One virtual link [TeX:] $$e_{i j k}^{S}$$ is mapped as a flow from the physical source to sink. Hence, we impose the following flow related constraints.

in which [TeX:] $$N\left(n_{u}^{I}\right)$$ stands for the neighbor set for the physical node [TeX:] $$n_{u}^{I}.$$ Constraint (8) ensures that there is no loop along the physical path mapped for the virtual link. Constraint (9) satisfies the flow conservation constraints.

Finally, we set forth the problem objective formulation. One reasonable strategy to allocate the infrastructure for these K NSRs would be to minimize the utilization of the network resources. The physical resource consumed on each physical node is calculated as: [TeX:] $$C_{u}^{I_{s}}+C_{u}^{I_{n}}, \forall n_{u}^{I}.$$ The bandwidth consumption on each physical link is: [TeX:] $$\sum_{k} \sum_{e_{i j k}^{S}} B_{i j k}^{S} y_{i j k}^{u v}, \forall e_{u v}^{I}.$$

Then, the SVM-VNE problem is formulated as Problem (P1), subjects to the NSRs’ SLA requirements and physical network capacity:

The complexity of the Problem (P1) is NP-hard, because when K = 1, this problem is reduced to the NP-hard VNE problem. Hence we focus on developing fast algorithms to practically tackle the problem for real and large system setting.

The minimization of the objective of the Problem (P1) comes from two parts: (1) By integrating the sharable VNFs into less instances, the physical node resource consumption could be reduced; (2) by mapping virtual links into shorter physical paths, the bandwidth resource could be saved. Inspired through these two observations, we design our SVM-VNE algorithm to especially tackle these two aspects of the problem.

We first introduce how to measure network node importance by considering both resource and topology information. This measurement is applicable for both physical network nodes and virtual nodes to distinguish the importance of nodes for determining the sequence of slices and nodes mapping. The following concepts of node importance are conventional in general networks, hence we manifest the measurement of the virtual nodes for one NS, that of the physical nodes can be derived similarly.

We consider the measurement for virtual nodes in [TeX:] $$N S R_{k},$$ the topology is given by [TeX:] $$G_{S}^{k}.$$ as:

Thus, we consider both the computing resource required by [TeX:] $$n_{i k}^{S},$$ and the bandwidth requirement of virtual links connected to [TeX:] $$n_{i k}^{S}$$ in [TeX:] $$G_{S}^{k}.$$

We utilize the following conventional concepts to measure the topological characteristics of [TeX:] $$n_{i k}^{S}.$$

Degree centrality. The degree of [TeX:] $$n_{i k}^{S}$$ measures the number of links that connect to it in [TeX:] $$G_{S}^{k}.$$ The normalized node degree is defined as [TeX:] $$d_{n_{i k}^{\prime}}^{\prime}=d_{n_{i k}^{S}} /\left(\left|N_{S}^{k}\right|-1\right), \text { where } d_{n_{i k}^{S}}$$ is node degree of [TeX:] $$n_{i k}^{S} \text { and }\left|N_{S}^{k}\right|$$ is the number of virtual nodes in [TeX:] $$N S R_{k}.$$

Betweenness centrality. The betweenness centrality calculates the fraction of all-pairs shortest paths pass through the node in the topology graph, which is defined as [TeX:] $$b_{n_{i k}^{S}}=\sum_{j \neq i \neq m} p_{j m}^{k}\left(n_{i k}^{S}\right) / \sum_{j \neq i \neq m} p_{j m}^{k}.$$ Here, [TeX:] $$p_{j m}^{k}$$ is the number of shortest [TeX:] $$\left(n_{j k}^{S}, n_{m k}^{S}\right)-$$ paths in [TeX:] $$G_{S}^{k},$$ and [TeX:] $$p_{j m}^{k}\left(n_{i}^{S}\right)$$ is the number of those pathes goes through node [TeX:] $$n_{i k}^{S} \text { in } G_{S}^{k}.$$ We further normalize it into [TeX:] $$b_{n_{i k}^{S}}^{\prime}= 2 b_{n_{j k}^{S}} \left(\left|N_{S}^{k}\right|-1\right)\left(\left|N_{S}^{k}\right|-2\right).$$

Closeness centrality. The closeness centrality measures the distance of the node towards all other nodes in the topology graph, which is defined as [TeX:] $$a_{n_{i k}^{S}}=1 / \sum_{j \neq i} d\left(n_{i k}^{S}, n_{j k}^{S}\right).$$ Here, [TeX:] $$d\left(n_{i k}^{S}, n_{j k}^{S}\right)$$ denotes the distance between node [TeX:] $$n_{i k}^{S}$$ and [TeX:] $$n_{j k}^{S} \text { in } G_{S}^{k}.$$ We also normalize it into [TeX:] $$a_{n_{i k}^{S}}\left(\left|N_{S}^{k}\right|-1\right).$$

Then, the topology importance of [TeX:] $$n_{i k}^{S}$$ is defined as:

[TeX:] $$T I\left(n_{i k}^{S}\right)=d_{n_{i k}^{S}}^{\prime}+b_{n_{i k}^{S}}^{\prime}+a_{n_{i k}^{S}}^{\prime}.$$

Finally, the node importance of [TeX:] $$n_{i k}^{S}$$ is calculated as:

To deploy the K NSRs’ virtual networks, the first step would be to determine a sequence of deployment. We first measure the total resource requirement and sharable resource requirement of NSRs. Firstly, the total resource requirement of [TeX:] $$N S R_{k}$$ is calculated as:

in which and are two tuneable positive parameters, which drive the emphasis on computing or bandwidth resources. The sharable resource requirement of [TeX:] $$N S R_{k},$$ which can be potentially integrated, is calculated as:

which is weighted by the topology importance of the sharable VNF virtual node. Hence, a more topological important sharable virtual node is more emphasized in determining the sharable resource requirement. Based on the above two definition, we finally sort all K NSRs based on:

where is also a tuneable positive parameter. The process of deploying the K NSRs are depicted in Algorithm 1. Note that NSRs with more resource requirement and sharable resources will be prioritized in the sequence of deploying to facilitate the integration of sharable VNFs.

Then, we introduce our algorithm to deploy one NSR. Assume the to-be-deployed NSR is [TeX:] $$N S R_{k},$$ We adopt the coordinated virtual node and link mapping method to reduce physical bandwidth consumption [28]. Moreover, we restrict that two neighboring virtual nodes are mapped within h hops in the physical infrastructure. We adopt the back-tracking mechanism such that if the current virtual node cannot be mapped to the current candidate physical node, the algorithm will try the next best one. This mechanism can further explore more mapping opportunities and improve NSR acceptance ratio. We first determine a sequence based on which the virtual nodes of [TeX:] $$N S R_{k},$$ are mapped.

The virtual node sorting algorithm first select the virtual node

with the highest NI value as the root and build the BFS tree from [TeX:] $$G_{S}^{k}.$$ Then, from the higher layer of the tree, the virtual nodes are pushed into the sorted list based on their NI value. Hence, the virtual nodes are sorted based both on their distances from the root and the NI values.

For a given virtual node, the NSR mapping algorithm selects a set of candidate physical nodes, from which to map the corresponding virtual node. We define [TeX:] $$C P N\left(n_{i k}^{S}\right)$$ as the candidate physical nodes set for [TeX:] $$n_{i k}^{S}.$$ The candidate physical nodes selection algorithm is depicted in Algorithm 3. We classify four cases based on the role of the virtual node [TeX:] $$n_{i k}^{S}.$$

[TeX:] $$n_{i k}^{S}$$ is the root of the BFS tree and its VNF type is sharable (line 8-12). In this case, [TeX:] $$C P N\left(n_{i k}^{S}\right)$$ contains two parts: (1) [TeX:] $$C P N_{1}\left(n_{i k}^{S}\right)$$ (line 9) contains physical nodes with VNFs of the type [TeX:] $$T\left(n_{i k}^{S}\right)$$ already mapped, and with sufficient large physical resources, and these physical nodes can accommodate the [TeX:] $$n_{i k}^{S};$$ (2) in [TeX:] $$C P N_{2}\left(n_{i k}^{S}\right)$$ (line 10), we also consider physical nodes without the [TeX:] $$T\left(n_{i k}^{S}\right)$$ type VNFs in case [TeX:] $$C P N_{1}\left(n_{i k}^{S}\right)=\emptyset.$$ Then, these two sets are sorted based on NI value decreasing order respectively, and we append [TeX:] $$C P N_{2}\left(n_{i k}^{S}\right)$$ at the end of [TeX:] $$C P N_{1}\left(n_{i k}^{S}\right)$$ to form the [TeX:] $$C P N\left(n_{i k}^{S}\right)$$ set.

[TeX:] $$n_{i k}^{S}$$ is the root of the BFS tree and its VNF type is nonsharable (line 14-15). In this case, [TeX:] $$C P N\left(n_{i k}^{S}\right)$$ is composed of physical nodes with sufficient large resources and suitable locations. The [TeX:] $$C P N\left(n_{i k}^{S}\right)$$ set is also sorted based on NI value decreasing order.

[TeX:] $$n_{i k}^{S}$$ is not the root of the BFS tree and its VNF type is sharable (line 18-22). When [TeX:] $$n_{i k}^{S}$$ is not the root of the tree, it means that it is not the first to-be-mapped virtual node and some other virtual nodes (including its parent node in the BFS tree) have been already mapped. In the coordinated virtual node and link mapping mechanism, when mapping this node, the virtual links connecting this node and other mapped nodes should also be mapped. In order to save bandwidth resources, we select physical nodes that locate near (for instance, within h-hops, where h is a parameter) to the mapped nodes (parent node of [TeX:] $$n_{i k}^{S}$$ ). Hence, comparing to the CPN set of the root, we add a constraint on CPN such that the candidate physical nodes should locate within h-hops from the parent node of [TeX:] $$n_{i k}^{S}.$$ Finally, [TeX:] $$C P N\left(n_{i k}^{S}\right)$$ is formed and sorted following the same logic as for the root.

[TeX:] $$n_{i k}^{S}$$ is not the root of the BFS tree and its VNF type is non-sharable (line 24-25). In this case, [TeX:] $$C P N\left(n_{i k}^{S}\right)$$ is composed of physical nodes with sufficient large resources, locate near to the parent node and with suitable locations. The [TeX:] $$C P N\left(n_{i k}^{S}\right)$$ set is also sorted based on NI value decreasing order.

Then we describe our coordinated SVM-VNE algorithm. The algorithm is detailed in Algorithm 4:

The input of the algorithm is the physical network model [TeX:] $$G_{I}$$ and the [TeX:] $$N S R_{k}$$ model [TeX:] $$G_{S}^{k}.$$ The output of the algorithm is the mapping from the NSR to the physical network. If the NSR cannot be mapped due to lack of resource, a rejection is returned.

The algorithm tries to map the virtual node in the list [TeX:] $$\mathbb{L}\left(N_{S}^{k}\right)$$ one by one (step 4). For the current to be mapped virtual node [TeX:] $$n_{i k}^{S},$$ obtain the set of candidate physical nodes [TeX:] $$C P N\left(n_{i k}^{S}\right)$$ from Algorithm 3. Then, depending on the role of [TeX:] $$n_{i k}^{S}$$ in the virtual network, we further classify two subsituations.

First, if [TeX:] $$n_{i k}^{S}$$ is the root of the BFS tree (step 6), we directly map [TeX:] $$n_{i k}^{S}$$ to the first physical nodes in [TeX:] $$C P N\left(n_{i k}^{S}\right).$$

If [TeX:] $$n_{i k}^{S}$$ is not the root of the BFS tree, it implies both the virtual node and corresponding virtual links should be mapped. The idea is, we try to map [TeX:] $$n_{i k}^{S}$$ to the physical nodes in [TeX:] $$C P N\left(n_{i k}^{S}\right)$$ one-by-one: if all virtual links con

necting [TeX:] $$n_{i k}^{S}$$ and the already mapped nodes can be mapped successfully (the shortest path can fulfill Constraint (7)), then [TeX:] $$n_{i k}^{S}$$ is mapped to the current candidate physical node, otherwise we try the next physical nodes in the [TeX:] $$C P N\left(n_{i k}^{S}\right).$$ At the end, if all physical nodes cannot accommodate [TeX:] $$n_{i k}^{S},$$ which means [TeX:] $$n_{i k}^{S}$$ cannot be successfully mapped, a rejection is returned.

Our algorithm is designed to save the physical resource consumption through the following means: (1) For sharable VNF deployment, we prioritize physical nodes hosting the same type of VNFs to exploit the possibility of integrating the sharable VNFs; (2) we utilize the parameter h to restrict that neighboring virtual nodes are mapped towards near physical positions (within h-hops). Consequently, the virtual links are mapped into shorter physical pathes, which reduces bandwidth consumption.

In real system, the NSRs arrive dynamically and randomly. When a NSR arrives, the InP allocates physical network resources to implement the corresponding NS based on Algorithm 4; and after its life time expires, the NS is deleted and physical network resources are released. It is trivial to treat the NS expiration event. For NSR arriving event, our proposed algorithm can be utilized to implement the single NSR based on the already deployed NSRs setting and available network resources.

Then we analyze the runtime complexity of our proposed algorithm. The algorithm utilized the following operations: (1) Sorting. The runtime complexity of Quicksort

Table 2.

Physical network setting | Value |
---|---|

Node CPU capacity Link bandwidth capacity Link delay AN:TN:CN | U[50,70] U[100,200] U[3,5] 3:4:3 |

Virtual network setting | Value |

Node CPU requirement Link bandwidth requirement Link delay requirement | U[20,30] U[1,10] U[60,100] |

algorithm is [TeX:] $$O\left(\left|N_{S}\right| \log \left|N_{S}\right|\right);$$ (2) BFS with runtime complexity [TeX:] $$O\left(\left|N_{S} \| E_{S}\right|\right);$$ (3) shortest path. The runtime complexity of Bellman algorithm is [TeX:] $$O\left(\left|N_{I}\right|\left|E_{I}\right|\right).$$ Taking [TeX:] $$N= \max \left\{\left|N_{S}\right|,\left|N_{I}\right|\right\} \text { and } E=\max \left\{\left|E_{S}\right|,\left|E_{I}\right|\right\}.$$ Algorithm 4’s complexity is [TeX:] $$O\left(N E+N \log N+N\left(N \log N+N^{2} E\right)\right),$$ which is finally reduced into [TeX:] $$O\left(N^{3} E\right).$$ Then, for deploying K NSRs, the total complexity is [TeX:] $$O\left(K N^{3} E\right).$$

We build a simulation platform to evaluate the performance of our proposed algorithm. Firstly, in the experiment, the underlying 5G physical network and NSR’s virtual network topology is generated by a modified Barabasi-Albert (BA) scalefree network model construction algorithm [32]. The BA model is largely utilized to represent the 5G system and NSR topology [10], [33]. Typically, as introduced in Section III, the physical network contains three types of nodes: Access nodes (AN), transport nodes (TN) and core nodes (CN). The network is generated from an initially fully connected CN network. Then, new nodes are added into the network one-by-one. Each time, the incoming new node is connected towards existing nodes in the network based on a probability [TeX:] $$P_{i}=d_{i} / \sum_{j}^{N} d_{j},$$ where N denotes the total number of current existing nodes and [TeX:] $$d_{i}$$ is the degree of the incoming node. Moreover, TN nodes can be connected to TN or CN nodes, whilst AN nodes can only be connected to TN nodes.

The overall simulation setting is shown in Table 2. For the physical network, physical node CPU capacity follows uniform distribution on the interval [50, 70]; physical link capacity follows uniform distribution on the interval [100, 200]; and physical link delay follows uniform distribution on the interval [3, 5]. Moreover, the physical network is composed of AN, TN and CN nodes, the proportion of these three nodes follows 3 : 4 : 3. For virtual network, virtual node CPU requirement follows uniform distribution on the interval [20, 30]; virtual link bandwidth requirement follows uniform distribution on the interval [1, 10]; and virtual link delay requirement follows uniform distribution on the interval [60, 100]. Virtual network composition (node location specification) follows the same as the physical network. 40% of virtual nodes are sharable, and the additive CPU requirement of sharable virtual nodes accounts for 20% of its overall CPU resource requirement. For algorithm parameters, we set the link mapping hops parameter h = 1, and , , are also set to be 1. Simulations with the same setting are launched for 100 times, and the results are taken as the average value.

We conducted two sets of simulations. In the first set (detailed in Section V.B), we compare our SVM-VNE Algorithm towards its counterpart without VNF-sharing, and we denote this algorithm by NSVM-VNE Algorithm. In the second set (detailed in Section V.C), we compare SVM-VNE and NSVM-VNE Algorithms towards a baseline algorithm that is a SFC embedding algorithm presented in [13]. The difference of these two groups of simulation comes from the fact that the baseline algorithm is specifically designed for SFCs with chaining structure, whilst our algorithm is for NSs with general mesh based VN structure. Hence, for the first set of simulation, the NSs are meshes, whereas for the second set of simulation, in order to conduct comparable experiments, the NSs are chains. Simulation results show that (1) VNF sharing achieves higher NS acceptance ratio, hence higher physical resource utilization; (2) our algorithm still outperform the baseline algorithm for NSs with chaining structure.

We present the results of our first set of simulation in this section. We evaluate SVM-VNE and NSVM-VNE Algorithms. In Fig. 3, we show the acceptance ratio of the two algorithms by varying the scale of the physical network from 40 nodes to 100 nodes. The acceptance ratio is calculated as the number of successfully embedded NSRs over the overall NSRs. The overall NSR number is set to 30, and each NSR contains 10 virtual nodes. As the physical network enlarges, the underlying resources increase and more NSRs could be embedded. For all physical network scales, the sharing based NSR embedding algorithms achieves higher acceptance ratio: 33.7% for 40 physical nodes and 99.1% for 100 physical nodes for the SVM-VNE algorithm; and 26.5% for 40 physical nodes and 66.3% for 100 physical nodes for the NSVM-VNE algorithm.

In Fig. 4, we show the acceptance ratio of the two algorithms for different number of NSRs. The physical network remains with 100 physical nodes. Each NSR contains 10 virtual nodes. We increase the number of NSRs from 30 to 100. The acceptance ratio decreases as the resource requirement increases. The sharing based SVM-VNE algorithm also achieves higher resource utilization ratio as the acceptance ratio is 96.2% for 30 NSRs and 25.0% for 100 NSRs. For NSVM-VNE algorithm, the acceptance ratio is 66:8% for 30 NSRs and 19.5% for 100 NSRs. In Fig. 5, we show the acceptance ratio of the two algorithms for different virtual network scales. The physical network remains with 100 physical nodes. The number of NSRs are 30. We vary the number of virtual nodes contained in each NSR from 9 to 36. As the scale of the virtual network increases, more resource are demanded, and the acceptance ratio decreases. The acceptance ratio is 96.8% with 9 virtual nodes and 20.0% with 36 virtual nodes in each NSR for the SVM-VNE algorithm, and the result is 67.7% with 9 virtual nodes and 16.7% with 36 virtual nodes in each NSR for the NSVM-VNE algorithm.

Finally, we show in Fig. 6 the number of VNF instances used per slice. For the non-sharing based NSVM-VNE algorithm, each virtual node should be implemented with one VNF instance, hence the VNF instance number is the same as the virtual node number. For our VNF-sharing based SVM-VNE algorithm, we set that 40% percent of virtual nodes are with sharable VNF types, hence the sharable virtual nodes can be co-localized into the same VNF instances, and the VNF instance number is less than the virtual nodes number. We also observe that the ratio of VNF instance over virtual node number decreases as the virtual network scale increases. As the physical network is saturated, more VNF instances are used.

In the second set of simulation, we aim to compare the performance of our algorithm towards the SFC embedding algorithm presented in [13]. We denote the algorithm presented in [13] as the baseline algorithm. The baseline algorithm is typically designed for SFCs with chaining structure, hence we conducted a set of simulation with chaining structured NSRs. Our algorithm is designed for general NSRs by graph model, hence it can be applied for the chaining structured NSRs, as chain is a typical structure which can also be represented by our model.

The results are presented in Fig. 7 to Fig. 10. Both the VNFsharing based SVM-VNE algorithm and the baseline algorithm perform better than the non-sharing based one. Moreover, our algorithm achieves better performance as it obtains higher acceptance ratio. For Fig. 7 we increase the physical network scale with physical node number from 50 to 150. The number of NSR is 30 with each NSR contains a chain with 10 virtual nodes. SVM-VNE algorithm obtains the highest acceptance ratio. For instance, the acceptance ratio is 86.5% for 100 physical nodes with SVM-VNE, it is 80.1% for the baseline algorithm, and it is 66.0% for the NSVM-VNE algorithm.

In Figs. 8 and 9, we show the acceptance ratio with different number of NSRs and different NSR scales. The setting remains the same as for Figs. 4 and 5. The results show that SVM-VNE outperforms the baseline algorithm in achieving higher acceptance ratio. Finally, In Fig. 10, we also compare the number of VNF instances used by SVM-VNE and the baseline algorithms. Our algorithm uses less VNF instances, because we prioritize physical nodes with sharable VNF instances in the NSR embedding process. With more integrated VNF instances, our algorithm utilizes less physical node resources, hence achieves higher resource utilization ratio. Then, we further investigate the performance of our algorithm in some other aspects in Fig. 11 to Fig. 13. In Fig. 11, we show the NSR acceptance ratio by varying the percentage of VNFs which are sharable for our proposed algorithm and the baseline algorithm. We do not show this simulation result for the NSVM-VNE algorithm because in this case this percentage remains zero. The percentage of sharable virtual nodes vary from 10% to 60%. For this simulation, the physical network contains 100 physical nodes, and the number of NSRs is 30 with each NS contains 10 virtual nodes. As the percentage of sharable VNFs increases, the acceptance ratio also increases since more VNFs could be integrated. Our algorithm outperforms the baseline algorithm. Especially, when the percentage of sharable VNFs increases, the gap between the two algorithm also increases. For 10% VNFs are sharable, the acceptance ratio of our algorithm is 69.7%, and that of the baseline algorithm is 67:8%. Whilst for 60% VNFs are sharable, the acceptance ratio of our algorithm is 98.6%, and that of the baseline algorithm is

90.4%.

In Fig. 12, we show the NSR acceptance ratio by varying the additive CPU resource requirement of the sharable VNFs. For all the other figures, this parameter is set to 20%. The physical network setting is 100 physical nodes, and the number of NSRs is 30 with each NS contains 10 virtual nodes. The additive resource requirement is introduced in Section III.B, for the first VNF mapped on a physical node, the whole resource required by this VNF type is allocated, whereas for the following VNFs mapped on the same physical node with same shable type, the additive resource requirement is allocated to reduce resource consumption. The additive CPU requirement of sharable virtual nodes is represented by the percentage of its overall CPU resource requirement. Consequently, higher number shows higher resource requirement. We vary the additive CPU requirement from 20% to 100%, and the acceptance ratio of the two algorithms decreases because sharable VNFs require more resources. The result of NSVM-VNE is not shown because 100% additive CPU requirement actually refers to nonsharable VNFs of our algorithm. The performance of our algorithm outperforms the baseline algorithm. For 20% additive resource requirement, the acceptance ratio of our algorithm is 86.1%, and that of the baseline algorithm is 80.1%. Whilst for 80% additive resource requirement, the acceptance ratio of our algorithm is 76.6%, and that of the baseline algorithm is 75:4%. Finally, we show the resource consumption of the three algorithms in Fig. 13 by varying physical network scale. The number of NSRs is 30, with each NS contains 10 virtual nodes.

to minimize the resource consumption (physical nodes resource that is represented by CPU, and bandwidth resources). These two kinds of resources are not measured by the same metric, and in our algorithm, we mostly focused on saving physical node resource by integrating sharable VNFs with the same type. Hence, we show here the total CPU consumption of the three algorithms with different physical network scales. In this figure, we calculated the CPU allocated towards the NSRs which are successfully mapped. Hence, the Fig. 13 should be analyzed together with Fig. 7 to show more comprehensive information. In Fig. 13, we could observe two parts: for physical network with less than 120 nodes; and for physical network with more than 120 nodes. For the first part, the three algorithms almost consume the same number of CPUs. However, as observed from Fig. 7, our SVM-VNE algorithm achieves the highest acceptance ratio, which means that with the same CPU consumption, our algorithm maps more NSRs. The similar CPU consumption comes from the facts that the physical network is underprovisioned, which is not sufficient to map all NSRs. Hence all the three algorithms are restricted by the physical resources. Then, for physical network with more than 120 nodes, firstly our algorithm maps all NSRs. As a result, the CPU consumption of our algorithm remains almost the same for physical nodes 120 to 150. Then, as the number of physical nodes increases, the baseline algorithm and the NSVM-VNE also maps all the 30 NSRs, and their CPU consumption also converges. However, for mapping the same number of NSRs, our algorithm consumes the least CPU resources.

In this paper, we investigate the 5G E2E NS deployment problem with sharable VNF instances. We formulate the multiple coupled NS virtual network embedding problem through an ILP formulation. Our design goal is to minimize the resource consumption by integrating sharable VNF instances. We design VNF-sharing based NSR deployment algorithm. We conducted intensive simulation to evaluate the performance of our algorithm under different scenarios. We investigated the NSRs acceptance ratio, instantiated number of VNFs and CPU consumption under different physical network scales, NSRs resource requirements and sharable resources percentage. The simulation results demonstrate that our algorithm achieves higher NSRs acceptance ratio, hence higher physical resource utilization, by comparing to a baseline algorithm. Further, our algorithm instantiates less VNFs, hence more VNFs are integrated. Finally, our algorithm consumes less CPU resources with higher NSRs acceptance ratio, which shows that our design goal is achieved.

Jiayi Liu obtained her Bachelors of Science degree in Electronic Engineering from Xidian University in Xi’an China, in 2007. She received her Master of Science and Ph.D., both in Computer Science, from Telecom-Bretagne and Rennes 1 University, France, in 2009 and 2013, respectively. Since 2014, she works as Lecturer with Xidian University, in School of Telecommunication Engineering and Guangzhou Institute of Technology. Her research interests include 5G network, content distribution, Network resource scheduling.

Menghan Shao received the B.S. degree in Communication Engineering from Xidian University, Xi’an, China, in 2018, where she is currently pursuing the M.S. degree in Electronics and Communication with the State Key Laboratory of Integrated Service Networks. Her research interests include 5G network, mobile edge computing.

- 1 K. Samdanis, X. Costa-Perez, V. Sciancalepore, "From network sharing to multi-tenancy: The 5G network slice broker,"
*IEEE Commun.Mag.*, vol. 54, no. 7, pp. 32-39, 2016.doi:[[[10.1109/MCOM.2016.7514161]]] - 2 X. Foukas, G. Patounas, A. Elmokashfi, M. K. Marina, "Network slicing in 5G: Survey and challenges,"
*IEEE Commun. Mag.*, vol. 55, no. 5, pp. 94-100, 2017.doi:[[[10.1109/MCOM.2017.1600951]]] - 3 V. Nguyen, A. Brunstrom, K. Grinnemo, J. Taheri, "SDN/NFV-based mobile packet core network architectures: A survey,"
*IEEE Commun.SurveysTuts.*, vol. 19, no. 3, pp. 1567-1602, 2017.doi:[[[10.1109/COMST.2017.2690823]]] - 4 X. Zhou, R. Li, T. Chen, H. Zhang, "Network slicing as a service: Enabling enterprises’ own software-defined cellular networks,"
*IEEE Commun.Mag.*, vol. 54, no. 7, pp. 146-153, 2016.custom:[[[-]]] - 5 I. Afolabi, T. Taleb, K. Samdanis, A. Ksentini, H. Flinck, "Network slicing and softwarization: A survey on principles, enabling technologies, and solutions,"
*IEEE Commu.SurveysTuts.*, vol. 20, no. 3, pp. 2429-2453, 2018.doi:[[[10.1109/COMST.2018.2815638]]] - 6 C. Liang, F. R. Yu, "Wireless network virtualization: A survey, some research issues and challenges,"
*IEEE Commun. Surveys Tuts.*, vol. 17, no. 1, pp. 358-380, 2015.doi:[[[10.1109/COMST.2014.2352118]]] - 7 X. Foukas, M. K. Marina, K. Kontovasilis, "Orion: Ran slicing for a flexible and cost-effective multi-service mobile network architecture,"
*in Proc.ACMMobiCom*, pp. 127-140, 2017.custom:[[[-]]] - 8 C. Chang, N. Nikaein, "Ran runtime slicing system for flexible and dynamic service execution environment,"
*IEEE Access*, vol. 6, pp. 34 01834 042-34 01834 042, 2018.doi:[[[10.1109/ACCESS.2018.2847610]]] - 9 J. Li et al., "Joint resource allocation and online virtual network embedding for 5G networks,"
*in Proc.IEEE GLOBECOM*, pp. 1-6, 2017.custom:[[[-]]] - 10 W. Guan, X. Wen, L. Wang, Z. Lu, Y. Shen, "A service-oriented deployment policy of end-to-end network slicing based on complex network theory,"
*IEEE Access*, vol. 6, pp. 19 691-19 701, 2018.doi:[[[10.1109/ACCESS.2018.2822398]]] - 11 R. Ferrus, O. Sallent, J. Perez-Romero, R. Agusti, "On 5G radio access network slicing: Radio interface protocol features and configuration,"
*IEEE Commun.Mag.*, vol. 56, no. 5, pp. 184-192, 2018.doi:[[[10.1109/MCOM.2017.1700268]]] - 12 Z. Kotulski, T. W. Nowak, M. Sepczuk, M. Tunia, R. Artych, K. Bocianiak, T. Osko, J. P. Wary, "Towards constructive approach to end-toend slice isolation in 5G networks,"
*EurasipJ.Inform.Securityp. 2*, vol. 2018, no. 1, 2018.custom:[[[-]]] - 13 T. Truong-Huu, P. Murali Mohan, M. Gurusamy, "Service chain embedding for diversified 5G slices with virtual network function sharing,"
*IEEE Commun.Lett.*, vol. 23, no. 5, pp. 826-829, 2019.custom:[[[-]]] - 14 S. Zhang, "An overview of network slicing for 5G,"
*IEEE Wireless Commun.*, vol. 26, no. 3, pp. 111-117, 2019.custom:[[[-]]] - 15 J. P´ erez-Romero, O. Sallent, R. Ferr´ us, R. Agust´ ı, "On the configuration of radio resource management in a sliced ran,"
*in Proc. IEEE /IFIP NOMS*, pp. 1-6, 2018.custom:[[[-]]] - 16 R. Ravindran, A. Chakraborti, S. O. Amin, A. Azgin, G. Wang, "5Gicn: Delivering icn services over 5g using network slicing,"
*IEEE Commun.Mag.*, vol. 55, no. 5, pp. 101-107, 2017.custom:[[[-]]] - 17 I. Benkacem, T. Taleb, M. Bagaa, H. Flinck, "Optimal vnfs placement in cdn slicing over multi-cloud environment,"
*IEEE J. Sel. Areas Commun.*, vol. 36, no. 3, pp. 616-627, 2018.doi:[[[10.1109/JSAC.2018.2815441]]] - 18 J. Liu, Q. Yang, G. Simon, W. Cui, "Migration-based dynamic and practical virtual streaming agent placement for mobile adaptive live streaming,"
*IEEE Trans.NetworkServiceManag.*, vol. 15, no. 2, pp. 503515-503515, 2018.doi:[[[10.1109/TNSM.2017.2740432]]] - 19 A. N. Al-Quzweeni, A. Q. Lawey, T. E. H. Elgorashi, J. M. H. Elmirghani, "Optimized energy aware 5G network function virtualization,"
*IEEE Access*, vol. 7, pp. 44 939-44 958, 2019.custom:[[[-]]] - 20 M. R. Razaetal., "Dynamic slicing approach for multi-tenant 5G transport networks,"
*IEEE /OSAJ.OpticalCommun.Netw.*, vol. 10, no. 1, pp. A77A90-A77A90, 2018.custom:[[[-]]] - 21 N. Huin, B. Jaumard, F. Giroire, "Optimal network service chain provisioning,"
*IEEE /ACMTrans.Netw.*, vol. 26, no. 3, pp. 1320-1333, 2018.custom:[[[-]]] - 22 S. Agarwal, F. Malandrino, C. Chiasserini, S. De, "Joint VNF placement and cpu allocation in 5G,"
*in Proc. IEEE INFOCOM*, pp. 1943-1951, 2018.custom:[[[-]]] - 23 A. Fischer, J. F. Botero, M. T. Beck, H. de Meer, X. Hesselbach, "Virtual network embedding: A survey,"
*IEEE Commun. Surveys Tuts.*, vol. 15, no. 4, pp. 1888-1906, 2013.doi:[[[10.1109/SURV.2013.013013.00155]]] - 24 M. Chowdhury, M. R. Rahman, R. Boutaba, "Vineyard: Virtual network embedding algorithms with coordinated node and link mapping,"
*IEEE /ACMTrans.Netw.*, vol. 20, no. 1, pp. 206-219, 2012.doi:[[[10.1109/TNET.2011.2159308]]] - 25 A. Blenk, P. Kalmbach, J. Zerwas, M. Jarschel, S. Schmid, W. Kellerer, "Neurovine: A neural preprocessor for your virtual network embedding algorithm,"
*in Proc.IEEE INFOCOM*, pp. 405-413, 2018.custom:[[[-]]] - 26 L. Gong, Y. Wen, Z. Zhu, T. Lee, "Toward profit-seeking virtual network embedding algorithm via global resource capacity,"
*in Proc. IEEE INFOCOM*, pp. 1-9, 2014.custom:[[[-]]] - 27 A. Jarray, A. Karmouch, "Decomposition approaches for virtual network embedding with one-shot node and link mapping,"
*IEEE /ACM Trans.Netw.*, vol. 23, no. 3, pp. 1012-1025, 2015.doi:[[[10.1109/TNET.2014.2312928]]] - 28 X. Cheng, S. Su, Z. Zhang, H. Wang, F. Yang, Y. Luo, J. Wang, "Virtual network embedding through topology-aware node ranking,"
*SIGCOMMComput.Commun.Rev.*, vol. 41, no. 2, pp. 38-47, Apr, 2011.doi:[[[10.1145/1971162.1971168]]] - 29 Y. Mao, Y. Guo, H. Hu, Z. Wang, T. Ma, "Sharing based virtual network embedding algorithm with dynamic resource block generation,"
*IEEE Commun.Lett.*, vol. 19, no. 12, pp. 2126-2129, 2015.doi:[[[10.1109/LCOMM.2015.2484350]]] - 30 B. Addis, D. Belabed, M. Bouet, S. Secci, "Virtual network functions placement and routing optimization,"
*in Proc. IEEE CloudNet*, pp. 171-177, 2015.custom:[[[-]]] - 31 B. Yi, X. Wang, M. Huang, "A generalized vnf sharing approach for service scheduling,"
*IEEE Commun.Lett.*, vol. 22, no. 1, pp. 73-76, 2018.doi:[[[10.1109/LCOMM.2017.2761874]]] - 32 A. L. Barabasi, R. Albert, "Emergence of scaling in random networks,"
*Science*, vol. 286, no. 5439, pp. 509-512, 1999.custom:[[[-]]] - 33 W. Chang, G. Shou, Y. Liu, Z. Guo, Y. Hu, X. Jin, "Constructing scale-free topologies for low delay of 5G,"
*in Proc. IEEE PIMRC*, pp. 1-6, 2017.custom:[[[-]]]