CN108989122A - Virtual network requests mapping method, device and realization device - Google Patents

Abstract

The present invention provides a virtual network request mapping method, device, and implementation device; wherein, the method includes: receiving a virtual network mapping request; the mapping request includes virtual nodes, virtual node constraints, virtual links, and virtual link constraints One or more of the conditions; according to the mapping request and the pre-established physical network allocation model, allocate physical nodes and physical links for the virtual network; the physical network allocation model is established through the neural network. The invention reduces the time complexity of the virtual network mapping process, and improves the allocation efficiency and utilization rate of physical network resources.

Description

Virtual network request mapping method, device and implementation device

technical field

The present invention relates to the field of virtual network technology, in particular to a virtual network request mapping method, device and implementation device.

Background technique

Network virtualization technology is regarded as an important technology for building a new generation of network architecture. Using network virtualization technology, network service providers can create multiple virtual networks on the same underlying physical network, thereby providing users with diversified and customizable end-to-end services. In the process of establishing a virtual network, virtual network mapping technology needs to be used to map virtual network requests to specific nodes and links in the underlying physical network entities. At present, the virtual network mapping methods used at home and abroad all use heuristic algorithms, which need to manually formulate a series of rules and assumptions, ignoring the relationship between the underlying physical network and virtual network requests, resulting in high time complexity. less efficient.

Contents of the invention

In view of this, the purpose of the present invention is to provide a virtual network request mapping method, device and implementation device to reduce the time complexity of the virtual network mapping process and improve the allocation efficiency and utilization of physical network resources.

In the first aspect, an embodiment of the present invention provides a virtual network request mapping method, including: receiving a virtual network mapping request; the mapping request includes virtual nodes, virtual node constraints, virtual links, and virtual link constraints One or more; according to the mapping request and the pre-established physical network allocation model, allocate physical nodes and physical links for the virtual network; the physical network allocation model is established through the neural network.

In combination with the first aspect, the embodiment of the present invention provides a first possible implementation manner of the first aspect, wherein the above-mentioned physical network allocation model is established in the following manner: establishing a mathematical model of the physical network to be allocated; Architecture, mathematical model and preset effect indicators, establish the network structure of the neural network; obtain training samples; the training samples include mapping requests of multiple virtual networks; input the training samples into the network structure for training, and obtain the physical network allocation Model.

With reference to the first possible implementation manner of the first aspect, this embodiment of the present invention provides a second possible implementation manner of the first aspect, wherein the above step of establishing a mathematical model of the physical network to be allocated includes: The node information of the network is converted into the corresponding attribute matrix, and the link information of the physical network is converted into the corresponding adjacency matrix; the noise of the attribute matrix and the adjacency matrix is eliminated by using the spectral method, and the embedded matrix of the attribute matrix and the embedded matrix of the adjacency matrix are obtained; According to the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix, the embedding matrix of the physical network is determined; according to the matrix perturbation theory, the embedding matrix of the physical network is solved to obtain the mathematical model of the physical network; the mathematical model includes a static update model.

In combination with the first possible implementation of the first aspect, the embodiment of the present invention provides a third possible implementation of the first aspect, wherein the aforementioned preset effect indicators include the operator's long-term average revenue, revenue consumption ratio and one or more of long-term acceptance rates.

In combination with the second possible implementation manner of the first aspect, the embodiment of the present invention provides a fourth possible implementation manner of the first aspect, wherein the above-mentioned determination of the physical network is based on the embedded matrix of the attribute matrix and the embedded matrix of the adjacency matrix. The step of embedding the matrix includes: obtaining the projection vector corresponding to the embedding matrix of the attribute matrix and the projection vector corresponding to the embedding matrix of the adjacency matrix when the correlation between the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix is obtained by the following formula:

Among them, the constraints are P _A ^(t)′ Y _A ^(t)′ Y _A ^(t) P _A ^(t) +P _X ^(t)′ Y _X ^(t)′ Y _X ^(t) P _X ^(t) =1. Y _A ^(t) , Y _X ^(t) are the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix at time t respectively, Y _A ^(t)′ and Y _X ^(t)′ are Y _A ^(t) , Y The transposition matrix of _X ^(t) ; P _A ^(t) and P _X ^(t) are the projection vector corresponding to the embedding matrix of the attribute matrix and the projection vector corresponding to the embedding matrix of the adjacency matrix at time t, respectively, and P _A ^(t) , P _X ^(t) are the transposed matrices of P _A ^(t) and P _X ^(t) respectively; means to obtain the maximum value of the above formula with P _A ^(t) and P _X ^(t) as variables;

When the gradient of the projection vector corresponding to the embedding matrix of the attribute matrix and the projection vector corresponding to the embedding matrix of the adjacency matrix is calculated by the Lagrangian function is zero, the projection vector corresponding to the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix correspond to The value of the projection vector;

The consensus embedding matrix is obtained by the following formula:

Y ^(t) = [Y _A ^(t) , Y _X ^(t) ]×P ^(t)

Wherein, P ^(t) is a projection vector synthesized by P _A ^(t) and P _X ^(t) , and P ^(t) = [P _A ^(t) , P _X ^(t) ].

In the second aspect, the embodiment of the present invention also provides a virtual network request mapping device, including: a request receiving module, configured to receive a virtual network mapping request; the mapping request includes virtual nodes, virtual node constraints, virtual links, and virtual One or more of the link constraints; the physical network allocation module is used to allocate physical nodes and physical links for the virtual network according to the mapping request and the pre-established physical network allocation model; the physical network allocation model passes the neural network Establish.

