DYNAMIC DIRECTED ACYCLIC GRAPH (DAG) TOPOLOGY REPORTING

• US 20110228696A1
• Filed: 05/28/2010
• Published: 09/22/2011
• Est. Priority Date: 03/19/2010
• Status: Abandoned Application

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Achar, Vivek N., Vasseur, Jean-Philippe, Agarwal, Navneet
• Application Number:
  US12/790,028
• Publication Number:
  US 20110228696A1
• Time in Patent Office: Days
• US Class Current: 370/253
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

In one embodiment, a root device of a directed acyclic graph (DAG) may determine/detect a trigger to learn a network topology of the DAG. In response, the root device may transmit a DAG discovery request down the DAG with a route record request that requests that each device within the DAG add its device identification (ID) to a reverse route record stack for each route of a DAG discovery reply propagated up the DAG toward the root device. Upon receiving one or more DAG discovery replies, the root device may compile the recorded routes from the reverse route record stacks into a DAG network topology. Also, in one embodiment, the root device may determine “short-cuts” based on a traffic matrix generated in response to network statistics optionally included within the responses from the devices within the DAG.

Claims

1. A method, comprising:

determining, by a root device of a directed acyclic graph (DAG) in a computer network, a trigger to learn a network topology of the DAG;

in response, transmitting a DAG discovery request down the DAG, the DAG discovery request having a route record request that requests that each device within the DAG add its device identification (ID) to a reverse route record stack for each route of a DAG discovery reply propagated up the DAG toward the root device;

receiving one or more DAG discovery replies at the root device; and

compiling recorded routes of the one or more reverse route record stacks of the one or more DAG discovery replies into a DAG network topology.

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

reporting the DAG network topology.

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

determining whether the DAG network topology has changed since a previous DAG network topology.

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

determining the trigger on demand.

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

determining the trigger based on a periodic timer.

6. The method as in claim 1, wherein devices within the DAG that are unable to record state are configured to also add their respective device ID to the reverse route record stack for each route of the DAG discovery reply.

7. The method as in claim 1, wherein the route record request includes an indication that a reply is to be sent toward the root device by a particular device in the DAG in response to a local repair being performed by the particular device.

8. The method as in claim 1, wherein the route record request includes a request to include within the DAG discovery replies a set of traffic metrics regarding the routes carried in the DAG discovery replies.

9. The method as in claim 8, wherein the traffic metrics are selected from a group consisting of:

a number of packets handled, a number of packets redirected, and a rate of packets handled.

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

building, at the root device, a traffic matrix corresponding to the DAG network topology based on the traffic metrics.

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

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

12. An apparatus, comprising:

one or more network interfaces adapted to communicate on a 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 adapted to store a root device process executable by the processor, the process when executed operable to;

determine, as a root device of the DAG, a trigger to learn a network topology of the DAG;

transmit a DAG discovery request down the DAG in response to the trigger, the DAG discovery request having a route record request that requests that each device within the DAG add its device identification (ID) to a reverse route record stack for each route of a DAG discovery reply propagated up the DAG toward the apparatus;

receive one or more DAG discovery replies; and

compile recorded routes of the one or more reverse route record stacks of the one or more DAG discovery replies into a DAG network topology.

13. A method, comprising:

receiving, at a particular device of a directed acyclic graph (DAG) in a computer network, a DAG discovery request transmitted down the DAG from a root device of the DAG, the DAG discovery request having a route record request;

in response to the route record request, adding a device identification (ID) of the particular device to a reverse route record stack for each route of a DAG discovery reply; and

transmitting the DAG discovery reply up the DAG toward the root device.

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

waiting for expiration of a timer configured to allow receipt of DAG discovery replies from downstream DAG devices prior to adding the device ID and transmitting the DAG discovery reply.

15. The method as in claim 13, wherein the device ID is a network address of the device.

16. The method as in claim 13, further comprising:

determining that a local repair has been performed by the particular device; and

in response, transmitting a reply message toward the root device from the particular device indicating the local repair.

17. The method as in claim 13, further comprising:

including within the DAG discovery reply a set of traffic metrics regarding the routes in the reply.

18. The method as in claim 17, wherein the traffic metrics are selected from a group consisting of:

a number of packets handled, a number of packets redirected, and a rate of packets handled.

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

determining that a metric threshold has been reached at the particular device; and

in response, transmitting a reply message toward the root device from the particular device indicating metric.

20. The method as in claim 13, further comprising:

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

21. An apparatus, comprising:

one or more network interfaces adapted to communicate on a 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 adapted to store a root device process executable by the processor, the process when executed operable to;

receive a DAG discovery request transmitted down the DAG from a root device of the DAG, the DAG discovery request having a route record request;

add, in response to the route record request, a device identification (ID) of the apparatus to a reverse route record stack for each route of a DAG discovery reply; and

transmit the DAG discovery reply up the DAG toward the root device.