# HS-MOEA/D: An Oriented Algorithm for Delay and Reliability VNF-SC Deployment

Authors: Hejun Xuan; Lei You; Zhenghui Liu; Yanling Li; Xiaokai Yang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Network function virtualization (NFV) technology can realize on-demand distribution of network resources and improve network flexibility. It has become one of the key technologies for next-generation communications. Virtual network function service chain (VNF-SC) deployment is an important problem faced by network function virtualization technology. In this paper, the problem, VNF deployment for VNF-SC, is investigated. First, a two-objective mathematical model, which maximizes balancing and reliability of SFC, is established. In this model, VNFs are divided into two classes, i.e., part of required VNFs in each VNF-SC is dependent, others are independent. Second, harmony search-based MOEA/D (HS-MOEA/D) is proposed to solve the model effectively. In HS-MOEA/D, Chebyshev decomposition mechanism is used to transform multiobjective optimization problem into a series of single-objective optimization subproblems. A new evolutionary strategy is deeply studied in order to propose a new harmony search (HS) algorithm. Finally, to show high performance of the proposed algorithm, a large number of experiments are conducted. The simulation results show that the proposed algorithm enhances the reliability of SFC and reduces the end-to-end delay.


---

## Body

## 1. Introduction

Network traffic has experienced an explosive growth, and traditional network hardware and software tight coupling has been unable to meet user needs in recent years. Network function virtualization (NFV) technology was born under such network requirements [1–3]. Traditional network functions are tightly coupled with hardware devices, and only large number of network functions can be deployed to meet the growing service needs of users, but this will greatly increase the cost of network construction and operation [4–6]. By decoupling software and hardware, NFV abstracts network functions into software-based virtual network function (VNF). Network functions are no longer dependent on hardware devices, and resources can be flexibly shared, thus reducing construction costs and operating costs [7–9]. Specific VNFs are connected in a specific order to form a service function chain (SFC), through which the business in NFV environment is realized [10–12]. As one of the key technologies of 5G, the research of NFV has attracted the attention of many experts and scholars. Most studies mainly consider minimizing network resource consumption and maximizing network income [13, 14]. Eramo et al. [15] proposed, using feedback mechanism, to deploy VNF and select routing, so as to realize load balancing and improve the request acceptance rate. Allybokus et al. [16] proposed an integer linear programming model to deploy VNF and route selection to minimize energy overhead. Most current studies assume that the NFV infrastructure is absolutely reliable, that is, the ideal state [17, 18]. Any physical fault or software fault will lead to the interruption of SFC, so improving the reliability of SFC is very important for the stability of business. The 5G mobile communication system has high delay requirements for communication services, and the end-to-end delay in low-delay scenarios even needs to reach the millisecond level [19]. Therefore, how to effectively deploy VNF to improve the reliability of SFC and reduce end-to-end delay has become a hot issue.The effective deployment of VNF has proven to be an NP-hard problem. Most of the existing literature improves the reliability of SFC by increasing redundancy. Beyranvand et al. [20] supported the entire SFC, which increases resource costs. Qu et al. [21] proposed a reliability awareness method for joint deployment and route optimization of VNF and adopted a backup sharing method to reduce resource consumption. While adopting the backup mechanism to improve the reliability, the link length of the SFC is increased, and the end-to-end delay of the SFC is increased to a certain extent. Chen et al. [22] did not use a backup mechanism, used PageRank when deploying VNFs, and considered reliability and latency. However, when deploying VNF, the source node and target node are not considered, which increases the delay. There is no backup mechanism in the literature. In order to improve the stability and reliability of the network, a queue-aware SFC mapping algorithm considering the source node and the destination node is proposed. The literature [23] does not limit the type of VNF, and it assumes that each physical node can carry any type of VNF. The literature [24] pointed out that adjacent VNFs in the same SFC can be aggregated, that is, deployed on the same physical node, but no specific aggregation method is provided.In this paper, the problem VNF deployment for VNF-SC in interdata center elastic optical networks (inter-DC EONs) is investigated. A multiobjective mathematical model, which minimizes total time delay and reliability of SFC, is established. In this model, VNFs are divided into two classes, i.e., part of required VNFs in each VNF-SC is dependent and others are independent. Second, harmony search-based MOEA/D (HS-MOEA/D) is proposed to solve the model effectively. In HS-MOEA/D, Chebyshev decomposition mechanism is used to transform multiobjective optimization problem into a series of single-objective optimization subproblems. A new evolutionary strategy is deeply studied in order to propose a new harmony search (HS) algorithm.


## 2. Network Model and Problem Description

### 2.1. Network Model

