CN102724078A - End-to-end network flow reconstruction method based on compression sensing in dynamic network - Google Patents

Abstract

The invention discloses an end-to-end network flow reconstruction method based on compression sensing in a dynamic network. In a large-scale IP backbone network, the OD flow is selected by a random walk method; the flow value of partial OD flow acquired by a router subset is described by constructing a sparse flow matrix; a compressing sensing reconstruction module is established by adopting a main information analysis method; a relationship between the OD flow generated by the router sublet and all the end-to-end OD flow in the IP backbone network is descried by using the module, and further all the end-to-end OD flow of the whole IP backbone network is determined. The method can more accurately acquire end-to-end network flow detail characteristic, cannot consume mass hardware resources, can track the dynamic changes of the OD flow in a real time manner, and the reconstruction error is less.

Description

End-to-end network flow reconstruction method based on compressed sensing in dynamic network

Technical Field

The invention belongs to the field of flow measurement and analysis under a dynamic network, and particularly relates to an end-to-end network flow reconstruction method based on compressed sensing under the dynamic network.

Background

In recent years, with the rapid development of the internet, an increasing number of network applications provide convenient services to users. But also makes the network increasingly complex. It is also increasingly difficult for network operators to manage and control networks. The traffic matrix is the most important input parameter in network traffic engineering, represents all end-to-end traffic in the network, and completely describes the traffic distribution, and provides the current network state for the network manager, but it is difficult to accurately obtain the traffic matrix in practical application.

Even though the traffic matrix is very important for the network operator, it is very difficult to accurately obtain an estimate of the traffic matrix. Therefore, the traffic matrix estimation becomes a very challenging research topic. In recent years, a great deal of research results have emerged. Vardi proposed the use of network tomography to solve the end-to-end traffic reconstruction problem, and this method was subsequently widely used and used to study IP network internal features. For the network tomography method, the end-to-end flow can be reconstructed through Poisson distribution and Gaussian distribution, but the spatial and temporal correlation of the end-to-end flow cannot be captured; conti et al estimate the flow matrix by calculating Hurst values using a maximum likelihood estimation algorithm. Nucci et al adds weights to the route configuration derived from multiple routing information to obtain a small traffic matrix estimation error. Zhang et al propose to use the gravity field model to describe the characteristic of the current end-to-end flow, and overcome the problem of high morbidity by obtaining additional constraint information; lakhina et al propose a principal component analysis method to directly measure and construct an end-to-end flow reconstruction model; soule et al propose an iterative Bayesian inversion algorithm to reconstruct end-to-end flow based on an independent identically distributed Poisson model assumption of end-to-end flow; liang et al propose a pseudo-likelihood reconstruction method that uses an improved EM algorithm to decompose the problem into several sub-problems containing one OD pair, reducing the error in the estimation accuracy.

Although statistical model correlation techniques can obtain an estimated value of a traffic matrix and are widely used in practice, these methods still cannot accurately estimate the traffic matrix. In fact, measuring end-to-end network traffic directly is more accurate than traffic estimation, and device manufacturers offer a large number of measurement techniques and devices, most typically Netflow. Netflow can obtain an end-to-end network traffic value by extracting and analyzing the source and destination IP addresses, source and destination port numbers, and protocol numbers of the data packets. But measuring each OD flow using NetFlow is impractical, if not impossible. This is because the ports of the router will consume a lot of hardware resources when running the NetFlow program, and the direct measurement will cause extra communication overhead. This reduces the store-and-forward efficiency of the router, thus increasing network latency and easily causing network congestion.

Disclosure of Invention

Aiming at the defects of the prior art, the invention provides an end-to-end network flow reconstruction method based on compressed sensing in a dynamic network, so as to achieve the purposes of reducing hardware resources, tracking the dynamic change of an OD flow in real time and reducing reconstruction errors.

A compression sensing-based end-to-end network flow reconstruction method in a dynamic network comprises the following steps:

step 1, setting the length and the random walk times of a system aiming at OD stream random walks;

step 2, in a large-scale IP backbone network, selecting OD flows in a random walk mode, and describing the opening and closing states of all routers by adopting a method for constructing a Boolean sparse measurement matrix according to the selected OD flows;

step 3, describing flow values of part of OD flows collected by a router subset by adopting a method for constructing a sparse flow matrix, wherein the router subset is a router in all opening states, and calculating a measurement value according to a Boolean sparse measurement matrix and the constructed sparse flow matrix;

and 4, according to the sparse measurement matrix constructed in the step 3 and the measurement value obtained by calculation, adopting a principal component analysis method to construct a compressed sensing reconstruction model, describing the relationship between the OD flows generated by the router subset and all end-to-end OD flows in the large-scale IP backbone network by using the model, and further determining all end-to-end OD flow in the whole IP backbone network.

The method for constructing the Boolean sparse measurement matrix in the step 2 comprises the following steps:

step 2-1, constructing an OD flow complete graph, wherein the complete graph comprises vertexes and edges, and the number of the vertexes is equal to the number of the OD flows;

step 2-2: setting an initial value of the random walk measurement times;

step 2-3: selecting a vertex as a unified starting point;

step 2-4: executing uniformly distributed random walks on the complete graph, and according to points found by the random walks, the state of the router corresponding to the points is an open state, otherwise, the state is a closed state;

step 2-5: if the random walk measurement times are smaller than the initialization set random walk measurement times, returning to the step 2-3; if the number of random walk measurements is greater than or equal to the number of initial random walk measurements, executing step 2-6;

step 2-6: and saving the Boolean sparse measurement matrix.

