Dynamic Routing Metric Adjustment

• US 20120155475A1
• Filed: 12/17/2010
• Published: 06/21/2012
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Shaffer, Shmuel, Shetty, Sandeep Jay
• Granted Patent: US 8,787,392 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 45/028 Dynamic adaptation of the update intervals, e.g. event-triggered updates
• CPC Class Codes: H04W 40/248 Connectivity information update

Abstract

In one embodiment, one or more routing update parameters may be set for and propagated to nodes of a directed acyclic graph (DAG) in a computer network, the routing update parameters indicative of when to perform a corresponding routing update operation. A decision node (e.g., a root node of the DAG, application in a head-end, etc.) may gather network statistics of the DAG during operation based on the routing update parameters, and may accordingly determine at least one adjusted routing update parameter based on the gathered network statistics. This adjusted routing update parameter may then be propagated to the nodes of the DAG, such that the nodes operate according to the (adaptively) adjusted routing update parameter.

Claims

1. A method, comprising:

setting one or more routing update parameters for a directed acyclic graph (DAG) in a computer network, the routing update parameters indicative of when to perform a corresponding routing update operation;

propagating the routing update parameters to nodes in the DAG;

gathering one or more network statistics of the DAG during operation based on the routing update parameters;

determining at least one adjusted routing update parameter based on the gathered network statistics; and

propagating the adjusted routing update parameter to the nodes in the DAG.

2. The method as in claim 1, wherein a particular routing update parameter is a minimum link metric change required before advertising a particular metric change.

3. The method as in claim 1, wherein a particular routing update parameter is a minimum path cost gain required before a particular node in the DAG selects a new parent node.

4. The method as in claim 1, wherein the network statistics are selected from a group consisting of:

an amount of routing traffic;

an amount of power remaining in battery operating nodes;

a number of routing path changes;

a number of new parent selections;

a level of sub-optimality provided by DAG paths;

a number of dropped packets; and

a number of collisions.

5. The method as in claim 1, wherein gathering comprises:

receiving the network statistics from the nodes in the DAG.

6. The method as in claim 1, wherein setting, propagating, gathering, and determining are performed by a root node of the DAG.

7. The method as in claim 1, wherein there is a plurality of routing update parameters, the propagating of the adjusted routing parameter comprising:

propagating the plurality of routing update parameters including the adjusted routing parameter.

8. The method as in claim 1, wherein there is a plurality of routing update parameters, wherein the determining of the at least one adjusted routing parameter comprises adjusting each of the plurality of routing update parameters.

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

initializing a timer in response to propagating the adjusted routing parameter;

gathering updated network statistics during the timer; and

determining the at least one adjusted routing update parameter based on the gathered network statistics in response to expiration of the timer.

10. The method as in claim 1, wherein determining comprises:

incrementally adjusting a particular routing update parameter based on the gathered network statistics.

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

adjusting the route update parameters to a less-aggressive route update policy based on observation that batteries of specific nodes are running low on power; and

adjusting the route update parameters to a more-aggressive route update policy based on observation that batteries of the specific nodes have sufficient power.

12. An apparatus, comprising:

one or more network interfaces;

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;

set one or more routing update parameters for a directed acyclic graph (DAG) in a computer network, the routing update parameters indicative of when to perform a corresponding routing update operation;

propagate the routing update parameters to nodes in the DAG;

gather one or more network statistics of the DAG during operation based on the routing update parameters;

determine at least one adjusted routing update parameter based on the gathered network statistics; and

propagate the adjusted routing update parameter to the nodes in the DAG.

13. The apparatus as in claim 12, wherein a particular routing update parameter is a minimum link metric change required before advertising a particular metric change.

14. The apparatus as in claim 12, wherein a particular routing update parameter is a minimum path cost gain required before a particular node in the DAG selects a new parent node.

15. The apparatus as in claim 12, wherein the network statistics are selected from a group consisting of:

an amount of routing traffic;

an amount of power remaining in battery operating nodes;

a number of routing path changes;

a number of new parent selections;

a level of sub-optimality provided by DAG paths;

a number of dropped packets; and

a number of collisions.

16. The apparatus as in claim 12, wherein the network interfaces are configured to receive the network statistics from the nodes in the DAG.

17. The apparatus as in claim 12, wherein the apparatus is a root node of the DAG.

18. The apparatus as in claim 12, wherein there is a plurality of routing update parameters, the process when executed to propagate the adjusted routing parameter further operable to propagate the plurality of routing update parameters including the adjusted routing parameter.

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

initialize a timer in response to propagating the adjusted routing parameter;

gather updated network statistics during the timer; and

determine the at least one adjusted routing update parameter based on the gathered network statistics in response to expiration of the timer.

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

incrementally adjust a particular routing update parameter based on the gathered network statistics.

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

adjust the route update parameters to a less-aggressive route update policy based on observation that batteries of specific nodes are running low on power; and

adjust the route update parameters to a more-aggressive route update policy based on observation that batteries of the specific nodes have sufficient power.

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

set one or more routing update parameters for a directed acyclic graph (DAG) in a computer network, the routing update parameters indicative of when to perform a corresponding routing update operation;

propagate the routing update parameters to nodes in the DAG;

gather one or more network statistics of the DAG during operation based on the routing update parameters;

determine at least one adjusted routing update parameter based on the gathered network statistics; and

propagate the adjusted routing update parameter to the nodes in the DAG.

23. A method, comprising:

receiving one or more adjusted routing update parameters for a directed acyclic graph (DAG) at a node in a computer network, the routing update parameters indicative of when to perform a corresponding routing update operation;

configuring operation of the node according to the one or more routing update parameters;

collecting one or more network statistics during operation of the node based on the routing update parameters;

transmitting the collected network statistics toward a decision device for the DAG; and

receiving an updated adjusted routing update parameter from the decision device.