Method and apparatus for propagating content filters for a publish-subscribe network

• US 7,551,629 B2
• Filed: 03/28/2003
• Issued: 06/23/2009
• Est. Priority Date: 03/28/2002
• Status: Expired due to Fees

• Current Assignee: Precache Incorporated
• Original Assignee: Precache Incorporated
• Inventors: Yang, Ping-Fai, Chen, Tsu-Wei, Rosenblum, David S., Fung, Alex W. P.
• Primary Examiner(s): Gauthier; Gerald
• Application Number:
  US10/400,444
• Publication Number:
  US 20040001498A1
• Time in Patent Office: 2,279 Days
• Field of Search: 370/352, 370/392, 370/401, 709/203, 709/202, 709/236, 709/201, 707/3, 707/104.1, 707/10
• US Class Current: 370/401
• CPC Class Codes: H04L 12/1859 adapted to provide push services, e.g. data channels
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 12/1895 for short real-time information, e.g. alarms, notifications, alerts, updates
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method and apparatus provide for propagating filters in a publish-subscribe network. A plurality of filters relating to subscriptions to content in the network are received. A number of the filters is reduced based upon particular criteria, and the reduced number of filters are propagated for use in satisfying the subscriptions. A filter receiving module, a filter reduction module, and a filter propagation module may execute these steps.

Claims

1. A method for propagating filters in a publish-subscribe network, comprising:

receiving, at a router, a plurality of filters from one or more nodes relating to subscriptions to content in the network, wherein a filter of the plurality of filters describes a set of events that a subscriber is interested in receiving;

the router reducing a number of the filters based upon particular criteria; and

the router propagating in the network the reduced number of filters for use in satisfying the subscriptions to content;

wherein the propagating step includes propagating the filters using one or more of a plurality of particular procedures chosen from a list consisting of;

an eager propagation scheme;

lazy propagation scheme;

response to broadcast advertisement scheme;

after network topology computation scheme;

periodic propagation scheme;

filter re-propagation during fault repair scheme; and

, filter re-propagation during network re-configuration scheme.

2. The method of claim 1 wherein the reducing step includes one or more of:

performing an approximation operation on one or more of the plurality of filters; and

performing a merging operation on one or more of the plurality of filters.

3. The method of claim 2, wherein the performing a merging operation step includes determining whether a merged filter will exceed a packet leakage threshold.

4. The method of claim 1 wherein the receiving step includes receiving the plurality of filters via a content-based routing network.

5. The method of claim 1 wherein source and destination nodes for the propagation are connected using one or more of a plurality of particular mechanisms chosen from a list consisting of:

hop-by-hop, end-to-end, using tunnels, and using transmission control protocol.

6. The method of claim 1, further including injecting the filters at one or more of a plurality of particular locations in the network.

7. The method of claim 1 wherein the propagating step includes propagating the filters based upon one or more of a plurality of particular behaviors of an intended recipient, the behaviors chosen from a list consisting of:

mobile, permanent, and temporary.

8. The method of claim 1 wherein the propagating step includes propagating the filters based upon one or more of a plurality of particular behaviors of a sender of one or more of the filters, the behaviors chosen from a list consisting of:

mobile, permanent, and temporary.

9. The method of claim 1, further including performing one or more of a plurality of particular processing steps on one or more of the filters, the processing steps chosen from a list consisting of:

attribute content translation, expression expansion, expression translation, transformation of representations, encoding/decoding, and encryption/decryption.

10. The method of claim 1, further including formatting a message containing one or more of the filters according to one or more of a plurality of particular formats.

11. The method of claim 1 wherein the propagating step includes propagating the filters according to one or more of a plurality of particular policies or procedures chosen from a list consisting of:

administering, maintenance, filter persistency, performance enhancing policies, monitoring, and accounting.

12. The method of claim 1, wherein the propagating step includes:

determining a network topology underlying a filter propagation strategy, wherein the underlying network topology includes one or more of a plurality of requirements for filter propagation that must be satisfied in order to propagate filters; and

