CN115361284A - A deployment adjustment method for SDN-based virtual network functions - Google Patents

Abstract

The invention discloses a method for deploying and adjusting a virtual network function based on SDN. The method includes: after receiving a request for deploying a virtual network function, determining an initial deployment plan after deploying the requested virtual network function in the network; For the initial deployment plan, for the SFG composed of all SFCs in the network, traverse the physical nodes and links in it, and determine the overloaded physical nodes and links; adjust the deployment of virtual network functions for the overloaded physical nodes and links . The application of the invention can balance the load globally from the network.

Description

A deployment adjustment method for SDN-based virtual network functions

technical field

The invention relates to the field of computer technology, in particular to an SDN-based virtual network function deployment adjustment method.

Background technique

Currently, NFV has emerged as a promising technology to efficiently deploy and manage various network functions. In the NFV architecture, these network functions in the form of software are handled as virtual network functions (VNFs) and can be managed by NFV MANOs. NFV can provide services in the form of an end-to-end service function chain (SFC), which defines a specific sequence of VNFs and their logical connections, which can be embedded in a physical network in a flexible manner. In contrast to traditional middleware that relies on specialized hardware, NFV leverages commodity servers that use standard hardware. A major benefit of this evolution is that network functions can be flexibly scaled according to user traffic. For example, when traffic bursts, a group of servers can be configured to run the same VNF to process packets.

In a cloud-edge collaborative network based on software-defined networking (SDN), due to changes in network traffic, SFC needs to adjust the deployment strategy by scaling in time. Traditional SFC scaling methods are often based on a single SFC in user requests, which cannot be effective It saves costs and balances loads from the perspective of the overall network.

That is to say, the existing SFC scaling methods focus on the scaling of a single SFC, and cannot effectively optimize network performance globally. For the basic network where SFC services have been deployed, in the face of traffic bursts, scaling network functions from the perspective of a single SFC cannot efficiently ensure the utilization of the entire network resources and balance the load among network devices. At the same time, although some existing studies have predicted the peak traffic and proposed some optimization strategies, they have not proposed a specific scaling SFC deployment scheme. In addition, in the cloud-edge network environment, the scaling problem of the integrated SDN cloud-edge network structure characteristics has not been considered.

Contents of the invention

In view of this, the purpose of the present invention is to propose an SDN-based virtual network function deployment adjustment method, which can balance the load globally from the network.

Based on the above purpose, the present invention provides a deployment adjustment method based on SDN virtual network function, including:

After receiving a request to deploy a virtual network function, determine an initial deployment plan after deploying the requested virtual network function in the network;

Based on the initial deployment plan, for the SFG composed of all SFCs in the network, traverse the physical nodes and links in it, and determine the overloaded physical nodes and links;

Adjust the deployment of virtual network functions for overloaded physical nodes and links.

Wherein, the deployment and adjustment of virtual network functions for overloaded physical nodes and links specifically includes:

The overloaded physical nodes and links are composed of node sets and link sets respectively;

Carrying out deployment and adjustment of virtual network functions sequentially on each physical node in the node set according to the load rate;

The deployment and adjustment of the virtual network function is sequentially performed on each link in the link set according to the load rate.

Preferably, the deployment and adjustment of the virtual network function is sequentially performed on each physical node in the node set according to the load rate, which specifically includes:

The physical nodes in the node set are sorted from large to small according to the load rate; the sorted physical nodes are sequentially adjusted for the deployment of virtual network functions:

For the current physical node to be deployed and adjusted, determine the predecessor node and successor node of the SFC to which the physical node belongs;

Using the predecessor node as the starting node, and the successor node as the ending node; using the path between the starting node and the ending node as the path to be adjusted;

Use a tabu search algorithm to select a path with a server node that is consistent with the type of the physical node and whose load rate meets the requirements from multiple paths between the starting node and the terminating node, and adjust the virtual network function of the physical node Deploy to the server node of the selected path.

Preferably, the deployment and adjustment of the virtual network function is sequentially performed on each physical link in the link set according to the load rate, which specifically includes:

Sorting the physical links in the link set from large to small according to the load rate; and adjusting the deployment of the virtual network function on the sorted physical links in turn:

For the current physical link to be deployed and adjusted, the deployment and adjustment of m paths are performed; wherein, the deployment and adjustment process of the kth path is as follows:

The first physical node of the physical link is used as the starting node, and the k+2th physical node of the physical link is used as the terminating node; the path between the starting node and the terminating node is used as the to-be-adjusted path;

Use the tabu search algorithm to select a path with a server node that is consistent with the type of the physical node and that meets the requirements of the load rate from the multiple paths between the starting node and the terminating node, and the k+1th physical node The virtual network function is adjusted and deployed on the server node of the selected path.

Preferably, using the tabu search algorithm to select a path with a server node that is consistent with the physical node type and has a load rate that meets the requirements from multiple paths between the starting node and the terminating node, specifically including:

Based on the optimal comprehensive cost, using a tabu search algorithm to select a path with a server node consistent with the physical node type as a candidate path from among the multiple paths between the starting node and the terminating node;

For each candidate path, calculate the comprehensive cost of the entire network after adjusting and deploying the virtual network function of the physical node to the candidate path;

The virtual network function of the physical node is finally adjusted and deployed to the path with the minimum comprehensive cost in the network.

Preferably, the comprehensive cost specifically includes: load cost, service delay cost and node start-up cost.

