Automatic root cause diagnosis in networks

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. 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;

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.

11. The article of manufacture of claim 10 , 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.

12. The article of manufacture of claim 10 , 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.

13. The article of manufacture of claim 10 , 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.

14. The article of manufacture of claim 10 , 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.

15. The article of manufacture of claim 10 , the operations 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.

16. The article of manufacture of claim 10 , 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.

17. A computing device comprising:

a processor;

memory; and

program instructions, stored in the memory, that upon execution by the processor 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;

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.

18. The computing device of claim 17 , 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.