Providing a backup network topology without service disruption

• US 9,176,832 B2
• Filed: 03/15/2013
• Issued: 11/03/2015
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Dasgupta, Sukrit
• Primary Examiner(s): Bonzo, Bryce
• Assistant Examiner(s): Amoroso, Anthony J
• Application Number:
  US13/839,053
• Publication Number:
  US 20140281670A1
• Time in Patent Office: 963 Days
• Field of Search: 714/4.11
• US Class Current: 1/1
• CPC Class Codes: G06F 11/2002 where interconnections or communication control functionality are redundant flexible arrangements for bus networks involving redundancy H04L12/40176
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

In one embodiment, a primary root node may detect one or more neighboring root nodes based on information received from a first-hop node and may select a backup root node among the neighboring root nodes. Once selected, the backup root node may send the primary root node a networking identification and a corresponding group mesh key which the primary root node may forward to the first-hop nodes to cause the first-hop nodes to migrate to the backup root node when connectivity to the primary root node fails. In addition, the first-hop root nodes may migrate back to the primary root node when connectivity to the primary root node is restored.

Claims

1. A method, comprising:

detecting, by a primary root node, one or more neighboring root nodes based on information received from first-hop nodes in a shared-media communication network;

selecting a backup root node from the neighboring root nodes;

receiving a network identification and a corresponding mesh group key from the backup root node; and

notifying the first-hop nodes of the backup root node along with the network identification and the corresponding mesh group key to cause the first-hop nodes to migrate to the backup root node when connectivity to the primary root node fails, while maintaining a subordinate state.

2. The method of claim 1, further comprising:

determining restored connectivity of the primary root node; and

sending a message to the first-hop nodes indicating restored connectivity to trigger migration back to the primary root node.

3. The method of claim 1, wherein selecting the backup root node further comprises:

receiving a notification from the first-hop nodes of potential backup root nodes; and

selecting the backup root node based on the potential backup root node received from the most first-hop nodes.

4. The method of claim 1, wherein selecting the backup root node further comprises:

determining a total path cost associated with one or more neighboring root nodes; and

selecting the backup root node based on the determined total path costs.

5. The method of claim 1, wherein selecting the backup root node further comprises:

sending a message to one or more neighboring root nodes to determine resource availability; and

selecting the backup root node based on resource availability.

6. The method of claim 1, further comprising:

sending an instruction to the backup root node to operate as a backup root node; and

receiving an acknowledgment message from the backup root node, wherein notifying the first-hop nodes at the backup root node is in response to the acknowledgement message.

7. The method of claim 1, further comprising:

sending a message to a management node indicating the selected backup root node to cause the management node to send an instruction to the backup root node to operate as a backup root node; and

receiving an acknowledgment message that the backup root node has received the instruction, wherein notifying the first-hop nodes at the backup root node is in response to the acknowledgment message.

8. An apparatus, comprising:

one or more network interfaces to communicate with a shared-media communication 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;

detect neighboring root nodes based on information received from first-hop nodes in a shared-media communication network;

select a backup root node from the neighboring root nodes; and

in response to receiving a networking identification and a corresponding mesh group key from the backup root node, notify the first-hop nodes of the backup root node along with the received network identification and the corresponding mesh group key to cause the first-hop nodes to migrate to the backup root node when connectivity to the primary root node fails.

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

determine restored connectivity of the primary root node; and

send a message to the first-hop nodes indicating restored connectivity to trigger migration back to the primary root node.

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

receive a notification from the first-hop nodes of potential backup root nodes; and

select the backup root node based on the potential backup root node received from the most first-hop nodes.

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

determine a path cost associated with one or more neighboring root nodes; and

select the backup root node based on the determined total path costs.

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

send a message to one or more neighboring root nodes to determine resource availability; and

select the backup root node based on resource availability.

13. A method, comprising:

sending, by a first hop node, information identifying one or more neighboring root nodes to a primary root node;

receiving a first message from the primary root node indicating a backup root node along with a network identification and a corresponding mesh group key associated with the backup root node;

determining a connectivity failure to the primary root node; and

in response to determining the connectivity failure, migrating to the backup root node, while maintaining a state of a subordinate network.

14. The method of claim 13, further comprising:

receiving a second message from the primary root node indicating restored connectivity to the primary root node; and

in response to receiving the second message, migrating back to the primary root node.

15. The method of claim 13, wherein determining a connectivity failure to the primary root node further comprises:

sending a message to one or more neighboring nodes to test connectivity to primary root node;

detecting a communication failure to the primary root node; and

confirming the communication failure by the one or more neighboring nodes.

16. The method of claim 14, further comprising:

receiving a selection metric regarding the backup root node to cause the migration back to the primary root node.

17. An apparatus, comprising:

one or more network interfaces to communicate with a shared-media communication 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;

send information identifying one or more neighboring root nodes to a primary root node;

determine a connectivity failure to the primary root node, in response to receiving a first message from the primary root node indicating a backup root node along with a network identification and a corresponding mesh group key associated with the backup root node; and

migrating to the backup root node while maintaining a state of a subordinate network, in response to determining a connectivity failure,

wherein the apparatus is a first hop node.

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

migrate back to the primary root node, in response to receiving a second message from the primary root node indicating restored connectivity to the primary root node.

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

send a message to one or more neighboring nodes to test connectivity to primary root node;

detect a communication failure to the primary root node; and

confirm the communication failure by the one or more neighboring nodes.

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

cause migration back to the primary root node, in response to receiving a selection metric regarding the backup root node.