Partitioning directed acyclic graph (DAG) topologies

• US 8,451,744 B2
• Filed: 10/01/2010
• Issued: 05/28/2013
• Est. Priority Date: 08/16/2010
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe
• Primary Examiner(s): CHRISS, ANDREW W
• Assistant Examiner(s): Reddy, Ajit
• Application Number:
  US12/895,991
• Publication Number:
  US 20120039190A1
• Time in Patent Office: 970 Days
• Field of Search: None
• US Class Current: 370/252
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In one embodiment, network statistics may be monitored for a first directed acyclic graph (DAG) from a first root node, and based on those network statistics, a trigger may be determined to partition the first DAG. As such, a candidate second root node may be selected for each of one or more DAG partitions, and a tunnel may be established between the first root node and the one or more second root nodes. Each second root node may then establish a new DAG partition with itself as the root (and with the same DAG parameters as the first DAG), wherein nodes of the first DAG remain with the first DAG or attach to the new DAG partition based on one or more metrics associated with each respective root (e.g., reachability, cost, DAG rank, etc.).

Claims

1. A method, comprising:

monitoring network statistics for a first directed acyclic graph (DAG) from a first root node;

determining a trigger to partition the first DAG based on the network statistics;

in response to the trigger, selecting a candidate second root node for each of one or more DAG partitions; and

requesting, by the first root node, that each selected second root node establish a new DAG partition with the respective second root node itself as the root of their new DAG, wherein nodes of the first DAG one of either remain with the first DAG or attach to the new DAG partition based on one or more metrics associated with each respective root.

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

establishing a tunnel between the first root node and the one or more second root nodes.

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

sending DAG configuration parameters of the first DAG to the one or more second root nodes such that the one or more new DAGs are established with the same DAG configuration parameters as the first DAG.

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

determining the triggers based on one of;

an amount of control plane traffic;

an amount of control plane traffic when compared to data traffic;

a number of local repairs that took place in the network;

statistics on link loads within the DAG; and

a fan-out ratio of the DAG.

5. The method as in claim 1, wherein selecting a candidate second root node further comprises:

determining a set of candidate root nodes from a set of nodes capable of acting as DAG roots based on one of either a configured list of nodes capable of acting as DAG roots or by searching for the set of nodes capable of acting as DAG roots within the network.

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

incrementally requesting one or more additional new DAG partitions up to a number of candidate second root nodes in the network.

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

converging one or more new DAG partitions.

8. 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;

operate as a first root node of a first directed acyclic graph (DAG);

monitor network statistics for the first DAG;

determine a trigger to partition the first DAG based on the network statistics;

select a candidate second root node for each of one or more DAG partitions in response to the trigger; and

request that each selected second root node establish a new DAG partition with the respective second root node itself as the root of their new DAG, wherein nodes of the first DAG one of either remain with the first DAG or attach to the new DAG partition based on one or more metrics associated with each respective root.

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

establish a tunnel between the first root node and the one or more second root nodes.

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

determine the triggers based on one of;

an amount of control plane traffic;

an amount of control plane traffic when compared to data traffic;

a number of local repairs that took place in the network;

statistics on link loads within the DAG; and

a fan-out ratio of the DAG.

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

determine a set of candidate root nodes from a set of nodes capable of acting as DAG roots based on one of either a configured list of nodes capable of acting as DAG roots or by searching for the set of nodes capable of acting as DAG roots within the network.

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

incrementally request one or more additional new DAG partitions up to a number of candidate second root nodes in the network.

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

request convergence of one or more new DAG partitions.

14. A method, comprising:

receiving, at a candidate second root node, a request from a first root node of a first directed acyclic graph (DAG) to establish a second DAG partition;

determining DAG configuration parameters of the first DAG;

establishing, by the candidate root node, a second DAG partition with itself as the root of the second DAG, the second DAG partition established with the DAG configuration parameters of the first DAG; and

maintaining the second DAG such that nodes of the first DAG one of either remain with the first DAG or attach to the second DAG partition based on one or more metrics associated with the first root node and the second root node.

15. The method as in claim 14, further comprising:

establishing a tunnel between the first root node and the second root node.

16. The method as in claim 14, wherein the one or more metrics associated with the first root node and the second root node comprise at least one of reachability, cost, and DAG rank.

17. The method as in claim 14, wherein the second root node was a node within the first DAG prior to receiving the request.

18. The method as in claim 14, further comprising:

utilizing one or more mechanisms to attract nodes to the second DAG in order to increase a number of nodes that attach to the second DAG given a substantially equal option to remain in the first DAG.

19. The method as in claim 14, further comprising:

monitoring network statistics for the second DAG;

determining a trigger to partition the second DAG based on the network statistics;

in response to the trigger, selecting a candidate third root node for each of one or more DAG partitions; and

requesting, by the second root node, that each selected third root node establish a new DAG partition with the respective third root node itself as the root of their new DAG, wherein nodes of the second DAG one of either remain with the second DAG or attach to the new DAG partition based on one or more metrics associated with each respective root.

20. 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;

receive a request from a first root node of a first directed acyclic graph (DAG) to establish a second DAG partition;

determine DAG configuration parameters of the first DAG;

establish a second DAG partition with the apparatus itself as the root of the second DAG, the second DAG partition established with the DAG configuration parameters of the first DAG; and

maintain the second DAG such that nodes of the first DAG one of either remain with the first DAG or attach to the second DAG partition based on one or more metrics associated with the first root node and the apparatus.

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

establish a tunnel between the first root node and the apparatus for the second DAG partition.

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

operate as a node within the first DAG prior to receiving the request.

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

utilize one or more mechanisms to attract nodes to the second DAG in order to increase a number of nodes that attach to the second DAG given a substantially equal option to remain in the first DAG.

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

monitor network statistics for the second DAG;

determine a trigger to partition the second DAG based on the network statistics;

select a candidate third root node for each of one or more DAG partitions in response to the trigger; and

request that each selected third root node establish a new DAG partition with the respective third root node itself as the root of their new DAG, wherein nodes of the second DAG one of either remain with the second DAG or attach to the new DAG partition based on one or more metrics associated with each respective root.