The Boolean sparse measurement matrix in the step 1 accords with a constraint equidistance criterion; the number of rows in the boolean sparse measurement matrix represents the number of times the large-scale IP backbone network is randomly walked, and the number of columns in the boolean sparse measurement matrix represents the total number of OD flows in the large-scale IP backbone network.

The calculation of the measured values described in step 3 satisfies the following formula:

measured value = boolean sparse measurement matrix x sparse flow matrix

The invention has the advantages that:

the invention relates to an end-to-end network flow reconstruction method based on compressed sensing in a dynamic network, which realizes end-to-end network flow reconstruction of a large IP backbone network by a partial direct measurement mode. The method can more accurately acquire the detailed characteristics of the end-to-end network flow, does not consume a large amount of hardware resources, can track the dynamic change of the OD flow in real time, and has smaller reconstruction error.

Drawings

Fig. 1 is a flowchart of a method for reconstructing an end-to-end network traffic based on compressive sensing in a dynamic network according to an embodiment of the present invention;

FIG. 2 is a schematic view of a flow reconstruction framework according to an embodiment of the present invention;

FIG. 3 is a flow chart of constructing a Boolean sparse measurement matrix according to one embodiment of the present invention;

FIG. 4 is a schematic diagram of a Boolean sparse measurement matrix constructed by random walk according to an embodiment of the present invention;

wherein 4-1 is a complete diagram;

FIG. 5 is a schematic representation of the rank variation of the NMAE with flow matrix according to an embodiment of the present invention;

FIG. 6 is a schematic representation of NMAE as a function of random walk length in accordance with an embodiment of the present invention;

FIG. 7 is a diagram illustrating the number of OD flows that need to be measured directly according to one embodiment of the present invention;

FIG. 8 is a schematic diagram illustrating the estimation of the 30 th and 60 th OD flow traffic matrices according to an embodiment of the present invention; a) a schematic diagram of the 30 th OD flow traffic matrix estimation; b) a schematic diagram of the 60 th OD flow matrix estimation;

FIG. 9 is a diagram illustrating a spatial relative error and a temporal relative error according to an embodiment of the present invention; a) is a schematic diagram of spatial relative error; b) is a schematic diagram of relative error of time;

FIG. 10 is a diagram illustrating a cumulative distribution function of spatial relative error and temporal error according to an embodiment of the present invention; a) is a schematic diagram of a spatial relative error cumulative distribution function; b) is a diagram of a time relative error accumulation distribution function.

Detailed Description

The following further describes the embodiments of the present invention with reference to the drawings.

Firstly, constructing a Boolean sparse measurement matrix according to random walk, and obeying RIP (restricted equal distance) criterion; then collecting part of end-to-end flow by using fewer router ports corresponding to the Boolean sparse measurement matrix, and calculating a measurement value according to the Boolean sparse measurement matrix, the sparse flow matrix and the linear relation among the measurement values; and finally, carrying out singular value decomposition on the flow matrix by utilizing a PCA (principal component analysis) model to meet the sparsification condition, and reconstructing all OD flow matrixes based on compressed sensing.

The real flow data of the Abilene backbone network is used in the embodiment of the invention, the real flow data comprises 12 nodes, 30 internal links, 24 external links and 144 end-to-end flows, and the simulation data adopts 5min time intervals and totals 2016 moments.

The traffic matrix in the Abilene backbone network can be as shown in equation (1),

$M=\left[\begin{array}{cccc}{m}_1\left(1\right)& m_1\left(2\right)& ...& m_1\left(T\right)\\ m_2\left(1\right)& m_2\left(2\right)& ...& m_2\left(T\right)\\ .& .& & .\\ .& .& & .\\ .& .& & .\\ m_N\left(1\right)& m_N\left(2\right)& ...& m_N\left(T\right)\end{array}\right]---\left(1\right)$

m in the formula (1) represents a traffic matrix, and rows of the matrix M represent the total amount of traffic from a source node to a destination node in the large-scale Abilene backbone network.

Wherein, the number of network nodes is N, and the number of OD streams N = N². Thus, M is an N × T traffic matrix.

m_j(t): represents the t-th time of the j-th OD flow;

m (t): the t-th column representing M;

j∈{1,2,…,N}；

t∈{1,2,…,T}。

the compressive sensing theory must satisfy two characteristics: firstly, the measurement matrix meets the RIP (restricted equal distance) criterion; one is that the traffic matrix is a sparse matrix. The following description is made with respect to the requirement for a matrix in the compressive sensing theory in conjunction with equation (2).

Due to the redundancy of the signals, it is assumed that the vector s can be expressed as:

wherein,

s is a discrete signal N-dimensional space R^NAn N × 1 order column vector;

x_ieach column element being s, i ═ 1,2,3, …, N;

is a basis vector that is a function of,

is R^NA set of orthogonal bases.

If and only if the signal is composed of K (K)<<N) order basis vector

The signal s is sparse in the linear combination of the components, i.e. { x in equation (2) }_iOnly K elements are non-zero. The signal s is considered compressible in compressed sensing theory. K also becomes the sparsity of the signal.

In the embodiment of the invention, the length of the random walk is set as r, the measurement times are set as p, wherein

In the embodiment of the invention, the random walk times p =19, the random walk step length r =11, and the rank q =5 (q = K) of the flow matrix, and the Boolean sparse measurement matrix constructed by the method obeys the RIP criterion.

Fig. 1 is a flowchart of a method for reconstructing an end-to-end network traffic based on compressive sensing in a dynamic network according to an embodiment of the present invention, including the following steps:

step 1, setting the length of random walk, the random walk times and the rank of a flow matrix for a router in a system;

the rank of the flow matrix is the sparsity meeting the compressed sensing theory matrix, and the rank q of the flow matrix in the embodiment = 5;

step 2, in a large-scale IP backbone network, selecting OD flows in a random walk mode, and describing the opening and closing states of all routers by adopting a method for constructing a Boolean sparse measurement matrix according to the selected OD flows;

in the embodiment of the invention, a router is selected by adopting a random walk mode, the selected router forms a router subset, the opening or closing state of the selected router subset is described by adopting a method for constructing a Boolean sparse measurement matrix, and a p multiplied by N Boolean sparse measurement matrix A is constructed according to p times of random walks. Fig. 2 is a schematic diagram of a flow-aware reconfiguration framework according to the present invention, in which a network operator collects end-to-end network traffic data on partially operating routers by controlling network devices (including hardware and software) through NetFlow, that is, a network management center controls the routers to be turned on or off, and collects traffic data from NetFlow operating on each router interface. After part of end-to-end network traffic is collected, all OD flow traffic matrixes are recovered in a network management center. Fig. 3 is a flowchart of constructing a boolean sparse measurement matrix according to an embodiment of the present invention, which specifically includes the following steps:

step 2-1, an OD flow complete graph G (V, E) is constructed (as in the complete graph 4-1 in FIG. 4), wherein V and E represent the set of graph vertices and edges, respectively. The number of vertices is equal to the number of OD flows N;

step 2-2: setting a measurement time parameter c_iteration=1；

Step 2-3: selecting a vertex as a unified starting point;

step 2-4: executing uniformly distributed random walks on G (V, E), and according to the points found by the random walks, the state of the router corresponding to the points is an open state (namely 1), otherwise, the state is a closed state (namely 0);

fig. 4 is a schematic diagram of a boolean sparse measurement matrix constructed by random walk in the present invention, wherein black vertices represent N OD streams, and the vertices are randomly walked. In the embodiment of the present invention, the vertices 10,15,18,70, and 72 are vertices found by random walk, and 10,15,18,70, and 72 OD flows are measured using NetFlow. a is_iFor a row of the boolean sparse measurement matrix constructed for random walk, a p × N (19 × 144) boolean sparse measurement matrix a is obtained by p (p = 19) random walks, as follows:

$A=\left[\begin{array}{c}{a}_1\\ a_2\\ .\\ .\\ .\\ a_p\end{array}\right]---\left(3\right)$

a_iis a row vector of:

a_i=[a_i1,a_i2,a_i3,…,a_iN],i∈{1,2,3,…,p}. (4)

when a vertex is found by random walk, its corresponding matrix element value is 1. In FIG. 3, a_iThe 10 th, 15 th, 18 th, 70 th and 72 th element values are 1, the rest are 0, namely, the setting a_i10,a_i15，a_i18，a_i70And a_i72“1”。

Step 2-5: if c is_iteration<p, then set up c_iteration=c_iteration+1, execution returns to step 204; if c is_iteration>p, go to step 207;

step 2-6: and saving the Boolean sparse measurement matrix.

Step 3, describing flow values of part of OD flows collected by a router subset by adopting a method for constructing a sparse flow matrix, wherein the router subset is a router in all opening states, and calculating a measurement value according to a Boolean sparse measurement matrix and the constructed sparse flow matrix;

in the embodiment of the invention, all network flows are subjected to zero-mean processing according to formulas (5) to (7).

In the embodiment of the invention, a section of historical flow data is intercepted as prior information, and M is used_hisAnd (4) showing. The zero-mean process is expressed as:

M'=M_his-M^mean (5)

wherein M' is a sparse flow matrix after zero-mean processing;

M_hisa historical traffic data matrix;

$M^{\mathrm{mean}}=\left[\begin{array}{c}{\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="HDA00001834071600042.png,HDA00001834071600051.png"\; state="\{\{state\}\}">m</figure-callout>}}_1^{\mathrm{mean}},{\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="HDA00001834071600042.png,HDA00001834071600051.png"\; state="\{\{state\}\}">m</figure-callout>}}_1^{\mathrm{mean}},{\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="HDA00001834071600042.png,HDA00001834071600051.png"\; state="\{\{state\}\}">m</figure-callout>}}_1^{\mathrm{mean}},...,{\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="HDA00001834071600042.png,HDA00001834071600051.png"\; state="\{\{state\}\}">m</figure-callout>}}_1^{\mathrm{mean}}\\ .\\ .\\ .\\ m_N^{\mathrm{mean}},m_N^{\mathrm{mean}},m_N^{\mathrm{mean}},...,m_N^{\mathrm{mean}}\end{array}\right]---\left(6\right)$

equation (6) is an N × T matrix whose elements are defined as follows:

<math> <mrow> <msubsup> <mi>m</mi> <mi>j</mi> <mi>mean</mi> </msubsup> <mo>=</mo> <mfrac> <mn>1</mn> <mi>T</mi> </mfrac> <munderover> <mi>&Sigma;</mi> <mrow> <mi>t</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>T</mi> </munderover> <msub> <mi>m</mi> <mi>j</mi> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>7</mn> <mo>)</mo> </mrow> </mrow> </math>

wherein: t is the length of intercepting the historical flow;

in the embodiment of the invention, the measurement value Y is calculated by using the historical flow matrix according to the formulas (8) to (10).

the measured value y (t) at time t.

