Dynamic keepalive parameters for reverse path validation in computer networks

• US 8,862,774 B2
• Filed: 09/12/2011
• Issued: 10/14/2014
• Est. Priority Date: 09/12/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Hui, Jonathan W.
• Primary Examiner(s): Osman, Ramy M
• Application Number:
  US13/230,373
• Publication Number:
  US 20130067063A1
• Time in Patent Office: 1,128 Days
• Field of Search: 709/203, 709/223, 709/230, 709/238, 709/242, 709/245, 709/224, 709/229, 709/246, 709/239, 709/243, 370/338, 370/241, 370/248, 370/351, 370/389
• US Class Current: 709/239
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04L 45/70 Routing based on monitoring results

Abstract

In one embodiment, a network device determines a path from itself to a source device in a computer network, where the source device utilizes the path in reverse to reach the network device. Based on determining a reliability of the path in reverse, the network device may dynamically adjust one or more keepalive parameters for keepalive messages sent on the path. Accordingly, the network device may then send keepalive messages on the path based on the dynamically adjusted keepalive parameters.

Claims

1. A method, comprising:

determining a path from a network device to a source device in a computer network, wherein the source device utilizes the path in reverse from the source device to the network device to reach the network device;

determining a reliability of a plurality of links connecting a plurality of nodes along the path in reverse by the network device;

dynamically adjusting one or more keepalive parameters for keepalive messages sent on the path based on the reliability of the path in reverse; and

sending keepalive messages on the path based on the dynamically adjusted keepalive parameters,

wherein in response to failure of the keepalive messages on the path, the network device repairs a broken path to the source device with a route change.

2. The method as in claim 1, wherein determining the reliability comprises:

observing a retransmission count contained in messages received at the network device from the path in reverse.

3. The method as in claim 2, wherein the messages are data messages.

4. The method as in claim 1, wherein determining the reliability comprises:

determining an expected retransmission count (ETX) metric for the path in reverse.

5. The method as in claim 1, wherein adjusting the keepalive parameters comprises:

adjusting a rate at which keepalive messages are sent.

6. The method as in claim 5, wherein adjusting further comprises:

increasing the rate in response to the reliability surpassing an unacceptable reliability threshold; and

decreasing the rate in response to the reliability surpassing an acceptable reliability threshold.

7. The method as in claim 6, further comprising:

adjusting the rate respectively in increments in response to the reliability continuing to surpass the corresponding reliability threshold.

8. The method as in claim 1, wherein adjusting the keepalive parameters comprises:

adjusting a hop distance for which keepalive messages are sent.

9. The method as in claim 8, wherein adjusting further comprises:

increasing the hop distance in response to the reliability surpassing an unacceptable reliability threshold; and

decreasing the hop distance in response to the reliability surpassing an acceptable reliability threshold.

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

adjusting the hop distance respectively in increments in response to the reliability continuing to surpass the corresponding reliability threshold.

11. The method as in claim 1, wherein adjusting the keepalive parameters comprises:

adjusting a rate at which keepalive messages are sent and a hop distance for which keepalive messages are sent.

12. The method as in claim 11, wherein adjusting further comprises:

increasing the rate;

determining that the reliability continues to surpass an unacceptable reliability threshold; and

in response, increasing the hop distance.

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

determining an acceptable reliability threshold and an unacceptable reliability threshold on an individual device basis.

14. The method as in claim 1, wherein the source device is a root device of a directed acyclic graph (DAG).

15. An apparatus, comprising:

one or more network interfaces to communicate in a computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

determine a path from the apparatus to a source device in the computer network, wherein the source device utilizes the path in reverse from the source device to the apparatus to reach the apparatus;

determine a reliability of a plurality of links connecting a plurality of nodes along the path in reverse;

dynamically adjust one or more keepalive parameters for keepalive messages sent on the path based on the reliability of the path in reverse; and

send keepalive messages on the path based on the dynamically adjusted keepalive parameters,

wherein in response to failure of the keepalive messages on the path, the network device repairs a broken path to the source device with a route change.

16. The apparatus as in claim 15, wherein the process when executed to determine the reliability is further operable to:

observe a retransmission count contained in messages received at the apparatus from the path in reverse.

17. The apparatus as in claim 15, wherein the process when executed to adjust the keepalive parameters is further operable to:

adjust a rate at which keepalive messages are sent.

18. The apparatus as in claim 17, wherein the process when executed to adjust is further operable to:

increase the rate in response to the reliability surpassing an unacceptable reliability threshold; and

decrease the rate in response to the reliability surpassing an acceptable reliability threshold.

19. The apparatus as in claim 15, wherein the process when executed to adjust the keepalive parameters is further operable to:

adjust a hop distance for which keepalive messages are sent.

20. The apparatus as in claim 19, wherein the process when executed to adjust is further operable to:

increase the hop distance in response to the reliability surpassing an unacceptable reliability threshold; and

decrease the hop distance in response to the reliability surpassing an acceptable reliability threshold.

21. The apparatus as in claim 15, wherein the process when executed to adjust the keepalive parameters is further operable to:

adjust a rate at which keepalive messages are sent and a hop distance for which keepalive messages are sent.

22. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor on a network device operable to:

determine a path from a network device to a source device in a computer network, wherein the source device utilizes the path in reverse from the source device to the network device to reach the network device;

determine a reliability of a plurality of links connecting a plurality of nodes along the path in reverse by the network device;

dynamically adjust one or more keepalive parameters for keepalive messages sent on the path based on the reliability of the path in reverse; and

send keepalive messages on the path based on the dynamically adjusted keepalive parameters,

wherein in response to failure of the keepalive messages on the path, the network device repairs a broken path to the source device with a route change.

23. The computer-readable media as in claim 22, wherein the software when executed to determine the reliability is further operable to:

observe a retransmission count contained in messages received at the network device from the path in reverse.

24. The computer-readable media as in claim 22, wherein the software when executed to adjust the keepalive parameters is further operable to adjust at least one parameter selected from the group consisting of:

a rate at which keepalive messages are sent; and

a hop distance for which keepalive messages are sent.