Method and apparatus for correlating events in a network

• US 20060041659A1
• Filed: 08/23/2004
• Published: 02/23/2006
• Est. Priority Date: 08/23/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Clemm, L. Alexander, Dini, Petre, Hasan, Masum Z.
• Granted Patent: US 7,631,222 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 41/0631 using root cause analysis; using analysis of correlation between notifications, alarms or events based on decision criteria, e.g. hierarchy, tree or time analysis

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.

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, and

a second set of data that comprises 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 with the first entity; and

determining, based at least in part on the first data structure, the likelihood that an event in the network, other than a first event reported in association with the first entity, caused the first event or was caused by the first event.

2. The method of claim 1, wherein the first data structure comprises:

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.

3. The method of claim 2, wherein the second data comprises a list of records in which each record is associated with an event that originated in association with an entity on which the first entity is dependent, and wherein the step of determining comprises:

determining, based at least in part on the first data structure, the likelihood that an event in the network, other than a first event reported in association with the first entity, caused the first event.

4. The method of claim 2, wherein the second data comprises a list of records in which each record is associated with an event that originated in association with an entity that is dependent on the first entity, and wherein the step of determining comprises:

determining, based at least on the first data structure, the likelihood that one or more events in the network, other than the first event reported in association with the first entity, were caused by the first event.

5. The method of claim 2,

wherein a data structure configured like the first data structure is associated with each entity in the network, and

wherein, for each data structure, the list of records in the second set of data comprises a reference to the first set of data associated with each of one or more entity that has a dependency relationship with the entity associated with the data structure.

6. The method of claim 5, further comprising the computer-implemented step of:

in response to an event originating from the first entity,

determining that the event occurred at the first entity; and

adding, only to the list in the first set of data in the first data structure, a record of the event that originated in association with the first entity.

7. The method of claim 5, further comprising the computer-implemented step of:

identifying, based at least in part on the data structures, a set of one or more events in the network that may have caused the first event.

8. The method of claim 7, further comprising the computer-implemented step of:

providing the set of one or more events to an inference engine that performs fault analysis of the network.

9. The method of claim 5, further comprising the computer-implemented step of:

identifying, based at least in part on the data structures, a set of one or more events in the network that may have been caused by the first event.

10. The method of claim 9, further comprising the computer-implemented step of:

providing the set of one or more events to an inference engine that performs fault analysis of the network.

11. The method of claim 2,

wherein the second set of data comprises a list of records in which each record is associated with an event that originated in association with an entity that is one node away from the node that represents the first entity;

and

wherein n additional sets of data in the first data structure each comprise a list of records in which each record is associated with an event that originated in association with an entity (a) that has a dependency relationship with the node that represents the first entity and (b) that is n+1 nodes away from the node that represents the first entity.

12. The method of claim 11,

wherein the second and the n sets of data are configured as an array of data;

and

wherein the position of each set of data in the array is the information that indicates how many nodes away, from the node that represents the first entity, are the entities from which the associated events originated.

13. The method of claim 1, wherein the events occurring in the network are associated with faults occurring in the network.

14. The method of claim 1, wherein the network is a packet-switched network.

15. A computer-readable 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, and

a second set of data that comprises 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 with the first entity; and

determining, based at least in part on the first data structure, the likelihood that an event in the network, other than a first event reported in association with the first entity, caused the first event or was caused by the first event.

16. The computer-readable medium of claim 15, wherein the first data structure comprises:

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.

17. The computer-readable medium of claim 16, wherein the second data comprises a list of records in which each record is associated with an event that originated in association with an entity on which the first entity is dependent, wherein the instructions cause the one or more processors to perform the step of determining by determining, based at least in part on the first data structure, the likelihood that an event in the network, other than a first event reported in association with the first entity, caused the first event.

18. The computer-readable medium of claim 16, wherein the second data comprises a list of records in which each record is associated with an event that originated in association with an entity that is dependent on the first entity, wherein the instructions cause the one or more processors to perform the step of determining by determining, based at least on the first data structure, the likelihood that one or more events in the network, other than the first event reported in association with the first entity, were caused by the first event.

