Efficient algorithm and protocol for remote differential compression on a local device

• US 20050262167A1
• Filed: 05/13/2004
• Published: 11/24/2005
• Est. Priority Date: 05/13/2004
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bjorner, Nikolaj S., Teodosiu, Dan, Gurevich, Yuri, Bozeman, Patrick E.
• Application Number:
  US10/844,907
• Publication Number:
  US 20050262167A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data

Abstract

The present invention is used to update objects over limited bandwidth networks. Objects are updated between two or more computing devices using remote differential compression (RDC) techniques such that required data transfers are minimized. In one aspect, efficient large object transfers are achieved by recursively applying the RDC algorithm to its own metadata; a single or multiple recursion step(s) may be used in this case to reduce the amount of metadata sent over the network by the RDC algorithm. Objects and/or signature and chunk length lists can be chunked by locating boundaries at dynamically determined locations. A mathematical function evaluates hash values associated within a horizon window relative to potential chunk boundary.

Claims

1. A method for updating an object between two or more computing devices using remote differential compression techniques, comprising:

partitioning a local object into chunks;

computing a signature and a chunk length for each chunk of the local object, wherein each of the signatures and the chunk lengths create a local chunk list;

generating a local recursive chunk list by recursively chunking the local chunk list;

comparing a remote recursive chunk list associated with a remote object to the local recursive chunk list to identify any differences between the local chunk list and a remote chunk list; and

comparing a remote chunk list associated with a remote object to the local chunk list to identify any differences between the local object and a remote object.

2. The method of claim 1, further comprising requesting at least one chunk from the remote object when the comparison determines a difference and assembling an object with the at least one chunk.

3. The method of claim 1, further comprising requesting at least one recursive chunk from the remote recursive chunk list when the comparison determines a difference and assembling a signature and chunk length list with the at least one recursive chunk.

4. The method of claim 1, wherein generating the local recursive chunk list, further comprises:

partitioning the local chunk list into recursive chunks;

computing a recursive signature for each recursive chunk of the local chunk list; and

assembling the local recursive chunk list with the recursive signatures and recursive chunk lengths.

5. The method of claim 1, wherein partitioning the local object further comprises applying a fingerprint function to the local object to generate fingerprints, and partitioning the local object into the chunks based on the fingerprints.

6. The method of claim 5, wherein applying the fingerprinting function further comprises providing a window that surrounds a position in the local object;

and computing a value from byte values that are located within the window.

7. The method of claim 6, further comprising dynamically adjusting the size of the window.

8. The method of claim 7, wherein dynamically adjusting the size of the window, further comprises:

adjusting the size of the window based on at least one of;

a data type associated with the local object, a data type associated with the remote object, an environmental constraint associated with a local device, an environmental constraint associated with the remote device, the characteristics of a communication medium coupling the local device and the remote device, a usage model associated with the local object, and a usage model associated with the remote object.

9. The method of claim 6, wherein computing the value comprises computing a hash value from the byte values.

10. The method of claim 4, wherein partitioning the local chunk list into recursive chunks further comprises:

determining at least one recursive chunking parameter;

determining at least one of a recursive horizon, a recursive trigger value, and a list of recursive triggers from the at least one recursive chunking parameter;

computing hash values at each position within the local chunk list;

applying a mathematical function to hash values located within the chunking horizon around each position within the local chunk list;

designating at least one of cut-points and chunking boundaries when the mathematical function is satisfied; and

chunking the local chunk list with the designated cut-points.

11. The method of claim 10, where the mathematical function is arranged as:

a predicate that maps hash values into Boolean values, a first function that partitions hash values into a small domain, a second function that determines a maximum value within the horizon, a third function that determines a minimum value within the horizon, a fourth function that evaluates differences between hash values within the horizon, a fifth function that sums hash values within the horizon, and a sixth function that calculates a mean of hash values within the horizon.

12. The method of claim 10, further comprising:

adjusting the at least one recursive chunking parameter based on at least one of;

a data type associated with the local object, a data type associated with the remote object, an environmental constraint associated with the local device, an environmental constraint associated with the remote device, the characteristics of a communication medium coupling the local device and the remote device, a usage model associated with the local object, and a usage model associated with the remote object.

13. A computer-readable medium having computer-executable instructions for updating an object over a communication channel between two or more computing devices using remote differential compression techniques, comprising:

partitioning a local object into chunks;

creating a local chunk list by computing a signature and a chunk length for each chunk of the local object;

generating a local recursive chunk list;

comparing a remote recursive chunk list associated with a remote object to the local recursive chunk list to identify any differences between the local chunk list and a remote chunk list;

comparing a remote chunk list associated with a remote object to the local chunk list to identify any differences between the local object and a remote object; and

requesting at least one chunk from the remote object when the comparison determines a difference and when at least one chunk from the remote object has been requested, assembling an object with the at least one chunk.

14. The computer-readable medium of claim 13, further comprising requesting at least one recursive chunk from the remote recursive chunk list when the comparison determines a difference and assembling a signature and chunk length list with the at least one recursive chunk.

15. The computer-readable medium of claim 13, wherein generating the local recursive chunk list, further comprises:

partitioning the local chunk list into recursive chunks;

computing a recursive signature for each recursive chunk associated with the chunked local list; and

assembling the local recursive chunk list with the recursive signatures and recursive chunk lengths.

