# Novel Node-Ranking Approach for SDN-Based Virtual Network Embedding

Authors: Chaowei Shi; Xiangru Meng; Qiaoyan Kang; Xiaoyang Han
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Network virtualization is considered as a key technology for the future network. The emergence of software-defined network (SDN) provides a platform for the research and development of network virtualization. One of the key challenges in network virtualization is virtual network embedding (VNE). Some of the previous VNE algorithms perform virtual node embedding, which combines the nodes’ resource attributes and local topology attributes by arithmetic operations. On the one hand, it is not easy to distinguish the topological differences between SN and VN only by simple topology metrics. On the other hand, it is easy to ignore the different weight impacts of different metrics using only arithmetic operations, which will lead to an unbalanced embedding solution. To deal with these issues, we propose a novel node-ranking approach based on topology-differentiating (VNE-NRTD) for SDN-based virtual network embedding. Owing to the topological difference between SN and VN, different node metrics are used to quantify the substrate nodes and virtual nodes, respectively. Then, the nodes are ranked using the modified set pair analysis (SPA) method to avoid the unbalanced embedding solution. On this basis, we introduce the global bandwidth of the network topology into node-ranking to further improve the efficiency of node embedding. The simulation results show that the VNE-NRTD algorithm proposed in this paper outperforms other latest heuristic algorithms in terms of the VNR acceptance ratio, long-term average R/C ratio, substrate node utilization, and substrate link utilization.


---

## Body

## 1. Introduction

Over the past decades, Internet has achieved great success. However, the ossification of Internet is getting worse with the rapid growth of end-users and various applications. Inspired by the success of virtualization technology in the field of computing [1], network virtualization (NV) [2] allows multiple heterogeneous virtual networks (VNs) to run on a shared substrate network (SN) simultaneously [3] and is gradually becoming an important research topic in academia and industry recently.In the NV environments, traditional Internet service providers (ISPs) are decoupled into infrastructure providers (InPs) and service providers (SPs) [4]. The InPs are responsible for the operation and maintenance of the substrate network infrastructures. The SPs construct different VNs according to the user’s service request and rent SN resources from the InPs to fulfill these requirements, which is called virtual network embedding (VNE) [5] in academia.VNE is a process of embedding the virtual network requests (VNRs) onto the shared SN infrastructures, with the constraints of nodes (e.g., node computing capacity and node location) and links (link bandwidth). This makes the VNE be an NP-hard problem [2]; hence, a considerable volume of algorithms has been proposed to solve the VNE problem.Some studies addressed this problem with exact algorithms [7, 8]. Although it can get better results after multiple optimization computations, its computational complexity grows exponentially with the increases in the network scale [9]. Therefore, it is unsuitable to adopt exact algorithms to embed VNs for large-scale networks. Other exact-like algorithms [10] have to relax or cut down the integer variable constraints to achieve a workable VNE in a limited time.Besides, numerous heuristic algorithms [11] have been proposed to find the near-optimal solution of VNE. Part of studies [12, 13] used one-stage heuristic embedding algorithms to solve the VNE problem. The drawback of these algorithms is that it can easily lead to multiple backtracking, which affects the performance of the algorithm. Therefore, a large number of two-stage heuristic VNE algorithms [6, 14–18] have been designed over the past years, which divide VNE into two stages: (1) virtual node embedding stage and (2) virtual link embedding stage. After the nodes are successfully embedded through the greedy strategy, Dijkstra’s algorithm [19], k-shortest path algorithm [20], or multicommodity flow model [21] are used to search a loop-free path between the corresponding substrate nodes for virtual link embedding.Most of these algorithms perform node embedding only to combine the nodes’ resource attributes (e.g., nodes’ computing capability and their adjacent link bandwidths) and local topology attributes (e.g., node degree and node centrality) by simple arithmetic operations, while without fully considering the weight of different node metrics in different network environments. This would lead to the unbalance problem of these metrics and reduce the resource utilization of SN.Moreover, only the resource and topology attributes of the nodes to be embedded are considered in the node-ranking process. The attributes of its adjacent nodes and the importance of the node in the global network topology are not considered. This can easily give rise to poor node-ranking results. The other two latest heuristics consider global network resource [22, 23] during the node embedding stage. However, the global network resource metrics considered are oversimplified.On the contrary, we all know that the goal of VNE is to make full use of SN resources and improve the revenue of InPs. Therefore, it is also an important issue to efficiently adjust the entire network resources. However, the distributed architecture of the traditional networks makes it not easy for InPs to obtain global network resources in real-time and dynamically manage network resources.The emergence of the software-defined network (SDN) [24] has provided powerful convenience for the implementation and application of network virtualization, while VNE has become a heavyweight application in SDN applications. Since the SDN controller has an outstanding ability to call and control global resource, it is possible to achieve reasonable scheduling of global resource on the substrate network and improve the efficiency of resource allocation through the SDN controller.To describe the VNE problem more clearly, this paper studies the model of SDN-based VNE and lists the mathematical formulation inSection 3. VNs can be abstracted as applications for users deployed on the substrate network, which can apply for network resources from the SDN controller through the northbound interface. SDN controller can grasp the dynamic changes in the SN resources and regulate the global resource of the SN at the same time. The substrate switches forward the payload data according to the contents of the flow rule issued by the SDN controller through the southbound interface.Furthermore, in view of the low request acceptance ratio and high embedding cost in VNE, a novel node-ranking approach based on topology-differentiating is proposed for virtual network embedding. The main difference between our paper and previous works is that we take into consideration the topology difference between SN and VN and use different node metrics to quantify the substrate nodes and virtual nodes, respectively. Then, different from the previous node-ranking methods that ignore the weight difference between different metrics, the modified set pair analysis (SPA) [25] method is adopted to rank all virtual nodes and substrate nodes in advance, which can assign appropriate weights to different metrics according to the network environment. Corresponding subalgorithm is labeled as VNE-NRTD-S. Finally, the global bandwidth is introduced into the iterative operation to enhance node-ranking reliability and improve the resource utilization of SN. Corresponding subalgorithm is labeled as VNE-NRTD-G.To verify the efficiency of the proposed algorithm, a comprehensive comparison of algorithm performance is performed in this paper. The results validate that the VNE-NRTD algorithm proposed in this paper performs better than the latest three algorithms.Overall, the main contributions of this paper are summarized as follows:(i)
To describe the VNE problem more clearly, this paper studies the virtual network embedding model based on SDN. The mixed-integer linear programming (MILP) model is established for the SDN-based virtual network embedding problem, and the flow rule capacity constraint is added in the node embedding process.(ii)
A two-stage heuristic algorithm VNE-NRTD is proposed based on topology-differentiating to find the near-optimal solution of MILP. According to the topology difference between SN and VN, different node metrics are used to quantify the substrate nodes and virtual nodes, respectively. Different from the previous node-ranking methods that ignore the weight difference between different metrics, an appropriate weight is assigned to each metric and the node importance is calculated based on the modified SPA method. On this basis, the global bandwidth of the network topology is introduced into the node-ranking process to further improve the efficiency of node embedding.(iii)
Comprehensive performance evaluation is performed to verify the efficiency of the VNE-NRTD algorithm. Three typical and latest heuristic algorithms are selected for performance comparison. Simulation results vividly demonstrated that the proposed VNE-NRTD algorithm has obvious improvements compared with the selected algorithm in terms of the VNR acceptance ratio, long-term average R/C ratio, and substrate node utilization under different network environments, while reducing the substrate link utilization.The remainder of this paper is organized as follows:Section 2 briefly reviews the related work of VNE; the VNE model based on SDN is discussed in Section 3; in Section 4, we present the MILP model for VNE, and the heuristic VNE-NRTD algorithm is detailed in Section 5; extensive simulation work is implemented in Section 6; and Section 7 concludes this paper.


## 2. Related Work

VNE is formulated as a resource allocation problem, which is NP-hard. Existing VNE algorithms can be roughly divided into three categories: (i) the exact and exact-like algorithms, (ii) the metaheuristic algorithms, and (iii) the heuristic algorithms. In this section, we briefly look back on some previous and latest studies in terms of these three aspects.


### 2.1. Exact and Exact-Like VNE Algorithms

The exact algorithms solve the VNE problem based on the fixed mathematical programming model, to different goals, and the exact embedding of each given VN is different [8].Chowdhury et al. [26] first formulated the VNE as a mixed-integer program (MIP) problem through substrate network augmentation. Owing to the computational complexity of the MIP model, they relaxed the integer constraints and turned the MIP model to a linear program (LP) model. VNRs are then embedded by using deterministic and random rounding techniques. Hu et al. [7] enhanced the path-based MIP model formulated based on previous research. They developed an iterative process based on the primal-dual analysis of the MIP model, which allowed feedbacks between the link embedding subproblem and the node assignment subproblem. After multiple iterations, their decomposition approach can lead to a near-optimal solution to the VNE problem.Cao et al. [10] proposed an efficient VNE algorithm based on restrictive selection and optimization theory. The algorithm can calculate the suboptimal embedding in limited time by largely cutting down on the number of integer variables. The restrictive selection contributes to selecting candidate substrate nodes and paths.Farkiani et al. [27] used the stochastic programming framework to formulate the stochastic VNE problem for the first time. The authors used the Benders method and decomposed the stochastic VNE problem into two tractable subproblems to improve the scalability of the technique. Then, they proposed a novel iterative algorithm to reduce the problem-solving time via new acceleration techniques applied on the Benders method.The constraints of these exact algorithms are only node capacity and link bandwidth. The latest exact algorithms introduced new constraints to extend the VNE problem to a more practical online VNE process. Yang et al. [28] employed an exact VNE algorithm, which is based on the integer linear program (ILP) model, for embedding virtual network requests with location constraints. Lu et al. [29] presented a novel collaborative VNE algorithm based on the LP model, which could bring about the coordinative embedding between different VNRs.


### 2.2. Metaheuristic Algorithms

Given that the exact VNE algorithms would consume a large amount of computation time, some scholars have introduced metaheuristic algorithms into VNE, which can reduce the running time of the algorithm while ensuring the efficiency of VNE. These types of algorithms are an alternative way to obtain near-optimal solutions at a limited time, especially for NP-hard problems. In this part, we will briefly introduce the application of metaheuristic algorithms.Fajjari et al. [30] employed the ant colony optimization algorithm to deal with the VNE problem, which aims to minimize the reject rate of requests and maximize the revenue of InPs. The near-optimal solution can be found by iteratively improving candidate solutions. Zhu et al. [31] proposed a modified ant colony optimization algorithm to solve the VNE problem. The combination of revenue and acceptance ratio of an SN is used as an important component when designing the fitness function to evaluate iterative solutions obtained by ants, and the pheromone update rules are designed based on the fitness function.Pathak et al. [32] exploited the basic genetic algorithm for VNE problem to embed multiple VNRs on InPs that manage multiple SNs. However, the limitations of the genetic algorithm make the problem easy to early into the local optimal solution, and the convergence speed is slow. Liu et al. [33] established a new VNE algorithm based on mixed genetic algorithm, which regarded VNE as a MILP model to maximize the revenue of InPs. The simplex method is used to estimate the optimal direction. The proposed algorithm took advantage of the genetic algorithm and simplex method to optimize the embedding scheme, as much as possible to avoid local optimal. Zhang et al. [5] proposed an approach of VNE based on modified genetic algorithm. This algorithm considered the bandwidth utilization of link embedding as the optimization target and performed the VNE process through selection, crossover, mutation, and feasibility checking operations.Although metaheuristic algorithms can be used to find near-optimal solutions for large instances by iteratively improving a candidate solution, these algorithms are highly dependent on the initial population and the embedding results are relatively random. We intend to combine this work with deep learning and artificial intelligence in our future work.


### 2.3. Heuristic Algorithms

Owing to the limitations of exact algorithms and metaheuristic algorithms, some works have to design a large number of two-stage heuristic VNE algorithms, which consider the resource and topology information of the nodes more or less.Yu et al. [21] ranked the nodes based on local resource attributes and used a greedy algorithm to embed the virtual nodes. Wang et al. [14] considered the topology information of substrate nodes and virtual nodes, and they ranked the nodes based on its centrality. Cui et al. [15] considered the proximity of the substrate nodes corresponding to the embedded virtual nodes when ranking the substrate nodes, so as to avoid blindly calculating the global centrality of the nodes. Liu [17] et al. introduced the node topology potential to find the optimal substrate node based on the field theory, which improved the poor match between the virtual nodes and the substrate nodes.However, these algorithms perform node embedding only to combine the node’s resource attributes and local topology attributes by simple arithmetic operations, without fully considering the weight of different node metrics in different network environments. In response to this problem, Gong et al. [16] used the Technique for Order Preference by Similarity to an Ideal Solution (TOPSIS) for the first time to rank the nodes with multiple metrics. Shooshtarian et al. [18] applied the TOPSIS method to the node ranking in the process of secure VNE. Nevertheless, neither of them considered the case where the points on the vertical line are in the same distance from the positive and negative ideals.The latest VNE algorithms extend the VNE problem to a more realistic approach for more accurate and realistic online VNE processes. Chen et al. [6]. proposed a novel VNE model in SDN and P4 [34] environments that considered the label, computing, and bandwidth constraints. It generated virtual network identifiers by combining the link-grained labels with their location information. Since the virtual links are embedded onto one or more substrate links that may be connected through intermediate substrate nodes, the resource required by the intermediate substrate node to forward the data traffic is also considered in [35]. Zhao et al. [36] focused on embedding the virtual networks onto the distributed soft-defined network with multiple controllers. Zhang et al. [37] considered the storage resource parameter of the substrate nodes for the first time in the virtual network embedding, which is similar to the parameter of flow rule capacity in the SDN environment.


### 2.4. Innovations to Existing Two-Stage Heuristic Algorithms

