Efficient algorithm and protocol for remote differential compression

• US 20050235043A1
• Filed: 04/15/2004
• Published: 10/20/2005
• Est. Priority Date: 04/15/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bjorner, Nikolaj S., Teodosiu, Dan, Gurevich, Yuri, Bozeman, Patrick E.
• Granted Patent: US 7,555,531 B2
• Time in Patent Office: Days
• US Class Current: 709/217
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A method and system are related to updating 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. The described method and system is useful in a variety of networked applications, such as peer-to-peer replicators, email clients and servers, client-side caching systems, general-purpose copy utilities, database replicators, portals, software update services, file/data synchronization, and others.

Claims

1. A system for updating objects over a network between a local device and a remote device, comprising:

a means for computing a first fingerprint function at every byte offset of a first object on the remote device;

a means for chunking the first object on the remote device based on the first fingerprint function;

a means for computing a remote signature for each chunk associated with the first object on the remote device;

a means for generating a remote signature and chunk length list on the remote device, wherein the remote signature and chunk length list is associated with the first object;

a means for computing a second fingerprint function at every byte offset of a second object on the local device, where the first and second objects are associated with one another, and where the first fingerprint function is matched to the second fingerprint function;

a means for chunking the second object on the local device based on the second fingerprint function, wherein the means for chunking the first object on the remote device is matched to the means for chunking the second object on the local device;

a means for computing a local signature for each chunk associated with the second object on the local device, wherein the means for computing the local signature is matched to the means for computing the remote signature;

a means for generating a local signature and chunk length list on the local device, wherein the local signature and chunk length list is associated with the second object;

a means for negotiating a chunked transmission of the remote signature and chunk length list from the remote device to the local device over the network such that bandwidth use is minimized for the transfer of the remote signature and chunk length list to the local device;

a means for identifying differences between the first object and the second object by comparing the local signature and chunk length list to the remote signature and chunk length list on the local device;

a means for requesting transmission of at least one updated object chunk from the remote device when differences between the first object and the second object are identified by the local device;

a means for transmitting the at least one updated object chunk from the remote device to the local device over the network; and

a means for reassembling a copy of the first object on the local device with the at least one updated object chunk.

2. The system of claim 1, further comprising a means for requesting an update for the first object from the remote device.

3. The system of claim 1, further comprising a means for requesting an update for the first object from the local device.

4. The system of claim 1, wherein negotiating the chunked transmission of the remote signature and chunk length list comprises sending at least a portion of the remote signature and chunk length list from the remote device to the local device.

5. The system of claim 1, wherein one of the local device and the remote device is a client, and the other of the local device and the remote device is a server.

6. The system of claim 1, wherein the network is at least one of:

a direct wired connection, a parallel port, a serial port, a USB port, an IEEE 1394 port, a wireless connection, an IR port, a Bluetooth port, a wired network, a wireless network, a local area network, a wide area network, an ultra-wide area network, an internet, an intranet, and an extranet.

7. The system of claim 1, wherein the means for computing the local signature for each chunk associated with the second object on the local device comprises a strong hashing function that is applied to the chunks on the local device.

8. The system of claim 1, wherein the means for identifying differences between the first object and the second object on the local device comprises:

a means for comparing the remote signature and chunk length list to the local signature and chunk length list;

a means for identifying at least one difference between the remote signature and chunk length list and the local signature and chunk length list;

a means for mapping the at least one difference to the remote signature and chunk length list; and

a means for identifying the at least one updated object chunk from the mapping between the at least one difference and the remote signature and chunk length list.

9. The system of claim 1, wherein the means for computing the first fingerprint function at every byte offset of the first object on the remote device comprises:

a means for providing a small window that is referenced around each byte position associated with the first object; and

a means for generating a fingerprint using the small window at each byte position.

10. The system of claim 9, further comprising:

a means for adjusting a window size associated with the small window based on at least one of;

a data type associated with the first object, a data type associated with the second object, an environmental constraint associated with the remote device, and environmental constraint associated with the local device, the characteristics of the network, a usage model associated with the first object, and a usage model associated with the second object.

11. The system of claim 1, wherein the first fingerprint function comprises at least one of:

a hash function using a Rabin polynomial, a cyclic shifting hash function, a 32-bit Adler hash function.

12. The system of claim 1, wherein the means for chunking the first object on the remote device comprises a means for determining at least one chunking parameter.

