[go: up one dir, main page]

CN108260169B - A Dynamic Deployment Method of Service Function Chain Based on QoS Guarantee - Google Patents

A Dynamic Deployment Method of Service Function Chain Based on QoS Guarantee Download PDF

Info

Publication number
CN108260169B
CN108260169B CN201810078926.0A CN201810078926A CN108260169B CN 108260169 B CN108260169 B CN 108260169B CN 201810078926 A CN201810078926 A CN 201810078926A CN 108260169 B CN108260169 B CN 108260169B
Authority
CN
China
Prior art keywords
node
link
delay
reliability
sfc
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201810078926.0A
Other languages
Chinese (zh)
Other versions
CN108260169A (en
Inventor
唐伦
赵培培
周钰
杨友超
马润琳
陈前斌
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Shenzhen Nanheng Technology Co ltd
Shenzhen Wanzhida Technology Transfer Center Co ltd
Original Assignee
Chongqing University of Post and Telecommunications
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Chongqing University of Post and Telecommunications filed Critical Chongqing University of Post and Telecommunications
Priority to CN201810078926.0A priority Critical patent/CN108260169B/en
Publication of CN108260169A publication Critical patent/CN108260169A/en
Application granted granted Critical
Publication of CN108260169B publication Critical patent/CN108260169B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W28/00—Network traffic management; Network resource management
    • H04W28/16—Central resource management; Negotiation of resources or communication parameters, e.g. negotiating bandwidth or QoS [Quality of Service]
    • H04W28/24—Negotiating SLA [Service Level Agreement]; Negotiating QoS [Quality of Service]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
    • H04L41/50—Network service management, e.g. ensuring proper service fulfilment according to agreements
    • H04L41/5003—Managing SLA; Interaction between SLA and QoS
    • H04L41/5019—Ensuring fulfilment of SLA
    • H04L41/5022—Ensuring fulfilment of SLA by giving priorities, e.g. assigning classes of service
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
    • H04L41/50—Network service management, e.g. ensuring proper service fulfilment according to agreements
    • H04L41/5041—Network service management, e.g. ensuring proper service fulfilment according to agreements characterised by the time relationship between creation and deployment of a service
    • H04L41/5051—Service on demand, e.g. definition and deployment of services in real time
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/121—Shortest path evaluation by minimising delays
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W28/00—Network traffic management; Network resource management
    • H04W28/02—Traffic management, e.g. flow control or congestion control
    • H04W28/08—Load balancing or load distribution

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Quality & Reliability (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

本发明涉及一种基于QoS保障的服务功能链动态部署方法，属于移动通信技术领域。该方法为：5G网络切片借助软件定义网络和网络功能虚拟化技术实现了资源的灵活配置。为了提高切片网络中通信业务的QoS，建立面向可靠性需求的服务功能链部署模型，该模型以最小化端到端时延为目标，设计一种基于QoS保障的服务功能链动态部署方案。该方案综合考虑了节点位置和可靠性，利用一种新颖的节点排序方法进行虚拟网络功能的部署，均衡网络的负载。在链路映射过程中，通过选择满足可靠性需求的时延最短路径提高QoS。本发明在降低服务功能链端到端时延的同时保证了部署的可靠性，并且提高了请求接受率和资源利用率。

Figure 201810078926

The invention relates to a dynamic deployment method of service function chain based on QoS guarantee, and belongs to the technical field of mobile communication. The method is: 5G network slicing realizes flexible configuration of resources by means of software-defined network and network function virtualization technologies. In order to improve the QoS of communication services in the sliced network, a service function chain deployment model for reliability requirements is established. This model aims to minimize the end-to-end delay, and designs a dynamic deployment scheme of service function chain based on QoS guarantee. The scheme comprehensively considers node location and reliability, and uses a novel node sorting method to deploy virtual network functions to balance the load of the network. In the process of link mapping, QoS is improved by selecting the shortest delay path that meets reliability requirements. The invention ensures the reliability of deployment while reducing the end-to-end delay of the service function chain, and improves the request acceptance rate and resource utilization rate.

Figure 201810078926

Description

QoS guarantee-based dynamic service function chain deployment method
Technical Field
The invention belongs to the technical field of mobile communication, and relates to a QoS guarantee-based dynamic service function chain deployment method.
Background
At present, the mobile network industry is rapidly evolving to 5g, and three new application fields of mobile broadband enhancement, large-scale internet of things and low-delay high-reliability communication play an important role. The 5g network has high flexibility to cope with the service change of mobile operators, and particularly, the proposal of the network function virtualization concept enables the infrastructure to flexibly meet the diversification of the vertical application requirements. The network slice is a technology for flexibly configuring resources in a wireless virtual network, and can be quickly deployed and centrally managed. Limited physical resources are divided and recombined by means of Software Defined Networking (SDN) and Network Function Virtualization (NFV) technologies to form logically mutually independent virtual network resources for each slice network, so that repeated and efficient utilization of network resources is realized, cost input and operation expenditure of operators are reduced, better quality is provided for tenants, and the utilization rate of the network resources is improved. In a slice network, each service request is composed of several different Virtual Network Functions (VNFs), which are interconnected to be called Service Function Chains (SFCs). The different requirements of each service request can cause different sets of VNFs on each SFC, and how to effectively deploy SFCs so as to maximize the revenue of virtual operators while satisfying the slice quality of service (QOS) is a hot issue of research in 5G networks.
The low-delay scene of the 5G mobile communication system has higher requirement on the delay of the communication service, and the user millisecond-level end-to-end network service needs to be supported. Reducing the end-to-end latency of network services is one of the key issues that SFC deployments need to address. The existing invention takes the processing delay and the transmission delay as the end-to-end delay for analysis. The processing time delay is set as a fixed value, the influence of the node load on the time delay is ignored, the method is not practical, the scale of the applicable network service is limited, and the time delay problem caused by the node position and the reliability is not considered.
During SFC deployment, either a hardware failure (e.g., failure of a physical node executing a VNF) or a software failure (e.g., misconfiguration of the VNF itself) destroys the entire link, resulting in service suspension. To date, most existing inventions employ redundancy-based VNF deployment policies to achieve reliability of SFC deployment. It should be noted that the presence of these redundant VNFs will increase the length of the service function chain, thereby increasing the end-to-end latency of the service, which is very disadvantageous for latency-limited SFCs and reduces the utilization of resources. Therefore, it is necessary to develop a new SFC deployment scheme to improve the service quality of SFC deployment.
Disclosure of Invention
In view of this, an object of the present invention is to provide a QoS guarantee-based dynamic service function chain deployment method, which can dynamically allocate resources to an SFC according to underlying resources, improve QoS for SFC deployment, that is, ensure reliability requirements of the SFC while minimizing end-to-end delay. Furthermore, it is another object of the present invention to be able to accept more SFC requests to maximize the utilization of the underlying resources. In order to achieve the purpose, the invention provides the following technical scheme:
a QoS guarantee-based service function chain dynamic deployment method comprises the following steps:
s1: aiming at the QoS problem of communication service in a slice network, establishing a Service Function Chain (SFC) deployment model facing the reliability requirement, wherein the model aims at minimizing end-to-end time delay;
s2: the method comprises the steps of comprehensively considering node positions and reliability, and utilizing a novel node sorting method to sort Virtual Network Functions (VNFs) in physical nodes and service function chains respectively;
s3: determining a node mapping priority according to a node sequencing result, and selecting nodes meeting resource constraints to deploy virtual network functions to realize load balancing;
s4: in the link mapping process, a time delay shortest path which meets the link resource constraint and ensures the reliability requirement is searched for mapping.
Further, in step S1, the service function chain deployment network model is:
the underlying network is formalized as an undirected graph GS＝(NS,LS) In which N isSRepresenting a set of underlying nodes, each of which may deploy one or more VNFs, LSRepresents the set of all underlying links; each bottom node m is belonged to NSHas a CPU capacity of
Figure BDA0001560404880000021
The node position is loc (m), and a link l connecting the nodes m and nmnHas a bandwidth of
Figure BDA0001560404880000022
Reliability is R (l)mn)；
Figure BDA0001560404880000023
Is a loop-free set of paths between nodes m and n;
chains of SFCs are formalized into a directed graph, denoted GV＝(NV,LV)，NVRepresenting all VNF sets, LVA set representing all virtual links connecting the VNFs; each SFC consists of ordered VNF functions, Q denotes the strength of the SFC request arriving per unit time, and the set of SFCs is denoted S ═ Sq1,2,. cndot.Q }, each SFC ∈ Q consisting of
Figure BDA0001560404880000024
And a virtual link connecting two adjacent VNFu and v
Figure BDA0001560404880000025
Composition is carried out; the CPU resource requirement of each VNFu in the SFC is
Figure BDA0001560404880000026
Virtual link luvThe bandwidth requirement is
Figure BDA0001560404880000027
Defining a binary variable
Figure BDA0001560404880000028
Representing a virtual link luvWhether or not to map to physical link/mn∈LSThe above step (1); the position of the virtual machine represented by each VNF is loc '(u), the maximum distance offset cannot exceed lp' (u) when the virtual machine is mapped to the bottom layer node, and the time delay of the virtual link after the virtual link is mapped to the bottom layer link is duvReliability after mapping to underlying link cannot be lower than R (l)uv)。
Further, in step S1, the reliability-oriented requirement is to select a node and a link with high reliability for SFC deployment and the selected link satisfies the minimum requirement of the link for reliability.
Further, in step S1, the dynamic deployment model with the objective of minimizing the end-to-end latency is:
Figure BDA0001560404880000031
the first part is to maximize the number of requests to access the SFC, in order to maximize the utilization of resources; the second part is to minimize the end-to-end delay; calculating end-to-end delay by using the delay superposition of each hop of link in the SFC; the delay per hop link is expressed as the processing delay
Figure BDA0001560404880000032
And transmission delay
Figure BDA0001560404880000033
The sum of (1); in which the processing delay and the load that the node needs to handle
Figure BDA0001560404880000034
In relation, the processing load is defined as the ratio of the total VNF resource demand to be processed to the processing capacity of the underlying node, when the CPU load of a node increases, the processing delay of the node increases rapidly, assuming that the processing delay is a convex function of the processing load, a convex delay curve is approximated using piecewise linearization; the transmission delay is related to the number of hops that the SFC link that needs to be processed maps to the underlying link.
Further, in step S2, the node position and reliability are:
the node position is represented by a node connectivity G (m), the validity E (m) of the node and an adaptability T (m); wherein the connectivity of the node is determined by the total number of adjacent links; the effectiveness of the node is expressed by the node efficiency, the node efficiency is defined as the reciprocal of the distance between the node and other nodes, the distance represents the hop count of a link, and the shorter the transmission distance is, the higher the node efficiency is; the node adaptability means that after the node m fails, all other nodes connected with the shortest path through the node m are used as the minimum value of the communication distance increased for recovering the link connected with the node m, the smaller the increased communication distance is, the shorter the recovery time is, the larger the node adaptability value is, otherwise, the smaller the node adaptability value is;
the node reliability can be represented by the normal working probability of the node; and the normal working probability and the failure rate of the node are lambdam(ii) related; node failure rates are expressed in terms of Mean Time Between Failure (MTBF) and Mean Time To Repair (MTTR); the normal operation probability of the node can be expressed as 1-lambdam；
Assuming that the link failure satisfies the poisson distribution, the probability of no failure occurring in the time interval t is
Figure BDA0001560404880000035
So that the link has a reliability of
Figure BDA0001560404880000036
Wherein λmnIs a link lmnThe failure rate of (t) is the link lmnTime delay of (3); due to link factors taken into account when VNF deployment is performed, under the delay constraint, the following transformations are made:
Figure BDA0001560404880000037
maximizing the above equation amounts to minimizing the following equation:
Figure BDA0001560404880000038
due to du'vThe value mapped to each physical link is the same and can be further translated into the following equation: min lambdamn(ii) a The link influencing factor is expressed in node ordering as:
Figure BDA0001560404880000039
further, in step S2, the novel node ranking method is: the significance of the node is redefined by adopting the idea in the PageRank algorithm of Google, and is expressed as the following formula:
Figure BDA0001560404880000041
where r (m) represents the score of node m, which characterizes the importance of the node, γ is a damping coefficient between 0 and 1, J (m) represents the set of nodes adjacent to node m,
Figure BDA0001560404880000042
represents a normalized node resource state, represented as
Figure BDA0001560404880000043
According to the idea of PageRank, obtaining a final node iteration score expression which is expressed as the following vector expression, and obtaining the importance of all nodes through continuous iteration:
r＝(1-γ)C+γHr。
further, in step S3, the deployment of the virtual network function specifically includes: carrying out VNF deployment according to the node score result; firstly, nodes and VNF scores are arranged in a descending order, and then the VNF with a large score value is deployed to a physical node with a large score value according to the idea of merging and sorting, wherein the physical node must meet the resource requirement constraint of the VNF; if all nodes in the physical network can not meet the VNF resource constraint after circulation, the SFC is rejected; carrying out the deployment of VNFs in the SFC in sequence according to the steps until the deployment is completed or the VNFs do not meet the resource constraint and are rejected; certain changes are required when VNF sorting is performed; since the VNF in the SFC does not need to consider the normal operation probability of the node and the reliability property of the link, the resource state in the node normalization is represented as
Figure BDA0001560404880000044
Due to the link reliability constraint per hop link in the SFC, the impact condition of the link in the SFC changes
Figure BDA0001560404880000045
Further, in step S4, the link mapping process specifically includes: firstly sorting the sizes of links according to the reliability requirement of each hop of the links in the SFC, firstly selecting the links with higher reliability requirement for mapping, deleting all bottom links which do not meet the requirement of the corresponding links of the SFC, then executing a K-shortest path algorithm to select K paths with shortest time delay, sorting the paths in an increasing way according to the time delay size, and finally selecting the path with the shortest time delay which meets the link reliability constraint of the SFC.
The invention has the beneficial effects that: the invention establishes a service function chain deployment model facing the reliability requirement, and designs a service function chain dynamic deployment scheme based on QoS guarantee by taking the minimized end-to-end time delay as a target. The method comprehensively considers the position and the reliability of the node, the VNF is deployed by using a novel node sequencing method, the node with high reliability and high reliability of the link connected with the node is selected as far as possible to deploy the VNF, and preparation is made for link mapping. In addition, the VNF selects nodes with relatively more resources to deploy, so that load balance is realized, and processing time delay is reduced. And in the link mapping, selecting a time delay shortest path meeting the reliability requirement for deployment. The invention reduces the end-to-end time delay of the service function chain, ensures the reliability of deployment, and improves the request acceptance rate and the resource utilization rate by the method of load balancing and no resource reservation in the process.
Drawings
In order to make the object, technical scheme and beneficial effect of the invention more clear, the invention provides the following drawings for explanation:
FIG. 1 is a diagram illustrating an example scenario in which embodiments of the present invention may be used;
FIG. 2 is a model diagram of a node sorting process according to the present invention;
FIG. 3 is a schematic diagram illustrating an SFC request deployment process according to the present invention;
figure 4 is a schematic VNF deployment flow diagram of the present invention;
fig. 5 is a schematic diagram of a virtual link mapping process according to the present invention.
Detailed Description
Preferred embodiments of the present invention will be described in detail below with reference to the accompanying drawings.
FIG. 1 is a schematic diagram of an example of a scenario in which embodiments of the present invention may be applied. Consider a network function virtualization architecture composed of an NFV orchestration and control framework. To the left of fig. 1, the orchestration and management functions of the system are represented, consisting of management and orchestrator (MANO) and Software Defined Network (SDN) controllers. The MANO comprises three parts of service arrangement, virtual network function management and virtualization infrastructure management, and is respectively responsible for SFC service requests, VNF connection and infrastructure global resource management on the right side of the figure. The infrastructure of a Physical Network (PN) is composed of an access network and a core network, and the access network and the core network are connected through an SDN network. By isolation, multiple VNFs may run on the same underlying node without affecting each other. The MANO may perform resource allocation based on the resource status and the service request. Furthermore, the introduction of access networks requires SDN controllers to enhance MANO functionality, enabling MANOs with a wider range of connection configuration management capabilities. The SDN controller may perform traffic management according to bandwidth consumption, delay, and the like, and may also report network state information to the MANO for resource allocation. The end-to-end SFC service request is orderly composed of different VNFs and is mapped to an underlying network for service according to the resource requirements of the VNFs. In the mapping process, in consideration of the low delay and reliability requirements of the SFC, a scheme is required to be found for minimizing the end-to-end delay of the SFC deployed on the underlying network and simultaneously ensuring the reliability of the SFC service request.
FIG. 2 is a model diagram of a node sorting process in the present invention. The flow is used to order VNFs in the underlying physical node and SFC requests. The method comprises the following steps:
step 201: initializing a network topology G ═ N, L, and presetting a small positive value sigma;
step 202: calculating a matrix H and an initial vector C;
step 203: defining iteration times k, and initializing k to be 0; defining a variable w, and initializing w ═ infinity;
step 204: judging whether the w & gt sigma condition is met, if not, executing the step 208; otherwise, go on to step 205;
step 205: calculating r ═ (1-gamma) (I-gamma H)-1C；
Step 206: let k be k + 1;
step 207: calculating w ═ abs (r)k+1-rk) Returning to step 204 to continue execution;
fig. 3 is a schematic diagram of SFC request deployment process in the present invention, which includes the following steps:
step 301: collecting SFCs arriving in a unit time;
step 302: is there SFC left unprocessed? If yes, go to step 303; otherwise, the deployment is finished;
step 303: based on the node position and reliability, calculating the priorities of the nodes and VNFs in the bottom nodes and the VNFs in the SFCs according to a node sorting method, and sorting the nodes and the VNFs in a descending order;
step 304: and executing a VNF deployment algorithm, and deploying the VNF with a large score value to the physical node with the large score value meeting the resource constraint of the VNF to realize load balancing. If successful, go to step 305; otherwise, rejecting the SFC and continuing to process the next SFC;
step 305: and executing a link mapping algorithm, and searching a time delay shortest path which meets the virtual link resource constraint in the SFC and can ensure the reliability requirement for mapping. If successful, go on to step 306; otherwise, rejecting the SFC, returning to the step 302 to continue processing the next SFC;
step 306: if step 305 is successful, the SFC is accepted, the underlying network resources are updated, and the process returns to step 302 to continue execution until all SFCs are processed.
Fig. 4 is a schematic VNF deployment flow chart in the present invention, including the following steps:
step 401: storing the sorted physical nodes and the VNF priority order in the SFC;
step 402: is it determined whether all VNFs in the SFC have been completely deployed? If yes, go to step 406 to perform link mapping; otherwise, go on to step 403;
step 403: deploying the VNFs ranked in the front first according to the VNF priorities;
step 404: searching a physical node meeting the VNF resource constraint according to the priority of the physical node, namely deploying the VNF with high priority to the physical node with high priority;
step 405: if a physical node satisfying the condition is found, the VNF is deployed to the physical node, and the physical node is not considered in subsequent VNF deployment, and then the procedure returns to step 402 to continue processing the next VNF;
fig. 5 is a schematic diagram of a virtual link mapping process in the present invention, which includes the following steps:
step 501: sequencing links of each hop in the SFC according to the reliability requirement, and firstly deploying links with high reliability requirements;
step 502: is it determined whether each hop link in the SFC has been deployed completed? If yes, executing step 507 to deploy the next SFC, otherwise, continuing to execute step 503;
step 503: deleting physical links which do not meet the resource requirement of the hop link;
step 504: obtaining K time delay shortest paths by using a K shortest path method, and sequencing the K time delay shortest paths from small to large;
step 505: selecting a time delay shortest path meeting the reliability requirement of the hop link from the K paths;
step 506: the jump link is mapped to the shortest delay path, and the process returns to step 502 to continue processing until each jump link is processed.
Finally, it is noted that the above-mentioned preferred embodiments illustrate rather than limit the invention, and that, although the invention has been described in detail with reference to the above-mentioned preferred embodiments, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the scope of the invention as defined by the appended claims.

