Summary-based routing for content-based event distribution networks

• US 7,200,675 B2
• Filed: 03/14/2003
• Issued: 04/03/2007
• Est. Priority Date: 03/13/2003
• Status: Active Grant

• Current Assignee: Intel Corporation, Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Yi-Min, Larson, Per-Ake, Das, Gautam, Qiu, Lili, Achlioptas, Demetrios, Verbowski, Chad E.
• Primary Examiner(s): Vaughn; William
• Assistant Examiner(s): MESFIN, YEMANE
• Application Number:
  US10/389,623
• Publication Number:
  US 20040181588A1
• Time in Patent Office: 1,481 Days
• Field of Search: 709/203, 709/207, 709/219, 709/245, 709/238, 709/240
• US Class Current: 709/238
• CPC Class Codes: H04L 12/1859 adapted to provide push services, e.g. data channels
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A system and method for enabling highly scalable multi-node event distribution networks through the use of summary-based routing, particularly event distribution networks using a content-based publish/subscribe model to distribute information. By allowing event routers to use imprecise summaries of the subscriptions hosted by matcher nodes, an event router can eliminate itself as a bottleneck thus improving overall event distribution network throughput even though the use of imprecise summaries results in some false positive event traffic. False positive event traffic is reduced by using a filter set partitioning that provides for good subscription set locality at each matcher node, while at the same time avoiding overloading any one matcher node. Good subscription set locality is maintained by routing new subscriptions to a matcher node with a subscription summary that best covers the new subscription. Where event space partitioning is desirable, an over-partitioning scheme is described that enables load balancing without repartitioning.

Claims

1. A computerized event distribution system, comprising:

a source of event messages;

a plurality of matchers for determining whether received ones of the event messages fall within an event message scope defined by each of a set of hosted subscriptions and issuing corresponding notification messages to corresponding subscriber clients; and

at least one event message router communicatively coupled to the source of event messages and programmed to selectively pass event messages to the plurality of matchers, wherein the event message router is configured to maintain, for each one of the plurality of matchers, an imprecise summary of subscriptions for which each of the plurality of matchers is responsible the imprecise summary having a level of summary precision that is less than 100%;

wherein the at least one event message router is programmed to pass some amount of false positive event messages to the plurality of matchers based on a level of precision of the imprecise summary of subscriptions for each one of the plurality of matchers; and

wherein the at least one event message router is configured such that the level of precision of each imprecise summary of subscriptions is variable based at least in part on a load of the at least one event message router.

2. The system of claim 1, wherein the ax least one event router is further configured to maintain, for each one of the plurality of matchers, a plurality of imprecise summaries of subscriptions for which each of the plurality of matchers is responsible.

3. The system of claim 1, wherein each subscription for which a matcher is responsible comprises a set of predicates describing an area of event space.

4. The system of claim 3, wherein each subscription for which a matcher is responsible further comprises a notification address for notifying a subscriber if an event falls within the area of event space described byte set of predicates.

5. The system of claim 1, wherein a matcher is further configured to send a notification to a notification address associated with a subscription when an event matches the subscription.

6. The system of claim 1, wherein an imprecise summary of the set of subscriptions for which a matcher is responsible comprises a set of the maximal elements of a partially ordered set of the subscription filters associated with the subscriptions for which a matcher is responsible, wherein at least two of the maximal set elements have been replaced by their minimum bounding rectangle.

7. The system of claim 1, wherein the at least one event message router is configured to vary the level of precision of the imprecise summaries in response to a load of the at least one event message router.

8. The system of claim 1, wherein the at least one event message router is configured to reduce the level of precision of the imprecise summaries if the at least one event message router is overloaded.

9. The system of claim 8, wherein the at least one event message router is further configured to increase the level of precision of imprecise summaries if the at least one event message router load is under a threshold.

10. The system of claim 9, wherein the at least one event message router is further configured to dampen oscillations in the level of summary precision.

11. A computer-implemented method, comprising:

assigning, to each of a plurality of matcher nodes, a subset of subscriptions hosted by an event distribution network;

maintaining, at an event router node, for each of the plurality of matcher nodes, at least one imprecise summary of the subscriptions assigned to a matcher node, the at least one imprecise summary having a level of summary precision that is less than 100%;

for each of the plurality of matcher nodes, reciving event messages at the event router node, the event messages comprising first event messages falling within the imprecise summary of the subscriptions assigned to matcher node and second false positive event messages falling outside of the imprecise summary of the subscriptions assigned to the matcher node, and passing all of the first event messages and at least some of the second false positive event messages from the event router node to the matcher node based on the imprecise summary of subscriptions for the matcher node; and

