System and method for automatic election of a representative node within a communications network with built-in redundancy

• US 6,363,416 B1
• Filed: 08/28/1998
• Issued: 03/26/2002
• Est. Priority Date: 08/28/1998
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Iverson, Tamara J., Naeimi, Ramin
• Primary Examiner(s): Burgess, Glenton B.
• Assistant Examiner(s): FIELDS, KENNETH WAYNE
• Application Number:
  US09/141,829
• Time in Patent Office: 1,306 Days
• Field of Search: 709/208, 709/209, 709/229, 709/225, 709/226, 375/356, 370/85.3, 370/445, 370/60, 370/943, 370/260, 364/200, 395/200.39
• US Class Current: 709/209
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 41/30 Decision processes by autonomous network management units using voting and bidding

Abstract

A system and method for automatic election a representative node within a communication network with built-in redundancy. In a communication network where data is distributed from a central location to multiple nodes, the present invention enables one of the nodes to be automatically identified as a master of the nodes for retrieving data from the central location and then transmitting the data to all peer nodes interested in receiving the data. No manual intervention or pre-operation designation of a master is required within the present invention. As such, repetitive requests for information by individual nodes are eliminated, and the volume of network traffic is thereby significantly localized. Hence, the performance of the network is greatly enhanced. Furthermore, rather than arbitrarily preassigning particular node(s) to serve as a master, the present invention provides an automated process by which a new master is dynamically elected whenever an existing master fails or none exists. Therefore, the present invention provides built-in redundancy which greatly improves the reliability of network communications.

Claims

1. A computer implemented method for arbitrating among nodes within a communication network having a plurality of client nodes communicatively coupled together, said method comprising the steps of:

a) a first client node broadcasting a first message to said nodes in response to an absence of master node-initiated messages during a predetermined time period, said first message for identifying a viable master node in said communication network, said first client node initiating an election process for dynamically electing a new master node from among said plurality of client nodes only when no response is received from an existing master node to said first message, said election process comprising the steps of;

a1) said first client node broadcasting a first master negotiate request (MNR) message to said plurality of client nodes;

a2) provided that said first client node does not receive a message in response to said MNR message from a second client node, said first client node asserting itself as said new master node; and

a3) provided that said first client node does receive a message in response to said MNR message from a second client node, comparing resources of said first client node to resources of said second client node, wherein results of said comparing are used to select said new master node; and

b) in response to said step a) wherein said new master node is selected, said new master node periodically broadcasting heartbeat messages to said plurality of client nodes.

2. The method as recited in claim 1 wherein said step b) is performed whenever a heartbeat timeout period expires.

3. The method as recited in claim 2 further comprising the step of:

c) said plurality of client nodes monitoring to receive said heartbeat messages within said heartbeat timeout period to ensure that said new master node is viable.

4. The method as recited in claim 3 wherein said step a1) comprises the step of said first client node broadcasting said first MNR message to said plurality of client nodes provided that said first client node does not receive a master discovery response (MDResp) message within a certain period of time.

5. The method as recited in claim 3 wherein said steps a2) and a3) further comprise the steps of:

provided that said first client node does not receive a first MC message and does not receive a second MNR message from said second client node within a negotiation timeout period after broadcasting said first MNR message, said first client node broadcasting a second MC message to said plurality of client nodes; and

provided that said first client node receives at least one of said first MC message and said second MNR message from said second client node within said negotiation timeout period after broadcasting said first MNR message;

said first client node broadcasting said second MC message to said plurality of client nodes provided that said first client is more resourceful than said second client node; and

said first client node recognizing said second client node as said new master node provided that said second client is more resourceful than said first client node.

6. The method as recited in claim 3 wherein said step a) further comprises the step of:

said existing master node monitoring to respond to said first message from one of said plurality of client nodes.

7. The method as recited in claim 6 further comprising the step of:

soliciting a response from said existing master node provided that one of said plurality of client nodes is powered on.

8. The method as recited in claim 6 further comprising the step of:

said plurality of client nodes monitoring to receive a master claim (MC) message to update the identity of said new master node.

9. A computer system coupled to a communication network having a plurality of client nodes communicatively coupled together, wherein said computer system is one of said plurality of client nodes and comprises a processor coupled to a bus and a memory unit coupled to said bus, said memory unit having stored therein instructions that when executed implement a method for arbitrating among said plurality of client nodes, said method comprising the steps of:

a) a first client node broadcasting a first message to said nodes in response to an absence of master node-initiated messages during a predetermined time period, said first message for identifying a viable master node in said communication network, said first client node initiating an election process for dynamically electing a new master node from among said plurality of client nodes only when no response is received from an existing master node to said first message, said election process comprising the steps of;

a1) said first client node broadcasting a first master negotiate request (MNR) message to said plurality of client nodes;

a2) provided that said first client node does not receive a message in response to said MNR message from a second client node, said first client node asserting itself as said new master node; and

a3) provided that said first client node does receive a message in response to said MNR message from a second client node, comparing resources of said first client node to resources of said second client node, wherein results of said comparing are used to select said new master node; and

b) in response to said step a) wherein said new master node is selected, said master node periodically broadcasting heartbeat messages to said plurality of client nodes.

10. The computer system as recited in claim 9 wherein said step b) of said method is performed whenever a heartbeat timeout period expires.

11. The computer system as recited in claim 10 wherein said method further comprises the step of:

c) said plurality of client nodes monitoring to receive said heartbeat messages within said heartbeat timeout period to ensure that said new master node is viable.

12. The computer system as recited in claim 11 wherein said step a1) of said method comprises the step of said first client node broadcasting said first MNR message to said plurality of client nodes provided that said first client node does not receive a master discovery response (MDResp) message within a certain period of time.

13. The computer system as recited in claim 11 wherein said steps a2) and a3) of said method further comprise the steps of:

provided that said first client node does not receive a first MC message and does not receive a second MNR message from said second client node within a negotiation timeout period after broadcasting said first MNR message, said first client node broadcasting a second MC message to said plurality of client nodes; and

provided that said first client node receives at least one of said first MC message and said second MNR message from said second client node within said negotiation timeout period after broadcasting said first MNR message;

said first client node broadcasting said second MC message to said plurality of client nodes provided that said first client is more resourceful than said second client node; and

said first client node recognizing said second client node as said new master node provided that said second client is more resourceful than said first client node.

14. The computer system as recited in claim 11 wherein said method further comprises the step of:

said existing master node monitoring to respond to said first message from one of said plurality of client nodes.

15. The computer system as recited in claim 14 wherein said method further comprises the step of:

soliciting a response from said existing master node provided that one of said plurality of client nodes is powered on.

16. The computer system as recited in claim 14 wherein said method further comprises the step of:

said plurality of client nodes monitoring to receive a master claim (MC) message to update the identity of said master new node.