In combination with the second aspect, the embodiment of the present invention provides a first possible implementation manner of the second aspect, wherein the above-mentioned physical network allocation model is established in the following manner: establishing a mathematical model of the physical network to be allocated; Architecture, mathematical model and preset effect indicators, establish the network structure of the neural network; obtain training samples; the training samples include mapping requests of multiple virtual networks; input the training samples into the network structure for training, and obtain the physical network allocation Model.

With reference to the first possible implementation manner of the second aspect, the embodiment of the present invention provides a second possible implementation manner of the second aspect, wherein the above step of establishing a mathematical model of the physical network to be allocated includes: The node information of the network is converted into the corresponding attribute matrix, and the link information of the physical network is converted into the corresponding adjacency matrix; the noise of the attribute matrix and the adjacency matrix is eliminated by using the spectral method, and the embedded matrix of the attribute matrix and the embedded matrix of the adjacency matrix are obtained; According to the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix, the embedding matrix of the physical network is determined; according to the matrix perturbation theory, the embedding matrix of the physical network is solved to obtain the mathematical model of the physical network; the mathematical model includes a static update model.

In combination with the first possible implementation of the second aspect, the embodiment of the present invention provides a third possible implementation of the second aspect, wherein the above-mentioned preset effect indicators include the operator's long-term average revenue, revenue consumption ratio and one or more of long-term acceptance rates.

In the third aspect, the embodiment of the present invention also provides a device for implementing virtual network request mapping, including a memory and a processor, wherein the memory is used to store one or more computer instructions, and one or more computer instructions are executed by the processor to Implement the above method.

Embodiments of the present invention bring the following beneficial effects:

Embodiments of the present invention provide a virtual network request mapping method, device, and implementation device; after receiving a virtual network mapping request, assign physical nodes and physical links to the virtual network according to the mapping request and a pre-established physical network allocation model ; This method reduces the time complexity of the virtual network mapping process, and improves the allocation efficiency and utilization of physical network resources.

Other features and advantages of the present invention will be set forth in the following description, or some of the features and advantages can be inferred or unambiguously determined from the description, or can be known by implementing the above-mentioned techniques of the present invention.

In order to make the above-mentioned purpose, features and advantages of the present invention more comprehensible, preferred implementation modes are specifically cited below, together with the accompanying drawings, to be described in detail as follows.

Description of drawings

In order to more clearly illustrate the specific implementation of the present invention or the technical solutions in the prior art, the following will briefly introduce the accompanying drawings that need to be used in the specific implementation or description of the prior art. Obviously, the accompanying drawings in the following description The drawings show some implementations of the present invention, and those skilled in the art can obtain other drawings based on these drawings without any creative work.

FIG. 1 is a flowchart of a virtual network request mapping method provided by an embodiment of the present invention;

2 is a flowchart of a method for establishing a physical network allocation model in a virtual network request mapping method provided by an embodiment of the present invention;

FIG. 3 is a topology diagram of a virtual network request and a physical network in a virtual network request mapping method provided by an embodiment of the present invention;

FIG. 4 is a flowchart of node mapping in a virtual network request mapping method provided by an embodiment of the present invention;

5 is a working process diagram of a physical network allocation model in a virtual network request mapping method provided by an embodiment of the present invention;

FIG. 6 is a comparison chart of evaluation indicators for testing the same group of test sets by four physical network allocation models using different algorithms provided by the embodiment of the present invention;

FIG. 7 is a schematic structural diagram of a virtual network request mapping device provided by an embodiment of the present invention;

FIG. 8 is a schematic structural diagram of an apparatus for implementing virtual network request mapping provided by an embodiment of the present invention.

Detailed ways

In order to make the purpose, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions of the present invention will be clearly and completely described below in conjunction with the accompanying drawings. Obviously, the described embodiments are part of the embodiments of the present invention, not all of them. the embodiment. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

Currently, virtual network technology is developing rapidly. In the process of establishing a virtual network, virtual network mapping technology needs to be used; the goal of virtual network mapping is to realize efficient utilization of underlying physical network resources under the premise of satisfying resource constraints. Virtual network mapping needs to select physical nodes and physical links that match the virtual network request to carry the individual needs of tenants. If an efficient and reliable virtual network mapping technology can be realized, and dynamic virtual requests can be quickly responded to, the utilization rate of physical resources will be significantly improved, thereby improving the revenue capability of network service providers.

But in actual operation, under the constraints of nodes and links, virtual network mapping is an NP-hard (non-deterministic polynomial-hard, non-deterministic polynomial-hard) problem.

The existing virtual network mapping method has high time complexity, and the allocation efficiency and utilization rate of physical network resources are low. Based on this, embodiments of the present invention provide a virtual network request mapping method, device and implementation device, which can be applied to physical network resource allocation and other resource allocation fields.

In order to facilitate the understanding of this embodiment, a virtual network request mapping method disclosed in this embodiment of the present invention is first introduced in detail.

Referring to the flowchart of a virtual network request mapping method shown in Figure 1, the method includes the following steps:

Step S100, receiving a virtual network mapping request; the mapping request includes one or more of virtual nodes, virtual node constraints, virtual links, and virtual link constraints; when establishing a virtual network, it is proposed to allocate physical network resources request; the allocation of the physical network resources shall be carried out according to the nodes, links and corresponding constraints of the virtual network, and the constraints may be CPU (Central Processing Unit, central processing unit) computing resources and bandwidth resources.

Step S102, according to the mapping request and the pre-established physical network allocation model, allocate physical nodes and physical links for the virtual network; the physical network allocation model is established through the neural network.

Specifically, the above physical network allocation model can be established in the following manner:

(1) Establish a mathematical model of the physical network to be allocated; since the physical network resources to be allocated are limited, it is necessary to consider the bearing capacity of the physical network resources for the virtual network mapping request, establish an accurate mathematical model of the physical network, and Applied to the neural network model, it is more conducive to efficiently completing the virtual network mapping request.