The VNE-NRTD algorithm proposed in this paper differs from previous heuristic algorithms in four main aspects.First of all, to extend the VNE problem to a more realistic approach, we study the virtual network embedding model based on SDN. Then, according to the topological difference between SN and VN, different node metrics are used to quantify the substrate nodes and virtual nodes, respectively.Third, the importance of nodes is calculated based on the modified SPA method. On this basis, the global bandwidth of the network topology is introduced into the node-ranking process to further improve the efficiency of node embedding.Finally, we perform a comprehensive performance evaluation against typical and latest heuristic algorithms.


## 2.1. Exact and Exact-Like VNE Algorithms

The exact algorithms solve the VNE problem based on the fixed mathematical programming model, to different goals, and the exact embedding of each given VN is different [8].Chowdhury et al. [26] first formulated the VNE as a mixed-integer program (MIP) problem through substrate network augmentation. Owing to the computational complexity of the MIP model, they relaxed the integer constraints and turned the MIP model to a linear program (LP) model. VNRs are then embedded by using deterministic and random rounding techniques. Hu et al. [7] enhanced the path-based MIP model formulated based on previous research. They developed an iterative process based on the primal-dual analysis of the MIP model, which allowed feedbacks between the link embedding subproblem and the node assignment subproblem. After multiple iterations, their decomposition approach can lead to a near-optimal solution to the VNE problem.Cao et al. [10] proposed an efficient VNE algorithm based on restrictive selection and optimization theory. The algorithm can calculate the suboptimal embedding in limited time by largely cutting down on the number of integer variables. The restrictive selection contributes to selecting candidate substrate nodes and paths.Farkiani et al. [27] used the stochastic programming framework to formulate the stochastic VNE problem for the first time. The authors used the Benders method and decomposed the stochastic VNE problem into two tractable subproblems to improve the scalability of the technique. Then, they proposed a novel iterative algorithm to reduce the problem-solving time via new acceleration techniques applied on the Benders method.The constraints of these exact algorithms are only node capacity and link bandwidth. The latest exact algorithms introduced new constraints to extend the VNE problem to a more practical online VNE process. Yang et al. [28] employed an exact VNE algorithm, which is based on the integer linear program (ILP) model, for embedding virtual network requests with location constraints. Lu et al. [29] presented a novel collaborative VNE algorithm based on the LP model, which could bring about the coordinative embedding between different VNRs.


## 2.2. Metaheuristic Algorithms

Given that the exact VNE algorithms would consume a large amount of computation time, some scholars have introduced metaheuristic algorithms into VNE, which can reduce the running time of the algorithm while ensuring the efficiency of VNE. These types of algorithms are an alternative way to obtain near-optimal solutions at a limited time, especially for NP-hard problems. In this part, we will briefly introduce the application of metaheuristic algorithms.Fajjari et al. [30] employed the ant colony optimization algorithm to deal with the VNE problem, which aims to minimize the reject rate of requests and maximize the revenue of InPs. The near-optimal solution can be found by iteratively improving candidate solutions. Zhu et al. [31] proposed a modified ant colony optimization algorithm to solve the VNE problem. The combination of revenue and acceptance ratio of an SN is used as an important component when designing the fitness function to evaluate iterative solutions obtained by ants, and the pheromone update rules are designed based on the fitness function.Pathak et al. [32] exploited the basic genetic algorithm for VNE problem to embed multiple VNRs on InPs that manage multiple SNs. However, the limitations of the genetic algorithm make the problem easy to early into the local optimal solution, and the convergence speed is slow. Liu et al. [33] established a new VNE algorithm based on mixed genetic algorithm, which regarded VNE as a MILP model to maximize the revenue of InPs. The simplex method is used to estimate the optimal direction. The proposed algorithm took advantage of the genetic algorithm and simplex method to optimize the embedding scheme, as much as possible to avoid local optimal. Zhang et al. [5] proposed an approach of VNE based on modified genetic algorithm. This algorithm considered the bandwidth utilization of link embedding as the optimization target and performed the VNE process through selection, crossover, mutation, and feasibility checking operations.Although metaheuristic algorithms can be used to find near-optimal solutions for large instances by iteratively improving a candidate solution, these algorithms are highly dependent on the initial population and the embedding results are relatively random. We intend to combine this work with deep learning and artificial intelligence in our future work.


## 2.3. Heuristic Algorithms

Owing to the limitations of exact algorithms and metaheuristic algorithms, some works have to design a large number of two-stage heuristic VNE algorithms, which consider the resource and topology information of the nodes more or less.Yu et al. [21] ranked the nodes based on local resource attributes and used a greedy algorithm to embed the virtual nodes. Wang et al. [14] considered the topology information of substrate nodes and virtual nodes, and they ranked the nodes based on its centrality. Cui et al. [15] considered the proximity of the substrate nodes corresponding to the embedded virtual nodes when ranking the substrate nodes, so as to avoid blindly calculating the global centrality of the nodes. Liu [17] et al. introduced the node topology potential to find the optimal substrate node based on the field theory, which improved the poor match between the virtual nodes and the substrate nodes.However, these algorithms perform node embedding only to combine the node’s resource attributes and local topology attributes by simple arithmetic operations, without fully considering the weight of different node metrics in different network environments. In response to this problem, Gong et al. [16] used the Technique for Order Preference by Similarity to an Ideal Solution (TOPSIS) for the first time to rank the nodes with multiple metrics. Shooshtarian et al. [18] applied the TOPSIS method to the node ranking in the process of secure VNE. Nevertheless, neither of them considered the case where the points on the vertical line are in the same distance from the positive and negative ideals.The latest VNE algorithms extend the VNE problem to a more realistic approach for more accurate and realistic online VNE processes. Chen et al. [6]. proposed a novel VNE model in SDN and P4 [34] environments that considered the label, computing, and bandwidth constraints. It generated virtual network identifiers by combining the link-grained labels with their location information. Since the virtual links are embedded onto one or more substrate links that may be connected through intermediate substrate nodes, the resource required by the intermediate substrate node to forward the data traffic is also considered in [35]. Zhao et al. [36] focused on embedding the virtual networks onto the distributed soft-defined network with multiple controllers. Zhang et al. [37] considered the storage resource parameter of the substrate nodes for the first time in the virtual network embedding, which is similar to the parameter of flow rule capacity in the SDN environment.


## 2.4. Innovations to Existing Two-Stage Heuristic Algorithms

The VNE-NRTD algorithm proposed in this paper differs from previous heuristic algorithms in four main aspects.First of all, to extend the VNE problem to a more realistic approach, we study the virtual network embedding model based on SDN. Then, according to the topological difference between SN and VN, different node metrics are used to quantify the substrate nodes and virtual nodes, respectively.Third, the importance of nodes is calculated based on the modified SPA method. On this basis, the global bandwidth of the network topology is introduced into the node-ranking process to further improve the efficiency of node embedding.Finally, we perform a comprehensive performance evaluation against typical and latest heuristic algorithms.


## 3. SDN-Based VNE Model

This section describes the VNE process based on SDN, including the SDN-based VNE model, SN resources measurement, VN embedding stages, and main performance evaluation metrics.


### 3.1. VNE Model Based on SDN

Abstract modeling of SN and VN is needed in the research of VNE, so as to discuss the constraints of resource and location in the embedding process. In this section, we layer the SDN-based VNE model to discuss the hardware components and functions performed by each layer. We abstract this model into the following four layers and illustrate it in Figure1.Figure 1
VNE model based on SDN.


#### 3.1.1. User Layer

At the user layer, different tenants or applications, which can adopt different architectures and carry out different network protocols, request network resources from SPs to fulfill their functional requirements.


#### 3.1.2. Service Provide Layer

The SPs construct the logical VN topology according to the requirements of end user and rent substrate network resources from the SDN controller through the northbound interface. The VN constructed by SPs is a logical topology consisting of nodes and links, which can be abstracted as an undirected graphGv=Nv,Lv; therein, Nv represents the set of virtual nodes and Lv represents the set of virtual links. Each virtual node nv∈Nv is characterized by its required flow rule capacity Flownv and computing capability Cpunv. Each virtual link lv∈Lv has a required bandwidth Bwlv. A VNR can be defined as VNRi=Gv,Dv,Tv, where Gv indicates the VN topology and Dv is the deviation relationship between virtual node nv∈Nv and any selected substrate nodes. Tv=ta,td indicates the duration time of the VNR, where ta indicates the arrival time of the VNR and td indicates the end time of the VNR.The upper part of Figure1 illustrates two VNRs with different topologies constructed by SPs, where a, b, c, d, and e are virtual nodes. The number in the left part of the box represents the computing capability demand. The number in the right part of the box denotes the flow rule capacity demand. The number over the link denotes the required link bandwidth. For simplicity, the location constraints of virtual nodes and the time attributes of VNRs are omitted in this figure.


#### 3.1.3. Control Layer

According to [8, 38], it can be understood that FlowN adopts a logical distributed controller method, and each VN has a logical controller that can independently call and control the network resources requested by itself. Therefore, this paper chooses FlowN as the virtualization platform for VNE. On this platform, the SDN controller executes the resource scheduling algorithm, that is, the VNE-NRTD algorithm. In the control layer, the SDN controller combines the attributes of the underlying SN resources to perform resource scheduling on the OpenFlow (OF) switches in the data layer and efficiently allocates substrate network resources to each virtual network.


#### 3.1.4. Data Layer

The data layer is one or more SNs that consist of multiple OF switches with the data forwarding function. OF switches perform traffic forwarding according to the contents of the flow rules issued by the controller. In SDN architecture, the substrate network also can be abstracted as an undirected graphGs=Ns,Ls, where Ns represents the set of substrate nodes (bottom switches) and Ls represents the set of substrate links. Each substrate node is associated with its remaining computing capability RCpusns, flow rule capacity RFlowsns, and location coordinates locns that are denoted by x and y coordinates. The basic attribute of each substrate link is its remaining bandwidth RBwsls.The lower part of Figure1 illustrates a substrate network model in the control area, where A, B, C, D, E, and F are substrate nodes. The number in the left part of the box indicates the remaining computing resources of the node. The number in the right part of the box indicates the remaining flow rule capacity of the nodes. The number over the link indicates the remaining link bandwidth. Likewise, the location of substrate nodes is not plotted either.


#### 3.1.5. VNE Notations

The main notations used throughout this paper are listed in Table1.Table 1
VNE notations.
GsSubstrate networkNsSet of substrate nodesns,M,NSubstrate nodesLsSet of substrate linksls,MNSubstrate linksCpunsTotal computing capability of substrate nodesRCpusnsRemaining node computing capabilityFlownsTotal flow rule capacity of substrate nodesRFlowsnsRemaining flow rule capacity of substrate nodesBwlsTotal bandwidth of substrate linksRBwslsRemaining bandwidth of substrate linksGvVirtual networkNvSet of virtual nodesnv,m,nVirtual nodesLvSet of virtual linkslv,mnVirtual linksCpunvComputing capability demand of virtual nodesFlownvFlow rule capacity demand of virtual nodesBwlvBandwidth demand of virtual links


### 3.2. Measurement of Substrate Network Resources

In the SDN-based virtual network embedding area, the SDN controller can grasp the dynamic changes in SN resources in real time, to quantify the resource usage of substrate nodes, and the remaining available computing capability of nodeM in SN is defined as follows:(1)RCpusM=CpuM−∑∀nv↑MCpunv,where CpuM indicates the total computing capability of substrate nodes and ∀nv↑M indicates that the virtual node nv is embedded onto the substrate node M.Similarly, the remaining available flow rule capacity of nodeM in SN is defined as follows:(2)RFlowsM=FlowM−∑∀nv↑MFlownv.The remaining available bandwidth of the linkMN is defined as(3)RBwsMN=BwMN−∑∀lv↑MNBwlv,where ∀lv↑MN indicates that the virtual link lv is embedded onto the substrate link MN.


### 3.3. VNR Embedding

The embedding process of each VNR consists of the following two stages: (1) the stage dealing with the embedding of virtual nodes; (2) the stage of embedding the virtual links. The process of VNE is shown in Figure2.Figure 2
The process of VNE.


#### 3.3.1. Node Embedding Stage

Each substrate node can only host one node in the same virtual network, while the nodes in different VNs can be embedded onto the same substrate node and are subject to(4)Cpunv≤RCpusns,(5)Flownv≤RFlowsns,(6)Dislocns,locnv≤D,where equations (4) and (5) make sure that substrate nodes have sufficient computing capability and flow rule capacity to host virtual nodes. The node location constraint is defined in equation (6), the allowed maximum deviation of virtual node nv is D, and the deviation must be within the radius D of virtual nodenv. The virtual node embedding results demonstrated in Figure 1 are a⟶A,b⟶C,c⟶E and d⟶E,e⟶F.


#### 3.3.2. Link Embedding Stage

Each substrate link can host multiple virtual links in different VNs and is subject to(7)Bwlv≤RBwsls,where equation (7) ensures that the remaining bandwidth of the substrate link is greater than the bandwidth demand of the virtual link. The virtual link embedding result demonstrated in Figure 1 is a,b⟶A,C,a,c⟶A,E,b,c⟶C,E and d,e⟶E,F.


### 3.4. Performance Evaluation Metrics

#### 3.4.1. VNR Acceptance Ratio

The acceptance ratio of VNR is defined in equation (8), and it indicates the ratio of the number of successfully embedded VNRs to the total number of VNRs in the continuous time T:(8)ωaccept=limT⟶∞NUMvsucTNUMvT+δ,where NUMvsucT and NUMvT represent the number of VNRs successfully embedded and the total number of VNRs in time T, respectively. δ is an infinitely small positive number.


#### 3.4.2. Long-Term Average R/C Ratio

