Automatic Root Cause Diagnosis in Networks

• US 20200136891A1
• Filed: 10/22/2019
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: EXFO Incorporated (11172239 Canada, Inc.)
• Original Assignee: EXFO Solutions SAS (11172239 Canada, Inc.), Institut Mines-Télécom
• Inventors: Mdini, Maha, Simon, Gwendal, Blanc, Alberto, Lecoeuvre, Julien
• Granted Patent: US 11,388,040 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 41/0613 based on the type or category of the network elements
• CPC Class Codes: H04L 41/065 involving logical or physical relationship, e.g. grouping and hierarchies
• CPC Class Codes: H04L 41/069 using logs of notifications; Post-processing of notifications
• CPC Class Codes: H04L 41/0873 Checking configuration conflicts between network elements
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/0823 Errors, e.g. transmission errors
• CPC Class Codes: H04L 43/16 Threshold monitoring

Abstract

An embodiment may involve: (i) obtaining a set of data records that include respective pluralities of tuples characterizing operation of communication sessions in a network and that identify hardware or software components related to the network that were involved in the communication sessions, (ii) determining degrees to which signatures in the pluralities of tuples are associated with communication problems in the network; (iii) identifying, from the degrees, a subset of the signatures most associated with the communication problems; (iv) grouping specific pairs from the subset of the signatures into equivalence classes based on co-occurrence of signatures of the specific pairs within the data records; (v) generating and pruning a dependency graph between the equivalence classes; (vi) from the equivalence classes remaining in the dependency graph, selecting a subset of the hardware or software components related to the network that are candidates for involvement with the communication problems.

Claims

1. A computer-implemented method comprising:

obtaining a set of data records, wherein the data records include respective pluralities of tuples characterizing operation of communication sessions in a network, wherein the tuples contain signatures representing features and values, wherein the features and values identify hardware or software components related to the network that were involved in the communication sessions;

generating binary labels for the data records, wherein the binary labels respectively indicate whether the communication sessions associated with the data records were successful or failed;

determining degrees to which signatures in the pluralities of tuples are associated with communication problems in the network, wherein, for a particular signature, a degree is based on linear combinations of;

(i) a proportion of the data records not including the particular signature, and (ii) a proportion of the data records labelled as failed that do not include the particular signature;

identifying, from the degrees, a subset of the signatures most associated with the communication problems;

grouping specific pairs from the subset of the signatures into equivalence classes based on co-occurrence of signatures of the specific pairs within the data records;

generating a dependency graph between the equivalence classes in which the equivalence classes are represented as nodes in the dependency graph and edges are placed between a parent equivalence class and a child equivalence class where the data records in the child equivalence class are approximately a subset of the data records in the parent equivalence class;

based on the signatures and the binary labels, determining relative failure ratios of each of the child equivalence classes with respect to their parent equivalence classes;

removing a parent or child equivalence classes from the dependency graph where all of the relative failure ratios thereof are less than a pre-determined threshold; and

from the equivalence classes remaining in the dependency graph, selecting a subset of the hardware or software components related to the network that are candidates for involvement with the communication problems.

2. The computer-implemented method of claim 1, wherein generating a binary label for a data record involving a voice or multimedia call facilitated by the network comprises:

determining, from packet traffic collected from the network, whether to label the data record as successful or failed based on call management messages related to the voice or multimedia call.

3. The computer-implemented method of claim 1, wherein generating a binary label for a data record involving a data session facilitated by the network comprises:

determining, from packet traffic collected from the network, whether to label the data record as successful or failed based on response times of devices and a packet retransmission ratio of the data session.

4. The computer-implemented method of claim 1, wherein a pair from the specific pairs includes a first signature and a second signature, and wherein grouping the pair into an equivalence class of the equivalence classes comprises:

extracting a first subset from the data records containing the first signature and a second subset from the data records containing the second signature;

calculating a first cardinality of the first subset and a second cardinality of the second subset;

determining a union of the first subset and the second subset;

