Routing messages within a network using the data content of the message

• US 6,091,724 A
• Filed: 11/20/1997
• Issued: 07/18/2000
• Est. Priority Date: 11/20/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Strom, Robert Evan, Sturman, Daniel Charles, Chandra, Tushar Deepak
• Primary Examiner(s): FELBER, JOSEPH LEON
• Application Number:
  US08/975,303
• Time in Patent Office: 971 Days
• Field of Search: 370/400, 370/401, 370/389, 370/351, 370/390, 370/256
• US Class Current: 370/390
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast

Abstract

A router within a network uses the data of a message received at the router to determine on which links out of the router the message needs to be forwarded. The router does not need any destination information from the message, and thus, the message need not include any destination information. Instead, the router uses an annotated search data structure to determine which links correspond to consumers interested in receiving the message. The message is sent only over those links.

Claims

1. A method of determining zero or more links to be used in routing a message, said method comprising:

receiving a message; and

determining zero or more links over which said message is to be sent, said determining comprising searching a data structure using at least a portion of a data content of said message to determine said zero or more links, wherein said data structure comprises a plurality of tests performable on said at least a portion of said data content, and said searching comprises following one or more paths of said data structure, but less than all paths of said data structure, based upon results of one or more tests of said plurality of tests performed to determine said zero or more links to be used in routing said message.

2. The method of claim 1, wherein said searching comprises traversing said data structure until a mask provides an indication of said zero or more links.

3. The method of claim 2, wherein said mask comprises a plurality of values the positions of which correspond to a plurality of links, and wherein said indication indicates:

zero links when said plurality of values includes a plurality of first predefined values; and

one or more links when one or more of said plurality of values includes a second predefined value.

4. The method of claim 3, wherein said plurality of first predefined values includes a plurality of no indications and wherein said second predefined value includes a yes indication.

5. The method of claim 2, wherein said traversing comprises:

comparing said mask to a vector associated with a node of said data structure;

refining said mask when said comparing indicates refinement;

proceeding to another node of said data structure, when said mask is to be further refined; and

repeating said comparing, refining and proceeding until said mask needs no further refinement.

6. The method of claim 5, wherein said proceeding comprises using said data content to determine the another node.

7. The method of claim 5, wherein said mask comprises a plurality of values the positions of which correspond to a plurality of links of a router that received said message, and wherein said refining comprises updating at least one of said plurality of values in said mask based on at least one value of at least one corresponding position in said vector.

8. The method of claim 7, wherein said updating comprises changing at least one value of the mask from a maybe indication to a yes indication or a no indication, depending on the value in the corresponding position of the vector.

9. The method of claim 5, further comprising annotating a plurality of nodes of said data structure with a plurality of vectors, each of said plurality of vectors indicating at its corresponding node whether any links may be used to reach one or more clients interested in said message.

10. The method of claim 1, wherein said data structure comprises a plurality of subscriptions received from a plurality of clients.

11. The method of claim 1, wherein said receiving and said determining are by a router of a network.

12. A method of routing messages within a network, said method comprising:

receiving a message; and

routing said message to a subset of clients of said network, said subset comprising less than all of said clients of said network, wherein said routing is irrespective of any destination information that may be within said message, and wherein said routing comprises searching a data structure using at least a portion of a data content of said message to determine said subset of clients, wherein said data structure comprises a plurality of tests performable on said at least a portion of said data content, and said searching comprises following one or more paths of said data structure, but less than all paths of said data structure, based upon results of one or more tests of said plurality of tests performed to determine said subset of clients to be routed said message.

13. 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 of determining zero or more links to be used in routing a message, said method comprising:

receiving a message; and

determining zero or more links over which said message is to be sent, said determining comprising searching a data structure using at least a portion of a data content of said message to determine said zero or more links, wherein said data structure comprises a plurality of tests performable on said at least a portion of said data content, and said searching comprises following one or more paths of said data structure, but less than all paths of said data structure, based upon results of one or more tests of said plurality of tests performed to determine said zero or more links to be used in routing said message.

14. The at least one program storage device of claim 13, wherein said searching comprises traversing said data structure until a mask provides an indication of said zero or more links.

15. The at least one program storage device of claim 14, wherein said mask comprises a plurality of values the positions of which correspond to a plurality of links, and wherein said indication indicates:

zero links when said plurality of values includes a plurality of first predefined values; and

one or more links when one or more of said plurality of values includes a second predefined value.

16. The at least one program storage device of claim 15, wherein said plurality of first predefined values includes a plurality of no indications and wherein said second predefined value includes a yes indication.

17. The at least one program storage device of claim 14, wherein said traversing comprises:

comparing said mask to a vector associated with a node of said data structure;

refining said mask when said comparing indicates refinement;

proceeding to another node of said data structure, when said mask is to be further refined; and

repeating said comparing, refining and proceeding until said mask needs no further refinement.

18. The at least one program storage device of claim 17, wherein said proceeding comprises using said data content to determine the another node.

19. The at least one program storage device of claim 17, wherein said mask comprises a plurality of values the positions of which correspond to a plurality of links of a router that received said message, and wherein said refining comprises updating at least one of said plurality of values in said mask based on at least one value of at least one corresponding position in said vector.