<math> <mrow> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mi>y</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>y</mi> <mn>2</mn> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <msub> <mi>y</mi> <mi>p</mi> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> <mo>=</mo> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mi>a</mi> <mn>1</mn> </msub> </mtd> </mtr> <mtr> <mtd> <msub> <mi>a</mi> <mn>2</mn> </msub> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <msub> <mi>a</mi> <mi>p</mi> </msub> </mtd> </mtr> </mtable> </mfenced> <mo>&times;</mo> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mi>m</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>m</mi> <mn>2</mn> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <msub> <mi>m</mi> <mi>N</mi> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> <mo>.</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>8</mn> <mo>)</mo> </mrow> </mrow> </math>

The formula (8) is equivalent to,

y(t)=A×m(t) (9)

for all moments, there is the following equation:

<math> <mrow> <mi>Y</mi> <mo>=</mo> <mi>A</mi> <mo>&times;</mo> <msup> <mi>M</mi> <mo>&prime;</mo> </msup> </mrow> </math>

<math> <mrow> <mo>=</mo> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mi>a</mi> <mn>1</mn> </msub> </mtd> </mtr> <mtr> <mtd> <msub> <mi>a</mi> <mn>2</mn> </msub> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <msub> <mi>a</mi> <mi>p</mi> </msub> </mtd> </mtr> </mtable> </mfenced> <mo>&times;</mo> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mi>m</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> </mtd> <mtd> <msub> <mi>m</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mn>2</mn> <mo>)</mo> </mrow> </mtd> <mtd> <mo>.</mo> <mo>.</mo> <mo>.</mo> </mtd> <mtd> <msub> <mi>m</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mi>T</mi> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>m</mi> <mn>2</mn> </msub> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> </mtd> <mtd> <msub> <mi>m</mi> <mn>2</mn> </msub> <mrow> <mo>(</mo> <mn>2</mn> <mo>)</mo> </mrow> </mtd> <mtd> <mo>.</mo> <mo>.</mo> <mo>.</mo> </mtd> <mtd> <msub> <mi>m</mi> <mn>2</mn> </msub> <mrow> <mo>(</mo> <mi>T</mi> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> <mtd> <mo>.</mo> </mtd> <mtd> </mtd> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> <mtd> <mo>.</mo> </mtd> <mtd> </mtd> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> <mtd> <mo>.</mo> </mtd> <mtd> </mtd> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <msub> <mi>m</mi> <mi>N</mi> </msub> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> </mtd> <mtd> <msub> <mi>m</mi> <mi>N</mi> </msub> <mrow> <mo>(</mo> <mn>2</mn> <mo>)</mo> </mrow> </mtd> <mtd> <mo>.</mo> <mo>.</mo> <mo>.</mo> </mtd> <mtd> <msub> <mi>m</mi> <mi>N</mi> </msub> <mrow> <mo>(</mo> <mi>T</mi> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>10</mn> <mo>)</mo> </mrow> </mrow> </math>

the measured value Y, the boolean sparse measurement matrix a, and the sparse traffic matrix M' are p × T, p × N, and N × T matrices, respectively.

Since a is a sparse random matrix, we can find the measurement value Y by knowing the element value corresponding to a in the matrix M' in equation (10).

In the embodiment of the present invention, a union of OD flow sets of all random walk measurements is obtained by equation (11).

Suppose that

Represents the set of OD flows that need to be measured by the ith random walk, all the necessary OD flows are represented as:

<math> <mrow> <mfenced open='{' close=''> <mtable> <mtr> <mtd> <msup> <mi>S</mi> <mi>f</mi> </msup> <mo>=</mo> <msubsup> <mo>&cup;</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>p</mi> </msubsup> <msubsup> <mi>S</mi> <mi>i</mi> <mi>f</mi> </msubsup> </mtd> </mtr> <mtr> <mtd> <mi>p</mi> <mo>&le;</mo> <mi>N</mi> </mtd> </mtr> </mtable> </mfenced> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>11</mn> <mo>)</mo> </mrow> </mrow> </math>

wherein: s^fRepresenting the union of the OD flows generated from the first random walk to the p-th random walk;

represents the set of OD flows that need to be measured by the ith random walk;

thus, all the necessary OD streams are generated

The number of the corresponding necessary OD flows is

Then the traffic matrix

<math> <mrow> <mover> <mi>M</mi> <mover> <mo>&OverBar;</mo> <mo>&OverBar;</mo> </mover> </mover> <mo>=</mo> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mi>m</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>m</mi> <mn>2</mn> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <mo>.</mo> </mtd> </mtr> <mtr> <mtd> <msub> <mi>m</mi> <mi>N</mi> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>12</mn> <mo>)</mo> </mrow> </mrow> </math>

Wherein:

is a sparse matrix containing the necessary OD streams;

each row represents an OD stream time series, the extraction requiring direct measurement

Strip OD stream, the remaining OD streams correspond

Behavior 0 of the matrix. In equation (10), since A is a Boolean sparse measurement matrix, it is only necessary to know the individual rows in MY can be obtained. That is Y = A × M' is equivalent to

The method of selecting a subset of OD flows to be measured directly is exemplified in detail below. As shown in equation (13):

