CN111884854A - Virtual network traffic migration method based on multi-mode hybrid prediction - Google Patents

Abstract

The invention relates to a multi-mode hybrid prediction-based virtual network traffic migration method.A virtual network control platform senses virtual network traffic constantlySimulating the current flow of the link, predicting the flow value of the link in the next period by using historical data, and calculating the bandwidth utilization rate u of each link_ij. Then the link utilization u_ijRespectively with the upper threshold value W_HAnd a lower threshold value W_LA comparison is made. If u is present_ij≥W_HCalculating the overload traffic of the link and increasing the bandwidth value B of the link_l. If the bandwidth utilization rate of the link in one prediction period satisfies u_ij≤W_LAnd if other constraint conditions are met, deleting the virtual link and ensuring the link utilization rate u_ij≤W_HAnd migrating the traffic on the current link to the target virtual link on the basis. The method ensures the prediction accuracy, has shorter operation time and higher prediction efficiency, improves the virtual network flow migration efficiency and can save more bandwidth resources.

Description

A virtual network traffic migration method based on multi-modal hybrid prediction

technical field

The invention relates to a virtual network traffic migration method, in particular to a virtual network traffic migration method based on multi-mode mixed prediction.

Background technique

The document "Din D, Chou C. Virtual topology reconfiguration for mixed-line-rate optical WDM networks under dynamic traffic. Photonic Network Communication, 2015, 30(2): 1-19" discloses a virtual network topology reconfiguration method. Aiming at the problem of virtual network topology reconstruction under dynamic traffic demand, this method proposes a topology reconstruction method to track traffic changes by monitoring the traffic of links, and optimize resource utilization by adding or deleting one or more links. rate and network traffic performance. However, this method still has the following problems:

(1) The method disclosed in the literature has the phenomenon of "topology reconstruction lag". Because the method passively reconstructs the topology by detecting network traffic, it does not predict the future network traffic information, and the problem of virtual network topology reconstruction lag occurs.

(2) This method stipulates that the newly added virtual link cannot be deleted in the next period of time. Although frequent link jitter is avoided to a certain extent, the newly added virtual link may occupy a large amount of bandwidth resources for a long time, resulting in resource waste.

SUMMARY OF THE INVENTION

technical problem to be solved

In order to solve the problems of reconstruction delay and resource waste in the existing virtual network topology reconstruction methods, the present invention proposes a virtual network traffic migration method based on multi-mode hybrid prediction (Virtual Network Traffic Migration Approach Based on Multi-mode Hybrid Prediction, VNTM-MHP).

Technical solutions

A virtual network traffic migration method based on multi-mode mixed prediction, characterized in that the steps are as follows:

Step 1: initialize network parameters, and set the upper and lower thresholds of link utilization to be W _H and W _L respectively;

Step 2: Sense the current traffic of the virtual link, use the multi-mode mixed traffic prediction method based on parameter optimization to predict the traffic value of the next cycle, and calculate the bandwidth utilization u _ij of each link, if u _ij ≥ W _H , the link is stored in the set L _h ; if u _ij ≤ W _L , the link is stored in the set L _v ;

Step 3: For each virtual link l _ij in the set L _h , calculate the link overload traffic T _l =u _ij ·B _ij -W _H ·B _ij , and increase the link bandwidth value B _l =T _l /W _H ; wherein, B _ij is the bandwidth value of the virtual link l _ij ;

Step 4: For each virtual link l _ij in the set L _v , select other shortest paths between nodes i and j and store them in the set L _r ;

Step 5: Calculate the remaining available bandwidth resources of each link in the set L _r in turn. If the remaining bandwidth resources of the kth link satisfy B _k >u _ij ·B _ij ′, B _i ′ _j is the current link to be migrated bandwidth, the traffic flowing through the virtual link l _ij is migrated to the kth virtual link in the set L _r , and the virtual link l _ij is deleted to recover the bandwidth resources;

Step 6: Update the virtual network topology and go to Step 2.

The described multi-mode mixed flow forecasting method based on parameter optimization selection: first, the wavelet decomposition method is used to decompose the flow data into high-frequency detailed time series and low-frequency approximate time series; The optimal sample selection method is to extract the features of the decomposed time series to construct training samples; then use the chaotic model and extreme learning machine neural network to train and predict the detailed time series and approximate time series respectively; finally, use the threshold to calculate the prediction error. Judgment, adaptive trigger combination parameter selection algorithm based on particle swarm optimization.

