Summary-based routing for content-based event distribution networks

Abstract

A system arid 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.

1 - 18 . (canceled)  
   
   
       19 . A computer-implemented method, comprising: dividing subscriptions hosted by an event distribution network into a plurality of subsets, one subset of subscriptions for each matcher node in the event distribution network, such that each subset of subscriptions has good event space locality and covers a corresponding area of event space; 
 assigning each subset of subscriptions to a matcher node;    maintaining, at an event router node, a summary of the set of subscriptions assigned to a matcher node; and    routing an event from an event router node to a matcher node if the event falls within the summary of the set of subscriptions assigned to the matcher node.    
   
   
       20 . The method according to  claim 19 , wherein dividing subscriptions hosted by an event distribution network into a plurality of subsets, one for each matcher node in the event distribution network, such that each subset of subscriptions has good event space locality and covers a corresponding area of event space comprises: 
 setting the number of child nodes of the root node of a partitioning R-tree to be equal to the number of matcher nodes in an event distribution network;    loading the partitioning R-tree top-down with the subscriptions hosted by the event distribution network such that, for each partitioning of the subscription filter set associated with the subscriptions, the subscription filter set is partitioned to minimize the minimum bounding rectangle of the subscription filter subsets on each side of a partition; and    choosing a subset of subscriptions to be the subscriptions indexed by the sub-tree rooted at a child node of the root node of the loaded partitioning R-tree.    
   
   
       21 . The method according to  claim 19 , further comprising: 
 maintaining, at a subscription router node, for each of the plurality of matcher nodes, an imprecise summary of the subscriptions assigned to a matcher node;    receiving, at a subscription router node, a new subscription to be hosted by the event distribution network;    determining, at a subscription router node, which of the imprecise summaries best covers the new subscription; and    assigning the new subscription to the matcher node with the best imprecise summary.    
   
   
       22 . The method according to  claim 21 , wherein each imprecise summary comprises a plurality of data rectangles indexed by an R-tree, and wherein determining which of the imprecise summaries best covers the new subscription comprises: 
 calculating the overlap between the subscription filter rectangle associated with the new subscription and each data rectangle indexed by a leaf-node of each imprecise summary R-tree; and    choosing the imprecise summary with the data rectangle that has the maximum overlap with the new subscription.    
   
   
       23 . A computer-readable medium having thereon computer executable instructions for performing a method comprising: 
 dividing subscriptions hosted by an event distribution network into a plurality of subsets, one for each matcher node in the event distribution network, such that each subset of subscriptions has good event space locality and covers a corresponding area of event space;    assigning each subset of subscriptions to a matcher node;    maintaining, at an event router node, a summary of the set of subscriptions assigned to a matcher node; and    routing an event from an event router node to a matcher node if the event falls within the summary of the set of subscriptions assigned to the matcher node.    
   
   
       24 . A computer-implemented method, comprising: 
 partitioning an event space such that the number of event space partitions exceeds the number of matcher nodes in an event distribution network;    assigning responsibility for a set of event space partitions to each matcher node;    assigning each subscription to be hosted to the at least one matcher node responsible for an event space partition that the subscription falls within;    maintaining, at an event router node, a summary of the set of subscriptions assigned to a matcher node; and    routing an event from an event router node to a matcher node if the event falls within the summary of the set of subscriptions assigned to the matcher node.    
   
   
       25 . The method according to  claim 24 , wherein the event space partitions are each orthogonal to an equality filtered dimension of the event space, wherein the number of event space partitions is a multiple of the number of matcher nodes in an event distribution network and wherein assigning a set of event space partitions to each matcher node comprises: 
 assigning each event space partition a weight that is the product of the number of subscriptions hosted by the event distribution network that subscribe to the event space partition and the number of unique equality predicates on the equality filtered dimension in the subscriptions hosted by the event distribution network that subscribe to the event space partition;    sorting the event space partitions in order of decreasing weight;    assigning each event space partition in sorted order to a matcher node that has a lowest cumulative event space partition weight at the time of assignment.    
   
   
       26 . The method according to  claim 25 , further comprising: 
 re-calculating, after initial event space partition assignment, each event space partition weight;    repeatedly re-assigning a lowest weight event space partition currently assigned to a most heavily loaded matcher node to a matcher node that has a lowest cumulative event space partition weight at the time of re-assignment, until the heavily loaded matcher node is no longer most heavily loaded.    
   
   
       27 . The method according to  claim 24 , further comprising re-assigning an event space partition from a heavily loaded matcher node to a less heavily loaded matcher node.  
   
   
       28 . A computer-readable medium having thereon computer executable instructions for performing a method comprising: 
 partitioning an event space such that the number of event space partitions is a multiple of the number of matcher nodes in an event distribution network;    assigning responsibility for a set of event space partitions to each matcher node;    assigning each subscription to be hosted to the at least one matcher node responsible for an event space partition that the subscription falls within;    maintaining, at an event router node, a summary of the set of subscriptions assigned to a matcher node; and    routing an event from an event router node to a matcher node if the event falls within the summary of the set of subscriptions assigned to the matcher node.    
   
   
       29 - 37 . (canceled)