Apparatus and method for efficiently updating files in computer networks

• US 6,145,012 A
• Filed: 10/14/1998
• Issued: 11/07/2000
• Est. Priority Date: 10/14/1998
• Status: Expired due to Term

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Veritas Software Corporation (Whitehouse Group Ltd.)
• Inventors: Small, Hunter
• Primary Examiner(s): Matar, Ahmad F.
• Assistant Examiner(s): WINDER, PATRICE L
• Application Number:
  US09/173,481
• Time in Patent Office: 755 Days
• Field of Search: 709/204, 709/205, 709/246, 709/217, 709/218, 709/219, 707/10, 707/201, 707/203, 707/204, 707/511, 707/513, 707/531
• US Class Current: 709/246
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

A method of transferring a file is executed by a client computer under control of a first program portion and is alsoexecuted by a server computer under control of a second program portion. The server computer stores a baseline file having baseline data. The client computer stores a local file that is a modified baseline file having modified data. The client computer is coupled to the server computer. First tier baseline reference keys are generated for and associated with first tier subsets of the baseline data stored in the baseline file. First tier client reference keys are generated for and associated with first tier subsets of the modified data stored in the local file. When the associated reference keys match, one of the first tier subsets of baseline data is transferred to a destination file stored on the server computer. When the associated first tier baseline and client reference keys do not match, a second tier baseline reference key is generated for and associated with a second tier baseline subset of one of the first tier subsets of the baseline data. At least one second tier client reference key is generated for and associated with a second tier client subset of one of the first tier subsets of the modified data. The second tier baseline subset or second tier client subset is transferred to the destination file based on the associated second tier baseline and client reference keys.

Claims

1. A method of transferring a file, executed by a client computer under control of a first program portion and also executed by a server computer under control of a second program portion, said server computer storing a baseline file having baseline data, said client computer storing a local file that is a modified baseline file having modified data, said client computer being coupled to said server computer, said method comprising the steps of:

(a) generating and associating first tier baseline reference keys for first tier subsets of said baseline data stored in said baseline file using a predetermined key defining method to generate said first tier baseline reference keys from at least a portion of said associated first tier subset of said baseline data;

(b) generating and associating first tier client reference keys for first tier subsets of said modified data stored in said local file using said key defining method to generate said first tier of client reference keys from at least a portion of said associated first tier subset of said modified data;

(c) transferring one of said first tier subsets of baseline data to a destination file stored on said server computer when said associated first tier baseline reference key and said associated first tier client reference key match;

(d) generating and associating at least one second tier baseline reference key for at least one second tier baseline subset of one of said first tier subsets of said baseline data, and also generating and associating at least one second tier client reference key for at least one second tier client subset of one of said first tier subsets of said modified data, when said associated first tier baseline reference key and said associated first tier client reference key do not match; and

(e) transferring said at least one second tier baseline subset or said at least one second tier client subset to said destination file, based on said associated second tier baseline reference key and said associated second tier client reference key.

2. The method of claim 1 wherein said step (e) of transferring includes the steps of:

transferring said at least one second tier baseline subset to said destination file, when said associated second tier baseline reference key and said associated second tier client reference key match; and

transferring said at least one second tier client subset to said destination file, when said associated second tier baseline reference key and said associated second tier client reference key do not match.

3. The method of claim 2 further comprising the steps of:

(f) determining an offset by comparing said at least one second tier baseline subset and said at least one second tier client subset associated with said non matching second tier baseline and client reference keys;

(g) regenerating said at least one second tier baseline reference key for a portion of said at least one second tier baseline subsets by applying said offset to redefine the portions of baseline data associated with the second tier baseline reference key;

(h) comparing said at least one second tier baseline reference key to said at least one second tier client reference key;

(i) regenerating said first tier baseline reference keys for a portion of said first tier subsets of said baseline data by applying said offset to redefine the portions of the baseline data associated with the first tier baseline reference keys, when said at least one second tier baseline reference key matches said at least one second tier client reference key; and

(j) repeating said steps (c), (d) and (e).

4. The method of claim 1 wherein said first tier subsets of said baseline data are mutually exclusive and said first tier subsets of said modified data are mutually exclusive.

5. The method of claim 1 wherein said first tier subsets are metasegments, and said second tier baseline subsets and said second tier client subsets are segments.

6. The method of claim 1 wherein said step (d) of generating and associated at least one second tier baseline reference key uses said key defining method to generate said at least one second tier baseline reference key from at least a portion of said associated second tier baseline subsets.

7. The method of claim 1 wherein said predetermined key defining method generates a cyclic redundancy code.

8. The method of claim 1 wherein said predetermined key defining method is digital signature encryption.

9. The method of claim 8 wherein said digital signature encryption is a message digest algorithm.

10. The method of claim 1 further comprising the steps of:

(f) transferring only a portion of said modified data from said local file to said destination file, if a predetermined number of said second tier baseline reference keys and second tier client reference keys do not match.

11. The method of claim 1 wherein said server is a mass storage subsystem.

12. A method executed by a client computer under control of a program and also executed by a server computer under control of another program, said server computer storing a baseline file, said client computer storing a local file that is a modified baseline file, said client computer being coupled to said server computer, said method comprising the steps of:

in said server computer,

generating and associating a baseline set of baseline reference keys for a plurality of metasegments of said baseline file using a key defining method that generates said baseline reference keys from at least a portion of said baseline data;

in said client computer,

generating and associating a client set of client reference keys for a plurality of metasegments of said local file using said key defining method;

transferring said client set of client reference keys to said server computer;

in said server computer,

comparing at least one transferred client reference key with at least one baseline reference key;

when said transferred reference key matches said baseline reference key, said server computer copies said metasegment associated with said matched baseline reference key to a destination file on said server computer;

when said transferred reference key does not match said baseline reference key,

said server computer generates a baseline segment set of baseline segment reference keys, a baseline segment reference key being generated for and associated with each segment of said associated metasegment of said non-matching baseline reference key;

said server computer requests said client computer to generate a client segment set of client segment reference keys for said metasegment associated with said non-matching transferred reference key;

in said client computer,

said client computer generates said client segment set of client segment reference keys, one'"'"'s of said client segment reference key being generated for and associated with one'"'"'s of said segments;

transferring said client segment set of client segment reference keys to said server computer;

in said server computer,

comparing at least one transferred client segment reference key with at least one baseline segment reference key;

when said at least one transferred client segment reference key matches said at least one baseline segment reference key, transferring said segment associated with said matched at least one baseline segment reference key from said baseline file to said destination file;

when said at least one transferred client segment reference key does not match said at least one baseline segment reference key, transferring said segment associated with said non-matching at least one client segment reference key from said local file on said client to said destination file on said server computer;

determining an offset by comparing said transferred segment associated with said non-matching at least one client reference key to said segment associated with said non-matching baseline segment reference key;

re-generating said baseline segment reference keys for said uncompared baseline segment reference keys by applying said offset to redefine said segments associated with said uncompared baseline segment reference keys;

comparing at least one of said regenerated baseline segment reference keys to at least one uncompared client segment reference key;

when said at least one compared regenerated baseline segment reference key matches said uncompared base segment reference key, re-generating said baseline reference keys for uncompared baseline metasegments by applying said offset to redefine said metasegments associated with said uncompared baseline segment reference keys; and

repeating from said step of comparing at least one transferred client reference key with at least one baseline reference key, in said server computer.

13. A computer readable memory to direct a computer to function in a specified manner, comprising:

a first module to generate and associate first tier baseline reference keys for first tier subsets of a baseline data stored in a baseline file using a predetermined key defining method to generate said first tier baseline reference keys from at least a portion of said associated first tier subset of said baseline data;

a second module to generate and associate first tier client reference keys for first tier subsets of a modified data stored in a local file using said key defining method to generate said first tier of client reference keys from at least a portion of said associated first tier subset of said modified data;

a third module to transfer one of said first tier subsets of baseline data to a destination file stored on a server computer when said associated first tier baseline reference key and said associated first tier client reference key match;

a fourth module to generate and associate at least one second tier baseline reference key for at least one second tier baseline subset of one of said first tier subsets of said baseline data, and also to generate and associate at least one second tier client reference key for at least one second tier client subset of one of said first tier subsets of said modified data, when said associated first tier baseline reference key and said associated first tier client reference key do not match; and

a fifth module to transfer said at least one second tier baseline subset or said at least one second tier client subset to said destination file, based on said associated second tier baseline reference key and said associated second tier client reference key.

14. The computer readable memory of claim 13 wherein said fifth module includes modules to:

transfer said at least one second tier baseline subset to said destination file, when said associated second tier baseline reference key and said associated second tier client reference key match; and

transfer said at least one second tier client subset to said destination file, when said associated second tier baseline reference key and said associated second tier client reference key do not match.

15. The computer readable memory of claim 13 further comprising:

a sixth module to determine an offset by comparing said at least one second tier baseline subset and said at least one second tier client subset associated with said non matching second tier baseline and client reference keys;

a seventh module to regenerate said at least one second tier baseline reference key for a portion of said at least one second tier baseline subsets by applying said offset to redefine the portions of baseline data associated with the second tier baseline reference key;

an eighth module to compare at least one of said at least one second tier baseline reference key to at least one of said at least one second tier client reference key;

a ninth module to regenerate said first tier baseline reference keys for a portion of said first tier subsets of said baseline data by applying said offset to redefine the portions of the baseline data associated with the first tier baseline reference keys, when said at least one second tier baseline reference key matches said at least one second tier client reference key; and

a tenth module to cause said third, fourth and fifth modules to repeatedly execute.

16. The computer readable memory of claim 13 wherein said first tier subsets of said baseline data are mutually exclusive and said first tier subsets of said modified data are mutually exclusive.

17. The computer readable memory of claim 13 wherein said first tier subsets are metasegments, and said second tier baseline subsets and said second tier client subsets are segments.

18. The computer readable memory of claim 13 wherein said fourth module uses said key defining method to generate said at least one second tier baseline segment reference key from at least a portion of said associated second tier baseline subsets.

19. The computer readable memory of claim 13 wherein said predetermined key defining method generates a cyclic redundancy code.

20. The computer readable memory of claim 13 wherein said predetermined key defining method is digital signature encryption.