RENDEZVOUSING RESOURCE REQUESTS WITH CORRESPONDING RESOURCES

• US 20100046399A1
• Filed: 11/03/2009
• Published: 02/25/2010
• Est. Priority Date: 10/22/2004
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hasha, Richard L., Kakivaya, Gopala Krishna R., Rodeheffer, Thomas Lee
• Application Number:
  US12/611,825
• Publication Number:
  US 20100046399A1
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 61/4541 Directories for service discovery
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1048 Departure or maintenance mechanisms

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 creating and maintaining a node distribution data structure, the method comprising:

an act of accessing from a current node at least one routing table in the federation infrastructure to determine identification information for each node in the federation infrastructure of which the routing table has knowledge, wherein one or more of the nodes in the routing table references at least one other node in the federation infrastructure;

an act of subsequently accessing the other nodes in the federation infrastructure by following the nodes pointed to by each node; and

based on the accessed nodes, an act of forming a node distribution data structure that points to every node in the federation infrastructure.

2. The method as recited in claim 1, wherein the nodes and routing tables are members of the same proximal ring.

3. The method as recited in claim 2, wherein at least the node identification information and any node references maintained in the routing table are used to address a message to at least one other node in the federation infrastructure.

4. The method as recited in claim 2, wherein at least the node identification information and any node references maintained in the routing table are used to determine at least one node from a set of nodes to address a message to.

5. The method as recited in claim 3, further comprising sending a plurality of messages instead of a single message.

6. The method as recited in claim 1, wherein the nodes and routing tables are members of different proximal rings.

7. The method as recited in claim 6, wherein at least the node identification information and any node references maintained in the routing table are used to address a message to at least one other node in the federation infrastructure.

8. The method as recited in claim 6, wherein at least the node identification information and any node references maintained in the routing table are used to determine at least one node from a set of nodes to address a message to.

9. The method as recited in claim 1, wherein the node distribution data structure comprises a connectivity graph.

10. In a federation infrastructure, a system configured to create and maintain a node distribution data structure, the system comprising:

an accessing module configured to access from a current node at least one routing table in the federation infrastructure to determine identification information for each node in the federation infrastructure of which the routing table has knowledge, wherein one or more of the nodes in the routing table points to at least one other node in the federation infrastructure;

a second accessing module configured to subsequently access the other nodes in the federation infrastructure by following the nodes pointed to by each node; and

a distributed forming module configured to form, based on the accessed nodes, a node distribution data structure that points to every node in the federation infrastructure.

11. The system as recited in claim 10, wherein the nodes and routing tables are members of the same proximal ring.

12. The system as recited in claim 11, wherein at least the node identification information and any node references maintained in the routing table are used to address a message to at least one other node in the federation infrastructure.

13. The system as recited in claim 11, wherein at least the node identification information and any node references maintained in the routing table are used to determine at least one node from a set of nodes to address a message to.

14. The system as recited in claim 12, further comprising sending a plurality of messages instead of a single message.

15. The system as recited in claim 10, wherein the nodes and routing tables are members of different proximal rings.

16. The system as recited in claim 15, wherein at least the node identification information and any node references maintained in the routing table are used to address a message to at least one other node in the federation infrastructure.

17. The system as recited in claim 15, wherein at least the node identification information and any node references maintained in the routing table are used to determine at least one node from a set of nodes to address a message to.

18. The system as recited in claim 10, wherein the node distribution data structure comprises a connectivity graph.

19. In a federation infrastructure, a system including a fully connected node distribution data structure, the system comprising:

a receiving module for receiving at a current node an indication that a message is to be sent to from the current node to each of the nodes of the federation infrastructure; and

a sending module for sending the message to at least one other node in the federation infrastructure, whereupon each receiving node accesses stored state information to send the message to at least one other node until all nodes have received the message at least once.

20. The system as recited in claim 19, wherein the message is addressed to a particular identified node among the plurality of nodes in the federation infrastructure.