<math> <mrow> <mfenced open='' close=''> <mtable> <mtr> <mtd> <mfenced open='' close=''> <mtable> <mtr> <mtd> <mi>Y</mi> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> <mtd> <msub> <mi>A</mi> <mrow> <mo>(</mo> <mn>5</mn> <mo>&times;</mo> <mn>10</mn> <mo>)</mo> </mrow> </msub> </mtd> <mtd> <mi>m</mi> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> </mtd> </mtr> <mtr> <mtd> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mi>y</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>y</mi> <mn>2</mn> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>y</mi> <mn>3</mn> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>y</mi> <mn>4</mn> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>y</mi> <mn>5</mn> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> <mo>=</mo> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <mn>0001010100</mn> </mtd> </mtr> <mtr> <mtd> <mn>0001100000</mn> </mtd> </mtr> <mtr> <mtd> <mn>1000010000</mn> </mtd> </mtr> <mtr> <mtd> <mn>1000110000</mn> </mtd> </mtr> <mtr> <mtd> <mn>0001000000</mn> </mtd> </mtr> </mtable> </mfenced> <mo>&times;</mo> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mi>OD</mi> <mn>1</mn> </msub> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <msub> <mi>OD</mi> <mn>4</mn> </msub> </mtd> </mtr> <mtr> <mtd> <msub> <mi>OD</mi> <mn>5</mn> </msub> </mtd> </mtr> <mtr> <mtd> <msub> <mi>OD</mi> <mn>6</mn> </msub> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <msub> <mi>OD</mi> <mn>8</mn> </msub> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> </mfenced> </mtd> </mtr> </mtable> </mfenced> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>13</mn> <mo>)</mo> </mrow> </mrow> </math>

in the formula, a boolean sparse measurement matrix a is a sparse matrix composed of "1" or "0", the row number of a represents the number of random walks, and the column number represents the OD flow traversed by each random walk. At any time t, the OD stream to be measured is indexed by a "1" in the column element of matrix a. Then a (5 rows and 10 columns) in fig. 4 is a boolean sparse measurement matrix, i.e. random walk 5 times, and the number of OD streams to traverse is 10. OD flows respectively indexed by using the column element '1' in the A for the first time are divided into OD4, OD6 and OD 8; OD flows indexed for the second time are OD4, OD 5; by analogy, the total OD flows to be measured obtained by 5 random walks are: OD1, OD4, OD5, OD6 and OD 8.

And 4, according to the sparse measurement matrix constructed in the step 3 and the measurement value obtained by calculation, adopting a PCA (principal component analysis) method to construct a compressed sensing reconstruction model, describing the relationship between the OD flow generated by the router subset and all end-to-end OD flows in the large-scale IP backbone network by using the model, and further determining all end-to-end OD flow in the whole IP backbone network.

In order to meet the requirement of compressed sensing on the sparsification characteristic of the traffic matrix, the PCA model is used for the historical traffic matrix in the embodiment of the invention

Singular value decomposition is performed.

Step 4-1: performing singular value decomposition on the measured value Y;

the principle of singular value decomposition is further explained below with reference to equations (14) to (17).

The Principal Component Analysis (PCA) has the main idea of projecting high dimensional data into a lower dimensional space. The m multiplied by n order flow matrix L in the PCA model is expressed as

L=U∑V^T， (14)

Wherein: u is an orthogonal matrix;

UU^Tor U^TU is an identity matrix;

Σ is a singular value of a diagonal matrix whose diagonal tuple value is L;

v is L^TA feature vector of L;

L^Tis the transpose of L.

In practice, the formula (14) is that L utilizes an orthogonal baseU Σ is projected into space. The columns of the L matrix are basis vectors σ_ku_kThe normalized basis vector is expressed as:

<math> <mrow> <msub> <mi>u</mi> <mi>k</mi> </msub> <mo>=</mo> <mfrac> <msub> <mi>Lv</mi> <mi>k</mi> </msub> <msub> <mi>&sigma;</mi> <mi>k</mi> </msub> </mfrac> <mo>,</mo> <mi>k</mi> <mo>=</mo> <mn>1,2</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mi>min</mi> <mrow> <mo>(</mo> <mi>m</mi> <mo>,</mo> <mi>n</mi> <mo>)</mo> </mrow> <mo>,</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>15</mn> <mo>)</mo> </mrow> </mrow> </math>

wherein: u. of_k，v_kK columns representing U and V, respectively;

min (m, n) represents the rank of the matrix L;

σ_kit is the singular values of the matrix L that represent the energy characteristics of L.

To facilitate understanding of the low rank approximation process, equation (14) may be expressed as:

<math> <mrow> <mi>L</mi> <mo>=</mo> <msup> <mi>U&Sigma;V</mi> <mi>T</mi> </msup> <mo>=</mo> <munderover> <mi>&Sigma;</mi> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow> <mi>min</mi> <mrow> <mo>(</mo> <mi>m</mi> <mo>,</mo> <mi>n</mi> <mo>)</mo> </mrow> </mrow> </munderover> <msub> <mi>&sigma;</mi> <mi>k</mi> </msub> <msub> <mi>u</mi> <mi>k</mi> </msub> <msubsup> <mi>v</mi> <mi>k</mi> <mi>T</mi> </msubsup> <mo>,</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>16</mn> <mo>)</mo> </mrow> </mrow> </math>

therefore, large singular values can be selected to approximate the true matrix, and this process can be expressed by the mathematical formula:

<math> <mrow> <mover> <mi>L</mi> <mo>^</mo> </mover> <mo>=</mo> <munderover> <mi>&Sigma;</mi> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>q</mi> </munderover> <msub> <mi>&sigma;</mi> <mi>k</mi> </msub> <msub> <mi>u</mi> <mi>k</mi> </msub> <msubsup> <mi>v</mi> <mi>k</mi> <mi>T</mi> </msubsup> <mo>.</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>17</mn> <mo>)</mo> </mrow> </mrow> </math>

wherein: the constant q < min (m, n);

σ_kis the q largest singular values;

