Establishing membership within a federation infrastructure
First Claim
1. At a joining node, the joining node including a processor and system memory, a method for establishing membership within 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 one or more lower levels of sub-rings, the root ring including all the nodes in the linked list of nodes, each of the one or more sub-rings including a subset of nodes from the linked list of nodes in accordance a plurality of proximity criteria, wherein any node included in a lower level sub-ring is also included in the root ring and is also included in any intermediate higher level sub-rings between the lower level sub-ring and the root ring, the method comprising:
- an act of sending a join message to a federation infrastructure, the join message including one or more proximity criteria from among the plurality of proximity criteria, the one or more proximity criteria indicating that the joining node is to be a member of one or more sub-rings in a path of sub-rings from a specified sub-ring to the root ring, the specified sub-ring representing a proximally equivalent set of nodes based on the one or more proximity criteria, the destination property of the join message being the ID of the joining node;
an act of receiving a join response message from a federation infrastructure node that processed the join message, the join response identifying any prospective predecessor nodes in the specified sub-ring and any prospective successor nodes in the specified sub-ring corresponding to the joining node based on the one or more proximity criteria;
an act of sending a sync request to any identified immediate predecessor nodes and any identified immediate successor nodes within the specified sub-ring;
an act of receiving a sync response message from any of the identified immediate predecessor nodes and any of the identified immediate successor nodes that processed the sync request within the specified sub-ring, the received sync responses indicating any neighborhood nodes of the predecessor nodes and any neighborhood nodes of the successor nodes that processed the sync request within the specified sub-ring; and
an act of the processor computing neighborhood nodes for the joining node within the specified sub-ring based on a summarized view of the join response message and any sync response messages.
2 Assignments
0 Petitions
Accused Products
Abstract
The present invention extends to methods, systems, and computer program products for establishing and maintaining membership within a federation infrastructure. A joining node submits a join message to an existing federation infrastructure. The federation infrastructure routes the join message to a processing node. The processing node facilitates identification of predecessor, successor, neighborhood, and routing nodes (for the joining node) within a ring of nodes. The joining node exchanges messages with identified nodes to obtain state information for the identified nodes and other nodes within the ring. Nodes periodically exchange state information, including state information for other nodes, such that state information for the ring is efficiently propagated to all nodes in the ring even when communication between some nodes is lost. Instance IDs, phase values, and freshness values are used to determine when state information is stale and/or is to be updated.
-
Citations
43 Claims
-
1. At a joining node, the joining node including a processor and system memory, a method for establishing membership within 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 one or more lower levels of sub-rings, the root ring including all the nodes in the linked list of nodes, each of the one or more sub-rings including a subset of nodes from the linked list of nodes in accordance a plurality of proximity criteria, wherein any node included in a lower level sub-ring is also included in the root ring and is also included in any intermediate higher level sub-rings between the lower level sub-ring and the root ring, the method comprising:
-
an act of sending a join message to a federation infrastructure, the join message including one or more proximity criteria from among the plurality of proximity criteria, the one or more proximity criteria indicating that the joining node is to be a member of one or more sub-rings in a path of sub-rings from a specified sub-ring to the root ring, the specified sub-ring representing a proximally equivalent set of nodes based on the one or more proximity criteria, the destination property of the join message being the ID of the joining node; an act of receiving a join response message from a federation infrastructure node that processed the join message, the join response identifying any prospective predecessor nodes in the specified sub-ring and any prospective successor nodes in the specified sub-ring corresponding to the joining node based on the one or more proximity criteria; an act of sending a sync request to any identified immediate predecessor nodes and any identified immediate successor nodes within the specified sub-ring; an act of receiving a sync response message from any of the identified immediate predecessor nodes and any of the identified immediate successor nodes that processed the sync request within the specified sub-ring, the received sync responses indicating any neighborhood nodes of the predecessor nodes and any neighborhood nodes of the successor nodes that processed the sync request within the specified sub-ring; and an act of the processor computing neighborhood nodes for the joining node within the specified sub-ring based on a summarized view of the join response message and any sync response messages. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35)
-
-
36. At a federation infrastructure, a method for a joining a node to establish membership within the 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 one or more lower levels of sub-rings, the root ring including all the nodes in the linked list of nodes, each of the one or more sub-rings including a subset of nodes from the linked list of nodes in accordance a plurality of proximity criteria, wherein any node included in a lower level sub-ring is also included in the root ring and is also included in any intermediate higher level sub-rings between the lower level sub-ring and the root ring, the method comprising:
-
an act of a receiving node in the federation infrastructure receiving a join message, the destination property of the join message being the ID of a joining node, the join message including one or more proximity criteria from among the plurality of proximity criteria, the one or more proximity criteria indicating that the node is to be a member of one or more sub-rings in a path of sub-rings from a specified sub-ring to the root ring, the specified sub-ring representing a proximally equivalent set of nodes based on the one or more proximity criteria; an act of routing the join message to a processing node having an ID numerically closer to the ID of the joining node than other nodes in the federation infrastructure, the processing node including a processor and system memory; an act of the processor at the processing node computing one or more predecessor nodes at least in the specified sub-ring and one or more successor nodes for the joining node at least in the specified sub-ring; an act of the processor at the processing node computing one or more routing nodes in the specified sub-ring for the joining node; and an act of sending a join response to the joining node, the join response identifying at least the computed predecessor nodes in the specified sub-ring and the computed successor nodes in the specified sub-ring to the joining node. - View Dependent Claims (37, 38, 39, 40, 41)
-
-
42. A computer program product for use at a joining node, the computer program product for implementing a method for establishing membership within 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 one or more lower levels of sub-rings, the root ring including all the nodes in the linked list of nodes, each of the one or more sub-rings including a subset of nodes from the linked list of nodes in accordance a plurality of proximity criteria, wherein any node included in a lower level sub-ring is also included in the root ring and is also included in any intermediate higher level sub-rings between the lower level sub-ring and the root ring, the computer program product comprising one or more computer-readable storage media having stored thereon computer-executable instructions that, when executed by a processor, cause the joining node to perform the following:
-
send a join message to a federation infrastructure, the join message including one or more proximity criteria from among the plurality of proximity criteria, the one or more proximity criteria indicating that the joining node is to be a member of one or more sub-rings in a path of sub-rings from a specified sub-ring to the root ring, the specified sub-ring representing a proximally equivalent set of nodes based on the one or more proximity criteria, the destination property of the join message being the ID of the joining node; receive a join response message from a federation infrastructure node that processed the join message, the join response identifying any prospective predecessor nodes in the specified sub-ring and any prospective successor nodes in the specified sub-ring corresponding to the joining node based on the one or more proximity criteria; send a sync request to any identified immediate predecessor nodes and any identified immediate successor nodes within the specified sub-ring; receive a sync response message from any of the identified immediate predecessor nodes and any of the identified immediate successor nodes that processed the sync request within the specified sub-ring, the received sync responses indicating any neighborhood nodes of the predecessor nodes and any neighborhood nodes of the successor nodes that processed the sync request within the specified sub-ring; and compute neighborhood nodes for the joining node within the specified sub-ring based on a summarized view of the join response message and any sync response messages.
-
-
43. A computer program product for use at a federation infrastructure, the computer program product for implementing a method for a joining a node to establish membership within the 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 one or more lower levels of sub-rings, the root ring including all the nodes in the linked list of nodes, each of the one or more sub-rings including a subset of nodes from the linked list of nodes in accordance a plurality of proximity criteria, wherein any node included in a lower level sub-ring is also included in the root ring and is also included in any intermediate higher level sub-rings between the lower level sub-ring and the root ring, the computer program product comprising one or more computer-readable storage media having stored thereon computer-executable instructions that, when executed by a processor, cause a processing node within the federation infrastructure to perform the following:
-
receive node in the federation infrastructure receiving a join message, the join message including one or more proximity criteria from among the plurality of proximity criteria, the one or more proximity criteria indicating that the node is to be a member of one or more sub-rings in a path of sub-rings from a specified sub-ring to the root ring, the specified sub-ring representing a proximally equivalent set of nodes based on the one or more proximity criteria, the destination property of the join message being the ID of a joining node; route the join message to a processing node having an ID numerically closer to the ID of the joining node than other nodes in the federation infrastructure; compute one or more predecessor nodes at least in the specified sub-ring and one or more successor nodes at least in the specified sub-ring for the joining node; compute one or more routing nodes in the specified sub-ring for the joining node; and send a join response to the joining node, the join response identifying at least the computed predecessor nodes in the specified sub-ring and the computed successor nodes in the specified sub-ring to the joining node.
-
Specification