Master node selection in clustered node configurations

• US 6,950,855 B2
• Filed: 01/18/2002
• Issued: 09/27/2005
• Est. Priority Date: 01/18/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sampathkumar, Govindaraj
• Primary Examiner(s): Donaghue, Larry D.
• Assistant Examiner(s): Refai, Ramsey
• Application Number:
  US10/052,551
• Publication Number:
  US 20030140108A1
• Time in Patent Office: 1,348 Days
• Field of Search: 709/208, 709/209, 709/223, 709/221, 370/254, 370901-911
• US Class Current: 709/209
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method and system for selecting master nodes to manage a target node group in a computer network having multiple nodes and overlapping node groups. The system includes determining a hamming distance for node pairs within the network. The node pair includes two node pair members and the hamming distance is the number of node groups the node pair members do not share in common. A participation index for nodes within the network is determined at a determining operation. The participation index is the number of node groups the node belongs to. An availability potential for node pairs is also determined. The availability potential is the sum of the participation indexes of the node pair members subtracted by the hamming distance of the node pair. An optimal combination of node pairs is found by searching for the maximum total availability potential for the network. A master node pair for the target node group is selected from the optimal combination of node pairs. If a master node pair does not exist for the target node group, a master node belonging to the target node group is selected for the target group.

Claims

1. A method for selecting master nodes to manage a target node group in a computer network having multiple nodes and node groups, the method comprising:

determining a hamming distance for node pairs within the network, each of the node pairs having two node pair members and the hamming distance being the number of node groups the node pair members do not share in common;

determining a participation index for nodes within the network, the participation index being the number of node groups a node belongs to;

determining an availability potential for the node pairs, the availability potential being the sum of the participation indexes of the node pair members subtracted by the hamming distance of the node pair;

finding an optimal combination of node pairs, the optimal combination of node pairs having a maximum total availability potential for the network;

selecting a master node pair for the target node group, the master node pair being the node pair from the optimal combination of node pairs having both node pair members belonging to the target node group; and

if the master node pair does not exist for the target node group, selecting a master node for the target node group, the master node being the node belonging to the target node group.

2. The method of claim 1, wherein either of the node pair members of the master node pair selected for the target node group are not master nodes for another node group with a third node.

3. The method of claim 1, wherein selecting a master node pair for the target node group further includes if the optimal combination of node pairs contains more than one node pair having both node pair members belonging to the target node group, selecting the node pair with the smallest sum of the participation indexes of the node pair members.

4. The method of claim 1, wherein selecting a master node for the target node group further includes if more than one node belongs to the target node group, selecting the node with the smallest participation index.

5. The method of claim 1, wherein determining a hamming distance for node pairs within the network includes XORing the node pair members.

6. In a computer-readable medium having stored thereon a data structure for use in selecting master nodes to manage a target node group in a computer network having multiple nodes and overlapping node groups, the data structure comprising:

a hamming distance array containing, for node pairs in the network, the number of node groups node pair members do not share in common;

a participation index array containing, for nodes in the network, the number of node groups the node belongs to; and

an availability potential array containing, for node pairs in the network, the sum of the participation indexes of the node pair members subtracted by the hamming distance of the node pair.

7. The data structure of claim 6, wherein the hamming distance array is an n by n array, where n is the number of nodes in the network.

8. The data structure of claim 6, wherein the participation index array is a one by n array, where n is the number of nodes in the network.

9. The data structure of claim 6, wherein the availability potential array is an n by n array, where n is the number of nodes in the network.

10. The data structure of claim 6, further comprising a node group configuration array storing the relationships between each node and each node group in the network.

11. The data structure of claim 10, wherein the node group configuration array is an m by n array, where m is the number of node groups in the network and n is the number of nodes in the network.

12. The data structure of claim 10, wherein in the node group configuration array a “

1”

is used to signify the node belonging to the node group and a “

0”

is used to signify the node not belonging to the node group.

13. The data structure of claim 6, further comprising an optimal combination of node pairs, the optimal combination of node pairs being the combination of node pairs having a maximum total availability potential for the network.

14. The data structure of claim 6, further comprising a preferred order array listing a hierarchy of master node pairs for node groups in the network.

15. The data structure of claim 14, wherein the preferred order array further includes a hierarchy of master nodes for node groups in the network.

