Method and apparatus to reduce cumulative effect of dynamic metric advertisement in smart grid/sensor networks

• US 9,325,626 B2
• Filed: 05/12/2014
• Issued: 04/26/2016
• Est. Priority Date: 08/16/2010
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe
• Primary Examiner(s): Avellino, Joseph E
• Assistant Examiner(s): Book, Phyllis A
• Application Number:
  US14/275,701
• Publication Number:
  US 20140247726A1
• Time in Patent Office: 715 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

The subject disclosure relates to a method for directing acyclic graph routing and management for Low power and Lossy Networks (LANs). A system may identify a gain factor that indicates a potential gain that can be obtained in link cost from a node in a network represented by a direct acyclic graph (DAG) to the root node of the DAG when an upper node in the DAG changes its routing decision. When the gain factor exceeds a threshold, the node can transmit a DAG rebuild request to other nodes in the DAG. Upon receiving the request, the system may determine whether to satisfy the DAG rebuild request based on the number of requesting nodes. Based on the determination, the system may select a new parent node for the node that receives the request. The DAG rebuild can decrease in link cost from the transmitting node to the root node.

Claims

1. A method comprising:

identifying, via a processor, a gain factor at a first node in a network represented by a directed acyclic graph (DAG), wherein the gain factor indicates a potential gain that can be obtained in link cost from the first node to a root node of the DAG when an upper node in the DAG changes its routing decision by selecting a different parent node;

when the gain factor exceeds a pre-defined threshold, transmitting a DAG rebuild request from the first node to other nodes in the DAG, wherein the DAG rebuild request recursively travels in an upward direction in the DAG;

determining whether to satisfy the DAG rebuild request based on a number of requesting nodes upon receiving the DAG rebuild request at a second node in the network; and

based on the determining step, at least partially rebuilding the DAG by selecting a new parent node for the second node, wherein the selection of the new parent node causes a decrease in link cost from the first node to the root node.

2. The method of claim 1, wherein identifying the gain factor comprises identifying an actual path cost to the root node.

3. The method of claim 1, wherein the DAG rebuild request recursively travels in the upward direction in the DAG to trigger one or more ancestor nodes of the first node to change their parent node selection.

4. The method of claim 1, wherein transmitting a DAG rebuild request comprises using a routing oscillation avoidance mechanism.

5. The method of claim 1, wherein the pre-defined threshold is defined on a per-topology basis.

6. The method of claim 1, wherein the DAG rebuild request stops at an ancestor node before reaching the root node.

7. The method of claim 1, wherein the gain factor is a cumulative gain factor.

8. A system comprising:

a processor; and

a computer-readable storage medium storing instructions which, when executed by the processor, cause the processor to perform operations comprising;

identifying a gain factor at a first node in a network represented by a directed acyclic graph (DAG), wherein the gain factor indicates a potential gain that can be obtained in link cost from the first node to a root node of the DAG when an upper node in the DAG changes its routing decision by selecting a different parent node;

when the gain factor exceeds a pre-defined threshold, transmitting a DAG rebuild request from the first node to other nodes in the DAG, wherein the DAG rebuild request recursively travels in an upward direction in the DAG;

determining whether to satisfy the DAG rebuild request based on a number of requesting nodes upon receiving the DAG rebuild request at a second node in the network; and

based on the determining step, at least partially rebuilding the DAG by selecting a new parent node for the second node, wherein the selection of the new parent node causes a decrease in link cost from the first node to the root node.

9. The system of claim 8, wherein identifying the gain factor comprises identifying an actual path cost to the root node.

10. The system of claim 8, wherein the DAG rebuild request recursively travels in the upward direction in the DAG to trigger one or more ancestor nodes of the first node to change their parent node selection.

11. The system of claim 8, wherein transmitting a DAG rebuild request comprises using a routing oscillation avoidance mechanism.

12. The system of claim 8, wherein the pre-defined threshold is defined on a per-topology basis.

13. The system of claim 8, wherein the DAG rebuild request stops at an ancestor node before reaching the root node.

14. The system of claim 8, wherein the gain factor is a cumulative gain factor.

15. A computer-readable storage device storing instructions which, when executed by a processor, cause the processor to perform operations comprising:

identifying a gain factor at a first node in a network represented by a directed acyclic graph (DAG), wherein the gain factor indicates a potential gain that can be obtained in link cost from the first node to a root node of the DAG when an upper node in the DAG changes its routing decision by selecting a different parent node;

when the gain factor exceeds a pre-defined threshold, transmitting a DAG rebuild request from the first node to other nodes in the DAG, wherein the DAG rebuild request recursively travels in an upward direction in the DAG;

determining whether to satisfy the DAG rebuild request based on a number of requesting nodes upon receiving the DAG rebuild request at a second node in the network; and

based on the determining step, at least partially rebuilding the DAG by selecting a new parent node for the second node, wherein the selection of the new parent node causes a decrease in link cost from the first node to the root node.

16. The computer-readable storage device of claim 15, wherein identifying the gain factor comprises identifying an actual path cost to the root node.

17. The computer-readable storage device of claim 15, wherein the DAG rebuild request recursively travels in the upward direction in the DAG to trigger one or more ancestor nodes of the first node to change their parent node selection.

18. The computer-readable storage device of claim 15, wherein transmitting a DAG rebuild request comprises using a routing oscillation avoidance mechanism.

19. The computer-readable storage device of claim 15, wherein the pre-defined threshold is defined on a per-topology basis.

20. The computer-readable storage device of claim 15, wherein the DAG rebuild request stops at an ancestor node before reaching the root node.