Route optimization for on-demand routing protocols for mesh networks

• US 8,737,268 B2
• Filed: 08/08/2011
• Issued: 05/27/2014
• Est. Priority Date: 07/20/2005
• Status: Active Grant

• Current Assignee: FireTide Incorporated (UNICOM Global, Inc.)
• Original Assignee: FireTide Incorporated (UNICOM Global, Inc.)
• Inventors: Jetcheva, Jorjeta Gueorguieva, Kanodia, Sachin, Repakula, Murali Sundaramoorthy, Natarajan, Mohan
• Primary Examiner(s): Elallam, Ahmed
• Application Number:
  US13/204,902
• Publication Number:
  US 20120176931A1
• Time in Patent Office: 1,023 Days
• Field of Search: 370/229, 370/235, 370/237, 370/238, 370/252, 370/254, 370/255, 370/315, 370/338, 455/3.01, 709/238, 709/239, 709/241, 709/242, 709/243
• US Class Current: 370/255
• 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 system comprising:

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

wherein each of the nodes comprises a respective processing element enabled to execute wireless mesh networking functions;

wherein the wireless mesh 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,

a node divergence function to determine when a node is a first node of divergence between the first path and the second path, the first node of divergence being a one of the nodes having at least first, second, and third links to respective other nodes of the wireless mesh network, and the first path and the second path commonly comprise the first link and respectively comprise the second link and the third link, and

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

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

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

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

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

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

5. The system of claim 1, wherein the wireless mesh networking functions further comprise a path comparison function to provide the indication of availability of a better path and a path accumulation function to generate a packet.

6. The system of claim 1, wherein the wireless mesh networking functions further comprise a path comparison function to provide the indication of availability of a better path and a path accumulation function to observe a packet.

7. The system of claim 1, wherein the wireless mesh networking functions further comprise a path comparison function to provide the indication of availability of a better path, and a path accumulation function to accumulate path information referenced by the path comparison function;

and wherein the accumulated path information comprises topology information.

8. The system of claim 1, wherein the wireless mesh networking functions further comprise a path comparison function to provide the indication of availability of a better path, and a path accumulation function to accumulate path information referenced by the path comparison function;

and wherein the accumulated path information comprises a network address of a forwarding node.

9. The system of claim 1, wherein the recipients comprise actively communicating nodes.

10. The system of claim 1, wherein at least one of the recipients provides a service.

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

12. The system of claim 1, wherein the recipients are all nodes of the wireless mesh network that are currently reachable.

13. The system of claim 1, wherein the wireless networking functions are specified by a computer readable medium.

14. The system of claim 13, further comprising the computer readable medium.

15. A method comprising:

in a mesh network of nodes, in any one or more of the nodes, computing a first route from a source node of the nodes to a destination node of the nodes;

in any one or more of the nodes, computing a second route from the source node to the destination node;

in a particular node of the nodes, determining when the particular node is a first node of divergence between the first route and the second route, the first node of divergence being a node of the mesh network having at least first, second, and third links to respective other nodes of the mesh network, and the first route and the second route commonly comprise the first link and respectively comprise the second link and the third link; and

further in the particular node, in response to ascertaining that the second route is an improved route with respect to the first route, conditionally communicating the improved route to a plurality of recipients such that the particular node communicates the improved route when the determining is positive, and the particular node is silent about the improved route when the determining is negative.

16. The method of claim 15, further comprising, in any one or more of the nodes, comparing the first route to the second route according to a comparison criteria, and wherein the comparison criteria comprises a count of hops between the source node and the destination node.

17. The method of claim 15, wherein the first node compares the first route to the second route and performs the computing the second route.

18. A device enabled to operate in a wireless mesh network of nodes, the device enabled to perform as one of the nodes, the device comprising:

a wireless interface enabled to communicate with other of the nodes; and

a processing element enabled to execute wireless mesh networking functions, the wireless mesh networking functions comprising;

a node of divergence function to determine when the device is a first node of divergence between a current best path and a previous best path, the first node of divergence being a one of the nodes having at least first, second, and third links to respective others of the nodes, and the current best path and the previous best path commonly comprise the first link and respectively comprise the second link and the third link, and

a path dissemination function to conditionally distribute the current best path at least in response to a concurrent determination that;

a) the current best path has changed from the previous best path, b) the node of divergence function has determined that the device is the first node of divergence between the current best path and the previous best path, and c) a retry-attempt-count is less than a predetermined threshold, and wherein the conditional distribution is via a route reply, and only a single route reply is sent for the current best path, even when other of the nodes detect the current best path has changed from the previous best path.

19. The device of claim 18, wherein when the device is a source node of a particular traffic flow of a plurality of active traffic flows, the device is enabled to use the current best path immediately.