Journal of Quantum Computing DOI:10.32604/jqc.2022.027560
Article

Research on Service Function Chain Orchestrating Algorithm Based on SDN and NFV

Yuning Jia*, Yu Gong and Yifei Wei

Beijing Key Laboratory of Work Safety Intelligent Monitoring, Beijing University of Posts and Telecommunications, Beijing, 100876, China
*Corresponding Author: Yuning Jia. Email: 1073967337@qq.com
Received: 25 January 2022; Accepted: 27 April 2022

Abstract: Software defined network (SDN) and network function virtualization (NFV) have become a new paradigm of a new generation of network architecture. SDN and NFV can effectively improve the flexibility of deploying and managing service function chains (SFCs). By combining SDN and NFV and applying them to the resource orchestration problem of SFC deployment, the three-tier architecture consisting of SDN controller, network function virtualization and physical underlying computing resource layer in the process of heterogeneous network resource mapping is considered. And an optimization algorithm for active control resources based on SDN and NFV is proposed. Firstly, the user’s utility is modeled by the multi-standard aggregated multi-criteria utility algorithm, and the optimization goal is transformed into the problem of maximizing the user’s utility. Then the controller, based on the algorithm’s prediction of the future state and real-time monitoring of the network utilization, makes decisions and issues control commands for the arriving SFC requests, based on which it occupies the underlying resources held by the virtualized network function (VNF). The simulation results show that, compared with the static timing resource allocation algorithm, the active control resource deployment algorithm proposed in the article has better performance in terms of resource utilization, acceptance rate, and user creation utility.

Keywords: SDN; NFV; service function chain; resource allocation

1  Introduction

In order to adapt to the explosive growth of mobile data traffic and a large number of new applications and business needs, operators have deployed large-scale network infrastructure to provide users with ubiquitous network services. At the same time, different access networks such as wired, cellular, and WLAN coexist in the network space around us. On the one hand, huge traffic and heterogeneous characteristics bring difficulties to network management. On the other hand, as the available bandwidth of the network increases, the performance requirements of users for network services are becoming more and more acute. How to design a solution that can satisfy users’ needs for network-perceived network quality [1] under the condition of considering indifferent heterogeneous network connection and rational distribution of heterogeneous network resources has become a key issue in optimizing the utilization of network resources.

Nowadays, SDN and NFV have been widely used in the research of network resource orchestration. With the help of SDN technology, network equipment has changed from a closed mode to an open general equipment mode, which separates the control plane and the data plane, which allows the network to be programmed through open interfaces [2]; With the help of NFV technology, network element functions can be deployed in the form of software on the general server node of the infrastructure, so that network element functions and special hardware devices are separated [3,12]. In [4], the author focuses on the SDN-based 5G cellular network resource allocation solution, describes the methods to solve different resource requirements, and conducts an in-depth analysis and overview of different resource allocation schemes. The author in [5] proposed a GSO-RBFDM model based on dynamic resource pricing to solve the problem of virtual network resource allocation. While realizing dynamic resource allocation, it also optimizes acceptance rate, network cost and link pressure. In [6], the author designed a virtualized resource management framework called GreenVolP based on SDN and NFV orchestration. By managing the number of network devices such as VolP servers and switches, design algorithms that effectively prevent VolP network overloads while minimizing the use of switches and other devices in the network.

At present, the research on network resource mapping and orchestration algorithms for the integration of SDN and NFV is mainly focused on a certain network resource, and the optimization direction is mostly to optimize the overall network resource utilization efficiency and reduce network costs [13,14]. However, in reality we are faced with complex heterogeneous network resources and user groups with different needs and preferences. It has become an inevitable trend to bring users a better perceived service quality. Therefore, the focus of this article is: in the long-term operation process, while ensuring the consumption of physical network resources, as much as possible to meet the needs and preferences of the user side, so as to achieve the goal of maximizing the quality of service for the user by the network.