beneficial effect

A virtual network traffic migration method based on multi-mode hybrid prediction proposed by the present invention utilizes the multi-mode hybrid traffic prediction method based on parameter optimization selection (Multi-mode Hybrid Traffic Prediction Approach Based on Parameter Optimization Selection, MHTP-POS) for the next The periodic network traffic is predicted, and the traffic is migrated in real time according to the traffic prediction result, which saves more bandwidth resources while avoiding the ping-pong effect. While ensuring the prediction accuracy, the method has shorter running time and higher prediction efficiency, improves the virtual network traffic migration efficiency, and can save more bandwidth resources.

Description of drawings

FIG. 1 is a flow chart of the VNTM-MHP method proposed by the present invention.

FIG. 2 is an example diagram of the VNTM-MHP method proposed by the present invention.

FIG. 3 is a flow chart of the MHTP-POS method proposed by the present invention.

FIG. 4 is a comparison diagram of the flow prediction sequence in the present invention and the original sequence.

Fig. 5 is the prediction error of the network traffic sequence by the MHTP-POS method in the present invention.

FIG. 6 is a comparison diagram of bandwidth resources saved by the VNTM-MHP method and the IW method in the present invention.

FIG. 7 shows the bandwidth resources saved by the VNTM-MHP method in the present invention at different link utilization upper limit thresholds _WH .

FIG. 8 shows the bandwidth resources saved by the _VNTM -MHP method in the present invention at different link utilization lower limit thresholds WL.

Detailed ways

Now in conjunction with embodiment, accompanying drawing the present invention is further described:

1. Build the VNTM-MHP method process

The present invention proposes a VNTM-MHP method to solve the problems of reconstruction delay and resource waste in existing virtual network topology reconstruction methods, and the specific process is shown in FIG. 1 .

First, the virtual network control platform senses the current flow of the virtual link at all times, uses historical data to predict the link flow value of the next cycle, and calculates the bandwidth utilization u _ij of each link. The link utilization u _ij is then compared with the upper threshold _WH and the lower threshold W _L respectively. If there is u _ij ≥ W _H , calculate the link overload traffic and increase the link bandwidth value B _l . If the bandwidth utilization of any link in a prediction period satisfies u _ij ≤ W _L and other constraints, delete the virtual link, and on the basis of ensuring link utilization u _ij ≤ W _H Traffic on the current link is migrated to the destination virtual link.

Figure 2 shows an example of virtual network traffic migration. When it is predicted that the bandwidth utilization rate of the link _{la in the next cycle satisfies u ad ≥} W _H , the link overload traffic is calculated and the link bandwidth value _Bad is increased. When it is predicted that the bandwidth utilization rate of the link _{lab in the next cycle satisfies u ab ≤} W _L , and there is sufficient bandwidth resources on the other link 1 _acb from node a to node _b , it can ensure that the bandwidth on the link lab After the traffic is migrated, its bandwidth utilization still satisfies u _acb ≤ W _H . At this time, the traffic flowing through the link lab is migrated to the link la _acb , and the link _lab is _deleted to reclaim the bandwidth resources.

2. Use the MHTP-POS method to predict the network traffic at the next moment

The accuracy of traffic prediction and the time required for prediction have an important impact on the result and efficiency of virtual network traffic migration. In order to improve the traffic prediction accuracy and prediction efficiency, the present invention introduces a multi-mode mixed traffic prediction method based on parameter optimization selection. The method first uses the wavelet decomposition method to decompose the flow data into high-frequency detailed time series and low-frequency approximate time series; Feature extraction to construct training samples; then use chaos model and extreme learning machine neural network to train and predict detailed time series and approximate time series respectively, so as to improve prediction accuracy and prediction efficiency; finally, use threshold to judge prediction error, and adaptively trigger Combination parameter selection algorithm based on particle swarm optimization.

The flow of the multi-mode mixed flow prediction method based on parameter optimization selection is shown in Figure 3, which mainly includes five steps: wavelet decomposition, phase space reconstruction, optimal sample selection, combined parameter optimization selection and flow prediction.

