Dynamic Reroute Scheduling in a Directed Acyclic Graph (DAG)

• US 20120155329A1
• 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: Shaffer, Shmuel, Vasseur, Jean-Philippe, Shetty, Sandeep Jay
• Granted Patent: US 8,937,886 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 45/023 Delayed use of routing table updates

Abstract

In one embodiment, a particular node joins a directed acyclic graph (DAG) in a computer network at a parent node, and determines its grade based on a topology of the DAG, the grade lower than the parent node and higher than any child nodes of the particular node. In response to detecting a trigger for a routing change in the DAG, the particular node delays the routing change based on the grade such that the delay is longer than a first associated delay of any of the child nodes and shorter than a second associated delay of the parent node. Upon expiration of the delay, the particular node may determine if the trigger for the routing change is still valid, and if valid, performs the routing change.

Claims

1. A method, comprising:

joining, by a particular node, a directed acyclic graph (DAG) in a computer network at a parent node;

determining a grade of the particular node based on a topology of the DAG, the grade being lower than the parent node and higher than child nodes of the particular node;

detecting a trigger for a routing change in the DAG;

in response, delaying the routing change by the particular node based on the grade such that the delay is longer than a first associated delay of at least some of the child nodes and shorter than a second associated delay of the parent node;

in response to expiration of the delay, determining if the trigger for the routing change is still valid; and

if valid, performing the routing change by the particular node.

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

determining the grade based on topology factors of the DAG selected from a group consisting of;

a number of nodes in a sub-DAG of the particular node;

a depth of the particular node within the DAG from a root node; and

a height in the sub-DAG of the particular node from a deepest leaf node in the sub-DAG.

3. The method as in claim 1, wherein determining the grade comprises:

determining the grade based on topology factors of the DAG selected from a group consisting of;

traffic expected at the particular node based on the topology;

current traffic at the particular node due to the topology; and

an average traffic at the particular node based on the topology.

4. The method as in claim 1, wherein detecting the trigger comprises:

identifying a routing metric change of a metric selected from a group consisting of;

cost;

delay;

latency;

available bandwidth;

utilized bandwidth; and

estimated transmission count (ETX).

5. The method as in claim 1, wherein detecting the trigger comprises:

identifying a routing metric change that is greater than a threshold, the threshold based on the grade such that the threshold is greater than or equal to a first associated threshold of at least some of the child nodes and less than or equal to a second associated threshold of the parent node.

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

receiving the grade at the particular node from a management node of the DAG.

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

receiving a notification from a particular one of the child nodes that the particular child node is changing parents to a node other than the particular node; and

in response, determining if the trigger is still valid based on the child node changing parents.

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

transmitting a notification from the particular node to the parent node that the particular node is changing parents to a node other than the parent node.

9. The method as in claim 1, wherein determining if the trigger is still valid comprises:

waiting for new measurements based on any route changes performed by one or more child nodes of the particular node;

analyzing the new measurements;

determining that the trigger is still valid if the new measurements merit route changes by the particular node.

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

determining that one of the child nodes changed parents to a node other than the particular node; and

in response, resetting the delay to the routing change.

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

randomizing the performance of the routing change within a range that is longer than the first associated delay of at least some of the child nodes and shorter than the second associated delay of the parent node.

24. The method of claim 1 wherein determining the grade of the particular node based on the topology of the DAG, includes determining the grade to be higher than any of the child nodes.

12. An apparatus, comprising:

one or more network interfaces adapted to participate in a directed acyclic graph (DAG) 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;

joining the DAG at a parent node;

determine a grade of the apparatus based on a topology of the DAG, the grade lower than the parent node and higher than child nodes of the apparatus;

detect a trigger for a routing change in the DAG;

in response, delay the routing change by the apparatus based on the grade such that the delay is longer than a first associated delay of at least some of the child nodes and shorter than a second associated delay of the parent node;

in response to expiration of the delay, determine if the trigger for the routing change is still valid; and

if valid, perform the routing change.

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

determine the grade based on topology factors of the DAG selected from a group consisting of;

a number of nodes in a sub-DAG of the particular node;

a depth of the particular node within the DAG from a root node; and

a height in the sub-DAG of the particular node from a deepest leaf node in the sub-DAG.

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

determine the grade based on topology factors of the DAG selected from a group consisting of;

traffic expected at the particular node based on the topology;

current traffic at the particular node due to the topology; and

an average traffic at the particular node based on the topology.

15. The apparatus as in claim 12, wherein the process when executed to detect the trigger is operable to:

identify a routing metric change of a metric selected from a group consisting of;

cost;

delay;

latency;

available bandwidth;

utilized bandwidth; and

estimated transmission count (ETX).

16. The apparatus as in claim 12, wherein the process when executed to detect the trigger is operable to:

identify a routing metric change that is greater than a threshold, the threshold based on the grade such that the threshold is greater than or equal to a first associated threshold of the some of the child nodes and less than or equal to a second associated threshold of the parent node.

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

receive the grade from a management node of the DAG.

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

receive a notification from a particular one of the child nodes that the particular child node is changing parents to a node other than the apparatus; and

in response, determine if the trigger is still valid based on the child node changing parents.

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

transmit a notification to the parent node that the apparatus changed parents to a node other than the parent node in response to the performed routing change.

20. The apparatus as in claim 12, wherein the process when executed to determine if the trigger is still valid is operable to:

wait for new measurements based on any route changes performed by one or more child nodes of the apparatus;

analyze the new measurements;

determine that the trigger is still valid if the new measurements merit route changes by the apparatus.

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

determine that one of the child nodes changed parents to a node other than the apparatus; and

in response, reset the delay to the routing change.

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

randomize the performance of the routing change within a range that is longer than the first associated delay of at least some of the child nodes and shorter than the second associated delay of the parent node.

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

joining a directed acyclic graph (DAG) in a computer network at a parent node;

determine a grade of the device based on a topology of the DAG, the grade lower than the parent node and higher than child nodes of the device;

detect a trigger for a routing change in the DAG;

in response, delay the routing change by the device based on the grade such that the delay is longer than a first associated delay of at least some of the child nodes and shorter than a second associated delay of the parent node;

in response to expiration of the delay, determine if the trigger for the routing change is still valid; and

if valid, perform the routing change.