(1)
Physical network: the physical network is represented as an undirected graphGs=Ns,Ls, where Ns represents the set of physical nodes, each of which can carry a specific type of VNF, and Ls represents the set of physical links. For any physical node n∈Ns, Cns, Cn,us, and Cn,as denote the total CPU resources, used CPU resources, and available CPU resources on node n, respectively. Fns, Fn,us, and Fn,as represent the total forwarding resources, occupied forwarding resources, and available forwarding resources, respectively. hn,m represents the number of hops between physical nodes m and n. rn denotes the reliability of the node n. For any physical links ln,ms, its bandwidth resource is Bn,ms.(2)
SFC request: SFC requests are represented as directed graphsGVg=Sg,Dg,NVg,LVg,Tg, where Sg and Dg are the source node and destination node of gth SFC, respectively. For any one of them, SFCg, the physical node for deployment Sg and Dg is determined. NVg=fii=1,2,…,NVg represents the set of all the VNFs. For any fi∈NVg, Cg,iV and Fg,iV represent its CPU resource demand and forwarding resource demand, respectively. LVg and Nlg represent the routing set and the number of routes of SFCg, respectively. The routing and bandwidth request between fi and fj are denoted as li,jg and Bi,jg. Assuming that all routes in any one route have the same bandwidth requirements bg in any SFCg, Tg denotes the life time of SFCg.S=SFCgg=1,2,…,Q denotes the set of SFCs if the ith VNF in SFCg is deployed on kth node, αk,ig=1; otherwise, αk,ig=0. We use An.mi,j=1 represents that virtual link li,jg is mapping on the physical link ln,mS. If not, we have An.mi,j=0. For each SFCg, the nodes’ set of deployed on denoted as Ng=ng,ii=1,2,…,k,ng,i⊂Ns. The reliability of SFCg is Rg=∏i=1krng,i, where rng,i denotes the reliability of ng,i. The node set of physical link is denoted as Npg=ng,pp=1,2,…,K. In this paper, we assume that a node cannot realize all the VNFs. Wg=wii=1,2,…,T represents the VNFs of SFCg requested. If node n can realize the ith VNF, Fnwi=1. Otherwise, Fnwi=0.


### 2.2. Mathematical Modeling

The problem to be solved in this paper is to minimize the time delay and maximize the reliability of SFC through reasonable deployment of VNF. The objective function of delay can be found in previous paper [25], and the objective function of reliability is(1)f2=maxmin1≤g≤QRg.Some constraints should be satisfied:(a)
NF in the SFC can only be deployed to one physical node, that is,(2)∑k∈Nsαk,ig=1.(b)
Each physical node deploys up to two VNFs in the same SFC:(3)∑fi∈Nvgαk,ig≤2.(c)
The physical nodes deployed by VNF meet the functional constraints and the deployment is contiguous in order to reduce the number of link hops. The physical node satisfies the hops constraint while ensuring that the number of hops between it and the destination node will not increase:(4)ifαnj=1,αnj+1=1,fj,fj+1∈NVg,n,m∈Ns,Fnfj,wi=1,Fnfj,wj=1,hn,m<h0,hm,D<hn,D.(d)
Both of the aggregated VNFs meet the functional mutual constraints and the deployed physical nodes meet the aggregated VNF functional constraints. In order to reduce the number of links hops, it is ensured that the deployed neighboring physical nodes meet the hops constraint and the number of hops between them and the destination node will not increase:(5)Pj,j+1g=1,αnj−1=1,αmj=1,αmj+1=1,fj−1,fj,fj+1∈NVg,n,m∈Ns,Fnfj−1,wl=1,Fnfj,wj=1,fj+1,wj=1,hn,m<h1,hm,D<hn,D.(e)
To increase the success rate of polymerization,(6)h1>h0.(f)
The resource requirements of the SFC cannot exceed the resources available to the physical nodes and links on which it is deployed:(7)∑g=1Q∑lj,ug∈LVgAn,mj,u+Am,nj,uBj,ug≤Bn,mS,∑g=1Q∑j∈NVgαmjCg,jV≤CmS,Cm,avaS=CmS×ρ1−Cm,useS,Fm,avaS=FmS×ρ2−Fm,useS,∀m∈NS(g)
VNF deployment, routing, feature mutual exclusion, and binary constraints need to be met for feature hosting:(8)αmj∈0,1,∀m∈NS,fj∈NVg,An,mj,u∈0,1,∀lj,ug∈LVg,ln,m∈LS,Pk,k+1g∈0,1,∀fk,fk+1∈NVg,Fmfk,wi∈0,1,∀m∈NS,VNFwi∈W.


## 2.1. Network Model

(1)
Physical network: the physical network is represented as an undirected graphGs=Ns,Ls, where Ns represents the set of physical nodes, each of which can carry a specific type of VNF, and Ls represents the set of physical links. For any physical node n∈Ns, Cns, Cn,us, and Cn,as denote the total CPU resources, used CPU resources, and available CPU resources on node n, respectively. Fns, Fn,us, and Fn,as represent the total forwarding resources, occupied forwarding resources, and available forwarding resources, respectively. hn,m represents the number of hops between physical nodes m and n. rn denotes the reliability of the node n. For any physical links ln,ms, its bandwidth resource is Bn,ms.(2)
SFC request: SFC requests are represented as directed graphsGVg=Sg,Dg,NVg,LVg,Tg, where Sg and Dg are the source node and destination node of gth SFC, respectively. For any one of them, SFCg, the physical node for deployment Sg and Dg is determined. NVg=fii=1,2,…,NVg represents the set of all the VNFs. For any fi∈NVg, Cg,iV and Fg,iV represent its CPU resource demand and forwarding resource demand, respectively. LVg and Nlg represent the routing set and the number of routes of SFCg, respectively. The routing and bandwidth request between fi and fj are denoted as li,jg and Bi,jg. Assuming that all routes in any one route have the same bandwidth requirements bg in any SFCg, Tg denotes the life time of SFCg.S=SFCgg=1,2,…,Q denotes the set of SFCs if the ith VNF in SFCg is deployed on kth node, αk,ig=1; otherwise, αk,ig=0. We use An.mi,j=1 represents that virtual link li,jg is mapping on the physical link ln,mS. If not, we have An.mi,j=0. For each SFCg, the nodes’ set of deployed on denoted as Ng=ng,ii=1,2,…,k,ng,i⊂Ns. The reliability of SFCg is Rg=∏i=1krng,i, where rng,i denotes the reliability of ng,i. The node set of physical link is denoted as Npg=ng,pp=1,2,…,K. In this paper, we assume that a node cannot realize all the VNFs. Wg=wii=1,2,…,T represents the VNFs of SFCg requested. If node n can realize the ith VNF, Fnwi=1. Otherwise, Fnwi=0.


