Remote Stitched Directed Acyclic Graphs

• US 20120230204A1
• Filed: 03/08/2011
• Published: 09/13/2012
• Est. Priority Date: 03/08/2011
• 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 9,001,669 B2
• Time in Patent Office: Days
• US Class Current: 370/242
• CPC Class Codes: H04L 43/0823 Errors, e.g. transmission errors
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: Y04S 40/00 Systems for electrical power generation, transmission, distribution or end-user application management characterised by the use of communication or information technologies, or communication or information technology specific aspects supporting them
• CPC Class Codes: Y04S 40/18 Network protocols supporting networked applications, e.g. including control of end-device applications over a network

Abstract

In one embodiment, in response to a trigger condition being detected at a particular location in a primary directed acyclic graph (DAG) in a computer network, a particular node in the primary DAG at the particular location may be determined to act as a remote stitched (RS)-DAG root for an RS-DAG at the particular location. The determined RS-DAG root may then be instructed to initiate the RS-DAG, the instructing indicating one or more properties for the RS-DAG that are based on the trigger condition and that are different from properties of the primary DAG. In another embodiment, a particular node receives instructions to initiate an RS-DAG as its RS-DAG root, initiates the RS-DAG, and relays messages of the RS-DAG with a primary root of the primary DAG.

Claims

1. A method, comprising:

detecting a trigger condition at a particular location in a primary directed acyclic graph (DAG) in a computer network;

determining a particular node in the primary DAG at the particular location to act as a remote stitched (RS)-DAG root for an RS-DAG at the particular location; and

instructing the RS-DAG root to initiate the RS-DAG, the instructing indicating one or more properties for the RS-DAG that are based on the trigger condition and that are different from properties of the primary DAG.

2. The method as in claim 1, wherein the trigger condition is a sensed event at the particular location.

3. The method as in claim 1, wherein the trigger condition is selected from a group consisting of:

congestion at the particular location;

greater than a threshold of lost packets at the particular location; and

link failure at the particular location.

4. The method as in claim 1, wherein one of the one or more properties for the RS-DAG comprises one or more routing metrics for the RS-DAG.

5. The method as in claim 1, wherein one of the one or more properties for the RS-DAG comprises a list of one or more nodes in the primary DAG to specifically exclude or include from the RS-DAG.

6. The method as in claim 1, wherein one of the one or more properties for the RS-DAG comprises a length of time to maintain the RS-DAG.

7. The method as in claim 1, wherein one of the one or more properties for the RS-DAG comprises an increased sensing rate for sensor nodes in the RS-DAG.

8. The method as in claim 1, wherein one of the one or more properties for the RS-DAG comprises an objective function (OF) for the RS-DAG.

9. The method as in claim 1, wherein one of the one or more properties for the RS-DAG comprises a limited depth for the RS-DAG.

10. The method as in claim 1, wherein one of the one or more properties for the RS-DAG comprises data aggregation properties for the RS-DAG.

11. The method as in claim 1, wherein the particular location is selected from a group consisting of:

a subnet mask, a list of one or more specific addresses, a geographical positioning;

a particular device; and

a set of devices within an identified distance from a particular device.

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

establishing a tunnel between a primary root of the primary DAG and the RS-DAG root.

13. The method as in claim 1, wherein the detecting, determining, and instructing are performed by one of either a primary root of the primary DAG or a network management node in the computer network.

14. An apparatus, comprising:

one or more network interfaces to communicate 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;

detect a trigger condition at a particular location in a primary directed acyclic graph (DAG) in the computer network;

determine a particular node in the primary DAG at the particular location to act as a remote stitched (RS)-DAG root for an RS-DAG at the particular location; and

instruct the RS-DAG root to initiate the RS-DAG, the instructing indicating one or more properties for the RS-DAG that are based on the trigger condition and that are different from properties of the primary DAG.

15. The apparatus as in claim 14, wherein the trigger condition is selected from a group consisting of:

a sensed event at the particular location;

congestion at the particular location;

greater than a threshold of lost packets at the particular location; and

link failure at the particular location.

16. The apparatus as in claim 14, wherein the one or more properties for the RS-DAG are selected from a group consisting of:

one or more routing metrics for the RS-DAG;

a list of one or more nodes in the primary DAG to specifically exclude or include from the RS-DAG;

