I. INTRODUCTION
NETWORK slicing is recognized as a key technology for the fifth generation (5G) mobile network in enabling the network to support multiple diversified vertical markets with efficiency and flexibility [1], [2]. Enabled by new maturing paradigms, such as network function virtualization (NFV) and software defined networking (SDN) [3], network slicing empowers the infrastructure provider (InP) to compose multiple separated end-to-end (E2E) logical networks over a shared common physical infrastructure and delivers different types of services based on various requirements and business needs of each vertical. It improves the intelligence of the 5G network, delivers the Network-as-a-Service business model for value creation and reduces both capital expenditure (CAPEX) and operating expense (OPEX) of the InP [4].
The 5G network slice (NS) spans across multiple parts of the 5G network, including the 5G radio access network (RAN), the 5G transport network (TN) and the 5G core network (CN). In the literature, research works related to 5G network slicing can be roughly classified into two categories [5]. Some works have been conducted on virtualizing and softwarizing the radio resource for RAN slicing [6]–[8]; whereas some works, known as E2E network slicing (or CN slicing) investigate the placement of virtual network functions (VNFs) towards the underlying physical infrastructure to form the corresponding virtual network for the slices to operate independently [9], [10]. There are also works design the interfaces and protocols between RAN slices and CN slices [11]. In the current work, we focus on the deployment of E2E 5G NSs, in which each instance of the slice must contain all the required VNFs to compose the NS’s service across the whole 5G system, from the RAN to the CN. Hence, the realization of such an E2E 5G NS is essentially the deployment of the corresponding virtual network which involves the optimization of resource allocations by considering network and computing resources. The mapping from the slice instance virtual network towards the physical infrastructure is a typical virtual network embedding (VNE) problem which has been intensively studied in the literature. However, for 5G E2E NS deployment, the specific requirements of the 5G system should be considered to reformulate the VNE problem.
One of the specific requirements of network slicing is the isolation of slice instances, whereby each slice is composed of isolated VNFs and carries specific application traffic. Hence in the literature, related works normally tackle the optimization for the deployment of multiple independent virtual networks. However, for 5G slicing, different levels of isolation can be considered [12], and some common network services or functions can be shared among multiple slice instances, such as mobility management, the network address translation (NAT) function, etc. The working of VNFs is actually realized by the instantiation of VNF instances that are software modules executed on virtual machines, and towards which a certain amount of physical resources are allocated. By allowing these common VNF to be shared among slices, less VNF instances are required to be instantiated and physical resources could be saved. Hence, in this work we consider a loosed level of isolation in which the non-security-critical VNF instances can be shared across multiple slices to further improve the utilization of the underlying physical resources [8], [13].
For NSs with sharable VNF instances, the deployment of the slice instances is essentially the embedding of multiple virtual networks coupled by the VNFs shared among these slices. Hence, the typical VNE problem should be reformulated in the context of sharable VNFs for the 5G network. In this paper, we formulate this 5G E2E sharable-VNFs-based multiple coupled VNE problem (short for SVM-VNE problem) through an integer linear program (ILP) formulation. Especially, we consider the specific topological characteristics of the 5G network. Then, we distinguish VNF types into sharable and non-sharable ones, and formulate the different resource requirements of these two. We leverage on the sharing property of VNFs to minimize the physical resources consumption. Due to the complexity of the problem, we design an heuristic algorithm to implement these NS virtual networks. Firstly, by measuring total and sharable resource requirements, we define a scheme which determines the deployment sequence of the multiple NSs. Then, for each NS instance, we adopt a back-tracking coordinated virtual node and link mapping mechanism to reduce bandwidth resource consumption. For sharable VNF mapping, we prioritize physical nodes with the same types of VNFs to reduce physical resource consumption. Finally, we conducted intensive simulations to evaluate our algorithm. The results show that VNF-sharing is beneficial for improving physical resource utilization ratio.
The remainder of this paper is organized as follows. Related works are summarized in Section II. Then, Section III describes the system model and presents the coupled multiple network slices embedding problem formulation. Our proposed sharable VNFs oriented network slices embedding algorithm is presented in Section IV. In Section V we evaluate the performance gain of our proposed algorithm. Finally, we conclude this work in Section VI.
II. RELATED WORKS
A. 5G Network Slicing
The basic idea of Network Slicing can be traced back to the infrastructure-as-a-service (IaaS) model for cloud computing, where a pool of physical resources is shared by multiple different tenants to create their logically isolated virtual systems to run their own businesses [5]. The NS is gaining extreme research interest in the development of the 5G network, because the 5G aims to explore new business models for value creation by providing tailored network services towards different types of vertical applications, such as Industry 4.0, wireless virtual/augmented reality (VR/AR) streaming, etc. The NS has been also the focus of multiple standardization organizations, for example, the logical end-to-end slicing has been included in the 3GPP Release 15 as one of the fundamental technologies for the 5G network. In [1], the authors outline the evolution from network sharing principle toward network slicing concept for the 5G network. In [2], the authors review the state-of-the-art in 5G network slicing and present a widely adopted three-layer generic framework for 5G NS.
5G NS can be roughly classified into two categories: (1) RAN slicing includes dynamic RAN composition and slice-oriented radio resource virtualization and scheduling mechanisms; (2) E2E slicing (or CN slicing) refers to the embedding of the verticals’ virtual networks towards the physical infrastructure [5], [14]. There are also works design the interfaces and protocols between RAN slices and CN slices [11]. For RAN slicing, the main issue is to allocate radio resources among multiple slices according to the channel conditions and service-level agreement (SLA) requirements of tenants, to achieve slice isolation without compromising multiplexing gain over the shared radio resources. In [7], the authors present Orion, a RAN slicing system that achieves isolation among RAN slices based on the abstraction for the virtualization of the hardware and spectrum of RAN. In [15], the authors specify a subset of RAN slice configuration parameters to drive the radio resources allocation based on the quality of service (QoS) requirement of slices.
On the other hand, the E2E slicing also stands for an important part for 5G NS. NS is service oriented, hence implementing service specific slices is achieved by the means of E2E slicing, such as information centric network (ICN) slices [16], content distribution network (CDN) slices [17], evolved multimedia broadcast multicast service (eMBMS) slices [18]. In the current paper, we focus on E2E 5G NS which spans across RAN, TN, and CN.
In [3], the authors survey the two NS enabling technologies, software defined networking (SDN) and network function virtualization (NFV), which bring virtualization and softwarization into the mobile packet core network architecture to offer the flexibility for establishing on-demand E2E network slices. In [9], the authors first determine the NS network level parameter by measuring E2E traffic at aggregation points in RAN, then, based on the formed virtual network, a virtual network embedding algorithm is proposed to implement the corresponding slices. In [10], the authors propose model and algorithm for E2E 5G NSs embedding by considering the topological information of NS virtual networks. In [19], the authors investigated 5G network function virtualization to minimize energy consumption. The VNFs deployment is formulated as a mixed integer linear program and heuristic algorithm is designed. In [20], the authors present a solution for the 5G transport network slicing problem in terms of both mixed integer linear programming formulations and heuristic algorithms.
B. Virtual Network Embedding Problem
The essential problem for 5G E2E NS implementation is the embedding of the NS corresponding virtual network, which is composed of VNFs to form the vertical’s serving system, towards the physical infrastructure. In the literature, some works consider that the slices are formed by service function chains (SFCs) with chaining structure [13], [21]. While chains can be modeled to support some types of applications, however we choose to use the more general virtual network (VN) to represent slice’s customized E2E network structure. As a matter of fact, a large part of the current related works on 5G E2E slicing use VN to represent the NS structure and model the VN by a graph [22]. Implementing an instance of a NS involves two steps: Firstly the VN is embedded by localizing both virtual nodes and virtual links, then traffic steering rules are established by the SDN controller to configure switches to route traffic accordingly. In this process, the VN embedding is essentially a VNE problem, which has been intensively studied in the literature [23].
The VNE problem can be formulated as an ILP model, and the complexity of the problem is known as NP-hard [23], [24]. In [21], the authors propose an exact mathematical model based on layered graph and column generation for the embedding of SFCs. In [25], the authors presents an approach to accelerate VNE algorithms by reducing the searching space and extracting the VN into subgraphs. There are also a large amount of efforts devoted in designing heuristic algorithms to achieve a practical solution with efficiency. Some works adopt the twostep embedding method in which the virtual nodes are firstly placed, then based on the position of virtual nodes, virtual links are mapped as multi-commodity flow problem [10], [24], [26]. This method neglects the relation between network nodes and links, which may result in less efficient usage of physical resources. Another class of methods try to place virtual nodes and links coordinately within one stage. In [27], the authors utilize the one-stage method to map nodes and links at the same time and show the benefits of this method on obtaining a better physical resource utilization. In [28], the authors apply the breadth-first search to determine the sequence of embedding virtual nodes and map links during the same stage along the node embedding process. However, for embedding 5G E2E NSs with sharable VNFs (the above defined SVM-VNE problem), it requires to extend the VNE problem and redesign algorithms by considering the specific requirements of the 5G system.
C. Network Slicing with Sharable VNFs
Despite the large amount of related works on the topic of 5G E2E slicing, the number of works on NS with sharable VNFs is very limited. In the 5G network, some common network services can be shared among multiple slice instances, such as mobility management, the network address translation (NAT) function, etc. The reutilization of these sharable VNFs can further improve the physical resource utilization ratio. In [12], the authors state that NS isolation level and strength depends on slicing requirements and usage scenarios, and a network slice instance could be partially isolated from another one. In [29], the authors investigate the VNE embedding problem to collocate multiple virtual networks within the same substrate resources by sharing underlying resource blocks dynamically to satisfy VN’s working probability and tolerance threshold. In [30], VNF locations of different types are already deployed in the physical infrastructure, the authors optimize VNF placement and routing problem with sharable VNF nodes. In [31], the authors study a sharing based SFC scheduling problem, in which SFC flows are scheduled through the already equipped VNF instances in the network to satisfy service requirements. However, the above works are not about implementing NSs with sharable VNFs among multiple different slice instances in the 5G system. In [13], the authors study the chaining-structured SFCs embedding problem with VNF instances sharing among multiple chains in the context of 5G network. As we stated in the previous section, NS is service oriented, virtual network is more general for presenting slice’s customized service system. Moreover, comparing to VNFs located in the CN, the quantity of RAN VNFs (such as virtualized BBU or MEC nodes) is larger. Hence, in our work, we consider the more general VN to represent tenant’s slice instance. We conducted simulations to compare the performance of our proposed algorithm towards the works stated in [13], the results are detailed in Section V.
III. SYSTEM MODEL AND PROBLEM FORMULATION
In Fig. 1, we illustrate 5G E2E network slices with sharable VNFs. This paper investigates the embedding of multiple NSs coupled with the sharable VNFs. In this section, we first de-
5G E2E network slices with sharable VNFs.
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.
A. Physical Infrastructure Model
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.
B. Network Slice Request Model
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},$$
An illustrative example: A 5G ICN NS.
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}.$$
C. SVM-VNE Problem Formulation
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.
IV. SVM-VNE ALGORITHM
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.
A. Network Node Importance
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.
A.1 Resource Importance
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}.$$
A.2 Topology Importance
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:
Finally, the node importance of [TeX:] $$n_{i k}^{S}$$ is calculated as:
B. Deployment Scheme for K NSRs
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:
Deployment algorithm for the K NSRs
Virtual node sorting algorithm for [TeX:] $$N S R_{k},$$
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.
C. Coordinated Mapping Algorithm for One NSR
C.1 Virtual Node Sorting
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
Candidate physical nodes selection algorithm for [TeX:] $$n_{i k}^{S}$$
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.
C.2 Candidate Physical Nodes Selection
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.
C.3 SVM-VNE Algorithm
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
SVM-VNE algorithm for [TeX:] $$N S R_{k}$$
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.
D. Practical Relevance
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
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).$$
V. EVALUATIONS
A. Simulation Setting
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.
B. Basic Performance
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.
C. Comparison to Baseline
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
Acceptance ratio with different physical networks.
Acceptance ratio with different NSRs.
Acceptance ratio with different virtual networks.
VNF instances number with different virtual network.
Acceptance ratio with different physical networks.
Acceptance ratio with different NSRs.
Acceptance ratio with different virtual networks.
VNF instances number with different virtual network.
Acceptance ratio with different VNF sharable ratio.
Acceptance ratio vs. additive CPU requirement.
Acceptance ratio with different VNF sharable ratio.
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.
Acceptance ratio vs. additive CPU requirement.
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.
VI. CONCLUSIONS
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.