20. The at least one program storage device of claim 19, wherein said updating comprises changing at least one value of the mask from a maybe indication to a yes indication or a no indication, depending on the value in the corresponding position of the vector.

21. The at least one program storage device of claim 17, wherein said method further comprises annotating a plurality of nodes of said data structure with a plurality of vectors, each of said plurality of vectors indicating at its corresponding node whether any links may be used to reach one or more clients interested in said message.

22. The at least one program storage device of claim 13, wherein said data structure comprises a plurality of subscriptions received from a plurality of clients.

23. 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 of routing messages within a network, said method comprising:

receiving a message; and

routing said message to a subset of clients of said network, said subset comprising less than all of said clients of said network, wherein said routing is irrespective of any destination information that may be within said message, and wherein said routing comprises searching a data structure using at least a portion of a data content of said message to determine said subset of clients, wherein said data structure comprises a plurality of tests performable on said at least a portion of said data content, and said searching comprises following one or more paths of said data structure, but less than all paths of said data structure, based upon results of one or more tests of said plurality of tests performed to determine said subset of clients to be routed said message.

24. An article of manufacture, comprising:

at least one computer usable medium having computer readable program code means embodied therein for causing the determining of zero or more links to be used in routing a message, the computer readable program code means in said article of manufacture comprising;

computer readable program code means for causing a computer to receive a message; and

computer readable program code means for causing a computer to determine zero or more links over which said message is to be sent, said computer readable program code means for causing a computer to determine comprising computer readable program code means for causing a computer to search a data structure using at least a portion of a data content of said message to determine said zero or more links, wherein said data structure comprises a plurality of tests performable on said at least a portion of said data content, and said computer readable program code means for causing a computer to search comprises computer readable program code means for causing a computer to follow one or more oaths of said data structure, but less than all paths of said data structure, based upon results of one or more tests of said plurality of tests performed to determine said zero or more links to be used in routing said message.

25. The article of manufacture of claim 24, wherein said computer readable program code means for causing a computer to search comprises computer readable program code means for causing a computer to traverse said data structure until a mask provides an indication of said zero or more links.

26. The article of manufacture of claim 25, wherein said computer readable program code means for causing a computer to traverse comprises:

computer readable program code means for causing a computer to compare said mask to a vector associated with a node of said data structure;

computer readable program code means for causing a computer to refine said mask when said comparing indicates refinement;

computer readable program code means for causing a computer to proceed to another node of said data structure, when said mask is to be further refined; and

computer readable program code means for causing a computer to repeat comparing, refining and proceeding until said mask needs no further refinement.

27. The article of manufacture of claim 26, wherein said mask comprises a plurality of values the positions of which correspond to a plurality of links of a router that received said message, and wherein said computer readable program code means for causing a computer to refine comprises computer readable program code means for causing a computer to update at least one of said plurality of values in said mask based on at least one value of at least one corresponding position in said vector.

28. An article of manufacture, comprising:

at least one computer usable medium having computer readable program code means embodied therein for causing the routing of messages within a network, the computer readable program code means in said article of manufacture comprising;

computer readable program code means for causing a computer to receive a message; and

computer readable program code means for causing a computer to route said message to a subset of clients of said network, said subset comprising less than all of said clients of said network, wherein routing is irrespective of any destination information that may be within said message, and wherein said computer readable program code means for causing a computer to route comprises computer readable program code means for causing a computer to search a data structure using at least a portion of a data content of said message to determine said subset of clients, wherein said data structure comprises a plurality of tests performable on said at least a portion of said data content, and said computer readable program code means for causing a computer to search comprises computer readable program code means for causing a computer to follow one or more paths of said data structure, but less than all paths of said data structure, based upon results of one or more tests of said plurality of tests performed to determine said subset of clients to be routed said message.

29. A system of determining zero or more links to be used in routing a message, said system comprising:

a router being adapted to receive a message; and

said router being further adapted to determine zero or more links over which said message is to be sent, the determining comprising searching a data structure using at least a portion of a data content of said message to determine said zero or more links, wherein said data structure comprises a plurality of tests performable on said at least a portion of said data content, and said searching comprises following one or more paths of said data structure, but less than all paths of said data structure, based upon results of one or more tests of said plurality of tests performed to determine said zero or more links to be used in routing said message.

30. The system of claim 29, wherein said router is further adapted to traverse said data structure until a mask provides an indication of said zero or more links.

31. The system of claim 30, wherein said router is further adapted to:

compare said mask to a vector associated with a node of said data structure;

refine said mask when the comparing indicates refinement;

proceed to another node of said data structure, when said mask is to be further refined; and

repeat the comparing, refining and proceeding until said mask needs no further refinement.

32. A system of routing messages within a network, said system comprising:

means for receiving a message; and

means for routing said message to a subset of clients of said network, said subset comprising less than all of said clients of said network, wherein said routing is irrespective of any destination information that may be within said message, and wherein said means for routing comprising means for searching a data structure using at least a portion of a data content of said message to determine said zero or more links, wherein said data structure comprises a plurality of tests performable on said at least a portion of said data content, and said searching comprises following one or more paths of said data structure, but less than all paths of said data structure, based upon results of one or more tests of said plurality of tests performed to determine said subset of clients to be routed said message.