Preferably, the network is specifically an SDN-based cloud-edge collaboration network.

The present invention also provides an electronic device, including a central processing unit, a signal processing and storage unit, and a computer program stored on the signal processing and storage unit and operable on the central processing unit, wherein the central processing unit executes the above The deployment adjustment method of the SDN-based virtual network function.

In the technical solution of the present invention, after receiving a request for deploying a virtual network function, the initial deployment plan after deploying the requested virtual network function is determined in the SDN-based network; based on the initial deployment plan, for all The SFG composed of SFCs traverses the physical nodes and links in it to determine the overloaded physical nodes and links; and adjusts the deployment of virtual network functions for the overloaded physical nodes and links. Therefore, for the SFG composed of all deployed SFCs, the overloaded nodes and links in the global network can be re-deployed and routed, and a global virtual network function deployment adjustment plan can be output; compared with the existing single SFC From the perspective of network function scaling technology, the technical solution of the present invention can efficiently ensure the utilization rate of the entire network resources and balance the load among network devices.

Further, the technical solution of the present invention also proposes an SDN-based cloud-edge collaborative network scaling cost comprehensive optimization evaluation model at peak traffic times, which is applied to the deployment adjustment scheme of the virtual network function of the present invention, and the SFG can be realized. Cost-load balancing optimizes the overall cost of the adjusted and deployed network, enables the SDN network to guarantee the service quality of SFC at traffic peaks, and balances the load globally from the network.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. Those skilled in the art can also obtain other drawings based on these drawings without creative work.

FIG. 1 is a schematic diagram of an SDN-based cloud-edge collaboration network architecture provided by an embodiment of the present invention;

FIG. 2 is a flowchart of a method for deploying and adjusting an SDN-based virtual network function provided by an embodiment of the present invention;

FIG. 3 is a flow chart of a method for sequentially performing deployment and adjustment of virtual network functions on physical nodes according to an embodiment of the present invention;

FIG. 4 is a flow chart of a specific method for deploying and adjusting a virtual network function on a current physical node provided by an embodiment of the present invention;

FIG. 5 is a flowchart of a method for sequentially performing deployment and adjustment of virtual network functions on physical links according to an embodiment of the present invention;

FIG. 6 is a flow chart of a specific method for deploying and adjusting primary paths provided by an embodiment of the present invention;

FIG. 7 is a schematic diagram of an example of SFG deployment during traffic peaks provided by an embodiment of the present invention;

Figures 8, 9, and 10 are schematic diagrams comparing the experimental results of various deployment adjustment algorithms provided by the embodiments of the present invention;

FIG. 11 is a schematic diagram of a hardware structure of an electronic device provided by an embodiment of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be described in further detail below in conjunction with specific embodiments and with reference to the accompanying drawings.

It should be noted that, unless otherwise defined, the technical terms or scientific terms used in the embodiments of the present invention shall have the usual meanings understood by those skilled in the art to which the present disclosure belongs. "First", "second" and similar words used in the present disclosure do not indicate any order, quantity or importance, but are only used to distinguish different components. "Comprising" or "comprising" and similar words mean that the elements or items appearing before the word include the elements or items listed after the word and their equivalents, without excluding other elements or items. Words such as "connected" or "connected" are not limited to physical or mechanical connections, but may include electrical connections, whether direct or indirect. "Up", "Down", "Left", "Right" and so on are only used to indicate the relative positional relationship. When the absolute position of the described object changes, the relative positional relationship may also change accordingly.

In order to solve the above problems, the inventors of the present invention provide a global SFG scaling method in a multi-SFC scenario. Considering the SFG composed of all deployed SFCs in the network, the overloaded nodes and Link re-deployment and routing, and output a SFG scaling solution, that is, a global virtual network function deployment adjustment solution. Compared with the existing technology for network function scaling from the perspective of a single SFC, the technical solution of the present invention can efficiently Ensure the utilization of the entire network resources and balance the load among network devices.

More preferably, the technical solution of the present invention also proposes an SDN cloud-edge collaborative network traffic scaling cost comprehensive optimization evaluation model, which is applied to the above-mentioned global SFG scaling solution, which can realize SFG cost-load balancing The scaling deployment algorithm optimizes the overall cost of the adjusted and deployed network, enables the SDN network to guarantee the service quality of SFC at traffic peaks, and balances the load globally from the network.

The technical solutions of the embodiments of the present invention will be described in detail below in conjunction with the accompanying drawings.

The SDN-based cloud-edge collaboration network architecture is shown in Figure 1, including the cloud layer, edge layer, and terminal layer. The cloud layer (Cloud Layer) includes cloud server (Cloud Server) nodes and router (Router) nodes, the edge layer (EdgeLayer) includes edge server (Edge Server) and router (Router) nodes, and the terminal layer (Terminal Layer) includes IoT access and user terminals. The user requests generated at the terminal layer and the basic information of the cloud-edge network are used as the input of the NFV management orchestrator. Multiple requests can form an SFG based on instance sharing, and NFV MANO outputs the deployment strategy of the corresponding SFG. In this way, network service deployment can be completed by allocating corresponding computing and communication resources to the network service.

In the technical solution of the present invention, a network model, an SFG model, a flow change evaluation model, a time delay model and an optimization problem model under the SFC scene are established.

The network model reflects the information of the physical network and is defined as follows:

Define the base network of the SDN-based cloud-edge collaborative network as an undirected graph G(N,E), where N is a physical node set, N={NS ^SV ,N ^RT }={n ₁ ,n ₂ ,..., n _|N| }, E is a physical link set, E={e ₁ , e ₂ ,...,e _|E| }.

Where N ^SV ={Ν ^E , N ^C }, Ν ^E is the edge server node set, and N ^C is the cloud server node set.

表示，其中

是该物理节点总共的计算资源，

表示该节点剩余的计算资源，pr_i表示该节点的处理数据包的能力，actc_i表示启用当前节点所的开启成本。type_i表示该节点的类型。The i-th physical node n _i in N can use tuples

said, among them

is the total computing resources of the physical node,

Indicates the remaining computing resources of the node, _pri indicates the ability of the node to process data packets, and actc _i indicates the activation cost of the current node. type _i indicates the type of the node.

pr_i＝0，因此不承载VNF。When n _i ∈ N ^RT is a routing node, type _i = 0, indicating that the routing node has no server,

_pri = 0, so no VNF is carried.

When n _i is an edge server node, type _i =1, n _i ∈N ^E ∈NS ^SV .

When n _i is a cloud server node, type _i = 2, n _i ∈ N ^C ∈ N ^SV .

Compared with edge server nodes, cloud server nodes have more computing resources and data processing capabilities.

E={E ^EE , E ^EC , E ^CC } represents the link set between nodes in the entire network, E ^EE represents the link set between edge server nodes, and E ^EC represents the link set between cloud server nodes and edge server nodes A collection of roads, and E ^CC represents a collection of links between cloud server nodes.

表示，其中

表示该物理链路总共的带宽资源，

表示该链路剩余的带宽资源，d_j表示链路e_j的传播时延。e_j∈E^EE时，链路在边缘节点之间，链路带宽小，传播时延小；e_j∈E^EC时，链路连接边缘节点和云服务器节点，链路有较大的带宽和较大的传播时延；e_j∈E^CC时，链路连接不同的云服务器节点，有大的链路带宽和小的传播时延。注意，e_j可以写成

其中i₁,i₂表示链路e_j连接的两个物理节点的序号。同理，

tuple per physical link

said, among them

Indicates the total bandwidth resources of the physical link,

Indicates the remaining bandwidth resources of the link, and d _j indicates the propagation delay of the link e _j . When e _j ∈ E ^EE , the link is between the edge nodes, the link bandwidth is small, and the propagation delay is small; when e _j ∈ E ^EC , the link connects the edge node and the cloud server node, the link has a large bandwidth and Larger propagation delay; when e _j ∈ E ^CC , the link connects different cloud server nodes, with large link bandwidth and small propagation delay. Note that e _j can be written as

Among them, i ₁ and i ₂ represent the sequence numbers of the two physical nodes connected by the link e _j . In the same way,

Combined with the above network model, two variables nlr and elr are defined to describe the load rate of physical nodes and physical links, respectively, as shown in formulas 1 and 2, so as to evaluate the load of the entire network.

Further, the load rate of the entire network is shown in formula 3:

The SFG model reflects the information of the virtual network and is defined as follows:

是虚拟节点集，表示网络功能组件，

是虚拟链路集，表示业务流量路径，snum表示SFG包含的SFC数量。集合RD＝{rd₁,rd₂,...,rd_snum}记录G^V中每条SFC的最大容忍时延。同理，第s条SFCs可以表示成

Describe the SFC business as a directed acyclic graph, G ^V (N ^V , E ^V , snum, RD), and the graph consists of several SFCs.

is a set of virtual nodes representing network functional components,

is a virtual link set, indicating the service traffic path, and snum indicates the number of SFCs included in the SFG. The set RD={rd ₁ ,rd ₂ ,...,rd _snum } records the maximum tolerable time delay of each SFC in G ^V. Similarly, the s-th SFCs can be expressed as

描述，其中v_i表示该虚拟节点的VNF类型，

表示该虚拟节点所需的计算资源，P_i表示该虚拟节点待处理的数据包大小，

表示该虚拟节点

所属的SFC集合。The i-th virtual node consists of the tuple

description, where v _i represents the VNF type of the virtual node,

Indicates the computing resources required by the virtual node, _Pi indicates the size of the data packet to be processed by the virtual node,

represents the virtual node

The SFC collection to which it belongs.

描述，其中

分别表示

的源虚拟节点和目标虚拟节点。

表示

所需的带宽资源，

表示流量经过

的SFC集合。与物理链路类似，虚拟链路也可以由其两端的节点表示，因此

jth virtual link routing tuple

description, where

Respectively

The source virtual node and target virtual node.

express

required bandwidth resources,

Indicates that traffic passes through

The SFC collection. Similar to physical links, virtual links can also be represented by nodes at both ends, so

来描述虚拟网络到物理网络的映射情况。

表示虚拟节点

部署在物理节点n_i'上；

表示虚拟链路

部署在物理链路e_j'上。假设虚拟节点到服务器节点为1到1映射，虚拟链路到物理链路是m到n映射。Additionally, two binary variables are defined

To describe the mapping from virtual network to physical network.

Represents a virtual node

Deployed on the physical node n _i' ;

Represents a virtual link

Deployed on the physical link e _j' . It is assumed that virtual nodes are mapped to server nodes from 1 to 1, and virtual links to physical links are mapped from m to n.

和部署信息

可以获得每条SFC部署信息。SFCs部署的物理节点集为