Claims (2)

1.一种基于QoS保障的服务功能链动态部署方法，其特征在于：该方法包括以下步骤：1. a service function chain dynamic deployment method based on QoS guarantee is characterized in that: the method comprises the following steps: S1：针对切片网络中通信业务的QoS问题，建立面向可靠性需求的服务功能链SFC部署模型，该模型以最小化端到端时延为目标；S1: Aiming at the QoS problem of communication services in the slicing network, establish a service function chain SFC deployment model oriented to reliability requirements, which aims to minimize end-to-end delay; S2：综合考虑节点位置和可靠性，利用新颖的节点排序方法分别对物理节点和服务功能链中的虚拟网络功能VNF排序；S2: Considering the node location and reliability comprehensively, use a novel node sorting method to sort the physical nodes and the virtual network function VNFs in the service function chain respectively; S3：根据节点排序结果确定节点映射优先级，选择满足资源约束的节点进行虚拟网络功能的部署，实现负载的均衡；S3: Determine the node mapping priority according to the node sorting result, select the node that meets the resource constraints to deploy the virtual network function, and achieve load balance; S4：在链路映射过程中，寻找满足链路资源约束并保证可靠性需求的时延最短路径进行映射；S4: In the process of link mapping, find the shortest path with delay that satisfies the link resource constraints and ensures the reliability requirements for mapping; 在步骤S1中，所述服务功能链部署网络模型为：In step S1, the service function chain deployment network model is: 底层网络形式化为一个无向图GS＝(NS,LS)，其中NS表示底层节点集合，每个节点能够部署一个或多个VNF，LS表示所有底层链路的集合；每个底层节点m∈NS的CPU容量为
Figure FDA0002936504690000011
节点位置为loc(m)，连接节点m和n的链路lmn的带宽为
Figure FDA0002936504690000012
可靠性为R(lmn)；
Figure FDA0002936504690000013
是节点m和n之间无环路的路径集；The underlying network is formalized as an undirected graph G S = (N S , L S ), where N S represents the set of underlying nodes, each node can deploy one or more VNFs, and L S represents the set of all underlying links; The CPU capacity of each bottom node m∈NS is
Figure FDA0002936504690000011
The node location is loc(m), and the bandwidth of the link lmn connecting nodes m and n is
Figure FDA0002936504690000012
Reliability is R(l mn );
Figure FDA0002936504690000013
is the set of paths without loops between nodes m and n; SFCs链形式化成有向图，表示为GV＝(NV,LV)，NV表示所有的VNF集合，LV表示连接VNF的所有虚拟链路的集合；每个SFC由一些有序的VNF功能组成，用Q表示单位时间内到达的SFC请求强度，SFC集合表示为S＝{sq|q＝1,2,…Q}，每个SFC∈Q由
Figure FDA0002936504690000014
和连接相邻两个VNF u和v的虚拟链路
Figure FDA0002936504690000015
组成；SFC中每个VNFu的CPU资源需求为
Figure FDA0002936504690000016
虚拟链路luv带宽需求为
Figure FDA0002936504690000017
定义一个二进制变量
Figure FDA0002936504690000018
表示虚拟链路luv是否映射到物理链路lmn∈LS上；每个VNF所代表的虚拟机的位置为loc'(u)，映射到底层节点时最大距离偏移不能超过lp'(u)，虚拟链路映射到底层链路后的的时延为duv，映射到底层链路后的可靠性不能低于R(luv)；The SFCs chain is formalized into a directed graph, expressed as G V = (N V , L V ), where N V represents the set of all VNFs, and L V represents the set of all virtual links connecting VNFs; each SFC consists of some ordered It consists of VNF functions, and Q is used to represent the strength of SFC requests arriving in unit time.
Figure FDA0002936504690000014
and a virtual link connecting two adjacent VNFs u and v
Figure FDA0002936504690000015
composition; the CPU resource requirement of each VNFu in the SFC is
Figure FDA0002936504690000016
The virtual link l uv bandwidth requirement is
Figure FDA0002936504690000017
define a binary variable
Figure FDA0002936504690000018
Indicates whether the virtual link l uv is mapped to the physical link l mn ∈ L S ; the position of the virtual machine represented by each VNF is loc'(u), and the maximum distance offset cannot exceed lp' ( u), the delay after the virtual link is mapped to the underlying link is d uv , and the reliability after mapping to the underlying link cannot be lower than R(l uv ); 在步骤S1中，所述面向可靠性需求为选择可靠性高的节点和链路进行SFC的部署并且所选链路满足链路对可靠性的最低需求；In step S1, the reliability-oriented requirements are to select nodes and links with high reliability for SFC deployment, and the selected links meet the minimum requirements for reliability of the links; 在步骤S1中，所述以最小化端到端时延为目标的动态部署模型为：In step S1, the dynamic deployment model aiming at minimizing the end-to-end delay is:
Figure FDA0002936504690000019
Figure FDA0002936504690000019
 第一部分为最大化接入SFC请求的数目，是为了最大化资源的利用率；第二部分为最小化端到端时延；使用SFC中每跳链路的时延叠加来计算端到端时延；每跳链路的时延表示为处理时延