q is

Is equal to the sparsity.

In the embodiment of the invention, a historical traffic matrix M is assumed_hisLength d of>And N is added. According to the formula (14),

can be decomposed into:

<math> <mrow> <msubsup> <mi>M</mi> <mi>his</mi> <mi>T</mi> </msubsup> <mo>=</mo> <msub> <mi>U</mi> <mi>his</mi> </msub> <msub> <mi>&Sigma;</mi> <mi>his</mi> </msub> <msubsup> <mi>V</mi> <mi>his</mi> <mi>T</mi> </msubsup> <mo>,</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>18</mn> <mo>)</mo> </mrow> </mrow> </math>

wherein, U_his，∑_hisAnd

are d × N, N × N and N × N matrices, respectively.

Step 4-2: and further analyzing and calculating according to the historical flow matrix and the singular value decomposition method.

V can be calculated according to the formula (18)_his∑_his. Because each OD stream in the traffic matrix has a long correlation, the principal component remains substantially unchanged. Thus, in conjunction with equation (18), equation (10) can be approximately converted to:

Y=A×V_his∑_hisU^T=ΘU^T, (19)

wherein, AV_his∑_his=Θ。

According to equation (19), the first q columns of Θ are truncated, and there is a new matrix Θ_colRepresents;

according to equation (16), Y can be approximately expressed as:

<math> <mrow> <mi>Y</mi> <mo>=</mo> <mi>&Theta;</mi> <msup> <mi>U</mi> <mi>T</mi> </msup> <mo>=</mo> <mi>&Theta;</mi> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msubsup> <mi>u</mi> <mi>PC</mi> <mi>T</mi> </msubsup> </mtd> </mtr> <mtr> <mtd> <msup> <mi>u</mi> <mi>T</mi> </msup> </mtd> </mtr> </mtable> </mfenced> <mo>&ap;</mo> <mi>&Theta;</mi> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msubsup> <mi>u</mi> <mi>PC</mi> <mi>T</mi> </msubsup> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> </mfenced> <mo>=</mo> <mi>&Theta;</mi> <msubsup> <mi>U</mi> <mi>PC</mi> <mi>T</mi> </msubsup> <mo>,</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>20</mn> <mo>)</mo> </mrow> </mrow> </math>

wherein,and u^TAre respectively U^Tq.times.T (q)<p) and (N-q) xT order submatrices;

is a sparse matrix with sparsity q.

Step 4-3: matrix sparsification after singular value decomposition is realized through a convex optimization method:

<math> <mrow> <msubsup> <mover> <mi>U</mi> <mo>^</mo> </mover> <mi>PC</mi> <mi>T</mi> </msubsup> <mo>=</mo> <mi>arg</mi> <mi>min</mi> <msub> <mrow> <mo>|</mo> <mo>|</mo> <msubsup> <mi>U</mi> <mi>PC</mi> <mi>T</mi> </msubsup> <mo>|</mo> <mo>|</mo> </mrow> <mn>1</mn> </msub> <mi>s</mi> <mo>.</mo> <mi>t</mi> <mo>.</mo> <mi>&Theta;</mi> <msubsup> <mi>U</mi> <mi>PC</mi> <mi>T</mi> </msubsup> <mo>=</mo> <mi>Y</mi> <mo>,</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>21</mn> <mo>)</mo> </mrow> </mrow> </math>

wherein:

to make it possible toWhen taking the minimum valueA value of (d);

thus, equation (20) can be transformed into:

<math> <mrow> <mi>Y</mi> <mo>=</mo> <msub> <mi>&Theta;</mi> <mi>col</mi> </msub> <msubsup> <mi>u</mi> <mi>PC</mi> <mi>T</mi> </msubsup> <mo>,</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>22</mn> <mo>)</mo> </mrow> </mrow> </math>

wherein, theta_colIs q of theta<And p columns. Thus, l₂The norm minimization problem can be used to solve u_PCThat is to say that,

<math> <mrow> <msubsup> <mover> <mi>u</mi> <mo>^</mo> </mover> <mi>PC</mi> <mi>T</mi> </msubsup> <mo>=</mo> <mi>arg</mi> <mi>min</mi> <msub> <mrow> <mo>|</mo> <mo>|</mo> <msubsup> <mi>u</mi> <mi>PC</mi> <mi>T</mi> </msubsup> <mo>|</mo> <mo>|</mo> </mrow> <mn>2</mn> </msub> <mi>s</mi> <mo>.</mo> <mi>t</mi> <mo>.</mo> <msub> <mi>&Theta;</mi> <mi>col</mi> </msub> <msubsup> <mi>u</mi> <mi>PC</mi> <mi>T</mi> </msubsup> <mo>=</mo> <mi>Y</mi> <mo>,</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>23</mn> <mo>)</mo> </mrow> </mrow> </math>

thus, equation (22) is an overdetermined problem and an optimal solution is easily found.

From equation (22), it can be known that Θ_colAnd u_PCIs a column full rank matrix. Thus, the following formula can be obtained,

<math> <mrow> <mi>Y</mi> <mo>=</mo> <msub> <mi>u</mi> <mi>y</mi> </msub> <msub> <mi>&Sigma;</mi> <mi>y</mi> </msub> <msubsup> <mi>v</mi> <mi>y</mi> <mi>T</mi> </msubsup> <mo>.</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>24</mn> <mo>)</mo> </mrow> </mrow> </math>

wherein the matrix u_yObtained by singular value decomposition of Y;

matrix arrayIs Y^TA feature vector of Y;