(1) Wavelet decomposition

Since the small-scale network traffic sequence has chaotic characteristics, direct traffic prediction is prone to large prediction errors. Therefore, the present invention adopts the wavelet decomposition method to decompose the network traffic into approximate and detailed time series and then use different models for processing. prediction accuracy. When performing wavelet decomposition, the larger the number of decomposition layers, the more detailed features of network traffic can be observed, but when the number of decomposition layers is too large, the amount of calculation will increase rapidly, and the prediction efficiency will decrease. According to the research, when the number of decomposition layers is 3, the prediction error can basically achieve the expected effect, and at the same time, it has a low computational complexity. Therefore, the present invention decomposes the network traffic sequence into an approximate time sequence AT3 and three detailed time sequences DT1, DT2 and DT3.

(2) Phase space reconstruction

The chaotic time series of network traffic has complex dynamic characteristics, which cannot be accurately described by traditional low-dimensional coordinates. As an important theory for chaotic time series prediction, phase space reconstruction theory incorporates existing data into a descriptive framework by accurately describing the evolution law of hidden chaotic attractors. Based on the chaotic and abrupt characteristics of small-scale network traffic, the present invention selects the delay coordinate state phase space reconstruction based on the embedding theorem, and transforms the small-scale network traffic prediction into a nonlinear time series prediction problem, that is, selecting appropriate parameters m and τ , m is the embedding dimension, τ is the delay time, and they are all positive integers, there is a certain mapping f such that Y=f(X). For the traffic forecast problem:

x _n+1 =f(x _n-(m-1)τ ,x _n-(m-2)τ ,…,x _n-τ ,x _n ) (1)

Among them, x _n+1 is the predicted future network traffic value, {x _n-(m-1)τ , x _n-(m-2)τ ,...,x _n-τ ,x _n } is the history Sample network traffic. Assuming that the length of the flow data is n, after the phase space reconstruction, the learning sample can be obtained:

(3) Optimal sample selection

The nonlinear time series forecasting methods are divided into global forecasting methods and local forecasting methods. The global prediction method uses all the historical data to predict future values, which requires a large amount of computation and is complicated to implement. The local prediction method only selects some suitable historical data to predict the future value, and the complexity is low, and under the same embedding dimension, the performance of the local prediction method is better than that of the global prediction method. Therefore, the present invention uses the local prediction method to predict the future network traffic.

By reconstructing the phase space of historical flow data, in the chaotic time series, the most relevant information to the predicted sample is in the sample point with the closest Euclidean distance, and there is a great distance correlation between the two. Therefore, the k training samples with the nearest Euclidean distance to the predicted samples are selected to predict the traffic sequence.

x _t is the point to be predicted in the phase space, and x _n is the neighboring point of x _t in the phase space. Then the Euclidean distance s between x _t and x _n is expressed as:

s=||x _t -x _n || ₂ (3)

The number of training samples k is of great significance in the local prediction method, it not only affects the accuracy of the prediction results, but also affects the complexity of the prediction method. When the number of training samples k is too small, the prediction accuracy will be reduced, but if the number of training samples is too large, the phenomenon of "overfitting" may occur, which may not only reduce the prediction accuracy, but also increase the prediction complexity.

(4) Combination parameter selection based on particle swarm optimization

When using some historical information to predict network traffic, the parameters m and τ in the phase space reconstruction and the number of training samples k have important influences on the traffic prediction results. In order to better select combination parameters, the present invention proposes an optimal combination parameter selection algorithm based on particle swarm optimization. First define particle-related parameters and operations.

1) Particle position: The particle position vector D _i =[d _i1 ,d _i2 ,d _i3 ] is defined as the parameter selection scheme, d _i1 , d _i2 and d _i3 represent the values of parameters m, τ and k respectively, d _i1 ∈ M, d _i2 ∈ N, d _i3 ∈ K.

2) Particle velocity: The particle velocity vector V _i =[v _i1 ,v _i2 ,v _i3 ] is defined as the parameter adjustment decision, v _i1 ,v _i2 ,v _i3 are binary variables, if v _i1 ,v _i2 ,v _i3 If it is 0, it means that the parameter needs to be reselected.

3) The fitness f(D _i ) represents the flow prediction error of the particle selection scheme.

