Rendezvousing resource requests with corresponding resources

• US 8,014,321 B2
• Filed: 09/07/2005
• Issued: 09/06/2011
• Est. Priority Date: 10/22/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hasha, Richard L., Kakivaya, Gopala Krishna R., Rodeheffer, Thomas Lee
• Primary Examiner(s): Sam; Phirin
• Application Number:
  US11/220,756
• Publication Number:
  US 20060087990A1
• Time in Patent Office: 2,190 Days
• Field of Search: None
• US Class Current: 370/258
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

The present invention extends to methods, systems, and computer program products for rendezvousing resource requests with corresponding resources. Doubly linked sorted lists are traversed using modulo arithmetic in both directions. Sorted lists can be partitioned based on a multiple proximity metrics. Node routing tables provide a logarithmic index to nodes within the ID space of the federation infrastructure to facilitate more efficient routing. Messages can be routed to nodes within a ring and proximally routed to nodes in other partitioned rings.

Claims

1. In a federation infrastructure, a method for routing a message towards a destination node, the method comprising:

an act of a receiving node receiving a message along with a destination identifier indicating a destination and a partially ordered list of proximity criterion, the receiving node being included in a root ring of nodes configured for bi-directional routing as well as a plurality of sub-rings of nodes defined by the proximity criterion, the partially ordered list of proximity criterion defining a plurality of classes of nodes in a hierarchy of node classes, the receiving node being part of a plurality of classes of nodes in the hierarchy of node classes corresponding to the plurality of sub-rings, including a current class of nodes selected from among the one or more classes of nodes in the hierarchy of node classes corresponding to a current sub-ring;

an act of determining a next appropriate node that is to receive the message based on the position of the receiving node in the plurality of sub-rings of nodes and the partially ordered list of proximity criterion, the next appropriate node being numerically closer to the destination than other routing nodes in a routing table at the receiving node while still being within the current class of nodes defined by the partially ordered list or proximity criterion, the routing table representing separate routing information for the root ring of nodes and for each of the plurality of sub-rings of nodes, including at least a logarithmic index of other nodes in each ring of nodes, the routing table being populated at least based on the number base utilized to generate the identifier space for generating identifiers in the federation infrastructure, the receiving node having a symmetric relationship with nodes in the receiving node'"'"'s routing table;

an act of sending the message to the next appropriate node; and

an act of sending a previously received status message back to the node that sent the received message to the receiving node, the status message related to the received message.

2. The method as recited in claim 1, wherein the act of determining the next appropriate node that is to receive the message comprises an act of identifying an intermediate node that is numerically closer to the destination than other routing nodes in the receiving node'"'"'s routing table.

3. The method as recited in claim 2, wherein the act of identifying an intermediate node comprises an act of identifying the intermediate node as a node included in the receiving node'"'"'s routing table.

4. The method as recited in claim 1, further comprising an act of the receiving node receiving the status message from another node.

5. The method as recited in claim 4, wherein the status message includes node presence information identifying a different next appropriate node by the receiving node.

6. The method as recited in claim 5, further comprising:

an act of determining from the received status message that the received message should not be sent any further by the receiving node.

7. The method as recited in claim 6, wherein the act of determining from the received status message that the message should not be sent any further comprises an act of determining from the received status message that the message was delivered to at least one destination node.

8. The method as recited in claim 6, wherein the act of determining from the received status message that the message should not be sent any further comprises an act of determining from the message was not delivered to any destination nodes.

9. The method as recited in claim 1, wherein the act of determining the next appropriate node that is to receive the message comprises an act of identifying the receiving node as the next appropriate node.

10. The method as recited in claim 9, wherein the act of identifying the receiving node as the next appropriate node comprises an act of determining that the identifier of the receiving node matches the destination identifier more closely.

11. The method as recited in claim 10, wherein the act of determining that the identifier of the receiving node matches the destination identifier more closely comprises an act of determining that the identifier of the receiving node matches the destination identifier exactly.

12. The method as recited in claim 10, further comprising:

an act of forwarding the received message to an immediate neighboring node of the receiving node, the immediate neighborhood node in the receiving node'"'"'s current sub-ring.

13. The method as recited in claim 12, wherein the act of forwarding the received message to an immediate neighboring node of the receiving node comprises an act of determining that the destination identifier falls between the receiving node and the receiving node'"'"'s immediate predecessor neighbor node.

14. The method as recited in claim 12, wherein the act of forwarding the received message to an immediate neighboring node of the receiving node comprises an act of determining that the destination identifier falls between the receiving node and the receiving node'"'"'s immediate successor neighbor node.

15. The method as recited in claim 12, further comprising:

an act of the immediate neighboring node of the receiving node sending a status message related to the forwarded message back to the receiving node.

16. The method as recited in claim 15, further comprising:

an act of the immediate neighborhood node of the receiving node including node presence information in the status message.

17. The method as recited in claim 15, wherein the act of the immediate neighboring node of the receiving node sending a status message related to the forwarded message back to the receiving node further comprises sending a status message that includes at least an indication that the receiving node is considered the best next appropriate node for the message by the immediate neighboring node of the receiving node.

18. The method as recited in claim 15, wherein the act of the immediate neighboring node of the receiving node sending a status message related to the forwarded message back to the receiving node comprises sending a status message that includes node presence information.

19. The method as recited in claim 15, wherein the act of the immediate neighboring node of the receiving node sending a status message related to the forwarded message back to the receiving node comprises sending a status message that includes an indication that the received message should not be sent any further by the receiving node.

20. The method as recited in claim 9, wherein the act of identifying the receiving node as the next appropriate node comprises an act of the received message causing identification of the receiving node as the next appropriate node.

