Broadcasting communication within a rendezvous federation
First Claim
1. At a computer system, a method for broadcasting a message within a sub-ring of nodes included 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 root ring including all the nodes in the linked list of nodes, the plurality of lower sub-ring levels arranged relative to one another within the hierarchical tree in accordance with a plurality of different proximity criteria, each lower sub-ring level in the hierarchical tree of rings including a plurality of different sub-rings, each different sub-ring within each lower sub-ring level representing a corresponding different equivalence class of nodes respectively based on assigned values for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree, 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 used to arrange the lower sub-ring within the hierarchical tree, 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, the method comprising:
- an act of a node within hierarchical tree of rings accessing a message, the node having membership in a sub-ring, the sub-ring being one of a plurality of sub-rings at a lower sub-ring level arranged within the tree hierarchy based on the plurality of proximity criteria, membership in the sub-ring also indicative of membership in other sub-rings in each of one or more other sub-ring levels between the lower sub-ring level and the root ring, the sub-rings in each of the one or more other sub-ring levels indicative of a ring path forming a spine of sub-rings the node is a member of from the sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the message for delivery to a range of nodes within a specified sub-ring the node is a member of;
an act of the node accessing a routing table for the node, the routing table including a plurality of routing partner nodes for each sub-ring in the spine of sub-rings, including the specified sub-ring;
an act of the node broadcasting the message within the specified sub-ring in a manner that distributes the resource burden for broadcasting the message across a plurality of nodes that are members of the specified sub-ring, including;
an act of the node partitioning the range of nodes in the specified sub-ring into a plurality of sub ranges, including at least a first and second sub range;
an act of the node forwarding the message along with an indication of first sub ranges to a first routing partner node within the first sub range; and
an act of the node forwarding the message along with an indication of the second sub range to a second routing partner node within the second sub range.
2 Assignments
0 Petitions
Accused Products
Abstract
The present invention extends to methods, systems, and computer program products for broadcasting communication within a rendezvous federation. Embodiments of the invention include inter-ring and intra-ring communication. Inter-ring communication includes sending a message to destination rings included in a node'"'"'s Collateral Ring Set entry table. When a node identifies a destination ring that has not yet received a message, the node can send a ring notification message. The ring notification message propagates towards a publishing node until a responsible node in the message path to the publishing node is identified. The responsible node updates its entry table to include the ring and forwards the message to the destination ring. Intra-ring communication can include recursively partitioning ranges of nodes within a ring and forwarding the message to nodes included the partitioned ranges.
-
Citations
35 Claims
-
1. At a computer system, a method for broadcasting a message within a sub-ring of nodes included 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 root ring including all the nodes in the linked list of nodes, the plurality of lower sub-ring levels arranged relative to one another within the hierarchical tree in accordance with a plurality of different proximity criteria, each lower sub-ring level in the hierarchical tree of rings including a plurality of different sub-rings, each different sub-ring within each lower sub-ring level representing a corresponding different equivalence class of nodes respectively based on assigned values for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree, 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 used to arrange the lower sub-ring within the hierarchical tree, 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, the method comprising:
-
an act of a node within hierarchical tree of rings accessing a message, the node having membership in a sub-ring, the sub-ring being one of a plurality of sub-rings at a lower sub-ring level arranged within the tree hierarchy based on the plurality of proximity criteria, membership in the sub-ring also indicative of membership in other sub-rings in each of one or more other sub-ring levels between the lower sub-ring level and the root ring, the sub-rings in each of the one or more other sub-ring levels indicative of a ring path forming a spine of sub-rings the node is a member of from the sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the message for delivery to a range of nodes within a specified sub-ring the node is a member of; an act of the node accessing a routing table for the node, the routing table including a plurality of routing partner nodes for each sub-ring in the spine of sub-rings, including the specified sub-ring; an act of the node broadcasting the message within the specified sub-ring in a manner that distributes the resource burden for broadcasting the message across a plurality of nodes that are members of the specified sub-ring, including; an act of the node partitioning the range of nodes in the specified sub-ring into a plurality of sub ranges, including at least a first and second sub range; an act of the node forwarding the message along with an indication of first sub ranges to a first routing partner node within the first sub range; and an act of the node forwarding the message along with an indication of the second sub range to a second routing partner node within the second sub range. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. At a computer system, a method for broadcasting a message to one or more sub-rings of nodes 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 root ring including all the nodes in the linked list of nodes, the plurality of lower sub-ring levels arranged relative to one another within the hierarchical tree in accordance with a plurality of different proximity criteria, each lower sub-ring level in the hierarchical tree of rings including a plurality of different sub-rings, each different sub-ring within each lower sub-ring level representing a corresponding different equivalence class of nodes respectively based on assigned values for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree, 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 used to arrange the lower sub-ring within the hierarchical tree, 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, the method comprising:
-
an act of a node accessing a message that is to be broadcast to one or more destination sub-rings in the federation infrastructure, the node having membership in a specified sub-ring, the specified sub-ring being one of a plurality of sub-rings at a lower sub-ring level arranged within the tree hierarchy based on the plurality of proximity criteria, membership in the specified sub-ring also indicative of membership in other sub-rings in each of one or more other sub-ring levels between the lower sub-ring level and the root ring, the sub-rings in each of the one or more other sub-ring levels indicative of a ring path forming a spine of sub-rings the node is a member of from the specified sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the one or more destination sub-rings being collateral sub-rings relative to the specified sub-ring within the hierarchical tree of rings, a collateral sub-ring being one of;
a peer sub-ring to the specified sub-ring or a peer sub-ring to another sub-ring in the spine of sub-rings;an act of the node accessing an entry table for the node, the entry table containing any known entry nodes into the one or more destination sub-rings; an act of the current node constructing broadcast control information including a reached ring list identifying any destination sub-rings that had known entry nodes in the entry table, a responsible ring indicator indicating a specified sub-ring the current node is responsible for, and a parent entry node indicator indicating a parent entry node that was the last entry node to access the message before the node accessed the message; and an act of the node sending inter-ring communication that includes the message and the broadcast control information to an entry node into at least one of the destination collateral sub-rings to propagate the message for further intra-ring broadcasting within the at least one of the destination collateral sub-rings. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
29. At a computer system, a method for broadcasting a message between a plurality of sub-rings 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 root ring including all the nodes in the linked list of nodes, the plurality of lower sub-ring levels arranged relative to one another within the hierarchical tree in accordance with a plurality of different proximity criteria, each lower sub-ring level in the hierarchical tree of rings including a plurality of different sub-rings, each different sub-ring within each lower sub-ring level representing a corresponding different equivalence class of nodes respectively based on assigned values for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree, 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 used to arrange the lower sub-ring within the hierarchical tree, 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, the method comprising:
-
an act of a node receiving a message and associated broadcast control information, the message to be broadcast to one or more destination sub-rings in the hierarchical tree of rings, the node having membership in a sub-ring, the sub-ring being one of a plurality of sub-rings at a lower sub-ring level arranged within the tree hierarchy based on the plurality of proximity criteria, membership in the sub-ring also indicative of membership in other sub-rings in each of one or more other sub-ring levels between the lower sub-ring level and the root ring, the sub-rings in each of the one or more other sub-ring levels indicative of a ring path forming a spine of sub-rings the node is a member of from the sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the broadcast control information including a reached ring list indicating destination sub-rings that the message has already been considered to have reached and a parent entry node indicator indicating a parent entry node that was the last entry node to access the message; an act of the node accessing a corresponding entry node table that identifies entry nodes for one or more collateral sub-rings in the collateral ring set (“
CRS”
) of the sub-ring, each collateral sub-ring being one of;
a peer sub-ring to the sub-ring or a peer sub-ring to another sub-ring in the spine of sub-rings;an act of the node identifying at least one destination sub-ring in the receiving node'"'"'s collateral ring set (“
CRS”
) that does not appear to have received the message according to information in the reached ring list;an act of the node sending the message to any identified destination rings the node is responsible for; and an act of the node identifying at least one destination sub-ring the node is not responsible for and that is not included in the reached ring list for the message; an act of the node sending a ring notification message back to the parent entry node, the ring notification message identifying the at least one destination sub-ring that the node is not responsible for and identifying at least one corresponding entry node for the at least one sub-destination ring that the node is not responsible for. - View Dependent Claims (30, 31, 32, 33, 34, 35)
-
Specification