Method and system for cooperatively backing up data on computers in a network

• US 7,529,834 B1
• Filed: 09/22/2000
• Issued: 05/05/2009
• Est. Priority Date: 06/02/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lillibridge, Mark David, Burrows, Michael, Birrell, Andrew David, Isard, Michael Acheson
• Primary Examiner(s): BOUTAH, ALINA A
• Application Number:
  US09/668,643
• Time in Patent Office: 3,147 Days
• Field of Search: 709219-203, 709/211, 709/205, 709/223, 709226-229, 709/244, 709/201, 707/200, 707/204, 707/100, 707/E17.007, 705/1, 705/7, 705/8, 715/533, 726/7, 711/162, 714/6
• US Class Current: 709/226
• CPC Class Codes: G06F 11/1464 for networked environments

Abstract

A method for backing up data in a plurality of computers connected via a network. The method includes forming partnerships between the plurality of computers such that each computer in a partnership commits under agreements to help backup the data of its partners. The method further includes periodically verifying that previously backed up data is being retained by the computers committed to act as backup partners in accordance with the agreements. In another embodiment, the method provides a distributed cooperative backing up of data in a system that includes a loose confederation of computers connected via a network. In this embodiment the method includes selecting computers as potential backup partners from among the loose confederation of computers connected via the network based on predetermined criteria, and negotiating a reciprocal backup partnership agreement between the computers based on predetermined requirements, including backup requirements. Once the negotiations are complete and the agreements are made, the method proceeds to form partnerships between the computers. The computers become backup partners by agreeing to cooperatively provide backup services to each other so that a distributed cooperative backing up of data can be administered in the absence of central control. The method further includes periodically backing up data at the backup partners, where the data being backed up is encoded. The method also includes periodically verifying that previously backed up data is retained by the backup partners. Another aspect of the invention is a distributed cooperative backup system that includes a network and a loose confederation of computers connected via the network. A plurality of computers from among the loose confederation of computers is configured for distributed cooperative backing up of data and for functioning as backup partners. Each computer of the plurality of computers has a storage that can be used for providing reciprocal backup services. Each computer of the plurality of computers respectively also has a computer readable medium embodying computer program code configured to cause the computer to perform functions comparable to the method steps as described above.

Claims

1. A method for backing up data on a plurality of computers connected via a network, comprising:

forming one or more backup partnerships among the plurality of computers such that each computer in a backup partnership commits under an agreement to store backup data received from one or more backup partners, whereby a first computer in each partnership assumes the task of storing backup data received from one or more other computers in the partnership and one or more of the other computers in the partnership assume the task of storing backup data received from the first computer;

backing up data in accordance with each agreement; and

periodically verifying that previously backed up data is being retained by the computers committed to act as backup partners in accordance with each agreement.

2. The method of claim 1, further comprising:

selecting potential backup partners from among the plurality computers based on predetermined criteria.

3. The method of claim 1, further comprising:

negotiating the agreements between the plurality of computers based on predetermined requirements, including backup requirements.

4. The method of claim 1, wherein the plurality of computers administer a distributed cooperative backing up of data in the absence of central control.

5. The method of claim 1, wherein each of the plurality of computers has a storage, the storage being periodically scanned to find data to be backed up and identify data previously backed up that no longer needs to be backed up, the data to be backed up being retrieved from the storage for a next periodic backup.

6. The method of claim 1, wherein the verifying that previously backed up data is retained by the backup partners includes monitoring the backup partners, and for any one of the backup partners being monitored,

selecting a block of data stored at the monitored backup partner,

requesting the block of data from the monitored backup partner, and

receiving from the monitored backup partner and checking the block of data to determine if the block of data represents a corresponding block of previously backed up data.

7. The method of claim 6, wherein the block is selected randomly.

8. The method of claim 6, wherein the block is selected using a protocol to produce a number that corresponds to the selected block and that is controlled by at least two backup partners.

9. The method of claim 8, wherein the protocol, being performed by any computer of the plurality of computers, includes

sending by the computer to a monitored one of its backup partners a has value of a first random number,

receiving by the computer from the monitored one of its backup partners a second random number,

sending by the computer to the monitored one of its backup partners the first random number,

computing the number from the first and second random numbers by both the computer and the monitored one of its backup partners.

10. The method of claim 1, further comprising:

selecting another computer connected via the network to be a new backup partner if it is determined that a backup partner has reneged by not retaining the previously backed up data;

negotiating and, if an agreement is reached, forming a partnership with the other computer, accepting the other computer as the new backup partner.

11. The method of claim 10, wherein selecting another computer to be the new backup partner includes

determining if there are sufficient backup partners for backing up the data, and

searching for the other computer based on predetermined criteria including one or both of geographic separation and system diversity.

12. The method of claim 10, wherein if after accepting the other computer as the new backup partner it is determined that the backup partners are insufficient in number for backing up the data, the selecting, negotiating and forming backup partnership with yet another computer are repeated, the determining, selecting, negotiating and forming backup partnership being repeated until the number of backup partners is sufficient.

13. The method of claim 2, wherein selecting computers as potential backup partners includes

determining if there are sufficient backup partners for backing up the data, and

searching for computers based on the predetermined criteria that includes one or both of geographic separation and system diversity.