For InPs, the purpose of VNE is to reduce the SN resources consumption while guaranteeing revenue. This paper uses the long-term average R/C ratio to evaluate the performance of the algorithm.Similar to the work in [36], the revenue of InPs can be denoted as(9)RevGv=∑nv∈NvαCpunv+βFlownv+γ∑lv∈LvBwlv,where α, β, and γ represent the proportion of Cpunv, Flownv, and Bwlv resources in revenue and cost, respectively.Likewise, we denote the cost of SPs as the total amount of substrate resources allocated to the VNR:(10)CostGv=∑nv∈NvαCpunv+βFlownv+γ∑lv∈LvhopslvBwlv,where hopslv is the number of hops in the substrate link corresponding to the virtual link.The long-term average R/C ratio can be defined as follows:(11)RevCost=limT⟶∞∑t=0TRevGv,t∑t=0TCostGv,t.


## 3.1. VNE Model Based on SDN

Abstract modeling of SN and VN is needed in the research of VNE, so as to discuss the constraints of resource and location in the embedding process. In this section, we layer the SDN-based VNE model to discuss the hardware components and functions performed by each layer. We abstract this model into the following four layers and illustrate it in Figure1.Figure 1
VNE model based on SDN.


### 3.1.1. User Layer

At the user layer, different tenants or applications, which can adopt different architectures and carry out different network protocols, request network resources from SPs to fulfill their functional requirements.


### 3.1.2. Service Provide Layer

The SPs construct the logical VN topology according to the requirements of end user and rent substrate network resources from the SDN controller through the northbound interface. The VN constructed by SPs is a logical topology consisting of nodes and links, which can be abstracted as an undirected graphGv=Nv,Lv; therein, Nv represents the set of virtual nodes and Lv represents the set of virtual links. Each virtual node nv∈Nv is characterized by its required flow rule capacity Flownv and computing capability Cpunv. Each virtual link lv∈Lv has a required bandwidth Bwlv. A VNR can be defined as VNRi=Gv,Dv,Tv, where Gv indicates the VN topology and Dv is the deviation relationship between virtual node nv∈Nv and any selected substrate nodes. Tv=ta,td indicates the duration time of the VNR, where ta indicates the arrival time of the VNR and td indicates the end time of the VNR.The upper part of Figure1 illustrates two VNRs with different topologies constructed by SPs, where a, b, c, d, and e are virtual nodes. The number in the left part of the box represents the computing capability demand. The number in the right part of the box denotes the flow rule capacity demand. The number over the link denotes the required link bandwidth. For simplicity, the location constraints of virtual nodes and the time attributes of VNRs are omitted in this figure.


### 3.1.3. Control Layer

According to [8, 38], it can be understood that FlowN adopts a logical distributed controller method, and each VN has a logical controller that can independently call and control the network resources requested by itself. Therefore, this paper chooses FlowN as the virtualization platform for VNE. On this platform, the SDN controller executes the resource scheduling algorithm, that is, the VNE-NRTD algorithm. In the control layer, the SDN controller combines the attributes of the underlying SN resources to perform resource scheduling on the OpenFlow (OF) switches in the data layer and efficiently allocates substrate network resources to each virtual network.


### 3.1.4. Data Layer

The data layer is one or more SNs that consist of multiple OF switches with the data forwarding function. OF switches perform traffic forwarding according to the contents of the flow rules issued by the controller. In SDN architecture, the substrate network also can be abstracted as an undirected graphGs=Ns,Ls, where Ns represents the set of substrate nodes (bottom switches) and Ls represents the set of substrate links. Each substrate node is associated with its remaining computing capability RCpusns, flow rule capacity RFlowsns, and location coordinates locns that are denoted by x and y coordinates. The basic attribute of each substrate link is its remaining bandwidth RBwsls.The lower part of Figure1 illustrates a substrate network model in the control area, where A, B, C, D, E, and F are substrate nodes. The number in the left part of the box indicates the remaining computing resources of the node. The number in the right part of the box indicates the remaining flow rule capacity of the nodes. The number over the link indicates the remaining link bandwidth. Likewise, the location of substrate nodes is not plotted either.


### 3.1.5. VNE Notations

The main notations used throughout this paper are listed in Table1.Table 1
VNE notations.
GsSubstrate networkNsSet of substrate nodesns,M,NSubstrate nodesLsSet of substrate linksls,MNSubstrate linksCpunsTotal computing capability of substrate nodesRCpusnsRemaining node computing capabilityFlownsTotal flow rule capacity of substrate nodesRFlowsnsRemaining flow rule capacity of substrate nodesBwlsTotal bandwidth of substrate linksRBwslsRemaining bandwidth of substrate linksGvVirtual networkNvSet of virtual nodesnv,m,nVirtual nodesLvSet of virtual linkslv,mnVirtual linksCpunvComputing capability demand of virtual nodesFlownvFlow rule capacity demand of virtual nodesBwlvBandwidth demand of virtual links


## 3.1.1. User Layer

At the user layer, different tenants or applications, which can adopt different architectures and carry out different network protocols, request network resources from SPs to fulfill their functional requirements.


## 3.1.2. Service Provide Layer

The SPs construct the logical VN topology according to the requirements of end user and rent substrate network resources from the SDN controller through the northbound interface. The VN constructed by SPs is a logical topology consisting of nodes and links, which can be abstracted as an undirected graphGv=Nv,Lv; therein, Nv represents the set of virtual nodes and Lv represents the set of virtual links. Each virtual node nv∈Nv is characterized by its required flow rule capacity Flownv and computing capability Cpunv. Each virtual link lv∈Lv has a required bandwidth Bwlv. A VNR can be defined as VNRi=Gv,Dv,Tv, where Gv indicates the VN topology and Dv is the deviation relationship between virtual node nv∈Nv and any selected substrate nodes. Tv=ta,td indicates the duration time of the VNR, where ta indicates the arrival time of the VNR and td indicates the end time of the VNR.The upper part of Figure1 illustrates two VNRs with different topologies constructed by SPs, where a, b, c, d, and e are virtual nodes. The number in the left part of the box represents the computing capability demand. The number in the right part of the box denotes the flow rule capacity demand. The number over the link denotes the required link bandwidth. For simplicity, the location constraints of virtual nodes and the time attributes of VNRs are omitted in this figure.


## 3.1.3. Control Layer

According to [8, 38], it can be understood that FlowN adopts a logical distributed controller method, and each VN has a logical controller that can independently call and control the network resources requested by itself. Therefore, this paper chooses FlowN as the virtualization platform for VNE. On this platform, the SDN controller executes the resource scheduling algorithm, that is, the VNE-NRTD algorithm. In the control layer, the SDN controller combines the attributes of the underlying SN resources to perform resource scheduling on the OpenFlow (OF) switches in the data layer and efficiently allocates substrate network resources to each virtual network.


## 3.1.4. Data Layer

The data layer is one or more SNs that consist of multiple OF switches with the data forwarding function. OF switches perform traffic forwarding according to the contents of the flow rules issued by the controller. In SDN architecture, the substrate network also can be abstracted as an undirected graphGs=Ns,Ls, where Ns represents the set of substrate nodes (bottom switches) and Ls represents the set of substrate links. Each substrate node is associated with its remaining computing capability RCpusns, flow rule capacity RFlowsns, and location coordinates locns that are denoted by x and y coordinates. The basic attribute of each substrate link is its remaining bandwidth RBwsls.The lower part of Figure1 illustrates a substrate network model in the control area, where A, B, C, D, E, and F are substrate nodes. The number in the left part of the box indicates the remaining computing resources of the node. The number in the right part of the box indicates the remaining flow rule capacity of the nodes. The number over the link indicates the remaining link bandwidth. Likewise, the location of substrate nodes is not plotted either.


## 3.1.5. VNE Notations

The main notations used throughout this paper are listed in Table1.Table 1
VNE notations.
GsSubstrate networkNsSet of substrate nodesns,M,NSubstrate nodesLsSet of substrate linksls,MNSubstrate linksCpunsTotal computing capability of substrate nodesRCpusnsRemaining node computing capabilityFlownsTotal flow rule capacity of substrate nodesRFlowsnsRemaining flow rule capacity of substrate nodesBwlsTotal bandwidth of substrate linksRBwslsRemaining bandwidth of substrate linksGvVirtual networkNvSet of virtual nodesnv,m,nVirtual nodesLvSet of virtual linkslv,mnVirtual linksCpunvComputing capability demand of virtual nodesFlownvFlow rule capacity demand of virtual nodesBwlvBandwidth demand of virtual links


## 3.2. Measurement of Substrate Network Resources

In the SDN-based virtual network embedding area, the SDN controller can grasp the dynamic changes in SN resources in real time, to quantify the resource usage of substrate nodes, and the remaining available computing capability of nodeM in SN is defined as follows:(1)RCpusM=CpuM−∑∀nv↑MCpunv,where CpuM indicates the total computing capability of substrate nodes and ∀nv↑M indicates that the virtual node nv is embedded onto the substrate node M.Similarly, the remaining available flow rule capacity of nodeM in SN is defined as follows:(2)RFlowsM=FlowM−∑∀nv↑MFlownv.The remaining available bandwidth of the linkMN is defined as(3)RBwsMN=BwMN−∑∀lv↑MNBwlv,where ∀lv↑MN indicates that the virtual link lv is embedded onto the substrate link MN.


## 3.3. VNR Embedding

The embedding process of each VNR consists of the following two stages: (1) the stage dealing with the embedding of virtual nodes; (2) the stage of embedding the virtual links. The process of VNE is shown in Figure2.Figure 2
The process of VNE.


### 3.3.1. Node Embedding Stage

Each substrate node can only host one node in the same virtual network, while the nodes in different VNs can be embedded onto the same substrate node and are subject to(4)Cpunv≤RCpusns,(5)Flownv≤RFlowsns,(6)Dislocns,locnv≤D,where equations (4) and (5) make sure that substrate nodes have sufficient computing capability and flow rule capacity to host virtual nodes. The node location constraint is defined in equation (6), the allowed maximum deviation of virtual node nv is D, and the deviation must be within the radius D of virtual nodenv. The virtual node embedding results demonstrated in Figure 1 are a⟶A,b⟶C,c⟶E and d⟶E,e⟶F.


### 3.3.2. Link Embedding Stage

Each substrate link can host multiple virtual links in different VNs and is subject to(7)Bwlv≤RBwsls,where equation (7) ensures that the remaining bandwidth of the substrate link is greater than the bandwidth demand of the virtual link. The virtual link embedding result demonstrated in Figure 1 is a,b⟶A,C,a,c⟶A,E,b,c⟶C,E and d,e⟶E,F.


## 3.3.1. Node Embedding Stage

Each substrate node can only host one node in the same virtual network, while the nodes in different VNs can be embedded onto the same substrate node and are subject to(4)Cpunv≤RCpusns,(5)Flownv≤RFlowsns,(6)Dislocns,locnv≤D,where equations (4) and (5) make sure that substrate nodes have sufficient computing capability and flow rule capacity to host virtual nodes. The node location constraint is defined in equation (6), the allowed maximum deviation of virtual node nv is D, and the deviation must be within the radius D of virtual nodenv. The virtual node embedding results demonstrated in Figure 1 are a⟶A,b⟶C,c⟶E and d⟶E,e⟶F.


## 3.3.2. Link Embedding Stage

Each substrate link can host multiple virtual links in different VNs and is subject to(7)Bwlv≤RBwsls,where equation (7) ensures that the remaining bandwidth of the substrate link is greater than the bandwidth demand of the virtual link. The virtual link embedding result demonstrated in Figure 1 is a,b⟶A,C,a,c⟶A,E,b,c⟶C,E and d,e⟶E,F.


## 3.4. Performance Evaluation Metrics

### 3.4.1. VNR Acceptance Ratio

The acceptance ratio of VNR is defined in equation (8), and it indicates the ratio of the number of successfully embedded VNRs to the total number of VNRs in the continuous time T:(8)ωaccept=limT⟶∞NUMvsucTNUMvT+δ,where NUMvsucT and NUMvT represent the number of VNRs successfully embedded and the total number of VNRs in time T, respectively. δ is an infinitely small positive number.


### 3.4.2. Long-Term Average R/C Ratio

For InPs, the purpose of VNE is to reduce the SN resources consumption while guaranteeing revenue. This paper uses the long-term average R/C ratio to evaluate the performance of the algorithm.Similar to the work in [36], the revenue of InPs can be denoted as(9)RevGv=∑nv∈NvαCpunv+βFlownv+γ∑lv∈LvBwlv,where α, β, and γ represent the proportion of Cpunv, Flownv, and Bwlv resources in revenue and cost, respectively.Likewise, we denote the cost of SPs as the total amount of substrate resources allocated to the VNR:(10)CostGv=∑nv∈NvαCpunv+βFlownv+γ∑lv∈LvhopslvBwlv,where hopslv is the number of hops in the substrate link corresponding to the virtual link.The long-term average R/C ratio can be defined as follows:(11)RevCost=limT⟶∞∑t=0TRevGv,t∑t=0TCostGv,t.


## 3.4.1. VNR Acceptance Ratio

The acceptance ratio of VNR is defined in equation (8), and it indicates the ratio of the number of successfully embedded VNRs to the total number of VNRs in the continuous time T:(8)ωaccept=limT⟶∞NUMvsucTNUMvT+δ,where NUMvsucT and NUMvT represent the number of VNRs successfully embedded and the total number of VNRs in time T, respectively. δ is an infinitely small positive number.


## 3.4.2. Long-Term Average R/C Ratio

For InPs, the purpose of VNE is to reduce the SN resources consumption while guaranteeing revenue. This paper uses the long-term average R/C ratio to evaluate the performance of the algorithm.Similar to the work in [36], the revenue of InPs can be denoted as(9)RevGv=∑nv∈NvαCpunv+βFlownv+γ∑lv∈LvBwlv,where α, β, and γ represent the proportion of Cpunv, Flownv, and Bwlv resources in revenue and cost, respectively.Likewise, we denote the cost of SPs as the total amount of substrate resources allocated to the VNR:(10)CostGv=∑nv∈NvαCpunv+βFlownv+γ∑lv∈LvhopslvBwlv,where hopslv is the number of hops in the substrate link corresponding to the virtual link.The long-term average R/C ratio can be defined as follows:(11)RevCost=limT⟶∞∑t=0TRevGv,t∑t=0TCostGv,t.


