RENDEZVOUSING RESOURCE REQUESTS WITH CORRESPONDING RESOURCES
First Claim
1. At a computer system including one or more processors and system memory, a method for partitioning a sorted linked list of node IDs representing corresponding nodes in a federation infrastructure into a hierarchical tree of rings, the method comprising:
- an act of accessing a sorted linked list of unique nodes IDs assigned to a federation infrastructure, each unique node ID assigned to a corresponding node in the federation infrastructure;
an act of accessing a partially-ordered list of a plurality of different types of proximity criteria for partitioning the sorted linked list into a plurality of sub-rings of a hierarchical tree of rings, the partially-ordered list defining the following;
a first proximity criteria type that is to be used at a first sub-ring level when partitioning the sorted linked list into the hierarchical tree of rings;
a second proximity criteria type that is to be used at a second sub-ring level that is below the first sub-ring level when partitioning the sorted linked list into the hierarchical tree of rings; and
a third proximity criteria type that is to be used at a third sub-ring level that is below the second sub-ring level when partitioning the sorted linked list into the hierarchical tree of rings;
an act of partitioning the node IDs in the sorted linked list into the hierarchical tree of rings based on the first, second and third proximity criteria types, the hierarchical tree of rings including;
a root ring that includes all the node IDs in the sorted linked list; and
a plurality of lower-level sub-rings arranged within a plurality of lower sub-ring levels, including the first, second, and third lower sub-ring levels, the plurality of lower sub-ring levels arranged relative to one another within the hierarchical tree in accordance with the plurality of different types of proximity criteria in the partially-ordered list, each lower sub-ring level including a plurality of different sub-rings at the lower sub-ring level, each different sub-ring at the lower sub-ring level representing a corresponding different equivalence class of node IDs based on assigned values for one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree,wherein node IDs of the same equivalence class within the same lower sub-ring level have the same value for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring within the hierarchical tree, andwherein nodes of different equivalence classes within the same lower sub-ring level have at least one different value for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree of rings; and
an act of generating a routing table for at least one node in the federation infrastructure, the at least one node belonging to the root ring as well as at least one sub-ring in each of the first, second, and third lower sub-ring levels, the routing table comprising routing information for the root ring as well as routing information for each sub-ring to which the at least one node belongs, for each ring the routing information including;
a predecessor node to the at least one node, the predecessor node preceding the at least one node in a first direction within the ring;
a successor node to the at least one node, the successor node succeeding the at least one node in the first direction within the ring;
appropriate neighborhood nodes of the at least one node, the neighborhood nodes identified in both the first direction and in a second opposite direction relative to the at least one node based on a neighborhood range and neighborhood size for the ring; and
appropriate routing nodes of the at least one node.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 Claims
-
1. At a computer system including one or more processors and system memory, a method for partitioning a sorted linked list of node IDs representing corresponding nodes in a federation infrastructure into a hierarchical tree of rings, the method comprising:
-
an act of accessing a sorted linked list of unique nodes IDs assigned to a federation infrastructure, each unique node ID assigned to a corresponding node in the federation infrastructure; an act of accessing a partially-ordered list of a plurality of different types of proximity criteria for partitioning the sorted linked list into a plurality of sub-rings of a hierarchical tree of rings, the partially-ordered list defining the following; a first proximity criteria type that is to be used at a first sub-ring level when partitioning the sorted linked list into the hierarchical tree of rings; a second proximity criteria type that is to be used at a second sub-ring level that is below the first sub-ring level when partitioning the sorted linked list into the hierarchical tree of rings; and a third proximity criteria type that is to be used at a third sub-ring level that is below the second sub-ring level when partitioning the sorted linked list into the hierarchical tree of rings; an act of partitioning the node IDs in the sorted linked list into the hierarchical tree of rings based on the first, second and third proximity criteria types, the hierarchical tree of rings including; a root ring that includes all the node IDs in the sorted linked list; and a plurality of lower-level sub-rings arranged within a plurality of lower sub-ring levels, including the first, second, and third lower sub-ring levels, the plurality of lower sub-ring levels arranged relative to one another within the hierarchical tree in accordance with the plurality of different types of proximity criteria in the partially-ordered list, each lower sub-ring level including a plurality of different sub-rings at the lower sub-ring level, each different sub-ring at the lower sub-ring level representing a corresponding different equivalence class of node IDs based on assigned values for one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree, wherein node IDs of the same equivalence class within the same lower sub-ring level have the same value for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring within the hierarchical tree, and wherein nodes of different equivalence classes within the same lower sub-ring level have at least one different value for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree of rings; and an act of generating a routing table for at least one node in the federation infrastructure, the at least one node belonging to the root ring as well as at least one sub-ring in each of the first, second, and third lower sub-ring levels, the routing table comprising routing information for the root ring as well as routing information for each sub-ring to which the at least one node belongs, for each ring the routing information including; a predecessor node to the at least one node, the predecessor node preceding the at least one node in a first direction within the ring; a successor node to the at least one node, the successor node succeeding the at least one node in the first direction within the ring; appropriate neighborhood nodes of the at least one node, the neighborhood nodes identified in both the first direction and in a second opposite direction relative to the at least one node based on a neighborhood range and neighborhood size for the ring; and appropriate routing nodes of the at least one node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. In a federation infrastructure, the federation infrastructure represented by a linked list of nodes, the linked list of nodes partitioned into a hierarchical tree of rings including a root ring and a plurality of lower sub-ring levels of sub-rings, a method for populating a node routing table for a current node taking a plurality of different types of proximity criteria into account, the method comprising:
-
an act of determining that the current node participates in a plurality of rings in the hierarchical tree of rings, the plurality of rings including the root ring and a plurality of lower level sub-rings, each of the plurality of lower level sub-rings partitioned from the root ring based on a previously defined partially ordered list of different types of proximity criteria, the previously defined partially ordered list defining the following;
a first proximity criteria type that is to be used at a first sub-ring level of a hierarchical tree of rings when partitioning the sorted linked list into a hierarchical tree of rings, a second, different proximity criteria type that is to be used at a second, different sub-ring level of a hierarchical tree of rings when partitioning the sorted linked list into a hierarchical tree of rings, and a third, different proximity criteria type that is to be used at a third, different sub-ring level of a hierarchical tree of rings when partitioning the sorted linked list into a hierarchical tree of rings; andan act of inserting different routing information into a routing table for the current node for each ring in the plurality of rings the current node participates in, including the root ring as well as a plurality of lower level sub-rings, for each ring the act comprising; an act of inserting a predecessor node to the current node into the routing table for the current node, the predecessor node preceding the current node in a first direction within the ring; an act of inserting a successor node to the current node into the routing table for the current node, the successor node succeeding the current node in the first direction within the ring; an act of inserting appropriate neighborhood nodes of the current node into the routing table for the current node the current node, the neighborhood nodes identified in both the first direction and in a second opposite direction relative to the current node based on a neighborhood range and neighborhood size for the ring; and an act of inserting appropriate routing nodes of the current node into the routing table for the current node. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. A computer program product for use in a federation infrastructure, the federation infrastructure represented by a linked list of nodes, the linked list of nodes partitioned into a hierarchical tree of rings including a root ring and a plurality of lower sub-ring levels of sub-rings, the computer program product for implementing a method for populating a routing table for a current node taking the plurality of different types of proximity criteria into account, the computer program product comprising one or more computer storage devices having stored thereon computer-executable instructions that, when executed by a processor, cause the namespace federation infrastructure to perform the method, including the following:
-
determine that the current node participates in a plurality of rings in the hierarchical tree of rings, the plurality of rings including the root ring and a plurality of lower level sub-rings, each of the plurality of lower level sub-rings partitioned from the root ring based on a previously defined partially ordered list of different types of proximity criteria, the previously defined partially ordered list defining the following;
a first proximity criteria type that is to be used at a first sub-ring level of a hierarchical tree of rings when partitioning the sorted linked list into a hierarchical tree of rings, a second, different proximity criteria type that is to be used at a second, different sub-ring level of a hierarchical tree of rings when partitioning the sorted linked list into a hierarchical tree of rings, and a third, different proximity criteria type that is to be used at a third, different sub-ring level of a hierarchical tree of rings when partitioning the sorted linked list into a hierarchical tree of rings; andinsert different routing information into a routing table for the current node for each ring in the plurality of rings the current node participates in, including that root ring as well as a plurality of lower level sub-rings, for each ring the act comprising; insert a predecessor node to the current node into the routing table for the current node, the predecessor node preceding the current node in a first direction within the ring; insert a successor node to the current node into the routing table for the current node, the successor node succeeding the current node in the first direction within the ring; insert appropriate neighborhood nodes of the current node into the routing table for the current node, the neighborhood nodes identified in both the first direction and in a second opposite direction based on a neighborhood range and neighborhood size for the ring; and insert appropriate routing nodes of the current node into the routing table for the current node.
-
Specification