This paper combines SDN and NFV technologies to further abstract the network, which can form an end-to-end and logically isolated network, and realize a user-centric framework. A user agent corresponding to each user can be generated on a virtual device with connection information retention and user situation awareness capabilities. Through the user agent, the ubiquitous and undifferentiated network connection of users in a heterogeneous network can be realized. User preference feature perception, through flexible resource scheduling management to ensure the maximum utility provided to users. The main contributions of this paper are summarized as follows:

(1)   Based on the three-tier architecture composed of SDN controller, network function virtualization, and physical underlying computing resource layer in the process of heterogeneous network resource mapping [15], in view of the resource allocation problem of service function chain deployment, A user-centered framework for maximizing user utility is proposed. Modeling through multi-criteria utility theory transforms the optimization problem of resource scheduling into a problem of maximizing user utility.

(2)   Propose a dynamic active control resource deployment algorithm based on request priority and user preference, including two stages: network state prediction and control based on load utilization. The controller makes corresponding decisions on the SFC request and issues control commands based on the real-time monitoring of the utilization rate predicted by the future state. Based on this, the VNF occupies the resources held by the physical nodes to achieve the purpose of active control and maximum utility.

(3)   A series of simulation experiments are used to prove the effectiveness of the proposed algorithm. The simulation results show that in a congested network scenario, the acceptance rate of high-priority requests and the overall user utility benefit are significantly improved. At the same time, this method does not reduce the utilization rate of the network, and ensures the efficiency of resource utilization.

2  System Model

2.1 Underlying Network Model

Under the business of virtual network resource allocation problem, different users access corresponding service providers (SP) to obtain network services according to business needs. SP constructs corresponding virtual network requests according to business needs, and then based on infrastructure providers (InP) physical network resource constraints, using resource allocation algorithms to allocate suitable physical networks to carry the virtual network [3]. In the network virtualization business system, users can access different service providers according to their own needs and enjoy customized services. When deploying virtual network requests, the SP selects an appropriate InP based on available physical resources, service type, and lease cost. Sometimes it is even necessary to lease the underlying physical network resources of multiple InPs at the same time. The performance of the virtual network resource allocation algorithm directly affects the resource utilization rate of the underlying physical network, the operational effect of network services and the user experience.

The underlying infrastructure network is represented by an undirected graph G = (N, L), where N represents the set of physical nodes, L represents the link between nodes, and node n(n∈N) and node p(p∈N) The link between is expressed as ln,p, and the upper limit of the link bandwidth resource is expressed as Bn,p. In the virtual mapping process, after the request arrives, according to the available resources of the physical network, a reasonable physical node is selected to perform the mapping of computing resources until the mapping is successful and the physical resources occupied by it are released.

After the underlying physical network is virtualized, it is constructed by multiple physical nodes that can provide physical resources. These physical nodes provide VNFs with various types of resources such as CPU, memory, and disk. At this time, each VNF in the service function chain can be deployed on any physical node, and one physical node can provide services for multiple VNFs located in the same service function chain [3].

The amount of data processed by each VNF determines its own resource requirements. In order to reduce the complexity of the algorithm, this model unifies the multiple resources (CPU, memory, disk) that can be provided by general-purpose processor nodes into computing resources. The virtual nodes in different virtual requests can be mapped to the same physical node. For each node n(n ∈ N), its available resources are:

CN(n)=c(n)−∑∀nv→n⁡c(nv)+∑∀nv→n⁡Rel(c(nv))(1)

c(n) represents the total amount of computing resources that the node n can provide, and the second term ∑∀nv→n⁡c(nv) represents the sum of computing power of all virtual nodes nv mapped to physical node n, the value will only change after the request is accepted and the actual computing resources are allocated. Rel(c(nv)) in the third item represents the resources released from the virtual node nv, and the change of this value depends on whether the corresponding NFV life cycle arrives or not. Therefore, the dynamic change status of the available resource CN(n) can be captured by the controller in real time, and the next decision can be made based on this.

2.2 SFC Deployment Model