Figure FDA0002936504690000021
和传输时延
Figure FDA0002936504690000022
的和；其中处理时延与节点需要处理的负载
Figure FDA0002936504690000023
有关，处理的负载定义为需要处理的总的VNF资源需求和底层节点的处理能力之比，当节点的CPU负载增大时，该节点的处理时延迅速增加，假设处理时延是处理负载的凸函数，使用分段线性化来近似凸时延曲线；传输时延与需要处理的SFC链路映射到底层链路的跳数有关；The first part is to maximize the number of access SFC requests, in order to maximize the utilization of resources; the second part is to minimize the end-to-end delay; the end-to-end delay is calculated by using the delay superposition of each hop link in the SFC Delay; the delay of each hop link is expressed as processing delay
Figure FDA0002936504690000021
and transmission delay
Figure FDA0002936504690000022
sum of ; where the processing delay is the
Figure FDA0002936504690000023
Related, the processing load is defined as the ratio of the total VNF resource demand to be processed and the processing capacity of the underlying node. When the CPU load of a node increases, the processing delay of the node increases rapidly. It is assumed that the processing delay is the processing load. Convex function, which uses piecewise linearization to approximate the convex delay curve; the transmission delay is related to the number of hops mapped from the SFC link to be processed to the underlying link; 在步骤S2中，所述节点位置和可靠性为：In step S2, the node location and reliability are: 节点位置用节点连接度G(m)、节点的有效性E(m)和适应性T(m)表示；其中节点的连接度由相邻的链路总数决定；节点的有效性用节点效率表示，节点效率定义为与其他节点之间的距离的倒数，距离表示链路的跳数，传输距离越短，节点效率就越高；节点的适应性是指当节点m失效后，所有以最短径通过m节点相连的其他节点为恢复与m相连的链路所增加通信距离的最小值，增加的通信距离越小，恢复时间越短，节点适应值越大，反之，节点适应值越小；Node location is represented by node connectivity G(m), node effectiveness E(m) and adaptability T(m); where node connectivity is determined by the total number of adjacent links; node effectiveness is represented by node efficiency , the node efficiency is defined as the reciprocal of the distance with other nodes, the distance represents the number of hops of the link, the shorter the transmission distance, the higher the node efficiency; the adaptability of the node refers to the shortest path The minimum value of the communication distance added by other nodes connected by the m node to restore the link connected to m, the smaller the increased communication distance, the shorter the recovery time, and the larger the node fitness value; otherwise, the smaller the node fitness value; 节点可靠性可用节点正常工作概率来表示；而节点正常工作概率与节点失效率λm有关；节点失效率用平均故障间隔时间MTBF和平均修复时间MTTR来表示；则节点的正常工作概率表示为1-λm；The node reliability can be represented by the normal working probability of the node; the normal working probability of the node is related to the node failure rate λ m ; the node failure rate is expressed by the mean time between failures MTBF and the mean repair time MTTR; then the normal working probability of the node is expressed as 1 -λ m ; 假设链路的失效满足泊松分布，则时间间隔t内，没有发生失效的概率为
Figure FDA0002936504690000024
链路的可靠度为
Figure FDA0002936504690000025
其中λmn为链路lmn的失效率，t为链路lmn上的时延；在进行VNF部署时考虑到链路因素，在时延约束下，做出以下转化：
Figure FDA0002936504690000026
最大化上式相当于最小化下式：
Figure FDA0002936504690000027
由于d′uv映射到每条物理链路上值是相同的，进一步转化为下式：minλmn；在节点排序时把链路影响因素表示为：
Figure FDA0002936504690000028
Assuming that the failure of the link satisfies the Poisson distribution, the probability of no failure in the time interval t is
Figure FDA0002936504690000024
The reliability of the link is
Figure FDA0002936504690000025
where λ mn is the failure rate of the link 1 mn , and t is the delay on the link 1 mn ; considering the link factor during VNF deployment, the following transformations are made under the delay constraint:
Figure FDA0002936504690000026
Maximizing the above equation is equivalent to minimizing the following equation:
Figure FDA0002936504690000027
Since the value of d′ uv mapped to each physical link is the same, it is further transformed into the following formula: minλ mn ; when the nodes are sorted, the link influencing factors are expressed as:
Figure FDA0002936504690000028
 在步骤S2中，所述新颖的节点排序方法为：采用Google的PageRank算法中的思想，重新定义节点的重要性，表示为下式：In step S2, the novel node sorting method is: adopting the idea in Google's PageRank algorithm, redefining the importance of nodes, which is expressed as the following formula:
Figure FDA0002936504690000029
Figure FDA0002936504690000029
 其中r(m)表示节点m的得分，用于表征节点的重要性，γ是一个介于0和1之间的阻尼系数，J(m)表示与节点m相邻的节点集合，
Figure FDA00029365046900000210
表示归一化的节点资源状态，表示为where r(m) represents the score of node m, which is used to characterize the importance of the node, γ is a damping coefficient between 0 and 1, J(m) represents the set of nodes adjacent to node m,
Figure FDA00029365046900000210
Represents the normalized node resource state, expressed as
Figure FDA00029365046900000211
Figure FDA00029365046900000211
 根据PageRank的思想，得到最终的节点迭代得分表达式，表示为下面的向量表达式，通过不断地迭代，得到所有节点的重要性：According to the idea of PageRank, the final node iteration score expression is obtained, which is expressed as the following vector expression. Through continuous iteration, the importance of all nodes is obtained: r＝(1-γ)C+γHrr=(1-γ)C+γHr 在步骤S3中，所述虚拟网络功能的部署具体为：根据节点得分结果进行VNF的部署；首先对节点和VNF得分按照降序排列，然后根据合并排序的思想，把得分值大的VNF部署到得分值大的物理节点上，该物理节点必须满足VNF的资源需求约束；若经过循环后物理网络中所有节点都不能满足VNF资源约束，就拒绝该SFC；按此步骤依次进行该SFC中VNF的部署，直到部署完成或不满足资源约束而拒绝；进行VNF排序时需要一定的变化；由于SFC中VNF不需要考虑节点正常工作概率和链路的可靠性性质，节点归一化中的资源状态表示为