(2) According to the preset model architecture, mathematical model and preset effect indicators, establish the network structure of the neural network; specifically, the above model architecture can be the preset effect indicators can be the long-term average income of the operator, revenue consumption One or more of ratio and long-term acceptance rate.

(3) Obtain a training sample; the training sample includes mapping requests of multiple virtual networks.

(4) Input the training samples into the network structure for training to obtain the physical network allocation model.

The embodiment of the present invention provides a virtual network request mapping method; after receiving the virtual network mapping request, according to the mapping request and the pre-established physical network allocation model, assign physical nodes and physical links to the virtual network; this method reduces virtual The time complexity of the network mapping process improves the allocation efficiency and utilization of physical network resources.

The embodiment of the present invention also provides a method for establishing a physical network allocation model in a virtual network request mapping method, the method is implemented on the basis of the method shown in Figure 1, and its flowchart is shown in Figure 2, including the following steps :

Step S200, convert the node information of the physical network into a corresponding attribute matrix, and convert the link information of the physical network into a corresponding adjacency matrix; specifically, the node information of the physical network can be represented by an attribute matrix, and each row represents a physical Node, each column represents a node attribute. The link information of the physical network can be represented by an adjacency matrix, and A ^(t) and X ^(t) can be used to represent the attribute matrix and adjacency matrix of the physical underlying network respectively. The definition of each symbol in the following formula is shown in Table 1:

Table 1

Step S202, using the spectral method to eliminate noise of the attribute matrix and the adjacency matrix, to obtain the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix.

Specifically, the embedding matrix of the adjacency matrix can be obtained as follows: D _X ^(t) is specified as the degree matrix of X ^(t) , namely It is stipulated that L _X ^(t) is the Laplacian matrix of X ^(t) , that is, L _X ^(t) = D _X ^(t) −X ^(t) . According to spectral theory, mapping an n-dimensional matrix to a k-dimensional embedding matrix (k<<n) can effectively reduce the noise in the matrix representation. A general way to choose Yx ^(t) = [y ₁ ,y ₂ ,...y _n ]' is to minimize the loss function That is, in the new space, the distance between the connected nodes is closer. At this time, the problem degenerates into a generalized characteristic problem suppose For the corresponding eigenvalue 0=λ ₁ <=λ ₂ <=...<=λ _n eigenvector of this problem, it is easy to verify that λ ₁ =0 and the corresponding eigenvector is 1. Pick As the embedding matrix Y _X (t) of the adjacency matrix X ^{( t)} , and take their corresponding eigenvalues [λ ₁ ,λ ₂ ,...,λ _k+1 ] as the eigenvalues of time t.

Similar to the adjacency matrix, the attribute matrix A ^(t) can also get the corresponding Y _A ^(t) , first get the normalized attribute matrix, and then get the similarity matrix W ^(t) of the attribute matrix. The embedded representation Y _A ^(t) of the attribute matrix A ^(t) is generated in the same way.

Step S204, determine the embedding matrix of the physical network according to the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix.

Specifically, this step is implemented in the following ways:

(1) When the correlation between the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix is obtained by the following formula, the projection vector corresponding to the embedding matrix of the attribute matrix and the projection vector corresponding to the embedding matrix of the adjacency matrix:

Among them, the constraints are P _A ^(t)′ Y _A ^(t)′ Y _A ^(t) P _A ^(t) +P _X ^(t)′ Y _X ^(t)′ Y _X ^(t) P _X ^(t) =1. Y _A ^(t) , Y _X ^(t) are the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix at time t respectively, Y _A ^(t) ′, Y _X ^(t) ′ are Y _A ^(t) , Y The transposition matrix of _X ^(t) ; P _A ^(t) and P _X ^(t) are the projection vector corresponding to the embedding matrix of the attribute matrix and the projection vector corresponding to the embedding matrix of the adjacency matrix at time t, respectively, and P _A ^(t) , P _X ^(t) are the transposed matrices of P _A ^(t) and P _X ^(t) respectively; means to obtain the maximum value of the above formula with P _A ^(t) and P _X ^(t) as variables.

(2) When the gradient of the projection vector corresponding to the embedding matrix of the attribute matrix and the projection vector corresponding to the embedding matrix of the adjacency matrix is obtained by the Lagrangian function is zero, the projection vector corresponding to the embedding matrix of the attribute matrix and the embedding of the adjacency matrix The value of the projection vector corresponding to the matrix; specifically, let γ be a Lagrangian operator, then the gradient of P _X ^(t) and PA ( _{t) is calculated to be zero through the Lagrangian function, and P X} ^can _be obtained ^(t) and the value of P _A ^(t) . The corresponding generalized eigenproblem is formulated as:

Then we take the consensus embedding representation of the first L eigenvectors of the above generalized eigenproblem, and we can get the projection matrix

(3) The consensus embedding matrix is obtained by the following formula:

Y ^(t) = [Y _A ^(t) , Y _X ^(t) ] × P ^(t) (3)

Wherein, P ^(t) is a projection vector synthesized by P _A ^(t) and P _X ^(t) , and P ^(t) = [P _A ^(t) , P _X ^(t) ].

In step S206, according to the matrix perturbation theory, the embedding matrix of the physical network is solved to obtain a mathematical model of the physical network; the mathematical model includes a static update model.

During the virtual network mapping process, when a virtual request comes, the physical network will change. Therefore, the attribute matrix is a matrix that changes dynamically at high frequency. If at each time step, Y _X ^(t) and Y _A ^(t) are first calculated for each physical network by means of eigenvectors and eigenvalues, and then Y _X ^(t) and Y _A ^(t) are obtained Y ^(t) , which is very time-consuming and unrealistic in a large-scale network. Therefore, it is proposed to dynamically update Y _X ^(t) and Y _A ^(t) by means of matrix variable update to reduce time complexity.

