The development of Fifth-Generation (5G) mobile communication technology has remarkably promoted the spread of the Internet of Things (IoT) applications. As a promising paradigm for IoT, edge computing can process the amount of data generated by mobile intelligent devices in less time response. Network Function Virtualization (NFV) that decouples network functions from dedicated hardware is an important architecture to implement edge computing, deploying heterogeneous Virtual Network Functions (VNF) (such as computer vision, natural language processing, intelligent control, etc.) on the edge service nodes. With the NFV MANO (Management and Orchestration) framework, a Service Function Chain (SFC) that contains a set of ordered VNFs can be constructed and placed in the network to offer a customized network service. However, the procedure of NFV orchestration faces a technical challenge in minimizing the network cost of VNF placement due to the complexity of the changing effect of traffic volume and the dependency on the VNF relationship. To this end, we jointly optimize SFC design and VNF placement to minimize resource cost while taking account of VNF dependency and traffic volume scaling. First, the problem is formulated as an Integer Linear Programming (ILP) model and proved NP-hard by reduction from Hamiltonian Cycle problem. Then we proposed an efficient heuristic algorithm called Traffic Aware and Interdependent VNF Placement (TAIVP) to solve the problem. Compared with the benchmark algorithms, emulation results show that our algorithm can reduce network cost by 10.2% and increase service request acceptance rate by 7.6% on average.
Fifth-Generation (5G) [
In the NFV architecture, VNFs are implemented in software and running on NFV based equipment. When traffic arrives, it will be orderly served by VNFs, and we call these ordered VNFs as a Service Function Chain (SFC) [
There has been extensive research on optimization for VNF placement assuming the SFC topology is given by users [
We demonstrate our motivation in
In this paper, the joint optimization of SFC design and VNF placement is studied while considering both traffic volume scaling and VNF dependency. First, the problem is formulated as an Integer Linear Programming (ILP) model and proved NP-hard by reduction from Hamiltonian Cycle problem. Next, due to its complexity, we design a heuristic algorithm called Traffic Aware and Interdependent VNF Placement (TAIVP) algorithm. In our algorithm, we first construct an optimal SFC based on traffic volume scaling factors and VNF dependency to minimize the computing resource cost. Thereafter, based on A-star algorithm, we find a feasible work path with sufficient resources and minimum hops for each SFC. Finally, to minimize the communication resource cost, we present an optimal SFC deployment strategy. Compared with the best of the benchmark algorithms, emulation results show that with the help of our algorithm, the network cost can be reduced by 10.2% on average, and the service request acceptance rate can be increased by 7.6% on average.
We summarize our main contributions as follows:
We study the joint optimization of SFC design and VNF placement for minimizing resource cost while taking account of VNF dependency and traffic volume change. And then the problem is formulated as an ILP model. Due to the studied problem is proved NP-hard, we develop an efficient heuristic algorithm to find sub-optimal solutions. Compared with three benchmark algorithms, emulation results show that with the help of our algorithm, the network cost can be reduced by 10.2% on average, and the service request acceptance rate can be increased by 7.6% on average.
We organize the rest of our paper as follows. In
Recently, extensive researches have emerged on SFC design and VNF placement. These works mainly focus on the following two parts.
For the first part, some of them studied the problem assuming the SFC topology is given. Ghaznavi et al. [
For the second part, the SFC design has been taken into consideration in many previous researches. Sallam et al. [
Compared with the previous works, the optimization of SFC design and VNF placement is focused, which is based on traffic volume scaling and VNF dependency. In this paper, an efficient heuristic algorithm is proposed which takes both communication and computing resources into consideration to minimize total network cost. The proposed algorithm divides the original optimization problem into three sub-problems, then solves each sub-problem with the optimal method.
In this section, the studied problem is developed as an ILP model. We provide all the definitions in
Notation | Description |
---|---|
The network topology, where the set of nodes is denoted by |
|
The set of service requests | |
The capacity of node |
|
Link |
|
The source node of flow |
|
The destination node of flow |
|
The initial traffic bandwidth requirement | |
The VNF set that flow |
|
The traffic volume scaling factor of VNF |
|
A binary variable. If |
|
A binary variable. If flow |
|
A binary variable. If VNF |
|
A binary variable. If the |
|
The traffic volume of flow |
|
The traffic volume of flow |
|
The correlation coefficient for computing resources of VNF |
|
The communication latency on the link of flow |
|
The computing latency on the edge server of flow |
|
The 5G-based SFC latency requirement of flow |
|
The computing resource cost of VNF |
|
A binary variable. If vertex |
|
A binary variable. If edge |
|
The load of the link | |
The weight of the link |
|
The processing VNF cost | |
The total cost of traffic from the current node |
|
The actual cost of going from the starting point |
|
The estimated cost of going from the current node |
|
The weight of the link between two adjacent nodes |
The input are specifications of the policy and information of the network in our problem. The network is denoted by
The model objective is to minimize the total network resource cost. The problem is formulated as an ILP model.
A binary variable
Next, a path for the traffic flow
Then, for any traffic flow in the network, the controller deploy its VNFs to the appropriate physical nodes. We use a binary variable
We assume flow
In addition, the same node is allowed to deploy multiple VNFs of the same flow to get the optimal solution when the computing resources are sufficient. Therefore, for flow
Next, we build a mathematical model according to the constraints in the underlying network. In this section,
Under circumstances that the computing resource cost of VNFs are positively related to the traffic volume, so we give the correlation coefficient
The sum of computing resources required must be no more than the node capacity provided by the physical node
In addition, we should guarantee that the coverage of the bandwidth capacity. We present it as follows:
Since the our VNFs are deployed on the edge servers to get close to the data source, meeting the low latency requirement of 5G, the model must have a latency constraint:
To meet the first and last hops of the service request which is at the source node and destination node, respectively, we present following formula:
That each VNF must only be placed on a physical node once is assumed:
For the dependency relationship between VNFs, the following formula gives the constraints that should be satisfied after mapping. It means that for the two virtual network functions of
After we map the virtual link of the traffic flow to the physical link, we ensure the law of flow conservation in the network. This can be described as:
In order to quantify computing resources and communication resources in a unified way, we design coefficients
Then, we give the contribution formula of total communication resource cost:
Finally, to minimize the total network resource cost, the ILP model is formulated as follows:
Subject to:
By reduction from Hamiltonian Cycle problem, we can prove our problem NP-hard, where the VNFs order constraint is relaxed. Because the Hamiltonian Cycle problem is a classic NP-hard problem, the TAVIP problem is a NP-hard problem. We use the following theorems demonstrating the NP-hardness of the TAVIP problem.
For each edge
There shall exist a simple circle that contains each vertex in the graph.
We redefine our optimization problem to a route planning problem. Then we will explain that we can reduce the Hamiltonian Cycle problem to our problem. Consider a TAVIP instance with a graph
We generate a link
For any
Mapping reductions are used to reduce one decision problem to another decision problem. So if we can reduce problem
We can reduce the Hamiltonian Cycle problem to our optimization problem through the definition and
In this section, a heuristic algorithm called TAIVP is proposed. As is shown in Algorithm 1, the TAIVP algorithm has three main components. For each service request, the algorithm constructs an optimal SFC based on VNF traffic volume scaling factor and dependency by SFC Construction function (line 2). Then, in line 3, it finds a feasible work path with sufficient resources and minimum hops for each SFC by Path Planing function. In line 4, according to the influence of traffic volume scaling factors of VNFs, the SFC is deployed to the determined path by SFC Embedding function [
SFC Construction function is used to construct SFC with the lowest network resource cost while satisfying the constraint of the VNF dependency. The most original solution is to put the VNF with smaller traffic volume scaling factor in the front position. Because of the dependency between VNFs, we propose the construction strategy of combining VNFs to minimize network resource cost. We first rank all VNFs in the ascending order of their traffic volume scaling factors. When a VNF has dependency constraint, if its traffic volume scaling factor is smaller than the dependent VNF
We define two parameters
For a combined VNF set with VNF
To determine the order of two VNF sets without dependency, as shown in
This shows that if
In Algorithm 2, we present the detail of SFC Construction function. The input of the Algorithm 2 is the VNF sets
A-star algorithm is a commonly used heuristic search algorithm based on Dijkstra algorithm. It is popular in path planning because of its flexibility, especially in the field of artificial intelligence. It selects the expansion direction of the node reasonably through the evaluation function, and constantly searches for the best path by approaching the destination node. In this way, it can search the node with high probability first, thus improving the search efficiency of the path node.
As shown in
In this formula,
The purpose of path planning is to minimize the resource cost on the work path. Under the condition of SFC construction, the shorter the path, the less the link resource cost. The key point of A-star algorithm is to find
As is shown in Algorithm 3, we present the detail of Path Planning function. First, we arrange the service requests according to the initial bandwidth requirement
Through the processing of the first two functions, we now know the SFC and work path. The problem to be solved in this stage is to ensure the total cost of the whole link is the smallest by deploying VNFs to the determined work path according to the impact of their traffic volume scaling factors on the traffic and its order. A SFC Embedding algorithm is proposed to optimize this problem.
The constructed SFC has
As is shown in
It can be seen that for each row, the communication cost after the
As is shown in Algorithm 4, we present the detail of SFC Embedding function. First, we construct a matrix diagram like
Our test networks, NSFNET and USNET, are shown in
The results of the network resource cost consumed by the five algorithms under different service requests in NSFNET and USNET network topologies are demonstrated
In our study, the coefficient of computing resource is denoted by
Beside the cost of network resources, we also need to consider the success rate of traffic flow deployment. Therefore, we will discuss the change of traffic flow acceptance rate of these five algorithms. The traffic flow acceptance rate is that the total number of requests divides the number of successful deployment requests, and the
The relationship between the traffic flow acceptance rate and the number of service requests is shown in
As shown in
In addition, the number of VNFs for service requests also affects the result of the request reception rate. In
As shown in
In this paper, we jointly optimize SFC design and VNF placement problems to minimize resource cost while taking into account VNF dependency and traffic volume scaling. We first formulated the problem as an ILP model and proved its NP-hardness. Then we proposed and evaluated a heuristic algorithm called TAIVP. Finally, emulation results showed that our algorithm could reduce network cost by 10.2% and increase service request acceptance rate by 7.6% on average. There is a wide range of scenarios where our algorithm can be applied. For example, we can use this algorithm to optimize the positions of VNFs (such as computer vision, natural language processing, intelligent control, etc.) in edge computing-enabled 5G networks. However, there are still some limitations of this paper. First, we didn’t consider the QoS of the service requests, which is an important part in NFV. Besides, the heuristic algorithm can not guarantee the distance of the returned solution to the optimal one. Therefore, in future work, we first plan to modify our ILP model to take account of the QoS of the service requests. Furthermore, we plan to analyze the problem and devise an approximate algorithm with provable approximate solutions.