Figure FDA0002936504690000031
SFC中每跳链路有链路可靠性约束，SFC中链路的影响条件改变为
Figure FDA0002936504690000032
In step S3, the deployment of the virtual network function is specifically: deploying the VNF according to the node score result; first, the nodes and the VNF scores are arranged in descending order, and then according to the idea of merge sorting, the VNF with a large score value is deployed to the On the physical node with a large score value, the physical node must meet the resource requirement constraints of the VNF; if all nodes in the physical network cannot meet the VNF resource constraints after the cycle, the SFC will be rejected; follow this step to perform the VNF in the SFC in turn It will be rejected until the deployment is completed or if the resource constraints are not met; certain changes are required for VNF sorting; since the VNF in SFC does not need to consider the normal working probability of the node and the reliability of the link, the resource status in the node normalization Expressed as
Figure FDA0002936504690000031
Each hop link in the SFC has a link reliability constraint, and the influence condition of the link in the SFC is changed to
Figure FDA0002936504690000032
 2.根据权利要求1所述的一种基于QoS保障的服务功能链动态部署方法，其特征在于：在步骤S4中，所述链路映射过程具体为：首先根据SFC中每跳链路的可靠性要求进行大小排序，首先选择可靠性要求较高的链路进行映射，删除所有不满足该SFC相应链路需求的底层链路，然后执行K-最短路径算法选出K条时延最短的路径，按照时延大小递增排序，最后选择满足该SFC的链路可靠性约束的时延最短的那条路径。2. a kind of service function chain dynamic deployment method based on QoS guarantee according to claim 1, is characterized in that: in step S4, described link mapping process is specifically: first according to the reliability of every hop link in SFC Sort the size according to the reliability requirements, first select the link with higher reliability requirements for mapping, delete all the underlying links that do not meet the corresponding link requirements of the SFC, and then execute the K-shortest path algorithm to select K paths with the shortest delay , sort according to the increasing delay size, and finally select the path with the shortest delay that satisfies the link reliability constraint of the SFC.