## 2.2. Mathematical Modeling

The problem to be solved in this paper is to minimize the time delay and maximize the reliability of SFC through reasonable deployment of VNF. The objective function of delay can be found in previous paper [25], and the objective function of reliability is(1)f2=maxmin1≤g≤QRg.Some constraints should be satisfied:(a)
NF in the SFC can only be deployed to one physical node, that is,(2)∑k∈Nsαk,ig=1.(b)
Each physical node deploys up to two VNFs in the same SFC:(3)∑fi∈Nvgαk,ig≤2.(c)
The physical nodes deployed by VNF meet the functional constraints and the deployment is contiguous in order to reduce the number of link hops. The physical node satisfies the hops constraint while ensuring that the number of hops between it and the destination node will not increase:(4)ifαnj=1,αnj+1=1,fj,fj+1∈NVg,n,m∈Ns,Fnfj,wi=1,Fnfj,wj=1,hn,m<h0,hm,D<hn,D.(d)
Both of the aggregated VNFs meet the functional mutual constraints and the deployed physical nodes meet the aggregated VNF functional constraints. In order to reduce the number of links hops, it is ensured that the deployed neighboring physical nodes meet the hops constraint and the number of hops between them and the destination node will not increase:(5)Pj,j+1g=1,αnj−1=1,αmj=1,αmj+1=1,fj−1,fj,fj+1∈NVg,n,m∈Ns,Fnfj−1,wl=1,Fnfj,wj=1,fj+1,wj=1,hn,m<h1,hm,D<hn,D.(e)
To increase the success rate of polymerization,(6)h1>h0.(f)
The resource requirements of the SFC cannot exceed the resources available to the physical nodes and links on which it is deployed:(7)∑g=1Q∑lj,ug∈LVgAn,mj,u+Am,nj,uBj,ug≤Bn,mS,∑g=1Q∑j∈NVgαmjCg,jV≤CmS,Cm,avaS=CmS×ρ1−Cm,useS,Fm,avaS=FmS×ρ2−Fm,useS,∀m∈NS(g)
VNF deployment, routing, feature mutual exclusion, and binary constraints need to be met for feature hosting:(8)αmj∈0,1,∀m∈NS,fj∈NVg,An,mj,u∈0,1,∀lj,ug∈LVg,ln,m∈LS,Pk,k+1g∈0,1,∀fk,fk+1∈NVg,Fmfk,wi∈0,1,∀m∈NS,VNFwi∈W.


## 3. Multiobjective Evolutionary HS-MOEA/D

### 3.1. Harmony Search

Harmony search (HS) algorithm is a new intelligent optimization algorithm. It can be optimized by repeatedly adjusting the solution variables in the memory base to make the function value converge with the increase of iteration times. The algorithm has simple concept and few adjustable parameters and is easy to implement. Similar to the simulation of physical annealing by simulated annealing algorithm, the imitation of biological evolution by genetic algorithm, and the imitation of bird flock by particle swarm optimization algorithm, harmony algorithm simulates the principle of music performance. It has been used to solve many problems [26, 27]:(i)
Determine parameter values: the size of the harmony memory bankHS, the value probability of the harmony memory bank Hmcr, the tonal fine-tuning probability Par, the tonal fine-tuning bandwidth Bw, and the times of creation (iterations) Tmax.(ii)
Initialize the harmony memory libraryHS: generate HS of harmonies randomly from the solution space, denoted as X1,X2,…,XHS. And, record the corresponding fX. The form of harmony library is(9)HM=X1X2⋮XHS=x11⋯xn1fX1x12⋯xn2fX2⋮⋮⋮⋮x1HS⋯xnHSfXHS.(iii)
Generate a new harmony: (1) a random numberr1 is generated between [0, 1]. (2) if r1<Hmcr, take a harmony variable from the harmony memory randomly, otherwise, generate a harmonic variable randomly from the solution space. (3) A harmony variable is obtained from above. If the harmony variable is obtained from the harmony library, the harmony variable needs to be fine tuned. A random number r2 is generated between [0, 1]. (4) If r2<PAR, the obtained harmony variable is adjusted to get a new harmony variable according to the fine-tuning bandwidth BW.(iv)
Update the harmony memory library: calculate the fitnessfXnew of the new harmony Xnew. If fXnew is better than fXworest, Xworest is replaced by Xnew.(v)
Terminate condition: repeat steps (III) and (IV) until the number of authoring (iterations) reachesTmax.


### 3.2. Improved Harmony Search

(1)
Random position update: if the worst and best harmony in the HS algorithm areXworst and Xbest, respectively, and Xworst is regarded as the basis vector, then the better harmony can be adjusted by learning Xbest. This paper proposes a method based on random position updating:(10)Xiworst=Xir+randXd−Xir,Xd=F×Xibest−Xir.IfXir>XiU, Xd=XiU. rand () is a random function, and the migration scale F∈0,2.(2)
Reverse learning: in order to increase the search space of HS algorithm, reverse learning is introduced into HS algorithm, and the reverse learning strategy is shown as follows:(11)Xinew=XiU+XiL−Xir,rand<0.5,Xir,else.(3)
Small probability mutation: small probability mutation operation in HS algorithm is shown as follows:(12)Xinew=XiL+randXiU−XiL.