The proposed dynamic update algorithm is based on the fact that the virtual network mapping algorithm does not change too much in two consecutive time steps. Because in virtual network mapping, after a virtual network request is completed, the physical network will subtract the resources required for this virtual request, and the resources of this virtual request usually do not occupy a large part of the physical resources. Using ΔA and ΔX to represent the change of attribute matrix and adjacency matrix in two consecutive time steps, then for the degree matrix and Laplacian matrix of the two:

D _A ^(t+1) = D _A ^(t) +ΔD _A , L _A ^(t+1) = L _A ^(t) +ΔL _A ,

D _X ^(t+1) ＝D _X ^(t) +ΔD _X , L _X ^(t+1) ＝L _X ^(t) +ΔL _X . (4)

In the static model, obtaining the embedding matrix of the attribute matrix and the adjacency matrix is equivalent to solving a generalized characteristic problem. Then take the first k eigenvectors as the embedding matrix, which needs to solve the generalized eigenproblem, but the complexity of solving the eigenvalue problem is very high, so we need an effective way to get the embedding matrix of the attribute matrix and the adjacency matrix. We take the embedding matrix update method of adjacency matrix as an example to illustrate the specific steps of dynamic update. According to the matrix perturbation theory:

For some eigenvalue and eigenvector pair (λ _i ,a _i ):

Then the algorithm problem of dynamic update is equivalent to how to obtain the change pair of eigenvalues and eigenvectors from the Laplacian change matrix ΔL and the degree matrix change matrix ΔD The way of solving is divided into finding Δλ _i and solving two parts.

First calculate Δλ _i , expand (6) to get:

Since the double derivative such as etc. have little effect on the results, so they are omitted. and due to (7) can be simplified to the result:

Multiply both sides of the equation by a _i ', (8) becomes:

Since the Laplacian matrix L _X ^(t) and the degree matrix D _X ^(t) are symmetric matrices, then:

So equation (9) becomes:

So the change in eigenvalues is:

easy therefore:

Next calculate Since the network structure changes smoothly in continuous time steps, it is assumed that the perturbation of the eigenvector is composed of the first k eigenvectors, namely where α _ij is the weight of the jth eigenvector, which can be obtained by:

Will Insert into formula (8), get:

multiply both sides of the equation by At the same time easy to get:

Therefore, the weight α _ip can be obtained:

When p≠i, the weight value has been obtained. The following describes how to obtain α _ii when p=i:

Expanding (17) and discarding the double derivative term, we get:

get:

So the perturbation of the eigenvector a _i is:

So far, the perturbation pairs of eigenvalues and eigenmatrix can be found The update process of the embedding matrix in the physical network is shown in the pseudo code in Algorithm 1, and its code is shown in Table 2.

Table 2

The input of the algorithm is to obtain the first k pairs of eigenvalues and eigenvectors by solving the eigenvalues and eigenvectors of the generalized eigenproblem at the starting time (t=1). and the perturbation of the Laplace and degree matrices at each time step. The output is the top k eigenvalue and eigenvector pairs at time step T. Among them, lines 3 and 4 call formula (13) and formula (20) to calculate the perturbation, and then update the eigenvalues and eigenvectors. The above process shows how to update the eigenvalues and eigenmatrix in the form of adjacency matrix, then the embedding matrix of the attribute matrix can also be updated in the same way, thus obtaining the static update model of the physical network.

The above method uses the spectral method to obtain a robust consensus matrix, which can effectively represent the underlying physical network and realize the static representation of the physical network; in addition, the matrix perturbation theory is also used to capture the nodes and nodes in the physical network in continuous time. The change of the link, and complete the update of the physical network, realize the dynamic update of the physical network.

The embodiment of the present invention also provides another virtual network request mapping method, which is implemented on the basis of the method shown in FIG. 2 .

The virtual network mapping problem can be represented by the virtual network request and physical network topology as shown in Figure 3, where (a) and (b) are virtual network requests, and (c) is the underlying physical network. Model using an undirected graph Represents the physical network, where ^NS and ^LS represent the node set and link set of the physical network, respectively, and Represents the attribute collection of nodes and links of the physical network, respectively. Node attributes of the physical network include node CPU capabilities and location information, and link attributes include link bandwidth and delay. Similarly, virtual network requests can also be represented using an undirected graph. Use an undirected graph model Represents a virtual network request, where N ^V and L ^V respectively represent the node set and link set of the virtual network request, and respectively represent the constraints of nodes and links requested by the virtual network. In order to make the description of the virtual network map concise and intuitive, the physical resources and the node resources requested by the virtual network mainly consider CPU computing resources, and the link resources mainly consider bandwidth resources.

Figure 3(c) shows a physical network, including seven physical nodes from A to G. Taking node A and node B as examples, the computing resources of node A are 30 units, and the computing resources of node B are 40 units. The bandwidth resource between A and node B is 20 units. Figure 3(a) and Figure 3(b) show virtual network requests. Taking Figure 3(a) as an example, the computing resources required by virtual node a are 5 units, and the computing resources required by virtual node b are 10 units. The virtual link resource required between node a and virtual node b is 10 units.

Record a virtual network mapping process as M: G ^V (N ^V , L ^V ) → G ^S (N', L'), where Taking Figure 3 as an example, two nodes a and b may be mapped to two nodes A and B, then the link request between ab is mapped to the physical link between AB; it is also possible that two nodes a and b A node may be mapped to two nodes A and C, then the link request between ab is mapped to two physical links between AB and BC, which consumes more than the previous mapping method Link resources between BCs are reduced, and this virtual network mapping task is completed with more network resource consumption.