13. The system of claim 12, wherein the means for chunking the first object on the remote device further comprises:

a means for determining a chunking horizon from the at least one chunking parameter;

a means for computing hash values at each position within the first object;

a means for applying a mathematical function to hash values located within the chunking horizon around each position within the first object;

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

a means for chunking the first object with the designated cut-points.

14. The system of claim 13, wherein the mathematical function comprises at least one of:

determining a maximum value within the horizon, determining a minimum value within the horizon, and evaluating differences between hash values within the horizon.

15. The system of claim 12, wherein the means for chunking the first object on the remote device comprises:

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

a means for computing hash values at each position within the first object;

a means for applying a mathematical function on each computed hash value;

a means for designating at least one of cut-point chunking boundaries when the mathematical function attains the trigger value at a given offset and attains the other triggers at all corresponding offsets given by the horizon; and

a means for chunking the first object with the designated cut-points.

16. The system of claim 13, where the mathematical function comprises at least one of:

a predicate that maps hash values into a Boolean value, and another mathematical function that partitions hash values into a suitable small domain.

17. The system of claim 12, further comprising:

a means for adjusting the at least one chunking parameter based on at least one of;

a data type associated with the first object, a data type associated with the second object, an environmental constraint associated with the remote device, and environmental constraint associated with the local device, the characteristics of the network, a usage model associated with the first object, and a usage model associated with the second object.

18. The system of claim 1, further comprising:

a means for receiving the request for transmission of the at least one updated object chunk on the remote device;

a means for extracting the at least one updated object chunk from the second object on the remote device in response to the received request for transmission of the at least one updated object chunk;

a means for sending the at least one updated object chunk over the network with the remote device;

a means for receiving at least one updated object chunk from the network with the local device; and

a means for updating the first object on the local device with the at least one updated object chunk.

19. The system of claim 18, wherein the means for updating the first object is arranged to provide a new object on the local device, wherein the new object includes the at least one updated object chunk.

20. The system of claim 1, further comprising:

a means for receiving the at least one updated object chunk from the network with the local device; and

a means for assembling an updated first object on the local device with the at least one updated object chunk.

21. The system of claim 20, wherein the means for assembling the updated first object is further arranged such that the updated first object includes at least one unchanged chunk from the first object.

22. The system of claim 1 wherein the means for negotiating the chunked transmission of the remote signature and chunk length list from the remote device to the local device over the network comprises:

a means for chunking the remote signature and chunk length list on the remote device to provide a chunked remote signature and chunk length list;

a means for computing a recursive remote signature for each chunk associated with the chunked remote signature and chunk length list on the remote device;

a means for generating a recursive remote signature and chunk length list on the remote device with the recursive remote signatures and the chunked remote signature and chunk length list;

a means for chunking the local signature and chunk length list on the local device, wherein the means for chunking the local signature and chunk length list is matched to the means for chunking the remote signature and chunk length list;

a means for computing a recursive local signature for each chunk associated with the chunked local signature and chunk length list on the local device, wherein the means for computing the recursive local signature is matched to the means for computing the recursive remote signature;

a means for generating a recursive local signature and chunk length list on the local device with the recursive local signatures and the chunked local signature and chunk length list, wherein the means for generating the recursive local signature and chunk length list is matched to the means for generating the recursive remote signature and chunk length list;

a means for negotiating transmission of the recursive remote signature and chunk length list from the remote device to the local device over the network such that bandwidth use is minimized for the transfer of the recursive remote signature and chunk length list to the local device;

a means for identifying differences between the recursive remote signature and chunk length list and the recursive local signature and chunk length list on the local device;

a means for requesting transmission of at least one updated signature chunk from the remote device when differences are identified between the recursive remote signature and chunk length list and the recursive local signature and chunk length list by the local device;

a means for transmitting the at least one updated signature chunk from the remote device to the local device over the network, wherein the requested at least one updated signature chunk is associated with the remote signature and chunk length list; and

a means for assembling a copy of the remote signature and chunk length list on the local device with the at least one updated signature chunk.

23. The system of claim 22, wherein the means for negotiating transmission of the recursive remote signature and chunk length list from the remote device to the local device comprises:

sending at least a portion of the recursive remote signature and chunk length list from the remote device to the local device over the network.

24. The system of claim 22, wherein the means for chunking the remote signature and chunk length list on the remote device comprises:

a means for computing a third fingerprint function at every byte offset of the remote signature and chunk length list on the remote device; and