## 4. Mixed-Integer Programming Formulation for VNE

In this paper, we formulate the MILP model intending to maximize the long-term average R/C ratio. The detailed description is presented as follows.


### 4.1. Objective Function

The objective function could be denoted as(12)maxRevCost=limT⟶∞∑t=0TRevGv,t∑t=0TCostGv,t.


### 4.2. VNE_MILP

#### 4.2.1. Variables

(13)∀m∈Nv,∀M∈Ns,ϒmM=1,ifmis embedded ontoM,0,otherwise.The binary variableϒ is used to represent the embedding relationship between the virtual node and the substrate node. In equation (13), if the virtual node m is embedded onto the substrate node M, ϒ=1; otherwise, ϒ=0.(14)∀mn∈Lv,∀MN∈Ls,ΓmnMN=1,ifmnis embedded ontoMN,0,otherwise.The binary variableΓ is used to represent the embedding relationship between the virtual link and the substrate link. In equation (14), if the virtual link mn is embedded onto the substrate link MN, ΓmnMN=1; otherwise, ΓmnMN=0.


#### 4.2.2. Constraints of Node Embedding

(15)∀m∈Nv,∀M∈Ns,ϒmMCpum≤RCpuM,(16)∀m∈Nv,∀M∈Ns,ϒmMFlowm≤RFlowM,(17)ϒmMdislocM,locm≤D,(18)∀M∈Ns,∑m∈NvϒmM≤1,(19)∀m∈Nv,∑M∈NsϒmM=1.Equation (15) ensures that the available computing capability of the candidate substrate node should be greater than the computing capability demand of the virtual node. Equation (16) ensures that the available flow rule capacity of the candidate substrate nodes should be greater than the flow rule capacity demand of the virtual node. Equation (17) is the location constraint, where dislocM,locm denotes the distance between the substrate node M and the virtual node m. Equation (18) ensures that the nodes in the same VN topology cannot be embedded onto the same substrate node. Equation (19) ensures that each virtual node can only be embedded onto at most in one substrate node.


#### 4.2.3. Constraints of Link Embedding

(20)∀M∈Ns,∀mn∈Lv,∑MN∈LsΓmnMN−∑MN∈LsΓmnNM=1,ϒmN=1,−1,ϒmM=1,0,otherwise,(21)∀mn∈Lv,∃MN∈Ls,∑MN∈LsΓmnMNBwmn≤BwMN,(22)∀mn∈Lv,∀MN∈Ls,∑MN∈LsΓmnMN≤1.Equation (20) is the connectivity constraint. It refers to the flow conservation constraint for routing one unit of net flow from virtual node m to virtual node n. Equation (21) ensures that the available bandwidth of the candidate substrate link should be greater than the bandwidth demand of the virtual link. Equation (22) ensures that there are no path splits and each virtual link is embedded onto up to one substrate path.


## 4.1. Objective Function

The objective function could be denoted as(12)maxRevCost=limT⟶∞∑t=0TRevGv,t∑t=0TCostGv,t.


## 4.2. VNE_MILP

### 4.2.1. Variables

(13)∀m∈Nv,∀M∈Ns,ϒmM=1,ifmis embedded ontoM,0,otherwise.The binary variableϒ is used to represent the embedding relationship between the virtual node and the substrate node. In equation (13), if the virtual node m is embedded onto the substrate node M, ϒ=1; otherwise, ϒ=0.(14)∀mn∈Lv,∀MN∈Ls,ΓmnMN=1,ifmnis embedded ontoMN,0,otherwise.The binary variableΓ is used to represent the embedding relationship between the virtual link and the substrate link. In equation (14), if the virtual link mn is embedded onto the substrate link MN, ΓmnMN=1; otherwise, ΓmnMN=0.


### 4.2.2. Constraints of Node Embedding

(15)∀m∈Nv,∀M∈Ns,ϒmMCpum≤RCpuM,(16)∀m∈Nv,∀M∈Ns,ϒmMFlowm≤RFlowM,(17)ϒmMdislocM,locm≤D,(18)∀M∈Ns,∑m∈NvϒmM≤1,(19)∀m∈Nv,∑M∈NsϒmM=1.Equation (15) ensures that the available computing capability of the candidate substrate node should be greater than the computing capability demand of the virtual node. Equation (16) ensures that the available flow rule capacity of the candidate substrate nodes should be greater than the flow rule capacity demand of the virtual node. Equation (17) is the location constraint, where dislocM,locm denotes the distance between the substrate node M and the virtual node m. Equation (18) ensures that the nodes in the same VN topology cannot be embedded onto the same substrate node. Equation (19) ensures that each virtual node can only be embedded onto at most in one substrate node.


### 4.2.3. Constraints of Link Embedding

(20)∀M∈Ns,∀mn∈Lv,∑MN∈LsΓmnMN−∑MN∈LsΓmnNM=1,ϒmN=1,−1,ϒmM=1,0,otherwise,(21)∀mn∈Lv,∃MN∈Ls,∑MN∈LsΓmnMNBwmn≤BwMN,(22)∀mn∈Lv,∀MN∈Ls,∑MN∈LsΓmnMN≤1.Equation (20) is the connectivity constraint. It refers to the flow conservation constraint for routing one unit of net flow from virtual node m to virtual node n. Equation (21) ensures that the available bandwidth of the candidate substrate link should be greater than the bandwidth demand of the virtual link. Equation (22) ensures that there are no path splits and each virtual link is embedded onto up to one substrate path.


## 4.2.1. Variables

(13)∀m∈Nv,∀M∈Ns,ϒmM=1,ifmis embedded ontoM,0,otherwise.The binary variableϒ is used to represent the embedding relationship between the virtual node and the substrate node. In equation (13), if the virtual node m is embedded onto the substrate node M, ϒ=1; otherwise, ϒ=0.(14)∀mn∈Lv,∀MN∈Ls,ΓmnMN=1,ifmnis embedded ontoMN,0,otherwise.The binary variableΓ is used to represent the embedding relationship between the virtual link and the substrate link. In equation (14), if the virtual link mn is embedded onto the substrate link MN, ΓmnMN=1; otherwise, ΓmnMN=0.


## 4.2.2. Constraints of Node Embedding

(15)∀m∈Nv,∀M∈Ns,ϒmMCpum≤RCpuM,(16)∀m∈Nv,∀M∈Ns,ϒmMFlowm≤RFlowM,(17)ϒmMdislocM,locm≤D,(18)∀M∈Ns,∑m∈NvϒmM≤1,(19)∀m∈Nv,∑M∈NsϒmM=1.Equation (15) ensures that the available computing capability of the candidate substrate node should be greater than the computing capability demand of the virtual node. Equation (16) ensures that the available flow rule capacity of the candidate substrate nodes should be greater than the flow rule capacity demand of the virtual node. Equation (17) is the location constraint, where dislocM,locm denotes the distance between the substrate node M and the virtual node m. Equation (18) ensures that the nodes in the same VN topology cannot be embedded onto the same substrate node. Equation (19) ensures that each virtual node can only be embedded onto at most in one substrate node.


## 4.2.3. Constraints of Link Embedding

(20)∀M∈Ns,∀mn∈Lv,∑MN∈LsΓmnMN−∑MN∈LsΓmnNM=1,ϒmN=1,−1,ϒmM=1,0,otherwise,(21)∀mn∈Lv,∃MN∈Ls,∑MN∈LsΓmnMNBwmn≤BwMN,(22)∀mn∈Lv,∀MN∈Ls,∑MN∈LsΓmnMN≤1.Equation (20) is the connectivity constraint. It refers to the flow conservation constraint for routing one unit of net flow from virtual node m to virtual node n. Equation (21) ensures that the available bandwidth of the candidate substrate link should be greater than the bandwidth demand of the virtual link. Equation (22) ensures that there are no path splits and each virtual link is embedded onto up to one substrate path.


## 5. Heuristic Algorithm Design

Owing to the high complexity of the exact algorithm, it is unsuitable for large-scale network topology environments. Therefore, we propose a novel heuristic algorithm called VNE-NRTD to find the near-optimal solution of MILP.This section details the proposed VNE-NRTD algorithm. We first introduce the node-ranking metrics. Then, two novel node-ranking methods are introduced. Based on the results of node ranking, the greedy strategy is used for node embedding. After the nodes are embedded successfully, the shortest path algorithm is used to perform virtual link embedding. Finally, we analyze the algorithm complexity and validate that the VNE-NRTD algorithm proposed in this paper is polynomial time-solvable.


### 5.1. Node-Ranking Metrics

Similar to [8], the importance of node n is measured by the node’s computing capability Cpuni, flow rule capacity Flowni, and the total bandwidth (Bwl) of its adjacent links in the network. According to the topological difference between SN and VN, different node topology metrics are used to quantify the substrate nodes and virtual nodes, respectively. The detailed metrics are defined as follows.


#### 5.1.1. Central Aggregation of Virtual Nodes

This paper uses node proximity clustering degree and node centrality to indicate the topological characteristics of virtual nodes. Node degree is used to represent the node proximity clustering degree, which indicates the number of nodes directly connected to the node. Node centrality represents the centrality of nodes in the global topology. The formulation is defined as follows:(23)Cniv=TDniv∑j=1mdi,j,where TDniv is the number of adjacent nodes of the ranked node. ∑j=1mdi,j is the sum of the shortest distances between the ranked node and all other nodes, which indicate the global topological characteristics of the ranked node.


#### 5.1.2. Closeness Aggregation Degree of Substrate Nodes

In this paper, the closeness degree and the aggregation degree of the substrate node are used to jointly represent the substrate node topology characteristics. The formulation is defined as follows:(24)Cnis=TDnisδ+∑nj∈ψndi,j,where TDnis is the number of adjacent nodes of the ranked substrate node, δ is an infinitely small positive number, ψn represents the set of substrate nodes that have already hosted the virtual nodes contained in the VNR, and di,j is the number of hops for the shortest path between two substrate nodes.It is preferable to embed the virtual node with a higher central aggregation degree first, which can make the virtual node that has a large number of adjacent nodes in the virtual network and close to the center of the network preferentially embedded. On the contrary, embedding virtual nodes onto a substrate node with high closeness aggregation degree can make the virtual nodes in the same virtual network embedded to substrate nodes closer, which can save more bandwidth resources.


### 5.2. Node-Ranking Methods

#### 5.2.1. Principle of SPA

The core idea of SPA is to regard certainty and uncertainty as a certain uncertain system. It uses identity, discrepancy, and contradistinction components of connection degree to describe the different properties of internal relation between two sets. Therefore, the basis of SPA is set pair, and its key is connection degree.Suppose the setsA=x1,x2,…,xn and B=y1,y2,…,yn, respectively. The set pair H=A,B is constructed of set A and relative set B. The connection degree between sets A and B can be defined as follows:(25)μAB=sn+fnI+pnJ=a+bI+cJ,where s is the number of the identical characteristics, p is the number of the contradictory characteristics, and f=n−s−p is the number of the discrepant characteristics. It is marked that a=s/n is the identity degree of sets A and B, b=f/n is the discrepancy degree, and c=p/n is the contradistinction degree. I is the uncertainty coefficient of discrepancy, which has different values in [−1, 1] according to different conditions. J is the contradictory coefficient, which has value of −1. The vector a,b,c consisting of the identity degree (a), the discrepancy degree (b), and the contradistinction degree (c) is defined as the connection vector of sets A and B, and it can be denoted as μ=a,b,c. The connection vector distance between sets A and B can be defined as follows:(26)d=1−a2+b2+c2.


#### 5.2.2. Steps of VNE-NRTD-S Algorithm Based on Modified SPA Method

The SPA method is modified based on the TOPSIS method in this paper, the positive and negative ideal schemes can be obtained by the TOPSIS method, and the relative contact degrees between each scheme and ideal schemes can be obtained by their connection degrees. The steps of VNE-NRTD-S algorithm are detailed as follows.Step 1.
Build a decision-making matrix.
Suppose there areK objects that need to be ranked, which represent different nodes to be embedded. Each node has Q evaluation metrics. The value of the j-th evaluation metric of the i-th node is denoted as Xiji=1,2,…,K;j=1,2,…,Q. The decision-making matrix formed by all network nodes and their evaluation metrics is defined as follows:(27)X=x11x12⋯x1Qx21x22⋯x2Q⋮⋮⋱⋮xK1xK2⋯xKQ.Step 2.
Normalize the decision-making matrix.
Because the dimensions of each metric are different, there may be order of magnitude differences. It is inconvenient to make direct comparisons. The metrics need to be normalized, so as to eliminate the dimensional differences between metrics:(28)yij=xij∑i=1Kxij.
Then, the standard normalization matrix can be defined as follows:(29)Y=y11y12⋯y1Qy21y22⋯y2Q⋮⋮⋱⋮yK1yK2⋯yKQ.Step 3.
Calculate the weighted normalized decision-making matrix.
The weight of thej-th evaluation metric can be represented by wjj=1,2,…,Q,0≤wj≤1,∑j=1Qwj=1. The weighted normalized decision-making matrix is defined as follows:(30)Z=w1y11w2y12⋯wQy1Qw1y21w2y22⋯wQy2Q⋮⋮⋱⋮w1yK1w2yK2⋯wQyKQ.Step 4.
Determine the positive ideal schemeA+ and negative ideal scheme A−, and the formulations are defined as follows:(31)A+=maxzi1,zi2,…,ziQ=z1max,z2max,…,zQmax,A−=minzi1,zi2,…,ziQ=z1min,z2min,…,zQmin.
The scheme of each node can form a set pair with the positive ideal scheme, denoted asHA+,Zk. Likewise, the scheme of each node can also form a set pair with the negative ideal scheme, denoted as HA−,Zk.Step 5.
Calculate the connection degree of each schemeZk to the positive ideal scheme A+, and the formulation is defined as follows:(32)μk+=ak++bk+I+ck+J=w1μk1++w2μk2++⋯+wQμkQ+=∑t=1Qwtμkt+μkt+=akt++bkt+I+ckt+J,k=1,2,…,K;t=1,2,…,Q,in which when ykt=ztmin, akt+=bkt+=0andckt+=1, and when ykt∈ztmin,ztmax, akt+=ykt/ztmax,bkt+=1−akt+,andckt+=0.Step 6.
Calculate the connection degree of each schemeZk to the negative ideal scheme A−, and the formulation is defined as follows:(33)μk−=ak−+bk−I+ck−J=w1μk1−+w2μk2−+⋯+wQμkQ−=∑t=1Qwtμkt−μkt−=akt−+bkt−I+ckt−J,k=1,2,…,K;t=1,2,…,Q,in which when ykt=ztmax, akt−=bkt−=0andckt−=1, and when ykt∈ztmin,ztmax), akt−=ztmin/ykt,bkt−=1−akt−,andckt−=0.Step 7.
Calculate the connection vector distance of each scheme to the positive ideal and negative ideal schemes, respectively. The formulations are defined as follows:(34)Dk+=1−ak+2+bk+2+ck+2,Dk−=1−ak−2+bk−2+ck−2.Step 8.
Calculate the similarity between each scheme and the ideal one, and the formulation is defined as follows:(35)Sk=Dk−Dk−+Dk+,0≤Sk≤1.Step 9.
Rank the nodes bySk in decreasing order. The nodes with larger Sk have higher importance in the network.