19. The computer-readable medium of claim 16,

wherein a data structure configured like the first data structure is associated with each entity in the network, and

wherein, for each data structure, the list of records in the second set of data comprises a reference to the first set of data associated with each of one or more entity that has a dependency relationship with the entity associated with the data structure.

20. The computer-readable medium of claim 19, wherein the instructions cause the one or more processors to perform:

in response to an event originating from the first entity,

determining that the event occurred at the first entity; and

adding, only to the list in the first set of data in the first data structure, a record of the event that originated in association with the first entity.

21. The computer-readable medium of claim 19, wherein the instructions cause the one or more processors to perform:

identifying, based at least in part on the data structures, a set of one or more events in the network that may have caused the first event.

22. The computer-readable medium of claim 21, wherein the instructions cause the one or more processors to perform:

providing the set of one or more events to an inference engine that performs fault analysis of the network.

23. The computer-readable medium of claim 19, wherein the instructions cause the one or more processors to perform:

identifying, based at least in part on the data structures, a set of one or more events in the network that may have been caused by the first event.

24. The computer-readable medium of claim 23, wherein the instructions cause the one or more processors to perform:

providing the set of one or more events to an inference engine that performs fault analysis of the network.

25. The computer-readable medium of claim 16,

wherein the second set of data comprises a list of records in which each record is associated with an event that originated in association with an entity that is one node away from the node that represents the first entity;

and

wherein n additional sets of data in the first data structure each comprise a list of records in which each record is associated with an event that originated in association with an entity (a) that has a dependency relationship with the node that represents the first entity and (b) that is n+1 nodes away from the node that represents the first entity.

26. The computer-readable medium of claim 25,

wherein the second and the n sets of data are configured as an array of data;

and

wherein the position of each set of data in the array is the information that indicates how many nodes away, from the node that represents the first entity, are the entities from which the associated events originated.

27. The computer-readable medium of claim 15, wherein the network is a packet-switched network.

28. A system comprising:

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, and

a second set of data that comprises 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 with the first entity; and

means for determining, based at least in part on the first data structure, the likelihood that an event in the network, other than a first event reported in association with the first entity, caused the first event or was caused by the first event

29. The system of claim 28, wherein the first data structure is configured to store, 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.

30. The system of claim 29, wherein the second data comprises a list of records in which each record is associated with an event that originated in association with an entity on which the first entity is dependent, and wherein the means for determining comprise:

means for determining, based at least in part on the first data structure, the likelihood that an event in the network, other than a first event reported in association with the first entity, caused the first event.

31. The system of claim 29, wherein the second data comprises a list of records in which each record is associated with an event that originated in association with an entity that is dependent on the first entity, and wherein the means for determining comprise:

means for determining, based at least on the first data structure, the likelihood that one or more events in the network, other than the first event reported in association with the first entity, were caused by the first event.

32. The system of claim 29,

wherein a data structure configured like the first data structure is associated with each entity in the network, and

wherein, for each data structure, the list of records in the second set of data comprises a reference to the first set of data associated with each of one or more entity that has a dependency relationship with the entity associated with the data structure.

33. The system of claim 32, further comprising:

means for determining that an event occurred at the first entity, in response to the event originating from the first entity; and

means for adding, only to the list in the first set of data in the first data structure, a record of the event that originated in association with the first entity.

34. The system of claim 32, further comprising:

means for identifying, based at least in part on the data structures, a set of one or more events in the network that may have caused the first event.

35. The system of claim 34, further comprising:

means for providing the set of one or more events to an inference engine that performs fault analysis of the network.

36. The system of claim 32, further comprising:

means for identifying, based at least in part on the data structures, a set of one or more events in the network that may have been caused by the first event.

37. The system of claim 36, further comprising:

means for providing the set of one or more events to an inference engine that performs fault analysis of the network.

