METHOD AND APPARATUS TO REDUCE CUMULATIVE EFFECT OF DYNAMIC METRIC ADVERTISEMENT IN SMART GRID/SENSOR NETWORKS

• US 20120039186A1
• Filed: 11/22/2010
• Published: 02/16/2012
• 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
• Granted Patent: US 8,743,866 B2
• Time in Patent Office: Days
• US Class Current: 370/248
• 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

In one embodiment, a node in a computer network represented by a directed acyclic graph (DAG) may receive advertisements of smoothed path costs to a root node of the DAG, where the advertisements contain a field for a virtual gain factor (VGF) indicative of a difference between the smoothed path cost and an actual best path cost to the root. The node may then determine a local smoothed path cost from itself to the root, and also a local VGF for each link of the node (for the path as a whole including the particular link) based on all of the received advertisements and VGFs, as well as corresponding actual link costs (e.g., based on selecting alternative parents or actual link costs being smoothed within a dual threshold). The node may then compute a resulting smoothed path cost to the root along with an associated (cumulative) VGF based on the locally determined cost and VGF. Accordingly, the node may then advertise the resulting smoothed path cost along with the associated (cumulative) VGF on each link such that, for example, any node receiving a resulting smoothed path cost and/or VGF that surpasses a threshold may request a rebuild of the DAG (e.g., a portion or in its entirety).

Claims

1. A method, comprising:

receiving one or more advertisements of smoothed path costs to a root node of a computer network represented by a directed acyclic graph (DAG) at a node in the network, each advertisement containing a field for a virtual gain factor (VGF);

determining a local smoothed path cost from the node to the root node and a local VGF for each link of the node;

computing a resulting smoothed path cost to the root node along with an associated VGF at the node based on the locally determined cost and locally determined VGF; and

advertising the resulting smoothed path cost along with the associated VGF at the node to other nodes in the network.

2. The method as in claim 1, wherein each VGF is indicative of a difference between the smoothed path cost and an actual best path cost to the root node.

3. The method as in claim 1, wherein the associated VGF is a cumulative VGF.

4. The method as in claim 1, wherein advertising comprises:

requesting a rebuild of the DAG when one of the resulting smoothed path cost and associated VGF surpasses a threshold.

5. The method as in claim 4, wherein requesting the rebuild comprises:

requesting a rebuild of one of a portion and an entirety of the DAG.

6. The method as in claim 1, wherein the smoothed path costs are metric values and wherein the smoothed path costs are advertised when the metric values exceed a threshold.

7. The method as in claim 6, wherein the threshold is a dual-threshold comprising upper and lower thresholds surrounding each metric value.

8. An apparatus, comprising:

one or more network interfaces;

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;

operate as a node of a computer network represented by a directed acyclic graph (DAG);

receive one or more advertisements of smoothed path costs to a root node of the network, wherein each advertisement contains a field for a virtual gain factor (VGF);

determine a local smoothed path cost from the node to the root node and a local VGF for each link of the node;

compute a resulting smoothed path cost to the root node along with an associated VGF at the node based on the locally determined cost and locally determined VGF; and

advertise the resulting smoothed path cost along with the associated VGF at the node to other nodes in the network.

9. The apparatus as in claim 8, wherein each VGF is indicative of a difference between the smoothed path cost and an actual best path cost to the root node.

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

determine the local smoothed path cost and local VGF based on the received advertisements and received VGFs, as well as corresponding actual link costs.

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

request a rebuild of the DAG when one of the resulting smoothed path cost and associated VGF surpasses a threshold.

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

request a rebuild of one of a portion and an entirety of the DAG.

13. The apparatus as in claim 8, wherein the smoothed path costs are metric values and wherein the smoothed path costs are advertised when the metric values exceed a threshold.

14. The apparatus as in claim 13, wherein the threshold is a dual-threshold comprising upper and lower thresholds surrounding each metric value.

15. A method, comprising:

receiving an advertisement of smoothed path cost to a root node of a computer network represented by a directed acyclic graph (DAG) at a node in the network, the advertisement containing a field for a virtual gain factor (VGF) indicative of a difference between the smoothed path cost and an actual best path cost to the root node;

determining a local smoothed path cost from the node to the root node and a local VGF for each link of the node based on the received advertisement and received VGF, as well as corresponding actual link cost;

computing a resulting smoothed path cost to the root node along with an associated VGF at the node by adding the locally determined cost and locally determined VGF to the received smoothed path cost and received VGF; and

advertising the resulting smoothed path cost along with the associated VGF at the node to other nodes in the network.

16. The method as in claim 15, wherein advertising comprises:

requesting a rebuild of the DAG when one of the resulting smoothed path cost and associated VGF surpasses a threshold.

17. The method as in claim 16, wherein requesting the rebuild comprises:

requesting a rebuild of one of a portion and an entirety of the DAG.

18. An apparatus, comprising:

one or more network interfaces;

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;

operate as a node of a computer network represented by a directed acyclic graph (DAG);

receive an advertisement of smoothed path cost to a root node of the network, wherein the advertisement contains a field for a virtual gain factor (VGF) indicative of a difference between the smoothed path cost and an actual best path cost to the root node;

determine a local smoothed path cost from the node to the root node and a local VGF for each link of the node based on the received advertisement and is received VGF, as well as corresponding actual link cost;

compute a resulting smoothed path cost to the root node along with an associated VGF at the node by adding the locally determined cost and locally determined VGF to the received smoothed path cost and received VGF; and

advertise the resulting smoothed path cost along with the associated VGF at the node to other nodes in the network.

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

request a rebuild of the DAG when one of the resulting smoothed path cost and associated VGF surpasses a threshold.

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

request a rebuild of one of a portion and an entirety of the DAG.