Shared keep-alive and failure detection mechanism in distributed network

• US 9,338,050 B2
• Filed: 03/27/2012
• Issued: 05/10/2016
• Est. Priority Date: 03/27/2012
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Cai, Xuejun
• Primary Examiner(s): LY, ANH VU H
• Application Number:
  US14/384,008
• Publication Number:
  US 20150138948A1
• Time in Patent Office: 1,505 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04L 41/0813 characterised by the conditions triggering a change of settings
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route

Abstract

Node, computer readable medium and method for detecting a failed node in a structured network. The method includes assigning nodes of a neighboring set either to an active group or to a passive group, wherein the nodes of the neighboring set are connected to a current node; instructing active nodes in the active group to send a keep-alive query to the current node, wherein a timing for sending the keep-alive query from the active nodes to the current node is controlled by the current node; instructing passive nodes to listen for a keep-alive query from the current node and to reply with a keep-alive query response to the current node; configuring the current node to reply with a keep-alive query response to the active nodes; and determining the failed node based on (i) the keep-alive query response received from the passive nodes and (ii) the keep-alive query sent by the active nodes. The current node is configured to not send the keep-alive query to the active nodes and the passive nodes are configured to not send a keep-alive query to the current node.

Claims

1. A method for detecting a failed node in a structured network, the method comprising:

assigning nodes of a neighboring set either to an active group or to a passive group, wherein the nodes of the neighboring set are connected to a current node;

instructing active nodes in the active group to send a keep-alive query to the current node, wherein a timing for sending the keep-alive query from the active nodes to the current node is controlled by the current node;

instructing passive nodes to listen for a keep-alive query from the current node and to reply with a keep-alive query response to the current node;

configuring the current node to reply with a keep-alive query response to the active nodes; and

determining the failed node based on (i) the keep-alive query response received from the passive nodes and (ii) the keep-alive query sent by the active nodes,

wherein the current node is configured to not send the keep-alive query to the active nodes and the passive nodes are configured to not send a keep-alive query to the current node.

2. The method of claim 1, further comprising:

maintaining at the current node an active list that includes only the active nodes and a passive list that includes only the passive nodes, wherein the active nodes and the passive nodes form the neighboring set of the current node.

3. The method of claim 1, further comprising:

determining that the failed node is a passive node if no keep-alive query response is received from the failed node in reply to the keep-alive query sent by the current node to the failed node.

4. The method of claim 1, further comprising:

determining that the failed node is an active node if no keep-alive query is received by the current node from the failed node at an expected time.

5. The method of claim 1, further comprising:

sending, from the current node, a keep-alive notification message to neighbor nodes of the failed node, wherein the keep-alive notification includes information that the failed node had failed.

6. The method of claim 5, further comprising:

maintaining a list with reachable neighbor nodes of the failed node,

wherein a reachable neighbor node is a node that replied to the current node in response to the keep-alive notification message.

7. The method of claim 6, further comprising:

maintaining a list with neighbor nodes of the failed node that are not reachable.

8. The method of claim 7, further comprising:

randomly selecting a predetermined number of nodes from the list of reachable neighbor nodes.

9. The method of claim 8, further comprising:

sending, from the current node, to the randomly selected reachable neighbor nodes the list with the unreachable neighbor nodes to be informed about the failed node.

10. The method of claim 1, further comprising:

removing the failed node from various tables or lists maintained by the current node.

11. A current node configured to detect a failed node in a structured network, the node comprising:

a processor configured to assign nodes of a neighboring set to either an active group or to a passive group, wherein the nodes of the neighboring set are connected to the current node; and

an interface configured to,

receive a keep-alive query from active nodes in the active group,

send a keep-alive query to passive nodes and receive a keep-alive query response from the passive nodes, and

send a keep-alive query response to the active nodes in response to the keep-alive query,

wherein the processor determines the failed node based on (i) the keep-alive query response received from the passive nodes and (ii) the keep-alive query sent by the active nodes, and

wherein the current node is configured to not send the keep-alive query to the active nodes.

12. The node of claim 11, wherein the processor is configured to not send a keep-alive query response to the passive nodes.

13. The node of claim 11, wherein the processor is further configured to:

maintain an active list that includes only the active nodes and a passive list that includes only the passive nodes, wherein the active nodes and the passive nodes form the neighboring set of the current node.

14. The node of claim 11, wherein the processor is further configured to:

determine that the failed node is a passive node if no keep-alive query response is received from the failed node in reply to the keep-alive query sent by the current node to the failed node, or

determine that the failed node is an active node if no keep-alive query is received by the current node from the failed node at an expected time.

15. The node of claim 11, wherein the processor is further configured to:

send a keep-alive notification message to neighbor nodes of the failed node.

16. The node of claim 15, wherein the processor is further configured to:

maintain a list with reachable neighbor nodes of the failed node,

wherein a reachable neighbor node is a node that replied to the current node in response to the keep-alive notification message.

17. The node of claim 16, wherein the processor is further configured to:

maintain a list with neighbor nodes of the failed node that are not reachable.

18. The node of claim 17, wherein the processor is further configured to:

randomly select a predetermined number of nodes from the list of reachable neighbor nodes.

19. The node of claim 18, wherein the processor is further configured to:

send to the randomly selected reachable neighbor nodes the list with the unreachable neighbor nodes to be informed about the failed node.

20. A non-transitory computer readable medium including computer executable instructions, wherein the instructions, when executed by a processor, implement a method for detecting a failed node in a structured network, the instructions comprising:

assigning nodes of a neighboring set either to an active group or to a passive group, wherein the nodes of the neighboring set are connected to a current node;

instructing active nodes in the active group to send a keep-alive query to the current node, wherein a timing for sending the keep-alive query from the active nodes to the current node is controlled by the current node;

instructing passive nodes to listen for a keep-alive query from the current node and to reply with a keep-alive query response to the current node;

configuring the current node to reply with a keep-alive query response to the active nodes; and

determining the failed node based on (i) the keep-alive query response received from the passive nodes and (ii) the keep-alive query sent by the active nodes,

wherein the current node is configured to not send the keep-alive query to the active nodes and the passive nodes are configured to not send a keep-alive query to the current node.