#### 5.2.3. Steps of VNE-NRTD-G Algorithm

The global bandwidth of the network topology is introduced into the node-ranking process to further improve the performance of the algorithm. The steps of the VNE-NRTD-G algorithm are detailed as follows:Step 1: for each node in the network, normalize the similarity between each scheme and the ideal scheme:(36)Ck=Sk∑k=1KSi,0≤Sk≤1.Step 2: introduce the global bandwidth of the network topology and calculate the node importance in a recursive manner. The formulation is presented as follows:(37)Rk=λ⋅Ck+1−λ∑m∈NbkBwlmk∑n∈NbmBwlmn⋅Rm,(38)R=λ⋅CR+1−λMR⋅R,(39)Mk,m=Bwlmk∑n∈NbmBwlmn.Step 3: rank the nodes byRk in decreasing order. The nodes with larger Rk have higher importance in the network.whereλ is the damping factor within (0, 1), Nbk indicates the set of the neighbor nodes of nodenk, and Ckis the normalized Sk of node nk in the network.To calculate theRk of all nodes, the traffic form of all node importance is expanded and the vector format is defined as follows:whereR=R1,R2,…,Rk,…,RKT. λ is a factor, and λ∈0,1. CR=C1,C2,…,Ck,…,CKT, MR is the transition matrix with dimensions of K×K, each dimension corresponds to the data for the two adjacent points, and Mk,m is defined as follows:


### 5.3. Virtual Node Embedding

The VNE-NRTD algorithm proposed in this paper embeds the virtual nodes through greedy way. The detailed procedure is illustrated in Algorithm1 (VNE-NRTD-S) and Algorithm 2 (VNE-NRTD-G).Algorithm 1: VNE-NRTD-S.
(1)
Calculate the node-ranking valueSk of virtual nodes according to equation (35)(2)
for all unembedded virtual nodes in VNR(3)
Select the virtual nodenk with the highest node-ranking value Sk(4)
Rank the virtual nodes using breadth first search (BFS) algorithm and put the ranking results into Virtual_node_list1(5)
end for(6)
for each unembedded virtual node in Virtual_node_list1(7)
Filter the set of substrate nodes that meet the resource and location constraints ofnk(8)
Calculate the node-ranking valueSk of substrate nodes according to equation (35)(9)
Rank the substrate nodes bySk in decreasing order(10)
Embed the virtual node onto the substrate node with the highestSk(11)
end forAlgorithm 2: VNE-NRTD-G.
(1)
Calculate the node-ranking valueRk of virtual nodes according to equation (37)(2)
for all unembedded virtual nodes in VNR(3)
Select the virtual nodenk with the highest node-ranking value Rk(4)
Rank the virtual nodes using BFS algorithm and put the ranking results into Virtual_node_list2(5)
end for(6)
for each unembedded virtual node in Virtual_node_list2(7)
Filter the set of substrate nodes that meet the resource and location constraints of virtual node(8)
Calculate the node-ranking valueRk of substrate nodes according to equation (37)(9)
Rank the substrate nodes byRk in decreasing order(10)
Embed the virtual node onto the substrate node with the highestRk(11)
end for


### 5.4. Virtual Link Embedding

If there is a node embedding failure in the VNR, the link embedding is not performed. Otherwise, theshortest path algorithm is used to search the shortest path between the nodes. The detailed steps of virtual link embedding algorithm are shown in Algorithm 3.Algorithm 3: The link embedding algorithm based on the shortest path algorithm.
(1)
Rank the virtual links by the required bandwidth in decreasing order(2)
for all unembedded virtual links in VNR(3)
Fetch two corresponding substrate nodes for the virtual link(4)
Remove the substrate links whose bandwidth is less than the required amount of bandwidth(5)
Choose a loop-free substrate path between the corresponding nodes usingshortest path algorithm(6)
Embed the virtual link onto the choose substrate path(7)
end for


### 5.5. Time Complexity of VNE-NRTD

For all virtual nodes in the VNR, the time complexities corresponding to calculating theSk and Rk of the candidate substrate node are ONvNs2 and ONvNs2+NvNs2log1/δ [40], respectively. The time complexity of link embedding is OLvNs2. Therefore, the time complexity of VNE-NRTD-S is ONvNs2+LvNs2, and the time complexity of VNE-NRTD-G is ONvNs2+NvNs2log1/δ+Lv|Ns2.Overall, compared with other algorithms, the proposed algorithm, either VNE-NRTD-G or VNE-NRTD-S, runs in polynomial time and can be simulated in a continuous time event.


## 5.1. Node-Ranking Metrics

Similar to [8], the importance of node n is measured by the node’s computing capability Cpuni, flow rule capacity Flowni, and the total bandwidth (Bwl) of its adjacent links in the network. According to the topological difference between SN and VN, different node topology metrics are used to quantify the substrate nodes and virtual nodes, respectively. The detailed metrics are defined as follows.


### 5.1.1. Central Aggregation of Virtual Nodes

This paper uses node proximity clustering degree and node centrality to indicate the topological characteristics of virtual nodes. Node degree is used to represent the node proximity clustering degree, which indicates the number of nodes directly connected to the node. Node centrality represents the centrality of nodes in the global topology. The formulation is defined as follows:(23)Cniv=TDniv∑j=1mdi,j,where TDniv is the number of adjacent nodes of the ranked node. ∑j=1mdi,j is the sum of the shortest distances between the ranked node and all other nodes, which indicate the global topological characteristics of the ranked node.


### 5.1.2. Closeness Aggregation Degree of Substrate Nodes

In this paper, the closeness degree and the aggregation degree of the substrate node are used to jointly represent the substrate node topology characteristics. The formulation is defined as follows:(24)Cnis=TDnisδ+∑nj∈ψndi,j,where TDnis is the number of adjacent nodes of the ranked substrate node, δ is an infinitely small positive number, ψn represents the set of substrate nodes that have already hosted the virtual nodes contained in the VNR, and di,j is the number of hops for the shortest path between two substrate nodes.It is preferable to embed the virtual node with a higher central aggregation degree first, which can make the virtual node that has a large number of adjacent nodes in the virtual network and close to the center of the network preferentially embedded. On the contrary, embedding virtual nodes onto a substrate node with high closeness aggregation degree can make the virtual nodes in the same virtual network embedded to substrate nodes closer, which can save more bandwidth resources.


## 5.1.1. Central Aggregation of Virtual Nodes

This paper uses node proximity clustering degree and node centrality to indicate the topological characteristics of virtual nodes. Node degree is used to represent the node proximity clustering degree, which indicates the number of nodes directly connected to the node. Node centrality represents the centrality of nodes in the global topology. The formulation is defined as follows:(23)Cniv=TDniv∑j=1mdi,j,where TDniv is the number of adjacent nodes of the ranked node. ∑j=1mdi,j is the sum of the shortest distances between the ranked node and all other nodes, which indicate the global topological characteristics of the ranked node.


## 5.1.2. Closeness Aggregation Degree of Substrate Nodes

In this paper, the closeness degree and the aggregation degree of the substrate node are used to jointly represent the substrate node topology characteristics. The formulation is defined as follows:(24)Cnis=TDnisδ+∑nj∈ψndi,j,where TDnis is the number of adjacent nodes of the ranked substrate node, δ is an infinitely small positive number, ψn represents the set of substrate nodes that have already hosted the virtual nodes contained in the VNR, and di,j is the number of hops for the shortest path between two substrate nodes.It is preferable to embed the virtual node with a higher central aggregation degree first, which can make the virtual node that has a large number of adjacent nodes in the virtual network and close to the center of the network preferentially embedded. On the contrary, embedding virtual nodes onto a substrate node with high closeness aggregation degree can make the virtual nodes in the same virtual network embedded to substrate nodes closer, which can save more bandwidth resources.


## 5.2. Node-Ranking Methods

### 5.2.1. Principle of SPA

The core idea of SPA is to regard certainty and uncertainty as a certain uncertain system. It uses identity, discrepancy, and contradistinction components of connection degree to describe the different properties of internal relation between two sets. Therefore, the basis of SPA is set pair, and its key is connection degree.Suppose the setsA=x1,x2,…,xn and B=y1,y2,…,yn, respectively. The set pair H=A,B is constructed of set A and relative set B. The connection degree between sets A and B can be defined as follows:(25)μAB=sn+fnI+pnJ=a+bI+cJ,where s is the number of the identical characteristics, p is the number of the contradictory characteristics, and f=n−s−p is the number of the discrepant characteristics. It is marked that a=s/n is the identity degree of sets A and B, b=f/n is the discrepancy degree, and c=p/n is the contradistinction degree. I is the uncertainty coefficient of discrepancy, which has different values in [−1, 1] according to different conditions. J is the contradictory coefficient, which has value of −1. The vector a,b,c consisting of the identity degree (a), the discrepancy degree (b), and the contradistinction degree (c) is defined as the connection vector of sets A and B, and it can be denoted as μ=a,b,c. The connection vector distance between sets A and B can be defined as follows:(26)d=1−a2+b2+c2.


### 5.2.2. Steps of VNE-NRTD-S Algorithm Based on Modified SPA Method

The SPA method is modified based on the TOPSIS method in this paper, the positive and negative ideal schemes can be obtained by the TOPSIS method, and the relative contact degrees between each scheme and ideal schemes can be obtained by their connection degrees. The steps of VNE-NRTD-S algorithm are detailed as follows.Step 1.
Build a decision-making matrix.
Suppose there areK objects that need to be ranked, which represent different nodes to be embedded. Each node has Q evaluation metrics. The value of the j-th evaluation metric of the i-th node is denoted as Xiji=1,2,…,K;j=1,2,…,Q. The decision-making matrix formed by all network nodes and their evaluation metrics is defined as follows:(27)X=x11x12⋯x1Qx21x22⋯x2Q⋮⋮⋱⋮xK1xK2⋯xKQ.Step 2.
Normalize the decision-making matrix.
Because the dimensions of each metric are different, there may be order of magnitude differences. It is inconvenient to make direct comparisons. The metrics need to be normalized, so as to eliminate the dimensional differences between metrics:(28)yij=xij∑i=1Kxij.
Then, the standard normalization matrix can be defined as follows:(29)Y=y11y12⋯y1Qy21y22⋯y2Q⋮⋮⋱⋮yK1yK2⋯yKQ.Step 3.
Calculate the weighted normalized decision-making matrix.
The weight of thej-th evaluation metric can be represented by wjj=1,2,…,Q,0≤wj≤1,∑j=1Qwj=1. The weighted normalized decision-making matrix is defined as follows:(30)Z=w1y11w2y12⋯wQy1Qw1y21w2y22⋯wQy2Q⋮⋮⋱⋮w1yK1w2yK2⋯wQyKQ.Step 4.
Determine the positive ideal schemeA+ and negative ideal scheme A−, and the formulations are defined as follows:(31)A+=maxzi1,zi2,…,ziQ=z1max,z2max,…,zQmax,A−=minzi1,zi2,…,ziQ=z1min,z2min,…,zQmin.
The scheme of each node can form a set pair with the positive ideal scheme, denoted asHA+,Zk. Likewise, the scheme of each node can also form a set pair with the negative ideal scheme, denoted as HA−,Zk.Step 5.
Calculate the connection degree of each schemeZk to the positive ideal scheme A+, and the formulation is defined as follows:(32)μk+=ak++bk+I+ck+J=w1μk1++w2μk2++⋯+wQμkQ+=∑t=1Qwtμkt+μkt+=akt++bkt+I+ckt+J,k=1,2,…,K;t=1,2,…,Q,in which when ykt=ztmin, akt+=bkt+=0andckt+=1, and when ykt∈ztmin,ztmax, akt+=ykt/ztmax,bkt+=1−akt+,andckt+=0.Step 6.
Calculate the connection degree of each schemeZk to the negative ideal scheme A−, and the formulation is defined as follows:(33)μk−=ak−+bk−I+ck−J=w1μk1−+w2μk2−+⋯+wQμkQ−=∑t=1Qwtμkt−μkt−=akt−+bkt−I+ckt−J,k=1,2,…,K;t=1,2,…,Q,in which when ykt=ztmax, akt−=bkt−=0andckt−=1, and when ykt∈ztmin,ztmax), akt−=ztmin/ykt,bkt−=1−akt−,andckt−=0.Step 7.
Calculate the connection vector distance of each scheme to the positive ideal and negative ideal schemes, respectively. The formulations are defined as follows:(34)Dk+=1−ak+2+bk+2+ck+2,Dk−=1−ak−2+bk−2+ck−2.Step 8.
Calculate the similarity between each scheme and the ideal one, and the formulation is defined as follows:(35)Sk=Dk−Dk−+Dk+,0≤Sk≤1.Step 9.
Rank the nodes bySk in decreasing order. The nodes with larger Sk have higher importance in the network.