a means for chunking the remote signature and chunk length list on the remote device based on the third fingerprint function to provide the chunked remote signature and chunk length list.

25. The system of claim 24, wherein the means for chunking the local signature and chunk length list on the local device comprises:

a means for computing a fourth fingerprint function at every byte offset of the local signature and chunk length list on the local device, wherein the fourth fingerprint function is matched to the third fingerprint function; and

a means for chunking the local signature and chunk length list on the local device based on the fourth fingerprint function to provide the chunked local signature and chunk length list, wherein the means for chunking the local signature and chunk length list on the local device is matched to the means for chunking the remote signature and chunk length list on the remote device.

26. The system of claim 25, wherein the means for computing the third fingerprint function and the means for chunking the remote signature and chunk length list on the remote device employs a different methodology from the means for computing the first fingerprint function and the means for chunking the first object on the remote device.

27. The system of claim 24, wherein the means for computing the third fingerprint function and the means for chunking the remote signature and chunk length list on the remote device employs the same methodology as the means for computing the first fingerprint function and the means for chunking the first object on the remote device.

28. The system of claim 24, wherein the means for computing the third fingerprint function at every byte offset of the remote signature and chunk length list on the remote device comprises:

a means for providing a small window that is referenced around each byte position associated with the remote signature and chunk length list, and a means for generating a fingerprint using the small window at each byte position.

29. The system of claim 28, further comprising:

a means for adjusting a window size associated with the small window based on at least one of;

a data type associated with the first object, a data type associated with the second object, an environmental constraint associated with the remote device, and environmental constraint associated with the local device, the characteristics of the network, a usage model associated with the first object, and a usage model associated with the second object.

30. The system of claim 24, wherein the third fingerprint function comprises at least one of:

a hash function using a Rabin polynomial, a cyclic shifting hash function, a 32-bit Adler hash function.

31. The system of claim 22, wherein the means for chunking the remote signature and chunk length list on the remote device comprises a means for determining at least one recursive chunking parameter.

32. The system of claim 31, wherein the means for chunking the remote signature and chunk length list on the remote device further comprises:

a means for determining a recursive chunking horizon from the at least one recursive chunking parameter;

a means for computing hash values at each position within the remote signature and chunk length list;

a means for applying a mathematical function to hash values located within the recursive chunking horizon around each position within the remote signature and chunk length list;

a means for designating cut-points in the chunking boundaries when the mathematical function is satisfied; and

a means for chunking the remote signature and chunk length list with the designated cut-points.

33. The system of claim 31, wherein the means for chunking the remote signature and chunk length list on the remote device further comprises:

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

a means for computing hash values at each position within the remote signature and chunk length list;

a means for applying a mathematical function on each computed hash value;

a means for designating at least one of cut-points and chunking boundaries when the mathematical function attains the recursive trigger value at a given offset and attains the other recursive triggers at all corresponding offsets given by the recursive horizon; and

a means for chunking the remote signature and chunk length list with the designated cut-points.

34. The system of claim 32, where the mathematical function comprises at least one of:

a predicate that maps hash values into Boolean values, and any other mathematical function that partitions hash values into a suitable small domain.

35. The system of claim 32, wherein the mathematical function comprises at least one of:

determining a maximum value within the horizon, determining a minimum value within the horizon, evaluating differences between hash values within the horizon, summing hash values within the horizon, and calculating a mean of hash values within the horizon.

36. The system of claim 33, further comprising:

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

a data type associated with the first object, a data type associated with the second object, an environmental constraint associated with the remote device, and environmental constraint associated with the local device, the characteristics of the network, a usage model associated with the first object, and a usage model associated with the second object.

37. The system of claim 29, wherein the means for computing the recursive remote signature for each signature chunk associated with the chunked remote signature and chunk length list on the remote device comprises a strong hashing function that is applied to the signature chunks on the remote device.

38. The system of claim 22, further comprising:

a means for receiving the request for transmission of the at least one updated signature chunk on the remote device;

a means for extracting the at least one updated signature chunk from the remote signature and chunk length list on the remote device in response to the received request for transmission of the at least one updated signature chunk;

a means for sending the at least one updated signature chunk over the network with the remote device;

a means for receiving at least one updated signature chunk from the network with the local device; and

a means for assembling a copy of the remote signature and chunk length list on the local device with the at least one updated signature chunk.

