SYSTEM AND METHOD FOR PACKET DELIVERY BACKTRACKING

• US 20130128726A1
• Filed: 12/07/2012
• Published: 05/23/2013
• Est. Priority Date: 05/17/2006
• Status: Active Grant

• Current Assignee: Rajant Corporation
• Original Assignee: Rajant Corporation
• Inventors: Parks, Joseph E., HELLHAKE, Paul R., Lamb, Martin A., Acker, David
• Granted Patent: US 9,001,645 B2
• Time in Patent Office: Days
• US Class Current: 370/225
• CPC Class Codes: H04B 1/00 Details of transmission systems, not covered by a single one of groups H04B3/00 - H04B13/00; Details of transmission systems not characterised by the medium used for transmission
• CPC Class Codes: H04L 2001/0097 Relays
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• CPC Class Codes: H04L 61/25 of the same type
• CPC Class Codes: H04L 61/5014 using dynamic host configuration protocol [DHCP] or bootstrap protocol [BOOTP]
• CPC Class Codes: H04L 61/5061 Pools of addresses
• CPC Class Codes: H04W 28/04 Error control
• CPC Class Codes: H04W 28/18 Negotiating wireless communication parameters
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes
• CPC Class Codes: H04W 72/00 Local resource management
• CPC Class Codes: H04W 76/20 Manipulation of established connections
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

Traditional computer networks have been designed with the need for highly reliable packet delivery. This is largely handled by a centrally managed simple send-acknowledge protocol. In a highly dynamic mesh network, these methods are inadequate to ensure the most reliable packet delivery. This invention uses the natural redundancy of routes in a mesh and other techniques to increase the reliability of a network, even as the paths to any given node are dynamic in nature.

Claims

1. A method for ensuring reliable and efficient packet delivery of data over highly mobile mesh networks, in which each network comprises two or more network nodes, in which each of said nodes contains at least one transceiver device and a processor that implements a data communications protocol to communicate data to other network devices in an ad-hoc network, and in which the data are divided into data packets, with each data packet being encoded with a protocol header that includes that packet'"'"'s source address, destination, cost information, and data flags that indicate a type and other attributes of said each data packet, the method comprising:

(a) maintaining, at each of said nodes, a bridge table with entries for all encountered nodes, routes for all known nodes, alternate routes for all known nodes, and flags for indicating nodes that are undiscovered;

(b) encoding, in each data packet, source and destination nodes and a set of flags that encode packet features, the packet features comprising an indication of whether the packet is unrouteable, discovery, introduction, or mesh/client;

(c) updating the bridge table based on successful and unsuccessful routing of the packets to both known and unknown nodes;

(d) routing failed packets via a known alternate route; and

(e) sending undeliverable packets back toward a source of the packets, when a route to the destination is not known, in an effort to both mark the failed route and to find an alternate route to the destination node device.

2. A method as in claim 1, wherein a discovery packet is a data packet with a discovery flag set, and further comprising:

(f) when all alternate and known routes to a destination node have failed, changing unroutable flagged packets to discovery flagged packets and broadcasting the discovery flagged packets throughout the network, in an effort to find a new route to a new or formerly known destination node;

(g) when a discovery flagged packet is received by a node that is not the destination for that packet, rebroadcasting the discovery packet from the node;

(h) when a discovery flagged packet is received by a node that is the destination for that packet, sending another packet type from the node, an introduction packet, back to the source of the discovery packet and locally delivering the discovery packet as a normal data packet; and

(i) when any node receives an introduction packet, updating the bridge table in that node based on the new routing information for the sender of that packet and, if the node is not the destination for that packet, relaying that packet toward the destination based on normal routing for that packet.

3. A method as in claim 1, wherein:

the processor at one of the nodes, if not the originator of the undeliverable packet, will check its bridge table for a stored alternate route to the destination;

given an alternate route, the packet is sent to the alternate address;

if successfully routed, the alternate route is updated to a primary route in the bridge table; and

if unsuccessfully routed, the data packet is sent back toward the originator of the packet.

4. A method as in claim 1, wherein:

the processor at one of the nodes, if the originator of the undeliverable packet, will update the packet sequence number of the packet and mark it as a discovery packet; and

the originator will then broadcast this packet to all nodes in range, in an attempt to find a route to the destination node.