The underlying network can provide VNFs of different protocol layer types. Let F={ fp|p=1,2,3,…P} represent the set of VNFs, where p=type(fp) represents the type of VNF [9]. It should be noted that each node may not provide all types of VNFs. Therefore, it is assumed that each VNF type has a set of nodes to be deployed [8]. Binary variable γn,p indicates whether node n can deploy VNFfp∈F:

γn,p={1,IfVNFfp canbedeployedonnoden∈N0,otherwise(2)

The SFC request is composed of multiple VNFs, ingress and egress nodes with order constraints [11,12]. Fig. 1 shows the deployment diagram of the service function chain. Let S={ sk|k=1,2,3,…K} represent the set of SFC requests, sk=<ik,ek,φk,τk> represents the SFC request, where ik,ek∈N represent the entry and exit nodes, respectively, and τk represents the life cycle of the SFC (the occupancy time of resources).

Figure 1: Schematic diagram of service function chain deployment

When the SFC service time exceeds the life cycle, the service ends and the allocated resources are reclaimed [10]. φk={ fmk|m=1,2,3,…Mk} represents the ordered VNF sequence of SFC, where fmk∈F. Finally, define the binary variable ηm,nk∈{0,1} to represent the mapping relationship between VNF and physical nodes [12]. If fmk is deployed on node n, then ηm,nk=1; otherwise, ηm,nk=0.

ηm,nk={1,IfVNFfpisdeployedonnoden∈N0,otherwise(3)

Therefore, the number of VNFs deployed in the k-th service function chain can be expressed as:

W=∑fmk∈k⁡∑n∈N⁡ηm,nk(4)

For the service function chain sk∈S, the data processing volume of the VNF fmk composing the SFC is expressed as Rmk, the fmk computing resource demand and its data processing volume are defined as a linear relationship, and the correlation coefficient (data processing demand factor) is expressed by αm, then the computing resource demand vmk of the VNF can be expressed as [13]:

vmk=αmkRmk(5)

2.3 Optimization Objective

In microeconomics, utility refers to the ability of goods or services to meet human needs. A related term is utility function, which relates to the utility that consumers obtain from goods or services. Different consumers with different user preferences will have different utility values for the same product. The basic idea of the utility theory is that the decision maker will always choose the decision with the greatest utility value.

In a heterogeneous network, for the user side, the utility function is defined as U(x), an aggregated multi-criteria utility algorithm based on multiple standards:

U(x)=∑i=1n⁡wiui(xi),∑i=1n⁡wi=1(6)

where x is the vector of n standards under consideration, wi is the corresponding weight, ui(xi) is the basic utility of standard i, so U(x) comprehensively considers n attributes that users care about. This format provides a simple and understandable way to aggregate different basic utilities. But it has some serious limitations that have been studied in [16], so a new form of utility function is proposed in conjunction with the discussion of related issues:

U(x)=∏i=1n⁡[ui(xi)]wi,∑i=1n⁡wi=1(7)

For the single-criteria utility function, select the Sigmoid function:

u(x)=11+ek(xm−x)(8)

The utility function used in the early research work is the logarithmic utility function, which is a good approximation of the utility value of the wired communication network. In recent years, the demand for wireless adaptive real-time applications has continued to increase, and the utility function that approximates real-time applications is the sigmoid function [17]. The concave utility function is only suitable for traditional data service modeling, and does not capture the characteristics of the increasingly popular audio and video services on the Internet. That is, corresponding to the common services that are sensitive to delay and rate, such as streaming video and audio services, reducing the transmission data rate below a certain threshold will cause a significant drop in experience (For example, below a certain bit rate, the quality of audio communication will drop sharply) [18]. Therefore, in order to effectively simulate the changes in user utility value, it is reasonable to use the Sigmoid utility function to model.

Obviously, the value of u(x) is between 0 and 1, the center of the function curve is (xm,0.5), the curve can be moved to the left or right by adjusting xm, and the steepness of the curve can be controlled by the gradient coefficient k, So it can simulate the user’s sensitivity to network changes. On the left side of xm, the curve is convex, and on the right side, the curve is concave. That is to say, when the criterion value is small, as the criterion value increases, the utility value will increase rapidly; and when the criterion value is greater than xm, as it increases, the utility value will increase slowly.

It can be defined as follows:

1)whenx≤xm:u(x)=11+ek1(xm−x),k1>0(9)

2)whenx>xm:u(x)=11+ek2(xm−x),k2>0(10)

