High speed subscribe-and-alert service using content graphs

• US 7,680,951 B1
• Filed: 09/08/2004
• Issued: 03/16/2010
• Est. Priority Date: 06/01/2004
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Kulik, Joanna L.
• Primary Examiner(s): NEURAUTER, GEORGE C
• Application Number:
  US10/935,843
• Time in Patent Office: 2,015 Days
• Field of Search: 709/238, 707/100
• US Class Current: 709/238
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application

Abstract

Described are techniques used in connection with subscribe and alert services as may be embodied in a subscription system. The subscription system uses a preprocessor for preprocessing subscription and notification messages prior to submission to the subscription/publication server. The preprocessor outputs a preprocessed message including one or more identifiers categorizing an input subscription or notification message. The preprocessor uses a content graph to produce the preprocessed message. The subscription system uses a content based routing system with a tree-like topology to process preprocessed subscriptions and notifications using content graphs maintained at each node in the system. Also described is a loss detection technique using sequence numbers.

Claims

1. A method for processing messages in a subscription system comprising:

preprocessing a message using a content graph to produce a preprocessed message including an identifier in accordance with said message; and

submitting said preprocessed message to a server for processing wherein said server performs at least one action in accordance with said identifier included in said preprocessed message, wherein said message is a subscription message and said preprocessed message includes an identifier matching said subscription message, and

wherein said server includes a plurality of routers in a hierarchical arrangement, and the method further comprises;

receiving said preprocessed message at a router of the plurality of routers;

storing, at said router, information in a content graph of said router, the information including information about a subscription in accordance with said preprocessed message; and

forwarding said preprocessed message to one or more upstream routers of the plurality of routers at a higher level in said hierarchical arrangement than said router in accordance with a forwarding table of said router.

2. The method of claim 1, further comprising:

adding a node to said content graph of said router if there are no nodes in said content graph corresponding to said subscription.

3. The method of claim 2, wherein said router communicates with another upstream router to obtain graph information about where to add said node to said content graph.

4. The method of claim 2, wherein said router communicates with said preprocessor to obtain graph information about where to add said node to said content graph.

5. The method of claim 1, wherein each router in said hierarchical arrangement includes a content graph of said each router including information about preprocessed subscription messages received from a subscriber and other routers connected to said each router in said hierarchical arrangement.

6. The method of claim 1, wherein a preprocessor adds a node to a preprocessor content graph of said preprocessor each time a received message does not have a corresponding node in said preprocessor content graph.

7. The method of claim 1, wherein information about said node is obtained from preconstructed tables including graph information about a categorical hierarchy.

8. The method of claim 1, wherein said message is a notification message and said preprocessed message includes at least one identifier matching said notification message.

9. The method of claim 8, wherein said preprocessed message includes a set of one or more nodes in said content graph representing lowest nodes in said content graph that cover said notification message, said content graph being a hierarchy of nodes representing relationships between different sets of elements, wherein each node in said set matches said notification message and no node in said set is an ancestor of any other node in said set.

10. The method of claim 8, wherein said preprocessed message includes a set of one or more nodes in said content graph representing all nodes in said content graph that cover said notification message, said content graph being a hierarchy of nodes representing relationships between different sets of elements.

11. The method of claim 9, wherein said server includes a plurality of routers in a hierarchical arrangement, and the method further comprising:

receiving at a first router that is a root of said hierarchical arrangement said preprocessed message; and

forwarding said preprocessed message to any downstream neighbors of said first router at a lower level in said hierarchical arrangement than said root in accordance with a content graph of said first router.

12. The method of claim 11, wherein said neighbors of said first router include other routers and subscribers, said other routers being connected to said first router in accordance with a subscription list of said content graph of said first router.

13. The method of claim 11, further comprising:

modifying a header of a notification message forwarded in said forwarding in which said identifier is replaced with another identifier determined in accordance with a neighbor receiving said notification message.

14. The method of claim 13, wherein said other identifier is predetermined prior to receiving said preprocessed message by said root.

15. The method of claim 11, wherein said preprocessed message includes a sequence number uniquely corresponding to the notification message, said notification message being associated with a node in a categorical hierarchy wherein said node in said categorical hierarchy has a sequence number determined in accordance with a number of notification messages received by said server covering said node, each node in said categorical hierarchy having its own sequence number.

16. The method of claim 15, further comprising:

