Method and system for matching consumers to events employing content-based multicast routing using approximate groups

• US 6,728,715 B1
• Filed: 03/30/2000
• Issued: 04/27/2004
• Est. Priority Date: 03/30/2000
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Strom, Robert E., Astley, Mark, Sturman, Daniel C.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US09/538,471
• Time in Patent Office: 1,489 Days
• Field of Search: 707/10, 707/100, 395/33, 395/275, 395/375, 725/34, 725/35
• US Class Current: 707/737
• CPC Class Codes: H04L 12/1859 adapted to provide push services, e.g. data channels
• CPC Class Codes: H04L 67/30 Profiles
• 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
• CPC Class Codes: Y10S 707/959 Network

Abstract

A facility is provided for distributing events to consumers in a content-based publish-subscribe system, wherein the consumers each have at least one subscription. The facility includes deriving a set of g approximate multicast groups from a larger set of G possible multicast groups in the publish-subscribe system. The deriving includes exploiting knowledge of subscription predicates of the consumers of the publish-subscribe system. The set of G possible multicast groups is collapsed to the smaller set of g approximate multicast groups, while minimizing the expected performance penalty in using the approximate multicast groups. The set of g approximate multicast groups is then used to forward events to consumers within the publish-subscribe system.

Claims

1. A method for distributing events to consumers in a content-based publish-subscribe system, wherein the consumers each have at least one subscription, said method comprising:

outside of event processing time, deriving a set of g approximate multicast groups from a larger set of G possible multicast groups in the publish-subscribe system, said deriving including exploiting knowledge of subscription predicates of at least some consumers of the publish-subscribe system;

using at least one multicast group of said set of g approximate multicast groups to forward an event to at least one consumer within the publish-subscribe system; and

wherein said deriving comprises employing a cost function to combine the possible multicast groups of the set of G possible multicast groups to arrive at the set of g approximate multicast groups.

2. The method of claim 1, wherein said exploiting comprises using probabilities that the subscriptions in the publish-subscribe system will match an event to condense the set of G possible multicast groups into the set of g approximate multicast groups.

3. The method of claim 1, wherein said deriving comprises determining a probability distribution of events in the publish-subscribe system and using the probability distribution of events to determine a probability for each of at least some subscriptions in the publish-subscribe system that the subscription will match an event, and condensing the set of G possible multicast groups into the set of g approximate multicast groups using the probabilities for the at least some subscriptions.

4. The method of claim 3, wherein said using the probability distribution of events to determine the probability for each of at least some subscriptions in the publish-subscribe system matching an event comprises using the probability distribution of events to determine a probability for each subscription in the publish-subscribe system that the subscription will match an event, and wherein said using the subscription probabilities comprises using the subscription probabilities for all subscriptions to condense the set of G possible multicast groups into the set of g approximate multicast groups.

5. The method of claim 3, wherein said deriving further comprises building an initial groups lattice using the probability distribution of events and the subscription probabilities of the at least some subscriptions, wherein the initial groups lattice includes a node corresponding to each possible multicast group and each node has associated therewith a probability that that node will receive an event.

6. The method of claim 5, wherein said condensing of the possible multicast groups comprises creating an approximate groups table wherein each row of the approximate groups table initially corresponds to a node of the initial groups lattice, and wherein said condensing comprises combining rows of the approximate groups table until a final approximate groups table is reached, wherein each row of the final approximate groups table comprises one approximate multicast group of the set of g approximate multicast groups.

7. The method of claim 6, wherein said combining rows of the approximate groups table comprises combining selected pairs of rows of the approximate groups table, wherein each selected pair is chosen based on consideration of a system cost for combining said selected pair of rows of the approximate groups table, wherein said system cost incorporates the probability of each group receiving an event, and wherein said combining seeks to minimize system costs.

8. The method of claim 6, wherein said combining at least two rows of the approximate groups table comprises combining rows of the approximate groups table until a desired number of rows in the approximate groups table is reached, wherein said desired number of rows equals said number g of approximate multicast groups in said set of g approximate multicast groups.