because theta_colAnd u_PCAre all column full rank matrices, then Θ_colIs equal to u_yRank (Θ)_col)=rank(u_y) And with theta_colSpace expanded as a basis is equal to u_PCSpace expanded for basis (theta)_col)=span(u_y)）。

Step 4-4: the matrix is analyzed in a last step according to the orthogonal transformation.

Calculating R according to equation (25);

the orthogonal transformation matrix obeys the following constraint condition, there is a matrix R satisfying the following formula,

u_y=Θ_colR. (25)

according to the formulas (26), (27), calculation

Assuming that the matrix W satisfies

And W theta_colI, I is the identity matrix.

Therefore, the temperature of the molten metal is controlled,

<math> <mrow> <mi>WY</mi> <mo>=</mo> <mi>W</mi> <msub> <mi>&Theta;</mi> <mi>col</mi> </msub> <msubsup> <mi>u</mi> <mi>PC</mi> <mi>T</mi> </msubsup> <mo>=</mo> <msubsup> <mi>u</mi> <mi>PC</mi> <mi>T</mi> </msubsup> <mo>.</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>26</mn> <mo>)</mo> </mrow> </mrow> </math>

in addition to this, the present invention is,

Wu_y=WΘ_colR=R. (27)

according to (28), calculating

From equations (26) and (27), we can obtain:

$\left\{\begin{array}{c}\mathrm{WY}=u_{\mathrm{PC}}^T\\ {\mathrm{Wu}}_y=R\end{array}\right..---\left(28\right)$

$u_{\mathrm{PC}}^T=\left({\mathrm{Ru}}_y^T\right)Y---\left(29\right)$

obtained according to the above steps

By calculation of

Obtaining a flow matrix M according to equation (18)_hisAnd (6) estimating the value.

Through the steps, partial end-to-end network flow can be obtained according to direct measurement, and an estimation result of a network flow matrix is obtained. The matrix describes the size of all end-to-end traffic in the large-scale IP backbone.

Performance evaluation results:

fig. 5 is a schematic diagram of rank variation of NMAE with a flow matrix according to an embodiment of the present invention, and the performance of the present invention is evaluated by using Normalized Mean Absolute Error (NMAE), where the rank q in the embodiment of the present invention is 1,2,3,4,5,6,7, and 8 (as shown in fig. 6).

The NMAE calculation formula is:

<math> <mrow> <mi>NMAE</mi> <mo>=</mo> <mfrac> <mrow> <munder> <mi>&Sigma;</mi> <mrow> <mi>j</mi> <mo>,</mo> <mi>t</mi> </mrow> </munder> <mo>|</mo> <msub> <mover> <mi>m</mi> <mo>^</mo> </mover> <mi>j</mi> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> <mo>-</mo> <msub> <mi>m</mi> <mi>j</mi> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> <mo>|</mo> </mrow> <mrow> <munder> <mi>&Sigma;</mi> <mrow> <mi>j</mi> <mo>,</mo> <mi>t</mi> </mrow> </munder> <mo>|</mo> <msub> <mi>m</mi> <mi>j</mi> </msub> <mrow> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mrow> <mo>|</mo> </mrow> </mfrac> <mo>.</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>29</mn> <mo>)</mo> </mrow> </mrow> </math>

wherein,representing the j-th OD flow estimation value at the t moment;

m_jand (t) represents the true value of the j-th OD flow at the t moment.

Simulation results show that the performance of the algorithm of the invention does not change much with the change of q. However q is constrained by some conditions, first the rank q is equivalent to sparsity. That is, in the formula (20), when the rank is q, U^TCan be prepared from

In the approximation that the difference between the first and second values,

is q sparse. The boolean sparsity measurement matrix a is a p × N matrix, p = O (Klog (N/K)). In the simulation, K = q, and thus, p = O (qlog (N/q)). The number of measurements p directly affects the total number of OD flows that need to be measured. In the embodiment of the invention, q is set to be equal to the total amount of OD streams according to p. In fig. 5, a fluctuation occurs in NMAE because p tends to flow boundary qlog (N/q) at this time. In this case, the smaller the p-qlog (N/q), the greater the probability of reconstruction failure. Fig. 6 is a schematic diagram of the variation of the random walk length of the NMAE according to the embodiment of the present invention, wherein the NMAE basically decreases with the increase of the random walk length. If r is small enough, robustness will be reduced; if r is too large, it will again produce a portion of the OD flow we have to measure.

FIG. 7 shows that the OD flow numbers are normally distributed, the intercept of the straight line represents the mean value of the OD flow numbers, and the slope represents the standard deviation. Simulation results show that: we need about 105 + 120 OD flows to recover the traffic matrix. In the flow compression reconstruction, the PCA method is adopted in the embodiment of the present invention without performing other preprocessing, so that the embodiment of the present invention requires 60% of links to operate NetFlow.

In FIG. 8, the first 500 points are used in the algorithm as a priori information for calculating V_his∑_his. The 30 th and 60 th OD streams were randomly selected for testing in the examples of the present invention. Three methods are found to track the dynamic changes of the flow in time. However, in fig. 8 (a), large fluctuations occur in SRSVD (sparse reconstruction singular value decomposition) and TomoG (gravity model), and FSR (flow sensing reconstruction) can accurately obtain the 30 th OD stream; fig. 8 (b) clearly shows that SRSVD and TomoG cannot reconstruct 60 OD streams accurately, and that FSR can more accurately derive the trend of flow rate changes. Therefore, experimental results prove that the method can better estimate the end-to-end network traffic.