CN201810078926.0A 2018-01-26 2018-01-26 A Dynamic Deployment Method of Service Function Chain Based on QoS Guarantee Active CN108260169B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201810078926.0A CN108260169B (en) 2018-01-26 2018-01-26 A Dynamic Deployment Method of Service Function Chain Based on QoS Guarantee

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201810078926.0A CN108260169B (en) 2018-01-26 2018-01-26 A Dynamic Deployment Method of Service Function Chain Based on QoS Guarantee

Publications (2)

Publication Number Publication Date
CN108260169A CN108260169A (en) 2018-07-06
CN108260169B true CN108260169B (en) 2021-04-02

Family

ID=62742419

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201810078926.0A Active CN108260169B (en) 2018-01-26 2018-01-26 A Dynamic Deployment Method of Service Function Chain Based on QoS Guarantee

Country Status (1)

Country Link
CN (1) CN108260169B (en)

Families Citing this family (39)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108965014B (en) * 2018-07-25 2021-06-15 北京智芯微电子科技有限公司 QoS-aware service chain backup method and system
CN108900358B (en) * 2018-08-01 2021-05-04 重庆邮电大学 Dynamic Migration Method of Virtual Network Function Based on Deep Belief Network Resource Demand Prediction
CN111092743A (en) * 2018-10-24 2020-05-01 中国移动通信有限公司研究院 Virtual link monitoring method, device and storage medium
CN109358971B (en) * 2018-10-30 2020-06-23 电子科技大学 Rapid and load-balancing service function chain deployment method in dynamic network environment
CN109379230B (en) * 2018-11-08 2020-05-22 电子科技大学 A service function chain deployment method based on breadth-first search
CN109361547B (en) * 2018-11-19 2020-06-30 北京邮电大学 Method and device for network slice link deployment
EP3939220A4 (en) * 2019-03-12 2022-11-09 Nokia Technologies OY Method, device and computer readable medium for service chain
CN109714219B (en) * 2019-03-13 2021-11-09 大连大学 Virtual network function rapid mapping method based on satellite network
CN110224873B (en) * 2019-06-24 2020-08-21 北京邮电大学 NFV (network virtual function) arranging method and device based on VNF (virtual network context) instance multiplexing
CN110739991B (en) * 2019-10-21 2021-08-10 大连大学 Satellite network end-end communication reliability analysis method based on QoS
CN110851235B (en) * 2019-11-04 2022-06-03 中国人民解放军战略支援部队信息工程大学 Virtual network function deployment method suitable for multidimensional resource optimization configuration
CN111147307B (en) * 2019-12-30 2022-04-29 重庆邮电大学 Reliable deployment method of service function chain based on deep reinforcement learning
CN113271629B (en) * 2020-02-14 2023-11-21 华为技术有限公司 A network load balancing method, access network equipment and network system
CN111385202B (en) * 2020-03-17 2022-03-11 重庆邮电大学 A Route Allocation Method Based on Virtual Network Function
CN111538567B (en) * 2020-04-26 2023-06-09 国网江苏省电力有限公司信息通信分公司 Deployment method and device of a virtual network function chain on an edge device
CN112087384B (en) * 2020-08-03 2023-04-28 国网甘肃省电力公司信息通信公司 SDN environment-based data transmission method and system
CN112087329B (en) * 2020-08-27 2022-06-07 重庆大学 A network service function chain deployment method
CN114124711B (en) * 2020-09-01 2023-11-24 中国电信股份有限公司 Method and device for arranging slices and selecting routes for multiple services
CN112104491B (en) * 2020-09-04 2022-06-10 中国电子科技集团公司第二十研究所 Service-oriented network virtualization resource management method
CN112543119B (en) * 2020-11-27 2022-02-18 西安交通大学 A service function chain reliability deployment method based on deep reinforcement learning
CN112506658B (en) * 2020-12-09 2024-04-26 华南理工大学 Dynamic resource allocation and task scheduling method in service chain
CN112636961B (en) * 2020-12-15 2022-11-08 国网河南省电力公司信息通信公司 Virtual network resource allocation method based on reliability and distribution strategy under network slice
CN112738820B (en) * 2020-12-22 2023-04-11 国网北京市电力公司 Dynamic deployment method and device of service function chain and computer equipment
CN113285823A (en) * 2021-04-08 2021-08-20 国网辽宁省电力有限公司信息通信分公司 Business function chain arranging method based on container
US12131174B2 (en) 2021-06-30 2024-10-29 International Business Machines Corporation Quantifying service chain functions of virtual machines for cross interferences
US11876729B2 (en) * 2021-07-22 2024-01-16 EMC IP Holding Company LLC Method and system for a proactive assignment of virtual network functions in local data systems
CN113938955B (en) * 2021-09-09 2023-06-06 中国联合网络通信集团有限公司 Data transmission method, device, equipment and system
CN114071582B (en) * 2021-10-14 2025-04-08 北京邮电大学 Cloud-edge collaborative Internet of things-oriented service chain deployment method and device
CN113766481B (en) * 2021-10-14 2023-11-28 山东鑫泽网络科技有限公司 Network communication device and method
CN114020455B (en) * 2021-10-27 2023-01-24 中国联合网络通信集团有限公司 Service function orchestration method, device and computer-readable storage medium
CN116132355A (en) * 2021-11-15 2023-05-16 中国移动通信有限公司研究院 End-to-end service deployment method and electronic device
CN114268548A (en) * 2021-12-24 2022-04-01 国网河南省电力公司信息通信公司 Network slice resource arranging and mapping method based on 5G
CN114258074B (en) * 2021-12-27 2025-01-14 吉林大学 A VNF deployment method based on coupled bandwidth allocation and with delay QoS guarantee
CN114390489B (en) * 2022-03-04 2024-05-28 江西山水光电科技股份有限公司 End-to-end network slice servitization deployment method
CN114760202A (en) * 2022-03-04 2022-07-15 重庆邮电大学 Reliable construction and deployment method of service function chain in network slice scene
CN114884833B (en) * 2022-06-02 2024-03-12 吉林大学 SFC hop-by-hop bandwidth allocation and deployment method for realizing statistical delay QoS guarantee based on theory
CN115714724B (en) * 2022-10-10 2024-11-22 北京邮电大学 5G network resource management and control method based on service function chain mapping
CN115665148A (en) * 2022-10-25 2023-01-31 成电创智(银川)信息科技有限公司 Service function chain deployment method and system based on MEC
CN116389259B (en) * 2023-04-18 2024-07-26 控环科技集团有限公司 Network slicing orchestration, backup, and deployment methods that ensure reliability and latency requirements

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101729430A (en) * 2010-01-15 2010-06-09 西安电子科技大学 Dynamic resource allocation system and allocation method used for supporting end-to-end time delay warranty
CN101729379A (en) * 2008-10-15 2010-06-09 华为技术有限公司 Method for metropolitan area network admission control and equipment and system
EP2261845A1 (en) * 2009-05-28 2010-12-15 Palo Alto Research Center Incorporated Data center batch job quality of service control
CN103338471A (en) * 2013-06-27 2013-10-02 南京邮电大学 Service quality index evaluating method for wireless multi-hop network based on model
CN106131891A (en) * 2016-08-30 2016-11-16 重庆邮电大学 A kind of resource mapping apparatus based on SDWN and method
CN106792739A (en) * 2016-11-17 2017-05-31 北京邮电大学 Network dicing method, device and equipment

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101729379A (en) * 2008-10-15 2010-06-09 华为技术有限公司 Method for metropolitan area network admission control and equipment and system
EP2261845A1 (en) * 2009-05-28 2010-12-15 Palo Alto Research Center Incorporated Data center batch job quality of service control
CN101729430A (en) * 2010-01-15 2010-06-09 西安电子科技大学 Dynamic resource allocation system and allocation method used for supporting end-to-end time delay warranty
CN103338471A (en) * 2013-06-27 2013-10-02 南京邮电大学 Service quality index evaluating method for wireless multi-hop network based on model
CN106131891A (en) * 2016-08-30 2016-11-16 重庆邮电大学 A kind of resource mapping apparatus based on SDWN and method
CN106792739A (en) * 2016-11-17 2017-05-31 北京邮电大学 Network dicing method, device and equipment

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
基于网络切片的网络效用最大化虚拟资源分配算法;唐伦，张亚，梁荣，陈前斌;《电子与信息学报》;20170831;第39卷(第8期);全文 *

