Method and apparatus for bandwidth-efficient and storage-efficient backups

• US 20030204609A1
• Filed: 04/30/2002
• Published: 10/30/2003
• Est. Priority Date: 04/30/2002
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Anderson, Andrew V., Bennett, Steven M., Robinson, Scott H.
• Granted Patent: US 7,139,808 B2
• Time in Patent Office: Days
• US Class Current: 709/229
• CPC Class Codes: H04L 67/30 Profiles
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method is presented that includes generating a content identifier for at least one article. The content identifier identifies the article. Also, determining if at least a portion of the at least one article is present on at least one device based on the content identifier. The at least one portion of the at least one article is stored if the at least one portion of the at least one article is determined to be not present on the at least one device. Also presented is a method including requesting at least one article by a content identifier representing the article. The at least one article is determined if it is present on at least one device based on the content identifier. At least one portion of the at least one article is returned if the at least one portion of the at least one article is determined to be present on the at least one device.

Claims

1. A method comprising:

generating a content identifier for at least one article, the content identifier representing the at least one article,

determining if at least one portion of the at least one article is present on at least one device based on the content identifier, and

storing the at least one portion of the at least one article if the at least one portion of the at least one article is determined to be not present on the at least one device.

2. The method of claim 1, wherein the content identifier is generated from one of

a hash of contents of the at least one article,

a hash of contents of the at least one article and at least one portion of metadata,

a combination of a hash of contents of the at least one article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the at least one article,

at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata.

3. The method of claim 1, wherein the at least one portion of the at least one article includes one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

4. The method of claim 3, wherein at least one portion of the at least one article is stored on the at least one device and at least two articles have the same at least one portion.

5. The method of claim 4, wherein the at least two articles reside on one of at least two separate devices and one device.

6. The method of claim 3, wherein a plurality of copies of the at least one portion of the at least one article are stored on the at least one device.

7. The method of claim 1, determining if the at least one portion of the at least one article is present on the at least one device based on the content identifier further comprising:

determining if a portion of a second article is present on the at least one device, the portion of the second article represented by a content identifier identical to the content identifier for the at least one article where the content identifier for the portion of the second article is determined using the same mechanism as the content identifier for the at least one article.

8. The method of claim 7, wherein the portion of the second article includes one of a portion of contents of the second article, at least one portion of metadata, and a portion of contents of the second article and at least one portion of metadata.

9. The method of claim 1, further comprising:

generating at least one portion of at least one contour for a plurality of articles.

10. The method of claim 9, wherein the at least one contour includes one of content identification for each of the plurality of articles, and content identification for each of the plurality of articles and metadata, wherein content identification for each of the plurality of articles is generated from one of

a hash of contents of the particular article,

a hash of contents of the particular article and at least one portion of metadata,

a combination of a hash of contents of the particular article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the particular article,

at least one content signaturing algorithm over contents of the particular article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the particular article and at least one portion of metadata.

11. The method of claim 9, further including:

storing the at least one portion of the at least one contour.

12. The method of claim 11, wherein the at least one portion of the at least one contour is stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

13. The method of claim 1, wherein the at least one article is originally stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

14. A method comprising:

requesting at least one portion of at least one article by a content identifier representing the at least one article,

determining if the at least one portion of at least one article is present on at least one device based on the content identifier, and

returning the at least one portion of the at least one article if the at least one portion of the at least one article is determined to be present on the at least one device.

15. The method of claim 14, wherein the content identifier is generated from one of

a hash of contents of the at least one article,

a hash of contents of the at least one article and at least one portion of metadata,

a combination of a hash of contents of the at least one article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the at least one article,

at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata.

16. The method of claim 14, wherein the at least one portion of the at least one article includes one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

17. The method of claim 14, wherein a plurality of representations of the at least one portion of the at least one article are returned.

18. The method of claim 14, wherein requesting at least one article by a content identifier representing the article further comprises:

selecting at least one portion of at least one article represented in at least one portion of at least one contour, wherein the at least one portion of the at least one contour includes one of content identification for each of the plurality of articles, and content identification for each of the plurality of articles and at least one portion of metadata, and

requesting the at least one portion of at least one article represented in at least one portion of at least one contour using the content identifier for the at least one article.

19. The method of claim 18, further including:

returning the at least one portion of at least one article represented by the at least one portion of at least one contour.

20. The method of claim 19, wherein the at least one portion of the at least one article includes one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

21. The method of claim 18, wherein the at least one portion of at least one contour is originally stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

22. The method of claim 14, wherein the at least one portion of at least one article is originally stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

23. An apparatus comprising a machine-readable medium containing instructions which, when executed by a machine, cause the machine to perform operations comprising:

generating a content identifier for at least one article, the content identifier representing the article,

determining if at least one portion of the at least one article is present on at least one device based on the content identifier, and

storing the at least one portion of the at least one article if the at least one article is determined to be not present on the at least one device.

24. The apparatus of claim 23, wherein the content identifier is generated from one of

a hash of contents of the at least one article,

a hash of contents of the at least one article and at least one portion of metadata,

a combination of a hash of contents of the at least one article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the at least one article,

