Automatic cluster join protocol

• US 6,965,957 B1
• Filed: 07/12/2002
• Issued: 11/15/2005
• Est. Priority Date: 07/12/2002
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3pardata Incorporated
• Inventors: Nguyen, Vy
• Primary Examiner(s): Dang, Khanh
• Application Number:
  US10/194,685
• Time in Patent Office: 1,222 Days
• Field of Search: 710/100, 710/123, 710300-304, 710240-244, 709220-222, 370/254, 370/257
• US Class Current: 710/100
• CPC Class Codes: G06F 2209/505 Clust
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources

Abstract

A method for new nodes to join a cluster in a serial sequence includes (a) a new node transmitting a first type of request to join the cluster and (b) the new node determining if it has to back off the first type of request. The new node has to back off if (1) it has received a second type of request to join the cluster from another new node, (2) it has received the first type of request with a higher sequence number from another new node, (3) it has received the first type of request with a lower node number from another new node, or (4) a member node of the cluster is in a busy state. The new node transmits the first type of request, receives the first type of request, and receives the second type of request through primary links to the new nodes and member nodes of the cluster.

Claims

1. A method for new nodes to join a cluster in a serial sequence, comprising:

transmitting by a new node a first type of request to join the cluster;

determining by the new node if it has to back off the first type of request;

if the new node does not have to back off, determining by the new node if it has received votes from all member nodes of the cluster within a time period;

if the new node has received the votes from all the member nodes, transmitting by the new node a second type of request to join the cluster;

determining by the new node if connectivity is complete among the member nodes and the new node;

if the connectivity is complete, integrating by the new node and the member nodes into the cluster.

2. The method of claim 1, wherein the new node receives the votes and transmits the second type of request through primary links with the member nodes of the cluster.

3. The method of claim 1, wherein said determining by the new node if connectivity is complete among the member nodes and the new node comprises:

transmitting by the new node a local view of a membership to the member nodes;

receiving by the new node local views of the membership from the member nodes;

constructing by the new node a global view of the membership from the local view and the local views of the member node;

determining by the new node if all the member nodes and the new node are connected from the global view of the membership.

4. The method of claim 3, wherein the new node transmits the local view and receives the local views through primary links with the member nodes.

5. The method of claim 1, further comprising transmitting by the new node a first type of signal indicating it is a member node.

6. The method of claim 5, further comprising transmitting by the new node a second type of signal indicating the new node is panicking when the new node panics.

7. The method of claim 6, wherein the new node transmits the first type of signal and the second type of signal through backup links with the member nodes.

8. The method of claim 1, wherein the new node has to back off upon detecting an event selected from the group consisting of:

(1) the new node has received a second type of request to join the cluster from another node, (2) another node has transmitted the first type of request with a higher sequence number, (3) another node has transmitted the first type of request with a lower node number, and (4) a member node of the cluster is in a busy state.

9. A method for new nodes to join a cluster in a serial sequence, comprising:

(a) transmitting by a new node a first type of request to join the cluster;

(b) determining by the new node if it has to back off the first type of request;

(c) if the new node does not have to back off, determining by the new node if it has received at least one vote from member nodes of the cluster within a time period;

(d) if the new node has not received at least one vote from the member nodes within the time period, determining by the new node if the cluster has any member nodes;

(e) if the cluster has member nodes, repeating actions (a) and (b);

(f) if the cluster does not have any member nodes, becoming a master node by the new node.

10. The method of claim 9, wherein the new node receives the at least one vote through one primary link with one member node of the cluster.

11. The method of claim 9, wherein in the new node determines if the cluster has any member nodes by detecting a signal on one backup link with another node, the signal indicating the cluster has at least one member code.

12. The method of claim 9, wherein the new node has to back off upon detecting an event selected from the group consisting of (1) the new node has received a second type of request to join the cluster from another node, (2) another node has transmitted the first type of request with a higher sequence number, (3) another node has transmitted the first type of request with a lower node number, and (4) a member node of the cluster is in a busy state.

13. A method for new nodes to join a cluster in a serial sequence, comprising:

transmitting by a new node a first type of request to join the cluster;

determining by the new node if it has to back off the first type of request;

