RENDEZVOUSING RESOURCE REQUESTS WITH CORRESPONDING RESOURCES
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 that references each of a plurality of nodes in the federation infrastructure, the method comprising:
an act of a computer system, which includes at least one processor, accessing a federation infrastructure comprising plurality of nodes organized into a root ring and a plurality of sub-rings below the root ring that each group the plurality of nodes based on proximity criterion, each node including:
a corresponding numeric identifier uniquely selected from a range of numeric values and that determines a sorted order of the plurality of nodes in each of the rings; and
a corresponding routing table that represents separate routing information for the root ring of nodes and for each of the plurality of sub-rings for which said node is a member, the separate routing information referencing a plurality of routing nodes within each ring for which said node is a member and of which said node has knowledge;
an act of accessing a first routing table from a first node to identify a first plurality of routing nodes of which the first node has knowledge, the first node being a member of a plurality of the sub-rings and storing the separate routing information for the root ring and each of the plurality of the sub-rings;
an act of subsequently accessing each routing table from each of the plurality of nodes in the federation infrastructure by recursively accessing at least a second routing table from at least one of the routing nodes for which the first node has knowledge; and
based on the accessed each routing table from each of the plurality of nodes, an act of forming a node distribution data structure that references each of the plurality of nodes in the federation infrastructure.
2 . The method as recited in claim 1 , wherein the plurality of routing nodes within each ring for which said node is a member are members of the same proximal ring.
3 . The method as recited in claim 1 , wherein the node distribution data structure is used to address a message to at least one other node in the federation infrastructure.
4 . The method as recited in claim 1 , wherein the node distribution data structure is used to determine at least one node from a set of nodes to address a message to.
5 . The method as recited in claim 2 , further comprising sending a plurality of messages instead of a single message.
6 . The method as recited in claim 1 , wherein each of the plurality of sub-rings represent different proximal rings that sort the plurality of nodes based on different proximity criteria.
7 . The method as recited in claim 6 , wherein the node distribution data structure is used by the first node to address a message to at least one other node in the federation infrastructure that is a member of a different proximal ring.
8 . The method as recited in claim 1 , wherein the node distribution data structure comprises a connectivity graph.
9 . The method as recited in claim 1 , further comprising:
an act of receiving at the first node an indication that a message is to be sent to from the first node to each of the plurality of nodes of the federation infrastructure; and
an act of sending the message to each of the plurality of nodes using the node distribution data structure.
10 . The method as recited in claim 1 , wherein the corresponding routing table includes, for each ring for which said node is a member:
a predecessor node identified by a predecessor numeric identifier sorted immediately prior to said corresponding numeric identifier within said ring;
a successor node identified by a successor numeric identifier sorted immediately subsequent to said corresponding numeric identifier within said ring;
a plurality of neighbor nodes identified by a first sequence of numeric identifiers sorted immediately prior to said corresponding numeric identifier within said ring and a second sequence of numeric identifiers sorted immediately subsequent to said corresponding identifier within said ring; and
an index of other nodes, each having a logarithmically-increasing distance from said node within said ring.
11 . In a federation infrastructure, a system configured to create and maintain a node distribution data structure that references each of a plurality of nodes in the federation infrastructure, the system comprising:
at least one processor; and
one or more computer storage media having stored thereon computer executable instructions that, when executed by the at least one processor, implement a method comprising:
an act of accessing a federation infrastructure comprising plurality of nodes organized into a root ring and a plurality of sub-rings below the root ring that each group the plurality of nodes based on proximity criterion, each node including:
a corresponding numeric identifier uniquely selected from a range of numeric values and that determines a sorted order of the plurality of nodes in each of the rings; and
a corresponding routing table that represents separate routing information for the root ring of nodes and for each of the plurality of sub-rings for which said node is a member, the separate routing information referencing a plurality of routing nodes within each ring for which said node is a member and of which said node has knowledge;
an act of accessing a first routing table from a first node to identify a first plurality of routing nodes of which the first node has knowledge, the first node being a member of a plurality of the sub-rings and storing the separate routing information for the root ring and each of the plurality of the sub-rings;
an act of subsequently accessing each routing table from each of the plurality of nodes in the federation infrastructure by recursively accessing at least a second routing table from at least one of the routing nodes for which the first node has knowledge; and
based on the accessed each routing table from each of the plurality of nodes, an act of forming a node distribution data structure that references each of the plurality of nodes in the federation infrastructure.
12 . The system as recited in claim 11 , wherein the plurality of routing nodes within each ring for which said node is a member are members of the same proximal ring.
13 . The system as recited in claim 11 , wherein the node distribution data structure is used to address a message to at least one other node in the federation infrastructure.
14 . The system as recited in claim 11 , wherein the node distribution data structure is used to determine at least one node from a set of nodes to address a message to.
15 . The system as recited in claim 13 , further comprising sending a plurality of messages instead of a single message.
16 . The system as recited in claim 10 , wherein each of the plurality of sub-rings represent different proximal rings that sort the plurality of nodes based on different proximity criteria.
17 . The system as recited in claim 16 , wherein the node distribution data structure is used by the first node to address a message to at least one other node in the federation infrastructure that is a member of a different proximal ring.
18 . The system as recited in claim 10 , wherein the node distribution data structure comprises a connectivity graph.
19 . The system as recited in claim 11 , further comprising:
an act of receiving at the first node an indication that a message is to be sent to from the first node to each of the plurality of nodes of the federation infrastructure; and
an act of sending the message to each of the plurality of nodes using the node distribution data structure.
20 . One or more computer storage devices having stored thereon computer executable instructions that, when executed by at least one processor of a computer system, implement a method for creating and maintaining a node distribution data structure that references each of a plurality of nodes in the federation infrastructure, the method comprising:
an act of the computer system accessing a federation infrastructure comprising plurality of nodes organized into a root ring and a plurality of sub-rings below the root ring that each group the plurality of nodes based on proximity criterion, each node including:
a corresponding numeric identifier uniquely selected from a range of numeric values and that determines a sorted order of the plurality of nodes in each of the rings; and
a corresponding routing table that represents separate routing information for the root ring of nodes and for each of the plurality of sub-rings for which said node is a member, the separate routing information referencing a plurality of routing nodes within each ring for which said node is a member and of which said node has knowledge;
an act of accessing a first routing table from a first node to identify a first plurality of routing nodes of which the first node has knowledge, the first node being a member of a plurality of the sub-rings and storing the separate routing information for the root ring and each of the plurality of the sub-rings;
an act of subsequently accessing each routing table from each of the plurality of nodes in the federation infrastructure by recursively accessing at least a second routing table from at least one of the of routing nodes for which the first node has knowledge; and
based on the accessed each routing table from each of the plurality of nodes, an act of forming a node distribution data structure that references each of the plurality of nodes in the federation infrastructure.