Remote stitched directed acyclic graphs

• US 9,001,669 B2
• Filed: 03/08/2011
• Issued: 04/07/2015
• 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
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): ANDREWS, LEON T
• Application Number:
  US13/043,111
• Publication Number:
  US 20120230204A1
• Time in Patent Office: 1,491 Days
• Field of Search: None
• 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, by a network device, a trigger condition at a particular location in a primary directed acyclic graph (DAG) in a computer network, wherein the primary DAG includes a root node of the primary DAG;

determining, by the network device, 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, wherein the particular node is a different node in the primary DAG than the root node of the primary DAG;

instructing, by the network device, the RS-DAG root to initiate the RS-DAG, the instructing indicating one or more properties for the RS-DAG that are selected to cause additional data regarding the trigger condition to be collected within the RS-DAG and that are different from properties of the primary DAG, wherein a particular child node of the RS-DAG root in the RS-DAG has a different parent node in the primary DAG; and

receiving, at the network device, a conclusion message from the RS-DAG root that aggregates the additional data regarding the trigger condition collected within the RS-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. method as in claim 1, further comprising:

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

13. The method as in claim 1, wherein the network device is root node 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 one or more 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 configured to;

detect a trigger condition at a particular location in a primary directed acyclic graph (DAG) in the computer network, wherein the primary DAG includes a root node of the primary DAG;

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, wherein the particular node is a different node in the primary DAG than the root node of the primary DAG;

instruct the RS-DAG root to initiate the RS-DAG, the instructing indicating one or more properties for the RS-DAG that are selected to cause additional data regarding the trigger condition to be collected within the RS-DAG and that are different from properties of the primary DAG, wherein a particular child node of the RS-DAG root in the RS-DAG has a different parent node in the primary DAG; and

receive a conclusion message from the RS-DAG root that aggregates the additional data regarding the trigger condition collected within the RS-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 configured to:

detect a trigger condition at a particular location in a primary directed acyclic graph (DAG) in a computer network, wherein the primary DAG includes a root node of the primary DAG;

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, wherein the particular node is a different node in the primary DAG than the root of the primary DAG;

instruct the RS-DAG root to initiate the RS-DAG, the instructing indicating one or more properties for the RS-DAG that are selected to cause additional data regarding the trigger condition to be collected within the RS-DAG and that are different from properties of the primary DAG, wherein a particular child node of the RS-DAG root in the RS-DAG has a different parent node in the primary DAG; and

receive a conclusion message from the RS-DAG root that aggregates the additional data regarding the trigger condition collected within the RS-DAG.

18. A method, comprising:

receiving, by a network device that is 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, wherein the RS-DAG root is a different node in the primary DAG than a root node of the primary DAG;

initiating, by the network device, the RS-DAG from the RS-DAG root to collect additional data within the RS-DAG regarding a triggering condition, wherein a particular child node of the RS-DAG root in the RS-DAG has a different parent node in the primary DAG; and

relaying, by the network device, messages of the RS-DAG between the RS-DAG root and the root node of the primary DAG that include the collected additional data.

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 the collected additional data at the RS-DAG root.

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

establishing a tunnel between the root node 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 the 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 root node of the primary DAG is in response to receiving a trigger condition notification from the root node of the primary DAG regarding the trigger condition, 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 the 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, wherein the primary DAG includes a root node of the primary DAG;

a processor coupled to the one or more 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 configured 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, wherein the particular node is a different node in the primary DAG than the root node of the primary DAG;

initiate the RS-DAG from the RS-DAG root to collect additional data within the RS-DAG regarding a triggering condition, wherein a particular child node of the RS-DAG root in the RS-DAG has a different parent node in the primary DAG; and

relay messages of the RS-DAG between the RS-DAG root and a primary root of the primary DAG that include the collected additional data.

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 the trigger condition, the process when executed further configured to:

perform an analysis of the trigger condition.

28. The apparatus as in claim 25, wherein the process is configured 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 root node of the primary DAG, and wherein the process is configured 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 configured 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, wherein the RS-DAG root is a different node in the primary DAG than a root node of the primary DAG;

initiate the RS-DAG from the RS-DAG root to collect additional data within the RS-DAG regarding a triggering condition, wherein a particular child node of the RS-DAG root in the RS-DAG has a different parent node in the primary DAG; and

relay messages of the RS-DAG between the RS-DAG root and the root node of the primary DAG that include the collected additional data.