Systems and methods for enhanced delta compression

• US 9,621,666 B2
• Filed: 07/31/2014
• Issued: 04/11/2017
• Est. Priority Date: 05/26/2005
• 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, Stavrakos, Nicholas, Monks, Jeff, Koopmans, Fred, Koopmans, Chris, Dakhane, Kapil
• Primary Examiner(s): PHAN, MAN U
• Application Number:
  US14/448,642
• Publication Number:
  US 20150026567A1
• Time in Patent Office: 985 Days
• Field of Search: 709203-218, 707640-694, 707741-798, 707200-203, 715242-511
• CPC Class Codes: G06F 16/116 Details of conversion of file system types or formats
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• 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 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/5651 Reducing the amount or size of exchanged application data
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04W 8/245 from a network towards a terminal
• CPC Class Codes: H04W 80/06 Transport layer protocols, e.g. TCP [Transport Control Protocol] over wireless transmission control protocol/Internet protocol [TCP/IP] or user datagram protocol [UDP] H04L69/16

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 intermediary to a plurality of clients and a server, a response from the server to a request for a web page by a client of the plurality of clients, the device storing a first file comprising a first plurality of sequences of data from a previous response served by the server;

(b) generating, by the device, an object list identifying object data within the response that is to be downloaded to the client;

(c) maintaining, by the device, a hash table having a plurality of entries, each of the plurality of entries corresponding to a respective one of a first plurality of sequences of data in the first file, and wherein at least two of the entries correspond to overlapping sequences of data;

(d) computing, by the device, hash values of a second plurality of sequences of data from the response for a second file;

(e) comparing, by the device, each of the second plurality of sequences of data with sequences from the first plurality of sequences having the same hash value to determine sequences of data present in both the first file and second file;

(f) creating, by the device, a third file comprising sequences of data from the second file, a first representation of a location and a length of a first sequence of data present in both the first file and second file and a second representation of a location and a length of a second sequence of data present in both the first file and the second file, the second representation of the location of the second sequence of data identifying a number of bytes between the first sequence of data and the second sequence of data in the first file, the first representation of the length of the first sequence of data identifying a number of matching bytes of the first sequence of data and the second representation of the length of the second sequence of data identifying a number of matching bytes of the second sequence of data; and

(g) transmitting, by the device, the third file and the object list to the client.

2. The method of claim 1, wherein (b) further comprises determining, by the device, whether each object data within the response is to be downloaded to a user agent of the client and generating the object list based on the determination.

3. The method of claim 1, further comprising receiving, by the device, request object data constructed by the client using the object list, the request object data comprising a request object list identifying object data and freshness data indicating that the object data is one of fresh or stale.

4. The method of claim 1, further comprising determining, by the device, whether object data within the response matches object data of the request object data.

5. The method of claim 4, further comprising indicating, by the device, that the object data is to be downloaded if the object data within the response does not match the object data of request object data.

6. The method of claim 4, further comprising determining, by the device, whether object data of the request object data is indicated by freshness data to be fresh or stale responsive to the object data within the response matching the object data of the request object data.

7. The method of claim 6, further comprising verifying with the server the request object data is fresh or stale if the request object data is indicated by the freshness data to be stale.

8. The method of claim 7, further comprising indicating that the object data is to be downloaded if the request object data is verified to be stale.

9. The method of claim 1, wherein (f) further comprises creating the third file comprising sequences of data from the second file and representations of locations and lengths of sequences present in both the first file and the second file, wherein the locations are represented as a relative distance from a location in the first file.

10. The method of claim 1, wherein (f) further comprises creating the third file comprising sequences of data from the second file and representations of locations and lengths of sequences present in both the first file and the second file, wherein the third file is translated into a byte sequence using a byte encoding protocol.

11. A system comprising:

a device intermediary to a plurality of clients and one or more servers, the device configured to receive a response from the server to a request for a web page by a client of the plurality of clients and configured to store a first file comprising a first plurality of sequences of data from a previous response served by the server;

a generator of the device configured to generate an object list identifying object data within the response that is to be downloaded to the client;

a hash engine of the device configured to maintain a hash table having a plurality of entries, each of the plurality of entries corresponding to a first plurality of sequences of data in the first file, and wherein at least two of the entries correspond to overlapping sequences of data;

wherein the hash engine is configured to compute hash values of a second plurality of sequences of data of the response for a second file;

wherein the device is configured to compare each of the second plurality of sequences of data with sequences from the first plurality of sequences having the same hash value to determine sequences of data present in both the first file and the second file; and

create a third file comprising sequences of data from the second file, a first representation of a location and a length of a first sequence of data present in both the first file and second file and a second representation of a location and a length of a second sequence of data present in both the first file and the second file, the second representation of the location of the second sequence of data identifying a number of bytes between the first sequence of data and the second sequence of data in the first file, the first representation of the length of the first sequence of data identifying a number of matching bytes of the first sequence of data and the second representation of the length of the second sequence of data identifying a number of matching bytes of the second sequence of data; and

wherein the device is configured to transmit the third file and the object list to the client.

12. The system of claim 11, wherein the generator is further configured to determine whether each object data within the response is to be downloaded to a user agent of the client and generating the object list based on the determination.

13. The system of claim 11, wherein the device is further configured to receive request object data constructed by the client using the object list, the request object data comprising a request object list identifying object data and freshness data indicating that the object data is one of fresh or stale.

14. The system of claim 11, wherein the device is further configured to determine whether object data within the response matches object data of the request object data.

15. The system of claim 14, wherein the device is further configured to indicate that the object data is to be downloaded if the object data within the response does not match the object data of request object data.

16. The system of claim 14, wherein the device is further configured to determine whether object data of the request object data is indicated by freshness data to be fresh or stale responsive to the object data within the response matching the object data of the request object data.

17. The system of claim 16, wherein the device is further configured to verify with the server the request object data is fresh or stale if the request object data is indicated by the freshness data to be stale.

18. The system of claim 17, wherein the device is further configured to indicate that the object data is to be downloaded if the request object data is verified to be stale.

19. The system of claim 11, wherein the device is further configured to create the third file comprising sequences of data from the second file and representations of locations and lengths of sequences present in both the first file and the second file, wherein the locations are represented as a relative distance from a location in the first file.

20. The system of claim 11, wherein the device is further configured to create the third file comprising sequences of data from the second file and representations of locations and lengths of sequences present in both the first file and second the second file, wherein the third file is translated into a byte sequence using a byte encoding protocol.