a length of time to maintain the RS-DAG;

an increased sensing rate for sensor nodes in the RS-DAG;

an objective function (OF) for the RS-DAG;

a limited depth for the RS-DAG; and

data aggregation properties for the RS-DAG.

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

detect a trigger condition at a particular location in a primary directed acyclic graph (DAG) in a computer network;

determine a particular node in the primary DAG at the particular location to act as a remote stitched (RS)-DAG root for an RS-DAG at the particular location; and

instruct the RS-DAG root to initiate the RS-DAG, the instructing indicating one or more properties for the RS-DAG that are based on the trigger condition and that are different from properties of the primary DAG.

18. A method, comprising:

receiving, by a particular node at a particular location in a primary directed acyclic graph (DAG) in a computer network, instructions to initiate a remote stitched (RS)-DAG by the particular node as an RS-DAG root, the instructions indicating one or more properties for the RS-DAG that are different from properties of the primary DAG;

initiating the RS-DAG from the RS-DAG root; and

relaying messages of the RS-DAG between the RS-DAG root and a primary root of the primary DAG.

19. The method as in claim 18, wherein the one or more properties for the RS-DAG are selected from a group consisting of:

one or more routing metrics for the RS-DAG;

a list of one or more nodes in the primary DAG to specifically exclude or include from the RS-DAG;

a length of time to maintain the RS-DAG;

an increased sensing rate for sensor nodes in the RS-DAG;

an objective function (OF) for the RS-DAG; and

a limited depth for the RS-DAG.

20. The method as in claim 18, wherein one of the one or more properties for the RS-DAG comprises data aggregation properties for the RS-DAG;

the method further comprising;

aggregating data for the RS-DAG at the RS-DAG root.

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

establishing a tunnel between a primary root of the primary DAG and the RS-DAG root.

22. The method as in claim 18, wherein the one or more properties of the RS-DAG are based on a trigger condition, the method further comprising:

performing an analysis of the trigger condition at the RS-DAG root.

23. The method as in claim 18, wherein relaying messages of the RS-DAG between the RS-DAG root and the primary root is in response to receiving a trigger condition notification from the primary root, and wherein the RS-DAG is initiated prior to receiving the trigger condition notification.

24. The method as in claim 18, wherein receiving instructions to initiate the RS-DAG by the particular node comprises:

detecting a trigger condition by the particular node, the instructions indicating one or more properties for the RS-DAG that are different from properties of the primary DAG and that are based on the trigger condition.

25. An apparatus, comprising:

one or more network interfaces to communicate as a particular node at a particular location in a primary 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;

receive instructions to initiate a remote stitched (RS)-DAG by the particular node as an RS-DAG root, the instructions indicating one or more properties for the RS-DAG that are different from properties of the primary DAG;

initiate the RS-DAG from the RS-DAG root; and

relay messages of the RS-DAG between the RS-DAG root and a primary root of the primary DAG.

26. The apparatus as in claim 25, wherein the one or more properties for the RS-DAG are selected from a group consisting of:

one or more routing metrics for the RS-DAG;

a list of one or more nodes in the primary DAG to specifically exclude or include from the RS-DAG;

a length of time to maintain the RS-DAG;

an increased sensing rate for sensor nodes in the RS-DAG;

an objective function (OF) for the RS-DAG;

a limited depth for the RS-DAG; and

data aggregation properties for the RS-DAG.

27. The apparatus as in claim 25, wherein the one or more properties of the RS-DAG are based on a trigger condition, the process when executed further operable to:

perform an analysis of the trigger condition.

28. The apparatus as in claim 25, wherein the process is operable to relay messages of the RS-DAG between the RS-DAG root and the primary root is in response to receiving a trigger condition notification from the primary root, and wherein the process is operable to initiate the RS-DAG prior to receiving the trigger condition notification.

29. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor on a particular node at a particular location in a primary directed acyclic graph (DAG) in a computer network operable to:

receive instructions to initiate a remote stitched (RS)-DAG by the particular node as an RS-DAG root, the instructions indicating one or more properties for the RS-DAG that are different from properties of the primary DAG;

initiate the RS-DAG from the RS-DAG root; and

relay messages of the RS-DAG between the RS-DAG root and a primary root of the primary DAG.