The upper limit xα(0<xα<xm) and the lower limit xβ(xβ>xm) need to be set. u(xα)=ul, ul is a floating-point number close to 0 [16]. u(xβ)=uh, uh is a floating-point number close to 1. Based on this, the values of k1 and k2 can be calculated:

k1=ln(1−ulul)xm−xα; k2=ln(1−uhuh)xm−xβ(11)

As for the total benefits provided by the allocation of SFC computing resources for a single user to the user, it is necessary to consider the priority of the user’s request and the pickiness of resources to calculate the benefits. Intuitively, high-priority has a larger slope and lower fault tolerance, and a low-priority has a smaller slope and higher fault tolerance. The criteria can be grouped into two types. The timeliness of acceptance of VNF requests and resource allocation in the service function chain can be regarded as a criterion. Whether the user’s criticality of the accessed network resources is met in a timely manner can also be regarded as another criterion. Therefore, it is stipulated that if the request is accepted within the time unit, or the resource criticality of a single user’s SFC access is satisfied (for example, the preference of cellular network access for security considerations, or the preference for WIFI resources based on cost performance), then the corresponding criterion obtains the maximum benefit, that is, the independent variable of u(x) can take the value xβ.

Otherwise, the corresponding benefit will be lost according to the amount of elapsed unit time, that is, x=xβ−c(tfmk−tfmk0) in u(x). In the formula, tfmk0 is the initial time when the VNFR request is initiated, and tfmk is the time when the request is accepted (the actual mapping resource is allocated).

The above U(x) is a measure of the user benefit result produced by the internal algorithm of the controller for a single SFC. The user benefits generated by a certain VNF within the SFC need to be expressed separately by ui(xi), according to the above φk={ fmk|m=1,2,3,…Mk}, i can be sequentially selected according to the number m of VNF sets of the SFC.

Usk=∏i=1Mk⁡[ui(xi)]wi(12)

Therefore, if the long-term realized total user benefit is calculated, it is necessary to perform cumulative calculation to allocate the total benefit of k SFC computing resources.

Ua=∑sk∈S⁡Usk(13)

The goal of this article is to fully consider user preferences and the priority of requests for SFC resource allocation. Calculate user request priority and resource criticality according to user characteristics to obtain utility benefits, thereby establishing a user-centric architecture. Therefore, the optimization goal of this paper is modeled as:

maxUa

s.t.

C1:∑i=1nwi=1C2:∑sk∈S∑fmk∈φkηm,nkνm,nk≤CN(n),∀n∈NC3:∑fp∈Fγn,p≥1C4:∑n∈Nγn,p≥1C5:∑sk∈S∑fmk∈φkηm,nkηm+1,pkνmk≤Bn,p,n,p∈N,n≠p(14)

C1 is the user utility calculation coefficient constraint. The calculation of the multi-standard aggregate utility Usk of each SFC is constrained so that the sum of the coefficients of each single standard is 1; C2 indicates that the computing resources occupied by all VNFs deployed on a node must not be exceeds the total amount of computing resources that this node can provide. Since the binary variable γn,p indicates whether the node can deploy VNFfp∈F, C3 ensures that each node can support at least one type of VNF for deployment, and C4 ensures that every type of VNFfp∈F can be deployed. C5 indicates that the bandwidth resources of each link in the network will not exceed the upper limit.

3  Algorithm Design

3.1 Process Description

The algorithm in this paper fully considers the decision factors including priority and resource preference when the controller receives the SFC request to allocate the actual resources for each VNF component, and determines the resource allocation plan within the time slice. In this way, a control instruction is issued to the user agent generated at the target node. The whole process is mainly composed of three parts: status collection, decision-making and issuing instructions.