### 3.3. MOEA/D Algorithm Based on Chebyshev Decomposition

The decomposition-based multiobjective evolutionary algorithm has great advantages in maintaining the distribution of solutions. The distribution of solutions can be optimized by analyzing the information of neighboring problems. The commonly used decomposition methods in MOEA/D include the weighted sum method, the Chebyshev method, and the penalty-based boundary intersection method [28]. Generally speaking, the Chebyshev method is the most widely used method. Using the Chebyshev method to decompose a multiobjective optimization problem into a set of optimization subproblems, mathematically, is described as follows: (13)mingtchxλi,z∗=max1≤i≤mλifix−zi∗,s.t.x∈Ω,where z∗=z1∗,z2∗,…,zm∗T is a reference point and λ=λ1∗,λ2∗,…,λN represents a set of uniformly distributed weight vectors. For zi∗i=1,2,…,m, it has zi∗<minfixx∈Ω.For each Pareto solution, there is always a weight vector to make the solution of (14) to the optimal solution, which corresponds to the multiobjective optimization problem. Chebyshev polymerization method is to add parameter ρ to Chebyshev method, which is to combine the weight sum polymerization method and Chebyshev method. By adjusting the ratio of the two methods, the fast convergence of the weighted summation polymerization method and the good distribution of the Chebyshev method are combined. The mathematical description of Chebyshev polymerization is as follows:(14)mingATxλ,z∗=max1≤i≤mλifix−zi∗+ρ∑i=1mλifix.


### 3.4. HS-MOEA/D Algorithm

This algorithm decomposes a multiobjective optimization problem into a series of single-objective optimization subproblems and optimizes these subproblems at the same time. Then, the HS algorithm is used to replace the genetic algorithm in MOEA/D, which realizes the effective solution of the problem. The pseudocode of HS-MOEA/D is as shown in Algorithm1.Algorithm 1:Pseudocode of HS-MOEA/D.
(1)
Initialize the populationN, and set the weight vectors of evenly distributed as λ=λ1∗,λ2∗,…,λN and the number of weight vectors in each neighborhood is T.(2)
SetEP as the empty set.(3)
Calculate the Euclidean distance of any two weight vectors and find the nearestT weight vectors of each weight vector. For each i=1,2,…,N, let Bi=i1,i2,…,iT. For each j∈Bi, λj is T neighborhood vector of λi.(4)
The initial populationx1,x2,…,xN is generated uniformly and randomly in the feasible space.(5)
For eachi=1,2,…,N, calculating FVi=Fxi.(6)
Initialization the reference pointz∗=z1,z2…,zmT.(7)
Genetic recombination: an individualy is randomly selected from Bi and a new solution is generated using HS.(8)
Improvement: by using the heuristic method to improvey for special problems, the solution y′ is generated.(9)
Function evaluation: evaluation functionFy′.(10)
Updatez: for each j=1,2,…,m, if zj>fjy′, let zj>fjy′.(11)
Update the neighborhood solution: for eachj∈Bi, if gtchy′λ,z≤gtchxjλ,z, let xj=y′,FVj=Fy′.(12)
UpdateEP: remove all vectors dominated by Fy′ from EP.(13)
If none of the vectors inEP dominated by Fy′, add Fy′ to EP.(14)
Terminal condition: if the ending condition is met, the algorithm stops and outputsEP. Otherwise, go to Step 3.


## 3.1. Harmony Search

Harmony search (HS) algorithm is a new intelligent optimization algorithm. It can be optimized by repeatedly adjusting the solution variables in the memory base to make the function value converge with the increase of iteration times. The algorithm has simple concept and few adjustable parameters and is easy to implement. Similar to the simulation of physical annealing by simulated annealing algorithm, the imitation of biological evolution by genetic algorithm, and the imitation of bird flock by particle swarm optimization algorithm, harmony algorithm simulates the principle of music performance. It has been used to solve many problems [26, 27]:(i)
Determine parameter values: the size of the harmony memory bankHS, the value probability of the harmony memory bank Hmcr, the tonal fine-tuning probability Par, the tonal fine-tuning bandwidth Bw, and the times of creation (iterations) Tmax.(ii)
Initialize the harmony memory libraryHS: generate HS of harmonies randomly from the solution space, denoted as X1,X2,…,XHS. And, record the corresponding fX. The form of harmony library is(9)HM=X1X2⋮XHS=x11⋯xn1fX1x12⋯xn2fX2⋮⋮⋮⋮x1HS⋯xnHSfXHS.(iii)
Generate a new harmony: (1) a random numberr1 is generated between [0, 1]. (2) if r1<Hmcr, take a harmony variable from the harmony memory randomly, otherwise, generate a harmonic variable randomly from the solution space. (3) A harmony variable is obtained from above. If the harmony variable is obtained from the harmony library, the harmony variable needs to be fine tuned. A random number r2 is generated between [0, 1]. (4) If r2<PAR, the obtained harmony variable is adjusted to get a new harmony variable according to the fine-tuning bandwidth BW.(iv)
Update the harmony memory library: calculate the fitnessfXnew of the new harmony Xnew. If fXnew is better than fXworest, Xworest is replaced by Xnew.(v)
Terminate condition: repeat steps (III) and (IV) until the number of authoring (iterations) reachesTmax.


## 3.2. Improved Harmony Search

