Cumulative node heartbeat relay agents in constrained computer networks

• US 9,178,772 B2
• Filed: 06/25/2013
• Issued: 11/03/2015
• Est. Priority Date: 06/25/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Dasgupta, Sukrit, Vasseur, Jean-Philippe, Mermoud, Grgory
• Primary Examiner(s): Iqbal, Nadeem
• Application Number:
  US13/926,761
• Publication Number:
  US 20140379900A1
• Time in Patent Office: 861 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 43/0805 by checking availability
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: Y04S 40/00 Systems for electrical power generation, transmission, distribution or end-user application management characterised by the use of communication or information technologies, or communication or information technology specific aspects supporting them

Abstract

In one embodiment, a message instructing a particular node to act as a heartbeat relay agent is received at the particular node in a network. The particular node is selected to receive the message based on a centrality of the particular node. Heartbeat messages are then collected from child nodes of the particular node in the network. Based on the collected heartbeat messages, a heartbeat report is generated, and the report is transmitted to a collecting node in the network.

Claims

1. A method, comprising:

receiving, at a particular node in a network, a message instructing the particular node to act as a heartbeat relay agent, the particular node being selected to receive the message based on a centrality of the particular node;

collecting heartbeat messages from child nodes of the particular node in the network, the heartbeat message indicating a liveness of a corresponding child node;

generating a heartbeat report based on the collected heartbeat messages; and

transmitting the heartbeat report to a collecting node in the network.

2. The method as in claim 1, further comprising:

determining whether to indicate in the heartbeat report a list of child nodes from which a heartbeat message was received, or a list of child nodes from which a heartbeat message was not received; and

encoding the determined list in the heartbeat report.

3. The method as in claim 2, further comprising:

receiving, from the collecting node, a message instructing the particular node to indicate in the heartbeat report the list of child nodes from which a heartbeat message was received, or the list of child nodes from which a heartbeat message was not received.

4. The method as in claim 2, wherein the determining is based on at least one of:

i) a number of active child nodes, ii) a frequency of heartbeat message transmissions, iii) an amount of congestion in the network, iv) a topology of the network, v) a stability of the network, and vi) the centrality of the particular node.

5. The method as in claim 2, further comprising:

receiving a message indicating that a child node has migrated to another area of the network; and

removing the child node from the list upon receipt of the indication.

6. The method as in claim 2, when the heartbeat report includes the list of child nodes from which a heartbeat message was not received, further comprising:

removing a child node from the list when the child node has been included in the list for a number of consecutive transmissions which exceeds a predetermined threshold.

7. The method as in claim 1, wherein the particular node is one of a plurality of nodes instructed to act as heartbeat relay agents.

8. A method, comprising:

selecting a node in a network to act as a heartbeat relay agent based on a centrality of the node, the heartbeat relay agent collecting heartbeat messages from child nodes of the node, the heartbeat message indicating a liveness of a corresponding child node;

sending, to the node, a message instructing the node to act as the heartbeat relay agent;

receiving, from the node, a heartbeat report generated by the node based on the collected heartbeat messages; and

determining whether a particular child node is active or inactive based on the received heartbeat report.

9. The method as in claim 8, further comprising:

computing the centrality of the node based on at least one of;

i) a topology of the network, ii) an amount of congestion in the network, and iii) a stability of the network.

10. The method as in claim 8, further comprising:

sending, to the node, a message instructing the node to indicate in the heartbeat report a list of child nodes from which a heartbeat message was received, or a list of child nodes from which a heartbeat message was not received.

11. An apparatus, comprising:

one or more network interfaces that communicate with a network;

a processor coupled to the one or more network interfaces and configured to execute a process; and

a memory configured to store program instructions which contain the process executable by the processor, the process comprising;

receiving, at a particular node in the network, a message instructing the particular node to act as a heartbeat relay agent, the particular node being selected to receive the message based on a centrality of the node;

collecting heartbeat messages from child nodes of the particular node in the network, the heartbeat message indicating a liveness of a corresponding child node;

generating a heartbeat report based on the collected heartbeat messages; and

transmitting the heartbeat report to a collecting node in the network.

12. The apparatus according to claim 11, wherein the process further comprises:

determining whether to indicate in the heartbeat report a list of child nodes from which a heartbeat message was received, or a list of child nodes from which a heartbeat message was not received; and

encoding the determined list in the heartbeat report.

13. The apparatus according to claim 12, wherein the process further comprises:

receiving, from the collecting node, a message instructing the particular node to indicate in the heartbeat report the list of child nodes from which a heartbeat message was received, or the list of child nodes from which a heartbeat message was not received.

14. The apparatus according to claim 12, wherein the determining is based on at least one of:

i) a number of active child nodes, ii) a frequency of heartbeat message transmissions, iii) an amount of congestion in the network, iv) a topology of the network, v) a stability of the network, and vi) the centrality of the node.

15. The apparatus according to claim 12, wherein the process further comprises:

receiving a message indicating that a child node has migrated to another area of the network; and

removing the child node from the list upon receipt of the indication.

16. The apparatus according to claim 12, when the heartbeat report includes the list of child nodes from which a heartbeat message was not received, further comprising:

removing a child node from the list when the child node has been included in the list for a number of consecutive transmissions which exceeds a predetermined threshold.

17. The apparatus according to claim 11, wherein the node is one of a plurality of nodes instructed to act as heartbeat relay agents.

18. An apparatus, comprising:

one or more network interfaces that communicate with a network;

a processor coupled to the one or more network interfaces and configured to execute a process; and

a memory configured to store program instructions which contain the process executable by the processor, the process comprising;

selecting a node in the network to act as a heartbeat relay agent based on a centrality of the node, the heartbeat relay agent collecting heartbeat messages from child nodes of the node, the heartbeat message indicating a liveness of a corresponding child node;

sending, to the node, a message instructing the node to act as the heartbeat relay agent;

receiving, from the node, a heartbeat report generated by the node based on the collected heartbeat messages; and

determining whether a particular child node is active or inactive based on the received heartbeat report.

19. The apparatus according to claim 18, wherein the process further comprises:

computing the centrality of the node based on at least one of;

i) a topology of the network, ii) an amount of congestion in the network, and iii) a stability of the network.

20. The apparatus as in claim 18, wherein the process further comprises:

sending, to the node, a message instructing the node to indicate in the heartbeat report a list of child nodes from which a heartbeat message was received, or a list of child nodes from which a heartbeat message was not received.