16. A computer program product embodied in a computer storage media comprising:

computer readable program codes coupled to the computer storage media for selecting master nodes to manage a target node group in a computer network having multiple nodes and node groups, the computer readable program codes comprising;

first computer readable program code configured to cause the program to determine a hamming distance for node pairs within the network, the node pair having two node pair members and the hamming distance being the number of node groups the node pair members do not share in common;

second computer readable program code configured to cause the program to determine a participation index for nodes within the network, the participation index being the number of node groups a node belongs to;

third computer readable program code configured to cause the program to determine an availability potential for each node pair, the availability potential being the sum of the participation indexes of the node pair members subtracted by the hamming distance of the node pair;

fourth computer readable program code configured to cause the program to find an optimal combination of node pairs, the optimal combination of node pairs having the maximum total availability potential for the network; and

fifth computer readable program code configured to cause the program to select a master node pair for the target node group, the master node pair being the node pair from the optimal combination of node pairs having both node pair members belonging to the target node group; and

if the master node pair does not exist for the target node group, sixth computer readable program code configured to cause the program to select a master node for the target node group, the master node being the node belonging to the target node group.

17. The computer program product of claim 16, wherein the computer storage media comprises a magnetic disk.

18. The computer program product of claim 16, wherein the computer storage media comprises an optical disk.

19. The computer program product of claim 16, wherein the computer storage media comprises a random access memory device.

20. A system for selecting master nodes to manage a target node group in a computer network having multiple nodes and node groups, the system comprising:

a computer storage media having stored thereon the following,

a hamming distance module for determining a hamming distance of node pairs within the network, each of the node pairs having two node pair members and the hamming distance being the number of node groups the node pair members do not share in common;

a participation index module for determining a participation index of nodes within the network, the participation index being the number of node groups a node belongs to;

an availability potential module for determining an availability potential of the node pairs, the availability potential being the sum of the participation indexes of the node pair members subtracted by the hamming distance of the node pair;

a search module for finding an optimal combination of node pairs, the optimal combination of node pairs having the maximum total availability potential for the network;

a first selection module for selecting a master node pair of the target node group, the master node pair being the node pair from the optimal combination of node pairs having both node pair members belonging to the target node group; and

a second selection module for selecting a master node for the target node group if the master node pair does not exist for the target node group, the master node being the node belonging to the target node group.

21. The system of claim 20, wherein the node pair members of the master node pair selected for the target node group are not master nodes for another node group with a third node.

22. The system of claim 20, wherein the first selection module further includes if the optimal combination of node pairs contains more than one node pair having both node pair members belonging to the target node group, selecting the node pair with the smallest sum of the participation indexes of the node pair members.

23. The system of claim 20, wherein the second selection module further includes if more than one node belongs to the target node group, selecting the node with the smallest participation index.

24. The system of claim 20, wherein the hamming distance module includes XORing the node pair members.

25. A method for selecting master nodes to manage a target node group in a computer network having multiple nodes and node groups, the method comprising:

determining a hamming distance for node pairs within the network, each of the node pairs having two node pair members and the hamming distance being the number of node groups the node pair members do not share in common;

finding an optimal combination of node pairs, the optimal combination of node pairs having a minimum total hamming distance for the network;

selecting a master node pair for the target node group, the master node pair being the node pair from the optimal combination of node pairs having both node pair members belonging to the target node group; and

if the master node pair does not exist for the target node group, selecting a master node for the target node group, the master node being the node belonging to the target node group.

26. The method of claim 25, wherein either of the node pair members of the master node pair selected for the target node group are not master nodes for another node group with a third node.

27. The method of claim 25, wherein selecting a master node pair for the target node group further includes:

determining a participation index for nodes within the network, the participation index being the number of node groups a node belongs to; and

if the optimal combination of node pairs contains more than one node pair having both node pair members belonging to the target node group, selecting the node pair with the smallest sum of the participation indexes of the node pair members.

28. The method of claim 25, wherein selecting a master node for the target node group further includes:

determining a participation index for nodes within the network, the participation index being the number of node groups a node belongs to; and

if more than one node belongs to the target node group, selecting the node with the smallest participation index.

29. The method of claim 25, wherein determining a hamming distance for node pairs within the network includes XORing the node pair members.