# US 2006/0041659 A1 · Method and apparatus for correlating events in a network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0041659 A1
- Document ID: US20060041659A1
- Status: Published application
- Kind: A1
- Application number: 10/924,702
- Filed: 2004-08-23
- Published: 2006-02-23
- Earliest claimed: 2004-08-23
- Assignees: Cisco Technology, Inc.
- Inventors: Masum Hasan; L. Clemm; Petre Dini
- Web page: https://patentgrep.com/patent/US20060041659A1

## CPC

- 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
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### 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, 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 2)

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.

### Claim 5 (depends on 2)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 5)

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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 5)

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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 2)

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.

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 1)

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

### Claim 14 (depends on 1)

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

### Claim 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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 16)

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.

### Claim 19 (depends on 16)

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.

### Claim 20 (depends on 19)

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.

### Claim 21 (depends on 19)

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.

### Claim 22 (depends on 21)

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.

### Claim 23 (depends on 19)

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.

### Claim 24 (depends on 23)

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.

### Claim 25 (depends on 16)

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.

### Claim 26 (depends on 25)

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.

### Claim 27 (depends on 15)

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

### Claim 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

### Claim 29 (depends on 28)

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.

### Claim 30 (depends on 29)

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.

### Claim 31 (depends on 29)

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.

### Claim 32 (depends on 29)

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.

### Claim 33 (depends on 32)

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.

### Claim 34 (depends on 32)

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.

### Claim 35 (depends on 34)

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.

### Claim 36 (depends on 32)

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.

### Claim 37 (depends on 36)

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.

### Claim 38 (depends on 29)

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.

### Claim 39 (depends on 38)

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.

### Claim 40 (depends on 28)

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

### Claim 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.

### Claim 42 (depends on 41)

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.

### Claim 43 (depends on 42)

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.

### Claim 44 (depends on 42)

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.

### Claim 45 (depends on 42)

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.

### Claim 46 (depends on 45)

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.

### Claim 47 (depends on 45)

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.

### Claim 48 (depends on 47)

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.

### Claim 49 (depends on 45)

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.

### Claim 50 (depends on 49)

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.

### Claim 51 (depends on 42)

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.

### Claim 52 (depends on 51)

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.

### Claim 53 (depends on 41)

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

### Claim 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.

### Claim 55 (depends on 54)

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.

### Claim 56 (depends on 54)

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.

### Claim 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.

### Claim 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.

### Claim 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.

### Claim 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.