物理链路集为

对

满足如下公式4：Combining SFC information corresponding to nodes and links

and deployment information

The deployment information of each SFC can be obtained. The set of physical nodes deployed by SFCs is

The physical link set is

right

Satisfies the following formula 4:

The packet size sequence is shown in Equation 5:

Routing nodes do not process VNFs, and the size of packets carried by physical nodes in _Ns is shown in Equation 6:

The traffic change evaluation model can reflect the load information of the traffic peak, which is defined as follows:

的计算资源请求为

虚拟链路

的带宽资源请求为

设

则虚拟节点

的流量变化如公式7所示：When defining traffic peaks, virtual nodes

The computing resource request for

virtual link

The bandwidth resource request for

Assume

then the virtual node

The flow change of is shown in Equation 7:

的流量变化如公式8所示：virtual link

The flow change of is shown in Equation 8:

时，当前部署的服务器有能力承载突发流量所需的新VNF实例，选择进行VNF实例的垂直缩放，否则只能进行水平缩放，在新的服务器节点部署n₁实例并分配路径。同理，

时，进行路由的垂直缩放，在原有路径上请求新的带宽，否则进行路由的水平缩放。when

When the currently deployed server is capable of carrying the new VNF instance required by the burst traffic, choose to perform vertical scaling of the VNF instance, otherwise, only horizontal scaling can be performed, and n ₁ instances are deployed on the new server node and paths are allocated. In the same way,

When , the vertical scaling of the route is performed, and new bandwidth is requested on the original path, otherwise, the horizontal scaling of the route is performed.

When the traffic peaks, the node load rate is shown in Formula 9:

When the traffic peaks, the link load rate is shown in Equation 10:

When the traffic peaks, the load rate of the entire network is shown in Formula 11:

表示流量峰值时，整个网络的节点负载率；

表示流量峰值时，整个网络的链路负载率；|N^SV|表示整个网络的服务器节点的数量；|E|表示整个网络的物理链路的数量。in,

Indicates the node load rate of the entire network when the traffic peaks;

Indicates the link load rate of the entire network when traffic peaks; | ^NSV | indicates the number of server nodes in the entire network; |E| indicates the number of physical links in the entire network.

The total start-up cost of deployed virtual nodes in the network, that is, servers with deployed virtual network functions, is shown in Equation 12:

表示虚拟节点

与物理节点n_i的映射关系，

表示

部署于物理节点n_i；

表示

没有部署于物理节点n_i；Among them, actc _i represents the opening cost of the i-th server,

Represents a virtual node

The mapping relationship with the physical node n _i ,

express

Deployed on physical node n _i ;

express

Not deployed on physical node n _i ;

The delay model is defined as follows:

The end-to-end delay of SFC includes three parts, propagation delay, transmission delay, queuing and processing delay.

1. Propagation delay: It is related to the length of the physical link and is determined by d _j . The sum of propagation delays for SFCs is given in Equation 13:

2. Transmission delay: The transmission delay of SFCs refers to the transmission time of the data packet from the server to the output link, which is related to the size of the data packet and the requested bandwidth. The calculation formula is shown in formula 14:

3. Queuing and processing delay: The processing delay of the VNF of SFCs is related to the data packet size, node processing capability and requested computing resources, and can be calculated according to formula 15:

部署在物理节点

上。

VNF的排队时延等于待处理数据包达到后的等待处理时间。将接入点的服务器建模为M/M/1队列，到达服务器

进行计算的任务遵循泊松过程，到达率为λ。因此服务器

完成VNF的平均时延

(包括排队和服务时间)可以表示为公式16所示：Among them, the virtual node

Deployed on physical nodes

superior.

The queuing delay of the VNF is equal to the waiting processing time after the data packets to be processed arrive. Model the server of the access point as an M/M/1 queue, reaching the server

The tasks performing the computation follow a Poisson process with an arrival rate λ. so the server

Average latency to complete the VNF

(including queuing and service time) can be expressed as shown in formula 16:

因此，SFCs的排队及处理时延可以表示为公式17：in,

Therefore, the queuing and processing delay of SFCs can be expressed as Equation 17:

In summary, the total delay of SFCs is calculated as Equation 18:

delay _s = ppd _s + trd _s + qpd _s . (Formula 18)

The optimization problem model is defined as follows:

The optimization goal of this paper is to minimize the comprehensive cost of load cost, service delay cost and node start-up cost in the network after deployment adjustment (SFC scaling), and the comprehensive cost is expressed as formula 19:

为流量峰值时，整个网络的负载率；rd_s表示SFCs的最大容忍时延；

表示SFCs的时延率；

表示所有SFC的时延率之和；snum表示SFG包含的SFC数量；actc表示所述网络中已部署虚拟网络功能的服务器的开启总成本；

表示所述网络中所有服务器的开启总成本；ρ为接受率惩罚值，由流量峰值导致业务无法部署造成，可根据如下公式20计算得到：Wherein, ω ₁ , ω ₂ , and ω ₃ are user-defined parameters, and ω ₁ +ω ₂ +ω ₃ =1.

is the load rate of the entire network when traffic peaks; rd _s represents the maximum tolerable delay of SFCs;

Indicates the delay rate of SFCs;

Indicates the sum of the delay rates of all SFCs; snum indicates the number of SFCs contained in the SFG; actc indicates the total cost of starting the server with the deployed virtual network function in the network;

