Method and apparatus for summarizing missing events using event stream interpretation

• US 6,662,206 B1
• Filed: 05/28/1999
• Issued: 12/09/2003
• Est. Priority Date: 05/28/1999
• Status: Expired due to Fees

• Current Assignee: International Business Corporation (Kleangas Energy Technologies, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Banavar, Guruduth S., Tao, Wei, Strom, Robert E., Sturman, Daniel C.
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US09/322,205
• Time in Patent Office: 1,656 Days
• Field of Search: 709/201, 709/224, 709/216, 709/203, 709/226, 709/202, 709/206, 709/207, 709/232, 707/9, 707/530, 705/35, 705/14, 706/11, 706/47, 703/4, 703/6, 348/88, 710/11, 717/1, 717/168, 380/271
• US Class Current: 709/201
• CPC Class Codes: H04L 12/1895 for short real-time information, e.g. alarms, notifications, alerts, updates

Abstract

A technique for optimizing published event message sequences destined for information subscribers in an information processing system. Subscribers specify event interpretation rules which map event message streams into states. The event interpretation rules are maintained elsewhere in the system in preparation for providing optimized, possibly shorter, event message streams to subscribers, sufficient to correctly update the states. If a subscriber temporarily loses access to its event message stream, the optimized event message stream is determined using a shortest path graph search technique between the states defined by the start and end of the missing portion of the stream. Optimizations to the shortest path graph search technique are disclosed for use when the event interpretation rule is in replacement form, in which estimator functions based on extended rules are employed.

Claims

1. In an event message handling system, in which a subscriber node specifies an event interpretation rule for mapping an event message stream into a first state, a method comprising:

delivering to the subscriber node an optimized version of the event message stream which correctly maps to the first state using the event interpretation rule, wherein the optimized version is a relevant summary of the event message stream based on the event interpretation rule.

2. The method of claim 1, further comprising:

a sequencer node elsewhere in the system receiving the event message stream, and using the event interpretation rule to update a second state therein as a function of incoming event messages of the event message stream delivered thereto.

3. The method of claim 2, wherein said delivering includes:

the sequencer node delivering the optimized version of the event message stream sufficient to correctly update the first state such that the first state is equivalent to the second state updated in the sequencer node.

4. The method of claim 1, wherein the subscriber node receives the event message stream from which it updates the first state therein, the method further comprising:

recovering from the subscriber node missing a portion of the event message stream, including;

a sequencer node delivering to the subscriber node an optimized version of the missing portion of the event message stream sufficient to correctly update the first state therein.

5. The method of claim 4, further comprising:

the subscriber node temporarily losing, and then regaining, its access to the event message stream thereby resulting in the portion of the event message stream missing from the subscriber node,

and wherein said delivering includes;

delivering the optimized version of the missing portion of the event message stream to the subscriber after said regaining.

6. The method of claim 4, further comprising:

using a shortest path graph search technique between a start and end of the missing portion of the event message stream to generate the optimized version of the missing portion of the event message stream.

7. The method of claim 6, wherein the event interpretation rule is in replacement form such that fields in the first state are replaced by parameters of the incoming event messages of the event message stream.

8. The method of claim 7, wherein said using a shortest path graph search technique includes:

extending the event interpretation rule in replacement form to unconstrained replacement form; and

using the extended, unconstrained replacement form rule as an estimator function in the shortest path graph search technique.

9. The method of claim 7, wherein the event interpretation rule is in unconstrained replacement form, and wherein said using a shortest path graph search technique includes:

extending the event interpretation rule in unconstrained replacement form to uniform unconstrained replacement form; and

using the extended, uniform unconstrained replacement form rule as an estimator function in the shortest path graph search technique.

10. The method of claim 7, wherein the event interpretation rule is in uniform unconstrained replacement form, and wherein said using a shortest path graph search technique includes:

using the uniform unconstrained replacement form rule as an estimator function in the shortest path graph search technique.

11. The method of claim 1, further comprising:

a plurality of subscriber nodes, including the subscriber node, each specifying a respective event interpretation rule to map a respective event message stream into a respective first state; and

a sequencer node, or a plurality of sequencer nodes, receiving the respective event message streams, and using each respective event interpretation rule to update a respective second state corresponding to a subscriber node as a function of incoming event messages of the corresponding event message stream, in preparation for delivering respective, optimized versions of the event message streams to any one or more of the subscriber nodes.

12. In an event handling system in which a subscriber node receives an event message stream from which it updates a first state therein according to an event interpretation rule, a method comprising:

a sequencer node also receiving the event message stream and updating a second state therein according to the event interpretation rule;

the subscriber node temporarily losing access to the event message stream thereby resulting in said subscriber node missing a portion of the event message stream;

the sequencer node continuing said receiving of the event message stream during the access loss of the subscriber node and continuing said updating of the second state therein; and

determining, and delivering to the subscriber node when it regains access to the event message stream, an optimized version of the missing portion of the event message stream sufficient to update the first state to be equivalent to the second state being updated in the sequencer node, wherein the optimized version is a relevant summary of the missing portion of the event message stream based on the event interpretation rule.

13. The method of claim 12, wherein said determining the optimized version of the missing portion of the event message stream includes using a shortest path graph search technique.

14. The method of claim 13, further comprising:

the subscriber node using an event interpretation rule in replacement form such that fields in the first state are replaced by parameters of the incoming event messages of the event message stream.

15. The method of claim 14, wherein said using a shortest path graph search technique includes:

extending the event interpretation rule in replacement form to unconstrained replacement form; and

using the extended, unconstrained replacement form rule as an estimator function in the shortest path graph search technique.

16. The method of claim 14, wherein the event interpretation rule is in unconstrained replacement form, and wherein said using a shortest path graph search technique includes:

extending the event interpretation rule in unconstrained replacement form to uniform unconstrained replacement form; and

using the extended, uniform unconstrained replacement form rule as an estimator function in the shortest path graph search technique.

17. The method of claim 14, wherein the event interpretation rule is in uniform unconstrained replacement form, and wherein said using a shortest path graph search technique includes:

using the uniform unconstrained replacement form rule as an estimator function by the shortest path graph search technique.

18. The method of claim 12, further comprising:

a plurality of subscriber nodes, including the subscriber node, each receiving a respective event message stream from which it updates a first state therein according to a respective event interpretation rule; and

the sequencer node, or a plurality of sequencer nodes including the sequencer node, receiving the respective event message streams, and using each respective event interpretation rule to update a respective second state corresponding to a subscriber node as a function of incoming event messages of the corresponding event message stream, in preparation for delivering respective, optimized versions of missing portions of event message streams to any one or more of the subscriber nodes in the event of a subscriber node'"'"'s loss of access to its respective event message stream.

19. In an event message handling system in which a subscriber node receives an event message stream having a state defined by an event interpretation rule, a method for preserving the state of the event message stream, comprising:

a node, other than the subscriber node, maintaining the event interpretation rule therein in preparation for providing an optimized event message stream to the subscriber node, the optimized event message stream sufficient to correctly update the first state, wherein the optimized event message stream is a relevant summary of the event message stream based on the event interpretation rule.

20. The method of claim 19, wherein the sequencer node, or a plurality of sequencer nodes including the sequencer node, maintain a plurality of event interpretation rules therein for respective subscribers of a plurality of subscriber nodes each receiving respective event message streams, in preparation for providing respective, optimized event message streams to any one or more of the subscriber nodes.

21. A method of delivering an equivalent event stream to a subscriber from one or more information providers in an event distribution system, in which said subscriber specifies an event stream interpretation rule that maps sequences of events to states, and said equivalent event stream maps to the same state as the sequence of events published by said one or more information providers, wherein said equivalent event stream is a relevant summary of the published sequence of events based on the event stream interpretation rule.

22. The method of claim 21 in which said subscriber loses connectivity with said one or more information providers, during which time missing events are published by said one or more information providers, and in which said equivalent event stream is delivered upon the one or more subscribers regaining connectivity, and in which said equivalent event stream represents a summary of said missing events.

23. The method of claim 22 in which said computing of the equivalent event stream is performed by saving the state before and after the generation of said missing events as a start and goal state respectively, and by using a shortest path graph search technique over a state transition graph determined by said event stream interpretation rule to compute the shortest path from said start state to said goal state, and delivering the equivalent event stream determined by said shortest path.

24. The method of claim 23 in which said event stream interpretation rule is specified in replacement form and in which said shortest path graph search technique is accelerated by using an estimator function derived by extending the replacement form rule to an unconstrained replacement form rule, and by extending an unconstrained replacement form rule to a uniform unconstrained replacement form rule.

25. In an event message handling system, in which a subscriber node specifies an event interpretation rule for mapping an event message stream into a first state, a system comprising:

means for delivering to the subscriber node an optimized version of the event message stream which correctly maps to the first state using the event interpretation rule, wherein the optimized version is a relevant summary of the event message stream based on the event interpretation rule.

26. The system of claim 25, further comprising:

a sequencer node elsewhere in the system for receiving the event message stream, and using the event interpretation rule to update a second state therein as a function of incoming event messages of the event message stream delivered thereto.

27. The system of claim 26, wherein said means for delivering includes:

means for the sequencer node delivering the optimized version of the event message stream sufficient to correctly update the first state such that the first state is equivalent to the second state updated in the sequencer node.

28. The system of claim 25, wherein the subscriber node receives the event message stream from which it updates the first state therein, the system further comprising:

means for recovering from the subscriber node missing a portion of the event message stream, including;

means for a sequencer node delivering to the subscriber node an optimized version of the missing portion of the event message stream sufficient to correctly update the first state therein.

29. The system of claim 28, wherein the subscriber node temporarily losing, and then regains, its access to the event message stream thereby resulting in the portion of the event message stream missing from the subscriber node,

and wherein said means for delivering includes:

means for delivering the optimized version of the missing portion of the event message stream to the subscriber after said regaining.

30. The system of claim 28, further comprising:

means for using a shortest path graph search technique between a start and end of the missing portion of the event message stream to generate the optimized version of the missing portion of the event message stream.

31. The system of claim 30, wherein the event interpretation rule is in replacement form such that fields in the first state are replaced by parameters of the incoming event messages of the event message stream.

32. The system of claim 31, wherein said means for using a shortest path graph search technique includes:

means for extending the event interpretation rule in replacement form to unconstrained replacement form; and

means for using the extended, unconstrained replacement form rule as an estimator function in the shortest path graph search technique.

33. The system of claim 31, wherein the event interpretation rule is in unconstrained replacement form, and wherein said means for using a shortest path graph search technique includes:

means for extending the event interpretation rule in unconstrained replacement form to uniform unconstrained replacement form; and

means for using the extended, uniform unconstrained replacement form rule as an estimator function in the shortest path graph search technique.

34. The system of claim 31, wherein the event interpretation rule is in uniform unconstrained replacement form, and wherein said means for using a shortest path graph search technique includes:

means for using the uniform unconstrained replacement form rule as an estimator function in the shortest path graph search technique.

35. The system of claim 25, further comprising:

a plurality of subscriber nodes, including the subscriber node, each specifying a respective event interpretation rule to map a respective event message stream into a respective first state; and

a sequencer node, or a plurality of sequencer nodes, receiving the respective event message streams, and using each respective event interpretation rule to update a respective second state corresponding to a subscriber node as a function of incoming event messages of the corresponding event message stream, in preparation for delivering respective, optimized versions of the event message streams to any one or more of the subscriber nodes.

36. In an event handling system in which a subscriber node receives an event message stream from which it updates a first state therein according to an event interpretation rule, a system comprising:

means for a sequencer node also receiving the event message stream and updating a second state therein according to the event interpretation rule;

wherein the subscriber node temporarily loses access to the event message stream thereby resulting in said subscriber node missing a portion of the event message stream;

means for the sequencer node continuing said receiving of the event message stream during the access loss of the subscriber node and continuing said updating of the second state therein; and

means for determining, and delivering to the subscriber node when it regains access to the event message stream, an optimized version of the missing portion of the event message stream sufficient to update the first state to be equivalent to the second state being updated in the sequencer node, wherein the optimized version is a relevant summary of the missing portion of the event message stream based on the event interpretation rule.

37. The system of claim 36, wherein said means for determining the optimized version of the missing portion of the event message stream includes means for using a shortest path graph search technique.

38. In an event message handling system in which a subscriber node receives an event message stream having a state defined by an event interpretation rule, a system for preserving the state of the event message stream, comprising:

a node, other than the subscriber node, maintaining the event interpretation rule therein in preparation for providing an optimized event message stream to the subscriber node, the optimized event message stream sufficient to correctly update the first state, wherein the optimized event message stream is a relevant summary of the event message stream based on the event interpretation rule.

39. The system of claim 38, wherein the sequencer node, or a plurality of sequencer nodes including the sequencer node, maintain a plurality of event interpretation rules therein for respective subscribers of a plurality of subscriber nodes each receiving respective event message streams, in preparation for providing respective, optimized event message streams to any one or more of the subscriber nodes.

40. An article of manufacture comprising a computer useable medium having computer readable program code means embodied therein for an event message handling system, in which a subscriber node specifies an event interpretation rule for mapping an event message stream into a first state, the article of manufacture comprising:

computer readable program code means for delivering to the subscriber node an optimized version of the event message stream which correctly maps to the first state using the event interpretation rule, wherein the optimized version is a relevant summary of the event message stream based on the event interpretation rule.

41. The article of manufacture of claim 40, further comprising:

computer readable program code means for a sequencer node elsewhere in the system receiving the event message stream, and using the event interpretation rule to update a second state therein as a function of incoming event messages of the event message stream delivered thereto.

42. The article of manufacture of claim 41, wherein said computer readable program code means for delivering includes:

computer readable program code means for the sequencer node delivering the optimized version of the event message stream sufficient to correctly update the first state such that the first state is equivalent to the second state updated in the sequencer node.

43. The article of manufacture of claim 40, wherein the subscriber node receives the event message stream from which it updates the first state therein, the article of manufacture further comprising:

computer readable program code means for recovering from the subscriber node missing a portion of the event message stream, including;

computer readable program code means for a sequencer node delivering to the subscriber node an optimized version of the missing portion of the event message stream sufficient to correctly update the first state therein.

44. The article of manufacture of claim 43, wherein the subscriber node temporarily loses, and then regains, its access to the event message stream thereby resulting in the portion of the event message stream missing from the subscriber node,

and wherein said computer readable program code means for delivering includes:

computer readable program code means for delivering the optimized version of the missing portion of the event message stream to the subscriber after said regaining.

45. The article of manufacture of claim 43, further comprising:

computer readable program code means for using a shortest path graph search technique between a start and end of the missing portion of the event message stream to generate the optimized version of the missing portion of the event message stream.

46. The article of manufacture of claim 45, wherein the event interpretation rule is in replacement form such that fields in the first state are replaced by parameters of the incoming event messages of the event message stream.

47. The article of manufacture of claim 46, wherein said computer readable program code means for using a shortest path graph search technique includes:

computer readable program code means for extending the event interpretation rule in replacement form to unconstrained replacement form; and

computer readable program code means for using the extended, unconstrained replacement form rule as an estimator function in the shortest path graph search technique.

48. The article of manufacture of claim 46, wherein the event interpretation rule is in unconstrained replacement form, and wherein said computer readable program code means for using a shortest path graph search technique includes:

computer readable program code means for extending the event interpretation rule in unconstrained replacement form to uniform unconstrained replacement form; and

computer readable program code means for using the extended, uniform unconstrained replacement form rule as an estimator function in the shortest path graph search technique.

49. The article of manufacture of claim 46, wherein the event interpretation rule is in uniform unconstrained replacement form, and wherein said computer readable program code means for using a shortest path graph search technique includes:

computer readable program code means for using the uniform unconstrained replacement form rule as an estimator function in the shortest path graph search technique.

50. The article of manufacture of claim 40, further comprising:

computer readable program code means for a plurality of subscriber nodes, including the subscriber node, each specifying a respective event interpretation rule to map a respective event message stream into a respective first state; and

computer readable program code means for a sequencer node, or a plurality of sequencer nodes, receiving the respective event message streams, and using each respective event interpretation rule to update a respective second state corresponding to a subscriber node as a function of incoming event messages of the corresponding event message stream, in preparation for delivering respective, optimized versions of the event message streams to any one or more of the subscriber nodes.

51. An article of manufacture comprising a computer useable medium having computer readable program code means embodied therein for an event handling system in which a subscriber node receives an event message stream from which it updates a first state therein according to an event interpretation rule, the article of manufacture comprising:

computer readable program code means for a sequencer node also receiving the event message stream and updating a second state therein according to the event interpretation rule;

wherein the subscriber node temporarily loses access to the event message stream thereby resulting in said subscriber node missing a portion of the event message stream;

computer readable program code means for the sequencer node continuing said receiving of the event message stream during the access loss of the subscriber node and continuing said updating of the second state therein; and

computer readable program code means for determining, and delivering to the subscriber node when it regains access to the event message stream, an optimized version of the missing portion of the event message stream sufficient to update the first state to be equivalent to the second state being updated in the sequencer node, wherein the optimized version is a relevant summary of the missing portion of the event message stream based on the event interpretation rule.

52. The article of manufacture of claim 51, wherein said computer readable program code means for determining the optimized version of the missing portion of the event message stream includes computer readable program code means for using a shortest path graph search technique.

53. An article of manufacture comprising a computer useable medium having computer readable program code means embodied therein for an event message handling system in which a subscriber node receives an event message stream having a state defined by an event interpretation rule, the article of manufacture for preserving the state of the event message stream, comprising:

computer readable program code means for a node, other than the subscriber node, maintaining the event interpretation rule therein in preparation for providing an optimized event message stream to the subscriber node, the optimized event message stream sufficient to correctly update the first state, wherein the optimized event message stream is a relevant summary of the event message stream based on the event interpretation rule.

54. The article of manufacture of claim 53, wherein the sequencer node, or a plurality of sequencer nodes including the sequencer node, maintain a plurality of event interpretation rules therein for respective subscribers of a plurality of subscriber nodes each receiving respective event message streams, in preparation for providing respective, optimized event message streams to any one or more of the subscriber nodes.