Data transport by named content synchronization

• US 9,400,800 B2
• Filed: 11/19/2012
• Issued: 07/26/2016
• Est. Priority Date: 11/19/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.), Samsung Electronics Co. Ltd.
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Jacobson, Van L., Mosko, Marc E.
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): McBeth, William C
• Application Number:
  US13/681,306
• Publication Number:
  US 20140143446A1
• Time in Patent Office: 1,345 Days
• Field of Search: 707610-639, 709/203, 709/217, 709/219, 709/248
• US Class Current: 1/1
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

A collection-synchronizing system synchronizes a local data collection with a remote device. During operation, the system can detect the remote device, and receives collection summaries for one or more data collections stored at the remote device. A collection summary can include at least one additive hash value that represents one or more content items of a data collection. Then, for a data collection that exists at the local device and the remote device, the system compares a remote additive hash value for the remote data collection with a local additive hash value for the local data collection. If the system determines that the local additive hash value does not match the remote additive hash value, the system synchronizes structured names for the data collection at the local device and the remote device.

Claims

1. A computer-implemented method, comprising:

receiving, by a local computing device over a computer network, collection summaries for one or more data collections at a remote device, wherein a respective collection summary includes only a current additive hash value for each data collection, wherein a respective additive hash value represents a sum of hash values for two or more content items of a corresponding data collection;

comparing, for a local data collection that also exists at the remote device, a current local additive hash value for a current version of the local data collection to a current remote additive hash value for a current version of the corresponding remote data collection at the remote device;

in response to determining that the current remote additive hash value does not match the current local additive hash value, comparing the current remote additive hash value to one or more historical local additive hash values that were generated for a previous version of the local data collection; and

in response to determining that the current remote additive hash value matches a historical local additive hash value for the local collection, sending, to the remote device over the computer network, structured names for content items that have been added to the local data collection after the matching historical local additive hash value was generated.

2. The method of claim 1, further comprising synchronizing structured names for the local data collection with the remote device, wherein synchronizing the structured names involves:

comparing the current remote additive hash value to one or more historical local additive hash values for the local data collection; and

responsive to determining that the received current remote additive hash value does not match a historical local additive hash value for the local data collection;

determining a set difference between hash values for content items in the local and remote data collections;

determining, based on the hash values of the set difference, structured names for content items from the local data collection that are missing from the remote device'"'"'s data collection; and

sending, to the remote device, the structured names for the identified content items.

3. The method of claim 1, further comprising:

receiving a filter from the remote device, wherein the filter indicates selection criteria for selecting content items that are desired by the remote device;

determining, from the local data collection, a set of content items that satisfy the filter'"'"'s selection criteria;

generating the current local additive hash value using the content items that satisfy the filter'"'"'s selection criteria; and

synchronizing structured names for the local data collection with the remote device, wherein synchronizing the structured names involves;

generating a filtered collection of content items that includes, from the content items that satisfy the filter'"'"'s selection criteria, one or more content items that are missing from the remote data collection; and

sending structured names, for content items in the filtered collection, to the remote device.

4. The method of claim 1, further comprising:

sending, to the remote device, a collection summary for the local data collection;

receiving structured names for one or more content items stored in the remote data collection that are not in the local data collection; and

storing the received structured names in the local data collection.

5. The method of claim 4, further comprising:

sending an interest packet for at least one of the received structured names, wherein the interest packet facilitates receiving a content item identified by the structured name from any computing device of a computer network that stores the content item.

6. The method of claim 4, further comprising:

responsive to synchronizing the structured names, generating one or more additive hash values for the local data collection based on the received structured names for the content items that are not in the local data collection.

7. The method of claim 1, wherein the local data collection includes one or more nested hash values, wherein a nested hash value indicates a hash value for a content item of the local data collection or for a nested collection of content items of the local data collection;

and

wherein the received collection summary further includes one or more nested hash values of the remote data collection.

8. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:

receiving, over a computer network, collection summaries for one or more data collections at a remote device, wherein a respective collection summary includes only a current additive hash value for each data collection, wherein a respective additive hash value represents a sum of hash values for two or more content items of a corresponding data collection;

comparing, for a local data collection that also exists at the remote device, a current local additive hash value for a current version of the local data collection to a current remote additive hash value for a current version of the corresponding remote data collection at the remote device;

in response to determining that the current remote additive hash value does not match the current local additive hash value, comparing the current remote additive hash value to one or more historical local additive hash values that were generated for a previous version of the local data collection; and

in response to determining that the current remote additive hash value matches a historical local additive hash value for the local collection, sending, to the remote device over the computer network, structured names for content items that have been added to the local data collection after the matching historical local additive hash value was generated.

9. The storage medium of claim 8, wherein the method further comprises synchronizing structured names for the local data collection with the remote device, and wherein synchronizing the structured names involves:

comparing the current remote additive hash value to one or more historical local additive hash values for the local data collection; and

