Efficient broadcast of data in a communication network

• US 8,340,131 B2
• Filed: 05/01/2009
• Issued: 12/25/2012
• Est. Priority Date: 05/05/2008
• Status: Expired due to Fees

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Sentilla Corp. (Telefonaktiebolaget LM Ericsson)
• Inventors: Sharp, Courtney, Ostrander, Jason, Polastre, Joseph
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): Ghafoerkhan, Faiyazkhan
• Application Number:
  US12/434,397
• Publication Number:
  US 20090274158A1
• Time in Patent Office: 1,334 Days
• Field of Search: None
• US Class Current: 370/474
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04W 8/205 Transfer to or from user equipment or user record carrier

Abstract

A system (and a method) are disclosed for reliably disseminating a state of a node in a large network consisting of nodes with constrained resources. The system comprises a process embodied by a state machine comprised of an advertise state, a request state, and a share state. The system processes input events, mutates its internal state, and outputs side effects. The outputs from one node in the network may become inputs events to one or more other nodes in the network. Viral dissemination is an emergent behavior across the nodes in a network that all independently and continuously perform these input processings, state mutations, and output side effects.

Claims

1. A method for disseminating first data of a first remote node to a local node in a network, the first remote node storing the first data, a first index, and a first version identifier in a first remote node storage, the first index uniquely identifying the first data across all versions of that data, the method comprising:

storing second data, a second index, and a second version identifier in a local node storage, the second index uniquely identifying the second data across all versions of that data;

receiving a first message advertising the first index and first version identifier corresponding to the first data stored in the first remote node storage;

determining, in response to receiving the first message and the first index corresponding to the second index, whether the first version identifier indicates a newer version than the second version identifier;

transmitting, in response to the first version identifier indicating a newer version than the second version identifier, a second message requesting the first data corresponding to the first version identifier and first index;

receiving a third message sharing the first data corresponding to the first version identifier and first index;

updating, in response to receiving the third message, the second data, the second index, and the second version identifier stored in the local node storage with the first data, first index, and the first version identifier received in the third message;

transmitting, in response to the updating, a fourth message advertising the first index and first version identifier;

receiving a fifth message advertising a third index and a third version identifier corresponding to third data stored in a second remote node storage;

determining, in response to receiving the fifth message, whether the third index and third version identifier indicate the same version as the first index and first version identifier; and

pausing, in response to the third index and third version identifier indicating the same version as the first index and first version identifier, the transmission of the fourth message for a period of time.

2. The method of claim 1, further comprising:

verifying, in response to updating the second data, the second index, and the second version identifier with the first data, the first index, and the first version identifier, that the complete first data is received.

3. The method of claim 1, further comprising:

verifying that the received first data is error free.

4. The method of claim 1, further comprising:

determining, in response to receiving the fifth message, whether the third version identifier indicates an older version than the second version identifier; and

transmitting, in response to the third version identifier indicating an older version than the second version identifier, a sixth message sharing the second data corresponding to the second data identifier stored in the local node storage.

5. The method of claim 1, wherein the period of time comprises a bounded random period of time.

6. A method for disseminating data in a network, the method comprising:

storing the first data, a first index, and a first version identifier in a local node storage, the first index uniquely identifying the first data across all versions of that data;

transmitting a first message advertising the first index and the first version identifier corresponding to the first data stored in the local node storage;

receiving a second message requesting second data corresponding to a second index and a second version identifier from the first remote node in the network, the second index uniquely identifying the second data across all versions of that data;

determining, in response to receiving the second message, whether the second index and second version identifier indicate the same version as the first index and first version identifier;

transmitting, in response to the second index and second version identifier indicating the same version as the first index and first version identifier, a third message sharing the first data stored in the local node storage;

receiving a fourth message advertising a third index and a third version identifier corresponding to third data stored in a second remote node storage;

determining, in response to receiving the fourth message, whether the third index and the third version identifier indicates a newer version than the first index and first version identifier;

transmitting, in response to the third index corresponding to the first index and the third version identifier indicating a newer version than the first version identifier, a fifth message requesting third data corresponding to the third index and the third version identifier;

receiving a sixth message sharing the third data corresponding to the third index and third version identifier;

updating, in response to receiving the sixth message, the first data, the first index, and the first version identifier stored in the local node storage with the third data, the third index, and the third version identifier received in the sixth message; and

transmitting a seventh message advertising the third data corresponding to the third index and third version identifier.

7. The method of claim 6, further comprising:

verifying, in response to the first data, first index, and the first version identifier being updated with the third data, third index, and the third version identifier, that the complete third data is received.

8. The method of claim 6, further comprising:

verifying that the received third data is error free.

9. The method of claim 6, wherein the local node is a mote.

10. The method of claim 6, wherein the network is a lossy network.