(1)   Before making any decision, the controller will collect the underlying network status information, calculate and update the available resources of each node, and collect user preferences.

(2)   Then, the controller will execute the decision-making component, which determines the virtual resource allocation plan within each time slice.

(3)   Once the allocation plan is determined, the controller will issue a control instruction to the user agent, and the user agent will occupy the underlying virtual resources held by the VNF according to the control instruction of the controller.

3.2 Algorithm Implementation

The input of the algorithm includes: the received VNFR, user characteristics (high and low priority) and resource preference; thus output: whether to accept the request and allocate the actual computing resources, including the selected physical nodes and the resources provided by them. During this period, monitor the information on the successful occupation of node resources, and update the network status in time; monitor the information on the release of node resources in the network, and when the service is terminated, the allocated resources occupied by the service function chain are recovered.

Active control resource deployment based on request priority and user preference is the main focus of this algorithm. Assuming that the controller knows the average arrival rate of SFC requests, it can predict the next state of the network by considering the arrival probability of the newly added SFC in the next time unit. Then, according to the prediction of the next state, the resource utilization rate of the next time unit is calculated. Based on the comparison between this value and the network utilization threshold, the algorithm selects and decides whether to temporarily not process a low-priority request. Therefore, the active control resource deployment algorithm proposed in this paper includes two stages: network state prediction and control based on load utilization. The flow chart of the SFC deployment algorithm is shown in Fig. 2.

Figure 2: Algorithm flow chart

1)   Network state prediction: At this stage, the controller estimates the next state of the network according to the arrival probability of the upcoming request in the next time unit [7]. The next state of the network is predicted as:

S~T+1=ρST+1+(1−ρ)ST(15)

2)   Control based on load utilization: Calculate the resource ∑n∈N⁡CN(n) according to the predicted next state S~T+1, and calculate the network resource utilization as:

U=1−∑n∈N⁡CN(n)∑n∈N⁡c(n)(16)

In the formula, U is the ratio of network allocation resources to total resources. If the percentage of network utilization is greater than the pre-selected threshold, it is possible that in the next state, the upcoming high-priority VN request will be rejected. Therefore, as will be mentioned below, in this case, the proposed active control resource deployment algorithm will actively not process a low-priority VNFR temporarily.

Since the algorithm solves the problem of VNF deployment and orchestration under dynamic changes in business requirements, the value will only change when the request is accepted and the actual computing resources are allocated. The essence of dynamic resource changes is the arrival of new requests and the release of allocated resources. When new requests arrive in each time slot, the deployment decision of the algorithm will be triggered. The dynamic changes of available resources can be captured by the controller in real time, based on which the next decision can be made.

After receiving a new request in this time slot, the algorithm will sequentially traverse the SFC request queue within the time unit and traverse the VNFs in the service chain in order. By evaluating the types of resources required by each VNF, a series of candidate nodes that can be deployed are selected. If the remaining available resources of the candidate node are sufficient to provide the mapping requirements of the VNF, the calculation resource pre-mapping is performed, that is, the process of assuming that the request is accepted and calculating the possible network resource utilization rate in the future. If the prediction result shows that even if all the requests are accepted, the network resource utilization rate of the next time slot will not exceed the threshold, then the actual resource allocation is performed. If it is found that the future utilization rate may exceed the preset threshold, select a low-priority SFC to temporarily not allocate available resources for it, and mark the request so that it will be prioritized in the next competition of the same level. This is to prevent the same or several requests from being discarded consecutively, which will not meet expectations. After the resource allocation is over, the algorithm updates the network state and starts to process the SFC request of the next time slot, and starts to traverse the newly arrived request queue.

4  Simulation Results and Analysis