39. The system of claim 38, wherein the means for assembling the local signature and chunk length list is arranged to provide a new copy of the remote signature and chunk length list on the local device, wherein the new copy of the remote signature and chunk length list includes the at least one updated signature chunk.

40. The system of claim 22, further comprising:

a means for receiving the at least one updated signature chunk from the network with the local device; and

a means for assembling a copy of the remote signature and chunk length list on the local device with the at least one updated signature chunk.

41. The system of claim 38, wherein the means for assembling the copy of the remote signature and chunk length list is further arranged such that the copy of the remote signature and chunk length list includes at least one unchanged chunk from the local signature and chunk length list.

42. The system of claim 22, wherein the means for identifying differences between the recursive remote signature and chunk length list and the recursive local signature and chunk length list on the local device comprises:

a means for comparing the recursive remote signature and chunk length list to the recursive local signature and chunk length list;

a means for identifying at least one signature chunk that is associated with a difference between the recursive remote signature and chunk length list and the recursive local signature and chunk length list;

a means for mapping the at least one signature chunk to the remote signature and chunk length list; and

a means for identifying the at least one updated signature chunk from the mapping between the at least one signature chunk and the remote signature and chunk length list.

43. The system of claim 1 wherein the means for negotiating the chunked transmission of the remote signature and chunk length list from the remote device to the local device over the network comprises:

a means for determining a number of iterations for recursive processing based on at least one of;

a data size associated with the first object, a data size associated with the second object, an environmental constraint associated with the remote device, and environmental constraint associated with the local device, the characteristics of the network, a usage model associated with the first object, and a usage model associated with the second object, a number of chunk signatures associated with the first object, and a number of chunk signatures associated with the chunked remote signature and chunk length list.

44. The system of claim 43, further comprising:

a recursive procedure for processing a signature and chunk length list, comprising;

a means for chunking the signature and chunk length list to provide a chunked signature and chunk length list;

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

a means for generating a recursive signature and chunk length list with the recursive signatures and the chunked signature and chunk length list;

a means for initializing the signature and chunk length list to the recursive signature and chunk length list when additional iterations are required for recursive processing; and

a means for returning the recursive signature and chunk length list when the recursive procedure has completed the number of iterations;

a means for processing the remote signature and chunk length list with the recursive procedure on the remote device by passing the remote signature and chunk length list to the recursive procedure as the signature and chunk length list, and by returning the recursive remote signature and chunk length list from the recursive procedure; and

a means for processing the local signature and chunk length list with the recursive procedure on the local device by passing the local signature and chunk length list to the recursive procedure as the signature and chunk length list, and by returning the recursive local signature and chunk length list from the recursive procedure.

45. The system of claim 1, wherein the means for generating the remote signature and chunk length list on the remote device is further arranged to compactly encode the remote signature and chunk length list.

46. The system of claim 1, wherein the means for generating the local signature and chunk length list on the local device is further arranged to compactly encode the local signature and chunk length list.

47. The system of claim 22, wherein the means for generating the recursive remote signature and chunk length list on the remote device is further arranged to compactly encode the recursive remote signature and chunk length list.

48. The system of claim 22, wherein the means for generating the recursive local signature and chunk length list on the local device is further arranged to compactly encode the recursive local signature and chunk length list.

49. A computer readable medium having computer-executable instructions for updating objects over a communication medium between a local device and a remote device, comprising:

chunking a first object on the remote device;

computing a signature for each chunk associated with the first object on the remote device to provide remote signatures;

assembling a remote signature and chunk length list on the remote device from the remote signatures;

generating a recursive remote signature and chunk length list on the remote device by;

chunking the remote signature and chunk length list on the remote device;

computing a signature for each chunk associated with the chunked remote signature and chunk length list on the remote device to provide recursive remote signatures; and

assembling a recursive remote signature and chunk length list on the remote device with the recursive remote signatures;

chunking a second object on the local device;

computing a signature for each chunk associated with the second object on the local device to provide local signatures;

assembling a local signature and chunk length list on the local device from the local signatures, such that the local signature and chunk length list is matched to the remote signature and chunk length list when the first object is matched to the second object;

generating a recursive local signature and chunk length list on the local device by;

chunking the local signature and chunk length list;

computing a signature for each chunk associated with the chunked local signature and chunk length list to provide recursive local signatures; and

assembling a recursive local signature and chunk length list with the recursive local signatures;

