Dynamic enabling of routing devices in shared-media communication networks

• US 9,264,349 B2
• Filed: 07/05/2011
• Issued: 02/16/2016
• Est. Priority Date: 07/05/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Shaffer, Shmuel
• Primary Examiner(s): Lam, Yee
• Application Number:
  US13/176,253
• Publication Number:
  US 20130010590A1
• Time in Patent Office: 1,687 Days
• Field of Search: 370/255, 370/256, 370/400, 370/401, 370/408, 709/224, 709/252
• US Class Current: 1/1
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership

Abstract

In one embodiment, a non-repeated reachability probe is transmitted from a particular node into a shared-media network, where nodes that receive the probe are configured to reply to the particular node. Based on determining a set of one or more nodes in the shared-media network that received the probe, one or more routing nodes of the set may be selected to act as routers in the shared-media network, and notified of their selection.

Claims

1. A method, comprising:

transmitting a non-repeated reachability probe from a particular node into a shared-media network, the shared-media network connecting a plurality of nodes, wherein nodes that receive the non-repeated reachability probe are configured to reply to the particular node;

determining a set of one or more nodes in the shared-media network that received the non-repeated reachability probe;

determining, at the particular node, a minimum number of required nodes of the plurality of nodes that must act as routers in order to reach each of the plurality of nodes in the shared-media network;

selecting, by the particular node, one or more routing nodes of the set of one or more nodes to act as the routers in the shared-media network based on the minimum number of required nodes;

notifying, by the particular node, the selected one or more routing nodes of the one or more routing nodes of their selection;

subsequently, dynamically adjusting, by the particular node, the minimum number of required nodes of the plurality of nodes that are selected as the one or more routing nodes of the set of one or more nodes based on network conditions; and

wherein the steps of the transmitting the non-repeated reachability probe and the selecting the one or more routing nodes in response to a trigger selected from a group consisting of;

a timer;

determination that a number of unreachable nodes in the shared-media network has exceeded a first threshold;

a determination that link quality in the shared-media network is below a second threshold;

a detection of network perturbations;

one or more new devices in the shared-media network;

one or more of the one or more routing nodes are removed from the shared-media network; and

a detection of one or more isolated nodes in the shared-media network.

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

requesting that the selected one or more routing nodes send out a corresponding second non-repeating reachability probe into the shared-media network.

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

receiving, at the particular node from a routing node of the selected routing nodes, a second set of one or more nodes in the shared-media network that received the second non-repeated reachability probe;

selecting one or more second routing nodes of the second set of one or more nodes to act as the routers in the shared-media network; and

notifying the selected second routing nodes of their selection.

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

requesting that the selected one or more routing nodes select and notify a second set of nodes to act as the routers in the shared-media network based on receipt of the second non-repeated reachability probe.

5. The method as in claim 1, wherein the shared-media network is a power-line communication (PLC) network.

6. The method as in claim 1, wherein the particular node is a head-end node in the shared-media network.

7. The method as in claim 1, wherein the particular node is a routing node of the one or more routing nodes in the shared-media network having received notification that was selected as a router.

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

determining, in advance, the each of the plurality of nodes in the shared-media network; and

selecting the one or more routing nodes to ensure reachability to the each of the plurality of nodes.

9. The method as in claim 8, further comprising:

transmitting a repeated reachability probe into the shared-media network to determine identify the each of the plurality of nodes in the network.

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

creating a directed acyclic graph (DAG) based on the selected one or more routing nodes.

11. An apparatus, comprising:

one or more network interfaces to communicate in a shared-media computer network;

a processor coupled to the one or more 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;

transmit a non-repeated reachability probe into the shared-media network, the shared-media network connecting a plurality of nodes, wherein nodes that receive the non-repeated reachability probe are configured to reply to the particular node;

determine a set of one or more nodes in the shared-media network that received the non-repeated reachability probe;

