CYCLE-FREE MULTI-TOPOLOGY ROUTING

• US 20140269413A1
• Filed: 03/15/2013
• Published: 09/18/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Vasseur, Jean-Philippe, Hong, Wei
• Granted Patent: US 9,553,796 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

In one embodiment, a node in a shared-media communication network may determine a first directed acyclic graph (DAG) topology, wherein the first DAG topology has a particular direction. The node may determine a second DAG topology in the shared-media communication network based on the first DAG topology. The second DAG topology may share the particular direction of the first DAG topology, to prevent loops between the first and the second DAG topologies.

Claims

1. A method, comprising:

determining a first directed acyclic graph (DAG) topology in a shared-media communication network, the first DAG topology having a particular direction; and

determining a second DAG topology in the shared-media communication network based on the first DAG topology, the second DAG topology sharing the particular direction of the first DAG topology, to prevent loops between the first and the second DAG topologies.

2. The method of claim 1, further comprising:

forwarding a message over the determined DAG topology.

3. The method of claim 1, wherein the first DAG topology emphasizes link stability and the second DAG topology emphasizes reduced hop count.

4. The method of claim 1, further comprising:

forwarding a message over the first DAG topology in response to a link quality of the second DAG topology being below a predetermined threshold, wherein the link quality is selected from a group consisting of;

a link margin constraint, a signal strength, and an estimated transmission count (ETX).

5. The method of claim 3, wherein determining the first DAG topology and the second DAG topology comprises:

building the first DAG topology by considering only next-hop routes that provide a link margin above a predetermined threshold constraint; and

building the second DAG topology by considering next-hop routes with a relaxed link margin constraint.

6. The method of claim 5, further comprising:

adjusting the link margin constraint based on the number of available next-hop routes.

7. The method of claim 5, wherein building the first DAG topology is based on the link margin constraint of paths in the shared-media communication network.

8. The method of claim 1, further comprising:

determining a rank of one or more neighboring nodes in the first DAG topology, wherein the rank of each neighboring node represents a topological distance to a root node of the first DAG topology.

9. The method of claim 8, further comprising:

determining the rank of a first parent in the first DAG topology; and

selecting a second parent in the second DAG topology to have a rank in the first DAG topology that is less than or equal to the rank of the first parent in the first DAG topology.

10. The method of claim 5, further comprising:

sending a message to a management node indicating insufficient next-hop routes that provide a link margin above a predetermined threshold constraint; and

receiving a response message from the management node to relax the link margin constraint.

11. The method of claim 1, wherein a management node determines the first and the second DAG topologies and informs the nodes in the shared-media communication network of the determined topologies.

12. The method of claim 1, further comprising:

adjusting one or both of the determined DAG topologies based on a determined delay in the shared-media communication network.

13. An apparatus, comprising:

one or more network interfaces to communicate with a shared-media 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 first directed acyclic graph (DAG) topology in a shared-media communication network, the first DAG topology having a particular direction; and

determine a second DAG topology in the shared-media communication network based on the first DAG topology, the second DAG topology sharing the particular direction of the first DAG topology, to prevent loops between the first and the second DAG topologies.

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

forward a message over the determined DAG topology.

15. The apparatus of claim 13, wherein the first DAG topology emphasizes link stability and the second DAG topology emphasizes reduced hop count.

16. The apparatus of claim 13, wherein the process when executed is further operable to:

forward a message over the first DAG topology in response to a link quality of the second DAG topology being below a predetermined threshold, wherein the link quality is selected from a group consisting of;

a link margin constraint, a signal strength, and an estimated transmission count (ETX).

17. The apparatus of claim 13, wherein the process when executed is further operable to:

build the first DAG topology by considering only next-hop routes that provide a link margin above a predetermined threshold constraint; and

build the second DAG topology by considering next-hop routes with a relaxed link margin constraint.

18. The apparatus of claim 13, wherein the process when executed is further operable to:

determine a rank of one or more neighboring nodes in the first DAG topology, wherein the rank of each neighboring node represents a topological distance to a root node of the first DAG topology.

19. The apparatus of claim 18, wherein the process when executed is further operable to:

determine the rank of a first parent in the first DAG topology; and

select a second parent in the second DAG topology to have a rank in the first DAG topology that is less than or equal to the rank of the first parent in the first DAG topology.

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

determine a first directed acyclic graph (DAG) topology in a shared-media communication network, the first DAG topology having a particular direction; and

determine a second DAG topology in the shared-media communication network based on the first DAG topology, the second DAG topology sharing the particular direction of the first DAG topology, to prevent loops between the first and the second DAG topologies.