Rendezvousing resource requests with corresponding resources

• US 20060087990A1
• Filed: 09/07/2005
• Published: 04/27/2006
• Est. Priority Date: 10/22/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hasha, Richard L., Kakivaya, Gopala Krishna R., Rodeheffer, Thomas Lee
• Granted Patent: US 8,014,321 B2
• Time in Patent Office: Days
• US Class Current: 370/299
• 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, the receiving node being included in a ring of nodes configured for bi-directional routing;

an act of determining the next appropriate node that is to receive the message based on the position of the receiving node in the ring of nodes, the next appropriate node being numerically closer to the destination than other routing nodes in the receiving node'"'"'s routing table, the routing table representing at least a logarithmic index of other nodes in the 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; and

an act of sending the message to the next appropriate component.

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, wherein the act of determining the next appropriate node that is to receive the message comprises an act of receiving a status message from a node to which the receiving node previously sent a message.

5. The method as recited in claim 4, wherein the act of receiving a status message comprises receiving a status message that contains node presence information.

6. The method as recited in claim 4 wherein the act of receiving a status message comprises receiving a status message that causes identification of a different next appropriate component by the receiving node.

7. The method as recited in claim 4, 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.

8. The method as recited in claim 7, 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.

9. The method as recited in claim 7, 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.

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

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

11. The method as recited in claim 10, wherein the act of sending a status message related to the received message comprises an act of sending a previously received status message back to the node that sent the received message to the receiving node.

12. 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.

13. The method as recited in claim 12, 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.

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

15. The method as recited in claim 13, 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 ring.

16. The method as recited in claim 15, 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.

17. The method as recited in claim 15, 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.

18. The method as recited in claim 15, 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.

19. The method as recited in claim 18, further comprising:

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

20. The method as recited in claim 18, 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 comprising 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.

21. The method as recited in claim 18, 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 comprising sending a status message that includes node presence information

22. The method as recited in claim 18, 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.

23. The method as recited in claim 12, 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.

24. The method as recited in claim 1, wherein the act of sending the message to the next appropriate component comprises the act of sending the message to the next appropriate node.

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

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

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

28. The method as recited in claim 26, further comprising:

an act of sending a status message associated with the received message back to the node that sent the received message to the receiving node.

29. 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 node receiving a message along with a destination identifier and a proximity criterion, the proximity criterion defining one or more classes of nodes in a hierarchy of node classes, the receiving node being part of a current class 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 an appropriate node from the receiving node'"'"'s routing table, the appropriate node being numerically closer to the destination than other routing nodes in the routing table while still being within the one or more classes of nodes defined by proximity criterion, the routing table representing at least a logarithmic index of other nodes in the one or more 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; and

an act of sending the message to the next appropriate node.

30. The method as cited in claim 29, wherein the act of a receiving node receiving a message along with a destination identifier and a proximity criterion comprises an act of the receiving node accessing a previously defined partially ordered list of proximity criterion

31. The method as cited in claim 30, wherein the act of the receiving node accessing a previously defined partially ordered list of proximity criterion comprises an act of receiving a previously defined partially ordered list of proximity criterion.

32. The method as recited in claim 29, 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 a previously defined partially ordered list of proximity criterion.

33. 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 node receiving a message along with a destination identifier and a proximity criterion, the proximity criterion defining a highest class of nodes within one or more classes of nodes in a hierarchy of node classes, the receiving node being part of at least a current class 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, the sufficient destination node being a member of the highest class of nodes defined by the received proximity criterion, the sufficient destination node being in the neighborhood of the destination identifier in the highest class of nodes; and

an act of sending the message to the sufficient destination node.

34. The method as recited in claim 33, wherein the act of identifying a sufficient destination node comprises an act of identifying a sufficient destination node from at least the receiving node'"'"'s routing table based on the proximity criterion.

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

36. The method as recited in claim 33, 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.

37. The method as recited in claim 36, 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.

38. The method as recited in claim 33, further comprising

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

39. A system including a plurality of hierarchically partitioned classes of nodes, the system comprising:

an upper ring of nodes, each node in the upper ring of nodes having a node identifier indicating a position in a sorted linked list nodes;

a first lower ring of nodes, each node in the first lower ring of nodes having a node identifier in a first sublist of nodes, the first sublist of nodes partitioned from the sorted linked list such that nodes in the first lower ring are also nodes in the upper ring, the first sublist being partitioned from the sorted linked list in accordance with a proximity criterion indicating how rings of nodes are to be classified, the first ring of nodes configured to allow routed message traffic to bypass at least some nodes included in the linked list when routed within the first ring of nodes; and

a second lower ring of nodes, each node in the second lower ring of nodes having a node identifier in a second different sublist of nodes, the second sublist of nodes partitioned from the sorted linked list such that nodes in the second lower ring are also nodes in the upper ring, the second sublist being partitioned from the sorted linked list in accordance with the proximity criterion such that the first lower ring and the second lower ring are classified equivalently with respect to the upper ring'"'"'s proximity criterion, the second ring of nodes configured to allow routed message traffic to bypass at least some nodes included in the first ring of nodes when routed within the second ring of nodes.

40. The system as recited in claim 39, wherein message traffic is limited to the upper ring of nodes.

41. The system as recited in claim 39, wherein message traffic is limited to the first lower ring of nodes.

42. The system as recited in claim 39, wherein message traffic is limited to the second lower ring of nodes.

43. The system as recited in claim 39, wherein the system is configured such that a message directed to a destination node in the upper ring of nodes makes as much progress toward the destination node as possible in the first lower ring of nodes before the message'"'"'s routing continues in the upper ring of nodes.

44. The system as recited in claim 39, wherein the system is configured such that a message directed to a destination node in the upper ring of nodes makes as much progress toward the destination node as possible in the second lower ring of nodes before the message'"'"'s routing continues in the upper ring of nodes.

45. The system as recited in claim 39, wherein the system is configured such that a message directed to a destination node in the upper ring of nodes can be delivered to an application component associated with the destination node after the message is received at a node in the neighborhood of the destination node within an expressed equivalence class of nodes.

46. The system as recited in claim 39, wherein the system is configured such that routing relationships between nodes in the upper ring of nodes are symmetric.

47. The system as recited in claim 39, wherein the system is configured such that routing relationships between nodes in the upper ring of nodes are bi-directional.

48. The system as recited in claim 39, wherein each node in the first lower ring of nodes having a node identifier in a first sublist of nodes comprises each node in the first lower ring of nodes having a node identifier from upper ring of nodes.

49. The system as recited in claim 39, wherein each node in the second lower ring of nodes having a node identifier in a second sublist of nodes comprises each node in the second lower ring of nodes having a node identifier from upper ring of nodes.

50. The system as recited in claim 39, wherein one or more of the nodes in the first lower ring of nodes are also included in the second lower ring of nodes.

51. The system as recited in claim 50, wherein the one or more of the nodes in the first lower ring of nodes being included in the second lower ring of nodes comprises the one or more nodes in the first lower ring of nodes being aliased in the second lower ring of nodes.