Method and apparatus to trigger DAG reoptimization in a sensor network

• US 8,588,108 B2
• Filed: 03/09/2011
• Issued: 11/19/2013
• Est. Priority Date: 02/21/2011
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Agarwal, Navneet, Hui, Jonathan W.
• Primary Examiner(s): Phillips, Hassan
• Assistant Examiner(s): Wei, Siren
• Application Number:
  US13/044,299
• Publication Number:
  US 20120213124A1
• Time in Patent Office: 986 Days
• Field of Search: 370/255, 370/254, 370/238
• US Class Current: 370/255
• 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
• CPC Class Codes: H04L 45/488 using root node determination
• CPC Class Codes: H04W 4/70 Services for machine-to-machine communication [M2M] or machine type communication [MTC]
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

In one embodiment, a probing technique allows a root node to determine whether to trigger reoptimization of a computer network represented by a directed acyclic graph (DAG) without injecting unnecessary traffic into the network. The root node may store and maintain information indicative of an ideal shape or topology of the DAG. During a normal DAG maintenance operation, the root node may transmit a DAG discovery request (probe request) that is configured to probe each node within the DAG for information used to determine a current topology of the DAG. In response, each node may record the information, e.g., routing and non-routing metrics, in a DAG discovery reply (probe reply) that is propagated to the root node. Upon receiving one or more replies, the root node may analyze the metrics to determine whether the current topology of the DAG deviates from the ideal DAG topology. The root node may thus determine DAG topology deviation upon probing at minimal cost. A number of algorithms may then be used to determine whether reoptimization, i.e., global repair, of the DAG is is required and, if so, the root node may dynamically trigger the global repair.

Claims

1. A method, comprising:

maintaining information at a root node of a computer network represented by a directed acyclic graph (DAG), the information indicative of an ideal DAG topology;

transmitting a discovery request from the root node to each node of the DAG, the discovery request configured to probe the node for metrics indicative of a current topology of the DAG, wherein the metrics include at least one of routing metrics and non-routing metrics;

receiving a discovery reply at the root node from the node in response to the discovery request, the discovery reply configured to record the metrics;

analyzing the metrics, indicative of the current topology of the DAG, at the root node to determine whether the current topology of the DAG deviates from the ideal DAG topology according to a predetermined threshold, in order to determine whether global repair of the DAG at the root node should be dynamically triggered; and

in response to determining the current topology of the DAG deviates from the ideal DAG topology according to the predetermined threshold, dynamically triggering global repair of the DAG at the root node.

2. The method as in claim 1, wherein transmitting of the discovery request occurs during normal DAG maintenance operation.

3. The method as in claim 1, wherein the discovery request is a DAG Information Object (DIO) message and wherein transmitting comprises:

generating the DIO message at the root node; and

configuring the DIO message with an asserted probe flag.

4. The method as in claim 1, wherein the discovery reply is a Destination Advertisement Object (DAO) message and wherein receiving comprises:

receiving the DAO message configured with an asserted probe flag.

5. The method as in claim 1, wherein the non-routing metrics include a rate of parent change experienced by the node.

6. The method as in claim 1, wherein the non-routing metrics include a rate of physical mobility of the node.

7. The method as in claim 1, wherein analyzing comprises:

comparing the metrics indicative of the current topology of the DAG with the information indicative of the ideal DAG topology to assess a deviation.

8. The method as in claim 7, wherein analyzing further comprises:

determining whether the deviation necessitates reoptimization of the DAG.

9. The method as in claim 1, wherein analyzing comprises:

determining that the global repair is needed when a sum of link costs in the DAG exceeds an average cost by a predetermined percentage.

10. An apparatus, comprising:

one or more network interfaces connected to a computer network represented by a directed acyclic graph (DAG);

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;

maintain information indicative of an ideal topology of the DAG;

transmit a discovery request to each node of the DAG, the discovery request configured to probe the node for metrics indicative of a current topology of the DAG, wherein the metrics include at least one of routing metrics and non-routing metrics;

receive a discovery reply from the node in response to the discovery request, the discovery reply configured to record the metrics;

analyze the metrics, indicative of the current topology of the DAG, to determine whether the current topology of the DAG deviates from the ideal topology of the DAG according to a predetermined threshold, in order to determine whether global repair of the DAG should be dynamically triggered; and

in response to determining the current topology of the DAG deviates from the ideal DAG topology according to the predetermined threshold, dynamically trigger global repair of the DAG.

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

transmit the discovery request during normal DAG maintenance operation.

12. The apparatus as in claim 10, wherein the discovery request is a DAG Information Object (DIO) message and wherein the process when executed is further operable to:

generate the DIO message; and

configure the DIO message with an asserted probe flag.

13. The apparatus as in claim 10, wherein the discovery reply is a Destination Advertisement Object (DAO) message and wherein the process when executed is further operable to:

receive the DAO message configured with an asserted probe flag.

14. The apparatus as in claim 10, wherein the non-routing metrics include a rate of parent change experienced by the node.

15. The apparatus as in claim 10, wherein the non-routing metrics include a rate of physical mobility of the node.

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

compare the metrics indicative of the current topology of the DAG with the information indicative of the ideal topology of the DAG to assess a deviation.

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

determine whether the deviation necessitates reoptimization of the DAG.

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

determine that the global repair is needed when a sum of link costs in the DAG exceeds a predetermined maximum threshold.

19. The apparatus as in claim 18, wherein the link costs include one of an expense incurred to traverse a type of link in the network, a throughput associated with the type of link, and a delay associated with the link.

20. A method, comprising:

transmitting probe requests from a root node to nodes of a computer network represented by a directed acyclic graph (DAG), the probe requests configured to probe the nodes for information used to determine topologies of the DAG;

receiving probe replies from the nodes at the root node, the probe replies configured to record the information;

compiling the information at the root node to create a history of DAG information indicative of at least an ideal DAG topology;

maintaining the ideal DAG topology at the root node;

transmitting a subsequent probe request from the root node to each node within the DAG during a maintenance operation to probe the node for metrics used to determine a current topology of the DAG, wherein the metrics includes at least one of routing metrics and non-routing metrics;

receiving a subsequent probe reply at the root node from the node, the subsequent probe reply configured to record the metrics;

analyzing the metrics, used to determine the current topology of the DAG, at the root node to determine whether the current topology of the DAG substantially deviates from the ideal DAG topology, in order to determine whether global repair of the DAG at the root node should be dynamically triggered; and

in response to determining the current topology of the DAG deviates from the ideal DAG topology according to the predetermined threshold, dynamically triggering global repair of the DAG at the root node.