Indicates the total cost of opening all servers in the network; ρ is the acceptance rate penalty value, which is caused by the failure of service deployment due to traffic peaks, and can be calculated according to the following formula 20:

Among them, total_sfc indicates the number of all SFCs, and accepted_sfc indicates the number of successfully deployed SFCs.

In order to solve the scaling problem of VNF instances, that is, the deployment adjustment problem of virtual network functions, some constraints need to be satisfied. First, on any physical node or physical link, the sum of the resources required by the deployed virtual nodes or links does not exceed its total resources, as shown in formulas 21 and 22:

Then, the mapping between server nodes and virtual nodes is 1-to-1, as shown in formulas 23 and 24:

In addition, the delay of all SFCs cannot exceed the maximum tolerated delay, as shown in Equation 25:

In summary, the optimization problem model in this paper can be summarized as:

s.t.:

The present invention provides a method for deploying and adjusting an SDN-based virtual network function, the process of which is shown in Figure 2, including the following steps:

Step S201: After receiving a request for deploying a virtual network function, determine an initial deployment scheme after deploying the requested virtual network function in the network.

Specifically, after receiving the request for deploying the virtual network function sent by the user equipment, determine the information of the source node and the multiple virtual network functions to be deployed from the request; and then adopt the existing method, based on A deployment scheme after deploying the requested multiple virtual network functions is determined in the SDN network as an initial deployment scheme.

Step S202: Based on the initial deployment scheme, for the SFG composed of all SFCs in the network, traverse the physical nodes and physical links therein, and determine the overloaded physical nodes and physical links.

Specifically, based on the initial deployment scheme, for the SFG composed of all SFCs in the network, traverse the physical nodes and physical links in it, and determine the overloaded physical nodes and physical links;

For example, a physical node whose load rate exceeds a node load degree threshold α is determined as an overloaded physical node; a physical link whose load rate exceeds a link load degree threshold β is determined as an overloaded physical link. Wherein, α and β can be set empirically by those skilled in the art, such as setting α=β=0.7.

The overloaded physical nodes form a node set, and the overloaded physical links form a link set.

Step S203: adjusting the deployment of virtual network functions for overloaded physical nodes and physical links.

In this step, the deployment and adjustment of the virtual network function is sequentially performed on each physical node in the node set according to the load rate; and the deployment and adjustment of the virtual network function is performed on each physical link in the link set according to the load rate.

Specifically, according to the load rate, each physical node in the node set sequentially performs a method of deploying and adjusting the virtual network function, as shown in Figure 3, including the following steps:

Step S301: sort each physical node in the node set according to the load rate from large to small;

Step S302: Perform deployment and adjustment of virtual network functions on the sorted physical nodes in sequence.

In this step, the sorted physical nodes are adjusted according to the order of load ratio from large to small, and the deployment and adjustment of virtual network functions are carried out sequentially; for the physical nodes currently to be deployed and adjusted, the specific method of performing deployment and adjustment of virtual network functions is as follows: The process is shown in Figure 4, including the following sub-steps:

Sub-step S401: determine the predecessor node and successor node of the SFC to which the physical node belongs;

Sub-step S402: use the predecessor node as the start node, and the successor node as the end node; use the path between the start node and the end node as the path to be adjusted;

Sub-step S403: use the tabu search algorithm to select a path with a server node that is consistent with the type of the physical node and whose load rate meets the requirements from the multiple paths between the start node and the end node, and select the path of the server node of the physical node The virtual network function is adjusted and deployed on the server node of the selected path.

In this sub-step, when selecting a path, a better implementation method can be adopted:

Based on the optimal comprehensive cost, use a tabu search algorithm to select a path with a server node consistent with the physical node type as a candidate path from multiple paths between the starting node and the terminating node; for each candidate path, After the virtual network function of the physical node is adjusted and deployed to the candidate path, the comprehensive cost of the entire network is calculated; the virtual network function of the physical node is finally adjusted and deployed to the path with the smallest comprehensive cost of the network.

Wherein, the comprehensive cost of the network may include load cost in the network, service delay cost and node start-up cost;

In the case that the network is specifically the above-mentioned SDN-based cloud-edge collaborative network, the comprehensive cost of the network can be calculated according to the above formula 19; that is, according to the information of the base network of the network (that is, the physical network information), the information of SFG composed of all SFCs in the network (that is, the information of the virtual network), the mapping information from the virtual network to the physical network, the load information of the traffic peak, the delay of all SFCs in the network, and the server’s Turn on the cost to calculate the comprehensive cost of the network in the current deployment situation.

Specifically, according to the load rate, each physical link in the link set sequentially performs a method for deploying and adjusting the virtual network function, as shown in Figure 5, including the following steps:

Step S501: sort each physical link in the link set according to the load rate from large to small;

Step S502: Perform deployment and adjustment of virtual network functions on the sorted physical links in sequence.

In this step, the sorted physical links are adjusted according to the order of load rate from large to small, and the deployment of virtual network functions is carried out in sequence;

For the physical link currently to be deployed and adjusted, the deployment adjustment of the path is performed m times; wherein, m=L-2, L is the total number of physical nodes in the physical link; wherein, the deployment adjustment process of the kth path, As shown in Figure 6, the following sub-steps are included:

Sub-step S601: taking the first physical node of the link as the starting node, and taking the k+2th physical node of the link as the ending node;

Sub-step S602: use the path between the start node and the end node as the path to be adjusted;

