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

• US 8,743,866 B2
• Filed: 11/22/2010
• Issued: 06/03/2014
• 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): Kizou, Hassan
• Assistant Examiner(s): BOOK, PHYLLIS A
• Application Number:
  US12/951,198
• Publication Number:
  US 20120039186A1
• Time in Patent Office: 1,289 Days
• Field of Search: 370/229, 370/230, 370/230.1, 370/235, 370/237, 370/238, 370/254, 370/255, 370/256, 370/310, 370/310.2, 370/311, 370/312, 370/328, 370351-360, 370/389, 370/390, 370/392, 370/393, 370/395.1, 370/395.3, 370/395.31, 370/395.32, 370/395.5, 370/395.51, 370/395.52, 370/395.53, 370/395.6, 370/395.63, 370/395.64, 370/395.7, 370/395.71, 370/395.72, 370396-409, 370/411, 709/230, 709/232, 709/235, 709238-244, 709250-253
• US Class Current: 370/351
• 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 an advertisement at a node in a network, the advertisement comprising a metric value and a gain factor, wherein the metric value indicates a path cost to a root node of the network, and wherein the metric value is advertised only when it exceeds a threshold;

determining at the node a local link cost and a local gain factor for each link of the node;

computing a resulting path cost from the node to the root node and a cumulative gain factor based on the metric value, the gain factor, the local link cost, and the local gain factor; and

advertising the resulting path cost and the cumulative gain factor at the node to another node in the network.

2. The method of claim 1, wherein the gain factor is indicative of a difference between an advertised path cost and an actual path cost to the root node.

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

receiving additional advertisements, each of the additional advertisements comprising an additional metric value and an additional gain factor, wherein the additional metric value indicates an additional path cost to the root node, and wherein the resulting path cost and the cumulative gain factor are computed further based on the additional metric value and the additional gain factor.

4. The method of claim 1, wherein the network is represented by a directed acyclic graph, and wherein advertising comprises:

requesting a rebuild of the directed acyclic graph when one of the resulting path cost and the cumulative gain factor surpasses a threshold.

5. The method of claim 4, wherein the rebuild

is requested for one of a portion and an entirety of the directed acyclic graph.

6. The method of claim 1, wherein the resulting path cost is advertised when one of the resulting path cost and the cumulative gain factor exceeds the threshold.

7. The method of claim 6, wherein the threshold is a dual-threshold comprising an upper threshold and a lower threshold surrounding one of the resulting path cost and the cumulative gain factor.

8. An apparatus comprising:

a network interface;

a processor coupled to the network interface 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 network;

receive an advertisement, the advertisement comprising a path cost to a root node of the network and a gain factor, wherein the path cost is advertised only when it exceeds a threshold;

determine at the node a local link cost and a local gain factor for each link of the node;

compute a resulting path cost from the node to the root node and a cumulative gain factor at the node based on the path cost, the gain factor, the local link cost, and the local gain factor; and

advertise the resulting path cost and the cumulative gain factor at the node to another node in the network.

9. The apparatus of claim 8, wherein the gain factor is indicative of a difference between an advertised path cost and an actual path cost to the root node.

10. The apparatus of claim 8, wherein the local link cost is an

actual link cost costs.

11. The apparatus of claim 8, wherein the network is represented by a directed acyclic graph, and wherein the process when executed is further operable to:

request a rebuild of the directed acyclic graph when one of the resulting path cost and the cumulative gain factor surpasses a threshold.

12. The apparatus of claim 11, wherein the

rebuild is requested for one of a portion and an entirety of the DAG.

13. The apparatus of claim 8, wherein the resulting path cost comprises a metric value, and wherein the resulting path cost is advertised when the metric value exceeds the threshold.

14. The apparatus of claim 13, wherein the threshold is a dual-threshold comprising an upper threshold and a lower threshold surrounding the metric value.

15. A method, comprising:

receiving an advertisement at a node in a network, the advertisement comprising a metric value and a gain factor, wherein the metric value indicates a path cost to a root node of the network, and wherein the gain factor is indicative of a difference between the metric value and an actual path cost to the root node;

determining at the node a local link cost and a local gain factor for each link of the node;

computing a resulting path cost from the node to the root node and an associated gain factor by adding the local link cost and the local gain factor to the metric value and the gain factor, respectively; and

advertising the resulting path cost and the associated gain factor at the node to other nodes in the network.

16. The method of claim 15, wherein the network is represented by a directed acyclic graph, and wherein advertising comprises:

requesting a rebuild of the directed acyclic graph when one of the resulting path cost and the associated gain factor surpasses a threshold.

17. The method of claim 16, wherein the rebuild

is requested for one of a portion and an entirety of the directed acyclic graph.

18. An apparatus comprising:

a network interface;

a processor coupled to the network interface 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 network;

receive an advertisement, the advertisement comprising a path cost to a root node of the network and a gain factor indicative of a difference between the path cost and an actual path cost to the root node;

determine at the node a local link cost and a local gain factor for each link of the node;

compute a resulting path cost from the node to the root node and an associated gain factor by adding the local link cost and the local gain factor to the path cost and the gain factor, respectively; and

advertise the resulting path cost and the associated gain factor at the node to other nodes in the network.

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

request a rebuild of the directed acyclic graph when one of the resulting path cost and the associated gain factor surpasses a threshold.

20. The apparatus of claim 19, wherein the

rebuild is requested for one of a portion and an entirety of the directed acyclic graph.