Inter-proximity communication within a rendezvous federation
First Claim
1. At a computer system, a method for sending communication in a federation infrastructure represented by a 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 below the root ring, the plurality of lower sub-ring levels defined in accordance with a plurality of different user-defined proximity category types corresponding to each lower sub-ring level,wherein the root ring includes all the nodes in the linked list of nodes, and the plurality of lower sub-ring levels are arranged relative to one another within the hierarchical tree in accordance with a plurality of different proximity criteria representing the different user-defined proximity category types, each lower sub-ring level including a plurality of different sub-rings, each different sub-ring representing a corresponding different equivalence class of nodes based on assigned values for one or more of the plurality of different proximity criteria for the corresponding different proximity criteria category type for the lower sub-ring level,wherein nodes 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 in the same proximity category type corresponding to the same lower sub-ring level and nodes of different equivalence classes within the same lower sub-ring level have at least one different value for the plurality of different proximity criteria in the same proximity category type corresponding to the same lower sub-ring level, andwherein nodes within the same equivalence class use intra-proximity communication to communicate between one another and nodes within different equivalence classes use inter-proximity communication to communicate between one another, the method comprising:
- an act of receiving a message at a first sub-ring;
an act of determining a node having membership in the first sub-ring is to send a message to another sub-ring,wherein the node is a member of the root ring and a plurality of sub-rings in a plurality of lower sub-ring levels based on the node matching different proximity criteria in different user-defined proximity category types, including (i) the first sub-ring representing a first equivalence class in a first proximity category type corresponding to a first lower sub-ring level, the first sub-ring being one of a plurality of sub-rings in the lower sub-ring level arranged within the tree hierarchy based on the first user-defined proximity category type and (ii) a second sub-ring representing a second equivalence class in a second proximity category type that is different from the first proximity category type, the second proximity category type corresponding to a second lower sub-ring level, the second sub-ring being one of a plurality of sub-rings in the second sub-ring level, the second sub-ring level arranged between the first lower sub-ring level and the root ring within the tree hierarchy based on the second user-defined proximity category type, the first and second sub-rings in each of the first and second sub-ring levels indicative of a first ring path forming a spine of sub-rings from the first sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the node storing separate routing information for the root ring, the first sub-ring, and a sub-ring in each of one or more other sub-ring levels including the second sub-ring, the routing information used by the node to determine membership in the root ring and in each sub-ring, andwherein the other sub-ring represents another different equivalence class, the other sub-ring being a collateral sub-ring of at least one specified sub-ring in the ring path, the first equivalence class and the other different equivalence class having at least one differing value for a proximity criteria, collateral sub-rings comprising a specialized type of rings including peer rings of the specified sub-ring and peer rings of the specified ring'"'"'s ancestor rings, the collateral sub-ring of the specified sub-ring comprising a collateral sub-ring of nodes included in the specified sub-ring;
an act of using intra-ring communication within the first sub-ring to identify a further node with a collateral ring set having an entry node into an additional sub-ring in a second ring path,wherein the collateral ring set comprises a set of one or more collateral sub-rings from the perspective of the specified sub-ring and comprises a specialized set of sub-rings in the tree of rings, wherein the specialized set of rings is unique for each ring, each collateral sub-ring node storing collateral sub-ring membership information and corresponding entry node information for each sub-ring, andwherein the second ring path forms a spine of sub-rings from the other sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the additional sub-ring being at the same specified sub-ring level as one of the sub-rings in the first ring path, the specified sub-ring level being below the root ring in the hierarchical tree of rings;
an act of using inter-ring communication to send the message from the further node to the additional sub-ring at the same specified sub-ring level so as to bypass the root ring, including;
an act of the further node accessing the entry node into the additional sub-ring from the further node'"'"'s collateral ring set entry table; and
an act of the further node sending the message to the entry node into the additional sub-ring.
2 Assignments
0 Petitions
Accused Products
Abstract
The present invention extends to methods, systems, and computer program products for facilitating inter-proximity communication within a rendezvous federation. Nodes maintain collateral ring set entry tables that include collateral rings and corresponding entry nodes into the collateral rings. Nodes can exchange collateral ring set entry state to update one another on the configuration of rings within a tree of rings. Nodes can refer to collateral ring set entry tables, as well as to other nodes, to identify entry nodes into rings that are collateral rings of the node. Messages can be sent to entry nodes in collateral rings. A message can include an indication that an entry node in a target proximity ring is to resolve the message to the node in the target proximity ring which has a node ID closest to an indicated destination node.
-
Citations
42 Claims
-
1. At a computer system, a method for sending communication in a federation infrastructure represented by a 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 below the root ring, the plurality of lower sub-ring levels defined in accordance with a plurality of different user-defined proximity category types corresponding to each lower sub-ring level,
wherein the root ring includes all the nodes in the linked list of nodes, and the plurality of lower sub-ring levels are arranged relative to one another within the hierarchical tree in accordance with a plurality of different proximity criteria representing the different user-defined proximity category types, each lower sub-ring level including a plurality of different sub-rings, each different sub-ring representing a corresponding different equivalence class of nodes based on assigned values for one or more of the plurality of different proximity criteria for the corresponding different proximity criteria category type for the lower sub-ring level, wherein nodes 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 in the same proximity category type corresponding to the same lower sub-ring level and nodes of different equivalence classes within the same lower sub-ring level have at least one different value for the plurality of different proximity criteria in the same proximity category type corresponding to the same lower sub-ring level, and wherein nodes within the same equivalence class use intra-proximity communication to communicate between one another and nodes within different equivalence classes use inter-proximity communication to communicate between one another, the method comprising: -
an act of receiving a message at a first sub-ring; an act of determining a node having membership in the first sub-ring is to send a message to another sub-ring, wherein the node is a member of the root ring and a plurality of sub-rings in a plurality of lower sub-ring levels based on the node matching different proximity criteria in different user-defined proximity category types, including (i) the first sub-ring representing a first equivalence class in a first proximity category type corresponding to a first lower sub-ring level, the first sub-ring being one of a plurality of sub-rings in the lower sub-ring level arranged within the tree hierarchy based on the first user-defined proximity category type and (ii) a second sub-ring representing a second equivalence class in a second proximity category type that is different from the first proximity category type, the second proximity category type corresponding to a second lower sub-ring level, the second sub-ring being one of a plurality of sub-rings in the second sub-ring level, the second sub-ring level arranged between the first lower sub-ring level and the root ring within the tree hierarchy based on the second user-defined proximity category type, the first and second sub-rings in each of the first and second sub-ring levels indicative of a first ring path forming a spine of sub-rings from the first sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the node storing separate routing information for the root ring, the first sub-ring, and a sub-ring in each of one or more other sub-ring levels including the second sub-ring, the routing information used by the node to determine membership in the root ring and in each sub-ring, and wherein the other sub-ring represents another different equivalence class, the other sub-ring being a collateral sub-ring of at least one specified sub-ring in the ring path, the first equivalence class and the other different equivalence class having at least one differing value for a proximity criteria, collateral sub-rings comprising a specialized type of rings including peer rings of the specified sub-ring and peer rings of the specified ring'"'"'s ancestor rings, the collateral sub-ring of the specified sub-ring comprising a collateral sub-ring of nodes included in the specified sub-ring; an act of using intra-ring communication within the first sub-ring to identify a further node with a collateral ring set having an entry node into an additional sub-ring in a second ring path, wherein the collateral ring set comprises a set of one or more collateral sub-rings from the perspective of the specified sub-ring and comprises a specialized set of sub-rings in the tree of rings, wherein the specialized set of rings is unique for each ring, each collateral sub-ring node storing collateral sub-ring membership information and corresponding entry node information for each sub-ring, and wherein the second ring path forms a spine of sub-rings from the other sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the additional sub-ring being at the same specified sub-ring level as one of the sub-rings in the first ring path, the specified sub-ring level being below the root ring in the hierarchical tree of rings; an act of using inter-ring communication to send the message from the further node to the additional sub-ring at the same specified sub-ring level so as to bypass the root ring, including; an act of the further node accessing the entry node into the additional sub-ring from the further node'"'"'s collateral ring set entry table; and an act of the further node sending the message to the entry node into the additional sub-ring. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. At a computer system, a method for sending communication in a network infrastructure represented by a 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 below the root ring, the plurality of lower sub-ring levels defined in accordance with a plurality of different user-defined proximity category types corresponding to each lower sub-ring level,
wherein the root ring includes all the nodes in the linked list of nodes, and the plurality of lower sub-ring levels are arranged relative to one another within the hierarchical tree in accordance with a plurality of different proximity criteria representing the different user-defined proximity category types, each lower sub-ring level including a plurality of different sub-rings, each different sub-ring representing a corresponding different equivalence class of nodes based on assigned values for one or more of the plurality of different proximity criteria for the corresponding different proximity criteria category type for the lower sub-ring level, wherein nodes 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 proximity criteria in the same proximity category type corresponding to the same lower sub-ring level and 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 in the same proximity category type corresponding to the same lower sub-ring level, and wherein nodes within the same equivalence class use intra-proximity communication to communicate between one another and nodes within different equivalence class use inter-proximity communication to communicate between one another, the method comprising: -
an act of a node determining an originating node in a sub-ring that intends to route a message to a destination node closest to a given node ID within another sub-ring, wherein the sub-ring represents one equivalence class and the other sub-ring representing a specified equivalence class, the node not being a member of the other sub-ring, wherein inter-proximity communication is used to send the message to the specified equivalence class, the specified equivalence class identified from values for one or more of the plurality of different proximity criteria corresponding to the message, wherein the sub-ring is included in a first ring path forming a spine of sub-rings from the sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, each sub-ring in the first ring path corresponding to a different sub-ring level, including at least a first sub-ring level defined by a first proximity criteria category type and a second sub-ring level defined by a second, different, proximity criteria category type, the node storing separate routing information for the root ring, the sub-ring, and at least one other sub-ring between the sub-ring and the root ring, the routing information used by the node to determine membership in the root ring and in each sub-ring, and wherein the sub-ring included in the first ring path comprises a collateral sub-ring, collateral sub-rings comprising a specialized type of ring comprising peer rings of the specified sub-ring and peer rings of the specified ring'"'"'s ancestor rings, the collateral sub-ring of the specified sub-ring comprises a collateral sub-ring of those nodes included in the specified sub-ring; an act of using intra-ring communication within the sub-ring to identify a further node with a collateral ring set having at least one entry node into an additional sub-ring in a second ring path, wherein the collateral ring set comprises a set of one or more collateral sub-rings from the perspective of the specified sub-ring, and comprises a specialized set of sub-rings in the tree of rings, wherein the specialized set of rings is unique for each ring, each collateral sub-ring node storing collateral sub-ring membership information and corresponding entry node information for each sub-ring, and wherein the second ring path forms a spine of sub-rings from the other sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the additional sub-ring being at the same specified sub-ring level as one of the sub-rings in the first ring path, the specified sub-ring level being below the root ring in the hierarchical tree of rings; and an act of using inter-ring communication to send the message from the further node to the additional sub-ring at the same specified sub-ring level so as to bypass the root ring, including; an act of the further node accessing the entry node into the additional sub-ring from the further node'"'"'s collateral ring set entry table; and an act of the further node sending the message to the entry node into the additional sub-ring, the message indicating the identified entry node is to resolve the message to the node having a node ID closest to an indicated destination node within the specified equivalence class. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
37. A computer program product for use at a computer system, the computer program product for implementing a method for sending inter-proximity communication in a federation infrastructure represented by a 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 below the root ring, the plurality of lower sub-ring levels defined in accordance with a plurality of different proximity category types corresponding to each lower sub-ring level,
wherein the root ring includes all the nodes in the linked list of nodes, and the plurality of lower sub-ring levels are arranged relative to one another within the hierarchical tree in accordance with a plurality of different proximity criteria representing the different user-defined proximity category types, each lower sub-ring level including a plurality of different sub-rings, each different sub-ring representing a corresponding different equivalence class of nodes based on assigned values for one or more of the plurality of different proximity criteria for the corresponding different proximity criteria category type for the lower sub-ring level, wherein nodes of the same equivalence class within the same lower sub-ring level have the same value for the plurality of proximity criteria in the same proximity category type corresponding to the same lower sub-ring level and nodes of different equivalence classes within the same lower sub-ring level have at least one different value for the plurality of proximity criteria in the same proximity category type corresponding to the same lower sub-ring level, and wherein nodes within the same equivalence class use intra-proximity communication to communicate between one another and nodes within different equivalence classes use inter-proximity communication to communicate between one another, the computer program product comprising one or more computer storage devices having stored thereon computer-executable instructions that, when executed by a processor, cause a receiving node to perform the following: -
receive a message at a first sub-ring; determine a node having membership in the first sub-ring is to send a message to another sub-ring, wherein the node is a member of the root ring and a plurality of sub-rings in a plurality of lower sub-ring levels based on the node matching different proximity criteria in different user-defined proximity category types, including (i) the first sub-ring representing a first equivalence class in a first proximity category type corresponding to a first lower sub-ring level, the first sub-ring being one of a plurality of sub-rings in the lower sub-ring level arranged within the tree hierarchy based on the first user defined proximity category type and (ii) a second sub-ring representing a second equivalence class in a second proximity category type that is different from the first proximity category type, the second proximity category type corresponding to a second lower sub-ring level, the second sub-ring being one of a plurality of sub-rings in the second sub-ring level, the second sub-ring level arranged between the first lower sub-ring level and the root ring within the tree hierarchy based on the second user-defined proximity category type, the first and second sub-rings in each of the one or more other sub-ring levels indicative of a first ring path forming a spine of sub-rings from the first sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the node storing separate routing information for the root ring, the first sub-ring, and a sub-ring in each of one or more other sub-ring levels including the second sub-ring, the routing information used by the node to determine membership in the root ring and in each sub-ring, and wherein the other sub-ring represents another different equivalence class, the other sub-ring being a collateral sub-ring of at least one specified sub-ring in the ring path, the first equivalence class and the other different equivalence class having at least one differing value for a proximity criteria, collateral sub-rings comprising a specialized type of rings including peer rings of the specified sub-ring and peer rings of the specified ring'"'"'s ancestor rings, the collateral sub-ring of the specified sub-ring comprising a collateral sub-ring of nodes included in the specified sub-ring; use intra-ring communication within the first sub-ring to identify a further node with a collateral ring set having an entry node into an additional sub-ring in a second ring path, wherein the collateral ring set comprises a set of one or more collateral sub-rings from the perspective of the specified sub-ring and comprises a specialized set of sub-rings in the tree of rings, wherein the specialized set of rings is unique for each ring, each collateral sub-ring node storing collateral sub-ring membership information and corresponding entry node information for each sub-ring, and wherein the second ring path forms a spine of sub-rings from the other sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the additional sub-ring being at the same specified sub-ring level as one of the sub-rings in the first ring path, the specified sub-ring level being below the root ring in the hierarchical tree of rings; use inter-ring communication to send the message from the further node to the additional sub-ring at the same specified sub-ring level so as to bypass the root ring, including; a further node accessing the entry node into the additional sub-ring from the further node'"'"'s collateral ring set entry table; and the further node sending the message to entry node into the additional sub-ring. - View Dependent Claims (38, 39)
-
-
40. A computer program product for use at a computer system, the computer program product for implementing a method for sending inter-proximity communication in a federation infrastructure represented by a 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 below the root ring, the plurality of lower sub-ring levels define in accordance with a plurality of different user-defined proximity category types corresponding to each lower sub-ring level,
wherein the root ring includes all the nodes in the linked list of nodes, and the plurality of lower sub-ring levels are arranged relative to one another within the hierarchical tree in accordance with a plurality of different proximity criteria representing the different user-defined proximity category types, each lower sub-ring level including a plurality of different sub-rings, each different sub-ring representing a corresponding different equivalence class of nodes based on assigned values for one or more of the plurality of different proximity criteria for the corresponding different proximity criteria category type for the lower sub-ring level, wherein nodes 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 in the same proximity category type corresponding to the same lower sub-ring level and nodes of different equivalence classes within the same lower sub-ring level have at least one different value for the plurality of different proximity criteria in the same proximity category type corresponding to the same lower sub-ring level, and wherein nodes within the same equivalence claims use intra-proximity communication to communicate between one another and nodes within different proximity classes use inter-proximity communication to communicate between one another, the computer program product comprising one or more computer storage devices having stored thereon computer-executable instruction that, when executed by a processor, cause a node to perform the following: -
determine an originating node in a sub-ring intends to route a message to a destination node closest to a given node ID within another sub-ring, wherein the sub-ring represents one equivalence class and the other sub-ring representing a specified equivalence class, the node not being a member of the other sub-ring, wherein inter-proximity communication is used to send the message to the specified equivalence class, the specified equivalence class identified from values of one or more of the plurality of different proximity criteria corresponding to the message, wherein the sub-ring is included in a first ring path forming a spine of sub-rings from the sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, each sub-ring in the first ring path corresponding to a different sub-ring level, including at least a first sub-ring level defined by a first proximity criteria category type and a second sub-ring level defined by a second, different, proximity criteria category type, the node storing separate routing information for the root ring, the sub-ring, and at least one other sub-ring between the sub-ring and the root ring, the routing information used by the node to determine membership in the root ring and in each sub-ring, and wherein the sub-ring included in the first ring path comprises a collateral sub-ring collateral sub-rings comprising a specialized type of ring comprising peer rings of the specified sub-ring and peer rings of the specified ring'"'"'s ancestor rings, the collateral sub-ring of the specified sub-ring comprises a collateral sub-ring of those nodes included in the specified sub-ring; using intra-ring communication within the sub-ring to identify a further node with a collateral ring set having at least one entry node into an additional sub-ring in a second ring path, wherein the collateral ring set comprises a set of one or more collateral sub-rings from the perspective of the specified sub-ring, and comprises a specialized set of sub-rings in the tree of rings, wherein the specialized set of rings is unique for each ring, each collateral sub-ring node storing collateral sub-ring membership information and corresponding entry node information for each sub-ring, and wherein the second ring path forms a spine of sub-rings from the other sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the additional sub-ring being at the same specified sub-ring level as one of the sub-rings in the first ring path, the specified sub-ring level being below the root ring in the hierarchical tree of rings; and using inter-ring communication to send the message from the further node to the additional sub-ring at the same specified sub-ring level so as to bypass the root ring, including; access, at the further node, the entry node into the additional sub-ring from the further node'"'"'s collateral ring set entry table; and send the message from the further node to the entry node into the additional sub-ring, the message indicating the identified entry node is to resolve the message to the node which has a node ID closest to an indicated destination node within the specified equivalence class. - View Dependent Claims (41, 42)
-
Specification