at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata.

25. The apparatus of claim 23, wherein the at least one portion of the at least one article includes one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

26. The apparatus of claim 25, wherein at least one portion of the at least one article is stored on the at least one device and at least two articles have the same at least one portion.

27. The apparatus of claim 26, wherein the at least two articles reside on one of at least two separate devices and one device.

28. The apparatus of claim 25, wherein a plurality of copies of the at least one portion of the at least one article are stored on the at least one device.

29. The apparatus of claim 23, determining if the at least one portion of the at least one article is present on the at least one device based on the content identifier further comprising:

determining if a portion of a second article is present on the at least one device, the portion of the second article represented by a content identifier identical to the content identifier for the at least one article where the content identifier for the second article is determined using the same mechanism as the content identifier for the at least one article.

30. The apparatus of claim 29, wherein the at least one portion of the second article includes one of a portion of contents of the second article, at least one portion of metadata, and a portion of contents of the second article and at least one portion of metadata.

31. The apparatus of claim 23, further containing instructions which, when executed by a machine, cause the machine to perform operations including:

generating at least one portion of at least one contour for a plurality of articles.

32. The apparatus of claim 31, wherein the at least one contour includes one of content identification for each of the plurality of articles, and content identification for each of the plurality of articles and at least one portion of metadata, wherein content identification is generated from one of

a hash of contents of the at least one article,

a hash of contents of the at least one article and at least one portion of metadata,

a combination of a hash of contents of the at least one article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the at least one article,

at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata.

33. The apparatus of claim 31, further containing instructions which, when executed by a machine, cause the machine to perform operations including:

storing the at least one portion of the at least one contour.

34. The apparatus of claim 33, wherein the at least one portion of the at least one contour is stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

35. The apparatus of claim 23, wherein the at least one article is originally stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

36. An apparatus comprising a machine-readable medium containing instructions which, when executed by a machine, cause the machine to perform operations comprising:

requesting at least one portion of at least one article by a content identifier representing the at least one article,

determining if the at least one portion of at least one article is present on at least one device based on the content identifier, and

returning at least one portion of the at least one article if the at least one portion of the at least one article is determined to be present on the at least one device.

37. The apparatus of claim 36, wherein the content identifier is generated from one of

a hash of contents of the at least one article,

a hash of contents of the at least one article and at least one portion of metadata,

a combination of a hash of contents of the at least one article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the at least one article,

at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata.

38. The apparatus of claim 36, wherein the at least one portion of the at least one article includes one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

39. The apparatus of claim 38, wherein a plurality of representations of the at least one portion of the at least one article are returned.

40. The apparatus of claim 36, further containing instructions which, when executed by a machine, cause the machine to perform operations including:

selecting at least one portion of at least one article represented in at least one portion of at least one contour, wherein the at least one portion of the at least one contour includes one of content identification for each of the plurality of articles, and content identification for each of the plurality of articles and at least one portion of metadata, and

requesting the at least one portion of at least one article represented in at least one portion of at least one contour using the content identifier for the at least one article.

41. The apparatus of claim 40, further containing instructions which, when executed by a machine, cause the machine to perform operations including:

returning at least one portion of at least one article represented by the at least one portion of at least one contour.

42. The apparatus of claim 41, wherein the at least one portion of the at least one article includes one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

43. The apparatus of claim 41, wherein the at least one portion of at least one contour is originally stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

44. The apparatus of claim 36, wherein the at least one portion of at least one article is originally stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

45. A system comprising:

a plurality of devices coupled to a transmission medium, each of the plurality of devices coupled with a first process and a second process and having at least one article,

wherein the first process;

generates a content identifier for the at least one article for each of the plurality of devices, the content identifier representing the at least one article,

determines if the at least one article is present on at least one other of the plurality of devices based on the content identifier, and

stores at least one portion of the at least one article if the at least one portion of the at least one article is determined to be not present on the at least one other of the plurality of devices, and

wherein the second process;

requests at least one portion of a second article by the content identifier representing the second article,

determines if the at least one portion of the second article is present on at least one of the plurality of devices based on the content identifier, and

returns the at least one portion of the second article if the at least one portion of the second article is determined to be present on the at least one of the plurality of devices.

46. The system of claim 45, wherein the content identifier is generated from one of

a hash of contents of the at least one article,

a hash of contents of the at least one article and at least one portion of metadata,

a combination of a hash of contents of the at least one article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the at least one article,

at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata.

47. The system of claim 45, wherein the at least one portion of each of the at least one article and the second article include one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

48. The system of claim 45, wherein the first process further:

generates at least one portion of at least one contour for a plurality of articles for at least one of the plurality of devices and

stores at least one portion of the at least one contour on at least one of the plurality of devices.

49. The system of claim 45, wherein the second process further:

selects at least one portion of at least one article represented in at least one portion of at least one contour, wherein the at least one portion of the at least one contour includes one of content identification for each of the plurality of articles, and content identification for each of the plurality of articles and at least one portion of metadata, and

requests the at least one portion of at least one article represented in at least one portion of at least one contour using the content identifier for the at least one article.