9. The method of claim 6, wherein said creating of the approximate groups table includes initially sorting rows thereof based on probability that the corresponding node of the initial groups lattice will receive an event, said sorting being from lowest probability to highest probability, and wherein said condensing possible multicast groups comprises condensing at least two rows out of N nodes first listed in the approximate groups table.

10. The method of claim 6, wherein said using comprises testing content of the event to be distributed to determine a node in the initial groups lattice and a set of local consumers needing the event;

and sending the event to the approximate multicast group corresponding to a row in the approximate groups table to which the node was collapsed, and to the local consumers thereof.

11. The method of claim 10, further comprising for each subscriber broker in the approximate multicast group to which the node was collapsed, receiving the event and forwarding the event to consumers thereof whose subscriptions match the event.

12. The method of claim 1, wherein said deriving comprises ascertaining said set of g approximate multicast groups to meet a specified tolerance on one of a maximum number of multicast groups or a maximum percentage of wasted event messages during matching of the event to the consumer.

13. The method of claim 1, wherein said deriving comprises obtaining:

(i) a set of subscriptions expressed as conjunctions of equality tests on event attributes, and a destination address per subscription;

(ii) a frequency distribution of possible values of each event attribute; and

(iii) a tolerance specifying either a maximum number of groups to generate or a maximum tolerated expected value of a number of wasted event messages delivered per event published.

14. The method of claim 1, wherein said publish-subscribe system is deployed over an internet protocol network.

15. The method of claim 1, wherein said exploiting comprises exploiting estimated or measured probabilities of different values of event content in condensing said set of G possible multicast groups into said set of g approximate multicast groups.

16. The method of claim 15, wherein said deriving further comprises exploiting a cost function measuring an expected penalty paid when an event intended for one possible multicast group is sent instead to a larger approximate multicast group.

17. The method of claim 1, wherein said deriving includes obtaining an event frequency table comprising a probability distribution of events in the publish-subscribe system, and wherein said deriving further comprises:

for each subscription, storing predicate and broker information therefor, and computing a total probability for the subscription using the event frequency table;

for each pair of nodes with predicates P1,P2, creating a new node, if one does not already exist, where the predicate is P1{circumflex over ( )}P2, the broker set is a union of the brokers of the nodes, probability is computed from the event frequency table, and wherein said deriving comprises repeating said creating until no new pair can be created;

sorting the resulting nodes into a lattice where A<

B whenever A'"'"'s predicate is implied by B'"'"'s predicate, wherein A and B comprise nodes;

propagating each broker set to nodes above it in the lattice, coalescing nodes with equal broker sets, adding their probabilities and merging their predicates; and

ascertaining an exclusive probability for each resultant node in the lattice wherein the exclusive probability is the total probability for the node less a sum of exclusive probabilities of all higher nodes in the lattice.

18. The method of claim 17, further comprising creating an approximate groups table using the resultant lattice, said creating of the approximate groups table including:

for each node in the lattice, creating a row in the approximate groups table;

determining whether a number of rows in the approximate groups table is greater than a desired number of rows; and

if so, for each pair i,j of rows in the approximate groups table, computing a penalty cost of sending an event message to the union of the pair of rows i,j, versus sending to the event one or the other of the rows individually, and choosing a row pairing i,j that minimizes network penalty, and replacing rows i,j by a new row comprising the union of rows i,j.

19. The method of claim 18, further comprising repeating said computing of the penalty cost and choosing a minimum expected penalty to condense additional pairs of rows of the approximate groups table until the number of rows in the approximate groups table is equal to a prespecified, desired number of rows in the approximate groups table.

20. At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method for distributing events to consumers in a content-based publish-subscribe system, wherein the consumers each have at least one subscription, said method comprising:

deriving, outside of event processing time, a set of g approximate multicast groups from a larger set of G possible multicast groups in the publish-subscribe system, said deriving including exploiting knowledge of subscription predicates of at least some consumers of the publish-subscribe system;

using at least one multicast group of said set of g approximate multicast groups to forward an event to at least one consumer within the publish-subscribe system; and

wherein said deriving comprises employing a cost function to combine the possible multicast groups of the set of G possible multicast groups to arrive at the set of g approximate multicast groups.

21. The at least one program storage device of claim 20, wherein said exploiting comprises using probabilities that the subscriptions in the publish-subscribe system will match an event to condense the set of G possible multicast groups into the set of g approximate multicast groups.