11. The method of claim 6, wherein the network is an epidemic network.

12. A data communication system for disseminating first data of a first node in a network comprising:

a state machine that comprises an advertise state, a request state, and a share state;

a storage module for storing the first data, as well as a first index and a first version identifier, both corresponding to the first data, wherein the first index uniquely identifies the first data across all versions of that data;

a logic module for processing the first data corresponding to the first index and the first version identifier according to a viral dissemination protocol;

a network interface in communication with the logic module adapted to receive second data corresponding to a second index and a second version identifier from a second node in the network and to transmit the first data, first index, and the first version identifier in the network, wherein the second index uniquely indentifies the second data across all versions of that data;

a comparison module in communication with the logic module for comparing the second version identifier received via the network interface with the first version identifier stored in the storage module, responsive to the second index corresponding to the first index; and

an invocation module in communication with the logic module and the state machine for invoking a state handler to handle a state transition action responsive to the comparison module comparing the second version identifier received via the network interface with the first version identifier stored in the storage module, wherein the state transition action comprises;

transitioning the state machine to the request state responsive to the second version identifier indicating a newer version than the first version identifier, transitioning the state machine to the share state responsive to second version identifier indicating an older version than the first version identifier, and transitioning the state machine to the advertise state responsive to the second version identifier indicating a same version as the first version identifier, wherein the invocation module is configured for invoking a specialized handler upon complete and valid reception of a new version of data.

13. The system of claim 12, further comprising:

a managing module for managing timeout in communication with invocation module and the network interface, the managing module causing the network interface module to pause transmission of the first index and the first version identifier for a period of time responsive to transitioning to the advertise state.

14. The system of claim 12, wherein the first node is a mote.

15. The system of claim 12, wherein the network is an epidemic network.

16. A non-transitory computer-readable storage medium configured to store instructions for disseminating data in a network, the instructions when executed by a processor cause the processor to:

store the first data, a first index, and a first version identifier in a local node storage, the first index uniquely identifying the first data across all versions of that data;

transmit a first message advertising the first index and the first version identifier corresponding to the first data stored in the local node storage;

receive a second message requesting second data corresponding to a second index and a second version identifier from the first remote node in the network, the second index uniquely identifying the second data across all versions of that data;

determine, in response to receiving the second message and the second index corresponding to the first index, whether the second version identifier indicates the same version as the first version identifier;

transmit, in response to the second version identifier indicating the same version as the first version identifier, a third message sharing the first data stored in the local node storage;

receive a fourth message advertising a third index and a third version identifier corresponding to third data stored in a second remote node storage;

determine, in response to receiving the fourth message, whether the third index and the third version identifier indicates a newer version than the first index and first version identifier;

transmit, in response to the third index corresponding to the first index and the third version identifier indicating a newer version than the first version identifier, a fifth message requesting third data corresponding to the third index and the third version identifier;

receive a sixth message sharing the third data corresponding to the third index and third version identifier;

update, in response to receiving the sixth message, the first data, the first index, and the first version identifier stored in the local node storage with the third data, the third index, and the third version identifier received in the sixth message; and

transmit a seventh message advertising the third data corresponding to the third index and third version identifier.

17. A non-transitory computer-readable storage medium configured to store instructions for disseminating first data of a first remote node to a local node in a network, the first remote node storing the first data, a first index, and a first version identifier in a first remote node storage, the instructions when executed by a processor cause the processor to:

store second data, a second index, and a second version identifier in a local node storage;

receive a first message advertising the first index and first version identifier corresponding to the first data stored in the first remote node storage;

determine, in response to receiving the first message, whether the first index and the first version identifier indicates a newer version than the second version identifier;

transmit, in response to the first version identifier indicating a newer version than the second version identifier, a second message requesting the first data corresponding to the first index and the first version identifier;

receive a third message sharing the first data corresponding to the first index and first version identifier;

update, in response to receiving the third message, the second data, the second index, and the second version identifier stored in the local node storage with the first data, the first index, and the first version identifier received in the third message;

transmit, in response to the updating, a fourth message advertising the first index and first version identifier;

receive a fifth message advertising a third index and a third version identifier corresponding to third data stored in a second remote node storage;

determine, in response to receiving the fifth message, whether the third index and third version identifier indicate the same version as the first index and first version identifier; and

pausing, in response to the third index and third version identifier indicating the same version as the first index and first version identifier, the transmission of the fourth message for a period of time.

18. The non-transitory computer-readable storage medium of claim 17, the instructions when executed further cause the processing system to:

determine, in response to receiving the fifth message, whether the third version identifier indicates an older version than the first version identifier; and

transmit, in response to the third version identifier indicating an older version than the first version identifier, a sixth message sharing the first data corresponding to the first data identifier stored in the local node storage.