Method and systems for efficient delivery of previously stored content

• US 8,838,630 B2
• Filed: 05/28/2010
• Issued: 09/16/2014
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Original Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Inventors: Bots, Henk, Devarajan, Srikanth, Annamalaisami, Saravana
• Primary Examiner(s): Ehichioya, Fred I
• Assistant Examiner(s): GORTAYO, DANGELINO N
• Application Number:
  US12/790,400
• Publication Number:
  US 20100235374A1
• Time in Patent Office: 1,572 Days
• Field of Search: 707/1, 707/3, 707/100, 707/200, 707/204, 707/205, 707/610, 707/624, 707/625, 707/643, 707/758
• US Class Current: 707/758
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image
• CPC Class Codes: Y10S 707/99955 Archiving or backup
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

Systems and methods for reducing file sizes for files delivered over a network are disclosed. A method comprises receiving a first file comprising sequences of data; creating a hash table having entries corresponding to overlapping sequences of data; receiving a second file comprising sequences of data; comparing each of the sequences of data in the second file to the sequences of data in the hash table to determine sequences of data present in both the first and second files; and creating a third file comprising sequences of data from the second file and representations of locations and lengths of said sequences of data present in both the first and second files.

Claims

1. A method comprising:

(a) receiving, by a device having a first file comprising a first plurality of sequences of data, a second file comprising a second plurality of sequences of data, the device creating a hash table comprising entries corresponding to successive, overlapping byte sequences within the first file;

(b) comparing, by the device, hashes for each of the first plurality of sequences of data with hashes for each of the second plurality of sequences of data to identify a first sequence of data and a second sequence of data present in both the first plurality of sequences of data of the first file and the second plurality of sequences of data of the second file; and

(c) establishing, by the device, a third file comprising one or more sequences of data from the second file, a representation of a location identifying a number of bytes in the third file between a predetermined byte of representation of the first sequence of data represented in the third file and a predetermined byte of representation of a second sequence of data represented in the third file, and a representation of a length identifying a number of bytes of the first sequence of data bytes matching the second sequence of data bytes.

2. The method of claim 1, wherein step (b) further comprises:

(i) computing a hash value for a given sequence of data in the second file;

(ii) checking a hash table of the first file for an entry corresponding to the hash value;

(iii) comparing the sequence of data from the second file with a sequence of data in the first file corresponding to said hash table entry; and

(iv) comparing the bytes following the sequence of data from the second file with the bytes following the sequence of data in the first file to determine a length of the first sequence of data present in both the first file and the second file.

3. The method of claim 1, wherein step (c) further comprising representing, by the device, the location as a relative distance from a location in the first file.

4. The method of claim 1, wherein step (c) further comprises translating, by the device, the third file into a byte sequence using a byte encoding protocol.

5. The method of claim 1, wherein step (c) further comprises executing, by the device, a script to create the third file.

6. The method of claim 1, wherein step (c) further comprises establishing, by the device, the representation of the location identifying the number of bytes between a last byte of the first sequence of data and the predetermined byte of the second sequence of data.

7. The method of claim 1, wherein step (c) further comprises establishing, by the device, the representation of the location identifying the number of bytes between the predetermined byte of the first sequence of data and a byte preceding the first byte of the second sequence of data.

8. The method of claim 1, wherein step (c) further comprises establishing, by the device, the representation of the location identifying a number of bytes between the last byte of the first sequence of data and a byte preceding the first byte of the second sequence of data.

9. A system comprising:

a device storing a first file comprising a first plurality of sequences of data, the device creating a hash table comprising entries corresponding to successive, overlapping byte sequences within the first file;

a transceiver of the device receiving a second file comprising a second plurality of sequences of data;

an engine of the device comparing hashes for each of the first plurality of sequences of data with hashes for each of the second plurality of sequences of data to identify a first sequence of data and a second sequence of data present in both the first plurality of sequences of data of the first file and the second plurality of sequences of data of the second file; and

wherein the device establishes a third file comprising one or more sequences of data from the second file, a representation of a location identifying a number of bytes in the third file between a predetermined byte of representation of the first sequence of data represented in the third file and a predetermined byte of representation of a second sequence of data represented in the third file, and a representation of a length identifying a number of bytes of the first sequence of data bytes matching the second sequence of data bytes.

10. The system of claim 9, wherein the engine of the device performs the following:

(i) computing a hash value for a given sequence of data in the second file;

(ii) checking a hash table of the first file for an entry corresponding to the hash value;

(iii) comparing the sequence of data from the second file with a sequence of data in the first file corresponding to said hash table entry; and

(iv) comparing the bytes following the sequence of data from the second file with the bytes following the sequence of data in the first file to determine a length of the first sequence of data present in both the first file and the second file.

11. The system of claim 9, wherein the engine creates the representation of the location as a relative distance from a location in the first file.

12. The system of claim 9, wherein the engine establishes the representation of the location identifying the number of bytes between the last byte of the first sequence of data and the predetermined byte of the second sequence of data.

13. The system of claim 9, wherein the engine establishes the representation of the location identifying the number of bytes between the predetermined byte of the first sequence of data and a byte preceding the first byte of the second sequence of data.

14. The system of claim 9, wherein the engine establishes the representation of the location identifying the number of bytes between the last byte of the first sequence of data and a byte preceding the first byte of the second sequence of data.

15. A system comprising:

a device intermediary to a client and a server, the device storing a first file communicated between the server and the client, the first file comprising a first plurality of sequences of data, the device creating a hash table comprising entries corresponding to successive, overlapping byte sequences within the first file;

a transceiver of the device receiving a second file communicated between the server and the client, the second file comprising a second plurality of sequences of data;

an engine of the device comparing hashes for each of the first plurality of sequences of data with hashes for each of the second plurality of sequences of data to identify a first sequence of data and a second sequence of data present in both the first plurality of sequences of data of the first file and the second plurality of sequences of data of the second file; and

wherein the device establishes a third file comprising one or more sequences of data from the second file, a representation of a location identifying a number of bytes in the third file between a predetermined byte of representation of the first sequence of data represented in the third file and a predetermined byte of representation of a second sequence of data represented in the third file, and a representation of a length identifying a number of bytes of the first sequence of data bytes matching the second sequence of data bytes.

16. The system of claim 15, wherein the device transmits the third file to the client.