×

Rendezvousing resource requests with corresponding resources

  • US 8,417,813 B2
  • Filed: 06/07/2011
  • Issued: 04/09/2013
  • Est. Priority Date: 10/22/2004
  • Status: Expired due to Fees
First Claim
Patent Images

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.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×