When the request in Figure 3(a) arrives at the physical network in Figure 3(c) at time t, the resource occupation time of the physical network is recorded as t _d , during the entire occupation time t _d , the physical resources allocated to the request cannot Consumed by other virtual network requests. Therefore, the virtual network mapping algorithm, that is, how to make a reasonable decision to allocate virtual network requests, will have an important impact on the utilization of physical resources.

The main goal of virtual network mapping is to map as many virtual network requests as possible to the physical network, so as to improve the utilization efficiency of physical network resources and increase the revenue of infrastructure operators. In this embodiment, the three indicators of long-term average income, income consumption ratio and long-term acceptance rate are used as standards for measuring the completion of virtual network request tasks.

According to the above-mentioned embodiment, the mathematical model of the physical network has been established according to formula (3), formula (13) and formula (20). ) algorithm to establish a physical network allocation model, input the virtual network mapping request into the network, and output the probability that the virtual network request node is mapped to each physical network node through the model.

RDAM algorithm regards virtual network mapping as two stages of node mapping and link mapping. Compared with the node mapping stage, the link mapping stage is to assign links to the nodes mapped in the node mapping stage according to the method of depth-first traversal. The process of node mapping is shown in Figure 4, which is divided into Problem 1 (problem 1) and Problem 2 (problem 2). Problem 1 refers to the problem of feature selection and feature representation, and Problem 2 refers to the problem of dynamic update of features. Feature selection and feature representation use the spectral analysis method to obtain a robust consensus matrix of the physical network; the feature update method uses matrix perturbation theory to solve the problem of high time complexity in the static update method.

As shown in Figure 4, the left side represents time step t, and the right side represents time step t+1. At time step t, the physical underlying network (Substrate Network) attributes (attributes) matrix A ^(t) and adjacency matrix X ^(t) are first obtained, and the noise in the two matrices is eliminated by spectral analysis, and the embedded representation of the attribute matrix is obtained Y _A ^(t) and adjacency matrix embedded representation Y _X ^(t) . Then the final consensus matrix (consensus embedding) Y ^(t) is obtained through two embedded matrices. Then at time step t+1, the gray grid in the figure represents the changing attribute, and the online update is performed from the change amount ΔA of the attribute matrix and the change amount ΔX of the adjacency matrix to obtain a new embedded representation of the attribute matrix Y _A ^{( t+1)} and the adjacency matrix embedded representation Y _X ^{(t +1)} to get a new consensus matrix Y ^(t+1) ; the problem of the above node mapping is how to get the consensus matrix and how to get it after virtual network mapping A new consensus matrix; these two issues have been solved in the process of establishing the mathematical model of the physical network, and will not be repeated here.

The working process diagram of the model is shown in Figure 5. The model (also known as Policy Network) includes an input layer, a convolutional layer, a softmax (soft maximum transfer function) layer, and a candidate layer (candidates layer). Among them, the first layer is the input layer, and Y is input into the model, where Y _i ^j (1≤i≤n,1≤j≤l) represents the value of the j-th dimension in the hidden layer representation of the i-th node. The second layer is the convolutional layer. After passing through the convolutional layer, an n-dimensional vector representation of available physical nodes is obtained. which is:

h _i =w·Y _i +b (21)

Among them, h _i is the output of the i-th convolutional layer, w is the weight vector of the convolution kernel, and b is the bias.

The third layer is the Softmax layer, which passes the output h of the convolutional layer into the Softmax layer to generate a probability, which represents the probability that the virtual network request node selects each physical node. For each physical node, the calculation method of the probability Softmax is:

Softmax is an extension of the logistic function, which can obtain the probability of each dimension of a vector, the range of the probability of each dimension is between (0,1), and the sum of the probabilities of all dimensions is 1.

The fourth layer is the candidate node layer. Through this model, each physical node has a probability, but in the actual situation, there will be a physical node that does not meet the virtual network request node, so this layer will have a filter for filtering nodes. Select the physical node with the highest probability after filtering.

After the model is established, the model needs to be trained by means of reinforcement learning. In the supervised learning of the neural network, the sample includes the sample features and the label of the sample, and the predicted label is obtained after the sample feature is passed through the model, and the distance from the real label of the sample is used as the loss function, then the process of supervised learning is to continuously reduce the value of the loss function the process of. In reinforcement learning, samples do not have real labels. Compared with supervised learning, reinforcement learning has less sample labels and an additional evaluation index function. After the sample features are passed through the model, the predicted label is obtained, and the predicted label is selected. If the label can bring a better evaluation index value to the entire system, it means that the direction of the model prediction is correct, so the parameters of the model are encouraged to continue Train in this direction. If the value of the evaluation index brought is small or even negative, it means that the direction predicted by the model is incorrect, so the parameter training direction of the model needs to be adjusted.

Specific to the virtual network mapping process, assuming that the physical network has n nodes, and the embedding matrix of each node has l dimension, the embedding matrix (n*l) of the physical network is passed into the model as input, and the virtual network node requests to select each The probability of a physical node. At this time, the physical network node with the highest probability cannot be directly selected, because the network model parameters are randomly initialized. If the node with the highest probability is selected, the model will always be biased. Therefore, it is necessary to find a balance between the exploration of models and the utilization of existing models. At this time, the probability vector P of each node is obtained through this model, and then we randomly select the i-th node to construct a one-hot encoded vector, that is, the vector has n dimensions, only the i-th bit is 1, and the rest are all is 0. Then the loss function can be written as:

Where y _i and p _i are the value of the i-th dimension of the randomly selected one-hot vector and the predicted probability vector P, respectively. Then, the gradient g is obtained by reverse derivation. The training result of the model tends to be that when the randomly selected node can bring a large ratio of income to consumption, the direction of model parameter training is more inclined to make similar decisions. ; and when the revenue consumption brought by this randomly selected node is relatively low, the direction of model parameter training is to discourage making similar decisions. So, make an update to the gradient:

g:=α·r·g (24)

Where α is the learning rate, which controls the speed of model training. When α is too large, the training process will fail to converge and miss the global optimal solution. When α is too small, the training process is too slow, so it is necessary to choose an appropriate learning rate. Multiplying the reward with the gradient, a decision with a larger reward will have a greater impact on the training agent and thus be more inclined to produce similar decisions; while a decision with a smaller or negative reward will have a greater impact on the training agent have a smaller impact.

When the model is trained on a virtual network request, the virtual network request generally contains multiple virtual network request nodes. After each virtual request node passes the model, the gradient is pushed into the stack instead of being directly applied to the model, because the virtual network request may fail to map. If the mapping fails, the part where the virtual network request node is pushed into the stack is cleared, and then the next virtual network request is processed. When the number of virtual network requests reaches the number of batches, all the gradients in the stack are applied to the model, and then the stack is cleared and counted again. The reason why batch gradient descent is applied is first of all because the gradient update takes a lot of time. If the batch gradient descent will save a lot of time. Secondly, the batch gradient descent averages the gradient within the batch size, and the training results are more stable.

The code of the training process of a complete virtual network mapping is shown in Algorithm 2 (Algorithm2) in Table 3:

table 3

Lines 7-10 are the process of node mapping, and lines 11-13 are the process of link mapping. In line 28, when the mapping is unsuccessful, the gradient in the stack will be cleared, and the training will start from the next virtual network mapping request. Lines 21-23 update the Batch Size gradients and clear the request counter.

The pseudocode of the test phase is shown in Algorithm 3 in Table 4:

Table 4

In the test phase, the greedy strategy is directly used to select physical nodes from the nodes with the largest probability for mapping. If all nodes and links are mapped successfully, then the long-term average income, acceptance rate and long-term income-to-consumption ratio of the final result will all be improved.

After the physical network allocation model is trained, the model can be applied to the processing of virtual network mapping requests. In order to verify the generalization effect of the model, we conducted experiments on the test set. Three controlled trials were selected. The first control model uses the baseline (baseline) algorithm:

The second comparison model uses the Node Rank algorithm. The third comparison model uses an algorithm RLVNE (Reinforcement Learning Algorithm for VirtualNetwork Embedding) that is also based on reinforcement learning. These three algorithms are all virtual network mapping algorithms that divide node mapping and link mapping into two stages, and the link mapping adopts the depth-first traversal method. The difference lies in the algorithm used in the node mapping stage.

During the training process, the long-term benefit-to-consumption ratio is used as the evaluation index. At each epoch (a point in time), if the long-term average income is higher than the current best long-term average income, then update the best long-term average income to be the long-term average income of this epoch, and use the current model to test the set Virtual network mapping. During training, there will be many sets of tests on the test set. Obviously, the last set of results is the virtual network mapping of the test set when the model is optimal during the training process. In Figure 6, this algorithm shows the results of the last set of test sets. Figure 6(a) shows the long-term average revenue of the four models on the test results of the same set of test sets. Figure 6 Shown in (b) is the revenue consumption ratio of the four models to the test results of the same set of test sets, and shown in Figure 6(c) is the long-term acceptance rate of the four models to the test results of the same set of test sets; among them, RDA- VNE represents a model using the RDAM algorithm, rl represents a model using the RLVNE algorithm, NodeRank represents a model using the NodeRank algorithm, and Baseline represents a model using the baseline algorithm.

In the test phase, the start time of the virtual network request is 22, and the end time is 30,000, with 1000 as a time unit. Figure 6 shows the change of the evaluation index of the virtual network request in thirty time periods. In Figure 6(a) and Figure 6(b), the long-term average revenue and acceptance rate will decrease at the beginning, because the physical resources will be gradually consumed with the arrival of virtual network requests. In the initial stage, the long-term benefit-to-consumption ratio will not drop significantly, because this indicator has nothing to do with the amount of physical resources. Then the three indicators tend to be stable, but it can be seen that among the three evaluation indicators, the convergence trend and convergence value of the RDAM algorithm are better than the other three algorithms. Through this experiment, it can be concluded that the reinforcement learning agent learns the relationship of physical network nodes in the RDN-VNE algorithm in the training phase, and can generalize the model in the testing phase, showing superiority on the test set.

In this embodiment, by adopting the reinforcement learning method to train the physical network allocation model based on the neural network, the relationship between the underlying network representation and the virtual network request can be effectively discovered, thereby completing effective virtual network mapping.

Corresponding to the above-mentioned embodiments, an embodiment of the present invention also provides a virtual network request mapping device, its structural diagram is shown in Figure 7, including: a request receiving module 700, configured to receive a virtual network mapping request; the mapping request includes a virtual One or more of nodes, virtual node constraints, virtual links, and virtual link constraints; the physical network allocation module 702 is used to allocate physical nodes for the virtual network according to the mapping request and the pre-established physical network allocation model and physical links; the physical network allocation model is established through a neural network.

The above physical network allocation model can be established in the following ways:

(1) Establish a mathematical model of the physical network to be assigned; specifically, convert the node information of the physical network into a corresponding attribute matrix, and convert the link information of the physical network into a corresponding adjacency matrix; use the spectral method to eliminate the attribute matrix and The noise of the adjacency matrix is used to obtain the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix; according to the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix, the embedding matrix of the physical network is determined; according to the matrix perturbation theory, the embedding matrix of the physical network Solve to obtain the mathematical model of the physical network; the mathematical model is a static update model of the physical network.