negotiating transmission of the recursive remote signature and chunk length list from the remote device to the local device over the communication medium such that bandwidth use is minimized for the transfer of the recursive remote signature and chunk length list to the local device;

identifying at least one difference between the first object and the second object by;

comparing the recursive remote signature and chunk length list and the recursive local signature and chunk length list on the local device to identify a difference; and

mapping the difference to at least one chunk associated with the second object; and

updating the first object on the local device by;

requesting transmission of at least one chunk from the remote device;

receiving a transmission from the remote device over the communication medium, wherein the transmission includes the at least one chunk; and

assembling an object with the at least one chunk.

50. The computer readable medium of claim 49, wherein chunking the first object on the remote device comprises:

applying a fingerprinting function to the first object to generate a first set of fingerprints, and partitioning the first object into a first set of chunks based on the first set of fingerprints.

51. The computer readable medium of claim 50, wherein chunking the second object on the local device comprises:

applying the fingerprinting function to the second object to generate a second set of fingerprints, and partitioning the second object into a second set of chunks based on the second set of fingerprints.

52. The computer readable medium of claim 49, wherein the communication medium is at least one of:

a direct wired connection, a parallel port, a serial port, a USB port, an IEEE 1394 port, a wireless connection, an IR port, a Bluetooth port, a wired network, a wireless network, a local area network, a wide area network, an ultra-wide area network, an internet, an intranet, and an extranet.

53. The computer readable medium of claim 59, wherein the fingerprinting function comprises:

providing a window that is referenced around each byte position of the first object; and

computing a hash from the byte values that are located in the window.

54. The computer readable medium of claim 53, further comprising:

adjusting a window size associated with the window based on at least one of;

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

55. The computer readable medium of claim 49, wherein identifying at least one difference between the first object and the second object further comprises:

identifying an updated signature chunk on the remote device based on the difference;

requesting transmission of the updated signature chunk from the remote device to the local device over the communication medium;

receiving the updated signature chunk on the local device from the communication medium; and

assembling an updated signature and chunk length list on the local device with the updated signature chunk.

56. The computer readable medium of claim 55, wherein mapping the difference to at least one chunk associated with the second object comprises:

comparing the updated signature and chunk length list to the local signature and chunk length list to identify at least one updated chunk on the remote device.

57. The computer readable medium of claim 49, wherein chunking the remote signature and chunk length list on the remote device comprises:

applying a fingerprinting function to the remote signature and chunk length list to generate a first set of fingerprints, and partitioning the remote signature and chunk length list into a first set of chunks based on the first set of fingerprints.

58. The computer readable medium of claim 57, wherein chunking the local signature and chunk length list on the remote device comprises:

applying the fingerprinting function to the local signature and chunk length list to generate a second set of fingerprints, and partitioning the local signature and chunk length list into a second set of chunks based on the second set of fingerprints.

59. The computer readable medium of claim 57, wherein the fingerprinting function comprises:

providing a window that is referenced around each byte position of the remote signature and chunk length list; and

computing a hash value from the byte values that are located in the window.

60. The computer readable medium of claim 59, further comprising:

adjusting a window size associated with the window based on at least one of;

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

61. The computer readable medium of claim 60, wherein chunking the remote signature and chunk length list on the remote device comprises:

determining at least one recursive chunking parameter;

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

computing hash values at each position within the remote signature and chunk length list;

applying a mathematical function on each computed hash value;

designating chunking boundaries when the mathematical function attains the at least one recursive trigger value at a given offset; and

chunking the remote signature and chunk length list with the designated cut-points.

62. The computer readable medium of claim 61, 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.

63. The computer readable medium of claim 61, further comprising:

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

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

64. A computer implemented method for updating objects over a communication channel between a local device and a remote device, comprising:

chunking a first object on the remote device;

computing a signature for each chunk associated with the first object on the remote device to provide remote signatures;

assembling a remote signature and chunk length list on the remote device from the remote signatures;

chunking a second object on the local device based on the computed fingerprint function;

computing a signature for each chunk associated with the second object on the local device to provide local signatures;

assembling a local signature and chunk length list on the local device from the local signatures, such that the local signature and chunk length list is matched to the remote signature and chunk length list when the first object is matched to the second object;

providing a recursive procedure on both the local device and the remote device, wherein the recursive procedure is arranged to process a designated signature and chunk length list by;

chunking the designated signature and chunk length list to provide a chunked signature and chunk length list;

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