### 5.2.3. Steps of VNE-NRTD-G Algorithm

The global bandwidth of the network topology is introduced into the node-ranking process to further improve the performance of the algorithm. The steps of the VNE-NRTD-G algorithm are detailed as follows:Step 1: for each node in the network, normalize the similarity between each scheme and the ideal scheme:(36)Ck=Sk∑k=1KSi,0≤Sk≤1.Step 2: introduce the global bandwidth of the network topology and calculate the node importance in a recursive manner. The formulation is presented as follows:(37)Rk=λ⋅Ck+1−λ∑m∈NbkBwlmk∑n∈NbmBwlmn⋅Rm,(38)R=λ⋅CR+1−λMR⋅R,(39)Mk,m=Bwlmk∑n∈NbmBwlmn.Step 3: rank the nodes byRk in decreasing order. The nodes with larger Rk have higher importance in the network.whereλ is the damping factor within (0, 1), Nbk indicates the set of the neighbor nodes of nodenk, and Ckis the normalized Sk of node nk in the network.To calculate theRk of all nodes, the traffic form of all node importance is expanded and the vector format is defined as follows:whereR=R1,R2,…,Rk,…,RKT. λ is a factor, and λ∈0,1. CR=C1,C2,…,Ck,…,CKT, MR is the transition matrix with dimensions of K×K, each dimension corresponds to the data for the two adjacent points, and Mk,m is defined as follows:


## 5.2.1. Principle of SPA

The core idea of SPA is to regard certainty and uncertainty as a certain uncertain system. It uses identity, discrepancy, and contradistinction components of connection degree to describe the different properties of internal relation between two sets. Therefore, the basis of SPA is set pair, and its key is connection degree.Suppose the setsA=x1,x2,…,xn and B=y1,y2,…,yn, respectively. The set pair H=A,B is constructed of set A and relative set B. The connection degree between sets A and B can be defined as follows:(25)μAB=sn+fnI+pnJ=a+bI+cJ,where s is the number of the identical characteristics, p is the number of the contradictory characteristics, and f=n−s−p is the number of the discrepant characteristics. It is marked that a=s/n is the identity degree of sets A and B, b=f/n is the discrepancy degree, and c=p/n is the contradistinction degree. I is the uncertainty coefficient of discrepancy, which has different values in [−1, 1] according to different conditions. J is the contradictory coefficient, which has value of −1. The vector a,b,c consisting of the identity degree (a), the discrepancy degree (b), and the contradistinction degree (c) is defined as the connection vector of sets A and B, and it can be denoted as μ=a,b,c. The connection vector distance between sets A and B can be defined as follows:(26)d=1−a2+b2+c2.


## 5.2.2. Steps of VNE-NRTD-S Algorithm Based on Modified SPA Method

The SPA method is modified based on the TOPSIS method in this paper, the positive and negative ideal schemes can be obtained by the TOPSIS method, and the relative contact degrees between each scheme and ideal schemes can be obtained by their connection degrees. The steps of VNE-NRTD-S algorithm are detailed as follows.Step 1.
Build a decision-making matrix.
Suppose there areK objects that need to be ranked, which represent different nodes to be embedded. Each node has Q evaluation metrics. The value of the j-th evaluation metric of the i-th node is denoted as Xiji=1,2,…,K;j=1,2,…,Q. The decision-making matrix formed by all network nodes and their evaluation metrics is defined as follows:(27)X=x11x12⋯x1Qx21x22⋯x2Q⋮⋮⋱⋮xK1xK2⋯xKQ.Step 2.
Normalize the decision-making matrix.
Because the dimensions of each metric are different, there may be order of magnitude differences. It is inconvenient to make direct comparisons. The metrics need to be normalized, so as to eliminate the dimensional differences between metrics:(28)yij=xij∑i=1Kxij.
Then, the standard normalization matrix can be defined as follows:(29)Y=y11y12⋯y1Qy21y22⋯y2Q⋮⋮⋱⋮yK1yK2⋯yKQ.Step 3.
Calculate the weighted normalized decision-making matrix.
The weight of thej-th evaluation metric can be represented by wjj=1,2,…,Q,0≤wj≤1,∑j=1Qwj=1. The weighted normalized decision-making matrix is defined as follows:(30)Z=w1y11w2y12⋯wQy1Qw1y21w2y22⋯wQy2Q⋮⋮⋱⋮w1yK1w2yK2⋯wQyKQ.Step 4.
Determine the positive ideal schemeA+ and negative ideal scheme A−, and the formulations are defined as follows:(31)A+=maxzi1,zi2,…,ziQ=z1max,z2max,…,zQmax,A−=minzi1,zi2,…,ziQ=z1min,z2min,…,zQmin.
The scheme of each node can form a set pair with the positive ideal scheme, denoted asHA+,Zk. Likewise, the scheme of each node can also form a set pair with the negative ideal scheme, denoted as HA−,Zk.Step 5.
Calculate the connection degree of each schemeZk to the positive ideal scheme A+, and the formulation is defined as follows:(32)μk+=ak++bk+I+ck+J=w1μk1++w2μk2++⋯+wQμkQ+=∑t=1Qwtμkt+μkt+=akt++bkt+I+ckt+J,k=1,2,…,K;t=1,2,…,Q,in which when ykt=ztmin, akt+=bkt+=0andckt+=1, and when ykt∈ztmin,ztmax, akt+=ykt/ztmax,bkt+=1−akt+,andckt+=0.Step 6.
Calculate the connection degree of each schemeZk to the negative ideal scheme A−, and the formulation is defined as follows:(33)μk−=ak−+bk−I+ck−J=w1μk1−+w2μk2−+⋯+wQμkQ−=∑t=1Qwtμkt−μkt−=akt−+bkt−I+ckt−J,k=1,2,…,K;t=1,2,…,Q,in which when ykt=ztmax, akt−=bkt−=0andckt−=1, and when ykt∈ztmin,ztmax), akt−=ztmin/ykt,bkt−=1−akt−,andckt−=0.Step 7.
Calculate the connection vector distance of each scheme to the positive ideal and negative ideal schemes, respectively. The formulations are defined as follows:(34)Dk+=1−ak+2+bk+2+ck+2,Dk−=1−ak−2+bk−2+ck−2.Step 8.
Calculate the similarity between each scheme and the ideal one, and the formulation is defined as follows:(35)Sk=Dk−Dk−+Dk+,0≤Sk≤1.Step 9.
Rank the nodes bySk in decreasing order. The nodes with larger Sk have higher importance in the network.


## 5.2.3. Steps of VNE-NRTD-G Algorithm

The global bandwidth of the network topology is introduced into the node-ranking process to further improve the performance of the algorithm. The steps of the VNE-NRTD-G algorithm are detailed as follows:Step 1: for each node in the network, normalize the similarity between each scheme and the ideal scheme:(36)Ck=Sk∑k=1KSi,0≤Sk≤1.Step 2: introduce the global bandwidth of the network topology and calculate the node importance in a recursive manner. The formulation is presented as follows:(37)Rk=λ⋅Ck+1−λ∑m∈NbkBwlmk∑n∈NbmBwlmn⋅Rm,(38)R=λ⋅CR+1−λMR⋅R,(39)Mk,m=Bwlmk∑n∈NbmBwlmn.Step 3: rank the nodes byRk in decreasing order. The nodes with larger Rk have higher importance in the network.whereλ is the damping factor within (0, 1), Nbk indicates the set of the neighbor nodes of nodenk, and Ckis the normalized Sk of node nk in the network.To calculate theRk of all nodes, the traffic form of all node importance is expanded and the vector format is defined as follows:whereR=R1,R2,…,Rk,…,RKT. λ is a factor, and λ∈0,1. CR=C1,C2,…,Ck,…,CKT, MR is the transition matrix with dimensions of K×K, each dimension corresponds to the data for the two adjacent points, and Mk,m is defined as follows:


## 5.3. Virtual Node Embedding

The VNE-NRTD algorithm proposed in this paper embeds the virtual nodes through greedy way. The detailed procedure is illustrated in Algorithm1 (VNE-NRTD-S) and Algorithm 2 (VNE-NRTD-G).Algorithm 1: VNE-NRTD-S.
(1)
Calculate the node-ranking valueSk of virtual nodes according to equation (35)(2)
for all unembedded virtual nodes in VNR(3)
Select the virtual nodenk with the highest node-ranking value Sk(4)
Rank the virtual nodes using breadth first search (BFS) algorithm and put the ranking results into Virtual_node_list1(5)
end for(6)
for each unembedded virtual node in Virtual_node_list1(7)
Filter the set of substrate nodes that meet the resource and location constraints ofnk(8)
Calculate the node-ranking valueSk of substrate nodes according to equation (35)(9)
Rank the substrate nodes bySk in decreasing order(10)
Embed the virtual node onto the substrate node with the highestSk(11)
end forAlgorithm 2: VNE-NRTD-G.
(1)
Calculate the node-ranking valueRk of virtual nodes according to equation (37)(2)
for all unembedded virtual nodes in VNR(3)
Select the virtual nodenk with the highest node-ranking value Rk(4)
Rank the virtual nodes using BFS algorithm and put the ranking results into Virtual_node_list2(5)
end for(6)
for each unembedded virtual node in Virtual_node_list2(7)
Filter the set of substrate nodes that meet the resource and location constraints of virtual node(8)
Calculate the node-ranking valueRk of substrate nodes according to equation (37)(9)
Rank the substrate nodes byRk in decreasing order(10)
Embed the virtual node onto the substrate node with the highestRk(11)
end for


## 5.4. Virtual Link Embedding

If there is a node embedding failure in the VNR, the link embedding is not performed. Otherwise, theshortest path algorithm is used to search the shortest path between the nodes. The detailed steps of virtual link embedding algorithm are shown in Algorithm 3.Algorithm 3: The link embedding algorithm based on the shortest path algorithm.
(1)
Rank the virtual links by the required bandwidth in decreasing order(2)
for all unembedded virtual links in VNR(3)
Fetch two corresponding substrate nodes for the virtual link(4)
Remove the substrate links whose bandwidth is less than the required amount of bandwidth(5)
Choose a loop-free substrate path between the corresponding nodes usingshortest path algorithm(6)
Embed the virtual link onto the choose substrate path(7)
end for


## 5.5. Time Complexity of VNE-NRTD

For all virtual nodes in the VNR, the time complexities corresponding to calculating theSk and Rk of the candidate substrate node are ONvNs2 and ONvNs2+NvNs2log1/δ [40], respectively. The time complexity of link embedding is OLvNs2. Therefore, the time complexity of VNE-NRTD-S is ONvNs2+LvNs2, and the time complexity of VNE-NRTD-G is ONvNs2+NvNs2log1/δ+Lv|Ns2.Overall, compared with other algorithms, the proposed algorithm, either VNE-NRTD-G or VNE-NRTD-S, runs in polynomial time and can be simulated in a continuous time event.


## 6. Performance Evaluation

In this section, we present the settings of our simulation environment in detail, and then, the performance of our algorithms is compared with three algorithms in the first simulation experiment. Next, the performance of the compared algorithms as a function of different VNR arrival rates is simulated in the second experiment. Finally, we simulate the impact of different VNR duration times on the compared algorithms. Simulation results verify the performance of the VNE-NRTD algorithm.


### 6.1. Simulation Environment Settings

Similar to the prior work [36], the topologies of the substrate network and virtual networks are generated by the modified Salam network topology random generation algorithm.Table2 summarizes the shared SN environments for our simulation. Table 3 summarizes the VN environments for our simulation.Table 2
SN environments.
Network generation approachModified Salam algorithmNumber of substrate nodes100Number of substrate links500Connectivity rate of node0.5Computing capability of node[50, 100], uniform distributedFlow rule capacity of node[50, 100], uniform distributedLink bandwidth[50, 100], uniform distributedLocation of substrate node[0, 1000], uniform distributedTable 3
VNR environments.
Network generation approachModified Salam algorithmVNR arrival rate5 VNRs per 100 time unitesVNR duration timeMean value is 1000 time unitesNumber of VNR nodes[2, 10], uniform distributedNode computing capability demand[10, 30], uniform distributedNode flow rule capacity demand[10, 30], uniform distributedLink bandwidth demand[10, 30], uniform distributedVirtual node location constraintDni=500In this paper, our simulation experiments evaluate the performance of five algorithms, which are listed in Table4. The simulation is performed in the same SN and VNRs environment.Table 4
Compared algorithms.
AlgorithmDescriptionVNE-NRTD-GVirtual node embedding based on global bandwidth metricVNE-NRTD-SVirtual node embedding using node multiple metrics based on the modified SPA methodVNE-MC [36]Virtual node embedding based on resource and topology attributes metricsVNE-NRM [37]Virtual node embedding based on resource importance metricVNE-RCR [37]Virtual node embedding based on resource balance metricAll simulations for different VNE algorithms run on a Windows 7 operating system. The hardware platform is composed of an Intel Core i7-7700 3.6 GHz processor and 8 GB of RAM. The analysis software is MATLAB R2017a. In order to reduce the influence of random parameters on the experimental results, we run our simulations for 50,000 time units so that the performance is in a stable state.


### 6.2. Simulation Results

In this section, we analyze the performance of the proposed algorithm in terms of the VNR acceptance ratio, long-term average R/C ratio, substrate node utilization, and substrate link utilization. The simulation results highlight the superior performance of the VNE-NRTD algorithm.