(2) According to the preset model structure, mathematical model and preset effect index, establish the network structure of the neural network; the preset effect index can be the operator's long-term average revenue, revenue consumption ratio and long-term acceptance rate one or more.

(3) Obtain a training sample; the training sample includes multiple mapping requests of the virtual network.

(4) Input the training samples into the network structure for training to obtain the physical network allocation model.

The virtual network request mapping device provided by the embodiment of the present invention has the same technical features as the virtual network request mapping method provided by the above embodiment, so it can also solve the same technical problem and achieve the same technical effect.

This implementation manner provides a device for implementing virtual network request mapping corresponding to the foregoing method implementation manner. Figure 8 is a schematic structural diagram of the implementation device, as shown in Figure 7, the device includes a processor 1201 and a memory 1202; wherein, the memory 1202 is used to store one or more computer instructions, and one or more computer instructions are executed by the processor , to implement the above virtual network request mapping method.

The implementation device shown in FIG. 8 further includes a bus 1203 and a forwarding chip 1204 , and the processor 1201 , the forwarding chip 1204 and the memory 1202 are connected through the bus 1203 . The device for realizing the packet transmission may be a network edge device.

Wherein, the memory 1202 may include a high-speed random access memory (RAM, Random Access Memory), and may also include a non-volatile memory (non-volatile memory), such as at least one disk memory. The bus 1203 may be an ISA bus, a PCI bus, or an EISA bus, etc. The bus can be divided into address bus, data bus, control bus and so on. For ease of representation, only one double-headed arrow is used in FIG. 8 , but it does not mean that there is only one bus or one type of bus.

The forwarding chip 1204 is used to connect with at least one user terminal and other network elements through the network interface, and send the encapsulated IPv4 message or IPv6 message to the user terminal through the network interface.

The processor 1201 may be an integrated circuit chip with signal processing capability. In the implementation process, each step of the above method may be implemented by an integrated logic circuit of hardware in the processor 1201 or instructions in the form of software. The above-mentioned processor 1201 may be a general-purpose processor, including a central processing unit (Central Processing Unit, referred to as CPU), a network processor (Network Processor, referred to as NP), etc.; it may also be a digital signal processor (Digital Signal Processing, referred to as DSP) , Application Specific Integrated Circuit (ASIC for short), off-the-shelf programmable gate array (Field-Programmable Gate Array, FPGA for short) or other programmable logic devices, discrete gate or transistor logic devices, discrete hardware components. The various methods, steps and logic block diagrams disclosed in the embodiments of the present invention can be realized or executed. A general-purpose processor may be a microprocessor, or the processor may be any conventional processor, or the like. The steps of the method disclosed in connection with the embodiments of the present invention may be directly implemented by a hardware decoding processor, or implemented by a combination of hardware and software modules in the decoding processor. The software module can be located in a mature storage medium in the field such as random access memory, flash memory, read-only memory, programmable read-only memory or electrically erasable programmable memory, register. The storage medium is located in the memory 1202, and the processor 1201 reads the information in the memory 1202, and combines its hardware to complete the steps of the methods in the foregoing embodiments.

The embodiment of the present invention also provides a machine-readable storage medium, the machine-readable storage medium stores machine-executable instructions, and when the machine-executable instructions are called and executed by a processor, the machine-executable instructions cause the processor to implement For the above virtual network request mapping method, for specific implementation, please refer to the method implementation manner, which will not be repeated here.

The virtual network request mapping device and implementation device provided by the embodiments of the present invention have the same realization principles and technical effects as the aforementioned method embodiments. For a brief description, the parts not mentioned in the device embodiment can be implemented with reference to the aforementioned methods. corresponding content in the method.

In the several implementation manners provided in this application, it should be understood that the disclosed devices and methods may also be implemented in other ways. The device implementations described above are only illustrative. For example, the flowcharts and block diagrams in the accompanying drawings show the architecture, functions and possible implementations of devices, methods, and computer program products according to multiple embodiments of the present invention. operate. In this regard, each block in a flowchart or block diagram may represent a module, program segment, or part of code that includes one or more Executable instructions. It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks in succession may, in fact, be executed substantially concurrently, or they may sometimes be executed in the reverse order, depending upon the functionality involved. It should also be noted that each block of the block diagrams and/or flowchart illustrations, and combinations of blocks in the block diagrams and/or flowchart illustrations, can be implemented by a dedicated hardware-based system that performs the specified function or action , or may be implemented by a combination of dedicated hardware and computer instructions.

In addition, each functional module or unit in each embodiment of the present invention can be integrated together to form an independent part, or each module can exist independently, or two or more modules can be integrated to form an independent part.

If the functions described above are realized in the form of software function units and sold or used as independent products, they can be stored in a computer-readable storage medium. Based on this understanding, the technical solution of the present disclosure is essentially or the part that contributes to the prior art or the part of the technical solution can be embodied in the form of a software product, and the computer software product is stored in a storage medium, including Several instructions are used to make a computer device (which may be a personal computer, a server, or a network device, etc.) execute all or part of the steps of the methods described in various embodiments of the present disclosure. The aforementioned storage medium includes: U disk, mobile hard disk, read-only memory (ROM, Read-Only Memory), random access memory (RAM, Random Access Memory), magnetic disk or optical disk and other media that can store program codes. .

