METHOD AND APPARATUS TO TRIGGER DAG REOPTIMIZATION IN A SENSOR NETWORK
First Claim
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;
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 at the root node to determine whether the current topology of the DAG deviates from the ideal DAG topology according to a predetermined threshold; and
if so, dynamically triggering global repair of the DAG at the root node.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
20 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; 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 at the root node to determine whether the current topology of the DAG deviates from the ideal DAG topology according to a predetermined threshold; and if so, dynamically triggering global repair of the DAG at the root node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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; receive a discovery reply from the node in response to the discovery request, the discovery reply configured to record the metrics; analyze the metrics to determine whether the current topology of the DAG deviates from the ideal topology of the DAG according to a predetermined threshold; and if so, dynamically trigger global repair of the DAG. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18, 19)
-
-
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; receiving a subsequent probe reply at the root node from the node, the subsequent probe reply configured to record the metrics; is analyzing the metrics at the root node to determine whether the current topology of the DAG substantially deviates from the ideal DAG topology; and if so, dynamically triggering global repair of the DAG at the root node.
-
Specification