Sub-step S603: use the tabu search algorithm to select a path with a server node that is consistent with the physical node type and has a load rate that meets the requirements from the multiple paths between the start node and the end node, and set the k+1th The virtual network function of each physical node is adjusted and deployed to the server node of the selected path.

In this sub-step, when selecting a path, a better implementation method can be adopted:

Based on the optimal comprehensive cost, use a tabu search algorithm to select a path with a server node consistent with the physical node type as a candidate path from multiple paths between the starting node and the terminating node; for each candidate path, After the virtual network function of the physical node is adjusted and deployed to the candidate path, the comprehensive cost of the entire network is calculated; the virtual network function of the physical node is finally adjusted and deployed to the path with the smallest comprehensive cost of the network.

Wherein, the comprehensive cost of the network may include load cost in the network, service delay cost and node start-up cost;

In the case that the network is specifically the above-mentioned SDN-based cloud-edge collaborative network, the comprehensive cost of the network can be calculated according to the above formula 19; that is, according to the information of the base network of the network (that is, the physical network information), the information of SFG composed of all SFCs in the network (that is, the information of the virtual network), the mapping information from the virtual network to the physical network, the load information of the traffic peak, the delay of all SFCs in the network, and the server’s Turn on the cost to calculate the comprehensive cost of the network in the current deployment situation.

For example, Figure 7 shows an instance of SFG deployment during traffic peaks. The upper part of Figure 7 shows the deployment of SFG without deployment adjustment (horizontal scaling), assuming α=0.7, the overloaded server nodes at this time include edge server n ₁ and cloud servers n ₃ , n ₇ , and the overloaded Physical links are partial links that pass through these servers. In order to balance the load of the network, some instances carried by n ₁ , n ₃ , and n ₇ are migrated to new server node deployments during deployment adjustment. Specifically, two instances of VNF1 carried by n ₁ are deployed to edge server n ₈ , one instance of VNF3 carried by n ₃ is deployed to cloud server n ₁₀ , and two instances of VNF6 carried by n ₇ are deployed to cloud server n ₉ . At the same time, adjust the link deployment related to the above nodes. In this way, the overloaded node and link resources are partially released, and the local overload situation of the network is alleviated.

In order to verify the technical effect of the technical solution of the present invention, we used a network topology consisting of 40 physical nodes, 20 of which are cloud servers, 10 are edge servers, and 10 router nodes, simulating the CEC network architecture. The nodes in the network are connected by 204 physical links. In our simulation, SFC requests will be generated according to a certain arrival frequency, and λ=4 at the traffic peak. In addition, we assume that each SFC is composed of 2 to 5 different VNFs, the required bandwidth of each VNF is set to 700 to 900 Mbps, and the delay limit of each VNF is set to 100 ms to 200 ms. For our deployed algorithm based on tabu search, the tabu table size is 20, the number of iterations is 50, and ε = 0.3 for the ε-greedy method is set. For the optimization objective in this paper, ω ₁ =0.7, ω ₂ =0.2, and ω ₃ =0.1 are default configurations. Node and link load threshold α=β=0.7.

The algorithm of the technical solution of the present invention is SFG-Scaling, which is a cost-load balancing scaling deployment algorithm based on SFG;

The prior art solution algorithm SFC-Scaling is a cost- and load-oriented scaling deployment algorithm based on a single SFC each time.

The prior art solution algorithm SFC-LEB is a load- and energy-consumption-oriented balanced deployment algorithm, aiming at optimizing the load while reducing changes to the network topology caused by scaling during traffic peaks.

The prior art solution algorithm SFC-DA is a delay-aware SFC deployment algorithm, and the load is unbalanced during traffic peaks.

This paper compares the performance of the above algorithms from three aspects: SFC acceptance rate, service delay, and comprehensive scaling cost.

(1) Define the SFC acceptance rate by dividing the number of successfully deployed SFCs by the total number of SFCs requested by users. As shown in Figure 8, the algorithm proposed in this paper can guarantee a high acceptance rate when the number of services is large. Both SFC-Scaling and SFC-LEB will balance the load of the network to ensure the smooth deployment of subsequent services. Therefore, as the number of services increases, the acceptance rate of the two decreases but is still above 70%. SFC-LEB does not consider the optimization of delay, and there may be SFCs that fail to be deployed due to service timeouts, so the acceptance rate is lower than that of SFC-Scaling. SFC-DA does not scale the deployment when the traffic peaks. A large number of services fail to be deployed due to insufficient resources of a single server node or a single link, and the acceptance rate of SFC is the worst.

(2) The service delay is defined in the delay model, and the result is shown in Fig. 9 . In terms of service latency, SFC-Scaling performs best. Compared with SFG-Scaling, which optimizes multiple SFCs together, SFC-Scaling tends to deploy each SFC on a path with lower latency. At the same time, the SFG-Scaling algorithm proposed in this paper is the second best. SFC-DA is a delay-optimized deployment algorithm. The critical path with the shortest delay is occupied in the early stage, so the delay is low. However, the SFC-DA algorithm does not scale the SFC, so with the increase of services, the nodes and links on the critical path can no longer carry more SFC, so the deployment needs to be completed through a longer path, resulting in a large amount of delay. The SFC-LEB algorithm does not pay attention to the delay performance of the service, so the delay is the highest.