22. The at least one program storage device of claim 20, wherein said deriving comprises determining a probability distribution of events in the publish-subscribe system and using the probability distribution of events to determine a probability for each of at least some subscriptions in the publish-subscribe system that the subscription will match an event, and condensing the set of G possible multicast groups into the set of g approximate multicast groups using the probabilities for the at least some subscriptions.

23. The at least one program storage device of claim 22, wherein said using the probability distribution of events to determine the probability for each of at least some subscriptions in the publish-subscribe system matching an event comprises using the probability distribution of events to determine a probability for each subscription in the publish-subscribe system that the subscription will match an event, and wherein said using the subscription probabilities comprises using the subscription probabilities for all subscriptions to condense the set of G possible multicast groups into the set of g approximate multicast groups.

24. The at least one program storage device of claim 22, wherein said deriving further comprises building an initial groups lattice using the probability distribution of events and the subscription probabilities of the at least some subscriptions, wherein the initial groups lattice includes a node corresponding to each possible multicast group and each node has associated therewith a probability that that node will receive an event.

25. The at least one program storage device of claim 24, wherein said condensing of the possible multicast groups comprises creating an approximate groups table wherein each row of the approximate groups table initially corresponds to a node of the initial groups lattice, and wherein said condensing comprises combining rows of the approximate groups table until a final approximate groups table is reached, wherein each row of the final approximate groups table comprises one approximate multicast group of the set of g approximate multicast groups.

26. The at least one program storage device of claim 25, wherein said combining rows of the approximate groups table comprises combining selected pairs of rows of the approximate groups table, wherein each selected pair is chosen based on consideration of a system cost for combining said selected pair of rows of the approximate groups table, wherein said system cost incorporates the probability of each group receiving an event, and wherein said combining seeks to minimize system costs.

27. The at least one program storage device of claim 25, wherein said combining at least two rows of the approximate groups table comprises combining rows of the approximate groups table until a desired number of rows in the approximate groups table is reached, wherein said desired number of rows equals said number g of approximate multicast groups in said set of g approximate multicast groups.

28. The at least one program storage device of claim 25, wherein said creating of the approximate groups table includes initially sorting rows thereof based on probability that the corresponding node of the initial groups lattice will receive an event, said sorting being from lowest probability to highest probability, and wherein said condensing possible multicast groups comprises condensing at least two rows out of N nodes first listed in the approximate groups table.

29. The at least one program storage device of claim 25, wherein said using comprises testing content of the event to be distributed to determine a node in the initial groups lattice and a set of local consumers needing the event;

and sending the event to the approximate multicast group corresponding to a row in the approximate groups table to which the node was collapsed, and to the local consumers thereof.

30. The at least one program storage device of claim 29, further comprising for each subscriber broker in the approximate multicast group to which the node was collapsed, receiving the event and forwarding the event to consumers thereof whose subscriptions match the event.

31. The at least one program storage device of claim 20, wherein said deriving comprises ascertaining said set of g approximate multicast groups to meet a specified tolerance on one of a maximum number of multicast groups or a maximum percentage of wasted event messages during matching of the event to the consumer.

32. The at least one program storage device of claim 20, wherein said deriving comprises obtaining:

(i) a set of subscriptions expressed as conjunctions of equality tests on event attributes, and a destination address per subscription;

(ii) a frequency distribution of possible values of each event attribute; and

(iii) a tolerance specifying either a maximum number of groups to generate or a maximum tolerated expected value of a number of wasted event messages delivered per event published.

33. The at least one program storage device of claim 20, wherein said publish-subscribe system is deployed over an internet protocol network.

34. The at least one program storage device of claim 20, wherein said exploiting comprises exploiting estimated or measured probabilities of different values of event content in condensing said set of G possible multicast groups into said set of g approximate multicast groups.

35. The at least one program storage device of claim 34, wherein said deriving further comprises exploiting a cost function measuring an expected penalty paid when an event intended for one possible multicast group is sent instead to a larger approximate multicast group.

36. The at least one program storage device of claim 20, wherein said deriving includes obtaining an event frequency table comprising a probability distribution of events in the publish-subscribe system, and wherein said deriving further comprises:

for each subscription, storing predicate and broker information therefor, and computing a total probability for the subscription using the event frequency table;

for each pair of nodes with predicates P1,P2, creating a new node, if one does not already exist, where the predicate is P1{circumflex over ( )}P2, the broker set is a union of the brokers of the nodes, probability is computed from the event frequency table, and wherein said deriving comprises repeating said creating until no new pair can be created;

sorting the resulting nodes into a lattice where A<

B whenever A'"'"'s predicate is implied by B'"'"'s predicate, wherein A and B comprise nodes;

propagating each broker set to nodes above it in the lattice, coalescing nodes with equal broker sets, adding their probabilities and merging their predicates; and

ascertaining an exclusive probability for each resultant node in the lattice wherein the exclusive probability is the total probability for the node less a sum of exclusive probabilities of all higher nodes in the lattice.

37. The at least one program storage device of claim 36, further comprising creating an approximate groups table using the resultant lattice, said creating of the approximate groups table including:

for each node in the lattice, creating a row in the approximate groups table;

determining whether a number of rows in the approximate groups table is greater than a desired number of rows; and

if so, for each pair i,j of rows in the approximate groups table, computing a penalty cost of sending an event message to the union of the pair of rows i,j, versus sending to the event one or the other of the rows individually, and choosing a row pairing i,j that minimizes network penalty, and replacing rows i,j by a new row comprising the union of rows i,j.

38. The at least one program storage device of claim 37, further comprising repeating said computing of the penalty cost and choosing a minimum expected penalty to condense additional pairs of rows of the approximate groups table until the number of rows in the approximate groups table is equal to a prespecified, desired number of rows in the approximate groups table.

39. A system for distributing events to consumers in a content-based publish-subscribe system, wherein the consumers each have at least one subscription, said system comprising:

means for deriving outside of event processing time a set of g approximate multicast groups from a larger set of G possible multicast groups in the publish-subscribe system, said means for deriving including means for exploiting knowledge of subscription predicates of at least some consumers of the publish-subscribe system;

means for using at least one multicast group of said set of g approximate multicast groups to forward an event to at least one consumer within the publish-subscribe system; and

wherein said means for deriving comprises means for employing a cost function to combine the possible multicast groups of the set of G possible multicast groups to arrive at the set of g approximate multicast groups.

40. The system of claim 39, wherein said means for exploiting comprises means for using probabilities that the subscriptions in the publish-subscribe system will match an event to condense the set of G possible multicast groups into the set of g approximate multicast groups.

41. The system of claim 39, wherein said means for deriving comprises means for determining a probability distribution of events in the publish-subscribe system and for using the probability distribution of events to determine a probability for each of at least some subscriptions in the publish-subscribe system that the subscription will match an event, and means for condensing the set of G possible multicast groups into the set of g approximate multicast groups using the probabilities for the at least some subscriptions.

42. The system of claim 41, wherein said means for using the probability distribution of events to determine the probability for each of at least some subscriptions in the publish-subscribe system matching an event comprises means for using the probability distribution of events to determine a probability for each subscription in the publish-subscribe system that the subscription will match an event, and wherein said means for using the subscription probabilities comprises means for using the subscription probabilities for all subscriptions to condense the set of G possible multicast groups into the set of g approximate multicast groups.

43. The system of claim 41, wherein said means for deriving further comprises means for building an initial groups lattice using the probability distribution of events and the subscription probabilities of the at least some subscriptions, wherein the initial groups lattice includes a node corresponding to each possible multicast group and each node has associated therewith a probability that that node will receive an event.

44. The system of claim 43, wherein said means for condensing of the possible multicast groups comprises means for creating an approximate groups table wherein each row of the approximate groups table initially corresponds to a node of the initial groups lattice, and wherein said means for condensing comprises means for combining rows of the approximate groups table until a final approximate groups table is reached, wherein each row of the final approximate groups table comprises one approximate multicast group of the set of g approximate multicast groups.

45. The system of claim 44, wherein said means for combining rows of the approximate groups table comprises means for combining selected pairs of rows of the approximate groups table, wherein each selected pair is chosen based on consideration of a system cost for combining said selected pair of rows of the approximate groups table, wherein said system cost incorporates the probability of each group receiving an event, and wherein said combining seeks to minimize system costs.

