Method and system for an adaptive wireless routing protocol in a mesh network

• US 7,668,173 B2
• Filed: 12/01/2005
• Issued: 02/23/2010
• Est. Priority Date: 12/01/2005
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Azalea Networks
• Inventors: Zhao, Fuyong
• Primary Examiner(s): Ahmed; Salman
• Application Number:
  US11/291,747
• Publication Number:
  US 20070127503A1
• Time in Patent Office: 1,545 Days
• Field of Search: 370/395.31, 370/238, 370/237, 370/331, 370/395.21, 370/406, 370/351, 370/400, 370/216, 370/236, 455/432.1, 709/238
• US Class Current: 370/395.21
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 84/22 with access to wired networks

Abstract

A method and system for an adaptive wireless routing protocol in a mesh network are disclosed. In one embodiment, the method comprises routing datagrams between a plurality of nodes in a mesh network. Update messages are routed to one or more of the plurality of nodes, wherein the update messages include hello packets and update packets.

Claims

1. A method, comprising:

routing datagrams between a plurality of nodes in a mesh network;

receiving a routing packet that contains distance information and messenger information associated with a destination node of the plurality of nodes;

routing the routing packet to one or more of the plurality of nodes;

maintaining a highest sequence number route and a least metric route to the destination node of the plurality of nodes using the distance information and the messenger information contained in the routing packet, wherein the highest sequence number route is a freshest route to the destination node and the least metric route is a least cost route to the destination node; and

updating a routing path to the destination node using the highest sequence number route and the least metric route.

2. The method of claim 1, wherein the routing packet establishes and maintains neighbor relationships.

3. The method of claim 1 further comprising maintaining routing tables in each node of the plurality of nodes.

4. The method of claim 3, wherein the routing tables include a destination IP address, a destination mark, a router ID, a highest sequence number route, a least metric route, an immediate update flag, and messenger information.

5. The method of claim 2, wherein the routing packet is a hello packet, a periodic update packet, an immediate trigger update packet, or a normal triggered update packet.

6. The method of claim 1, wherein routing datagrams comprises choosing the highest destination sequence number route.

7. The method of claim 1, further comprising monitoring if links with one or more neighbor nodes are broken.

8. The method of claim 7, further comprising performing a local repair procedure when links to the destination node are broken.

9. A computer-readable medium having stored thereon a plurality of instructions, said plurality of instructions when executed by a computer, cause said computer to perform:

routing datagrams between a plurality of nodes in a mesh network;

receiving a routing packet that contains distance information and messenger information associated with a destination node of the plurality of nodes;

routing the routing packet to one or more of the plurality of nodes;

maintaining a highest sequence number route and a least metric route to the destination node of the plurality of nodes using the distance information and the messenger information contained in the routing packet, wherein the highest sequence number route is a freshest route to the destination node and the least metric route is a least cost route to the destination node; and

updating a routing path to the destination node using the highest sequence number route and the least metric route.

10. The computer-readable medium of claim 9, wherein the routing packet establishes and maintains neighbor relationships.

11. The computer-readable medium of claim 9, having stored thereon-additional instructions, said additional instructions when executed by a computer for routing datagrams, cause said computer to further perform maintaining routing tables in each node of the plurality of nodes.

12. The computer-readable medium of claim 11, wherein the routing tables include a destination IP address, a destination mark, a router ID, a highest sequence number route, a least metric route, an immediate update flag, and messenger information.

13. The computer-readable medium of claim 10, wherein the routing packet is a hello packet, a periodic update packet, an immediate trigger update packet, or a normal triggered update packet.

14. The computer-readable medium of claim 9, having stored thereon-additional instructions, said additional instructions when executed by a computer for routing datagrams, cause said computer to further perform choosing the highest destination sequence number route.

15. The computer-readable medium of claim 9, having stored thereon-additional instructions, said additional instructions when executed by a computer, cause said computer to further perform monitoring if links with one or more neighbor nodes are broken.

16. The computer-readable medium of claim 10 having stored thereon-additional instructions, said additional instructions when executed by a computer, cause said computer to further perform performing a local repair procedure when links to the destination node are broken.

17. A mesh router, comprising:

a processor;

memory coupled to the processor; and

a bus coupling the processor and memory;

wherein the memory stores instructions that are executed by the processor to route datagrams between a plurality of nodes in a mesh network;

to receive a routing packet that contains distance information and messenger information associated with a destination node of the plurality of nodes;

to route the routing packet to one or more of the plurality of nodes;

to maintain a highest sequence number route and a least metric route to the destination node of the plurality of nodes using the distance information and the messenger information contained in the routing packet, wherein the highest sequence number route is a freshest route to the destination node and the least metric route is a least cost route to the destination node; and

to update a routing path to the destination node using the highest sequence number route and the least metric route.

18. The router of claim 17, wherein the routing packet establishes and maintains neighbor relationships.

19. The router of claim 17, wherein routing tables are stored in the memory.

20. The router of claim 19, wherein the routing tables include a destination IP address, a destination mark, a router ID, a highest sequence number route, a least metric route, an immediate update flag, and messenger information.

21. The method of claim 18, wherein the routing packet is a hello packet, a periodic update packet, an immediate trigger update packet, or a normal triggered update packet.

22. The method of claim 17, wherein the routing path is the highest destination sequence number route.

23. The method of claim 17, further comprising monitoring if links with one or more neighbor nodes are broken.

24. The method of claim 23, further comprising performing a local repair procedure when links to the destination node are broken.