Performing efficient insertions in wavefront table based causal graphs

• US 20070032987A1
• Filed: 08/03/2006
• Published: 02/08/2007
• Est. Priority Date: 08/05/2005
• Status: Active Grant

• Current Assignee: Vantos, Inc. (GoSecure, Inc.)
• Original Assignee: Graniteedge Networks
• Inventors: Hines, Ken
• Granted Patent: US 7,487,241 B2
• Time in Patent Office: Days
• US Class Current: 702/183
• 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 causal relationship between two events occurs when a first event meaningfully precedes a second event and is identified by a causality module. The causality module analyzes multiple events to determine whether the events are causally related. Reductions in both required storage space and search operations are obtained by tracing interrelated causal chains of events. Further improvement is achieved by reducing re-computation of wavefront tables through annotating causality chain with information that facilitates determination of validity of a wavefront table.

Claims

1. A method to be performed on a computing device, comprising:

receiving and storing event association data for a plurality of events;

determining causality of events employing causal chains of events and wavefront tables of events, with each wavefront table having one or more entries identifying one or more predecessor events of an event in terms of one or more causal chain membership and locations within, and each causal chain having an associated count identifying the highest valid table entry for the causal chain.

2. The method of claim 1, further comprising organizing the events into the causal chains, computing the wavefront tables, and assigning the count to each causal chain.

3. The method of claim 2, further comprising before using a wavefront table, determining whether entries of the wavefront table are valid by comparing the entries of the wavefront table with the counts of the causal chains.

4. The method of claim 3, further comprising considering a wavefront table invalid if any entry of the wavefront table is greater than any count of any of the causal chains.

5. The method of claim 4 further comprising re-computing the wavefront table on determining at least one entry of the wavefront table is invalid.

6. The method of claim 5 further comprising re-computing wavefront table(s) for successor event(s) of the event with the invalid entry.

7. The method of claim 5 further comprising re-computing wavefront table(s) for successor event(s) with the same count for the causal chain as the event with the invalid entry.

8. A device comprising:

a communication interface to receive data associated with a plurality of events having event association data stored for event causality determination;

a causality module coupled to the communication interface configured to determine causality of the events employing causal chains of events and wavefront tables of events, with each wavefront table having one or more entries identifying one or more predecessor events of an event in terms of one or more causal chain membership and locations within, and each causal chain having an associated count identifying the highest valid table entry for the causal chain.

9. The device as recited in claim 8, wherein the causality module is configured to organize the events into the causal chains, to compute the wavefront tables, and to assign the count to each causal chain.

10. The device as recited in claim 8, wherein the causality module is configured to determine whether entries of the wavefront table are valid by comparing the entries of the wavefront table with the counts of the causal chains.

11. The device as recited in claim 10, wherein the causality module is configured to consider a wavefront table invalid if any entry of the wavefront table is greater than any count of any of the causal chains.

12. The device as recited in claim 11, wherein the causality module is configured to re-compute the wavefront table on determining at least one entry of the wavefront table is invalid.

13. The device as recited in claim 12, wherein the causality module is configured to re-compute a successor wavefront table for any successor event of the event with the invalid entry.

14. The device as recited in claim 12, wherein the causality module is configured to re-compute a successor wavefront table for any event having the same count in an entry for the causal chain of the successor wavefront table as the event for the causal chain with the invalid entry.

15. The device as recited in claim 14, wherein the causality module is configured to revise the count to identify the next highest valid table entry for the causal chain after re-computing all wavefront tables associated with events having the same count as the event with the invalid entry.

16. A system comprising:

memory configured to store event association data for a plurality of events employing causal chains of events and wavefront tables of events;

at least one causality server having a communication interface and a causality module, the causality server being in communication with said memory, the communication interface being configured to receive event association data with said memory, and the causality module being configured to determine causality of events, with each wavefront table having one or more entries identifying one or more predecessor events of an event in terms of one or more causal chain membership and locations within, and each causal chain having an associated count identifying the highest valid table entry for the causal chain.

17. The system as recited in claim 16, wherein the causality module is configured to organize the events into the causal chains, to compute the wavefront tables, and to assign the count to each causal chain.

18. The system as recited in claim 16, wherein the causality module is configured to determine whether entries of the wavefront table are valid by comparing the entries of the wavefront table with the counts of the causal chains.

19. The system as recited in claim 18, wherein the causality module is configured to consider a wavefront table invalid if any entry of the wavefront table is greater than any count of any of the causal chains.

20. The system as recited in claim 19, wherein the causality module is configured to re-compute the wavefront table on determining at least one entry of the wavefront table is invalid.