Dynamic directed acyclic graph (DAG) adjustment

• US 8,489,765 B2
• Filed: 05/28/2010
• Issued: 07/16/2013
• Est. Priority Date: 03/19/2010
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Agarwal, Navneet, Thubert, Pascal, Wetterwald, Patrick
• Primary Examiner(s): Maung, Zarni
• Application Number:
  US12/790,060
• Publication Number:
  US 20110231573A1
• Time in Patent Office: 1,145 Days
• Field of Search: 709/203, 709238-242, 709/250
• US Class Current: 709/238
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

In one embodiment, a root device may request that one or more devices of a computer network build a directed acyclic graph (DAG) for routing traffic within the computer network based on an objective function (OF), where the OF has one or more metrics to optimize the DAG against and optionally certain constraints. Particular devices that receive the request may then build the DAG based on the OF, and may determine and report OF feedback to the root device. Upon receiving the reports regarding OF feedback, the root device may then adjust the OF based on the feedback, and request a rebuild of the DAG from the devices based on the adjusted OF.

Claims

1. A method, comprising:

requesting, from a root device, that one or more devices of a computer network build a directed acyclic graph (DAG) for routing traffic within the computer network based on an objective function (OF), the OF having one or more metrics to optimize the DAG against and zero or more constraints;

receiving one or more reports from devices of the DAG regarding OF feedback;

adjusting the OF based on the feedback; and

requesting a rebuild of the DAG from the devices based on the adjusted OF.

2. The method as in claim 1, wherein adjusting comprises:

determining a problem from the one or more reports;

determining a solution to the problem; and

adjusting the one or more metrics and zero or more constraints based on the solution.

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

reporting the one or more reports to a system administrator; and

receiving an adjusted OF from the system administrator.

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

determining network statistics by the root device; and

generating at least one of the received one or more reports regarding OF feedback by the root device as a device of the DAG, wherein the OF feedback is based on the network statistics.

5. The method as in claim 1, wherein the received feedback includes an indication of network congestion.

6. The method as in claim 1, wherein a constraint of a first OF requires that a single parent be selected by each device of the DAG, and wherein an adjusted constraint of the adjusted OF requires that a plurality of parents be selected by each device of the DAG.

7. The method as in claim 6, wherein the OF specifies that the plurality of selected parents must each have a particular metric that is within a threshold distance from a best particular metric of a selected parent.

8. The method as in claim 1, wherein the received feedback includes a request for an added constraint.

9. The method as in claim 1, wherein the received feedback from a particular device includes an indication that the particular device is unable to comply with a particular constraint of the OF.

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

receiving a plurality of feedbacks from devices indicating inability to comply with a particular constraint; and

in response to the plurality of feedbacks being greater than a threshold, relaxing the constraint in the adjusted OF.

11. The method as in claim 1, wherein the received feedback from a particular device is in response to the particular device encountering a problem.

12. The method as in claim 1, wherein the received feedback includes network statistics.

13. The method as in claim 1, wherein adjusting the OF comprises changing one or more of the metrics.

14. The method as in claim 13, wherein changing metrics comprises at least one of either selecting a new preferred metric or rearranging an order of a plurality of metrics.

15. The method as in claim 1, wherein adjusting the OF comprises at least one of either adding or removing constraints.

16. The method as in claim 1, wherein the one or more metrics are selected from a group consisting of:

delay, latency, bandwidth, estimated transmission count (ETX), and cost.

17. The method as in claim 1, wherein the zero or more constraints comprise at least one constraint selected from a group consisting of:

reliability thresholds, restricted battery operation, multipath diversity, load balancing requirements, bandwidth requirements, transmission types, and number of selected parents.

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

utilizing DAG routing according to a Routing Protocol for Low Power and Lossy Networks (RPL).

19. An apparatus, comprising:

one or more network interfaces adapted to communicate with one or more devices of a computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory adapted to store a process executable by the processor, the process when executed operable to;

request that the one or more devices build a directed acyclic graph (DAG) for routing traffic within the computer network based on an objective function (OF), the OF having one or more metrics to optimize the DAG against and zero or more constraints;

receive one or more reports from devices of the DAG regarding OF feedback;

adjust the OF based on the feedback; and

request a rebuild of the DAG from the devices based on the adjusted OF.

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

determine a problem from the one or more reports;

determine a solution to the problem; and

adjust the one or more metrics and zero or more constraints based on the solution.

21. A method, comprising:

receiving a request, originated from a root device, at a particular device of a computer network, to build a directed acyclic graph (DAG) for routing traffic within the computer network based on an objective function (OF), the OF having one or more metrics to optimize the DAG against and zero or more constraints;

building the DAG based on the OF;

determining OF feedback; and

reporting the OF feedback toward the root device.

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

determining the OF feedback in response to determining an encountered problem at the particular device.

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

determining network statistics at the particular device; and

including the network statistics within the reported OF feedback.

24. An apparatus, comprising:

one or more network interfaces adapted to communicate with one or more devices of a computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory adapted to store a process executable by the processor, the process when executed operable to;

receive a request, originated from a root device, to build a directed acyclic graph (DAG) for routing traffic within the computer network based on an objective function (OF), the OF having one or more metrics to optimize the DAG against and zero or more constraints;

build the DAG based on the OF;

determine OF feedback; and

report the OF feedback toward the root device.