5. A method as in claim 1, wherein:

if the processor at one of the nodes receives a broadcast discovery packet targeted to a non-local destination, the processor looks for the destination address in its bridge table;

if the destination address is found, the packet is sent to the destination device; and

if the destination address is not found, the packet is rebroadcast to all nearby mesh network nodes.

6. A method as in claim 1, wherein, when the processor at one of the nodes receives a broadcast discovery packet targeted to a local destination, the processor sends an introduction packet back to the originator of the data packet and then delivers that data packet.

7. A method as in claim 1, wherein:

when the processor at one of the nodes receives an introduction packet, the processor updates its bridge tablet to reflect the good route to that node; and

if that node is not the node originating the discovery packet that generated the introduction packet, the node sends the introduction packet back toward the originator.

8. A node for use in a highly mobile mesh network for ensuring reliable and efficient packet delivery of data over the highly mobile mesh network, in which each network comprises two or more of said nodes, said node comprising:

at least one transceiver device; and

a processor that implements a data communications protocol to communicate data to other network devices in an ad-hoc network, and in which the data are divided into data packets, with each data packet being encoded with a protocol header that includes that packet'"'"'s source address, destination, cost information, and data flags that indicate a type and other attributes of said each data packet, the processor being configured for;

(a) maintaining a bridge table with entries for all encountered nodes, routes for all known nodes, alternate routes for all known nodes, and flags for indicating nodes that are undiscovered;

(b) encoding, in each data packet, source and destination nodes and a set of flags that encode packet features, the packet features comprising an indication of whether the packet is unrouteable, discovery, introduction, or mesh/client;

(c) updating the bridge table based on successful and unsuccessful routing of the packets to both known and unknown nodes;

(d) routing failed packets via a known alternate route; and

(e) sending undeliverable packets back toward a source of the packets, when a route to the destination is not known, in an effort to both mark the failed route and to find an alternate route to the destination node device.

9. A node as in claim 8, wherein a discovery packet is a data packet with a discovery flag set, and wherein the processor is further configured for:

(f) when all alternate and known routes to a destination node have failed, changing unroutable flagged packets to discovery flagged packets and broadcasting the discovery flagged packets throughout the network, in an effort to find a new route to a new or formerly known destination node;

(g) when a discovery flagged packet is received by a node that is not the destination for that packet, rebroadcasting the discovery packet from the node;

(h) when a discovery flagged packet is received by a node that is the destination for that packet, sending another packet type from the node, an introduction packet, back to the source of the discovery packet and locally delivering the discovery packet as a normal data packet; and

(i) when any node receives an introduction packet, updating the bridge table in that node based on the new routing information for the sender of that packet and, if the node is not the destination for that packet, relaying that packet toward the destination based on normal routing for that packet.

10. A node as in claim 8, wherein the processor is further configured such that:

the processor, if not the originator of the undeliverable packet, will check its bridge table for a stored alternate route to the destination;

given an alternate route, the packet is sent to the alternate address;

if successfully routed, the alternate route is updated to a primary route in the bridge table; and

if unsuccessfully routed, the data packet is sent back toward the originator of the packet.

11. A node as in claim 8, wherein the processor is further configured such that:

the processor, if the originator of the undeliverable packet, will update the packet sequence number of the packet and mark it as a discovery packet; and

the originator will then broadcast this packet to all nodes in range, in an attempt to find a route to the destination node.

12. A node as in claim 8, wherein the processor is further configured such that:

if the processor at one of the nodes receives a broadcast discovery packet targeted to a non-local destination, the processor looks for the destination address in its bridge table;

if the destination address is found, the packet is sent to the destination device; and

if the destination address is not found, the packet is rebroadcast to all nearby mesh network nodes.

13. A node as in claim 8, wherein the processor is further configured such that, when the processor at one of the nodes receives a broadcast discovery packet targeted to a local destination, the processor sends an introduction packet back to the originator of the data packet and then delivers that data packet.

14. A node as in claim 8, wherein the processor is further configured such that:

when the processor at one of the nodes receives an introduction packet, the processor updates its bridge tablet to reflect the good route to that node; and

if that node is not the node originating the discovery packet that generated the introduction packet, the node sends the introduction packet back toward the originator.