CN104468196B - Virtual network method for diagnosing faults and device based on evidence screening - Google Patents

Abstract

The invention relates to the technical field of network fault diagnosis, in particular to a virtual network fault diagnosis method and device based on evidence screening. A virtual network fault diagnosis method and device based on evidence screening provided by the present invention establishes an evidence matrix model by using the observation results of the virtual network, and uses DS evidence theory to solve the fault probability of each virtual network component, thereby determining the faulty component and overcoming The dynamics, scalability and information uncertainty of the virtual network are improved. At the same time, because the technical solution adopted by the present invention screens the evidence in advance, the fault location not only maintains high accuracy, but also greatly improves the time efficiency, maximizing the overall benefit.

Description

Virtual network fault diagnosis method and device based on evidence screening

technical field

The invention relates to the technical field of network fault diagnosis, in particular to a virtual network fault diagnosis method and device based on evidence screening.

Background technique

In a virtual network environment, multiple virtual networks exist on the same underlying physical network at the same time. The traditional Internet Service Provider (Internet Service Provider, ISP) is divided into two parts: Infrastructure Providers (Infrastructure Providers, InPs) and network service providers Operators (Service Providers, SPs), infrastructure providers are used to provide and manage physical infrastructure, and network service operators use resources provided by multiple InPs to deploy virtual networks through abstraction, allocation and isolation mechanisms to provide end users with innovative End-to-end services and diverse business applications.

In a virtualized environment, due to the transparency of the underlying information to the upper virtual network, the fault detection system cannot obtain complete network knowledge, so there are a lot of uncertainties in the fault diagnosis of the virtual network; in addition, the virtual network is a typical large-scale Distributed network, which contains a large number of virtual nodes and virtual links, these components change dynamically with the demand, there is no fixed network topology. Coupled with the influence of noise, it becomes more difficult to diagnose the fault of the virtual network in the virtual environment.

Existing technical solutions mainly adopt a fault location method based on active or passive detection of the management layer to diagnose the fault of the virtual network. However, using the above methods to diagnose virtual network faults needs to understand the global topology of the network, which cannot be well adapted to the dynamics and scalability of virtual networks.

Contents of the invention

Aiming at the defect that the prior art cannot better adapt to the dynamics and expansibility of the virtual network, the present invention provides a virtual network fault diagnosis method and device based on evidence screening.

On the one hand, the present invention provides a virtual network fault diagnosis method based on evidence screening, including:

Obtain the observation result of each client whether the virtual network path corresponding to the client fails;

Establish an evidence matrix, wherein each row of the evidence matrix corresponds to a client, the first column of the evidence matrix corresponds to the observation result of the client, and each of the remaining columns corresponds to a virtual network component, and the virtual network component includes virtual nodes and virtual link;

Splitting the evidence matrix into a plurality of sub-evidence matrices, the number of columns of each of the sub-evidence matrices is equal to the number of columns of the evidence matrix;

For each sub-evidence matrix, the probability of failure of each virtual network component is obtained by solving according to the DS evidence theory;

Select the virtual network component with the highest failure probability in descending order of failure probability until the number of failed virtual network paths covered by all selected virtual network components reaches a preset value.

Further, the step of splitting the evidence matrix into multiple sub-evidence matrices includes:

The evidence matrix is split into two sub-evidence matrices, the odd-numbered rows of the evidence matrix are used as the first sub-evidence matrix, and the even-numbered rows of the evidence matrix are used as the second sub-evidence matrix.

Further, the step of obtaining the failure probability of each virtual network component according to the DS evidence theory includes:

For each sub-evidence matrix, construct an m-function of each virtual network component according to DS evidence theory;

For each virtual network component, all the m-functions of the same virtual network component are fused according to the fusion rules of DS evidence theory, and the failure probability of the virtual network component is obtained.

Further, the step of constructing an m-function of each virtual network component according to the DS evidence theory includes:

For the i-th virtual network component C _i , establish an identification frame of C _i Θ={N _i , A _i }, where N represents normal and A represents failure;

When Q _i >P _i , m(N _i )=min(1, log(Q _i \P _i )), m({N _i , A _i })=1-m(N _i ); m(A _i )=0;

