ADAPTIVE REOPTIMIZATION RATE FOR UNSTABLE NETWORK TOPOLOGIES

• US 20130121331A1
• Filed: 11/10/2011
• Published: 05/16/2013
• Est. Priority Date: 11/10/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.
• Granted Patent: US 9,277,482 B2
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

In one embodiment, the network stability of a communication network is determined based on one or more network metrics related to stability, and then based on the network stability, a particular frequency at which to perform route reoptimization is determined, where the frequency inversely corresponds to the network stability. As such, distributed route reoptimization is triggered in the communication network at the adaptively determined frequency.

Claims

1. A method, comprising:

determining a network stability of a communication network based on one or more network metrics related to stability;

determining, based on the network stability, with what frequency to perform route reoptimization, wherein the frequency inversely corresponds to the network stability; and

triggering distributed route reoptimization in the communication network at the determined frequency.

2. The method as in claim 1, wherein the communication network is configured to maintain link connectivity in a first direction and to utilize the links in a correspondingly reverse second direction without connectivity confirmation.

3. The method as in claim 1, wherein the network metrics related to stability are selected from a group consisting of:

route change frequency;

unreachability errors;

packet retransmissions;

expected retransmission count (ETX);

link metrics;

route metrics; and

link-layer noise-floor measurements.

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

receiving the one or more network metrics related to stability from nodes of the communication network.

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

determining whether the network stability reflects global instability or local instability within the communication network; and

in response to global instability, triggering global reoptimization at the determined frequency; and

in response to local instability, triggering local reoptimization at the determined frequency.

6. The method as in claim 1, wherein determining the network stability, determining with what frequency to perform route reoptimization, and triggering distributed route reoptimization are performed by a single device.

7. The method as in claim 1, wherein determining the network stability is performed by a first device, and wherein determining with what frequency to perform route reoptimization and triggering distributed route reoptimization are performed by a second device.

8. The method as in claim 1, wherein the communication network operates according to a proactive routing protocol, and wherein triggering comprises:

incrementing a topology instance identifier (ID) to correspondingly trigger a topology rebuild in the communication network.

9. The method as in claim 1, wherein the communication network operates according to a reactive routing protocol, and wherein triggering comprises:

sending a message to one or more targeted destinations in the communication network to correspondingly trigger reactive topology rebuilding in the communication network.

10. The method as in claim 1, wherein the communication network is a sub-directed acyclic graph (sub-DAG) of an encompassing DAG, and wherein the network stability is specific to the sub-DAG, and wherein the distributed route reoptimization occurs in the sub-DAG.

11. An apparatus, comprising:

one or more network interfaces to communicate with a communication 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 network stability of the communication network based on one or more network metrics related to stability;

determine, based on the network stability, with what frequency to perform route reoptimization, wherein the frequency inversely corresponds to the network stability; and

trigger distributed route reoptimization in the communication network at the determined frequency.

12. The apparatus as in claim 11, wherein the communication network is configured to maintain link connectivity in a first direction and to utilize the links in a correspondingly reverse second direction without connectivity confirmation.

13. The apparatus as in claim 11, wherein the network metrics related to stability are selected from a group consisting of:

route change frequency;

unreachability errors;

packet retransmissions;

expected retransmission count (ETX);

link metrics;

route metrics; and

link-layer noise-floor measurements.

14. The apparatus as in claim 13, wherein the process when executed is further operable to:

receive the one or more network metrics related to stability from nodes of the communication network.

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

determine whether the network stability reflects global instability or local instability within the communication network; and

in response to global instability, trigger global reoptimization at the determined frequency; and

in response to local instability, trigger local reoptimization at the determined frequency.

16. The apparatus as in claim 11, wherein the apparatus is selected from a group consisting of:

a root node of a directed acyclic graph (DAG); and

a network management server (NMS).

17. The apparatus as in claim 11, wherein the apparatus is a root node of a directed acyclic graph (DAG), and wherein the process when executed to determine the network stability is further operable to:

receive the network stability from a network management server (NMS).

18. The apparatus as in claim 11, wherein the communication network operates according to a proactive routing protocol, and wherein the process when executed to trigger is further operable to:

increment a topology instance identifier (ID) to correspondingly trigger a topology rebuild in the communication network.

19. The apparatus as in claim 11, wherein the communication network operates according to a reactive routing protocol, and wherein the process when executed to trigger is further operable to:

send a message to one or more targeted destinations in the communication s network to correspondingly trigger reactive topology rebuilding in the communication network.

20. The apparatus as in claim 11, wherein the communication network is a sub-directed acyclic graph (sub-DAG) of an encompassing DAG, and wherein the network stability is specific to the sub-DAG, and wherein the distributed route reoptimization occurs in the sub-DAG.

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

determine a network stability of a communication network based on one or more network metrics related to stability;

determine, based on the network stability, with what frequency to perform route reoptimization, wherein the frequency inversely corresponds to the network stability; and

trigger distributed route reoptimization in the communication network at the determined frequency.

22. The computer-readable media as in claim 21, wherein the communication network is configured to maintain link connectivity in a first direction and to utilize the links in a correspondingly reverse second direction without connectivity confirmation.

23. The computer-readable media as in claim 21, wherein the network metrics related to stability are selected from a group consisting of:

route change frequency;

unreachability errors;

packet retransmissions;

expected retransmission count (ETX);

link metrics;

route metrics; and

link-layer noise-floor measurements.

24. The computer-readable media as in claim 21, wherein the software when executed is further operable to:

determine whether the network stability reflects global instability or local instability within the communication network; and

in response to global instability, trigger global reoptimization at the determined frequency; and

in response to local instability, trigger local reoptimization at the determined frequency.

25. The computer-readable media as in claim 21, wherein the software is executed on a root node of a directed acyclic graph (DAG), and wherein the software when executed to determine the network stability is further operable to:

receive the network stability from a network management server (NMS).