Configuration of failure and acquire timeouts to facilitate recovery from failures in hierarchical mesh networks

• US 20060215581A1
• Filed: 08/26/2005
• Published: 09/28/2006
• Est. Priority Date: 03/23/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Castagnoli, Neal Dante
• Granted Patent: US 7,505,450 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 41/0663 Performing the actions predefined by failover planning, e.g. switching to standby network elements
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 7/0083 taking measures against momentary loss of synchronisation, e.g. inhibiting the synchronisation, using idle words or using redundant clocks
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 56/0015 one node acting as a reference for the others
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Methods, apparatuses and systems directed to providing an efficient failure recovery mechanism in hierarchical wireless mesh networks. In one implementation, the present invention mitigates the effect of synchronization loss between a parent and child node on the hierarchical wireless mesh network. In one implementation, the present invention employs a configuration scheme whereby the parent node failure timeouts are greater than the time to acquire a parent node to mitigate the effect of synchronization loss on downstream nodes in the hierarchical mesh network.

Claims

1. A method for mitigating synchronization loss between a parent and child node in a hierarchical wireless mesh network, the method comprising

monitoring, in a maintenance state, for a scheduling message from a parent routing node to maintain synchronization with the parent routing node;

upon failure to receive a scheduling message from the parent routing node within a failure time interval, entering a synchronization state for an acquire time interval to attempt to re-acquire the parent routing node;

entering the maintenance state if the parent routing node is re-acquired; and

wherein the acquire time interval is less than the failure time interval.

2. The method of claim 1 further comprising

if the parent routing node is not re-acquired, selecting a neighboring routing node as a tentative parent routing node;

and

entering the synchronization state for the acquire time interval with the tentative parent routing node.

3. The method of claim 1 wherein the synchronization state comprises

transmitting at least one request to the parent routing node;

and

monitoring for a response to the request from the parent routing node.

4. The method of claim 1 wherein the acquire time interval is less than or equal to one half of the failure time interval.

5. The method of claim 1 wherein the maintenance state further comprises transmitting slot scheduling messages to at least one child routing node.

6. The method of claim 1 wherein the maintenance state further comprises

computing a data slot schedule based on information contained in the scheduling messages received from the parent routing node;

and

transmitting data to, and receiving data from, the parent routing node according to the data slot schedule.

7. The method of claim 5 wherein the maintenance state further comprises

computing a data slot schedule based on information contained in the scheduling messages received from the parent routing node;

and

transmitting data to, and receiving data from, the parent routing node according to the data slot schedule.

8. The method of claim 7 wherein the maintenance state further comprises

transmitting data to, and receiving data from, to at least one child node according to the data slot schedule.

9. The method of claim 1 further comprising discovering neighboring routing nodes.

10. A wireless routing node for use in a hierarchical wireless mesh network, comprising

a wireless network interface for communicating with a parent routing node;

one or more processors;

a memory;

a routing node application, stored in the memory, comprising instructions operable to cause the one or more processors and the wireless network interface to

execute a maintenance state comprising monitoring for a scheduling message from a parent routing node to maintain synchronization with the parent routing node;

upon failure to receive a scheduling message from the parent routing node within a failure time interval, enter a synchronization state for an acquire time interval to attempt to re-acquire the parent routing node;

enter the maintenance state if the parent routing node is re-acquired;

wherein the acquire time interval is less than the failure time interval.

11. The wireless routing node of claim 10 wherein the routing node application further comprises instructions operable to cause the one or more processors and the wireless network interface to

if the parent routing node is not re-acquired, select a neighboring routing node as a tentative parent routing node;

and

enter the synchronization state for the acquire time interval with the tentative parent routing node.

12. The wireless routing node of claim 10 wherein the routing node application further comprises instructions operable to cause the one or more processors and the wireless network interface, in the synchronization state, to

transmit at least one request to the parent routing node;

monitor for a response to the request from the parent routing node.

13. The wireless routing node of claim 10 wherein the acquire time interval is less than or equal to one half of the failure time interval.

14. The wireless routing node of claim 10 wherein the routing node application further comprises instructions operable to cause the one or more processors and the wireless network interface, in the maintenance state, to

transmit scheduling messages to at least one child routing node.

15. The wireless routing node of claim 10 wherein the routing node application further comprises instructions operable to cause the one or more processors and the wireless network interface, in the maintenance state, to

compute a data slot schedule based on information contained in the scheduling messages received from the parent routing node;

and

transmit data to, and receiving data from, the parent routing node according to data slot schedule.

16. The wireless routing node of claim 14 wherein the routing node application further comprises instructions operable to cause the one or more processors and the wireless network interface, in the maintenance state, to

compute a data slot schedule based on information contained in the scheduling messages received from the parent routing node;

and

transmit data to, and receiving data from, the parent routing node according to the data slot schedule.

17. The wireless routing node of claim 16 wherein the routing node application further comprises instructions operable to cause the one or more processors and the wireless network interface, in the maintenance state, to

transmit data to, and receiving data from, to at least one child node according to the data slot schedule.

18. The wireless routing node of claim 10 wherein the routing node application further comprises instructions operable to cause the one or more processors and the wireless network interface to discover neighboring routing nodes.

19. A wireless routing node for use in a hierarchical wireless mesh network, comprising

means for wirelessly communicating with a parent routing node;

means for executing a maintenance state comprising monitoring for a slot scheduling message from a parent routing node to maintain synchronization with the parent routing node;

synchronization means for synchronizing with a selected routing node to attempt to acquire, during an acquire time interval, the routing node as a parent routing node;

means for triggering the synchronization means upon detection of synchronization loss with a parent routing node after a failure time interval,

wherein the acquire time interval is less than the failure time interval.

20. The wireless routing node of claim 19 further comprising

means for discovering neighboring wireless routing nodes.

21. The wireless routing node of claim 19 wherein the acquire time interval is less than or equal to one half of the failure time interval.

22. The wireless routing node of claim 19 wherein the maintenance state further comprises transmitting slot scheduling messages to at least one child routing node.

23. The wireless routing node of claim 19 wherein the maintenance state further comprises

computing a data slot schedule based on information contained in the slot scheduling messages received from the parent routing node;

and

transmitting data to, and receiving data from, the parent routing node according to data slot schedule.

24. The wireless routing node of claim 22 wherein the maintenance state further comprises

computing a data slot schedule based on information contained in the slot scheduling messages received from the parent routing node;

and

transmitting data to, and receiving data from, the parent routing node according to the data slot schedule.

25. The wireless routing node of claim 24 wherein the maintenance state further comprises

transmitting data to, and receiving data from, to at least one child node according to the data slot schedule.