When Q _i <=P _i , m(A _i )=min(1,-log(Q _i \P _i )); m({N _i ,A _i })=1-m(N _i ), m (N _i )=0;

The Q _i is the posterior probability that the virtual network component C _i is normal, and the P _i is the posterior probability that the virtual network component C _i is faulty.

Further, the step of fusing all m-function values of the same virtual network component according to the DS evidence theory includes:

for

Among them, X, B, and C are focal elements, m ₁ is the m function corresponding to the first sub-evidence matrix, m ₂ is the m function corresponding to the second sub-evidence matrix, and K is a normalization constant:

Further, the preset value is calculated using the following formula:

Default value = the number of all virtual network paths that have failed * (1-anti-noise factor);

The anti-noise coefficient is a preset parameter.

Correspondingly, the present invention also provides a virtual network fault diagnosis device based on evidence screening, including:

The acquisition module is used to acquire the observation result of each client whether the virtual network path corresponding to the client fails;

A building module for building an evidence matrix, wherein each row of the evidence matrix corresponds to a client, the first column of the evidence matrix corresponds to the observation result of the client, and each of the remaining columns corresponds to a virtual network component, and the virtual network Components include virtual nodes and virtual links;

A splitting module, configured to split the evidence matrix into a plurality of sub-evidence matrices, the number of columns of each of the sub-evidence matrices is equal to the number of columns of the evidence matrix;

A solving module, for each of the sub-evidence matrices, according to the DS evidence theory to obtain the failure probability of each virtual network component;

The selection module is used to sequentially select the virtual network component with the highest failure probability in descending order of failure probability until the number of failed virtual network paths covered by all selected virtual network components reaches a preset value .

Further, the splitting module is specifically used for:

The evidence matrix is split into two sub-evidence matrices, the odd-numbered rows of the evidence matrix are used as the first sub-evidence matrix, and the even-numbered rows of the evidence matrix are used as the second sub-evidence matrix.

Further, the solving module is specifically used for:

For the i-th virtual network component C _i , establish an identification frame of C _i Θ={N _i , A _i }, where N represents normal and A represents failure;

When Q _i >P _i , m(N _i )=min(1, log(Q _i \P _i )), m({N _i , A _i })=1-m(N _i ); m(A _i )=0;

When Q _i <=P _i , m(A _i )=min(1,-log(Q _i \P _i )); m({N _i ,A _i })=1-m(N _i ), m (N _i )=0;

The Q _i is the posterior probability that the virtual network component C _i is normal, and the P _i is the posterior probability that the virtual network component C _i is faulty;

for

Among them, X, B, and C are focal elements, m ₁ is the m function corresponding to the first sub-evidence matrix, m ₂ is the m function corresponding to the second sub-evidence matrix, and K is a normalization constant:

Further, the selection module is specifically used for:

The preset value is calculated using the following formula:

Default value=number of virtual network paths that have failed*(1-anti-noise factor); wherein the anti-noise factor is a preset parameter.

A virtual network fault diagnosis method and device based on evidence screening provided by the present invention establishes an evidence matrix model by using the observation results of the virtual network, and uses DS evidence theory to solve the fault probability of each virtual network component, thereby determining the faulty component and overcoming The dynamics, scalability and information uncertainty of the virtual network are improved. At the same time, because the technical solution adopted by the present invention screens the evidence in advance, the fault location not only maintains high accuracy, but also greatly improves the time efficiency, maximizing the overall benefit.

Description of drawings

The features and advantages of the present invention will be more clearly understood by referring to the accompanying drawings, which are schematic and should not be construed as limiting the invention in any way. In the accompanying drawings:

Fig. 1 is a schematic flow chart of a virtual network fault diagnosis method based on evidence screening in an embodiment of the present invention;

Fig. 2 is a schematic diagram of the change of the time-consuming ratio of the method of this embodiment and the fault detection of the prior art with the number of components in an embodiment of the present invention;

Fig. 3 is a schematic diagram of the change of the time-consuming ratio of the method of this embodiment and the fault detection of the prior art with the amount of evidence in an embodiment of the present invention;