21. The method as recited in claim 1, wherein the act of sending the message to the next appropriate node includes an act of the receiving node including additional node presence information in the message being sent to the next appropriate node.

22. The method as recited in claim 1, wherein the act of sending the message to the next appropriate component comprises an act of the receiving node serving as the final destination of the message.

23. The method as recited in claim 22, wherein the act of the receiving node serving as the final destination of the message comprises an act of delivering the message to an application component associated with the receiving node.

33. The method as recited in claim 1, wherein each of the plurality of sub-rings correspond to different proximity criteria.

34. The method as recited in claim 1, wherein the separate routing information comprises, for the root ring and for each of the plurality of sub-rings:

a predecessor node to the receiving node, the predecessor node preceding the receiving node in a first direction within the ring;

a successor node to the receiving node, the successor node succeeding the node in the first direction within the ring;

appropriate neighborhood nodes of the receiving node, the neighborhood nodes identified in both the first direction and in a second opposite direction relative to the receiving node based on a neighborhood range and neighborhood size for the ring; and

appropriate routing nodes of the receiving node, defined by the logarithmic index of other nodes.

24. At a node in a federation infrastructure including a hierarchy of partitioned node classes, a method for routing a message towards a destination node based on proximity criteria, the method comprising:

an act of a receiving a message along with a destination identifier that was sent from another node;

an act of accessing a previously defined partially ordered list of proximity criterion, the partially ordered list of proximity criterion defining a plurality of classes of nodes in a hierarchy of node classes, the node being part of a plurality of classes of nodes in the hierarchy of node classes, including a current class of nodes selected from among the one or more classes of nodes in the hierarchy of node classes;

an act of identifying an appropriate node from a routing table at the node, the appropriate node being numerically closer to the destination than other routing nodes in the routing table while still being within the current class of nodes defined by the partially ordered list of proximity criterion, the routing table representing separate routing information for a root ring of nodes and for each of a plurality of sub-rings of nodes corresponding to the plurality of classes of nodes, including at least a logarithmic index of other nodes in each ring of nodes corresponding to the plurality of classes of nodes defined by proximity criterion that was populated based on the number base utilized to generate the ID space for the federation infrastructure;

an act of sending the message to the next appropriate node; and

an act of sending a previously received status message back to the other node, the status message related to the received message.

25. The method as recited in claim 24, wherein the act of sending the message to the next appropriate node comprises an act of sending the message to the next appropriate node to honor the previously defined partially ordered list of proximity criterion.

26. At a node in a federation infrastructure including a hierarchy of partitioned node classes, a method for routing a message to a sufficient destination node, the method comprising:

an act of a receiving a message along with a destination identifier that was sent from another node;

an act of accessing a partially ordered list of proximity criterion, the partially ordered list of proximity criterion defining a highest class of nodes within a plurality of classes of nodes in a hierarchy of node classes, the node being part of at least the highest class of nodes and a current class of nodes selected from the plurality of classes of nodes in the hierarchy of node classes, the current class of nodes selected from among the one or more classes of nodes in the hierarchy of node classes;

an act of identifying a sufficient destination node for the message from a routing table at the node representing separate routing information for a root ring of nodes and at least two sub-rings of nodes corresponding to the highest class of nodes and the current class of nodes, the sufficient destination node being a member of the highest class of nodes defined by the received partially ordered list of proximity criterion, the sufficient destination node being in the neighborhood of the destination identifier in the highest class of nodes;

an act of sending the message to the sufficient destination node; and

an act of sending a previously received status message back to the other node, the status message related to the received message.

27. The method as recited in claim 26, wherein the act of identifying a sufficient destination node comprises an act of identifying a sufficient destination node from the node'"'"'s routing table based on the partially ordered list of proximity criterion.

28. The method as recited in claim 26, wherein the act of identifying a sufficient destination node comprises an act of application logic of an application component associated with the node identifying a sufficient destination node.

29. The method as recited in claim 26, further comprising

an act of qualifying that the sufficient destination node is in the neighborhood of the destination identifier in the highest class of nodes.

30. The method as recited in claim 29, wherein the act of qualifying that the sufficient destination node is in the neighborhood of the destination identifier in the highest class of nodes comprises an act of the receiving node further qualifying the sufficient destination node also being the closest numerically to the destination identifier in the highest class of nodes using the receiving node'"'"'s routing table.

31. The method as recited in claim 26, further comprising

an act of qualifying that the sufficient destination node is the node.

32. A computer program product for use at a node in a federation infrastructure including a hierarchy of partitioned node classes, the computer program product of implement a method for routing a message towards a destination node based on proximity criteria, the computer program product comprising one or more computer storage devices having stored thereon computer-executable instructions that, when executed at a processor, cause the node to perform the method, including the following:

receive a message along with a destination identifier that was sent from another node in the federation infrastructure;

access a previously defined partially ordered list of proximity criterion, the partially ordered list of proximity criterion defining a plurality of classes of nodes in a hierarchy of node classes, the node being part of a plurality of classes of nodes in the hierarchy of node classes, including a current class of nodes selected from among the plurality of classes of nodes in the hierarchy of node classes;

identify an appropriate node from a routing table at the node, the appropriate node being numerically closer to the destination than other routing nodes in the routing table while still being within the current class of nodes defined by the partially ordered list of proximity criterion, the routing table representing separate routing information for a root ring of nodes and for each of a plurality of sub-rings of nodes corresponding to the plurality of classes of nodes, including at least a logarithmic index of other nodes in each ring of nodes corresponding to the plurality of classes of nodes defined by proximity criterion that was populated based on the number base utilized to generate the ID space for the federation infrastructure;

an act of sending the message to the next appropriate node; and

an act of sending a previously received status message back to the other node, the status message related to the received message.