#### 6.2.1. Simulation Experiment 1

The first experiment aims to evaluate the performance of the VNE-NRTD algorithm compared with the other three state-of-the-art algorithms.Figure3 presents the average VNR acceptance ratio as a function of continuous time. Observed from Figure 3, the acceptance ratios of all algorithms are almost equal to 1 at the beginning because there are sufficient SN resources for embedding VNRs. However, as time goes on, the acceptance ratios of all algorithms have begun to decay because there are no infinite resources to embed increasing arrived VNRs. After a while, the acceptance of all algorithms gradually stabilizes because of the arrival and departure of VNRs maintaining a state of dynamic balance. Moreover, the VNE-NRTD-G algorithm outperforms the compared heuristic algorithms. The acceptance ratio of the VNE-NRTD-G algorithm improves 3.4%, 5.9%, 8.2%, and 12.9%, respectively, compared with the algorithms VNE-NRTD-S, VNE-MC, VNE-NRM, and VNE-RCR.Figure 3
VNR acceptance ratio.The acceptance ratio of the VNE-RCR algorithm is approximately 0.68. It only considers the resource balance of the nodes, when the node is ranked during the node embedding stage, without considering the resource attributes of the nodes. The VNE-NRM algorithm takes resource attributes into consideration and embeds virtual nodes onto substrate nodes with sufficient resources to improve the acceptance ratio of VNRs. The VNE-MC algorithm uses the BFS algorithm when ranking virtual nodes. The virtual node closest to the embedded node in location and requiring more resources is preferentially embedded to improve the topology association of the substrate nodes. In this way, the link bandwidth cost is reduced, thus improving the acceptance ratio of VNRs.These three algorithms perform node embedding only combining the nodes’ resource attributes and local topology attributes by simple arithmetic operations, while without fully considering the weight of different node metrics in different network environments. As a result, the performance of these algorithms is limited. The VNE-NRTD algorithm proposed in this paper runs as expected because it takes different node metrics to quantify the substrate nodes and virtual nodes, respectively. It also takes the modified SPA method to avoid metric weight imbalance. The iterative operation of global bandwidth further enhances the reliability of node ranking and improves the resource utilization of SN. Compared with the selected heuristic algorithms, the VNE-NRTD performs best.Figure4 depicts the long-term average R/C ratio as a function of continuous time. From Figure 4, we can observe that the long-term average R/C ratio of all compared algorithms gradually to be steady with the time goes on. The VNE-RCR and VNE-NRM algorithms have the lowest long-term average R/C ratio. The reason is that the virtual nodes are far away after embedding onto the substrate network. Thus, it leads to large amount of unnecessary bandwidth resources consumption. The VNE-MC algorithm considers the topology characteristics of nodes when ranking node to enhance the topology relevance; hence, more substrate link bandwidth resources are saved and the cost of virtual link embedding is reduced. It can be seen from the simulation that the VNE-NRTD algorithm improves the utilization efficiency of substrate network resources and has the highest long-term average R/C ratio, particularly to the VNE-NRTD-G algorithm.Figure 4
Long-term average R/C ratio.Figures5 and 6 illustrate the average node and link utilization of all compared algorithms as a function of continuous time, respectively. From Figures 5 and 6, we can observe that the node and link utilization of all compared algorithms gradually increase with the time. Meanwhile, the VNE-NRTD algorithm has obvious advantages over the compared heuristic algorithms. The reason for the VNE-NRTD algorithm having greater node utilization than other heuristic algorithms is that it can accept more VNRs, and the results in Figure 3 also confirm this inference. However, the link utilization shown in Figure 6 does not have the same result for all algorithms as the previous simulation. The reason for the lower link utilization of the VNE-NRTD algorithm is that it considers the global bandwidth resources when ranking the nodes so that the nodes are closer after embedding, thus avoiding overconsumption of substrate link bandwidth resources. We can also see that the main factor affecting the acceptance ratio of virtual network embedding is that the node resources are finite although the substrate link resources are still sufficient.Figure 5
Average node utilization.Figure 6
Average link utilization.


#### 6.2.2. Simulation Experiment 2

The second experiment aims to measure the performance of the five compared algorithms as a function of the VNR arrival rate. We compare and analyze the performance of the five algorithms with VNR arrival rate distribution between 1/30 and 1/10.Figure7 demonstrates the average VNR acceptance ratio of the five compared algorithms as a function of the VNR arrival rate. From Figure 7, we can observe that the acceptance ratios of all algorithms are decaying with the increasing arrival rate of VNRs. The reason is that the available SN resources are diminishing with the increasing VNRs, which lead to less remaining SN resources that can be used for VN embedding. Moreover, the simulation results in Figure 7 also show that the VNE-NRTD algorithm outperforms the other heuristic algorithms, particularly to the VNE-NRTD-G algorithm, in all simulated VNR arrival rates.Figure 7
VNR acceptance ratio.Figure8 shows the long-term average R/C ratio as a function of the VNR arrival rate. From Figure 8, we can observe that the long-term average R/C ratio performance of each algorithm is similar under different VNR arrival rates. The reason is that limited SN resources can only embed a certain number of VNRs. After the VNR is embedded successfully, it will also pay a certain cost while generating revenue. The ratio of revenues to costs will also be stable and balanced. The reason for the VNE-NRTD algorithm having a larger R/C ratio than other algorithms is that the nodes are closer after embedding, which reduce the unnecessary bandwidth consumption of substrate links.Figure 8
Long-term average R/C ratio.Figures9 and 10 illustrate the average node and link utilization of all compared algorithms as a function of the VNR arrival rate, respectively. From Figures 9 and 10, we can observe that, with the increase in the virtual network arrival rate, the utilization of the node and link resources of the substrate network has also improved. This is because the greedy strategy used for node and link embedding in the early stage led to resource fragmentation, thus resulted in the inability to fully utilize the remaining resources for virtual network embedding. However, as the arrival rate of VNRs increases, more VNs with fewer resource requirements can be embedded. Therefore, the fragmented SN resources can be fully used for these VNRs for embedding, thereby improving the utilization of substrate network nodes and links resources utilization.Figure 9
Average node utilization.Figure 10
Average link utilization.


#### 6.2.3. Simulation Experiment 3

In order to measure the performance of the five compared algorithms as a function of VNR duration time, we carried out the third experiment and let the duration time of the VNR uniformly distributes between 500 and 2000. Likewise, we evaluate our algorithms compared with the other three algorithms in terms of the average acceptance ratio, the long-term average R/C ratio, and the node and link utilization.Figure11 shows the average VNR acceptance ratio as a function of VNR duration time. From Figure 11, we can observe that, as the duration time of VNR increases, the request acceptance ratio of all algorithms gradually decreases. This is because as the duration time of each virtual network request increases, each successfully embedded VNR will occupy SN resources for a long period of time, resulting in insufficient SN resources to embedding more VNRs. The number of VNRs does not change, while the number of successfully embedded VNRs decreases, leading to a lower VNR acceptance ratio. In addition, the VNE-NRTD algorithm can maintain outstanding performance under different VNR durations, especially the VNE-NRTD-G algorithm.Figure 11
VNR acceptance ratio.Figure12 shows the long-term average R/C ratio as a function of VNR duration time. From Figure 12, we can get the same conclusion as in Figure 8. From equation (11), we can observe that the long-term average R/C ratio is also a function of time, while the ratio of revenues to costs will be independent of time. The VNE strategy of each algorithm is fixed, so the ratios of revenues to costs are similar in different environments. Likewise, the reason for the VNE-NRTD algorithm having larger R/C ratio than other algorithms is that the nodes are closer after embedding, which reduce the unnecessary bandwidth consumption of substrate links.Figure 12
Long-term average R/C ratio.Figures13 and 14 illustrate the average node and link utilization of all compared algorithms as a function of VNR duration time, respectively. From Figures 13 and 14, we can observe that, as the duration time of the VNR increases, the node and link resource utilization of the SN increases. The reason is that the VNR with fewer resource requirements is easy to embed, and it will occupy the fragmented resources for a long time, while other VNRs could not use these fragmented resources. Therefore, the node and link resource utilization of the SN is higher when the virtual network request has a long duration time.Figure 13
Average node utilization.Figure 14
Average link utilization.


## 6.1. Simulation Environment Settings

Similar to the prior work [36], the topologies of the substrate network and virtual networks are generated by the modified Salam network topology random generation algorithm.Table2 summarizes the shared SN environments for our simulation. Table 3 summarizes the VN environments for our simulation.Table 2
SN environments.
Network generation approachModified Salam algorithmNumber of substrate nodes100Number of substrate links500Connectivity rate of node0.5Computing capability of node[50, 100], uniform distributedFlow rule capacity of node[50, 100], uniform distributedLink bandwidth[50, 100], uniform distributedLocation of substrate node[0, 1000], uniform distributedTable 3
VNR environments.
Network generation approachModified Salam algorithmVNR arrival rate5 VNRs per 100 time unitesVNR duration timeMean value is 1000 time unitesNumber of VNR nodes[2, 10], uniform distributedNode computing capability demand[10, 30], uniform distributedNode flow rule capacity demand[10, 30], uniform distributedLink bandwidth demand[10, 30], uniform distributedVirtual node location constraintDni=500In this paper, our simulation experiments evaluate the performance of five algorithms, which are listed in Table4. The simulation is performed in the same SN and VNRs environment.Table 4
Compared algorithms.
AlgorithmDescriptionVNE-NRTD-GVirtual node embedding based on global bandwidth metricVNE-NRTD-SVirtual node embedding using node multiple metrics based on the modified SPA methodVNE-MC [36]Virtual node embedding based on resource and topology attributes metricsVNE-NRM [37]Virtual node embedding based on resource importance metricVNE-RCR [37]Virtual node embedding based on resource balance metricAll simulations for different VNE algorithms run on a Windows 7 operating system. The hardware platform is composed of an Intel Core i7-7700 3.6 GHz processor and 8 GB of RAM. The analysis software is MATLAB R2017a. In order to reduce the influence of random parameters on the experimental results, we run our simulations for 50,000 time units so that the performance is in a stable state.


## 6.2. Simulation Results

In this section, we analyze the performance of the proposed algorithm in terms of the VNR acceptance ratio, long-term average R/C ratio, substrate node utilization, and substrate link utilization. The simulation results highlight the superior performance of the VNE-NRTD algorithm.


### 6.2.1. Simulation Experiment 1

The first experiment aims to evaluate the performance of the VNE-NRTD algorithm compared with the other three state-of-the-art algorithms.Figure3 presents the average VNR acceptance ratio as a function of continuous time. Observed from Figure 3, the acceptance ratios of all algorithms are almost equal to 1 at the beginning because there are sufficient SN resources for embedding VNRs. However, as time goes on, the acceptance ratios of all algorithms have begun to decay because there are no infinite resources to embed increasing arrived VNRs. After a while, the acceptance of all algorithms gradually stabilizes because of the arrival and departure of VNRs maintaining a state of dynamic balance. Moreover, the VNE-NRTD-G algorithm outperforms the compared heuristic algorithms. The acceptance ratio of the VNE-NRTD-G algorithm improves 3.4%, 5.9%, 8.2%, and 12.9%, respectively, compared with the algorithms VNE-NRTD-S, VNE-MC, VNE-NRM, and VNE-RCR.Figure 3
VNR acceptance ratio.The acceptance ratio of the VNE-RCR algorithm is approximately 0.68. It only considers the resource balance of the nodes, when the node is ranked during the node embedding stage, without considering the resource attributes of the nodes. The VNE-NRM algorithm takes resource attributes into consideration and embeds virtual nodes onto substrate nodes with sufficient resources to improve the acceptance ratio of VNRs. The VNE-MC algorithm uses the BFS algorithm when ranking virtual nodes. The virtual node closest to the embedded node in location and requiring more resources is preferentially embedded to improve the topology association of the substrate nodes. In this way, the link bandwidth cost is reduced, thus improving the acceptance ratio of VNRs.These three algorithms perform node embedding only combining the nodes’ resource attributes and local topology attributes by simple arithmetic operations, while without fully considering the weight of different node metrics in different network environments. As a result, the performance of these algorithms is limited. The VNE-NRTD algorithm proposed in this paper runs as expected because it takes different node metrics to quantify the substrate nodes and virtual nodes, respectively. It also takes the modified SPA method to avoid metric weight imbalance. The iterative operation of global bandwidth further enhances the reliability of node ranking and improves the resource utilization of SN. Compared with the selected heuristic algorithms, the VNE-NRTD performs best.Figure4 depicts the long-term average R/C ratio as a function of continuous time. From Figure 4, we can observe that the long-term average R/C ratio of all compared algorithms gradually to be steady with the time goes on. The VNE-RCR and VNE-NRM algorithms have the lowest long-term average R/C ratio. The reason is that the virtual nodes are far away after embedding onto the substrate network. Thus, it leads to large amount of unnecessary bandwidth resources consumption. The VNE-MC algorithm considers the topology characteristics of nodes when ranking node to enhance the topology relevance; hence, more substrate link bandwidth resources are saved and the cost of virtual link embedding is reduced. It can be seen from the simulation that the VNE-NRTD algorithm improves the utilization efficiency of substrate network resources and has the highest long-term average R/C ratio, particularly to the VNE-NRTD-G algorithm.Figure 4
Long-term average R/C ratio.Figures5 and 6 illustrate the average node and link utilization of all compared algorithms as a function of continuous time, respectively. From Figures 5 and 6, we can observe that the node and link utilization of all compared algorithms gradually increase with the time. Meanwhile, the VNE-NRTD algorithm has obvious advantages over the compared heuristic algorithms. The reason for the VNE-NRTD algorithm having greater node utilization than other heuristic algorithms is that it can accept more VNRs, and the results in Figure 3 also confirm this inference. However, the link utilization shown in Figure 6 does not have the same result for all algorithms as the previous simulation. The reason for the lower link utilization of the VNE-NRTD algorithm is that it considers the global bandwidth resources when ranking the nodes so that the nodes are closer after embedding, thus avoiding overconsumption of substrate link bandwidth resources. We can also see that the main factor affecting the acceptance ratio of virtual network embedding is that the node resources are finite although the substrate link resources are still sufficient.Figure 5
Average node utilization.Figure 6
Average link utilization.