receiving by said first router a request from a subscriber for a table of current sequence numbers for a requested node and descendants of said requested node in said content graph of said first router; and

sending to said subscriber said table, wherein said subscriber uses said table to determine a missed notification message in accordance with consecutive sequence numbers for each node described by said table.

17. The method of claim 16, wherein, in response to receiving a notification message, said first router increments a sequence number of each of one or more nodes in said content graph corresponding to said notification message.

18. A computer program product stored in a memory for processing messages in a subscription system comprising code that:

preprocesses a message using a content graph to produce a preprocessed message including an identifier in accordance with said message; and

submits said preprocessed message to a server for processing wherein said server performs at least one action in accordance with said identifier included in said preprocessed message, wherein said message is a subscription message and said preprocessed message includes an identifier matching said subscription message, and

wherein said server includes a plurality of routers in a hierarchical arrangement, and the computer program product further comprising code that;

receives said preprocessed message at a router of the plurality of routers;

stores, at said router, information in a content graph of said router, the information including information about a subscription in accordance with said preprocessed message; and

forwards said preprocessed message to one or more upstream routers of the plurality of routers at a higher level in said hierarchical arrangement than said router in accordance with a forwarding table of said router.

19. The computer program product of claim 18, further comprising code that:

adds a node to said content graph of said router if there are no nodes in said content graph corresponding to said subscription.

20. The computer program product of claim 19, wherein said router communicates with another upstream router to obtain graph information about where to add said node to said content graph.

21. The computer program product of claim 19, wherein said router communicates with said preprocessor to obtain graph information about where to add said node to said content graph.

22. The computer program product of claim 18, wherein each router in said hierarchical arrangement includes a content graph of said each router including information about preprocessed subscription messages received from a subscriber and other routers connected to said each router in said hierarchical arrangement.

23. The computer program product of claim 18, wherein a preprocessor adds a node to a preprocessor content graph of said preprocessor each time a received message does not have a corresponding node in said preprocessor content graph.

24. The computer program product of claim 18, wherein information about said node is obtained from preconstructed tables including graph information about a categorical hierarchy.

25. The computer program product of claim 18, wherein said message is a notification message and said preprocessed message includes at least one identifier matching said notification message.

26. The computer program product of claim 25, wherein said preprocessed message includes a set of one or more nodes in said content graph representing lowest nodes in said content graph that cover said notification message, said content graph being a hierarchy of nodes representing relationships between different sets of elements, wherein each node in said set matches said notification message and no node in said set is an ancestor of any other node in said set.

27. The computer program product of claim 25, wherein said preprocessed message includes a set of one or more nodes in said content graph representing all nodes in said content graph that cover said notification message, said content graph being a hierarchy of nodes representing relationships between different sets of elements.

28. The computer program product of claim 26, wherein said server includes a plurality of routers in a hierarchical arrangement, and the computer program product further comprising code that:

receives at a first router that is a root of said hierarchical arrangement said preprocessed message; and

forwards said preprocessed message to any downstream neighbors of said first router at a lower level in said hierarchical arrangement than said root in accordance with a content graph of said first router.

29. The computer program product of claim 28, wherein said neighbors of said first router include other routers and subscribers, said other routers being connected to said first router in accordance with a subscription list of said content graph of said first router.

30. The computer program product of claim 28, further comprising code that:

modifies a header of a notification message forwarded in said forwarding in which said identifier is replaced with another identifier determined in accordance with a neighbor receiving said notification message.

31. The computer program product of claim 30, wherein said other identifier is predetermined prior to said preprocessed message being received by said root.

32. The computer program product of claim 28, wherein said preprocessed message includes a sequence number uniquely corresponding to the notification message, said notification message being associated with a node in a categorical hierarchy wherein said node in said categorical hierarchy has a sequence number determined in accordance with a number of notification messages received by said server covering said node, each node in said categorical hierarchy having its own sequence number.

33. The computer program product of claim 32, further comprising code that:

receives by said first router a request from a subscriber for a table of current sequence numbers for a requested node and descendants of said requested node in said content graph of said first router; and

sends to said subscriber said table, wherein said subscriber uses said table to determine a missed notification message in accordance with consecutive sequence numbers for each node described by said table.

34. The computer program product of claim 33, wherein, in response to receiving a notification message, said first router increments a sequence number of each of one or more nodes in said content graph corresponding to said notification message.