CN109379230B

CN109379230B - A service function chain deployment method based on breadth-first search

Info

Publication number: CN109379230B
Application number: CN201811324613.5A
Authority: CN
Inventors: 徐祝; 孙罡; 虞红芳
Original assignee: University of Electronic Science and Technology of China
Current assignee: University of Electronic Science and Technology of China
Priority date: 2018-11-08
Filing date: 2018-11-08
Publication date: 2020-05-22
Anticipated expiration: 2038-11-08
Also published as: CN109379230A

Abstract

The invention discloses a service function chain deployment method based on breadth-first search. The deployment algorithm provided by the invention does not restrict the scale, the sparse characteristic and the like of the network, so that the method can be suitable for most networks. The algorithm provided by the invention realizes the service function chain deployment based on the shortest path between the service terminal and the user, so that the bandwidth cost and the time delay consumed by the deployment can be reduced, and the deployment cost can be reduced. When the node is selected, the node load rate and the link load rate are considered, the optimal selection factor is designed to reflect the influence of the load rate on the node selection, and the load balance is optimized.

Description

Service function chain deployment method based on breadth-first search

Technical Field

The invention relates to the technical field of virtual networks, in particular to a service function chain deployment method based on breadth-first search.

Background

Network Function Virtualization (NFV) enables functions of network equipment to be independent of special hardware no longer through software and hardware decoupling and function abstraction, hardware resources can be fully and flexibly shared, and rapid development and deployment of new services are achieved. Based on actual traffic demands, multiple virtual network functions are grouped into Service Function Chains (SFCs) in a particular order and then deployed into the network to provide services to users.

With the increase of network users and the development of services, the telecommunication industry needs to store and transmit a large amount of data, and the hardware type network cannot bear the impact of the applications. In most conventional networks, each network function requires separate hardware and establishes a service chain to support applications on new network devices and integrate them into a cumbersome and error-prone sequence. These specialized hardware are closed and expensive, causing not only network rigidity, but also increased network capital and operating expenses. Network function virtualization can implement network function deployment in a shorter time by running virtual machines that perform various functions. Whenever a user requires a new network function, the service provider may automatically start a virtual machine that supports that function. Not only can the deployment time be reduced, but also the capital expenditure cost and the operating cost are reduced.

Deploying service function chains in a network is a hot spot of current research, and there have been many studies. For example, researchers have studied the deployment problem of a two-step service function chain with nodes and links considered separately, and proposed an algorithm based on greedy and simulated annealing to deploy the service function chain to reduce the deployment latency and bandwidth. This algorithm can reduce the overall deployment cost, but the authors do not consider node and link resources jointly. Researchers have modeled the deployment problem of service function chains as a mixed integer linear programming problem to optimize virtual network function deployment while satisfying constraints (e.g., bandwidth).

With the expansion of network size and the increase of requests for service function chains, how to guarantee the successful deployment of service function chains is a huge challenge. Many studies show that the service function chain deployment problem is an NP-Hard problem, a polynomial time algorithm does not exist to solve the problem, and an efficient heuristic algorithm is usually adopted to obtain an approximate solution. In addition, reducing the cost (e.g., delay, bandwidth) consumed by the service function chain deployment is another challenge, and is an important index for evaluating the deployment algorithm.

At present, there have been some studies on service function chain deployment methods, such as greedy and simulated annealing algorithms. The method mainly includes the steps that a greedy algorithm is used for finding out appropriate nodes to deploy VNFs, then the shortest path is found among the deployed nodes, and finally a scheme obtained by optimizing the greedy algorithm through a simulated annealing algorithm is used. Although the above method can implement deployment of service function chain, it does not consider node and link resources of the underlying topology at the same time, resulting in that the deployed path length is longer than the service function chain length, resulting in increase of delay and bandwidth cost.

For the deployment problem of the service function chain, related researchers also provide an ABA algorithm, and the main idea is to deploy by using a greedy algorithm and a tabu search algorithm, so that the success rate of deployment is increased, and the time delay and cost of deployment processing are reduced. Although the method can realize the deployment of the service function chain and bring about the optimization of the performance, the method only considers the node resource constraint in the bottom layer topology and does not process the link resource constraint in the topology. In addition, the order constraints of the VNFs in the service function chain are not considered in the model.

Disclosure of Invention