Also Published As

Publication number Publication date
CN108260169A (en) 2018-07-06

Similar Documents

Publication Publication Date Title
CN108260169B (en) A Dynamic Deployment Method of Service Function Chain Based on QoS Guarantee
WO2023039965A1 (en) Cloud-edge computing network computational resource balancing and scheduling method for traffic grooming, and system
CN108566659B (en) 5G network slice online mapping method based on reliability
CN112565082B (en) Service chain mapping method based on hybrid network, intelligent terminal and storage medium
CN108965014B (en) QoS-aware service chain backup method and system
EP3560148B1 (en) Database functions-defined network switch
CN112738820A (en) A method, device and computer equipment for dynamic deployment of service function chain
CN104993941B (en) One kind is based on Openflow network high fault tolerance virtual network mapping algorithms
CN114071582B (en) Cloud-edge collaborative Internet of things-oriented service chain deployment method and device
CN113708972A (en) Service function chain deployment method and device, electronic equipment and storage medium
CN105681153B (en) A virtual network mapping method and device
CN108684046B (en) A Method for Deploying Access Network Service Function Chain Based on Random Learning
Liu Intelligent routing based on deep reinforcement learning in software-defined data-center networks
CN108092706B (en) a mapping method
CN113904923A (en) Service function chain joint optimization method based on software defined network
CN105634974B (en) Route determining methods and device in software defined network
CN109614215A (en) Stream scheduling method, device, device and medium based on deep reinforcement learning
CN108881207A (en) Network safety service framework and its implementation based on security service chain
CN107124303B (en) Service chain optimization method with low transmission delay
CN110535705B (en) A Service Function Chain Construction Method for Adaptive User Delay Requirements
CN109412963A (en) A kind of service function chain dispositions method split based on stream
CN105704054A (en) Data center network flow migration method and system thereof
CN108111335A (en) A kind of method and system dispatched and link virtual network function
CN108092895A (en) A kind of software defined network joint route selection and network function dispositions method
CN104506337B (en) Mapping method of virtual network and device based on regional faults prediction

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
TR01 Transfer of patent right

Effective date of registration: 20231229

Address after: 518000 Room 201, building A, No. 1, Qian Wan Road, Qianhai Shenzhen Hong Kong cooperation zone, Shenzhen, Guangdong (Shenzhen Qianhai business secretary Co., Ltd.)

Patentee after: SHENZHEN NANHENG TECHNOLOGY Co.,Ltd.

Address before: 1003, Building A, Zhiyun Industrial Park, No. 13 Huaxing Road, Henglang Community, Dalang Street, Longhua District, Shenzhen City, Guangdong Province, 518000

Patentee before: Shenzhen Wanzhida Technology Transfer Center Co.,Ltd.

Effective date of registration: 20231229

Address after: 1003, Building A, Zhiyun Industrial Park, No. 13 Huaxing Road, Henglang Community, Dalang Street, Longhua District, Shenzhen City, Guangdong Province, 518000

Patentee after: Shenzhen Wanzhida Technology Transfer Center Co.,Ltd.

Address before: 400065 Chongqing Nan'an District huangjuezhen pass Chongwen Road No. 2

Patentee before: CHONGQING University OF POSTS AND TELECOMMUNICATIONS

TR01 Transfer of patent right