(3) We define the comprehensive scaling cost as the weighted calculation value of network load, service delay, node opening cost and acceptance rate, which is also the optimization goal of this paper. It can be seen from Figure 10 that the algorithm proposed in this paper has the lowest average comprehensive deployment cost. The algorithm proposed in this paper is oriented to multiple SFGs for one request, and it has a better performance in terms of network load rate when compared with the single SFC scaling algorithm. Compared with the load-energy balancing SFC deployment algorithm, the SFC-Scaling algorithm has more considerations on the delay cost, so the overall cost is lower. The delay-aware SFC deployment algorithm cannot alleviate local overload during traffic peaks, so the deployment cost is high. As time increases, the SFC-DA algorithm has no nodes that can carry more VNFs, so the growth of comprehensive deployment costs tends to be flat.

FIG. 11 shows a schematic diagram of a more specific hardware structure of an electronic device provided by this embodiment. The device may include: a processor 1010 , a memory 1020 , an input/output interface 1030 , a communication interface 1040 and a bus 1050 . The processor 1010 , the memory 1020 , the input/output interface 1030 and the communication interface 1040 are connected to each other within the device through the bus 1050 .

The processor 1010 may be implemented by a general-purpose CPU (Central Processing Unit, central processing unit), a microprocessor, an application specific integrated circuit (Application Specific Integrated Circuit, ASIC), or one or more integrated circuits, and is used to execute related A program to implement the method for adjusting the deployment of the virtual network function provided by the embodiment of this specification.

The memory 1020 may be implemented in the form of ROM (Read Only Memory, read only memory), RAM (Random Access Memory, random access memory), static storage device, dynamic storage device, and the like. The memory 1020 can store operating systems and other application programs. When implementing the technical solutions provided by the embodiments of this specification through software or firmware, the relevant program codes are stored in the memory 1020 and invoked by the processor 1010 for execution.

The input/output interface 1030 is used to connect the input/output module, and can be connected with a nonlinear receiver to receive information from the nonlinear receiver to realize information input and output. The input/output/module can be configured in the device as a component (not shown in the figure), or can be externally connected to the device to provide corresponding functions. The input device may include a keyboard, mouse, touch screen, microphone, various sensors, etc., and the output device may include a display, a speaker, a vibrator, an indicator light, and the like.

The communication interface 1040 is used to connect a communication module (not shown in the figure), so as to realize the communication interaction between the device and other devices. The communication module can realize communication through wired means (such as USB, network cable, etc.), and can also realize communication through wireless means (such as mobile network, WIFI, Bluetooth, etc.).

Bus 1050 includes a path that carries information between the various components of the device (eg, processor 1010, memory 1020, input/output interface 1030, and communication interface 1040).

It should be noted that although the above device only shows the processor 1010, the memory 1020, the input/output interface 1030, the communication interface 1040 and the bus 1050, in the specific implementation process, the device may also include other components. In addition, those skilled in the art can understand that the above-mentioned device may only include components necessary to implement the solutions of the embodiments of this specification, and does not necessarily include all the components shown in the figure.

In the technical solution of the present invention, after receiving a request for deploying a virtual network function, determine the initial deployment plan after deploying the requested virtual network function in the network; based on the initial deployment plan, for the SFG composed of all SFCs in the network, traverse The physical nodes and links among them determine the overloaded physical nodes and links; and adjust the deployment of virtual network functions for the overloaded physical nodes and links. Therefore, for the SFG composed of all deployed SFCs, the overloaded nodes and links in the global network can be re-deployed and routed, and a global virtual network function deployment adjustment plan can be output; compared with the existing single SFC From the perspective of network function scaling technology, the technical solution of the present invention can efficiently ensure the utilization rate of the entire network resources and balance the load among network devices.

Further, the technical solution of the present invention also proposes an SDN-based cloud-edge collaborative network scaling cost comprehensive optimization evaluation model at peak traffic times, which is applied to the deployment adjustment scheme of the virtual network function of the present invention, and the SFG can be realized. Cost-load balancing optimizes the overall cost of the adjusted and deployed network, enables the SDN network to guarantee the service quality of SFC at traffic peaks, and balances the load globally from the network.

The computer-readable medium in this embodiment includes permanent and non-permanent, removable and non-removable media, and information storage can be realized by any method or technology. Information may be computer readable instructions, data structures, modules of a program, or other data. Examples of computer storage media include, but are not limited to, phase change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read only memory (ROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), Flash memory or other memory technology, Compact Disc Read-Only Memory (CD-ROM), Digital Versatile Disc (DVD) or other optical storage, Magnetic tape cartridge, tape magnetic disk storage or other magnetic storage device or any other non-transmission medium that can be used to store information that can be accessed by a computing device.

Those of ordinary skill in the art should understand that: the discussion of any of the above embodiments is exemplary only, and is not intended to imply that the scope of the present disclosure (including claims) is limited to these examples; under the idea of the present invention, the above embodiments or Combinations between technical features in different embodiments are also possible, steps may be carried out in any order, and there are many other variations of the different aspects of the invention as described above, which are not presented in detail for the sake of brevity.

In addition, well-known power/ground connections to integrated circuit (IC) chips and other components may or may not be shown in the provided figures, for simplicity of illustration and discussion, and so as not to obscure the present invention. . Furthermore, devices may be shown in block diagram form in order to avoid obscuring the invention, and this also takes into account the fact that details regarding the implementation of these block diagram devices are highly dependent on the platform on which the invention is to be implemented (i.e. , these details should be well within the understanding of those skilled in the art). Where specific details (eg, circuits) have been set forth to describe example embodiments of the invention, it will be apparent to those skilled in the art that other embodiments may be implemented without or with variations from these specific details. Implement the present invention down. Accordingly, these descriptions should be regarded as illustrative rather than restrictive.