propagating the reduced number of filters based on satisfaction of the requirement of the determined filter propagation strategy.

13. The method of claim 12, wherein the determined filter propagation strategy is one of a list consisting of:

eager propagation scheme;

lazy propagation scheme;

response to broadcast advertisement scheme;

after network topology computation scheme;

periodic propagation scheme;

filter re-propagation during fault repair scheme; and

, filter re-propagation during network re-configuration scheme.

14. The method of claim 1, wherein the receiving step receives the plurality of filters at a core router in the network.

15. The method of claim 1, wherein the receiving step receives the plurality of filters at an edge router in the network.

16. The method of claim 1, wherein the receiving step receives the plurality of filters at publisher machine in the network.

17. A router for propagating filters in a publish-subscribe network, comprising modules for executing the method of claim 1.

18. A publish-subscribe network comprising a plurality of routers that include modules for executing the method of claim 1.

19. A publish-subscribe network comprising a plurality of user machines that include modules for executing the method of claim 1.

20. An apparatus for propagating filters in a publish-subscribe network, comprising:

a filter receiving module, wherein the filter receiving module receives a plurality of filters from one or more nodes relating to subscriptions to content in the network, wherein a filter of the plurality of filters describes a set of events that a subscriber is interested in receiving;

a filter reduction module, wherein the filter reduction module reduces a number of the filters by merging one or more filters of the plurality of filters based upon particular criteria; and

a filter propagation module, wherein the filter propagation module propagates, in the publish-subscribe network, the reduced number of filters for use in satisfying the subscriptions;

wherein the filter propagation module includes instructions for propagating the filters using one or more of a plurality of particular procedures chosen from a list consisting of;

an eager propagation scheme;

lazy propagation scheme;

response to broadcast advertisement scheme;

after network topology computation scheme;

periodic propagation scheme;

filter re-propagation during fault repair scheme; and

, filter re-propagation during network re-configuration scheme.

21. The apparatus of claim 20, wherein the filter reduction module further comprises:

a filter approximation module, wherein the filter approximation module performs an approximation operation on one or more the plurality of filters; and

a filter merging module, wherein the filter merging module merges two or more of the plurality of filters.

22. The apparatus of claim 20, further comprising:

a filter processing module, wherein the filter processing module transforms one or more of the filters; and

a filter grouping module, wherein the filter grouping module groups filters based on the filters proximity to one other.

23. A method for propagating filters in a publish-subscribe network, comprising the steps of:

(a) receiving, at a router, a plurality of filters at a node in the network, wherein a filter of the plurality of filters describes a set of events that a subscriber is interested in receiving;

(b) the router processing one or more of the received filters to reduce the number of filters;

(c) the router determining whether to propagate filters based on recipient behavior rules; and

(d) the router propagating the processed filters to a next node in the network;

wherein the router propagating includes propagating the filters using one or more of a plurality of particular procedures chosen from a list consisting of;

an eager propagation scheme;

lazy propagation scheme;

response to broadcast advertisement scheme;

after network topology computation scheme;

periodic propagation scheme;

filter re-propagation during fault repair scheme; and

, filter re-propagation during network re-configuration scheme.

24. The method of claim 23, further comprising:

determining whether to propagate filters based on sender behavior rules.

25. The method of claim 23, further comprising the step of determining if there is another node after the next node in the network.

26. The method of claim 25, if it is determined that there is another node, repeating steps (b)-(d).

27. The method of claim 23, further comprising the step of determining if there are additional filters to be received at the next node in the network.

28. The method of claim 27, if it is determined that there are additional filters to be received at the next node in the network, repeating steps (a)-(d) at the new node.

29. The method of claim 23, wherein the processing step includes one or more of the steps of:

simplifying the filters to remove redundant predicate expressions;

approximating the filters;

clustering the filters;

subsuming the filters; and

,

merging two or more filters.

30. The method of claim 29, wherein the processing step further includes:

grouping filters; and