38. The system of claim 29,

wherein the second set of data comprises a list of records in which each record is associated with an event that originated in association with an entity that is one node away from the node that represents the first entity;

and

wherein n additional sets of data in the first data structure each comprise a list of records in which each record is associated with an event that originated in association with an entity (a) that has a dependency relationship with the node that represents the first entity and (b) that is n+28 nodes away from the node that represents the first entity.

39. The system of claim 38,

wherein the second and the n sets of data are configured as an array of data;

and

wherein the position of each set of data in the array is the information that indicates how many nodes away, from the node that represents the first entity, are the entities from which the associated events originated.

40. The system of claim 28, wherein the network is a packet-switched network.

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, and

a second set of data that comprises 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 with the first entity; and

determining, based at least in part on the first data structure, the likelihood that an event in the network, other than a first event reported in association with the first entity, caused the first event or was caused by the first event.

42. The apparatus of claim 41, wherein the first data structure is configured to store, 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.

43. The apparatus of claim 42, wherein the second data comprises a list of records in which each record is associated with an event that originated in association with an entity on which the first entity is dependent, and wherein the instructions further cause the processor to perform the step of determining by:

determining, based at least in part on the first data structure, the likelihood that an event in the network, other than a first event reported in association with the first entity, caused the first event.

44. The apparatus of claim 42, wherein the second data comprises a list of records in which each record is associated with an event that originated in association with an entity that is dependent on the first entity, and wherein the instructions further cause the processor to perform the step of determining by:

determining, based at least on the first data structure, the likelihood that one or more events in the network, other than the first event reported in association with the first entity, were caused by the first event.

45. The apparatus of claim 42,

wherein a data structure configured like the first data structure is associated with each entity in the network, and

wherein, for each data structure, the list of records in the second set of data comprises a reference to the first set of data associated with each of one or more entity that has a dependency relationship with the entity associated with the data structure.

46. The apparatus of claim 45, and wherein the instructions further cause the processor to perform the step of:

in response to an event originating from the first entity,

determining that the event occurred at the first entity; and

adding, only to the list in the first set of data in the first data structure, a record of the event that originated in association with the first entity.

47. The apparatus of claim 45, and wherein the instructions further cause the processor to perform the step of:

identifying, based at least in part on the data structures, a set of one or more events in the network that may have caused the first event.

48. The apparatus of claim 47, and wherein the instructions further cause the processor to perform the step of:

providing the set of one or more events to an inference engine that performs fault analysis of the network.

49. The apparatus of claim 45, and wherein the instructions further cause the processor to perform the step of:

identifying, based at least in part on the data structures, a set of one or more events in the network that may have been caused by the first event.

50. The apparatus of claim 49, and wherein the instructions further cause the processor to perform the step of:

providing the set of one or more events to an inference engine that performs fault analysis of the network.

51. The apparatus of claim 42,

wherein the second set of data comprises a list of records in which each record is associated with an event that originated in association with an entity that is one node away from the node that represents the first entity;

and

wherein n additional sets of data in the first data structure each comprise a list of records in which each record is associated with an event that originated in association with an entity (a) that has a dependency relationship with the node that represents the first entity and (b) that is n+1 nodes away from the node that represents the first entity.

52. The apparatus of claim 51,

wherein the second and the n sets of data are configured as an array of data;

and

wherein the position of each set of data in the array is the information that indicates how many nodes away, from the node that represents the first entity, are the entities from which the associated events originated.

53. The method of claim 41, wherein the network is a packet-switched network.

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;

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.

55. The method of claim 54, wherein, for a first entity of the plurality of entities, the plurality of events in a candidate event set likely caused one or more particular events to issue by the first entity.

56. The method of claim 54, wherein, for a first entity of the plurality of entities, the plurality of events in a candidate event set were likely caused by one or more particular events issued by the first entity.

57. A computer-readable 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;

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:

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;

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;

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 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 is associated with an event that originated in association with an entity that has a dependency relationship with 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 associated event originated.