4) Subtraction Θ: When two position vectors are subtracted, if the values in the corresponding dimensions are the same, the difference is 1, otherwise it is 0. For example, (1,2,3)Θ(1,2,4)=(1,1,0).

5) Addition ⊕: P _i V _i ⊕ P _j V _j is used to obtain the adjustment decision of the parameter selection scheme. Among them, P _i V _i and P _j V _j respectively represent maintaining the value of each dimension of V _i with the probability of P _i and maintaining the value of each dimension of V _j with the probability of P _j , and P _i +P _j =1(0≤ P _i ≤ 1, 0 ≤ P _j ≤ 1). For example, 0.1(1,0,0)⊕0.9(1,1,0)=(1,*,0), where * means it is uncertain whether this dimension is 0 or 1. In this example, * means that this dimension takes 0 with probability 0.1 and 1 with probability 0.9.

用于获得新的参数选择方案。参数选择方案D_i按照调整决策V_i进行调整。例如，

表明方案中第二个参数需要调整。6) Multiplication

Used to obtain new parameter selection schemes. The parameter selection scheme D _i is adjusted according to the adjustment decision V _i . E.g,

Indicates that the second parameter in the scheme needs to be adjusted.

The basic formulas that define the position and velocity update of the particle swarm optimization algorithm are as follows:

Wherein, P ₁ , P ₂ and P ₃ are constants, and P ₁ +P ₂ +P ₃ =1. D _pb and D _gb are the particle's own historical best position and the neighborhood historical best position, respectively.

Therefore, the specific steps of the optimal parameter selection algorithm based on particle swarm optimization are as follows:

Step 1: Initialize network traffic information, set the value ranges of parameters m, τ and k to be M, N and K respectively, the maximum number of iterations of the algorithm MG, and the particles randomly generate initial position parameter _{Di and velocity parameter V i .}

Step 2: Calculate the fitness f(D _i ) of all particles to obtain D _pb and D _gb .

Step 3: According to equations (4) and (5), update the particle position and velocity parameters.

Step 4: For each particle, if f(D _i )<f(D _i ), then D _pb =D _i ; if f(D _pb )<f(D _gb ), then D _gb =D _pb .

Step 5: If the number of iterations is less than MG, go to Step 3; otherwise, go to Step 6.

Step 6: Output the optimization parameter selection scheme.

(5) Traffic forecast

For the approximate time series and the detailed time series after phase space reconstruction, the present invention adopts different training prediction models to analyze and process them. For the detailed time series, the chaotic model is used to train and predict it, and the predicted sequence is obtained. For approximate time series, extreme learning machine neural network is used for training prediction. The extreme learning machine neural network is a kind of single hidden layer feedforward neural network. It is based on the function approximation theory, randomly selects the input weights during training, and determines the output weights by analytical methods, which can greatly improve the artificial neural network. It has the advantages of simple training, simple structure, and fast learning convergence speed.

The prediction sequence can be obtained by linearly superposing the detailed time series processed by the chaos model and the approximate time series processed by the extreme learning machine neural network.

3. Performance evaluation and analysis

The invention uses Matlab as the simulation platform, and designs two groups of simulation experiments. The first set of simulation experiments verifies the performance of MHTP-POS. The second set of simulation experiments verifies the performance of VNTM-MHP.

(1) Experimental environment settings

The present invention adopts the actual flow LBL-tcp-3.tcp as the simulation data, the original sampling time is 2 hours, and the data is 1,789,995. The original traffic is resampled at 1-second intervals to obtain a traffic sequence with a length of 7199, and normalized to obtain the actual network traffic time series for simulation. The value range of the embedding dimension m is set to [5,25 ], the value range of the delay time τ is set to [1, 10], and the value range of the sample number k is set to [10, 400].

(2) MHTP-POS method performance verification

First, use the MHTP-POS method proposed by the present invention to predict the traffic within 200-800s, and analyze the performance of the MHTP-POS method. The results are shown in Figures 4 and 5.

It can be seen from Figure 4 that the traffic forecast sequence and the original sequence can be accurately fitted. The MHTP-POS method decomposes the chaotic sequence into approximate sequence and detail sequence through wavelet decomposition, and uses different training models to process the two sequences separately to achieve accurate prediction of network traffic and obtain good prediction results.