(1)
Random position update: if the worst and best harmony in the HS algorithm areXworst and Xbest, respectively, and Xworst is regarded as the basis vector, then the better harmony can be adjusted by learning Xbest. This paper proposes a method based on random position updating:(10)Xiworst=Xir+randXd−Xir,Xd=F×Xibest−Xir.IfXir>XiU, Xd=XiU. rand () is a random function, and the migration scale F∈0,2.(2)
Reverse learning: in order to increase the search space of HS algorithm, reverse learning is introduced into HS algorithm, and the reverse learning strategy is shown as follows:(11)Xinew=XiU+XiL−Xir,rand<0.5,Xir,else.(3)
Small probability mutation: small probability mutation operation in HS algorithm is shown as follows:(12)Xinew=XiL+randXiU−XiL.


## 3.3. MOEA/D Algorithm Based on Chebyshev Decomposition

The decomposition-based multiobjective evolutionary algorithm has great advantages in maintaining the distribution of solutions. The distribution of solutions can be optimized by analyzing the information of neighboring problems. The commonly used decomposition methods in MOEA/D include the weighted sum method, the Chebyshev method, and the penalty-based boundary intersection method [28]. Generally speaking, the Chebyshev method is the most widely used method. Using the Chebyshev method to decompose a multiobjective optimization problem into a set of optimization subproblems, mathematically, is described as follows: (13)mingtchxλi,z∗=max1≤i≤mλifix−zi∗,s.t.x∈Ω,where z∗=z1∗,z2∗,…,zm∗T is a reference point and λ=λ1∗,λ2∗,…,λN represents a set of uniformly distributed weight vectors. For zi∗i=1,2,…,m, it has zi∗<minfixx∈Ω.For each Pareto solution, there is always a weight vector to make the solution of (14) to the optimal solution, which corresponds to the multiobjective optimization problem. Chebyshev polymerization method is to add parameter ρ to Chebyshev method, which is to combine the weight sum polymerization method and Chebyshev method. By adjusting the ratio of the two methods, the fast convergence of the weighted summation polymerization method and the good distribution of the Chebyshev method are combined. The mathematical description of Chebyshev polymerization is as follows:(14)mingATxλ,z∗=max1≤i≤mλifix−zi∗+ρ∑i=1mλifix.


## 3.4. HS-MOEA/D Algorithm

This algorithm decomposes a multiobjective optimization problem into a series of single-objective optimization subproblems and optimizes these subproblems at the same time. Then, the HS algorithm is used to replace the genetic algorithm in MOEA/D, which realizes the effective solution of the problem. The pseudocode of HS-MOEA/D is as shown in Algorithm1.Algorithm 1:Pseudocode of HS-MOEA/D.
(1)
Initialize the populationN, and set the weight vectors of evenly distributed as λ=λ1∗,λ2∗,…,λN and the number of weight vectors in each neighborhood is T.(2)
SetEP as the empty set.(3)
Calculate the Euclidean distance of any two weight vectors and find the nearestT weight vectors of each weight vector. For each i=1,2,…,N, let Bi=i1,i2,…,iT. For each j∈Bi, λj is T neighborhood vector of λi.(4)
The initial populationx1,x2,…,xN is generated uniformly and randomly in the feasible space.(5)
For eachi=1,2,…,N, calculating FVi=Fxi.(6)
Initialization the reference pointz∗=z1,z2…,zmT.(7)
Genetic recombination: an individualy is randomly selected from Bi and a new solution is generated using HS.(8)
Improvement: by using the heuristic method to improvey for special problems, the solution y′ is generated.(9)
Function evaluation: evaluation functionFy′.(10)
Updatez: for each j=1,2,…,m, if zj>fjy′, let zj>fjy′.(11)
Update the neighborhood solution: for eachj∈Bi, if gtchy′λ,z≤gtchxjλ,z, let xj=y′,FVj=Fy′.(12)
UpdateEP: remove all vectors dominated by Fy′ from EP.(13)
If none of the vectors inEP dominated by Fy′, add Fy′ to EP.(14)
Terminal condition: if the ending condition is met, the algorithm stops and outputsEP. Otherwise, go to Step 3.


## 4. Experiments and Analysis

In order to verify the effectiveness and efficiency of the algorithm, experiments were carried out on two widely used networks. In Section4.1, the parameters used in the algorithm will be given. The experimental results are obtained in Section 4.2. Then, the experimental results are analyzed in Section 4.3.


### 4.1. Parameters’ Setting

Two widely used networks (NSFNET and US backbone) were used in the experiments. FS is 12.5 GHz, and the transmission distances of BPSK, QPSK, 8QAM, and 16QAM are selected as 9600, 4800, 2400, and 1200 km, respectively. In two topologies, all VNF-SCs in each group satisfy a uniform distribution. In order to make the algorithm converge to the optimal solution,tmax=2000 is used. Generally speaking, when the population is large, longer calculation time is required. In addition, when the population size is small, it will lead to poor population diversity. Therefore, the population size selected in the experiment is NP=100. Each VNF-SC requires frequency slots satisfying uniform distribution in [1, 10], and each link has 2000 frequency slots, that is, NF = 2000.


### 4.2. Experimental Results