calculating a third cardinality of the union;

determining that (i) a first quotient of the third cardinality divided by the first cardinality exceeds a pre-determined threshold, and (ii) a second quotient of the third cardinality divided by the second cardinality exceeds the pre-determined threshold; and

based on the first quotient and the second quotient both exceeding the pre-determined threshold, placing the first signature and the second signature in the equivalence class.

5. The computer-implemented method of claim 4, wherein the pre-determined threshold is between 0.8 and 1.0.

6. The computer-implemented method of claim 1, wherein a first equivalence class contains a first signature and a second equivalence class contains a second signature, and wherein generating the dependency graph comprises:

extracting a first subset from the data records containing the first signature and a second subset from the data records containing the second signature;

calculating a first cardinality of the first subset;

determining a union of the first subset and the second subset;

calculating a second cardinality of the union;

determining that a quotient of the second cardinality divided by the first cardinality exceeds a pre-determined threshold; and

based on the quotient exceeding the pre-determined threshold, identifying the first equivalence class as the child equivalence class and the second equivalence class as the parent equivalence class.

7. The computer-implemented method of claim 1, wherein the dependency graph is a directed acyclic graph.

8. The computer-implemented method of claim 1, further comprising:

performing a depth-first search on the dependency graph to find all paths between each pair of connected nodes therein, wherein each of the paths is represented as one or more adjacent edges in the dependency graph; and

removing all edges except for those on a longest of the paths between each pair of connected nodes.

9. The computer-implemented method of claim 1, wherein removing a child equivalence class from the dependency graph comprises:

connecting, in the dependency graph, parent equivalence classes of the child equivalence class to further child equivalence classes of the child equivalence class.

10. The computer-implemented method of claim 1, further comprising:

determining a 2-signature tuple present in at least one of the data records, wherein the 2-signature tuple is composed of a first signature and a second signature;

calculating, for the 2-signature tuple, a first gain representing an overall relative inefficiency of the communication sessions involving the 2-signature tuple compared to relative inefficiencies of the communication sessions involving the first signature or the second signature;

determining that the first gain exceeds a first pre-determined threshold;

based on determining that the first gain exceeds the first pre-determined threshold, (i) filtering the communication sessions involving the 2-signature tuple to create a subset of the communication sessions involving 1-signatures for which a size of the subset exceeds a second pre-determined threshold, and (ii) calculating a second gain representing the overall relative inefficiency of the communication sessions involving the 2-signature tuple compared to relative inefficiencies of the communication sessions involving the 1-signatures for which the size of the subset exceeds the second pre-determined threshold;

determining that the second gain exceeds the first pre-determined threshold; and

based on determining that the second gain exceeds the first pre-determined threshold, identifying the features and values that are represented by the first signature and the second signature as units of the hardware or software components that are incompatible.

11. A computer-implemented method comprising:

obtaining a set of data records, wherein the data records include respective pluralities of tuples characterizing operation of communication sessions in a network, wherein the tuples contain signatures representing features and values, wherein the features and values identify hardware or software components related to the network that were involved in the communication sessions;

determining a 2-signature tuple present in at least one of the data records, wherein the 2-signature tuple is composed of a first signature and a second signature;

calculating, for the 2-signature tuple, a first gain representing an overall relative inefficiency of the communication sessions involving the 2-signature tuple compared to relative inefficiencies of the communication sessions involving the first signature or the second signature;

determining that the first gain exceeds a first pre-determined threshold;

based on determining that the first gain exceeds the first pre-determined threshold, (i) filtering the communication sessions involving the 2-signature tuple to create a subset of the communication sessions involving 1-signatures for which a size of the subset exceeds a second pre-determined threshold, and (ii) calculating a second gain representing the overall relative inefficiency of the communication sessions involving the 2-signature tuple compared to relative inefficiencies of the communication sessions involving the 1-signatures for which the size of the subset exceeds the second pre-determined threshold;

determining that the second gain exceeds the first pre-determined threshold; and