In order to more accurately evaluate the advantages of the algorithm of the present invention, the embodiment of the present invention compares the three methods with another standard. Since network traffic exhibits time-varying and space-time correlation, embodiments of the present invention analyze FSR characteristics with reference to Spatial Relative Errors (SREs) and temporal relative errors (tress).

SREs and TREs are expressed as:

$\mathrm{SRE}\left(n\right)=\frac{{\left|\right|{\hat{x}}_T\left(n\right)-x_T\left(n\right)\left|\right|}_2}{{\left|\right|x_T\left(n\right)\left|\right|}_2},n=\mathrm{1,2},...,N---\left(29\right)$

wherein:

the nth OD flow estimation value at the T moment is represented;

x_Tand (n) represents the real value of the nth OD flow at the time T.

$\mathrm{TRE}\left(t\right)=\frac{{\left|\right|{\hat{x}}_N\left(t\right)-x_N\left(t\right)\left|\right|}_2}{{\left|\right|x_N\left(t\right)\left|\right|}_2},t=\mathrm{1,2},...,T---\left(30\right)$

Wherein:the estimated value of the Nth OD flow at the time t is shown;

x_N(t) represents the true value of the Nth OD flow at time t.

Here, non-negative integers N and T denote the total number of OD flows and the measurement time instant, respectively. I | · | purple wind₂Is represented by₂And (4) norm. SERs represent the spatial error distribution of different OD streams. While TREs represents the time error distribution.

In FIG. 9 (a), the SRSVD and Tomog methods showed high fluctuations in the OD streams at lanes 10 and 40. Because the first half of the data for this OD flow is very small, the energy occupied in the overall network traffic is particularly small. It is difficult to accurately estimate these OD streams. Further, the average spatial correlation errors of FSR, SRSVD and Tomog were 0.47,0.77 and 0.68, respectively. The FSR method of embodiments of the present invention has the lowest spatial correlation error in the first half of the OD flow. This shows that there is a very stable and efficient estimation characteristic for the small-scale flow FSR. In FIG. 9 (b), all methods have mutations in the time domain. But FSR has very low mutations in small intervals. Meanwhile, the average time correlation errors of FSR, SRSVD, TomoG are 0.20,0.29, 0.26, respectively, so that FSR has the lowest time correlation error.

In the embodiment of the invention, the flow matrix estimation characteristics are obtained through the cumulative distribution functions of the spatial relative errors and the time relative errors of the three methods. FIG. 10 (a) shows that the relative spatial error obtained for the three methods FSR, SRSVD, Tomog is 0.83 for OD flows of about 92%, 73%, 84%. Furthermore, fig. 10 (b) shows that the relative error in time obtained for the embodiment of the present invention is 0.25, 0.31,0.30 for about 80% of the estimated time. This measurement therefore represents the same estimation result for the three methods, with the FSR method employed by embodiments of the present invention having the lowest estimation error.

In conclusion, it is demonstrated that the traffic matrix reconstructed by the FSR method is more accurate.

Claims (4)

1. An end-to-end network flow reconstruction method based on compressed sensing in a dynamic network is characterized in that: the method comprises the following steps:

step 1, setting the length and the random walk times of a system aiming at OD stream random walks;

step 2, in a large-scale IP backbone network, selecting OD flows in a random walk mode, and describing the opening and closing states of all routers by adopting a method for constructing a Boolean sparse measurement matrix according to the selected OD flows;

step 3, describing flow values of part of OD flows collected by a router subset by adopting a method for constructing a sparse flow matrix, wherein the router subset is a router in all opening states, and calculating a measurement value according to a Boolean sparse measurement matrix and the constructed sparse flow matrix;

and 4, according to the sparse measurement matrix constructed in the step 3 and the measurement value obtained by calculation, adopting a principal component analysis method to construct a compressed sensing reconstruction model, describing the relationship between the OD flows generated by the router subset and all end-to-end OD flows in the large-scale IP backbone network by using the model, and further determining all end-to-end OD flow in the whole IP backbone network.

2. The method according to claim 1, wherein the method for reconstructing the end-to-end network traffic based on compressed sensing in the dynamic network comprises: the method for constructing the Boolean sparse measurement matrix in the step 2 comprises the following steps:

step 2-1, constructing an OD flow complete graph, wherein the complete graph comprises vertexes and edges, and the number of the vertexes is equal to the number of the OD flows;

step 2-2: setting an initial value of the random walk measurement times;

step 2-3: selecting a vertex as a unified starting point;

step 2-4: executing uniformly distributed random walks on the complete graph, and according to points found by the random walks, the state of the router corresponding to the points is an open state, otherwise, the state is a closed state;

step 2-5: if the random walk measurement times are smaller than the initialization set random walk measurement times, returning to the step 2-3; if the number of random walk measurements is greater than or equal to the number of initial random walk measurements, executing step 2-6;

step 2-6: and saving the Boolean sparse measurement matrix.

3. The method according to claim 1, wherein the method for reconstructing the end-to-end network traffic based on compressed sensing in the dynamic network comprises: the Boolean sparse measurement matrix in the step 1 accords with a constraint equidistance criterion; the number of rows in the boolean sparse measurement matrix represents the number of times the large-scale IP backbone network is randomly walked, and the number of columns in the boolean sparse measurement matrix represents the total number of OD flows in the large-scale IP backbone network.

4. The method according to claim 1, wherein the method for reconstructing the end-to-end network traffic based on compressed sensing in the dynamic network comprises: the calculation of the measured values described in step 3 satisfies the following formula:

measurement = boolean sparse measurement matrix x sparse traffic matrix.

Images