ROUTE OPTIMIZATION FOR ON-DEMAND ROUTING PROTOCOLS FOR MESH NETWORKS

• US 20080107034A1
• Filed: 01/16/2008
• Published: 05/08/2008
• Est. Priority Date: 07/20/2005
• Status: Active Grant

• Current Assignee: FireTide Incorporated (UNICOM Global, Inc.)
• Original Assignee: FireTide Incorporated (UNICOM Global, Inc.)
• Inventors: Natarajan, Mohan, Jetcheva, Jorjeta, Kanodia, Sachin, Repakula, Murali
• Granted Patent: US 7,995,501 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04L 49/1584 Full Mesh, e.g. knockout
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/023 Limited or focused flooding to selected areas of a network
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 40/34 Modification of an existing route
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Various embodiments implement a set of low overhead mechanisms to enable on-demand routing protocols. The on-demand protocols use route accumulation during discovery floods to discover when better paths have become available even if the paths that the protocols are currently using are not broken. In other words, the mechanisms (or “Route Optimizations”) enable improvements to routes even while functioning routes are available. The Route Optimization mechanisms enable nodes in the network that passively learn routing information to notify nodes that need to know of changes in the routing information when the changes are important. Learning routing information on up-to-date paths and determining nodes that would benefit from the information is performed, in some embodiments, without any explicit control packet exchange. One of the Route Optimization mechanisms includes communicating information describing an improved route from a node where the improved route diverges from a less nearly optimal route.

Claims

1. A method comprising:

in a first node of a mesh network, determining a first route from a source node to a destination node;

determining a second route from the source node to the destination node;

comparing the first route to the second route according to a comparison criteria;

in a second node of the mesh network;

if the comparing determines that the second route is better than the first route, then conditionally communicating an improved route to a plurality of recipients;

wherein the improved route is the second route;

wherein the comparison criteria comprises a count of hops between nodes; and

wherein the conditionally communicating is conditional based in part on determining a node of divergence between the first route and the second route, and the second node is the node of divergence.

2. The method of claim 1, wherein the conditionally communicating is further conditional based in part on a retry-attempt-count being less than a predetermined threshold.

3. The method of claim 1, wherein the determining the second route is in the first node.

4. The method of claim 1, wherein the comparing is in the first node.

5. A system comprising:

a wireless mesh network having a first node and a second node;

wherein each of the nodes comprises a respective wireless interface enabling communication with at least two other nodes;

wherein each of the nodes comprises a respective processing element executing wireless mesh networking functions;

wherein the networking functions comprise

a path determination function to determine a path between two nodes of the wireless mesh network,

a path comparison function to compare a first path determined by the path determination function with a second path determined by the path determination function, and

a path dissemination function to control distribution of path information to nodes of the wireless mesh network;

wherein the path comparison function comprises comparing hop counts between nodes;

wherein the path dissemination function conditionally distributes a new path to a plurality of recipients when the path comparison function indicates a better path is available; and

the conditional distribution is based on determining that a node is a first point of divergence between the new path and a previous path.

6. The system of claim 5, wherein the path dissemination function further conditionally distributes the new path when a retry-attempt-count is less than a predetermined threshold.

7. The system of claim 5, wherein at least one of the new path and the previous path is limited to a single link.

8. The system of claim 5, wherein at least one of the new path and the previous path comprises a plurality of links.

9. The system of claim 5, wherein the networking functions further comprise a path accumulation function to accumulate path information referenced by the path comparison function.

10. The system of claim 9, wherein the path accumulation function comprises generating a packet.

11. The system of claim 9, wherein the path accumulation function comprises observing a packet.

12. The system of claim 9, wherein the accumulated path information comprises topology information.

13. The system of claim 9, wherein the accumulated path information comprises a network address of a forwarding node.

14. The system of claim 5, wherein the recipients comprise actively communicating nodes.

15. The system of claim 5, wherein the networking functions further comprise a recipient selection function to select the recipients.

16. The system of claim 5, wherein at least one of the recipients provides a service.

17. The system of claim 16, wherein the service is at least one of an Internet connectivity service and a web proxy service.

18. The system of claim 5, wherein the recipients are all nodes of the mesh network that are currently reachable.

19. The system of claim 5, wherein the networking functions are specified by a computer readable medium.

20. The system of claim 19, further comprising the computer readable medium.