based on determining that the second gain exceeds the first pre-determined threshold, identifying the features and values that are represented by the first signature and the second signature as units of the hardware or software components that are incompatible.

12. The computer-implemented method of claim 11, wherein the first gain is based on a difference between:

(i) an overall failure ratio of the communication sessions involving the 2-signature tuple, and (ii) a maximum of a first failure ratio of the communication sessions involving the first signature and a second failure ratio of the communication sessions involving the second signature.

13. The computer-implemented method of claim 11, wherein the first pre-determined threshold is between 0.05 and 0.4.

14. The computer-implemented method of claim 11, wherein the second pre-determined threshold is between 0.8 and 1.0.

15. The computer-implemented method of claim 11, wherein filtering the communication sessions involving the 2-signature tuple comprises:

determining a first subset of the communication sessions involving a particular 1-signature and a second subset of the communication sessions involving the 2-signature tuple;

determining a union of the first subset and a second subset; and

determining that a quotient of;

(i) a first cardinality of the union, and (ii) a second cardinality of the second subset exceeds the second pre-determined threshold.

16. The computer-implemented method of claim 11, further comprising:

before identifying the features and values represented by the first signature and the second signature as units of the hardware or software components that are incompatible;

(i) identifying, for the first signature, a first equivalence class of 1-signatures that are incompatible thereto, and (ii) identifying, for the second signature, a second equivalence class of 1-signatures that are incompatible thereto.

17. The computer-implemented method of claim 16, further comprising:

generating, one for each 1-signature in the first equivalence class or the second equivalence class, dependency graphs between the respective 1-signature and other 1-signatures, in which equivalence classes for the respective 1-signature are represented as nodes in the dependency graphs and edges are placed between a parent 1-signature and a child 1-signature where the data records including the child 1-signature are approximately a subset of the data records including the parent 1-signature, wherein the first signature and the second signature are included in the 1-signatures.

18. The computer-implemented method of claim 17, further comprising:

determining that, in a particular dependency graph for a particular 1-signature, a particular parent 1-signature remains incompatible with the particular 1-signature after the data records including a particular child 1-signature are not considered; and

removing a node representing the particular child 1-signature from the particular dependency graph.

19. The computer-implemented method of claim 17, further comprising:

determining that, in a particular dependency graph for a particular 1-signature, a particular parent 1-signature is no longer incompatible with the particular 1-signature after the data records including a particular child 1-signature are not considered; and

removing a node representing the particular parent 1-signature from the particular dependency graph.

20. An article of manufacture including a non-transitory computer-readable medium, having stored thereon program instructions that, upon execution by a computing device, cause the computing device to perform operations comprising:

obtaining a set of data records, wherein the data records include respective pluralities of tuples characterizing operation of communication sessions in a network, wherein the tuples contain signatures representing features and values, wherein the features and values identify hardware or software components related to the network that were involved in the communication sessions;

determining a 2-signature tuple present in at least one of the data records, wherein the 2-signature tuple is composed of a first signature and a second signature;

calculating, for the 2-signature tuple, a first gain representing an overall relative inefficiency of the communication sessions involving the 2-signature tuple compared to relative inefficiencies of the communication sessions involving the first signature or the second signature;

determining that the first gain exceeds a first pre-determined threshold;

based on determining that the first gain exceeds the first pre-determined threshold, (i) filtering the communication sessions involving the 2-signature tuple to create a subset of the communication sessions involving 1-signatures for which a size of the subset exceeds a second pre-determined threshold, and (ii) calculating a second gain representing the overall relative inefficiency of the communication sessions involving the 2-signature tuple compared to relative inefficiencies of the communication sessions involving the 1-signatures for which the size of the subset exceeds the second pre-determined threshold;

determining that the second gain exceeds the first pre-determined threshold; and

based on determining that the second gain exceeds the first pre-determined threshold, identifying the features and values that are represented by the first signature and the second signature as units of the hardware or software components that are incompatible.