, wherein the approximating step approximates filters in the group, the clustering step locates and collects filters in the group with respect to the filters'"'"' proximity, the subsuming step subsumes filters in the group, and the merging step merges filters in the group.

31. The method of claim 30, wherein the grouping step groups filters only from downlinks relevant to a subject.

32. The method of claim 29, wherein the merging step includes determining whether a merged filter will exceed the packet leakage threshold.

33. The method of claim 23, wherein the processing step includes:

approximating the filters; and

, subsuming and merging the approximated filters.

34. The method of claim 23, wherein the node in the network includes stored filters and wherein the processing step process the received filters and the stored filters to reduce the number of filters.

35. The method of claim 34, wherein the stored filters are previously received and processed filters.

36. The method of claim 23, wherein the receiving step (a) receives the plurality of filters at a node in the core of the network.

37. A router for propagating filters in a publish-subscribe network, comprising modules for executing the method of claim 23.

38. A publish-subscribe network comprising a plurality of routers that include modules for executing the method of claim 23.

39. A publish-subscribe network comprising a plurality of user machines that include modules for executing the method of claim 23.

40. An apparatus for propagating filters in a publish-subscribe network, comprising:

a filter receiving module, wherein the filter receiving module receives a plurality of filters at a node in the network, wherein a filter of the plurality of filters describes a set of events that a subscriber is interested in receiving;

a filter processing module, wherein the filter processing module reduces the number of filters by merging one or more filters of the plurality of filters in the plurality of received filters; and

,

a filter propagation module, wherein the filter propagation module determines whether to propagate filters based on recipient behavior rules and, if determined to propagate, propagates the reduced number of filters to a next node in the network;

wherein the filter propagation module includes instructions for propagating the filters using one or more of a plurality of particular procedures chosen from a list consisting of;

an eager propagation scheme;

lazy propagation scheme;

response to broadcast advertisement scheme;

after network topology computation scheme;

periodic propagation scheme;

filter re-propagation during fault repair scheme; and

, filter re-propagation during network re-configuration scheme.

41. The apparatus of claim 40, wherein the filter processing module includes:

a simplification module, wherein the simplification module simplifies the filters to remove redundant predicate expressions.

42. The apparatus of claim 40, wherein the filter processing module includes:

a grouping module, wherein the grouping module groups filters according to a selection of downlinks.

43. The apparatus of claim 40, wherein the filter processing module includes:

an approximation module, wherein the approximation module approximates the filters.

44. The apparatus of claim 40, wherein the filter processing module includes:

a subsumption module, wherein the subsumption module subsumes filters.

45. The apparatus of claim 40, wherein the filter processing module includes:

a clustering module, wherein the clustering module clusters filters according to their proximity to each other.

46. The apparatus of claim 40, wherein the filter processing module includes:

a merging module, wherein the merging module merges filters.

47. A method of filter propagation in a publish-subscribe network, comprising the steps of:

a router sending notification requesting filters;

one or more downstream routers receiving the notification;

one or more of the downstream routers propagating the filter requests further downstream;

the router requesting filters waiting for a response from the downstream routers to which the filter request is propagated;

one or more of the downstream routers collecting filters from the further downstream routers to which the filter request is propagated;

one or more of the downstream routers processing the propagated filters to reduce the number of filters; and

,

one or more of downstream routers sending the reduced number of filters upstream to the router requesting filters;

wherein the one or more of downstream routers propagation includes propagating the filters using one or more of a plurality of particular procedures chosen from a list consisting of;

an eager propagation scheme;

lazy propagation scheme;

response to broadcast advertisement scheme;

after network topology computation scheme;

periodic propagation scheme;

filter re-propagation during fault repair scheme; and

, filter re-propagation during network re-configuration scheme.

48. The method of claim 47, further comprising:

each downstream router updating a bookkeeping database to reflect that a filter request is received from the router; and

determining if the router from which the filter request is received has been serviced.

49. A publish-subscribe network comprising a plurality of routers and publisher machines that include modules for executing the method of claim 47.