46. The system of claim 44, wherein said means for combining at least two rows of the approximate groups table comprises means for combining rows of the approximate groups table until a desired number of rows in the approximate groups table is reached, wherein said desired number of rows equals said number g of approximate multicast groups in said set of g approximate multicast groups.

47. The system of claim 44, wherein said means for creating of the approximate groups table includes means for initially sorting rows thereof based on probability that the corresponding node of the initial groups lattice will receive an event, said sorting being from lowest probability to highest probability, and wherein said means for condensing possible multicast groups comprises means for condensing at least two rows out of N nodes first listed in the approximate groups table.

48. The system of claim 44, wherein said means for using comprises means for testing content of the event to be distributed to determine a node in the initial groups lattice and a set of local consumers needing the event;

and means for sending the event to the approximate multicast group corresponding to a row in the approximate groups table to which the node was collapsed, and to the local consumers thereof.

49. The system of claim 44, further comprising for each subscriber broker in the approximate multicast group to which the node was collapsed, means for receiving the event and for forwarding the event to consumers thereof whose subscriptions match the event.

50. The system of claim 39, wherein said means for deriving comprises means for ascertaining said set of g approximate multicast groups to meet a specified tolerance on one of a maximum number of multicast groups or a maximum percentage of wasted event messages during matching of the event to the consumer.

51. The system of claim 39, wherein said means for deriving comprises means for obtaining:

(i) a set of subscriptions expressed as conjunctions of equality tests on event attributes, and a destination address per subscription;

(ii) a frequency distribution of possible values of each event attribute; and

(iii) a tolerance specifying either a maximum number of groups to generate or a maximum tolerated expected value of a number of wasted event messages delivered per event published.

52. The system of claim 39, wherein said publish-subscribe system is deployed over an internet protocol network.

53. The system of claim 39, wherein said means for exploiting comprises means for exploiting estimated or measured probabilities of different values of event content in condensing said set of G possible multicast groups into said set of g approximate multicast groups.

54. The system of claim 53, wherein said means for deriving further comprises means for exploiting a cost function measuring an expected penalty paid when an event intended for one possible multicast group is sent instead to a larger approximate multicast group.

55. The system of claim 39, wherein said means for deriving includes means for obtaining an event frequency table comprising a probability distribution of events in the publish-subscribe system, and wherein said means for deriving further comprises:

for each subscription, means for storing predicate and broker information therefor, and for computing a total probability for the subscription using the event frequency table;

for each pair of nodes with predicates P1,P2, means for creating a new node, if one does not already exist, where the predicate is P1{circumflex over ( )}P2, the broker set is a union of the brokers of the nodes, probability is computed from the event frequency table, and wherein said means for deriving comprises means for repeating said creating until no new pair can be created;

means for sorting the resulting nodes into a lattice where A<

B whenever A'"'"'s predicate is implied by B'"'"'s predicate, wherein A and B comprise nodes;

means for propagating each broker set to nodes above it in the lattice, means for coalescing nodes with equal broker sets, means for adding their probabilities and means for merging their predicates; and

means for ascertaining an exclusive probability for each resultant node in the lattice wherein the exclusive probability is the total probability for the node less a sum of exclusive probabilities of all higher nodes in the lattice.

56. The system of claim 55, further comprising means for creating an approximate groups table using the resultant lattice, said means for creating of the approximate groups table including:

for each node in the lattice, means for creating a row in the approximate groups table;

means for determining whether a number of rows in the approximate groups table is greater than a desired number of rows; and

if so, for each pair i,j of rows in the approximate groups table, means for computing a penalty cost of sending an event message to the union of the pair of rows i,j, versus sending to the event one or the other of the rows individually, and means for choosing a row pairing i,j that minimizes network penalty, and means for replacing rows i,j by a new row comprising the union of rows i,j.

57. The system of claim 56, further comprising means for repeating said means for computing of the penalty cost and choosing a minimum expected penalty to condense additional pairs of rows of the approximate groups table until the number of rows in the approximate groups table is equal to a prespecified, desired number of rows in the approximate groups table.