Finally, it should be noted that: the above-mentioned embodiments are only specific embodiments of the present disclosure, and are used to illustrate the technical solutions of the present disclosure, rather than to limit them, and the scope of protection of the present disclosure is not limited thereto. The embodiments describe the present disclosure in detail, and those skilled in the art should understand that any person familiar with the technical field can still modify the technical solutions described in the foregoing embodiments within the technical scope disclosed in the present disclosure Changes can be easily imagined, or equivalent replacements can be made to some of the technical features; and these modifications, changes or replacements do not make the essence of the corresponding technical solutions deviate from the spirit and scope of the technical solutions of the embodiments of the present disclosure, and should be included in this disclosure. within the scope of protection. Therefore, the protection scope of the present disclosure should be defined by the protection scope of the claims.

Claims (10)

1. A virtual network request mapping method, characterized in that, comprising: Receive a mapping request of a virtual network; the mapping request includes one or more of virtual nodes, virtual node constraints, virtual links, and virtual link constraints; Allocate physical nodes and physical links for the virtual network according to the mapping request and a pre-established physical network allocation model; the physical network allocation model is established through a neural network. 2. The method according to claim 1, wherein the physical network allocation model is established in the following manner: Build a mathematical model of the physical network to be allocated; Establishing the network structure of the neural network according to the preset model architecture, the mathematical model and the preset effect index; Acquiring training samples; the training samples include multiple mapping requests of the virtual network, virtual node constraints, virtual links, and virtual link constraints; The training samples are input into the network structure for training to obtain the physical network allocation model. 3. The method according to claim 2, characterized in that, the step of establishing the mathematical model of the physical network to be allocated comprises: Convert the node information of the physical network into the corresponding attribute matrix, and convert the link information of the physical network into the corresponding adjacency matrix; Eliminating the noise of the attribute matrix and the adjacency matrix by using a spectral method to obtain an embedding matrix of the attribute matrix and an embedding matrix of the adjacency matrix; determining an embedding matrix of the physical network according to an embedding matrix of the attribute matrix and an embedding matrix of the adjacency matrix; According to the matrix perturbation theory, the embedding matrix of the physical network is solved to obtain a mathematical model of the physical network; the mathematical model includes a static update model. 4. The method according to claim 2, wherein the preset effect index includes one or more of the operator's long-term average revenue, revenue-to-consumption ratio, and long-term acceptance rate. 5. The method according to claim 3, wherein the step of determining the embedding matrix of the physical network according to the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix comprises: When the correlation between the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix is obtained by the following formula, the projection vector corresponding to the embedding matrix of the attribute matrix and the projection vector corresponding to the embedding matrix of the adjacency matrix : Among them, the constraints are P _A ^(t)′ Y _A ^(t)′ Y _A ^(t) P _A ^(t) +P _X ^(t)′ Y _X ^(t)′ Y _X ^(t) P _X ^(t) =1. Y _A ^(t) and Y _X ^(t) are respectively the embedding matrix of the attribute matrix and the embedding matrix of the adjacency matrix at time t, and Y _A ^(t)′ and Y _X ^(t)′ are respectively Y _A ^{( t)} , the transposition matrix of Y _X ^(t) ; P _A ^(t) and P _X ^(t) are respectively the projection vector corresponding to the embedding matrix of the attribute matrix and the embedding matrix corresponding to the adjacency matrix at time t Projection vector, P _A ^(t) and P _X ^{(t) are} transpose matrices of P _A ⁽ t) and P _X (t) respectively; Indicates that the maximum value of the formula is obtained with P _A ^(t) and P _X ^(t) as variables; When the gradient of the projection vector corresponding to the embedding matrix of the attribute matrix and the projection vector corresponding to the embedding matrix of the adjacency matrix is obtained by the Lagrangian function is zero, the projection vector corresponding to the embedding matrix of the attribute matrix and the The value of the projection vector corresponding to the embedding matrix of the adjacency matrix; The consensus embedding matrix is obtained by the following formula: Y ^(t) = [Y _A ^(t) , Y _X ^(t) ]×P ^(t) Wherein, P ^(t) is a projection vector synthesized by P _A ^(t) and P _X ^(t) , and P ^(t) = [P _A ^(t) , P _X ^(t) ]. 6. A virtual network request mapping device, comprising: A request receiving module, configured to receive a virtual network mapping request; the mapping request includes one or more of virtual nodes, virtual node constraints, virtual links, and virtual link constraints; The physical network allocation module is configured to allocate physical nodes and physical links for the virtual network according to the mapping request and a pre-established physical network allocation model; the physical network allocation model is established through a neural network. 7. The device according to claim 6, wherein the physical network allocation model is established in the following manner: Build a mathematical model of the physical network to be allocated; Establishing the network structure of the neural network according to the preset model architecture, the mathematical model and the preset effect index; Obtain a training sample; the training sample includes a plurality of mapping requests of the virtual network; The training samples are input into the network structure for training to obtain the physical network allocation model. 8. The device according to claim 7, wherein the step of establishing a mathematical model of the physical network to be allocated comprises: Convert the node information of the physical network into the corresponding attribute matrix, and convert the link information of the physical network into the corresponding adjacency matrix; Eliminating the noise of the attribute matrix and the adjacency matrix by using a spectral method to obtain an embedding matrix of the attribute matrix and an embedding matrix of the adjacency matrix; determining an embedding matrix of the physical network according to an embedding matrix of the attribute matrix and an embedding matrix of the adjacency matrix; According to the matrix perturbation theory, the embedding matrix of the physical network is solved to obtain a mathematical model of the physical network; the mathematical model includes a static update model. 9. The device according to claim 7, wherein the preset effect index includes one or more of the operator's long-term average revenue, revenue-to-consumption ratio, and long-term acceptance rate. 10. A device for implementing virtual network request mapping, characterized by comprising a memory and a processor, wherein the memory is used to store one or more computer instructions, and the one or more computer instructions are executed by the processor , to realize the method described in any one of claims 1 to 5.