Selection of information for transmission and storage in an ad-hoc network based upon local synopsis exchange

• US 7,835,351 B2
• Filed: 07/03/2006
• Issued: 11/16/2010
• Est. Priority Date: 07/03/2006
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Liu, Juan, Huang, Qingfeng, Greene, Daniel H., Reich, James E., Mosko, Marc E.
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): Sloms; Nicholas
• Application Number:
  US11/428,440
• Publication Number:
  US 20080002635A1
• Time in Patent Office: 1,597 Days
• Field of Search: 370/254
• US Class Current: 370/389
• CPC Class Codes: H04L 67/04 specially adapted for terminals or networks with limited capabilities; specially adapted for terminal portability
• 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: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method of managing traffic in an ad-hoc network includes receiving, at a local node, a received synopsis of data sample updates in a neighbor storage of a neighboring node, the synopsis being based at least in part on dynamic priorities associated with the data samples. The received synopsis is then compared with data sample updates in a local storage of the local node and the local node determines which data samples will be transmitted.

Claims

1. A method of managing traffic in an ad-hoc network, comprising:

receiving, at a local node, a received synopsis of updates to data contained in data samples in a neighbor storage of a neighboring node, wherein the received synopsis is a list of compressed representations of data sample updates stored at the neighboring node and sorted using dynamic priorities associated with the data samples,

wherein a data sample is individual portion of data generated by applications on data source nodes;

generating a local synopsis of data sample updates in a storage at the local node;

comparing the received synopsis with the local synopsis of data sample updates in a local storage of the local node; and

determining which data samples the local node will transmit based upon the comparing, and

wherein generating the local synopsis further comprises;

computing a hash of some portion of information associated with a data sample, and computing a hash of a stream identifier associated with a data source and a timestamp for each update to produce a list of hashes representing the updates stored in the local storage.

2. The method of claim 1, the method further comprising combining the received synopsis with an update message to form a piggybacked update message.

3. The method of claim 1, the method further comprising storing data sample updates by only storing a data sample update for one or more data source streams having the most recent time stamp.

4. The method of claim 1, further comprising storing the updates until the dynamic priorities associated with the updates become less than or equal to a threshold.

5. The method of claim 1, wherein the received synopsis is sorted on the local node based at least in part on criteria that will sort recently generated data samples to the bottom of the local storage.

6. The method of claim 1, wherein the local synopsis is sorted on the local node based at least in part on criteria that will sort recently generated data samples to the bottom of the local storage.

7. The method of claim 5, wherein the criteria assigns updates a value zero until a predetermined time period has elapsed.

8. The method of claim 6, wherein the criteria assigns updates a value zero until a predetermined time period has elapsed.

9. The method of claim 1, the method further comprising:

when the local node holds a first unmatched difference in a sort order, transmitting a batch of differences from the local storage.

10. The method of claim 9, the method comprising limiting a rate at which batches of differences are transmitted.

11. The method of claim 1, the method further comprising:

when the received synopsis holds a first unmatched difference in a sort difference, transmitting a local synopsis to the neighbor node.

12. The method of claim 11, the method further comprising limiting a rate at which synopses are transmitted.

13. The method of claim 12, wherein limiting the rate further comprises limiting the rate based upon microutilities.

14. The method of claim 1, wherein comparing the received synopsis to the data sample updates in the local storage further comprises computing a Levenshtein distance to determine the minimum number of changes necessary to synchronize the received synopsis and the data sample updates in the local storage.

15. The method of claim 9, wherein transmitting a batch of differences further comprises transmitting a predetermined number of differences in the batch.

16. The method of claim 11, the method further comprising receiving a batch of differences from the neighbor node after transmitting a local synopsis to the neighbor node.

17. The method of claim 1, the method further comprising evaluating dynamic priorities on the local node using quantized parameters that are quantized in space or time.

18. The method of claim 17, wherein the quantized parameters used to evaluate the dynamic priorities are received with a received synopsis.

19. The method of claim 17, wherein comparing the received synopsis with the data sample updates in the local storage further comprises comparing the received synopsis using the received quantized parameters.

20. The method of claim 18, wherein the storage is resorted by evaluating the dynamic priorities with the quantization parameters received with a synopsis.

21. The method of claim 1, the method further comprising managing resources available for the local storage based in part on dynamic priority.

22. An article of non-transitory computer-readable storage media containing instructions that, when executed, cause the computer to:

receive a received synopsis of updates to data contained in samples in a neighbor storage of a neighboring node, wherein the received synopsis is a compressed representation of data samples updates stored in the neighboring node and sorted based on dynamic priorities associated with the data samples,

wherein a data sample is individual portion of data generated by applications on data source nodes; and

generating a local synopsis of data sample updates stored in a local storage of the local node;

compare the received synopsis with the local synopsis of data sample updates in a local storage of the local node; and

determine which data samples the local node will transmit based upon the comparison, and

wherein generating the local synopsis further comprises;

computing a hash of some portion of information associated with a data sample, and computing a hash of a stream identifier associated with a data source and a timestamp for each update to produce a list of hashes representing the updates stored in the local storage.

23. The article of claim 22, wherein the instructions, when executed, further cause the computer to combine the received synopsis with an update message to form a piggybacked update message.

24. The article of claim 22, wherein the instructions, when executed, further cause the computer to store data sample updates by only storing a data sample update for one or more data source streams having the most recent time stamp.

25. The article of claim 22, wherein the instructions, when executed, further cause the computer to store the updates until the dynamic priorities associated with the updates become less than or equal to a threshold.

26. The article of claim 22, wherein the instructions, when executed, further cause the computer to:

when the local node holds a first unmatched difference in a sort order, transmit a batch of differences from the local storage.

27. The article of claim 22, wherein the instructions, when executed, further cause the computer to:

when the received synopsis holds a first unmatched difference in a sort difference, transmit a local synopsis to the neighbor node.

28. The article of claim 22, wherein the instructions, when executed, further cause the computer to evaluate dynamic priorities on the local node using quantized parameters that are quantized in space or time.

29. A device, comprising:

a local storage;

a port to allow the device to receive a received synopsis of updates of data samples contained in a neighbor storage of a neighboring node, wherein the received synopsis is a compressed representation of data samples updates stored in the neighboring node based at least in part on dynamic priorities associated with the data samples,

wherein a data sample is individual portion of data generated by applications on data source nodes and; and

a processor to;

generate a local synopsis of data sample updates in the local storage of the local node;

compare the received synopsis with the local synopsis of data sample updates in the local storage of the local node; and

determine which data samples the local node will transmit based upon the comparison and transmission resources available to the processor, and

wherein generating the local synopsis further comprises;

computing a hash of some portion of information associated with a data sample, and computing a hash of a stream identifier associated with a data source and a timestamp for each update to produce a list of hashes representing the updates stored in the local storage.