Fig. 4 is a schematic diagram of comparing the accuracy of fault detection using the method of this embodiment and the prior art when the fault rate is 0.5% in one embodiment of the present invention;

Fig. 5 is a schematic diagram of comparing the accuracy of fault detection using the method of this embodiment and the prior art when the fault rate is 0.6% in one embodiment of the present invention;

Fig. 6 is a schematic diagram of comparison of the accuracy of fault detection using the method of this embodiment and the prior art when the fault rate is 0.8% in one embodiment of the present invention;

Fig. 7 is a schematic diagram of the comparison of the accuracy of fault detection using the method of this embodiment and the prior art when the fault rate is 1.0% in one embodiment of the present invention;

Fig. 8 is a schematic diagram of the misdiagnosis rate comparison between the method of this embodiment and the prior art for fault detection when the fault rate is 0.5% in one embodiment of the present invention;

Fig. 9 is a schematic diagram of the misdiagnosis rate comparison between the method of this embodiment and the prior art for fault detection when the fault rate is 0.6% in one embodiment of the present invention;

Fig. 10 is a schematic diagram of the misdiagnosis rate comparison between the method of this embodiment and the prior art for fault detection when the fault rate is 0.8% in one embodiment of the present invention;

Fig. 11 is a schematic diagram of the misdiagnosis rate comparison between the method of this embodiment and the prior art for fault detection when the fault rate is 1.0% in one embodiment of the present invention;

Fig. 12 is a schematic structural diagram of a virtual network fault diagnosis device based on evidence screening in an embodiment of the present invention.

detailed description

The technical solution of the present invention will be further described in detail in conjunction with the accompanying drawings and embodiments.

Figure 1 shows a schematic flowchart of a virtual network fault diagnosis method based on evidence screening in this embodiment. As shown in Figure 1, a virtual network fault diagnosis method based on evidence screening provided in this embodiment includes:

S1. Obtain an observation result of each client whether a virtual network path corresponding to the client fails.

S2. Establish an evidence matrix, wherein each row of the evidence matrix corresponds to a client, the first column of the evidence matrix corresponds to the observation result of the client, and each of the remaining columns corresponds to a virtual network component, and the virtual network component includes a virtual nodes and virtual links.

Specifically, the evidence matrix includes:

The first column of the evidence matrix is an error column. If the observation result of the client is faulty, the first column of the corresponding row of the client is 1. If the observation result of the client is normal, the corresponding The first column of the row is 0;

Starting from the second column, each virtual network component corresponds to a column of the evidence matrix. If the virtual network path corresponding to the client contains the virtual network component, then the virtual network component in the corresponding row of the client corresponds to is 1, and the rest are 0.

S3. Split the evidence matrix into a plurality of sub-evidence matrices, and the number of columns of each sub-evidence matrix is equal to the number of columns of the evidence matrix.

S4, for each of the sub-evidence matrices, obtain the failure probability of each virtual network component by solving according to the DS evidence theory.

S5. Select the virtual network component with the highest failure probability in descending order of failure probability until the number of failed virtual network paths covered by all selected virtual network components reaches a preset value.

In order to avoid the impact of noise on the detection results, the accuracy of the detection results is improved by introducing an anti-noise coefficient, that is, the preset value is calculated using the following formula:

Default value=the number of virtual network paths that have failed*(1-anti-noise factor).

Further, in order to obtain more accurate m-functions of virtual network components, in this embodiment, odd and even row splitting is used to split the evidence matrix into two sub-evidence matrices, and the odd-numbered rows of the evidence matrix are used as the first sub-evidence matrix. An evidence matrix, the even-numbered rows of the evidence matrix are used as the second sub-evidence matrix.

Further, the step of obtaining the failure probability of each virtual network component according to the DS evidence theory includes:

For each sub-evidence matrix, construct an m-function of each virtual network component according to DS evidence theory;

For each virtual network component, all the m-functions of the same virtual network component are fused according to the fusion rules of DS evidence theory, and the failure probability of the virtual network component is obtained.

Wherein, the step of constructing an m-function of each virtual network component according to the DS evidence theory includes:

For the i-th virtual network component C _i , establish an identification frame of C _i Θ={N _i , A _i }, where N represents normal and A represents failure;

