Reliable message distribution in an ad hoc mesh network

• US 20050174972A1
• Filed: 02/08/2005
• Published: 08/11/2005
• Est. Priority Date: 02/09/2004
• Status: Abandoned Application

• Current Assignee: Lee Boynton
• Original Assignee: Lee Boynton
• Inventors: Boynton, Lee
• Application Number:
  US11/054,080
• Publication Number:
  US 20050174972A1
• Time in Patent Office: Days
• US Class Current: 370/337
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/323 Discarding or blocking control packets, e.g. ACK packets
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A Data Distribution Service (DDS) transfers information between nodes in an ad hoc mobile mesh network. The DDS includes many different novel features including techniques for coalescing retransmit requests to minimize traffic, providing a reasonable level of reliability for event oriented communications, multicasting retransmissions for use by many nodes, and providing other optimizations for multicast traffic. The DDS uses UDP datagrams for communications. Communications operate in a truly peer-to-peer fashion without requiring central authority or storage, and can be purely ad hoc and not depend on any central server. The protocol is NACK-based, which is more suited to a mesh network than a traditional approach like TCP, which uses positive acknowledgements of all data. The DDS is amenable to very long recovery intervals, matching well with nodes on wireless networks that lose coverage for significant periods of time and also works well with constantly changing network topologies. Reliability can also be handled over a span of time that might correspond to losing wireless coverage.

Claims

1. A network processing node, comprising:

a processor sending Data Distribution Service (DDS) messages associated with data items contained in the network processing node, the DDS messages identifying a global revision value associated with a revision status for multiple different data items in the network processing node and data-revision numbers that identify revision status for the individual data items.

2. The network processing node according to claim 1 wherein the DDS messages include different node identifiers that are associated with different global revision values.

3. The network processing node according to claim 1 wherein the processor sends a STATUS message that identifies the network processing node sending the STATUS message and the global revision value associated with the last revision to the data items in the identified network processing node.

4. The network processing node according to claim 1 wherein the processor sends a DATA message that identifies:

the node sending the DATA message,

a global revision value for the node sending the DATA message,

a data-name identifying a data item contained in the DATA message,

a data-revision value for the data item, and

the actual data item identified by the data-name.

5. The network processing device according to claim 1 wherein the processor receives a Negative Acknowledge (NACK) message that identifies global revision values for data that was not successfully received.

6. The network processing device according to claim 5 wherein the NACK message identifies the network processing node associated with the identified global revision values.

7. The network processing device according to claim 5 wherein the NACK message contains a group of multiple global revision values each associated with the same or different data items that have not been successfully received.

8. The network processing device according to claim 5 wherein the processor sends a CHANGE message identifying for the global revision values identified in the NACK message a data-name identifying a data item and a data-revision number for the identified data item.

9. The network processing device according to claim 8 wherein the processor receives a RETRANSMIT message that identifies the data-names in the CHANGE message that are requested to be retransmitted, the processor in response to the RETRANSMIT message sending a DATA message that contains the data items for the identified data-names.

10. The network processing device according to claim 8 wherein the processor only sends global revision values and associated data-names in the CHANGE message only for the latest versions of the data items associated with the global revision values in the NACK message.

11. The network processing device according to claim 8 wherein the processor maintains time stamps for the data items and sends out EXPIRED messages for requested updates to data items with expired time stamps.

12. An ad-hoc mesh network, comprising:

multiple mobile nodes that operate in wireless peer-to-peer manner within the mesh network whereby the nodes can dynamically move out of the mesh network and are automatically reconfigured to resume communications after moving back into the mesh network,

at least some of the nodes operating a Data Distribution Service (DDS) that sends and receives DDS messages that use Global Revision Values (GRVs) for tracking changes to groups of different data items located on different nodes and for maintaining consistent versions of the data items on the different nodes.

13. The mesh network according to claim 12 wherein the DDS messages identify data-revision values for individual data items associated with the GRVs.

14. The mesh network according to claim 12 wherein a STATUS or DATA message is multicast by a source node to other receiver nodes in the mesh network that identifies a latest GRV for the source node.

15. The mesh network according to claim 12 wherein the receiver nodes compare the GRV for the source node to a local GRV value tracked for the same source node and send a Negative Acknowledge (NACK) message to the source node identifying any missing GRV values.

16. The mesh network according to claim 15 wherein each receiver node waits a random time delay period before sending the NACK messages and suppresses their NACK messages when another NACK message identifying the same GRV values is received from another receiver node prior to expiration of the random time delay period.

17. The mesh network according to claim 15 wherein the source node sends a CHANGE message to the receiver nodes that identifies only the data-names and data-revision numbers for the latest versions of data items associated with the GRV values identified in the NACK message.

18. The mesh network according to claim 15 wherein the source node identifies invalid locally stored data items and sends out an EXPIRED message for any of the GRV values in the NACK message that are associated with invalid data items.

19. The mesh network according to claim 18 wherein the source node generates time stamps for locally stored data items and invalidates data items that have expired time stamps.

20. A method for sending messages in a mesh network, comprising:

receiving a wireless message that identifies a global revision number for a remote set of multiple different data items located in a remote wireless device, the global revision number associated with a latest change made to any one of the data items;

comparing the received global revision number with a locally stored global revision number corresponding with a remote device sending the wireless message; and

sending a notice message when the received global revision number is different than the locally stored global revision number, the notice message identifying the global revision numbers associated with data items that have not yet been received from the remote device.

21. The method according to claim 20 including randomly varying a delay time for sending the notice message and suppressing the notice message when another notice message is received from another node identifying the same global revision numbers for the same remote device.

22. The method according to claim 20 including receiving a change message back from the remote device that identifies data names and associated data version numbers associated with the global revision numbers in the notice message.

23. The method according to claim 22 including using the data names and associated data version numbers to identify only a latest version of data items that have not yet been received from the remote device and sending a retransmit message to the remote device that contains the data names for the identified data items.

24. The method according to claim 23 including receiving a data message back from the remote device containing the data items for the data names identified in the retransmit message.