# US 2015/0103813 A1 · Route optimization for on-demand routing protocols for mesh networks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0103813 A1
- Document ID: US20150103813A1
- Status: Published application
- Kind: A1
- Application number: 14/286,461
- Filed: 2014-05-23
- Published: 2015-04-16
- Earliest claimed: 2005-07-20
- Assignees: Firetide, Inc.
- Applicants: Firetide, Inc.
- Inventors: Jorjeta Gueorguieva Jetcheva; Sachin Kanodia; Murali Sundaramoorthy Repakula; Mohan Natarajan
- Web page: https://patentgrep.com/patent/US20150103813A1

## CPC

- H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops
- H04L 45/22: {Alternate routing}
- H04L 45/26: {Route discovery packet}
- H04L 45/36: {Backward learning}
- H04L 49/1584: {Full Mesh, e.g. knockout}
- H04W 24/02: Arrangements for optimising operational condition
- H04W 40/02: Communication route or path selection, e.g. power-based or shortest path routing
- H04W 40/023: {Limited or focused flooding to selected areas of a network}
- H04W 40/28: for reactive routing
- H04W 40/38: adapting due to varying relative distances between nodes
- H04W 40/34: Modification of an existing route
- H04W 84/18: Self-organising networks, e.g. ad-hoc networks or sensor networks
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## 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

### Claim 1

(canceled)

### Claim 2

A system comprising:
a wireless mesh network of nodes;
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 node of divergence function to determine when the node is a first node of divergence between a current best path and a previous best path, and
a path dissemination function to conditionally distribute the current best path at least in response to a determination that the current best path has changed from the previous best path and a determination that the node is the first node of divergence; and
wherein the first node of divergence has least a first link, a second link, and a third link to respective others of the nodes, the current best path comprises the first link and the second link, and the previous best path comprises the first link and the third link.

### Claim 3 (depends on 2)

The system of claim 2, wherein the path dissemination function conditionally distributes a new path to a plurality of recipients when a better path is available.

### Claim 4 (depends on 2)

The system of claim 2, wherein the wireless mesh networking functions further comprise a path determination function to determine a path between two nodes of the wireless mesh network.

### Claim 5 (depends on 4)

The system of claim 4, wherein the wireless mesh networking functions further comprise 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.

### Claim 6 (depends on 2)

The system of claim 2, wherein the conditional distribution is further conditioned on a determination that a retry-attempt-count is less than a predetermined threshold.

### Claim 7 (depends on 2)

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

### Claim 8 (depends on 2)

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

### Claim 9 (depends on 2)

The system of claim 2, wherein the wireless mesh networking functions further comprise a path comparison function to provide an 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.

### Claim 10 (depends on 2)

The system of claim 2, wherein the wireless mesh networking functions further comprise a path comparison function to provide an 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.

### Claim 11 (depends on 3)

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

### Claim 12 (depends on 11)

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

### Claim 13 (depends on 2)

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

### Claim 14 (depends on 13)

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

### Claim 15

A device enabled to operate as one of the nodes of a wireless mesh network, the device comprising:
a wireless interface enabled to communicate with respective others of the nodes via at least a first link, a second link, and a third link; 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, comprising the first link and the second link, and a previous best path, comprising the first link and the third link, and
a path dissemination function to conditionally distribute the current best path at least in response to a determination that the current best path has changed from the previous best path and a determination that the device is the first node of divergence.

### Claim 16 (depends on 15)

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

### Claim 17 (depends on 15)

The device of claim 15, wherein the conditional distribution is further conditioned on a determination that a retry-attempt-count is less than a predetermined threshold.

### Claim 18 (depends on 15)

The device of claim 15, wherein the conditional distribution is via a route reply, and only a single route reply is sent for the current best path, even when others of the nodes detect the current best path has changed from the previous best path.

### Claim 19

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, the first route comprising a first link and a second link between a particular one of the nodes and respective others of the nodes;
in any one or more of the nodes, computing a second route from the source node to the destination node, the second route comprising the first link and a third link between the particular one of the nodes and respective others of the nodes;
in the particular node of the nodes, determining when the particular node is a first node of divergence between the first route and the second route; 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.

### Claim 20 (depends on 19)

The method of claim 19, 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.

### Claim 21 (depends on 19)

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