Rendezvousing resource requests with corresponding resources
AssigneeMicrosoft Corporation
InventorsGopala Krishna R. Kakivaya, Richard L. Hasha, Thomas Lee Rodeheffer
Life of this patent
Estimating the term…
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.
Claims20
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.
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.
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.
Dependencies are inferred from the claim text.