generating a recursive signature and chunk length list with the recursive signatures and the chunked signature and chunk length list;

initializing the designated signature and chunk length list to the recursive signature and chunk length list when additional iterations are required for recursive processing; and

returning the recursive signature and chunk length list when the recursive procedure has completed the required number of iterations;

generating a recursive remote signature and chunk length list on the remote device by passing the remote signature and chunk length list to the recursive procedure as the designated signature and chunk length list, and by returning the recursive remote signature and chunk length list from the recursive procedure;

generating a recursive local signature and chunk length list on the local device by passing the local signature and chunk length list to the recursive procedure as the designated signature and chunk length list, and by returning the recursive local signature and chunk length list from the recursive procedure;

sending the recursive remote signature and chunk length list from the remote device to the local device over the communication channel;

identifying at least one difference between the first object and the second object by comparing the received recursive remote signature and chunk length list to the recursive local signature and chunk length list;

identifying at least one updated chunk associated with the second object based on the at least one difference; and

updating the first object on the local device by;

requesting transmission of the at least one updated chunk from the remote device;

receiving a transmission from the remote device over the communication channel, wherein the transmission includes the at least one updated chunk; and

assembling an object with the at least one updated chunk.

65. The computer readable medium of claim 64, wherein chunking the first object on the remote device comprises:

applying a fingerprinting function to the first object to generate a first set of fingerprints, and partitioning the first object into a first set of chunks based on the first set of fingerprints.

66. The computer readable medium of claim 65, wherein chunking the second object on the local device comprises:

applying the fingerprinting function to the second object to generate a second set of fingerprints, and partitioning the second object into a second set of chunks based on the second set of fingerprints.

67. The computer implemented method of claim 64, wherein the communication channel is at least one of:

a direct wired connection, a parallel port, a serial port, a USB port, an IEEE 1394 port, a wireless connection, an IR port, a Bluetooth port, a wired network, a wireless network, a local area network, a wide area network, an ultra-wide area network, an internet, an intranet, and an extranet.

68. The computer implemented method of claim 64, wherein identifying at least one chunk associated with the second object based on the at least one difference comprises:

identifying at least one recursive chunk of the received recursive remote signature and chunk length list that is different from the recursive local signature and chunk length list;

mapping the at least one recursive chunk to at least one chunk of the remote signature and chunk length list;

requesting transmission of the at least one chunk of the remote signature and chunk length list from the remote device;

receiving a transmission from the remote device over the communication channel, wherein the transmission includes the at least one chunk of the remote signature and chunk length list; and

assembling an updated signature and chunk length list from the received at least one chunk of the remote signature and chunk length list.

69. The computer implemented method of claim 68, wherein identifying at least one chunk associated with the second object based on the at least one difference comprises:

comparing the updated signature and chunk length list to the local signature and chunk length list to identify the at least one updated chunk on the remote device.

70. The computer implemented method of claim 64, wherein chunking the designated signature and chunk length list comprises:

applying a fingerprinting function to the designated signature and chunk length list to generate a set of fingerprints, and partitioning the designated signature and chunk length list into a set of chunks based on the set of fingerprints.

71. The computer implemented method of claim 70, wherein the fingerprinting function comprises:

providing a window that is referenced around each byte position associated with the designated signature and chunk length list; and

computing a hash value from the byte values that are located in the window.

72. The computer implemented method of claim 71, further comprising:

adjusting a window size associated with the window based on at least one of;

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

73. The computer implemented method of claim 64, wherein chunking the designated signature and chunk length list to provide the chunked signature and chunk length list 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 designated signature and chunk length list;

applying a mathematical function to hash values located within the chunking horizon around each position within designated signature and chunk length list;

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

chunking the designated signature and chunk length list with the designated cut-points.

74. The computer implemented method of claim 73, 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.

75. The computer implemented method of claim 73, further comprising:

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

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

76. The computer implemented method of claim 64, further comprising:

determining the required number of iterations for recursive processing based on at least one of;

a data size associated with the first object, a data size associated with the second object, an environmental constraint associated with the remote device, and environmental constraint associated with the local device, the characteristics of the communication channel, a usage model associated with the first object, and a usage model associated with the second object, a number of chunk signatures associated with the first object, and a number of chunk signatures associated with the chunked remote signature and chunk length list.

77. The computer implemented method of claim 64, wherein the required number of iterations for recursive processing corresponds to at least one iteration.