determine a minimum number of required nodes of the plurality of nodes that must act as routers in order to reach each of the plurality of nodes in the shared-media network;

select one or more routing nodes of the set of one or more nodes to act as the routers in the shared-media network based on the minimum number of required nodes;

notify the selected one or more routing nodes of the one or more nodes of their selection;

subsequently, dynamically adjust the minimum number of required nodes of the plurality of nodes that are selected as the one or more routing nodes of the set of one or more nodes based on network conditions; and

wherein the steps of the transmit the non-repeated reachability probe and the select the one or more routing nodes in response to a trigger selected from a group consisting of;

a timer;

determination that a number of unreachable nodes in the shared-media network has exceeded a first threshold;

a determination that link quality in the shared-media network is below a second threshold;

a detection of network perturbations;

one or more new devices in the shared-media network;

one or more of the one or more routing nodes are removed from the shared-media network; and

a detection of one or more isolated nodes in the shared-media network.

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

request that the selected one or more routing nodes send out a corresponding second non-repeating reachability probe into the shared-media network.

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

propagate the selection of routing nodes in the shared-media network by one of either;

a) receiving, from a routing node of the selected routing nodes, a second set of one or more nodes in the shared-media network that received the second non-repeated reachability probe;

selecting one or more second routing nodes of the second set of one or more nodes to act as the routers in the shared-media network; and

notifying the selected second routing nodes of their selection; and

b) requesting that the selected one or more routing nodes select and notify the

second set of one or more nodes to act as the routers in the shared-media network based on receipt of the second non-repeated reachability probe.

14. The apparatus as in claim 11, wherein the shared-media network is a power-line communication (PLC) network.

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

create a directed acyclic graph (DAG) based on the selected one or more routing nodes.

16. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:

transmit a non-repeated reachability probe into the shared-media network, wherein nodes that receive the non-repeated reachability probe are configured to reply to the particular node;

determine a set of one or more nodes in the shared-media network that received the non-repeated reachability probe;

determine a minimum number of required nodes of the plurality of nodes that must act as routers in order to reach each of the plurality of nodes in the shared-media network;

select one or more routing nodes of the set of one or more nodes to act as the routers in the shared-media network based on the minimum number of required nodes;

notify the selected one or more routing nodes of the one or more nodes of their selection;

subsequently, dynamically adjust the minimum number of required nodes of the plurality of nodes that are selected as the one or more routing nodes of the set of one or more nodes based on network conditions; and

wherein the steps of the transmit the non-repeated reachability probe and the select the one or more routing nodes in response to a trigger selected from a group consisting of;

a timer;

determination that a number of unreachable nodes in the shared-media network has exceeded a first threshold;

a determination that link quality in the shared-media network is below a second threshold;

a detection of network perturbations;

one or more new devices in the shared-media network;

one or more of the one or more routing nodes are removed from the shared-media network; and

a detection of one or more isolated nodes in the shared-media network.

17. The tangible, non-transitory, computer-readable media as in claim 16, wherein the software when executed is further operable to:

request that the selected one or more routing nodes send out a corresponding second non-repeating reachability probe into the shared-media network.

18. The tangible, non-transitory, computer-readable media as in claim 17, wherein the software when executed is further operable to:

propagate the selection of routing nodes in the shared-media network by one of either;

a) receiving, from a routing node of the selected routing nodes, a second set of one or more nodes in the shared-media network that received the second non-repeated reachability probe;

selecting one or more second routing nodes of the second set to act as the routers in the shared-media network; and

notifying the selected second routing nodes of their selection; and

b) requesting that the selected one or more routing nodes select and notify the second set of one or more nodes to act as the routers in the shared-media network based on receipt of the second non-repeated reachability probe.

19. The tangible, non-transitory, computer-readable media as in claim 16, wherein the software when executed is further operable to:

create a directed acyclic graph (DAG) based on the selected one or more routing nodes.