Rendezvousing resource requests with corresponding resources

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.

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.