When Q _i >P _i , m(N _i )=min(1, log(Q _i \P _i )), m({N _i , A _i })=1-m(N _i ); m(A _i )=0;

When Q _i <=P _i , m(A _i )=min(1,-log(Q _i \P _i )); m({N _i ,A _i })=1-m(N _i ), m (N _i )=0;

The Q _i is the posterior probability that the virtual network component C _i is normal, and the P _i is the posterior probability that the virtual network component C _i is faulty.

A recursive function loop is used to solve the posterior probability Q _i . For any virtual network component C _i . Denote Relatei as the set of related components of C _i , that is, the set of other components in the faulty path containing component C _i . If the set is empty, then Q _i =FaultRate, that is, the inherent fault rate of the virtual network; if the set is not empty, use the recursive function loop to perform the following operations:

(1) Delete all the evidence containing Relatei[count] from the atomic evidence matrix M to obtain a new matrix M1;

(2) Remove Relatei[count] from the atomic evidence matrix to get a new matrix M2

Add 1 to the counter count, and then the recursive function loop returns Prc*loop(count, M1)+(1-Prc)*loop(count, M2), where Prc is the prior probability of Relatei[count].

Further, the step of fusing all m-function values of the same virtual network component according to the DS evidence theory includes:

for

Among them, X, B, and C are focal elements, m ₁ is the m function corresponding to the first sub-evidence matrix, m ₂ is the m function corresponding to the second sub-evidence matrix, and K is a normalization constant: The anti-noise coefficient is a preset parameter.

In this example, a virtual scene experiment is used to illustrate the effect of the detection method of this embodiment. Use the INET tool to generate network topologies with different numbers of nodes. The number of nodes is from 1,000 to 20,000, and 10% to 20% of them are selected as virtual components. The failure rate in the virtual network is from 0.5% to 1.5%. The number of evidence observed by the client is from 1,000 to 20,000, and the observed results are normal The evidence of is called positive evidence and the evidence that the observation is a failure is called negative evidence. Since the evidence is randomly generated, most of the evidence is positive evidence. The noise interference rate in this system is 0.01%, 70% of the routing hops are 1, 20% are 2, 7% are 3, and 3% are 4.

As shown in Figure 2, as the number of components increases under different failure rates, the time-consuming ratio of the time-consuming fault detection using the method of this embodiment to the time-consuming fault detection using the prior art changes, as shown in Figure 3. As the number of evidence increases under the failure rate, the ratio of the time-consuming fault detection using the method of this embodiment to the time-consuming fault detection using the prior art changes.

Fig. 4 to Fig. 7 respectively show the comparison of the accuracy rate of the fault detection using the method of this embodiment and the fault detection using the prior art under different fault rates. Fig. 8 to Fig. 11 respectively show the comparison of misdiagnosis rate between fault detection using the method of this embodiment and fault detection using the prior art under different fault rates.

To sum up, the time consumed by the detection method of this embodiment is reduced by an average of 20-30% compared with the time consumed by the existing technology, but after the evidence is split, the accuracy and misdiagnosis rate are comparable to those of the existing technology. Technology has barely changed. Therefore, the virtual network fault diagnosis method based on evidence screening provided by this embodiment greatly improves the time efficiency while maintaining a high accuracy rate.

This embodiment provides a virtual network fault diagnosis method based on evidence screening. By using the observation results of the virtual network to establish an evidence matrix model, using the DS evidence theory to solve the failure probability of each virtual network component, so as to determine the faulty component, overcome the Dynamics, scalability and information uncertainty of virtual networks. At the same time, because the technical solution adopted by the present invention screens the evidence in advance, the fault location not only maintains high accuracy, but also greatly improves the time efficiency, maximizing the overall benefit.

On the other hand, as shown in FIG. 12 , this embodiment also provides a virtual network fault diagnosis device based on evidence screening, including:

Obtaining module 101, for obtaining the observation result of each client whether the virtual network path corresponding to the client fails;

The establishment module 102 is used to establish an evidence matrix, wherein each row of the evidence matrix corresponds to a client, the first column of the evidence matrix corresponds to the observation result of the client, and each of the remaining columns corresponds to a virtual network component, and the virtual Network components include virtual nodes and virtual links;