In order to verify the performance of the proposed algorithm, we compared the proposed algorithm HS-MOEA/D with the other four algorithms. The first algorithm is proposed in the literature quotes [29], denoted as RSAGA. The queue information aware reliable SFC deployment algorithm (QARE) [30] was compared. An incremental approach is proposed to determine the number of required VNF backups in order to guarantee the required reliability, denoted as RAR-RS [31].The number of data center nodes are fixed asND=NV/4, ND=NV/2, and ND=3NV/3. In each experiment, the number of VNF-SCs is set as NR=ρNVNV−1, and ρ= 0.25, 0.5, 1, 2, and 4, respectively. Figures 1 and 2 show the total time delay and reliability obtained in NSFNST and US Backbone when ND=NV/4. The total time delay and reliability obtained in NSFNST and US Backbone when ND=NV/2 are shown in Figures 3 and 4, respectively. Figures 5 and 6 show the total time delay and reliability obtained in NSFNST and US Backbone when ND=3NV/4.Figure 1
Total time delay obtained whenND=NV/4. (a) Time delay in NSFNET. (b) Time delay in US Backbone.
(a)(b)Figure 2
Reliability obtained whenND=NV/4. (a) Reliability obtained in NSFNET. (b) Reliability obtained in US Backbone.
(a)(b)Figure 3
Total time delay obtained whenND=NV/2. (a) Time delay in NSFNET. (b) Time delay in US Backbone.
(a)(b)Figure 4
Reliability obtained whenND=NV/2. (a) Reliability obtained in NSFNET. (b) Reliability obtained in US Backbone.
(a)(b)Figure 5
Total time delay obtained whenND=3NV/4. (a) Time delay in NSFNET. (b) Time delay in US Backbone.
(a)(b)Figure 6
Reliability obtained whenND=3NV/4. (a) Reliability obtained in NSFNET. (b) Reliability obtained in US Backbone.
(a)(b)To demonstrate the uniformity, convergence, and diversity of the proposed algorithm, the following two metrics are used to evaluate the Pareto solutions:(1)
Spacing index (SI): it is defined by (15) below:(15)SIA=1PF∗−1∑z∈PF∗d¯−dz2,dz=minz−z′z≠z′,z′∈PF∗,d¯=1PF∗∑z∈PF∗dz.Spacing index is used to metric the uniformity of the Pareto solution. The smaller theSI, the better the solutions.(2)
Hypervolume index (HI): it is used to test the uniformity, convergence, and diversity of the solutions and defined by(16)HIPF∗=∪z∈PF∗volz,wherevolz is the hypervolume of area which is surrounded by z, the reference point r=r1,r2,…,rm, and m is the dimensionality of the objective space.


### 4.3. Experimental Analysis

Figures1, 3, and 5, respectively, show the total results obtained by the algorithm HS-MOEA/D and the benchmark algorithm (RSAGA, QARE, and RAR-RS), comparing the two networks. Time delay: in Figure 1, the total delay of the two networks when ND=NV/4 is obtained. It can be seen from the experimental results that when the number of VNF-SCs is the same, the total delay obtained by the HS-MOEA/D algorithm is less than that of the comparison algorithm. Similarly, when ND=NV/2 and ND=3NV/4, the total delay obtained is shown in Figures 3 and 5. It can be seen from the experimental results that when the number of VNF-SCs is the same, the total delay obtained by the HS-MOEA/D algorithm is less than that of the comparison algorithm. In each figure, the total delay increases as the number of VNF-SCs increases. When the number of VNF-SCs is 0.25NVNV−1, the total delay obtained by HS-MOEA/D is 4.2% to 5.1% less than that obtained by RSAGA, QARE, and RAR-RS. When the number of VNF-SCs is 4NVNV−1, the total delay obtained by the HS-MOEA/D algorithm is 6.8% to 10.7% smaller than that of the RSAGA, QARE, and RAR-RS algorithms, respectively.Figure2, 4, and 6 display HS-MOEA/D algorithms and three kinds of reference (RSAGA, QARE, and RAR-RS) in the two networks reliability. In Figure 1, when ND=NV/4, the reliability of the two networks is obtained. As it can be seen from the experimental results, when the number of VNF-SCs are the same, HS-MOEA/D algorithm is less than the overall delay alignment algorithms. Similarly, when the ND=NV/2 and Nd=3NV/4, the reliability obtained is shown in Figures 3 and 5. From the experimental results, HS-MOEA/D can obtain high reliability. In each figure, reliability increases as the number of VNF-SCs increases. When the number of VNF-SC is 0.25NVNV−1, reliability HS-MOEA/D of 3.1% to 4.5% is lower than RSAGA, QARE, and RAR-RS. When the number of VNF-SC is 4NVNV−1, the total delay HS-MOEA/D ratio, respectively, RSAGA, QARE, and RAR-RS from 7.8% to 13.2% is less.Table1 distance index shows two networks and overcapacity index (mean and standard deviation). This indicates that HS-MOEA/D algorithm can find Pareto at a different number of VNF-SCs and different data centers. This is more likely to meet the requirements of decision makers. Furthermore, it can be seen from Table 1, and the HS-MOEA/D of our objective optimization model can obtain a better PF.Table 1
Statistical results (mean and standard deviation) of the SI and HI.
NSFNETUS BackboneSIHISIHI0.250.252.3263 (1.6653E − 02)8.9380 (3.2723E − 01)1.7897 (1.9528E − 02)9.9280 (4.0634E − 01)0.52.8970 (1.9460E − 02)9.2320 (3.7531E − 01)2.1000 (2.1360E − 02)10.2581 (4.4745E − 01)13.3629 (2.9943E − 02)10.0051 (4.4146E − 01)2.3305 (3.1429E − 02)11.1974 (4.8147E − 01)23.6961 (3.9210E − 02)11.3392 (5.2283E − 01)2.5337 (4.5063E − 02)12.2851 (5.7294E − 01)44.1978 (4.9379E − 02)11.5057 (5.8654E − 01)3.1563 (5.2635E − 02)13.3369 (6.4754E-01)0.50.252.9545 (3.2742E − 02)9.3297 (3.7316E − 01)2.8562 (3.0922E − 02)10.3413 (4.3957E − 01)0.53.8342 (3.6206E − 02)9.9330 (4.5483E − 01)3.5894 (3.5052E − 02)11.5828 (4.9123E − 01)15.4902 (3.7653E − 02)10.3207 (5.6003E − 01)4.7823 (3.8701E − 02)12.3150 (5.6746E − 01)25.8677 (4.3181E − 02)10.9809 (6.1808E − 01)5.5477 (4.9167E − 02)13.3468 (6.2747E − 01)46.4148 (4.8029E − 02)11.7311 (6.6985E − 01)6.2916 (5.5488E − 02)13.5215 (6.7280E − 01)0.750.253.0428 (3.3962E − 02)9.8942 (3.9583E − 01)3.4076 (3.5179E − 02)10.6222 (4.5643E − 01)0.54.1417 (3.7368E − 02)10.2593 (4.7164E − 01)3.8753 (3.6518E − 02)11.9258 (5.2369E − 01)15.6085 (4.4496E − 02)10.8397 (5.9716E − 01)5.1496 (4.1972E − 02)12.3998 (6.0991E − 01)26.1780 (4.7168E − 02)11.4654 (6.4065E − 01)6.0941 (5.3259E − 02)13.5627 (6.5003E − 01)46.8401 (5.3024E − 02)12.1214 (7.0635E − 01)6.4832 (5.6802E − 02)14.4458 (7.0527E − 01)


