Determining event causality including employment of partitioned event space

• US 7,363,203 B2
• Filed: 06/27/2005
• Issued: 04/22/2008
• Est. Priority Date: 06/28/2004
• Status: Expired due to Fees

• Current Assignee: Vantos, Inc. (GoSecure, Inc.)
• Original Assignee: Graniteedge Networks
• Inventors: Hines, Ken
• Primary Examiner(s): PHAN, THAI Q
• Application Number:
  US11/168,258
• Publication Number:
  US 20050288916A1
• Time in Patent Office: 1,030 Days
• Field of Search: 703/2, 703/17, 703/22, 714/25, 717/125, 717/128, 702/183, 709/224
• US Class Current: 703/2
• 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

Causal relationships between events in a plurality of interrelated causal chains are maintained in a network event space through the partitioning of the event space into event subspaces. In this manner, events sharing the same event subspace stay constant so long as the partitioned subspace is substantially causally consistent. The causality of events from different neighboring subspaces may be determined through the individual subspace determination on each query event until a joining of shared boundary events is possible.

Claims

1. A method comprising:

receiving, by one or more computing devices, data associated with a plurality of boundary events of event subspaces of an event space comprising a plurality of events, the boundary events having been added to the event space of events to connect the event subspaces; and

determining, by the one or more computing devices, whether a first event of a first event subspace has a causality relationship with a second event of a second event subspace by first identifying one or more boundary event of the first and second event subspaces having causality relationship with the first and second events respectively.

2. The method of claim 1, further comprising maintaining, by the one or more computing devices, the data associated with the boundary events, based at least in part on the event subspaces to which the boundary events are members.

3. The method of claim 2, wherein the maintaining further comprises storing the data associated with the boundary events in one or more tables associated with the event subspace.

4. The method of claim 3, wherein the one or more tables are of one or more types selected from the group consisting of linked tables, chunk allocated tables, hash tables, and chain index tables.

5. The method of claim 2, wherein the maintaining further comprises storing the data associated with the boundary events in one or more mixed counters associated with the event subspace.

6. The method of claim 5, wherein the one or more mixed counters are of one or more types selected from the group consisting of binary mixed counters and ternary mixed counters.

7. The method of claim 2, wherein the maintaining further comprises storing the data associated with the boundary events of the event subspaces employing a multi-phase storage having a dormant phase, the dormant phase including storing causal tags for the boundary events of the event subspaces.

8. The method of claim 7, wherein the multi-phase storage further has an active phase that includes constructing causal tags for non-boundary events of the event subspaces.

9. The method of in claim 1, further comprising creating and adding the boundary events of the event subspaces to the event space of events to connect the event subspaces.

10. The method of claim 9, further comprising partitioning the event space to comprise the event subspaces.

11. The method of claim 1, wherein the determining comprises determining the first and second events as having a causality relationship if one boundary event connecting the first and second event subspace is identified as having causality relationship with the first and second events.

12. The method of claim 11, wherein the first and second boundary events are boundary events of a third event subspace, and the determining further comprises determining whether at least a third event of the third event subspace has causal relationships with both the first and second boundary event.

13. The method of claim 11, wherein the determining further comprises determining whether a first and a second different identified boundary events has a causality relationship.

14. A device comprising:

a processor;

a communication interface coupled to the processor to receive data associated with occurrences of a plurality of boundary events of event subspaces of an event space comprising a plurality of events, the boundary events having been added to the event space of events to connect the event subspaces; and

a causality module coupled to the communication interface and operated by the processor, the causality module configured to determine whether a first event of a first event subspace has a causality relationship with a second event of a second event subspace by first identifying one or more boundary events of the first and second event subspaces having causality relationship with the first and second events respectively.

15. The device of claim 14, wherein the causality module is further configured to maintain data associated with the boundary events, based at least in part on the event subspaces to which the boundary events are members.

16. The device of claim 15, wherein the causality module is further configured to maintain the data associated with the boundary events in one or more tables associated with the event subspace.

17. The device of claim 16, wherein the one or more tables are of one or more types selected from the group consisting of linked tables, chunk allocated tables, hash tables, and chain index tables.

18. The device of claim 15, wherein the causality module is further configured to maintain the data associated with the boundary events in one or more mixed counters associated with the event subspace.

19. The device of claim 18, wherein the one or more mixed counters are of one or more types selected from the group consisting of binary mixed counters and ternary mixed counters.

20. The device of claim 14, wherein the causality module is further configured to maintain the data associated with the boundary events of the event subspaces employing a multi-phase storage having a dormant phase, the dormant phase including storing causal tags for the boundary events of the event subspaces.

21. The device of claim 20, wherein the multi-phase storage further has an active phase that includes constructing causal tags for non-boundary events of the event subspaces.

22. The device of claim 14, wherein the causality module is further configured to create and add the boundary events of the event subspaces to the event space of events to connect the event subspaces.

23. The device of claim 14, wherein the causality module is further configured to determine the first and second events as having a causality relationship if one boundary event connecting the first and second event subspace is identified as having causality relationship with the first end second events.

24. The device of claim 14, wherein the causality module is further configured to maintain for event causality determination purposes, less than all the received data associated with occurrences of the plurality of boundary events.

25. The device of claim 14, wherein the causality module is further configured to partition the event space into a hierarchical divided event space.

26. The device of claim 25, wherein the causality module is further configured to determine causality without causal tables.

27. A system comprising:

at least one sensor configured to monitor for occurrences of a plurality of boundary events of event subspaces of an event space comprising a plurality of events, the boundary events having been added to the event space of events to connect the event subspaces; and

at least one causality server having a processor, communication interface, and a causality module operated by the processor, the causality server being in communication with the at least one sensor, the communication interface being configured to receive from said at least one sensor data associated with occurrences of the plurality of boundary events, and the causality module being configured to whether a first event of a first event subspace has a causality relationship with a second event of a second event subspace by first identifying one or more boundary events of the first and second event subspaces having causality relationship with the first and second events respectively.

28. The system of claim 27, wherein the causality module is further configured to maintain the data associated with the boundary events of the subspaces employing a multi-phase storage having a dormant phase, the dormant phase including storing causal tags for the boundary events of the subspaces.

29. The system of claim 28, wherein the multi-phase storage further has an active phase that includes constructing causal tags for non-boundary events of the subspaces.

30. The system of claim 27 wherein at least one sensor is assigned to each subspace in the partitioned event space.