Computing risk-sharing metrics in shared-media communication networks

• US 9,391,784 B2
• Filed: 02/23/2012
• Issued: 07/12/2016
• Est. Priority Date: 02/23/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Vasseur, Jean-Philippe
• Primary Examiner(s): Thier, Michael
• Assistant Examiner(s): MYERS, ERIC A
• Application Number:
  US13/403,023
• Publication Number:
  US 20130223225A1
• Time in Patent Office: 1,601 Days
• Field of Search: 370216-248, 370250-252, 370254-256, 370400-401, 370/406, 370/410
• US Class Current: 1/1
• CPC Class Codes: H04L 12/10 Current supply arrangements
• CPC Class Codes: H04L 41/0836 to enhance reliability, e.g. reduce downtime
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04W 4/38 for collecting sensor information
• CPC Class Codes: H04W 4/70 Services for machine-to-machine communication [M2M] or machine type communication [MTC]

Abstract

In one embodiment, a routing node determines a risk-sharing metric between pairs of nodes in a shared-media communication network, and may then compute a plurality of routes that minimizes the risk-sharing metric between the routes, to correspondingly route traffic according to the computed plurality of routes. Additionally, in another embodiment, a particular node in the shared-media communication network may determine a risk-sharing metric between itself and each of one or more other nodes in the shared-media communication network. The particular node may then share the one or more determined risk-sharing metrics with one or more routing nodes in the shared-media communication network, accordingly.

Claims

1. A method, comprising:

determining, by a node, a risk-sharing metric between pairs of nodes in a shared-media communication network, wherein the shared-media communication network is a wireless network or a Power Line Communication (PLC) network and the risk-sharing metric is received from each neighboring node of the pairs of nodes and includes information related to at least geographical position and signal strength that conveys how likely two or more devices in the shared-media communication network are affected by same sources of internal or external interference, wherein the risk-sharing metric for each pair of nodes comprises a value proportional to the signal strength, a value inversely proportional to a corresponding geographical distance determined using the geographical position, or a combination of both;

computing a plurality of routes that minimizes the risk-sharing metric between the routes; and

routing traffic according to the computed plurality of routes.

2. The method as in claim 1, wherein determining comprises:

receiving one or more advertisements from one or more nodes in the shared-media communication network, the advertisements relaying the associated risk-sharing metric between corresponding pairs of neighbor nodes of the respective node sending the advertisement.

3. The method as in claim 1, wherein determining comprises:

querying one or more nodes for their locally determined risk-sharing metrics between pairs of their neighbor nodes.

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

selecting a preferred node for a first computed route; and

querying the preferred node for its locally determined risk-sharing metrics between pairs of its neighbor nodes.

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

receiving an update to the risk-sharing metric between a particular pair of nodes in response to that risk-sharing metric changing by a threshold amount.

6. The method as in claim 1, wherein determining comprises:

querying one or more nodes for one or more of their locally determined least-risk-shared neighbor nodes.

7. The method as in claim 6, wherein querying comprises:

indicating a select subset of nodes from which the queried nodes are to select their locally determined least-risk-shared neighbor nodes.

8. The method as in claim 1, wherein computing comprises:

utilizing one or more routing metrics in addition to the risk-sharing metric when computing the plurality of routes.

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

utilizing a protection scheme selected from 1+1 protection and 1;

1 protection.

10. A method, comprising:

determining a risk-sharing metric between a particular node and each of one or more other nodes in a shared-media communication network, wherein the shared-media communication network is a wireless network or a Power Line Communication (PLC) network and the risk-sharing metric is received from each neighboring node of the pairs of nodes and includes information related to at least geographical position and signal strength that conveys how likely two or more devices in the shared-media communication network are affected by same sources of internal or external interference, wherein the risk-sharing metric for each pair of nodes comprises a value proportional to the signal strength, a value inversely proportional to a corresponding geographical distance determined using the geographical position, or a combination of both; and

sharing the one or more determined risk-sharing metrics with one or more routing nodes in the shared-media communication network.

11. The method as in claim 10, wherein sharing comprises:

sending one or more advertisements from the particular node to the one or more routing nodes.

12. The method as in claim 10, wherein sharing comprises:

replying to a query from the one or more routing nodes.

13. The method as in claim 10, further comprising:

sending an update for a particular risk-sharing metric of the one or more determined risk-sharing metrics in response to that risk-sharing metric changing by a threshold amount.

14. The method as in claim 10, wherein sharing comprises:

receiving a query from a particular routing node for one or more least-risk-shared neighbor nodes of the particular node;

determining the one or more least-risk-shared neighbor nodes of the particular node; and

replying to the query with the determined one or more least-risk-shared neighbor nodes of the particular node.

15. The method as in claim 14, wherein the received query indicates a select subset of nodes from which the particular node is to select its least-risk-shared neighbor nodes.

16. The method as in claim 10, wherein determining comprises:

receiving one or more noise event notifications from each of the one or more other nodes; and

determining the risk-sharing metric for each other node by correlating the noise event notifications.

17. The method as in claim 10, wherein the one or more other nodes are determined as a set of nodes selected from a group consisting of:

next-hop neighbor nodes;

n-hop neighbor nodes;

reachable neighbor nodes; and

all nodes of the communication network.

18. The method as in claim 10, further comprising:

determining a risk-sharing metric between pairs of the one or more other nodes in the shared-media communication network;

computing a plurality of routes that minimizes the risk-sharing metric between the routes; and

routing traffic according to the computed plurality of routes.

19. An apparatus, comprising:

one or more network interfaces to communicate in a shared-media communication network, wherein the shared-media communication network is a wireless network or a Power Line Communication (PLC) network;

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;

determine a risk-sharing metric between pairs of nodes in the shared-media communication network, wherein the risk-sharing metric is received from each neighboring node of the pairs of nodes and includes information related to at least geographical position and signal strength that conveys how likely two or more devices in the shared-media communication network are affected by same sources of internal or external interference, wherein the risk-sharing metric for each pair of nodes comprises a value proportional to the signal strength, a value inversely proportional to a corresponding geographical distance determined using the geographical position, or a combination of both;

compute a plurality of routes that minimizes the risk-sharing metric between the routes; and

route traffic according to the computed plurality of routes.

20. An apparatus, comprising:

one or more network interfaces to communicate in a shared-media communication network, wherein the shared-media communication network is a wireless network or a Power Line Communication (PLC) network;

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;

determine a risk-sharing metric between the apparatus and each of one or more other nodes in the shared-media communication network, wherein the risk-sharing metric is received from each neighboring node of the pairs of nodes and includes information related to at least geographical position and signal strength that conveys how likely two or more devices in the shared-media communication network are affected by same sources of internal or external interference, wherein the risk-sharing metric for each pair of nodes comprises a value proportional to the signal strength, a value inversely proportional to a corresponding geographical distance determined using the geographical position, or a combination of both;

share the one or more determined risk-sharing metrics with one or more routing nodes in the shared-media communication network.