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 . A method for partitioning the nodes of a federation infrastructure, the method comprising: 
 an act of accessing a sorted linked list containing node IDs that have been assigned to nodes in the federation infrastructure;    an act of accessing proximity categories that represent a plurality of different proximity criteria for partitioning the sorted linked list; and    an act of partitioning the sorted linked list into one or more first sub lists based on a first proximity criterion, each of the one or more first sub lists containing at least a subset of the node IDs from the sorted linked list.    
   
   
       2 . The method as recited in  claim 1 , wherein the act of accessing a sorted linked list containing node IDs comprises an act of access a bi-directional linked list.  
   
   
       3 . The method as recited in  claim 1 , wherein an act of accessing proximity categories that represent a plurality of different proximity criteria comprises an act of accessing a previously defined partially ordered list of proximity criterion.  
   
   
       4 . The method as recited in  claim 1 , wherein an act of accessing proximity categories that represent a plurality of different proximity criteria comprises an act of accessing proximity categories selected from among geographic locations, organizational boundaries, administrative boundaries, and routing characteristics.  
   
   
       5 . The method as recited in  claim 1 , wherein an act of partitioning the sorted linked list into one or more first sub-lists based on a first proximity criterion comprises an act partitioning a ring into a plurality of corresponding sub-rings.  
   
   
       6 . The method as recited in  claim 1 , wherein an act of partitioning the sorted linked list into one or more first sub-lists based on a first proximity criterion comprises an act partitioning the sorted link list into one or more first sub-lists wherein at least two of the one or more first sub lists contain a node with the same node ID.  
   
   
       7 . The method as recited in  claim 6 , wherein the act of partitioning the sorted linked list into one or more first sub-lists based on a first proximity criterion comprises an act partitioning a ring into a plurality of branches.  
   
   
       8 . The method as recited in  claim 7 , wherein the act partitioning a ring into a plurality of branches comprises an act of a node participating in two or more of the partitioned branches.  
   
   
       9 . The method as recited in  claim 8 , wherein the act of a node participating in two or more of the partitioned branches comprises an act of using aliasing to associate the specified node with each of the two or more branches.  
   
   
       10 . The method are recited in claim,  1  wherein an act of partitioning the sorted linked list into one or more first sub lists based on a first proximity criterion comprises an act of partitioning the sorted list based on a previously defined partially ordered list of proximity criteria.  
   
   
       11 . The method as recited in  claim 1 , wherein the act of partitioning the sorted linked list into one or more first sub lists based on a first proximity criterion comprises an act of partitioning the sorted linked list into one or more first sub lists that inherent ring parameters from the sorted linked list.  
   
   
       12 . The method as recited in  claim 1 , wherein the act of partitioning the sorted linked list into one or more first sub lists based on a first proximity criterion comprises an act of partitioning the sorted linked list into one or more first sub lists having individually configured ring parameters that differ from the ring parameters for the sorted linked list.  
   
   
       13 . The method as recited in  claim 1 , further comprising: 
 an act of partitioning a first sub list, selected from among the one or more first sub lists, into one or more second sub lists based on a second proximity criteria, each of the one or more second sub lists containing at least a subset of node IDs from the first sub list.    
   
   
       14 . The method as recited in  claim 13 , wherein the act of partitioning a first sub list comprises an act of partitioning the sub list based on a previously defined partially ordered list of proximity criteria.  
   
   
       15 . The method as recited in  claim 11 , wherein the act of partitioning a first sub list comprises an act of partitioning a branch that was partitioned based onto the first proximity criteria into a plurality of additional sub-branches based on the second proximity criteria.  
   
   
       16 . The method as recited in  claim 11 , wherein the act of partitioning a first sub list comprises an act of partitioning a first sub list into one or more second sub lists that inherent ring parameters from the first sub list.  
   
   
       17 . The method as recited in  claim 11 , wherein the act of partitioning a first sub list comprises an act of partitioning a first sub list into one or more second sub lists having individually configured ring parameters that differ from the ring parameters for the first sub list.  
   
   
       18 . In a federation infrastructure, a method for populating a node routing table, the method comprising: 
 an act of inserting a predecessor node into a routing table, the predecessor node preceding a current node relative to the current node in a first direction of a sorted linked list;    an act of inserting a successor node into the routing table, the successor node succeeding the current node relative to the current node in the first direction in the sorted linked list;    an act of inserting appropriate neighborhood nodes into the routing table, the neighborhood nodes identified from the sorted linked list in both the first direction and in a second opposite direction based on a neighborhood range and neighborhood size; and    an act of inserting appropriate routing nodes into the routing table, the routing nodes identified from the sorted linked list in both the first and second directions based on the a number base and field size of the ID space for the federation infrastructure, the routing nodes representing a logarithmic index of the sorted link list in both the first and second directions.    
   
   
       19 . The method as recited in  claim 18 , wherein the act of inserting a predecessor node into a routing table comprises an act of establishing a symmetric partnership between the current node and the predecessor node such that current node is a partner of predecessor node and the predecessor node is a partner of the current node.  
   
   
       20 . The method as recited in  claim 18 , wherein the act of establishing a symmetric partnership between the current node and the predecessor node comprises an act of the predecessor node viewing the partnership with the current node such that the current node is the successor node of the predecessor node  
   
   
       21 . The method as recited in  claim 18 , wherein the act of inserting a successor node into a routing table comprises an act of establishing a symmetric partnership between the current node and the successor node such that current node is a partner of successor node and the successor node is a partner of the current node.  
   
   
       22 . The method as recited in  claim 21 , wherein the act of establishing a symmetric partnership between the current node and the successor node comprises an act of the successor node views the partnership with the current node such that the current node is the predecessor node of the successor node.  
   
   
       23 . The method as recited in  claim 18 , wherein the act of inserting appropriate neighborhood nodes into the routing table comprises an act of establishing a symmetric partnership between the current node and the appropriate neighborhood nodes such that current node is a partner of appropriate neighborhood nodes and the appropriate neighborhood nodes are partners of the current node.  
   
   
       24 . The method as recited in  claim 23 , wherein the act of establishing a symmetric partnership between the current node and the appropriate neighborhood nodes comprises an act of the inserting the current node as a neighborhood node in the routing table of the appropriate neighborhood nodes.  
   
   
       25 . The method as recited in  claim 18 , wherein the act of inserting appropriate routing nodes into the routing table comprises an act of establishing a symmetric partnership between the current node and the one or more routing nodes such that current node is a partner of the one or more routing nodes and one or more routing nodes are partners of the current node.  
   
   
       26 . The method as recited in  claim 25 , wherein the act of establishing a symmetric partnership between the current node and the one or more routing nodes comprises an act of inserting the current node in the routing table of the routing nodes as a mathematically opposite routing partner node.  
   
   
       27 . In a federation infrastructure, a method for populating a node routing table for a current node taking proximity criteria into account, the method comprising: 
 an act of inserting a predecessor node for each hierarchically partitioned routing ring the current node participates in into a routing table, each predecessor node preceding the current node in a first direction within each hierarchically partitioned routing ring the current node participates in, the hierarchically partitioned routing rings being partitioned in accordance with corresponding proximity criteria and containing at least subsets of a bi-directional linked list;    an act of inserting a successor node for each hierarchically partitioned routing ring the current node participates in into the routing table, each successor node succeeding the current node in the first direction within each hierarchically partitioned routing ring the current node participates in;    an act of inserting appropriate neighborhood nodes for each hierarchically partitioned routing ring the current node participates in into the routing table, the neighborhood nodes identified in both the first direction and in a second opposite direction based on a neighborhood range and neighborhood size from the hierarchically partitioned routing rings the current node participates in; and    an act of inserting appropriate routing nodes for each hierarchically partitioned routing ring the current node participates in into the routing table.    
   
   
       28 . The method as recited in  claim 27 , wherein the act of inserting a predecessor node for each hierarchically partitioned routing ring the current node participates in into a routing table comprising an act of inserting a first predecessor node for a first ring at a first level in a hierarchical tree of rings and inserting a second predecessor node for a second ring at second different level in the hierarchical tree of rings.  
   
   
       29 . The method as recited in  claim 27 , wherein the act of inserting a predecessor node for each hierarchically partitioned routing ring the current node participates in into a routing table comprising an act of inserting predecessor nodes for one or more rings that are configured in accordance with a corresponding one or more ring parameters.  
   
   
       30 . The method as recited in  claim 29 , wherein the act of inserting predecessor nodes for one or more rings that are configured in accordance with corresponding one or more ring parameters comprises an act of inserting a first predecessor node for a first ring having first ring parameters and inserting a second predecessor node for a second lower level ring that inherited at least some of the first ring parameters from the first ring.  
   
   
       31 . The method as recited in  claim 27 , wherein the act of inserting a predecessor node for each hierarchically partitioned routing ring the current node participates in into a routing table comprising an act of inserting a first predecessor node for a first ring at a first level in a hierarchical tree of rings and inserting a second predecessor node for a second ring also at the first level in the hierarchical tree of rings.  
   
   
       32 . The method as recited in  claim 27 , wherein the act of inserting a successor node for each hierarchically partitioned routing ring the current node participates in into a routing table comprising an act of inserting a first successor node for a first ring at a first level in a hierarchical tree of rings and inserting a second successor node for a second ring at second different level in the hierarchical tree of rings.  
   
   
       33 . The method as recited in  claim 27 , wherein the act of inserting a successor node for each hierarchically partitioned routing ring the current node participates in into a routing table comprising an act of inserting successor nodes for one or more rings that are configured in accordance with a corresponding one or more ring parameters.  
   
   
       34 . The method as recited in  claim 33 , wherein the act of inserting successor nodes for one or more rings that are configured in accordance with a corresponding one or more ring parameters comprises an act of inserting a first successor node for a first ring having first ring parameters and inserting a second successor node for a second lower level ring that inherited at least some of the first ring parameters from the first ring.  
   
   
       35 . The method as recited in  claim 27 , wherein the of inserting a successor node for each hierarchically partitioned routing ring the current node participates in into a routing table comprising an act of inserting a first successor node for a first ring at a first level in a hierarchical tree of rings and inserting a second successor node for a second ring also at the first level in the hierarchical tree of rings.  
   
   
       36 . The method as recited in  claim 27 , wherein the act of inserting appropriate neighborhood nodes for each hierarchically partitioned routing ring the current node participates in into the routing table comprising an act of inserting first appropriate neighborhood nodes for a first ring at a first level in a hierarchical tree of rings and inserting second appropriate neighborhood nodes for a second ring at a second different level in the hierarchical tree of rings.  
   
   
       37 . The method as recited in  claim 27 , wherein the act of inserting appropriate neighborhood nodes for each hierarchically partitioned routing ring the current node participates in into a routing table comprising an act of inserting appropriate neighborhood nodes for one or more rings that are configured in accordance with a corresponding one or more ring parameters.  
   
   
       38 . The method as recited in  claim 37 , wherein the act of inserting appropriate neighborhood nodes for one or more rings that are configured in accordance with corresponding one or more ring parameters comprises an act of inserting a first appropriate neighborhood nodes for a first ring having first ring parameters and inserting a second appropriate neighborhood nodes for a second lower level ring that inherited at least some of the first ring parameters from the first ring.  
   
   
       39 . The method as recited in  claim 27 , wherein the act of inserting appropriate neighborhood nodes for each hierarchically partitioned routing ring the current node participates in into the routing table comprising an act of inserting first appropriate neighborhood nodes for a first ring at a first level in a hierarchical tree of rings and inserting second appropriate neighborhood nodes for a second ring also at the first level in the hierarchical tree of rings.  
   
   
       40 . The method as recited in  claim 27 , wherein the act of inserting appropriate routing nodes for each hierarchically partitioned routing ring the current node participates in into the routing table comprising an act of inserting first appropriate routing nodes for a first ring at a first level in a hierarchical tree of rings and inserting second appropriate routing nodes for a second ring at a second different level in the hierarchical tree of rings.  
   
   
       41 . The method as recited in  claim 27 , wherein the act of inserting appropriate routing nodes for each hierarchically partitioned routing ring the current node participates in into a routing table comprising an act of inserting appropriate routing nodes for one or more rings that are configured in accordance with a corresponding one or more ring parameters.  
   
   
       42 . The method as recited in  claim 41 , wherein the act of inserting appropriate routing nodes for one or more rings that are configured in accordance with corresponding one or more ring parameters comprises an act of inserting a first appropriate routing nodes for a first ring having first ring parameters and inserting a second appropriate routing nodes for a second lower level ring that inherited at least some of the first ring parameters from the first ring.  
   
   
       43 . The method as recited in  claim 27 , wherein the act of inserting appropriate routing nodes for each hierarchically partitioned routing ring the current node participates in into the routing table comprising an act of inserting first appropriate routing nodes for a first ring at a first level in a hierarchical tree of rings and inserting second appropriate routing nodes for a second ring also at the first level in the hierarchical tree of rings.  
   
   
       44 . The method as recited in  claim 27 , wherein the act of inserting appropriate routing nodes for each hierarchically partitioned routing ring the current node participates in into the routing table comprises an act of inserting appropriate routing nodes for each proximity ring the current node participates in.  
   
   
       45 . A computer program product for use in a federation infrastructure, the computer program product for implementing a method for partitioning the nodes of a federation infrastructure, the computer program product comprising one or more computer-readable media having stored thereon computer-executable instructions that, when executed by a processor, cause the federation infrastructure to perform the following: 
 access a sorted linked list containing node IDs that have been assigned to nodes in the federation infrastructure;    access proximity categories that represent a plurality of different proximity criteria for partitioning the sorted linked list; and    partition the sorted linked list into one or more first sub lists based on a first proximity criterion, each of the one or more first sub lists containing at least a subset of the node IDs from the sorted linked list.    
   
   
       46 . The computer program product as recited in  claim 45 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to access proximity criterion that represent a plurality of different proximity criteria comprise computer-executable instructions, that when executed, cause the federation infrastructure to access a previously defined partially ordered list of proximity criterion.  
   
   
       47 . The computer program product as recited in  claim 45 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to access proximity criterion that represent a plurality of different proximity criteria comprise computer-executable instructions, that when executed, cause the federation infrastructure to access proximity categories selected from among geographic locations, organizational boundaries, administrative boundaries, and routing characteristics.  
   
   
       48 . The method as recited in  claim 45 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to partition the sorted linked list into one or more first sub-lists based on a first proximity criterion comprise computer-executable instructions, that when executed, cause the federation infrastructure to partition a ring into a plurality of corresponding sub-rings.  
   
   
       49 . The method as recited in  claim 45 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to partition a ring into a plurality of corresponding sub-rings comprise computer-executable instructions, that when executed, cause the federation infrastructure to use aliasing to cause a node to participate in two or more of the corresponding sub-rings.  
   
   
       50 . The computer program product as recited in  claim 45 , further comprising computer-executable instructions, that when executed, cause the federation infrastructure to: 
 partition a first sub list, selected from among the one or more first sub lists, into one or more second sub lists based on a second proximity criteria, each of the one or more second sub lists containing at least a subset of node s from the first sub list.    
   
   
       51 . A computer program product for use in a federation infrastructure, the computer program product for implementing a method for populating a node routing table, the computer program product comprising one or more computer-readable media having stored thereon computer-executable instructions that, when executed by a processor, cause the namespace federation infrastructure to perform the following: 
 insert a predecessor node into a routing table, the predecessor node preceding a current node relative to the current node in a first direction of a sorted linked list;    insert a successor node into the routing table, the successor node succeeding the current node relative to the current node in the second direction in the sorted linked list;    insert appropriate neighborhood nodes into the routing table, the neighborhood nodes identified from the sorted linked list in both the first direction and in a second opposite direction based on a neighborhood range and neighborhood size; and    insert one or more routing nodes into the routing table, the routing nodes identified from the sorted linked list in both the first and second directions based on the a number base and field size of the ID space for the federation infrastructure, the routing nodes representing a logarithmic index of the sorted link list in both the first and second directions.    
   
   
       52 . The computer program product as recited in  claim 51 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to insert a predecessor node into a routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to establishing a symmetric partnership between the current node and the predecessor node such that the predecessor node views the current node as the successor node of the predecessor node.  
   
   
       53 . The computer program product as recited in  claim 51 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to insert a successor node into a routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to establishing a symmetric partnership between the current node and the successor node such that the successor node views the current node as the predecessor node of the successor node.  
   
   
       54 . The computer program product as recited in  claim 51 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to insert appropriate neighborhood nodes into the routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to establish a symmetric partnership between the current node and the appropriate neighborhood such that the appropriate neighborhood nodes view the current node as a neighborhood node.  
   
   
       55 . The computer program product as recited in  claim 51 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to insert one or more routing nodes into the routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to establish a symmetric partnership between the current node and the one or more routing nodes such that each of the one or more routing nodes views the current node as a mathematically opposite routing partner node.  
   
   
       56 . A computer program product for use in a federation infrastructure, the computer program product for implementing a method for populating a node routing table for a current node taking proximity criteria into account, the computer program product comprising one or more computer-readable media having stored thereon computer-executable instructions that, when executed by a processor, cause the namespace federation infrastructure to perform the following: 
 inserting a predecessor node for each hierarchically partitioned routing ring the current node participates in into a routing table, each predecessor node preceding the current node in a first direction within each hierarchically partitioned routing ring the current node participates in, the hierarchically partitioned routing rings being partitioned in accordance with corresponding proximity criteria and containing at least subsets of a bi-directional linked list;    inserting a successor node for each hierarchically partitioned routing ring the current node participates in into the routing table, each successor node succeeding the current node in the first direction within each hierarchically partitioned routing ring the current node participates in;    inserting appropriate neighborhood nodes for each hierarchically partitioned routing ring the current node participates in into the routing table, the neighborhood nodes identified in both the first direction and in a second opposite direction based on a neighborhood range and neighborhood size from the hierarchically partitioned routing rings the current node participates in; and    inserting appropriate routing nodes for each hierarchically partitioned routing ring the current node participates in into the routing table.    
   
   
       57 . The computer program product as recited in  claim 56 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to inset a predecessor node for each hierarchically partitioned routing ring the current node participates in into a routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to insert a first predecessor node for a first ring at a first level in a hierarchical tree of rings and insert a second predecessor node for a second ring at second different level in the hierarchical tree of rings.  
   
   
       58 . The computer program product as recited in  claim 56 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to inset a predecessor node for each hierarchically partitioned routing ring the current node participates in into a routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to insert a first predecessor node for a first ring at a first level in a hierarchical tree of rings and insert a second predecessor node for a second ring also at the first level in the hierarchical tree of rings.  
   
   
       59 . The computer program product as recited in  claim 56 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to insert a successor node for each hierarchically partitioned routing ring the current node participates in into a routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to insert a first successor node for a first ring at a first level in a hierarchical tree of rings and insert a second successor node for a second ring at second different level in the hierarchical tree of rings.  
   
   
       60 . The computer program product as recited in  claim 56 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to insert a successor node for each hierarchically partitioned routing ring the current node participates in into a routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to insert a first successor node for a first ring at a first level in a hierarchical tree of rings and insert a second successor node for a second ring also at the first level in the hierarchical tree of rings.  
   
   
       61 . The computer program product as recited in  claim 56 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to insert appropriate neighborhood nodes for each hierarchically partitioned routing ring the current node participates in into the routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to insert first appropriate neighborhood nodes for a first ring at a first level in a hierarchical tree of rings and insert second appropriate neighborhood nodes for a second ring at a second different level in the hierarchical tree of rings.  
   
   
       62 . The computer program product as recited in  claim 56 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to insert appropriate neighborhood nodes for each hierarchically partitioned routing ring the current node participates in into the routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to insert first appropriate neighborhood nodes for a first ring at a first level in a hierarchical tree of rings and insert second appropriate neighborhood nodes for a second ring also at the first level in the hierarchical tree of rings.  
   
   
       63 . The computer program product as recited in  claim 56 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to insert appropriate routing nodes for each hierarchically partitioned routing ring the current node participates in into the routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to insert first appropriate routing nodes for a first ring at a first level in a hierarchical tree of rings and insert second appropriate routing nodes for a second ring at a second different level in the hierarchical tree of rings.  
   
   
       64 . The computer program product as recited in  claim 56 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to insert appropriate routing nodes for each hierarchically partitioned routing ring the current node participates in into the routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to insert first appropriate routing nodes for a first ring at a first level in a hierarchical tree of rings and insert second appropriate routing nodes for a second ring also at the first level in the hierarchical tree of rings.  
   
   
       65 . The computer program product as recited in  claim 56 , wherein computer-executable instructions, that when executed, cause the federation infrastructure to insert appropriate routing nodes for each hierarchically partitioned routing ring the current node participates in into the routing table comprise computer-executable instructions, that when executed, cause the federation infrastructure to insert appropriate routing nodes for each proximity ring the current node participates in.