responsive to determining that the received current remote additive hash value does not match a historical local additive hash value for the local data collection;

determining a set difference between hash values for content items in the local and remote data collections;

determining, based on the hash values of the set difference, structured names for content items from the local data collection that are missing from the remote device'"'"'s data collection; and

sending, to the remote device, the structured names for the identified content items.

10. The storage medium of claim 8, wherein the method further comprises:

receiving a filter from the remote device, wherein the filter indicates selection criteria for selecting content items that are desired by the remote device;

determining, from the local data collection, a set of content items that satisfy the filter'"'"'s selection criteria;

generating the current local additive hash value using the content items that satisfy the filter'"'"'s selection criteria; and

synchronizing structured names for the local data collection with the remote device, wherein synchronizing the structured names involves;

generating a filtered collection of content items that includes, from the content items that satisfy the filter'"'"'s selection criteria, one or more content items that are missing from the remote data collection; and

sending structured names, for content items in the filtered collection, to the remote device.

11. The storage medium of claim 8, wherein the method further comprises:

sending, to the remote device, a collection summary for the local data collection;

receiving structured names for one or more content items stored in the remote data collection that are not in the local data collection; and

storing the received structured names in the local data collection.

12. The storage medium of claim 11, wherein the method further comprises:

sending an interest packet for at least one of the received structured names, wherein the interest packet facilitates receiving a content item identified by the structured name from any computing device of a computer network that stores the content item.

13. The storage medium of claim 11, wherein the method further comprises:

responsive to synchronizing the structured names, generating one or more additive hash values for the local data collection based on the received structured names for the content items that are not in the local data collection.

14. The storage medium of claim 8, wherein the local data collection includes one or more nested hash values, wherein a nested hash value indicates a hash value for a content item of the local data collection or for a nested collection of content items of the local data collection;

and

wherein the received collection summary further includes one or more nested hash values of the remote data collection.

15. An apparatus, comprising:

a communication module to receive, over a computer network, collection summaries for one or more data collections at a remote device, wherein a respective collection summary includes only a current additive hash value for each data collection, wherein a respective additive hash value represents a sum of hash values for two or more content items of a corresponding data collection;

a collection-comparing module to;

compare, for a local data collection that also exists at the remote device, a current local additive hash value for a current version of the local data collection to a current remote additive hash value for a current version of the corresponding remote data collection at the remote device; and

in response to determining that the current remote additive hash value does not match the current local additive hash value, compare the current remote additive hash value to one or more historical local additive hash values that were generated for a previous version of the local data collection;

a collection-synchronizing module, wherein in response to determining that the current remote additive hash matches the historical local additive hash value for the local collection, the collection-synchronization module is operable to send, to the remote device over the computer network, structured names for content items that have been added to the local data collection after the matching local historical hash value was generated.

16. The apparatus of claim 15, wherein the collection-comparing module is further configured to:

compare the current remote additive hash value to one or more historical local additive hash values for the local data collection; and

responsive to determining that the received current remote additive hash value does not match a historical local additive hash value for the local data collection, configure the collection-synchronizing module to;

determine a set difference between hash values for content items in the local and remote data collections;

determine, based on the hash values of the set difference, structured names for content items from the local data collection that are missing from the remote device'"'"'s data collection; and

send, to the remote device, the structured names for the identified content items.

17. The apparatus of claim 15, wherein the communication module is further configured to receive a filter from the remote device, wherein the filter indicates selection criteria for selecting content items that are desired by the remote device;

wherein the apparatus further comprises a hash-generating module to;

determine, from the local data collection, a set of content items that satisfy the filter'"'"'s selection criteria; and

generate the current local additive hash value using the content items that satisfy the filter'"'"'s selection criteria; and

wherein the collection-synchronizing module is further configured to;

generate a filtered collection of content items that includes, from the content items that satisfy the filter'"'"'s selection criteria, one or more content items that are missing from the remote data collection; and

send structured names, for content items in the filtered collection, to the remote device.

18. The apparatus of claim 15, wherein the communication module is further configured to:

send, to the remote device, a collection summary for the local data collection;

receive structured names for one or more content items stored in the remote data collection that are not in the local data collection; and

store the received structured names in the local data collection.

19. The apparatus of claim 18, wherein the communication module is further configured to:

send an interest packet for at least one of the received structured names, wherein the interest packet facilitates receiving a content item identified by the structured name from any computing device of a computer network that stores the content item.

20. The apparatus of claim 18, further comprising a hash-generating module operable to generate one or more additive hash values for the local data collection in response to the communication module receiving the structured names for the content items that are not in the local data collection.

21. The apparatus of claim 15, wherein the local data collection includes one or more nested hash values, wherein a nested hash value indicates a hash value for a content item of the local data collection or for a nested collection of content items of the local data collection;

and

wherein the received collection summary further includes one or more nested hash values of the remote data collection.