Although the invention has been described in conjunction with specific embodiments of the invention, many alternatives, modifications and variations of those embodiments will be apparent to those of ordinary skill in the art from the foregoing description. For example, other memory architectures such as dynamic RAM (DRAM) may use the discussed embodiments.

Embodiments of the present invention are intended to embrace all such alterations, modifications and variations that fall within the broad scope of the appended claims. Therefore, any omissions, modifications, equivalent replacements, improvements, etc. within the spirit and principles of the present invention shall be included within the protection scope of the present invention.

Claims (10)

1. A deployment adjustment method for virtual network functions is characterized by comprising the following steps:

after a request for deploying a virtual network function is received, determining an initial deployment scheme after the requested virtual network function is deployed in the SDN-based network;

based on an initial deployment scheme, aiming at SFGs formed by all SFCs in the network, traversing physical nodes and links in the SFGs, and determining overloaded physical nodes and links;

and carrying out deployment adjustment on virtual network functions aiming at the overloaded physical nodes and links.

2. The method according to claim 1, wherein the performing deployment adjustment of virtual network functions for overloaded physical nodes and links specifically comprises:

respectively forming overloaded physical nodes and links into a node set and a link set;

carrying out deployment adjustment of virtual network functions on all physical nodes in the node set in sequence according to the load rate;

and carrying out deployment adjustment of virtual network functions on all links in the link set according to the load rate.

3. The method according to claim 2, wherein the sequentially performing deployment adjustment of the virtual network function on the physical nodes in the node set according to the load factor specifically includes:

sorting all physical nodes in the node set from large load rate to small load rate; and sequentially carrying out deployment adjustment of the virtual network functions on the sequenced physical nodes:

for a physical node to be deployed and adjusted currently, determining a precursor node and a subsequent node of an SFC to which the physical node belongs;

taking the precursor node as an initial node and taking the successor node as a termination node; taking a path between the starting node and the terminating node as a path to be adjusted;

and selecting a path of the server node which is consistent with the type of the physical node and meets the requirement of the load rate from a plurality of paths between the starting node and the terminating node by using a tabu search algorithm, and adjusting and deploying the virtual network function of the physical node to the server node of the selected path.

4. The method according to claim 2, wherein the sequentially performing deployment adjustment of the virtual network function on the physical links in the link set according to the load factor specifically includes:

sorting all physical links in the link set from large to small according to load rates; and sequentially carrying out deployment adjustment of the virtual network function on the sequenced physical links:

carrying out deployment adjustment on the paths for m times for the physical link to be currently subjected to deployment adjustment; wherein m = L-2, L is the total number of physical nodes in the physical link; the deployment adjustment process of the k path is as follows:

taking the 1 st physical node of the physical link as an initial node and taking the (k + 2) th physical node of the physical link as a termination node; taking a path between the starting node and the terminating node as a path to be adjusted;

and selecting a path with a server node which is consistent with the type of the physical node and meets the requirement of the load rate from a plurality of paths between the starting node and the terminating node by using a tabu search algorithm, and adjusting and deploying the virtual network function of the (k + 1) th physical node to the server node of the selected path.

5. The method according to claim 3 or 4, wherein the using tabu search algorithm selects a path having a server node with a load rate meeting requirements and the type of the physical node from a plurality of paths between the start node and the end node, and specifically comprises:

based on the optimal comprehensive cost, selecting a path with a server node with the same type as the physical node from a plurality of paths between the starting node and the terminating node by using a tabu search algorithm as a candidate path;

aiming at each candidate path, calculating the comprehensive cost of the whole network after the virtual network function of the physical node is adjusted and deployed to the candidate path;

and finally adjusting and deploying the virtual network function of the physical node to the path with the minimum comprehensive cost of the network.

6. The method according to claim 5, wherein the composite cost specifically comprises: load cost, traffic delay cost, and node turn-on cost.

7. Method according to claim 6, wherein the network is in particular a SDN based cloud edge collaborative network.

8. The method of claim 7, wherein the overall cost is calculated as shown in equation 19:

wherein, ω is ₁ ，ω ₂ ，ω ₃ Is a custom parameter, ω ₁ +ω ₂ +ω ₃ =1, ρ is the acceptance rate penalty value;

when the flow is at the peak value, the load rate of the whole network is increased;

represents the sum of the delay rates of all SFCs; snum represents the number of SFCs contained in the SFG; act c represents a total startup cost of servers in the network that have deployed virtual network functions;

representing the total cost of switching on all servers in the network.

9. The method of claim 8, wherein the peak traffic flow rate is the load rate of the entire network

Specifically, as calculated by equation 11:

wherein,

when the flow peak value is expressed, the node load rate of the whole network is represented;

when the flow peak value is expressed, the link load rate of the whole network is represented; | N ^SV L represents the number of server nodes of the entire network; | E | represents the number of physical links of the entire network.

10. An electronic device comprising a central processing unit, a signal processing and storage unit, and a computer program stored on the signal processing and storage unit and executable on the central processing unit, characterized in that the central processing unit implements the method according to any of claims 1-9 when executing the program.

Images