A splitting module 103, configured to split the evidence matrix into a plurality of sub-evidence matrices, the number of columns of each of the sub-evidence matrices is equal to the number of columns of the evidence matrix;

The solving module 104 is used to solve the failure probability of each virtual network component according to the DS evidence theory for each of the sub-evidence matrices;

The selection module 105 is configured to sequentially select the virtual network component with the highest failure probability in descending order of failure probability until the number of failed virtual network paths covered by all selected virtual network components reaches a preset value until.

Further, the splitting module 103 is specifically used for:

The evidence matrix is split into two sub-evidence matrices, the odd-numbered rows of the evidence matrix are used as the first sub-evidence matrix, and the even-numbered rows of the evidence matrix are used as the second sub-evidence matrix.

Further, the solving module 104 is specifically used for:

For each sub-evidence matrix, construct an m-function of each virtual network component according to DS evidence theory;

For each virtual network component, all the m-functions of the same virtual network component are fused according to the fusion rules of DS evidence theory, and the failure probability of the virtual network component is obtained.

Specifically, for the i-th virtual network component C _i , an identification framework of C _i is established Θ={N _i , A _i }, where N represents normal and A represents failure;

When Q _i >P _i , m(N _i )=min(1, log(Q _i \P _i )), m({N _i , A _i })=1-m(N _i ); m(A _i )=0;

When Q _i <=P _i , m(A _i )=min(1,-log(Q _i \P _i )); m({N _i ,A _i })=1-m(N _i ), m (N _i )=0;

The Q _i is the posterior probability that the virtual network component C _i is normal, and the P _i is the posterior probability that the virtual network component C _i is faulty.

for

Among them, X, B, and C are focal elements, m ₁ is the m function corresponding to the first sub-evidence matrix, m ₂ is the m function corresponding to the second sub-evidence matrix, and K is a normalization constant:

Further, the selecting module 105 is specifically used for:

The preset value is calculated using the following formula:

Default value=number of virtual network paths that have failed*(1-anti-noise factor); wherein the anti-noise factor is a preset parameter.

A virtual network fault diagnosis device based on evidence screening provided by the present invention establishes an evidence matrix model by using the observation results of the virtual network, and uses DS evidence theory to solve the failure probability of each virtual network component, thereby determining the faulty component and overcoming the virtual Network dynamics, scalability and information uncertainty. At the same time, because the technical solution adopted by the present invention screens the evidence in advance, the fault location not only maintains high accuracy, but also greatly improves the time efficiency, maximizing the overall benefit.

Although the embodiments of the present invention have been described in conjunction with the accompanying drawings, those skilled in the art can make various modifications and variations without departing from the spirit and scope of the present invention. within the bounds of the requirements.

Claims (10)