It can be seen from Figure 5 that although the training samples are selected through phase space reconstruction and parameter optimization, there will still be a certain prediction error when affected by noise or when a burst traffic sequence occurs. It can be seen from Figure 5 that the maximum error value of the network traffic predicted by the MHTP-POS method is about 0.035, which is within the acceptable range.

(3) Performance Simulation of Virtual Network Traffic Migration Method

1) Performance comparison of different virtual network traffic migration methods

Figure 6 shows the comparison of bandwidth resources saved by different virtual network traffic migration methods. It can be seen from Figure 6 that the IW method does not delete newly added virtual links for a period of time in order to avoid the ping-pong effect during traffic migration. Some virtual links with low bandwidth utilization will occupy bandwidth resources for a long time, resulting in waste of resources and less bandwidth resources saved. The VNTM-MHP method introduces the traffic prediction function, uses the hybrid traffic prediction model to predict the traffic in the next cycle, and performs virtual network traffic migration according to the prediction result, which saves more bandwidth resources.

2) The effect of link utilization threshold setting on the performance of VNTM-MHP method

Figures 7 and 8 respectively show the variation of bandwidth resources saved by the VNTM-MHP method when different upper and lower thresholds of link utilization are set.

Figure 7 shows the variation of bandwidth resources saved by the VNTM-MHP method when the upper limit of the link utilization threshold _WH is 0.7, 0.8 and 0.9 respectively. It can be seen from FIG. 7 that with the increase of _WH , the saved bandwidth resources gradually increase. When _WH increases, the number of congested virtual links decreases, and each virtual link has more resources to carry traffic migrated from virtual links with low bandwidth utilization, thus saving more bandwidth resource.

Figure 8 shows the variation of bandwidth resources saved by the VNTM-MHP method when the lower limit of the link utilization threshold W _L is 0.1, 0.2 and 0.3 respectively. It can be seen from FIG. 8 that as W _L increases, the saved bandwidth resources also increase. As W _L gradually increases, more virtual links meet the conditions for link deletion, the number of deleted virtual links increases, and the released bandwidth resources also increase.

Claims (2)

1. A virtual network traffic migration method based on multi-mode hybrid prediction is characterized by comprising the following steps:

step 1: initializing network parameters, and respectively setting an upper limit threshold and a lower limit threshold of link utilization rate as W_HAnd W_L；

Step 2: sensing the current flow of the virtual link, predicting the flow value of the link in the next period by using a multi-mode mixed flow prediction method based on parameter optimization selection, and calculating the bandwidth utilization rate u of each link_ijIf u is_ij≥W_HThen store the link into set L_h(ii) a If u_ij≤W_LThen store the link into set L_v；

And step 3: for set L_hEach virtual link l in_ijCalculating the link overload traffic T_l＝u_ij·B_ij-W_H·B_ijAnd increasing the link bandwidth value B_l＝T_l/W_H(ii) a Wherein, B_ijFor a virtual link l_ijThe bandwidth value of (a);

and 4, step 4: for set L_vEach virtual link l in_ijSelecting other shortest paths between nodes i and j and storing them in set L_r；

And 5: sequentially computing the set L_rThe residual available bandwidth resources of each link in the system, if the residual bandwidth resources of the kth link exist, the condition B is satisfied_k>u_ij·B′_ij，B′_ijFor the current link bandwidth to be migrated, flow will flow through the virtual link l_ijTraffic of (2) to set L_rAnd deleting the virtual link l_ijRecovering bandwidth resources;

step 6: and updating the virtual network topology and executing the step 2.

2. The method according to claim 1, wherein the multi-mode hybrid traffic prediction method based on parameter optimization selection comprises: firstly, decomposing flow data into a high-frequency detail time sequence and a low-frequency approximate time sequence by adopting a wavelet decomposition method; then, performing feature extraction on the decomposed time sequence by using a phase space reconstruction and optimal sample selection method based on particle swarm optimization to construct a training sample; then, training and predicting the detailed time sequence and the approximate time sequence by adopting a chaotic model and an extreme learning machine neural network respectively; and finally, judging the prediction error by using a threshold value, and adaptively triggering a combination parameter selection algorithm based on particle swarm optimization.

Images