### 6.2.2. Simulation Experiment 2

The second experiment aims to measure the performance of the five compared algorithms as a function of the VNR arrival rate. We compare and analyze the performance of the five algorithms with VNR arrival rate distribution between 1/30 and 1/10.Figure7 demonstrates the average VNR acceptance ratio of the five compared algorithms as a function of the VNR arrival rate. From Figure 7, we can observe that the acceptance ratios of all algorithms are decaying with the increasing arrival rate of VNRs. The reason is that the available SN resources are diminishing with the increasing VNRs, which lead to less remaining SN resources that can be used for VN embedding. Moreover, the simulation results in Figure 7 also show that the VNE-NRTD algorithm outperforms the other heuristic algorithms, particularly to the VNE-NRTD-G algorithm, in all simulated VNR arrival rates.Figure 7
VNR acceptance ratio.Figure8 shows the long-term average R/C ratio as a function of the VNR arrival rate. From Figure 8, we can observe that the long-term average R/C ratio performance of each algorithm is similar under different VNR arrival rates. The reason is that limited SN resources can only embed a certain number of VNRs. After the VNR is embedded successfully, it will also pay a certain cost while generating revenue. The ratio of revenues to costs will also be stable and balanced. The reason for the VNE-NRTD algorithm having a larger R/C ratio than other algorithms is that the nodes are closer after embedding, which reduce the unnecessary bandwidth consumption of substrate links.Figure 8
Long-term average R/C ratio.Figures9 and 10 illustrate the average node and link utilization of all compared algorithms as a function of the VNR arrival rate, respectively. From Figures 9 and 10, we can observe that, with the increase in the virtual network arrival rate, the utilization of the node and link resources of the substrate network has also improved. This is because the greedy strategy used for node and link embedding in the early stage led to resource fragmentation, thus resulted in the inability to fully utilize the remaining resources for virtual network embedding. However, as the arrival rate of VNRs increases, more VNs with fewer resource requirements can be embedded. Therefore, the fragmented SN resources can be fully used for these VNRs for embedding, thereby improving the utilization of substrate network nodes and links resources utilization.Figure 9
Average node utilization.Figure 10
Average link utilization.


### 6.2.3. Simulation Experiment 3

In order to measure the performance of the five compared algorithms as a function of VNR duration time, we carried out the third experiment and let the duration time of the VNR uniformly distributes between 500 and 2000. Likewise, we evaluate our algorithms compared with the other three algorithms in terms of the average acceptance ratio, the long-term average R/C ratio, and the node and link utilization.Figure11 shows the average VNR acceptance ratio as a function of VNR duration time. From Figure 11, we can observe that, as the duration time of VNR increases, the request acceptance ratio of all algorithms gradually decreases. This is because as the duration time of each virtual network request increases, each successfully embedded VNR will occupy SN resources for a long period of time, resulting in insufficient SN resources to embedding more VNRs. The number of VNRs does not change, while the number of successfully embedded VNRs decreases, leading to a lower VNR acceptance ratio. In addition, the VNE-NRTD algorithm can maintain outstanding performance under different VNR durations, especially the VNE-NRTD-G algorithm.Figure 11
VNR acceptance ratio.Figure12 shows the long-term average R/C ratio as a function of VNR duration time. From Figure 12, we can get the same conclusion as in Figure 8. From equation (11), we can observe that the long-term average R/C ratio is also a function of time, while the ratio of revenues to costs will be independent of time. The VNE strategy of each algorithm is fixed, so the ratios of revenues to costs are similar in different environments. Likewise, the reason for the VNE-NRTD algorithm having larger R/C ratio than other algorithms is that the nodes are closer after embedding, which reduce the unnecessary bandwidth consumption of substrate links.Figure 12
Long-term average R/C ratio.Figures13 and 14 illustrate the average node and link utilization of all compared algorithms as a function of VNR duration time, respectively. From Figures 13 and 14, we can observe that, as the duration time of the VNR increases, the node and link resource utilization of the SN increases. The reason is that the VNR with fewer resource requirements is easy to embed, and it will occupy the fragmented resources for a long time, while other VNRs could not use these fragmented resources. Therefore, the node and link resource utilization of the SN is higher when the virtual network request has a long duration time.Figure 13
Average node utilization.Figure 14
Average link utilization.


## 6.2.1. Simulation Experiment 1

The first experiment aims to evaluate the performance of the VNE-NRTD algorithm compared with the other three state-of-the-art algorithms.Figure3 presents the average VNR acceptance ratio as a function of continuous time. Observed from Figure 3, the acceptance ratios of all algorithms are almost equal to 1 at the beginning because there are sufficient SN resources for embedding VNRs. However, as time goes on, the acceptance ratios of all algorithms have begun to decay because there are no infinite resources to embed increasing arrived VNRs. After a while, the acceptance of all algorithms gradually stabilizes because of the arrival and departure of VNRs maintaining a state of dynamic balance. Moreover, the VNE-NRTD-G algorithm outperforms the compared heuristic algorithms. The acceptance ratio of the VNE-NRTD-G algorithm improves 3.4%, 5.9%, 8.2%, and 12.9%, respectively, compared with the algorithms VNE-NRTD-S, VNE-MC, VNE-NRM, and VNE-RCR.Figure 3
VNR acceptance ratio.The acceptance ratio of the VNE-RCR algorithm is approximately 0.68. It only considers the resource balance of the nodes, when the node is ranked during the node embedding stage, without considering the resource attributes of the nodes. The VNE-NRM algorithm takes resource attributes into consideration and embeds virtual nodes onto substrate nodes with sufficient resources to improve the acceptance ratio of VNRs. The VNE-MC algorithm uses the BFS algorithm when ranking virtual nodes. The virtual node closest to the embedded node in location and requiring more resources is preferentially embedded to improve the topology association of the substrate nodes. In this way, the link bandwidth cost is reduced, thus improving the acceptance ratio of VNRs.These three algorithms perform node embedding only combining the nodes’ resource attributes and local topology attributes by simple arithmetic operations, while without fully considering the weight of different node metrics in different network environments. As a result, the performance of these algorithms is limited. The VNE-NRTD algorithm proposed in this paper runs as expected because it takes different node metrics to quantify the substrate nodes and virtual nodes, respectively. It also takes the modified SPA method to avoid metric weight imbalance. The iterative operation of global bandwidth further enhances the reliability of node ranking and improves the resource utilization of SN. Compared with the selected heuristic algorithms, the VNE-NRTD performs best.Figure4 depicts the long-term average R/C ratio as a function of continuous time. From Figure 4, we can observe that the long-term average R/C ratio of all compared algorithms gradually to be steady with the time goes on. The VNE-RCR and VNE-NRM algorithms have the lowest long-term average R/C ratio. The reason is that the virtual nodes are far away after embedding onto the substrate network. Thus, it leads to large amount of unnecessary bandwidth resources consumption. The VNE-MC algorithm considers the topology characteristics of nodes when ranking node to enhance the topology relevance; hence, more substrate link bandwidth resources are saved and the cost of virtual link embedding is reduced. It can be seen from the simulation that the VNE-NRTD algorithm improves the utilization efficiency of substrate network resources and has the highest long-term average R/C ratio, particularly to the VNE-NRTD-G algorithm.Figure 4
Long-term average R/C ratio.Figures5 and 6 illustrate the average node and link utilization of all compared algorithms as a function of continuous time, respectively. From Figures 5 and 6, we can observe that the node and link utilization of all compared algorithms gradually increase with the time. Meanwhile, the VNE-NRTD algorithm has obvious advantages over the compared heuristic algorithms. The reason for the VNE-NRTD algorithm having greater node utilization than other heuristic algorithms is that it can accept more VNRs, and the results in Figure 3 also confirm this inference. However, the link utilization shown in Figure 6 does not have the same result for all algorithms as the previous simulation. The reason for the lower link utilization of the VNE-NRTD algorithm is that it considers the global bandwidth resources when ranking the nodes so that the nodes are closer after embedding, thus avoiding overconsumption of substrate link bandwidth resources. We can also see that the main factor affecting the acceptance ratio of virtual network embedding is that the node resources are finite although the substrate link resources are still sufficient.Figure 5
Average node utilization.Figure 6
Average link utilization.


## 6.2.2. Simulation Experiment 2

The second experiment aims to measure the performance of the five compared algorithms as a function of the VNR arrival rate. We compare and analyze the performance of the five algorithms with VNR arrival rate distribution between 1/30 and 1/10.Figure7 demonstrates the average VNR acceptance ratio of the five compared algorithms as a function of the VNR arrival rate. From Figure 7, we can observe that the acceptance ratios of all algorithms are decaying with the increasing arrival rate of VNRs. The reason is that the available SN resources are diminishing with the increasing VNRs, which lead to less remaining SN resources that can be used for VN embedding. Moreover, the simulation results in Figure 7 also show that the VNE-NRTD algorithm outperforms the other heuristic algorithms, particularly to the VNE-NRTD-G algorithm, in all simulated VNR arrival rates.Figure 7
VNR acceptance ratio.Figure8 shows the long-term average R/C ratio as a function of the VNR arrival rate. From Figure 8, we can observe that the long-term average R/C ratio performance of each algorithm is similar under different VNR arrival rates. The reason is that limited SN resources can only embed a certain number of VNRs. After the VNR is embedded successfully, it will also pay a certain cost while generating revenue. The ratio of revenues to costs will also be stable and balanced. The reason for the VNE-NRTD algorithm having a larger R/C ratio than other algorithms is that the nodes are closer after embedding, which reduce the unnecessary bandwidth consumption of substrate links.Figure 8
Long-term average R/C ratio.Figures9 and 10 illustrate the average node and link utilization of all compared algorithms as a function of the VNR arrival rate, respectively. From Figures 9 and 10, we can observe that, with the increase in the virtual network arrival rate, the utilization of the node and link resources of the substrate network has also improved. This is because the greedy strategy used for node and link embedding in the early stage led to resource fragmentation, thus resulted in the inability to fully utilize the remaining resources for virtual network embedding. However, as the arrival rate of VNRs increases, more VNs with fewer resource requirements can be embedded. Therefore, the fragmented SN resources can be fully used for these VNRs for embedding, thereby improving the utilization of substrate network nodes and links resources utilization.Figure 9
Average node utilization.Figure 10
Average link utilization.


## 6.2.3. Simulation Experiment 3

In order to measure the performance of the five compared algorithms as a function of VNR duration time, we carried out the third experiment and let the duration time of the VNR uniformly distributes between 500 and 2000. Likewise, we evaluate our algorithms compared with the other three algorithms in terms of the average acceptance ratio, the long-term average R/C ratio, and the node and link utilization.Figure11 shows the average VNR acceptance ratio as a function of VNR duration time. From Figure 11, we can observe that, as the duration time of VNR increases, the request acceptance ratio of all algorithms gradually decreases. This is because as the duration time of each virtual network request increases, each successfully embedded VNR will occupy SN resources for a long period of time, resulting in insufficient SN resources to embedding more VNRs. The number of VNRs does not change, while the number of successfully embedded VNRs decreases, leading to a lower VNR acceptance ratio. In addition, the VNE-NRTD algorithm can maintain outstanding performance under different VNR durations, especially the VNE-NRTD-G algorithm.Figure 11
VNR acceptance ratio.Figure12 shows the long-term average R/C ratio as a function of VNR duration time. From Figure 12, we can get the same conclusion as in Figure 8. From equation (11), we can observe that the long-term average R/C ratio is also a function of time, while the ratio of revenues to costs will be independent of time. The VNE strategy of each algorithm is fixed, so the ratios of revenues to costs are similar in different environments. Likewise, the reason for the VNE-NRTD algorithm having larger R/C ratio than other algorithms is that the nodes are closer after embedding, which reduce the unnecessary bandwidth consumption of substrate links.Figure 12
Long-term average R/C ratio.Figures13 and 14 illustrate the average node and link utilization of all compared algorithms as a function of VNR duration time, respectively. From Figures 13 and 14, we can observe that, as the duration time of the VNR increases, the node and link resource utilization of the SN increases. The reason is that the VNR with fewer resource requirements is easy to embed, and it will occupy the fragmented resources for a long time, while other VNRs could not use these fragmented resources. Therefore, the node and link resource utilization of the SN is higher when the virtual network request has a long duration time.Figure 13
Average node utilization.Figure 14
Average link utilization.


## 7. Conclusion

Virtual network embedding is a key technique to overcome the ossification of the current Internet. To extend the VNE problem to a more realistic approach, we study the virtual network embedding model based on SDN. Then, we proposed a novel node-ranking approach based on topology-differentiating for SDN-based virtual network embedding, labeled as VNE-NRTD, in this paper. According to the topological difference between SN and VN, we used different node metrics to quantify the substrate nodes and virtual nodes, respectively. The importance of nodes is calculated based on the modified SPA method. On this basis, the global bandwidth of the network topology is introduced into the node-ranking process to further improve the efficiency of node embedding. Three kinds of simulation results validate that VNE-NRTD algorithm outperforms the other three typical and latest heuristic algorithms in terms of the VNR acceptance ratio, long-term average R/C ratio, substrate node utilization, and substrate link utilization.With the continuous development of the future network application, more network parameters need to be considered. The algorithm proposed in this paper can add new parameter indicators flexibly and conveniently, which has better scalability. The proposed algorithm also can be extended to support NFV and other new network scenarios.In the future work, we will consider more service scenarios to study more challenging virtual network embedding problems, such as node migration and failure recovery, to support multiple services.



---

*Source: 5452397-2020-10-17.xml*