## 4.1. Parameters’ Setting

Two widely used networks (NSFNET and US backbone) were used in the experiments. FS is 12.5 GHz, and the transmission distances of BPSK, QPSK, 8QAM, and 16QAM are selected as 9600, 4800, 2400, and 1200 km, respectively. In two topologies, all VNF-SCs in each group satisfy a uniform distribution. In order to make the algorithm converge to the optimal solution,tmax=2000 is used. Generally speaking, when the population is large, longer calculation time is required. In addition, when the population size is small, it will lead to poor population diversity. Therefore, the population size selected in the experiment is NP=100. Each VNF-SC requires frequency slots satisfying uniform distribution in [1, 10], and each link has 2000 frequency slots, that is, NF = 2000.


## 4.2. Experimental Results

In order to verify the performance of the proposed algorithm, we compared the proposed algorithm HS-MOEA/D with the other four algorithms. The first algorithm is proposed in the literature quotes [29], denoted as RSAGA. The queue information aware reliable SFC deployment algorithm (QARE) [30] was compared. An incremental approach is proposed to determine the number of required VNF backups in order to guarantee the required reliability, denoted as RAR-RS [31].The number of data center nodes are fixed asND=NV/4, ND=NV/2, and ND=3NV/3. In each experiment, the number of VNF-SCs is set as NR=ρNVNV−1, and ρ= 0.25, 0.5, 1, 2, and 4, respectively. Figures 1 and 2 show the total time delay and reliability obtained in NSFNST and US Backbone when ND=NV/4. The total time delay and reliability obtained in NSFNST and US Backbone when ND=NV/2 are shown in Figures 3 and 4, respectively. Figures 5 and 6 show the total time delay and reliability obtained in NSFNST and US Backbone when ND=3NV/4.Figure 1
Total time delay obtained whenND=NV/4. (a) Time delay in NSFNET. (b) Time delay in US Backbone.
(a)(b)Figure 2
Reliability obtained whenND=NV/4. (a) Reliability obtained in NSFNET. (b) Reliability obtained in US Backbone.
(a)(b)Figure 3
Total time delay obtained whenND=NV/2. (a) Time delay in NSFNET. (b) Time delay in US Backbone.
(a)(b)Figure 4
Reliability obtained whenND=NV/2. (a) Reliability obtained in NSFNET. (b) Reliability obtained in US Backbone.
(a)(b)Figure 5
Total time delay obtained whenND=3NV/4. (a) Time delay in NSFNET. (b) Time delay in US Backbone.
(a)(b)Figure 6
Reliability obtained whenND=3NV/4. (a) Reliability obtained in NSFNET. (b) Reliability obtained in US Backbone.
(a)(b)To demonstrate the uniformity, convergence, and diversity of the proposed algorithm, the following two metrics are used to evaluate the Pareto solutions:(1)
Spacing index (SI): it is defined by (15) below:(15)SIA=1PF∗−1∑z∈PF∗d¯−dz2,dz=minz−z′z≠z′,z′∈PF∗,d¯=1PF∗∑z∈PF∗dz.Spacing index is used to metric the uniformity of the Pareto solution. The smaller theSI, the better the solutions.(2)
Hypervolume index (HI): it is used to test the uniformity, convergence, and diversity of the solutions and defined by(16)HIPF∗=∪z∈PF∗volz,wherevolz is the hypervolume of area which is surrounded by z, the reference point r=r1,r2,…,rm, and m is the dimensionality of the objective space.


## 4.3. Experimental Analysis