Aiming at the defects in the prior art, the service function chain deployment method based on breadth-first search solves the problems of high service function chain deployment consumption and high time delay.

In order to achieve the purpose of the invention, the invention adopts the technical scheme that: a service function chain deployment method based on breadth-first search comprises the following steps:

s1, invoking a breadth-first search algorithm between physical nodes deployed between a user and a service terminal to obtain a two-dimensional set of node distribution of the shortest hop count and different hop counts between the nodes;

and S2, comparing the shortest hop count with the length of the service function chain, obtaining three deployment schemes according to the comparison result, iteratively searching the node with the minimum link delay in a two-dimensional set of different hop count node distribution through a GRA algorithm, and finding the service function chain deployment path with the optimized delay through the node.

Further: the specific steps of step S1 are:

s11, initializing queue, two-dimensional set List<List<v_i>>list₁And List set<v_i>list₂Order count variable con₁＝1，con₂Adding a service terminal position node s into a queue (0);

s12, when the queue is not empty, the step S13 is carried out, otherwise, the algorithm is ended, and the step S2 is carried out;

s13, taking out a node v from the queue, and adding the node v into the set list₂And mark node v as visited, let count variable con₁Subtracting 1;

s14, when the node v is not equal to the user node d, the step S16 is executed, otherwise, the step S15 is executed;

s15, list set₂Add to two-dimensional set list₁In the method, the Hop count Hop and the two-dimensional set list where the user node d is located are output₁Ending the algorithm, and proceeding to step S2;

s16, traversing all neighbor nodes of the node v, and entering the step S17 when all neighbor nodes are not traversed, or entering the step S19;

s17, when the current neighbor node z of the node v is not accessed, the step S18 is executed, otherwise, the step S16 is executed;

s18, adding the node z into the queue, and counting the variable con₂Adding 1, returning to step S16;

s19, when counting variable con₁When equal to 0, go to step S110, otherwise return to step S12;

s110, list set₂Add to two-dimensional set list₁In, order set list₂For new empty sets, order count variable con₁Equal to the count variable con₂Order count variable con₂Equal to 0, return to step S12.

Further: the specific steps of step S2 are:

s21, making the length SFCLEngth of the service function chain equal to the number of the service function chain links | ES |;

s22, when the Hop count Hop is SFCLength, the process proceeds to step S23, otherwise, the process proceeds to step S25;

s23, extracting service function chain virtual network function set V_SIn the last virtual network function, when a node v is found in the node distribution set of the previous hop, the node v satisfies the deployment constraint C_VSAnd C_ESAnd the optimum selection factor osf (v) is minimized, go to step S24, otherwise go to step S213;

s24, recording deployed nodes and links in a deployment scheme DS, subtracting 1 from both Hop count Hop and length SFCLength, and returning to the step S23;

s25, when the Hop count Hop > SFCLEnggth, the step S26 is executed, otherwise, the step S27 is executed;

s26 finding service function chain deployment request G_SThe link e with the smallest bandwidth resource request extends the service function chainThe Hop-SFCLength | link with the bandwidth request of epsilon (e) is set, the newly added node request resources at the two ends of the link are set to be 0, so that the Hop is SFCLength, and the step S22 is returned;

s27, when Hop count Hop < SFCLEnggth, entering step S28, otherwise, entering step S213;

s28, extracting service function chain virtual network function set V_SIn the last virtual network function, when a node v is found in the node distribution set of the hop, the node v satisfies the deployment constraint C_VSAnd C_ESAnd the optimum selection factor osf (v) is minimized, go to step S29, otherwise go to step S211;

s29, recording deployed nodes and links in a deployment scheme DS, subtracting 1 from the length SFCLEngth, and entering the step S210;

s210, when Hop is SFCLEnggth, returning to the step S22, otherwise, returning to the step S27;

s211, when a node v is found in the node distribution set of the previous hop, the node v meets the deployment constraint C_VSAnd C_ESAnd the optimum selection factor osf (v) is minimized, go to step S212, otherwise go to step S213;

s212, recording deployed nodes and links in a deployment scheme DS, subtracting 1 from both Hop count Hop and length SFCLength, and returning to the step S27;

and S213, when the deployment scheme DS meets the deployment constraint DC, deducting the resource consumption of the service function chain in the underlying network topology, counting the deployment cost, deploying the path delay and the load rate, outputting the deployment scheme DS, and ending the algorithm, otherwise, directly ending the algorithm.