16. The computer-readable medium of claim 13, wherein partitioning the local object further comprises applying a fingerprint function to the local object to generate fingerprints, and partitioning the local object into the chunks based on the fingerprints.

17. The computer-readable medium of claim 16, wherein applying the fingerprinting function further comprises providing a window that surrounds a position in the local object;

and computing a value from byte values that are located within the window.

18. The computer-readable medium of claim 17, further comprising, adjusting the size of the window based on at least one of:

a data type associated with the local object, a data type associated with the remote object, an environmental constraint associated with a local device, an environmental constraint associated with the remote device, the characteristics of a communication medium coupling the local device and the remote device, a usage model associated with the local object, and a usage model associated with the remote object.

19. The computer-readable medium of claim 17, wherein computing the value comprises computing a hash value from the byte values.

20. The computer-readable medium of claim 15, wherein partitioning the local chunk list into recursive chunks further comprises:

determining at least one recursive chunking parameter;

determining at least one of a recursive horizon, a recursive trigger value, and a list of recursive triggers from the at least one recursive chunking parameter;

computing hash values at each position within the local chunk list;

applying a mathematical function to hash values located within the chunking horizon around each position within the local chunk list;

designating at least one of cut-points and chunking boundaries when the mathematical function is satisfied; and

chunking the local chunk list with the designated cut-points.

21. The computer-readable medium of claim 20, where the mathematical function is arranged as:

a predicate that maps hash values into Boolean values, a first function that partitions hash values into a small domain, a second function that determines a maximum value within the horizon, a third function that determines a minimum value within the horizon, a fourth function that evaluates differences between hash values within the horizon, a fifth function that sums hash values within the horizon, and a sixth function that calculates a mean of hash values within the horizon.

22. The computer-readable medium of claim 21, further comprising:

adjusting the at least one recursive chunking parameter based on at least one of;

a data type associated with the local object, a data type associated with the remote object, an environmental constraint associated with the local device, an environmental constraint associated with the remote device, the characteristics of a communication medium coupling the local device and the remote device, a usage model associated with the local object, and a usage model associated with the remote object.

23. An apparatus for updating an object over a communication channel between two or more computing devices using remote differential compression techniques, comprising:

a network connection device coupling a local device to a remote device;

a data store; and

an application configured to perform actions, including

partitioning a local object into chunks;

creating a local chunk list by computing a signature and a chunk length for each chunk of the local object;

generating a local recursive chunk list;

storing the local recursive chunk list in the data store;

receiving a remote recursive chunk list using the network connection device list from the remote device;

comparing the remote recursive chunk list to the local recursive chunk list to identify any differences between the local chunk list and a remote chunk list;

comparing the remote chunk list to the local chunk list to identify any differences between the local object and a remote object; and

requesting at least one chunk from the remote device when the comparison determines a difference and when at least one chunk from the remote object has been requested, assembling an object with the at least one chunk.

24. The apparatus of claim 23, further comprising requesting at least one recursive chunk from the remote device when the comparison determines a difference and assembling a signature and chunk length list with the at least one recursive chunk.

25. The apparatus of claim 23, wherein generating the local recursive chunk list, further comprises:

partitioning the local chunk list into recursive chunks;

computing a recursive signature for each recursive chunk associated with the chunked local list; and

assembling the local recursive chunk list with the recursive signatures and recursive chunk lengths.

26. The apparatus of claim 23, wherein partitioning the local object further comprises applying a fingerprint function to the local object to generate fingerprints, and partitioning the local object into the chunks based on the fingerprints.

27. The apparatus of claim 26, wherein applying the fingerprinting function further comprises providing a window that surrounds a position in the local object;

and computing a value from byte values that are located within the window.

28. The apparatus of claim 27, further comprising, adjusting the size of the window based on at least one of:

a data type associated with the local object, a data type associated with the remote object, an environmental constraint associated with a local device, an environmental constraint associated with the remote device, the characteristics of a communication medium coupling the local device and the remote device, a usage model associated with the local object, and a usage model associated with the remote object.

29. The apparatus of claim 26, wherein partitioning the local chunk list into recursive chunks further comprises:

determining at least one recursive chunking parameter;

determining at least one of a recursive horizon, a recursive trigger value, and a list of recursive triggers from the at least one recursive chunking parameter;

computing hash values at each position within the local chunk list;

applying a mathematical function to hash values located within the chunking horizon around each position within local chunk list;

designating at least one of cut-points and chunking boundaries when the mathematical function is satisfied; and

chunking the local chunk list with the designated cut-points.

30. The apparatus of claim 29, where the mathematical function is arranged as:

a predicate that maps hash values into Boolean values, a first function that partitions hash values into a small domain, a second function that determines a maximum value within the horizon, a third function that determines a minimum value within the horizon, a fourth function that evaluates differences between hash values within the horizon, a fifth function that sums hash values within the horizon, and a sixth function that calculates a mean of hash values within the horizon.

31. The apparatus of claim 30, further comprising:

adjusting the at least one recursive chunking parameter based on at least one of;

a data type associated with the local object, a data type associated with the remote object, an environmental constraint associated with the local device, an environmental constraint associated with the remote device, the characteristics of a communication medium coupling the local device and the remote device, a usage model associated with the local object, and a usage model associated with the remote object.