Figures1, 3, and 5, respectively, show the total results obtained by the algorithm HS-MOEA/D and the benchmark algorithm (RSAGA, QARE, and RAR-RS), comparing the two networks. Time delay: in Figure 1, the total delay of the two networks when ND=NV/4 is obtained. It can be seen from the experimental results that when the number of VNF-SCs is the same, the total delay obtained by the HS-MOEA/D algorithm is less than that of the comparison algorithm. Similarly, when ND=NV/2 and ND=3NV/4, the total delay obtained is shown in Figures 3 and 5. It can be seen from the experimental results that when the number of VNF-SCs is the same, the total delay obtained by the HS-MOEA/D algorithm is less than that of the comparison algorithm. In each figure, the total delay increases as the number of VNF-SCs increases. When the number of VNF-SCs is 0.25NVNV−1, the total delay obtained by HS-MOEA/D is 4.2% to 5.1% less than that obtained by RSAGA, QARE, and RAR-RS. When the number of VNF-SCs is 4NVNV−1, the total delay obtained by the HS-MOEA/D algorithm is 6.8% to 10.7% smaller than that of the RSAGA, QARE, and RAR-RS algorithms, respectively.Figure2, 4, and 6 display HS-MOEA/D algorithms and three kinds of reference (RSAGA, QARE, and RAR-RS) in the two networks reliability. In Figure 1, when ND=NV/4, the reliability of the two networks is obtained. As it can be seen from the experimental results, when the number of VNF-SCs are the same, HS-MOEA/D algorithm is less than the overall delay alignment algorithms. Similarly, when the ND=NV/2 and Nd=3NV/4, the reliability obtained is shown in Figures 3 and 5. From the experimental results, HS-MOEA/D can obtain high reliability. In each figure, reliability increases as the number of VNF-SCs increases. When the number of VNF-SC is 0.25NVNV−1, reliability HS-MOEA/D of 3.1% to 4.5% is lower than RSAGA, QARE, and RAR-RS. When the number of VNF-SC is 4NVNV−1, the total delay HS-MOEA/D ratio, respectively, RSAGA, QARE, and RAR-RS from 7.8% to 13.2% is less.Table1 distance index shows two networks and overcapacity index (mean and standard deviation). This indicates that HS-MOEA/D algorithm can find Pareto at a different number of VNF-SCs and different data centers. This is more likely to meet the requirements of decision makers. Furthermore, it can be seen from Table 1, and the HS-MOEA/D of our objective optimization model can obtain a better PF.Table 1
Statistical results (mean and standard deviation) of the SI and HI.
NSFNETUS BackboneSIHISIHI0.250.252.3263 (1.6653E − 02)8.9380 (3.2723E − 01)1.7897 (1.9528E − 02)9.9280 (4.0634E − 01)0.52.8970 (1.9460E − 02)9.2320 (3.7531E − 01)2.1000 (2.1360E − 02)10.2581 (4.4745E − 01)13.3629 (2.9943E − 02)10.0051 (4.4146E − 01)2.3305 (3.1429E − 02)11.1974 (4.8147E − 01)23.6961 (3.9210E − 02)11.3392 (5.2283E − 01)2.5337 (4.5063E − 02)12.2851 (5.7294E − 01)44.1978 (4.9379E − 02)11.5057 (5.8654E − 01)3.1563 (5.2635E − 02)13.3369 (6.4754E-01)0.50.252.9545 (3.2742E − 02)9.3297 (3.7316E − 01)2.8562 (3.0922E − 02)10.3413 (4.3957E − 01)0.53.8342 (3.6206E − 02)9.9330 (4.5483E − 01)3.5894 (3.5052E − 02)11.5828 (4.9123E − 01)15.4902 (3.7653E − 02)10.3207 (5.6003E − 01)4.7823 (3.8701E − 02)12.3150 (5.6746E − 01)25.8677 (4.3181E − 02)10.9809 (6.1808E − 01)5.5477 (4.9167E − 02)13.3468 (6.2747E − 01)46.4148 (4.8029E − 02)11.7311 (6.6985E − 01)6.2916 (5.5488E − 02)13.5215 (6.7280E − 01)0.750.253.0428 (3.3962E − 02)9.8942 (3.9583E − 01)3.4076 (3.5179E − 02)10.6222 (4.5643E − 01)0.54.1417 (3.7368E − 02)10.2593 (4.7164E − 01)3.8753 (3.6518E − 02)11.9258 (5.2369E − 01)15.6085 (4.4496E − 02)10.8397 (5.9716E − 01)5.1496 (4.1972E − 02)12.3998 (6.0991E − 01)26.1780 (4.7168E − 02)11.4654 (6.4065E − 01)6.0941 (5.3259E − 02)13.5627 (6.5003E − 01)46.8401 (5.3024E − 02)12.1214 (7.0635E − 01)6.4832 (5.6802E − 02)14.4458 (7.0527E − 01)


## 5. Conclusions

This paper studies the deployment of VNFs for VNF-SC. Firstly, a two-objective mathematical model of reliability and delay is established. In this model, VNFs are divided into two categories; i.e., in a portion where each VNF-SC is required, VNFs are dependent the other parts are independent. Secondly, a MOEA/D (HS-MOEA/D) algorithm based on harmony search is proposed, which effectively solves the model. In the HS-MOEA/D, a multiobjective optimization problem is converted into a series of subproblems by using a single-objective optimization Chebyshev decomposition mechanism. The in-depth study of the evolution of a new strategy proposed a new harmony search (HS) algorithm. Finally, in order to display high-performance algorithm, a lot of experiments have been conducted. The simulation results show that the algorithm improves the performance of the system, the SFC, to improve the reliability and reduce the end-to-end delay.



---

*Source: 5538931-2021-08-24.xml*