varying a level of precision of at least one imprecise summary of subscriptions based at least in part on a load of the event router node.

12. The method according to claim 11, wherein maintaining an imprecise summary of the subscriptions assigned to a matcher nods comprises:

receiving, from a matcher node, a precise summary of the subscriptions assigned to the matcher node; and

reducing the level of precision of the precise summary.

13. The method according to claim 12, wherein the precise summary received by an event router node comprises the maximal elements of a partially ordered set of subscription filters associated with the subscriptions assigned to the matcher node, the maximal elements being indexed by an R-tree, and wherein reducing the level of precision of the precise summary comprises replacing at least a pair of the maximal elements indexed by adjacent R-tree leaf nodes with their minimum bounding rectangle.

14. The method according to claim 12, wherein the precise summary received by an event router node comprises a set of subscription filters associated with the subscriptions assigned to the matcher node, each subscription filter comprising a set of predicates on the attributes of an event schema and at least one of those predicates required to be an equality predicate, and wherein reducing the level of precision of the precise summary comprises, for each predicate required to be an equality predicate, loading a Bloom filter with that predicate from each subscription filter.

15. The method according to claim 11, further comprising measuring event distribution network throughput for different levels of precision of the imprecise summary maintained at an event router node.

16. The method according to claim 15, further comprising setting the level of precision of the imprecise summary maintained at an event router node to the level that resulted in the highest measured event distribution network throughput.

17. A computer-readable storage medium having stored thereon computer executable instructions for performing a method comprising:

assigning, to each of a plurality of matcher nodes, a subset of subscriptions hosted by an event distribution network;

maintaining, at an event router node, for each of the plurality of matcher nodes, at least one imprecise summary of the subscriptions assigned to a matcher node, the at least one imprecise summary level of summary precision is less than 100%;

for each of the plurality of matcher nodes, receiving event messages at the event router node, the event messages comprising first event messages falling within the imprecise summary of the subscriptions assigned to matcher node and second false positive event messages falling outside of the imprecise summary of the subscriptions assigned to the matcher node, and passing all of the first event messages and at least some of the second false positive event messages from the event router node to the matcher node based on the imprecise summary of subscriptions for the matcher node; and

varying a level of precision of at least one imprecise summary of subscriptions based at least in part on a load of the event router node.

18. A computerized first event distribution network node, comprising:

a subscription summary module configured to maintain an imprecise summary of subscriptions hosted by a second event distribution network node, the imprecise summary having a level of summary precision that is less tan 100%;

a route event module configured to route an event to the second event distribution network node if the event falls within the imprecise summary of subscriptions; and

a tune routing precision module configured to vary the level of precision of the imprecise summary of subscriptions maintained by the subscription summary module so as to vary a number of false positive events routed to the second event distribution network node based at least in part on a load of the event distribution node.

19. The computerized event distribution network node of claim 18, wherein the tune routing precision module is configured to reduce the level of precision of the imprecise summary of subscriptions maintained by the subscription summary module if the first event distribution network node is overloaded.

20. The computerized first event distribution network node of claim 19, wherein the tune routing precision module is further configured to increase the level of precision of the imprecise summary of subscriptions maintained by the subscription summary module if the first event distribution network node is under a threshold.

21. The computerized first event distribution network node of claim 20, wherein the tune routing precision module is further configured to dampen oscillations in the level of summary precision.

22. The computerized first event distribution network node of claim 18, further comprising an update route module capable of:

sending and receiving summaries of subscriptions hosted by the second event distribution network node; and

updating an imprecise summary maintained by the subscription summary module.

23. The computerized first event distribution network node of claim 22, wherein the update route module is further capable of aggregating summaries of subscriptions hosted by one or more event distribution network nodes.

24. The computerized first event distribution network node of claim 18, further comprising a route subscription module capable of routing a new subscription to an event distribution network node wit an imprecise summary of subscriptions already hosted by the event distribution network node that best covers the new subscription.

25. The computerized first event distribution network node of claim 18, wherein each imprecise summary is maintained in a Web Services namespace, wherein each event, each subscription and each subscription summary is capable of being represented by an extended mark-up language (XML) message, and wherein an event is routed to an event distribution network node in compliance with a simple object access protocol (SOAP).

26. The computerized first event distribution network node of claim 25, wherein each subscription summary is indexed by an R-tree.