transmitting by the new node a first type of signal indicating it is a new node;

incrementing by the new node a signal counter if it is receiving a second type of signal indicating another node is a member node;

decrementing by the node the signal counter if it is receiving a third type of signal indicating another node is panicking;

transmitting by the node a fourth type of signal indicating the cluster has at least one member node if the signal counter is greater than zero;

transmitting by the node the first type of signal if the signal counter is equal to zero.

14. The method of claim 13, wherein the new node transmits the first type of signal, receives the second type of signal, receives the third type of signal, and transmits the fourth type of signal through backup links with the member nodes.

31. The method of claim 13, wherein the new node has to back off upon detecting an event selected from the group consisting of (1) the new node has received a second type of request to join the cluster from another node, (2) another node has transmitted the first type of request with a higher sequence number, (3) another node has transmitted the first type of request with a lower node number, and (4) a member node of the cluster is in a busy state.

15. A method for a new node to communicate with member nodes of a cluster, comprising:

transmitting by the new node a fast type of signal indicating it is a new node;

incrementing by the new node a signal counter if it is receiving a second type of signal indicating another node is a member node;

decrementing by the new node the signal counter if it is receiving a third type of signal indicating another node is panicking;

transmitting by the new node a fourth type of signal indicating the cluster has at least one member node if the signal counter is greater than zero;

transmitting by the new node the first type of signal if the signal counter is equal to zero.

16. The method of claim 15, wherein the new node transmits the first type of signal, receives the second type of signal, receives the third type of signal, and transmits the fourth type of signal through backup links with the member nodes.

17. The method of claim 16, further comprising:

(a) transmitting by the new node a first type of request to join the cluster, and

(b) determining by the new node if it has to back off the first type of request.

18. The method of claim 17, wherein the new node transmits the first type of request through primary links with the member nodes.

19. The method of claim 17, wherein the new node has to back off if (1) it has received a second type of request to join the cluster from another node, (2) another node has transmitted the first type of request with a higher sequence number, (3) another node has transmitter the first type of request with a lower node number, or (4) a member node of the cluster is in a busy state.

20. The method of claim 19, wherein the member node is in a busy state if (1) it is integrating into the cluster, (2) it is validating another member node, or (3) it is being validated by other member nodes.

21. The method of claim 17, further comprising:

(c) if the new node does not have to back off, determining by the new node if it has received votes from all member nodes within a time period;

(d) if the new node has received the votes from all the member nodes, transmitting by the new node a second type of request to join the cluster;

(e) determining by the new node if connectivity is complete among the member nodes and the new node;

(f) if the connectivity is complete, integrating by the new node and the member nodes into the cluster.

22. The method of claim 21, wherein the new node receives the votes and transmits the second type of request through primary links with other nodes including the member nodes of the cluster.

23. The method of claim 21, wherein said determining by the new node if connectivity is complete among the member nodes and the new node comprises:

transmitting by the new node a local view of a membership to the member nodes;

receiving by the new node local views of the membership from the member nodes;

constructing by the new node a global view of the membership from the local view and the local views of the member node;

determining by the new node if all the member nodes and the new node are connected from the global view of the membership.

24. The method of claim 23, wherein the new node transmits the local view and receives the local views through primary links with the member nodes.

25. The method of claim 23, further comprising transmitting by the new node the second type of signal to indicate it is a member node.

26. The method of claim 25, further comprising transmitting by the now node the third type of signal to indicate it is panicking.

27. The method of claim 26, wherein the new node transmits the second type of signal and the third type of signal through backup links with the member nodes.

28. The method of claim 17, further comprising:

(c) if the new node does not have to back off, determining by the new node if it has received at least one vote from member nodes within a time period;

(d) if the new node has not received at least one vote from the member nodes within the time period, determining by the new node if the cluster has any member nodes;

(e) if the cluster has member nodes, repeating actions (a) and (b);

(f) if the cluster does not have any member nodes, becoming a master node by the new node.

29. The method of claim 28, wherein the new node receives the at least one vote through one primary link with one member node of the cluster.

30. The method of claim 29, wherein the new node determines if the cluster has any member nodes by detecting the fourth type of signal on one backup link with another node.