Back to results
US 2016/0105323 A1Published application
Node identification using clusters
AssigneeMicrosoft Corporation
InventorsBernhard Haeupler, Dahlia Malkhi
Life of this patent
Estimating the term…
Abstract
During an initialization phase, some nodes of a network form clusters. The nodes in a cluster share information with a leader node, which knows all of the nodes that each of the nodes in the cluster is aware of. During a growth phase, clusters are randomly activated or deactivated. The nodes of the activated clusters message randomly selected known nodes, asking the nodes to merge with the cluster. The nodes of deactivated clusters determine which activated cluster to join based on received messages. After the growth phase ends, the remaining clusters may merge to form a single cluster, and the list of nodes known to the leader of the single cluster may be shared as the list of all nodes on the network.
Claims20
A method comprising:
- determining that a number of nodes in a first cluster of a plurality of clusters is greater than a first threshold by a computing device, wherein each cluster comprises one or more nodes of a plurality of nodes, each node is assigned to one cluster, each node comprises a node identifier that identifies the node, each node comprises a cluster identifier that identifies the cluster that the node is assigned to, and each node comprises a list of the nodes of the plurality of nodes that the node is aware of;
- in response to determining that the number of nodes in the first cluster is greater than the first threshold:
- (a) activating or deactivating the first cluster by the computing device;
- and
- (b) while the first cluster is activated:
- instructing each node in the first cluster to select a first node from the list of nodes that the node is aware of by the computing device, wherein the first node is not in the first cluster;
- and
- instructing each node in the first cluster to send a message to the selected first node by the computing device, wherein the message includes the cluster identifier of the first cluster;
- receiving a request to identify the nodes of the plurality of nodes at the computing device;
- and
- in response to the request, providing the list of nodes associated with a node of the first cluster by the computing device.
8 more elements
A method comprising:
- (a) activating or deactivating a first cluster of a plurality of clusters by a computing device, wherein each cluster comprises one or more nodes of a plurality of nodes, each node is assigned to one cluster, each node comprises a node identifier that identifies the node, each node comprises a cluster identifier that identifies the cluster that the node is assigned to, and each node comprises a list of the nodes of the plurality of nodes that the node is aware of;
- (b) while the first cluster is activated:
- instructing each node in the first cluster to select a first node from the list of nodes that the node is aware of by the computing device;
- and
- instructing each node in the first cluster to send a message to the selected first node by the computing device, wherein the message includes the cluster identifier associated with the first cluster;
- (c) while the first cluster is deactivated:
- receiving cluster identifiers from one or more of the nodes in the first cluster by the computing device;
- selecting a cluster identifier from the received cluster identifiers by the computing device;
- and
- instructing each node in the first cluster to join the cluster identified by the selected cluster identifier by the computing device.
7 more elements
A system comprising:
- at least one computing device;
- a plurality of nodes, wherein each node comprises a node identifier that identifies the node, and each node comprises a list of the nodes of the plurality of nodes that the node is aware of;
- and
- a discovery engine adapted to:
- in an initialization phase, assign one or more nodes of the plurality of nodes to a cluster of a plurality of clusters, wherein each cluster comprises at least one node, and each node comprises a cluster identifier that identifies the cluster that the node is assigned to;
- and
- in a growth phase, grow one or more of the clusters by:
- randomly activating or deactivating each cluster of the plurality of clusters;
- for each activated cluster, instructing each node of the activated cluster to send a message to a randomly selected node from the list of nodes associated with the node of the activated cluster, wherein the message comprises the cluster identifier associated with the node of the activated cluster;
- and
- for each deactivated cluster, instructing each node of the deactivated cluster to join a cluster identified by a cluster identifier from a received message.
8 more elements
Dependencies are inferred from the claim text.