Further: the calculation formula of the optimal selection factor OSF is as follows:

in the above formula, delay is a delay factor, b (v)_k) Is a node v_kLoad factor of b (v)_c,v_k) To connect nodes v_cAnd node v_kThe load rate of the link;

in the above formula, d (v)_c,v_m) To connect nodes v_cAnd node v_mDelay rate of the link, d (v)_c,v_k) To connect nodes v_cAnd node v_kThe delay rate of the link.

Further: the deployment constraint DC is specifically:

DC＝(C_VS,C_ES,C_OR,L_U,L_T)

in the above formula, C_VSResource constraints for virtual network functions, C_ESFor serving resource constraints of functional chain links, C_ORFor sequential constraint of service function chains, L_UDeploying a user's location constraint, L, for a service function chain request_TThe location constraints of the service terminals in the request are deployed for the service function chain, wherein,

C_VS＝{ε(vnf₁),ε(vnf₂),…,ε(vnf_|VS|)}

C_ES＝{ε(e₁),ε(e₂),…,ε(e_|ES|)}

C_OR＝{vnf₁->vnf₂->...->vnf_|VS|}

in the above formula, { vnf₁,vnf₂,…,vnf_|VS|V set of virtual network functions that deploy requests for service function chains_SAnd | VS | is the number of virtual network functions in the service function chain deployment request, { e₁,e₂,…,e_|ES|Service function chain set of links E that deploy requests for service function chains_SAnd ES is the number of service function chain links, G_S＝(V_S,E_S) And epsilon () is the requested resource requirement of the node or link.

The invention has the beneficial effects that:

(1) the application range is wide. Conventional service function chain deployment algorithms are proposed for a particular network. The deployment algorithm provided by the invention does not restrict the scale, the sparse characteristic and the like of the network, so that the method can be suitable for most networks.

(2) The deployment cost is low. The algorithm provided by the invention realizes service function chain deployment based on the shortest path between a service terminal and a user. That is, the path close to the shortest path length is preferentially selected to deploy the service function chain, so that the bandwidth cost and the time delay consumed by deployment are reduced, and the deployment cost is reduced accordingly.

(3) And (4) load balancing. In the algorithm design provided by the invention, when the node is selected, the node load rate and the link load rate are considered, and the optimal selection factor is designed to reflect the influence of the load rate on the node selection, so that the load balance is optimized.

Drawings

FIG. 1 is a general flow chart of the present invention;

FIG. 2 is a flowchart of step S1 according to the present invention;

FIG. 3 is a flowchart of step S2 according to the present invention.

Detailed Description

The following description of the embodiments of the present invention is provided to facilitate the understanding of the present invention by those skilled in the art, but it should be understood that the present invention is not limited to the scope of the embodiments, and it will be apparent to those skilled in the art that various changes may be made without departing from the spirit and scope of the invention as defined and defined in the appended claims, and all matters produced by the invention using the inventive concept are protected.

As shown in fig. 1, a service function chain deployment method based on breadth-first search includes the following steps:

s1, invoking a breadth-first search algorithm between physical nodes deployed between the user and the service terminal, to obtain a two-dimensional set of the shortest hop count and node distributions of different hop counts between nodes, as shown in fig. 2, the specific steps are:

S2, comparing the shortest hop count with the length of the service function chain, obtaining three deployment schemes according to the comparison result, iteratively searching the node with the smallest link delay in the two-dimensional set of different hop count node distribution by the GRA algorithm, and finding the service function chain deployment path with the optimized delay by the node, as shown in fig. 3,

s26 finding service function chain deployment request G_SExpanding a link with a bandwidth request of | Hop-SFCLength | in a service function chain, wherein the link with the minimum bandwidth resource request is the link with the bandwidth request of epsilon (e), setting the request resource of a newly added node at two ends of the link to be 0, enabling the Hop to be SFCLength, and returning to the step S22;

The deployment constraint DC is specifically:

DC＝(C_VS,C_ES,C_OR,L_U,L_T)

C_VS＝{ε(vnf₁),ε(vnf₂),…,ε(vnf_|VS|)}

C_ES＝{ε(e₁),ε(e₂),…,ε(e_|ES|)}

C_OR＝{vnf₁->vnf₂->...->vnf_|VS|}

In the present invention, the underlying physical network can be modeled as an undirected weighted graph G_P＝(V_P,E_P). Wherein, V_P＝{v₁,v₂,…,v_|VP|Denotes a set of physical nodes, E_P＝{l₁,l₂,…,l_|EP|Denotes the set of physical links. | VP | and | EP | represent the number of physical nodes and physical links, respectively.

Definition RC ═ (C)_VP,C_EP,L_NP) Is a physical network resource constraint, wherein C_VPRepresenting a collection of attributes of a physical network node, a typical attribute of a physical network node comprising the node's total resource capacity a (v)_i) Node remaining resource capacity c (v)_i) And node load rate b (v)_i)。C_EPRepresenting a collection of physical network link attributes, a typical attribute of a physical network link comprising two nodes v to which the link is linked_i，v_jThe total bandwidth capacity of the link a (l)_i)＝a(v_i,v_j) Residual bandwidth capacity of the link c (l)_i)＝c(v_i,v_j) Link load rate b (l)_i)＝b(v_i,v_j) And link delay d (l)_i)＝d(v_i,v_j)。L_VP＝{L(v₁),L(v₂),…,L(v_|VP|) Denotes the set of all physical network node locations.

Wherein the node load rate b (v) in the service function chain deployment_i) And link load rate b (l)_i) The calculation formula of (2) is as follows:

the implementation deployment environment of the invention:

the technology can be used in an SDN-based network to realize the deployment of service function chains. SDN-based networks — SDN is a revolutionary revolution over traditional network architectures. It separates the control functions from the network switching device, moves them into a logically separate control environment, the network control system, and the SDN network transmits messages based on the OpeNFlow protocol. The system can be operated on a general server, and any user can directly program the control function at any time. Thus, the control functions are no longer limited to routers, nor to the programming and definition that can only be made by the manufacturer of the device. The essence of SDN is the programmability of a logic centralized control layer.

SDN facilitates network virtualization, thereby implementing integration of computing and storage resources of a network, and finally implementing control and management of the entire network by using a combination of simple software tools. This is one of the many advantages of SDN based networks and is also a key factor in deciding the deployment in the network with which service function chaining can be implemented.

Implementation of service function chaining in SDN-based network deployment:

a network operator can deploy the method for deploying the service function chain in the SDN-based network on the SDN on a control layer in a control router of the SDN, and the SDN control router can schedule a control management function carried by the SDN control router to collect information of the whole network, and obtain information of resource conditions of all nodes in the network, resources of links, time delay and the like. The router can acquire the topology of the whole network and corresponding resource information by the centralized control mode.

When a service function chain request comes, the SDN control router may schedule a service function chain-based deployment method deployed on its control layer according to the information of the whole network grasped by the SDN control router, calculate key parameters such as deployment cost, rejection rate, load rate, and the like, and feed back the parameters to an operator.

Claims

1. a service function chain deployment method based on breadth-first search, is characterized in that, comprises the following steps:

S1. Invoke the breadth-first search algorithm between the physical nodes deployed between the user and the service terminal to obtain the shortest number of hops between nodes and a two-dimensional set of node distributions with different hops;

S2. Compare the shortest number of hops and the length of the service function chain, obtain three deployment schemes according to the comparison results, and use the GRA algorithm to iteratively search for the node with the smallest link delay in the two-dimensional set of nodes with different hop numbers. Find the service function chain deployment path that optimizes the delay through this node;

The specific steps of the step S1 are:

S11. Initialize the queue queue, the two-dimensional set List<List<v _i >>list ₁ and the set List<v _i >list ₂ , set the count variables con ₁ =1, con ₂ =0, and add the service terminal location node s to the queue in queue;

S12, when the queue is not empty, go to step S13, otherwise end the algorithm, go to step S2;

S13. Take out a node v from the queue, add the node v to the set list ₂ , mark the node v as already visited, and decrease the count variable con ₁ by 1;

S14, when the node v is not equal to the user node d, go to step S16, otherwise go to step S15;

S15, adding the set list ₂ to the two-dimensional set list ₁ , outputting the hop number Hop where the user node d is located and the two-dimensional set list ₁ , ending the algorithm, and entering step S2;

S16, traverse all neighbor nodes of node v, when all neighbor nodes have not been traversed, go to step S17, otherwise go to step S19;

S17, when the current neighbor node z of node v has not been visited, go to step S18, otherwise return to step S16;

S18, add the node z to the queue, add 1 to the count variable con ₂ , and return to step S16;

S19, when the count variable con ₁ is equal to 0, go to step S110, otherwise return to step S12;

S110. Add the set list ₂ to the two-dimensional set list ₁ , set the set list ₂ to be a new empty set, set the count variable con ₁ to be equal to the count variable con ₂ , set the count variable con ₂ to be equal to 0, and return to step S12;

The specific steps of the step S2 are:

S21. Make the length of the service function chain SFCLength equal to the number of service function chain links |ES|;

S22, when the hop count Hop=SFCLength, go to step S23, otherwise go to step S25;

S23. Take out the last virtual network function in the virtual network function set V _S of the service function chain. When a node v is found in the node distribution set of the previous hop, the node v satisfies the deployment constraints C _VS and C _ES , and makes the optimal If the selection factor OSF(v) is the smallest, go to step S24, otherwise go to step S213;

S24, record the deployed nodes and links in the deployment scheme DS, decrease the hop count Hop and the length SFCLength by 1, and return to step S23;

S25, when the hop count Hop>SFCLength, go to step S26, otherwise go to step S27;

S26. Find the link e with the smallest bandwidth resource request in the service function chain deployment request GS, expand |Hop- _SFCLength | links in the service function chain with a bandwidth request of ε(e), and set new The resource requested by the added node is 0, so that Hop=SFCLength, and the process returns to step S22;

S27, when the hop count Hop<SFCLength, go to step S28, otherwise go to step S213;

S28. Take out the last virtual network function in the virtual network function set V _S of the service function chain. When a node v is found in the node distribution set of this hop, the node v satisfies the deployment constraints C _VS and C _ES , and makes the optimal choice If the factor OSF(v) is the smallest, go to step S29, otherwise go to step S211;

S29, record the deployed nodes and links in the deployment scheme DS, reduce the length SFCLength by 1, and enter step S210;

S210, when Hop=SFCLength, return to step S22, otherwise return to step S27;

S211, when a node v is found in the node distribution set of the previous hop, the node v satisfies the deployment constraints C _VS and C _ES , and makes the optimal selection factor OSF(v) the smallest, then go to step S212, otherwise go to step S213;

S212, record the deployed nodes and links in the deployment scheme DS, decrease the hop count Hop and the length SFCLength by 1, and return to step S27;

S213 , when the deployment scheme DS satisfies the deployment constraint DC, deduct the resource consumption of the service function chain in the underlying network topology and count the deployment cost, deployment path delay and load rate, output the deployment scheme DS, and end the algorithm, otherwise directly end the algorithm .

2. the described service function chain deployment method based on breadth-first search according to claim 1, is characterized in that, the calculation formula of described optimal selection factor OSF is:

candidate node set

In the above formula, delay is the delay factor, b(v _k ) is the load rate of the node v _k , and b(v _c , v _k ) is the load rate of the link connecting the node v _c and the node v _k ;

candidate node set

In the above formula, d(v _c , v _m ) is the delay rate of the link connecting node v _c and node v _m , and d( _vc , v _k ) is the delay of the link connecting node v _c and node v _k Rate.

3. the described service function chain deployment method based on breadth-first search according to claim 1, is characterized in that, described deployment constraint DC is specifically:

DC=(C _VS ,C _ES ,C _OR ,L _U ,L _T )

In the above formula, C _VS is the resource constraint of the virtual network function, C _ES is the resource constraint of the service function chain link, C _OR is the order constraint of the service function chain, _LU is the location constraint of the user in the service function chain deployment request, L _T is the location constraint of the service terminal in the service function chain deployment request, where,

C _VS ={ε(vnf ₁ ),ε(vnf ₂ ),...,ε(vnf _|VS| )}

C _ES ={ε(e ₁ ),ε(e ₂ ),...,ε(e _|ES| )}

C _OR = {vnf ₁ ->vnf ₂ ->...->vnf _|VS| }

In the above formula, {vnf ₁ ,vnf ₂ ,…,vnf _|VS| } is the virtual network function set V _S of the service function chain deployment request, |VS| is the number of virtual network functions in the service function chain deployment request, {e ₁ ,e ₂ ,...,e _|ES| } is the set ES of service function chain links requested by the service function chain deployment, |ES| is the number of service function chain links, G _S =(V _S , _E _S ), ε(.) is the request resource requirement of the node or link.