1. A virtual network fault diagnosis method based on evidence screening, characterized in that, the method comprises: Obtain the observation result of each client whether the virtual network path corresponding to the client fails; Establishing an evidence matrix, wherein each row of the evidence matrix corresponds to a client, the first column of the evidence matrix corresponds to the observation result of the client, and each of the remaining columns corresponds to a virtual network component, and the virtual network component includes a virtual nodes and virtual links; Splitting the evidence matrix into a plurality of sub-evidence matrices, the number of columns of each of the sub-evidence matrices is equal to the number of columns of the evidence matrix; For each sub-evidence matrix, the probability of failure of each virtual network component is obtained by solving according to the DS evidence theory; Select the virtual network component with the highest failure probability in descending order of failure probability until the number of failed virtual network paths covered by all selected virtual network components reaches a preset value. 2. The method according to claim 1, wherein the step of splitting the evidence matrix into a plurality of sub-evidence matrices comprises: The evidence matrix is split into two sub-evidence matrices, the odd-numbered rows of the evidence matrix are used as the first sub-evidence matrix, and the even-numbered rows of the evidence matrix are used as the second sub-evidence matrix. 3. The method according to claim 1 or 2, wherein the step of obtaining the failure probability of each virtual network component according to the DS evidence theory includes: For each sub-evidence matrix, construct an m-function of each virtual network component according to DS evidence theory; For each virtual network component, all the m-function values of the same virtual network component are fused according to the fusion rules of DS evidence theory to obtain the failure probability of the virtual network component. 4. The method according to claim 3, wherein the step of constructing an m-function of each virtual network component according to the DS evidence theory includes: For the i-th virtual network component C _i , establish an identification frame of C _i Θ={N _i , A _i }, where N represents normal and A represents failure; When Q _i >P _i , m(N _i )=min(1, log(Q _i \P _i )), m({N _i , A _i })=1-m(N _i ); m(A _i )=0; When Q _i <=P _i , m(A _i )=min(1,-log(Q _i \P _i )); m({N _i ,A _i })=1-m(N _i ), m (N _i )=0; The Q _i is the posterior probability that the virtual network component C _i is normal, and the P _i is the posterior probability that the virtual network component C _i is faulty. 5. The method according to claim 4, wherein the step of fusing all m-function values of the same virtual network component according to the DS evidence theory includes: for Among them, X, B, and C are focal elements, m ₁ is the m function corresponding to the first sub-evidence matrix, m ₂ is the m function corresponding to the second sub-evidence matrix, and m _{1, 2} are the m ₁ function value and m ₂ function m _1,2 (X) is the m _1,2 function value of focal element X, m ₁ (B) is the m ₁ function value of focal element B, m ₂ (C) is the focal element _m2 function value of element C, Indicates a direct sum operation, and K is a normalization constant: 6. The method according to claim 1, wherein the preset value is calculated using the following formula: Default value = the number of all virtual network paths that have failed * (1-anti-noise factor); The anti-noise coefficient is a preset parameter. 7. A virtual network fault diagnosis device based on evidence screening, characterized in that the device comprises: The acquisition module is used to acquire the observation result of each client whether the virtual network path corresponding to the client fails; A building module for building an evidence matrix, wherein each row of the evidence matrix corresponds to a client, the first column of the evidence matrix corresponds to the observation result of the client, and each of the remaining columns corresponds to a virtual network component, the Virtual network components include virtual nodes and virtual links; A splitting module, configured to split the evidence matrix into a plurality of sub-evidence matrices, the number of columns of each of the sub-evidence matrices is equal to the number of columns of the evidence matrix; A solving module, for each of the sub-evidence matrices, according to the DS evidence theory to obtain the failure probability of each virtual network component; The selection module is used to sequentially select the virtual network component with the highest failure probability in descending order of failure probability until the number of failed virtual network paths covered by all selected virtual network components reaches a preset value . 8. The device according to claim 7, wherein the splitting module is specifically used for: The evidence matrix is split into two sub-evidence matrices, the odd-numbered rows of the evidence matrix are used as the first sub-evidence matrix, and the even-numbered rows of the evidence matrix are used as the second sub-evidence matrix. 9. The device according to claim 8, wherein the solving module is specifically used for: For the i-th virtual network component C _i , establish an identification frame of C _i Θ={N _i , A _i }, where N represents normal and A represents failure; When Q _i >P _i , m(N _i )=min(1, log(Q _i \P _i )), m({N _i , A _i })=1-m(N _i ); m(A _i )=0; When Q _i <=P _i , m(A _i )=min(1,-log(Q _i \P _i )); m({N _i ,A _i })=1-m(N _i ), m (N _i )=0; The Q _i is the posterior probability that the virtual network component C _i is normal, and the P _i is the posterior probability that the virtual network component C _i is faulty; for Among them, X, B, and C are focal elements, m ₁ is the m function corresponding to the first sub-evidence matrix, m ₂ is the m function corresponding to the second sub-evidence matrix, and m _{1, 2} are the m ₁ function value and m ₂ function m _1,2 (X) is the m _1,2 function value of focal element X, m ₁ (B) is the m ₁ function value of focal element B, m ₂ (C) is the focal element _m2 function value of element C, Indicates a direct sum operation, and K is a normalization constant: 10. The device according to claim 7, wherein the selecting module is specifically used for: The preset value is calculated using the following formula: Default value = the number of all virtual network paths that have failed * (1-anti-noise factor); The anti-noise coefficient is a preset parameter.