In order to evaluate the method proposed in this article, we chose to use Python 3.6.9 for simulation and run on an Ubuntu 18.04 virtual machine with 4.0GB RAM and a 2-core processor. As shown in formula 17, the simulation assumes that the arrival rate of VNF requests follows the Poisson distribution P [19], and the values of λ for different priority requests are different, and the selection of numerical values was based on relevant studies [19,20] and the network scale simulated in this paper. The average arrival rate of high-priority requests is λh, and the average arrival rate of low-priority requests is λl. Choose to estimate the next state of the network based on the Poisson distribution arrival rate of high-priority VN requests.

P(X=i)=(ni)(λn)i(1−λn)n−i=e−λλii!(17)

And all the simulation data are shown in Tab. 1 as follows:

In order to verify the performance of the proposed active control resource deployment algorithm, the following four performance indicators are considered:

(1)   Acceptance rate of high-priority VNF requests: According to the purpose of resource management in this article, in order to increase the number of high-priority VN requests accepted in the network, we calculated the ratio of accepted high-priority VN requests to total high-priority VN requests.

(2)   Resource utilization: The average ratio of the sum of the used resources of the network to the total available resources is measured.

(3)   User utility: The algorithm in this paper aims to meet the needs and preferences of users as much as possible, so as to maximize the network’s service quality for users. The measurement of user utility can intuitively reflect the improvement of the algorithm to the user’s perception quality and the advantages of the algorithm.

(4)   Utility load ratio: In order to better evaluate the utilization value of the algorithm to the unit load, the ratio between utility and load intensity is calculated and measured in real time.

Fig. 3 shows the comparison between a network that uses active control resource deployment algorithm and a network that passively accepts requests for resource allocation. In the case of active control, the increase in the acceptance rate of high-priority requests can approach 1, and it has stabilized over time. As for the network that passively accepts requests for resource allocation, the degree of anti-congestion is poor, and can only be maintained between 0.8–1.0. This significant improvement confirms the effectiveness of the method based on active admission control and greatly improves the high-priority admission rate of the network.

Figure 3: Comparison of acceptance rate of high-priority requests

As shown in Fig. 4, the average ratio of the sum of the used resources of the network to the total available resources in the time unit is measured. Comparing the two utilization curves, it can be seen that the utilization of network resources using the active control algorithm is close to the situation of passive network resource allocation. That is to say, the algorithm proposed in this paper can effectively use network resources, it will not waste resources because of the emphasis on user-centered framework, and it will not reduce the effective utilization of resources because of the resource reservation in the prediction mapping stage.

Figure 4: Comparison of network resource utilization

Fig. 5 shows the user utility value using the active control resource deployment algorithm and passively accepting requests to allocate resources. Calculating the long-term total user benefits requires cumulative calculation to allocate the total revenue of k SFC computing resources. As shown in the figure, it is not difficult to find that the user utility value created by the former is significantly higher than that of the latter, and the gap is more significant over time. It shows that in the long-term operation process, under the condition of ensuring the consumption of physical network resources, the algorithm can meet the needs and preferences of the user side as much as possible, so as to achieve the purpose of maximizing the quality of service of the network to the user.

Figure 5: Comparison of created user utility

Fig. 6 shows the change trend of the average utility load ratio over time under the two schemes, the ratio between utility and load intensity can better evaluate the utilization value of the algorithm for unit load. It can be seen that compared with passive allocation, the proposed algorithm has great advantages in improving the utilization value of unit load.

Figure 6: Comparison of utility and load intensity ratio

5  Conclusion

Based on SDN and NFV technology, this paper abstracts the network to form an end-to-end and logically isolated network, realizes a user-centric framework, and proposes an active control resource deployment algorithm that maximizes user utility. In the process from receiving the SFC request to allocating actual resources for each VNF component, the controller takes the lead to consider the SFC demand on a user basis, and fully considers decision factors including priority, resource preference, and network prediction. Through flexible resource scheduling management to ensure the maximum utility provided to users. The simulation results show that, compared with the strategy of passively accepting VNF requests and allocating resources, our proposed solution performs better, can use network resources more effectively, and create greater value for network users.

Acknowledgement: This work was supported by the National Natural Science Foundation of China (61871058).

Funding Statement: The authors received no specific funding for this study.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.