Shared keep-alive and failure detection mechanism in distributed network

Patent metadata

Field	Value
Publication number	US-9338050-B2
Application number	US-201214384008-A
Country	US
Kind code	B2
Filing date	Mar 27, 2012
Priority date	Mar 27, 2012
Publication date	May 10, 2016
Grant date	May 10, 2016

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.

First claim

What is claimed is:

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.

Assignees

• Cai Xuejun
• Ericsson Telefon Ab L M

Inventors

• Cai Xuejun

Classifications

• H04L43/10

  Active monitoring, e.g. heartbeat, ping or trace-route · CPC title

• H04L41/0813

  characterised by the conditions triggering a change of settings · CPC title

• H04L43/0817 Primary

  by checking functioning · CPC title

• H04L41/0654 Primary

  using network fault recovery (ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437) · CPC title