Method and apparatus for correlating events in a network
First Claim
1. A method for correlating events occurring in a network, wherein the network is represented as a graph of interconnected nodes with interconnections between nodes representing dependencies between the entities represented by the nodes, the method comprising the computer-implemented steps of:
- creating a first data structure that is associated with a first entity, wherein the first data structure comprises;
a first set of data that comprises a list of events that originated in association with the first entity, wherein the list of events comprises a first event that originated in association with the first entity, anda second set of data that comprises a list of records, wherein the list of records comprises a record which incorporates by reference a different, second event that originated in association with a different, second entity that has a dependency relationship with the first entity;
wherein the second event is obtained by the first entity through incorporation by reference, without the second entity initiating propagation of the second event to the first entity; and
determining, based at least in part on the first data structure, a likelihood that the second event caused the first event or was caused by the first event;
wherein the method is performed by a computing device comprising one or more processors.
1 Assignment
0 Petitions
Accused Products
Abstract
A uniquely configured data structure is used to store event information for each network entity, where logical and physical dependency relationships among entities are captured in the data structure. For each entity, the data structure is configured to store (a) a “genuine event set”, which includes a list of events that originated in association with the entity; and (b) a “derived event set”, which includes a list of records in which each record is associated with an event that originated in association with an entity that has a dependency relationship (e.g., layering or topological) with the entity. The derived event set may simply comprise references to the genuine event sets for entities that have a dependency relationship with the entity.
-
Citations
60 Claims
-
1. A method for correlating events occurring in a network, wherein the network is represented as a graph of interconnected nodes with interconnections between nodes representing dependencies between the entities represented by the nodes, the method comprising the computer-implemented steps of:
-
creating a first data structure that is associated with a first entity, wherein the first data structure comprises; a first set of data that comprises a list of events that originated in association with the first entity, wherein the list of events comprises a first event that originated in association with the first entity, and a second set of data that comprises a list of records, wherein the list of records comprises a record which incorporates by reference a different, second event that originated in association with a different, second entity that has a dependency relationship with the first entity; wherein the second event is obtained by the first entity through incorporation by reference, without the second entity initiating propagation of the second event to the first entity; and determining, based at least in part on the first data structure, a likelihood that the second event caused the first event or was caused by the first event; wherein the method is performed by a computing device comprising one or more processors. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A computer-readable volatile or non-volatile storage medium storing one or more sequences of instructions for correlating events occurring in a network, wherein the network is represented as a graph of interconnected nodes with interconnections between nodes representing logical dependencies between the entities represented by the nodes, which instructions, when executed by one or more processors, cause the one or more processors to perform:
-
creating a first data structure that is associated with a first entity, wherein the first data structure comprises; a first set of data that comprises a list of events that originated in association with the first entity, wherein the list of events comprises a first event that originated in association with the first entity, and a second set of data that comprises a list of records, wherein the list of records comprises a record which incorporates by reference a different, second event that originated in association with a different, second entity that has a dependency relationship with the first entity; wherein the second event is obtained by the first entity through incorporation by reference, without the second entity initiating propagation of the second event to the first entity; and determining, based at least in part on the first data structure, a likelihood that the second event caused the first event or was caused by the first event. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. A system comprising:
-
a processor; means for creating a first data structure that is associated with a first entity, wherein the first data structure comprises, a first set of data that comprises a list of events that originated in association with the first entity, wherein the list of events comprises a first event that originated in association with the first entity, and a second set of data that comprises a list of records, wherein the list of records comprises a record which incorporates by reference a different, second event that originated in association with a different, second entity that has a dependency relationship with the first entity; wherein the second event is obtained by the first entity through incorporation by reference, without the second entity initiating propagation of the second event to the first entity; and means for determining, based at least in part on the first data structure, a likelihood that the second event caused the first event or was caused by the first event. - View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40)
-
-
41. An apparatus for correlating events occurring in a network, wherein the network can be represented as a graph of interconnected nodes with interconnections between nodes representing logical dependencies between the entities represented by the nodes the apparatus comprising:
-
a network interface that is coupled to the network for receiving one or more packet flows therefrom; a processor; one or more stored sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of; creating a first data structure that is associated with a first entity, wherein the first data structure comprises, a first set of data that comprises a list of events that originated in association with the first entity, wherein the list of events comprises a first event that originated in association with the first entity, and a second set of data that comprises a list of records, wherein the list of records comprises a record which incorporates by reference a different, second event that originated in association with a different, second entity that has a dependency relationship with the first entity; wherein the second event is obtained by the first entity through incorporation by reference, without the second entity initiating propagation of the second event to the first entity; and determining, based at least in part on the first data structure, a likelihood that the second event caused the first event or was caused by the first event. - View Dependent Claims (42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53)
-
-
54. A method for correlating events that occurred in a communications network comprising a plurality of entities, wherein the method comprises the computer-implemented steps of:
-
logically representing the network as a graph of interconnected nodes with interconnections between nodes representing logical or physical dependency relationships between the plurality of entities represented by the nodes; for each of the plurality of entities, creating, based on the graph, a data structure that comprises a genuine event set that comprises a list of event records about fault-related events issued by the entity, and a derived event set that comprises a list of event records that are each associated with a fault-related event issued by an entity that has a dependency relationship with the entity, wherein each record in the list of records in the derived event set comprises a reference to the genuine event set for each entity that has a dependency relationship with the entity, for each record listed in the second set of data, information that indicates how many nodes away, from a node that represents the first entity, is a node that represents the entity from which the associated event originated, populating each data structure with data for the genuine event set, the derived event set, the references, and the information; wherein populating each data structure with the derived event set comprises obtaining at least one event in the derived event set from an event originating entity through incorporation by reference, without the event originating entity initiating propagation of the at least one event; for one or more of the plurality of entities, reading at least some of the data structures to generate one or more candidate sets of events, wherein each candidate set of events contains a plurality of events that are likely related; and providing the one or more candidate sets of events for performing fault analysis of the network; wherein the method is performed by a computing device comprising one or more processors. - View Dependent Claims (55, 56)
-
-
57. A computer-readable volatile or non-volatile storage medium storing one or more sequences of instructions for correlating events that occurred in a communications network comprising a plurality of entities, which instructions, when executed by one or more processors, cause the one or more processors to perform:
-
logically representing the network as a graph of interconnected nodes with interconnections between nodes representing logical or physical dependency relationships between the plurality of entities represented by the nodes; for each of the plurality of entities, creating, based on the graph, a data structure that is configured to store a genuine event set that comprises a list of event records about fault-related events issued by the entity, and a derived event set that comprises a list of event records that are each associated with a fault-related event issued by an entity that has a dependency relationship with the entity, wherein each record in the list of records in the derived event set comprises a reference to the genuine event set for each entity that has a dependency relationship with the entity, for each record listed in the second set of data, information that indicates how many nodes away, from a node that represents the first entity, is a node that represents the entity from which the associated event originated, populating each data structure with data for the genuine event set, the derived event set, the references, and the information; wherein populating each data structure with the derived event set comprises obtaining at least one event in the derived event set from an event originating entity through incorporation by reference, without the event originating entity initiating propagation of the at least one event; for one or more of the plurality of entities, reading at least some of the data structures to generate one or more candidate sets of events, wherein each candidate set of events contains a plurality of events that are likely related; and providing the one or more candidate sets of events for performing fault analysis of the network.
-
-
58. A system that correlates events that occurred in a communications network comprising a plurality of entities, the system comprising:
-
a processor; means for logically representing the network as a graph of interconnected nodes with interconnections between nodes representing logical or physical dependency relationships between the plurality of entities represented by the nodes; means for creating for each of the plurality of entities, based on the graph, a data structure that is configured to store a genuine event set that comprises a list of event records about fault-related events issued by the entity, and a derived event set that comprises a list of event records that are each associated with a fault-related event issued by an entity that has a dependency relationship with the entity, wherein each record in the list of records in the derived event set comprises a reference to the genuine event set for each entity that has a dependency relationship with the entity, for each record listed in the second set of data, information that indicates how many nodes away, from a node that represents the first entity, is a node that represents the entity from which the associated event originated, means for populating each data structure with data for the genuine event set, the derived event set, the references, and the information; wherein means for populating each data structure with the derived event set comprises means for obtaining at least one event in the derived event set from an event originating entity through incorporation by reference, without the event originating entity initiating propagation of the at least one event; means for reading, for one or more of the plurality of entities, at least some of the data structures to generate one or more candidate sets of events, wherein each candidate set of events contains a plurality of events that are likely related; and means for providing the one or more candidate sets of events for performing fault analysis of the network.
-
-
59. An apparatus for correlating events occurring in a network, the apparatus comprising:
-
a network interface that is coupled to the network for receiving one or more packet flows therefrom; a processor; one or more stored sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of; logically representing the network as a graph of interconnected nodes with interconnections between nodes representing logical or physical dependency relationships between the plurality of entities represented by the nodes; for each of the plurality of entities, creating, based on the graph, a data structure that is configured to store a genuine event set that comprises a list of event records about fault-related events issued by the entity, and a derived event set that comprises a list of event records that are each associated with a fault-related event issued by an entity that has a dependency relationship with the entity, wherein each record in the list of records in the derived event set comprises a reference to the genuine event set for each entity that has a dependency relationship with the entity, for each record listed in the second set of data, information that indicates how many nodes away, from a node that represents the first entity, is a node that represents the entity from which the associated event originated, populating each data structure with data for the genuine event set, the derived event set, the references, and the information; wherein populating each data structure with the derived event set comprises obtaining at least one event in the derived event set from an event originating entity through incorporation by reference, without the event originating entity initiating propagation of the at least one event; for one or more of the plurality of entities, reading at least some of the data structures to generate one or more candidate sets of events, wherein each candidate set of events contains a plurality of events that are likely related; and providing the one or more candidate sets of events for performing fault analysis of the network.
-
-
60. A computer-readable volatile or non-volatile storage medium on which is stored a data structure configured for determining, based on the data structure, the likelihood that an event in a network that is represented as a graph of interconnected nodes with interconnections between nodes representing dependencies between the entities represented by the nodes, other than a first event reported in association with a first entity, caused the first event or was caused by the first event, wherein the data structure is configured to store:
-
a first set of data that comprises a list of events that originated in association with a first entity, a second set of data that comprises a list of records in which each record incorporates by reference an event that originated in association with an entity that has a dependency relationship with the first entity; wherein a record in the list of records incorporates by reference an event that originated in association with a second entity that has a dependency relationship with the first entity and wherein the first entity obtains the record from the second entity through incorporation by reference, without the second entity initiating propagation of the event to the first entity; and for each record listed in the second set of data, information that indicates how many nodes away, from a node that represents the first entity, is a node that represents the entity from which the event originated.
-
Specification