14. The method of claim 3, wherein negotiating the agreements includes, for any computer of the plurality of computers,

exchanging queries between the computer and computers selected as its potential backup partners about each such computer'"'"'s ability to satisfy the predetermined requirements that include one or more of

predictable and suitable time schedule for being on-line,

suitable network bandwidth,

matching backup space requirements, and

backup track record.

15. The method of claim 14, wherein, the computer prefers to partner with those of its potential backup partners that satisfy the predetermined requirements.

16. The method of claim 14, wherein the suitable network bandwidth is equal or larger than a predetermined threshold bandwidth and is characterized by an average bandwidth that is larger than the predetermined threshold bandwidth.

17. The method of claim 14, wherein the backup track record includes not reneging on a number of other backup partners that is greater than a predetermined number.

18. The method of claim 1, wherein each of the backup partners has a recent copy of a list of its backup partners'"'"' other backup partners.

19. The method of claim 1, wherein the agreements are respectively negotiated between the plurality of computers such that in each partnership each computer commits to avoid making or honoring a data restoration request for a commitment period that is longer than a grace period, wherein the grace period for a backup partner of a computer starts to run if it is determined that the backup partner has failed to respond to such computer verifying that the backup partner is retaining the previously backed up data or to prove to such computer that it is retaining the previously backed up data, and wherein upon the grace period running out such computer considers the backup partner to have reneged on its agreement.

20. The method of claim 1, wherein the data being backed up is file contents.

21. The method according to claim 1, wherein said forming comprises forming at least two partnerships among the plurality of computers.

22. The method according to claim 1, wherein at least one computer of the plurality assumes the task of storing backup data received from at least two other computers.

23. The method according to claim 1, wherein different portions of data of at least one computer of the plurality are stored by at least two other computers.

24. A distributed cooperative backup system, comprising:

a network; and

a loose confederation of computers connected via the network, a plurality of computers from among the loose confederation of computers being configured for distributed cooperative backing up of data, each computer of the plurality of computers having a storage that can be used for providing reciprocal backup services, and each computer of the plurality of computers respectively having a computer readable medium embodying computer program code configured to cause the computer to

form backup partnerships between the plurality of computers, each of the backup partnerships being of computers such that each computer in a partnership commits under an agreement to store backup data received from one or more backup partners, whereby a first computer in each partnership assumes the task of storing backup data received from one or more other computers in the partnership and one or more of the other computers in the partnership assume the task of storing backup data received from the first computer;

back up data in accordance with each agreement; and

periodically verify that previously backed up data is being retained by the computers committed to act as backup partners in accordance with each agreement.

25. The system of claim 24, wherein each of the backup partners is allowed to leave the system and return to the system.

26. The system of claim 24, wherein prevention of freeloading is enforced by the backup partners, by any of the backup partners being requested to prove that it is retaining the previously backed up data.

27. A distributed cooperative backup system, comprising:

a network; and

a loose confederation of computers connected via the network, a plurality of computers from among the loose confederation of computers being configured for distributed cooperative backing up of data and functioning as backup partners, each computer of the plurality of computers having a storage that can be used for providing reciprocal backup services, and each computer of the plurality of computers respectively having a computer readable medium embodying computer program code configured to cause the computer to

select computers as potential backup partners from among the plurality of computers based on predetermined criteria,

negotiate a reciprocal backup partnership agreement between the computer and the selected computers based on predetermined requirements, including backup requirements,

form partnerships between the computer and selected computers, the computer and the selected computers becoming backup partners by agreeing to cooperatively provide backup services to each other such that a first computer in each partnership assumes the task of storing backup data received from one or more other computers in the partnership and one or more of the other computers in the partnership assume the task of storing backup data received from the first computer and so that a distributed cooperative backing up of data is administered in the absence of central control,

periodically back up data at the backup partners, encoding the data each time before the data is backed up, and

periodically verify that previously backed up data is retained by the backup partners.

28. A method for backing up data on a plurality of computers connected via a network, comprising:

exchanging messages among computers of the plurality to determine the ability of each to satisfy backup storage requirements of one or more others;

forming a partnership among computers of the plurality in which a first computer in the partnership stores backup data received from one or more other computers in the partnership and one or more of the other computers in the partnership store backup data received from the first computer; and

each of the computers in the partnership periodically verifying that its backup data is being retained by one or more of the other computers in the partnership.

29. The method according to claim 28, wherein the verifying includes selecting a block of the previously backed up data wherein the selecting is controlled by at least two of the computers.

30. The method according to claim 28, wherein the partnership consists of two computers.

31. The method according to claim 28, further comprising at least one additional partnership among the plurality of computers.

32. The method according to claim 28, wherein the first computer of the partnership stores backup data received from at least two other computers in the partnership.

33. The method according to claim 28, wherein different portions of data of the first computer of the plurality are stored by at least two other computers in the partnership.

34. Computer readable media having stored thereon computer code for a method of backing up data on a plurality of computers connected via a network, the method comprising steps of:

exchanging messages among computers of the plurality to determine the ability of each to satisfy backup storage requirements of one or more others;

forming a partnership among computers of the plurality in which a first computer in the partnership stores backup data received from one or more other computers in the partnership and one or more of the other computers in the partnership store backup data received from the first computer; and

periodically verifying that stored backup data is being retained by one or more of the computers in the partnership.