Systems and methods for enhanced delta compression

Patent metadata

Field	Value
Publication number	US-9621666-B2
Application number	US-201414448642-A
Country	US
Kind code	B2
Filing date	Jul 31, 2014
Priority date	May 26, 2005
Publication date	Apr 11, 2017
Grant date	Apr 11, 2017

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.

First claim

What is claimed:

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

Assignees

• Citrix Systems Inc

Inventors

• Bots Henk
• Devarajan Srikanth
• Annamalaisami Saravana
• Stavrakos Nicholas
• Monks Jeff
• Koopmans Fred
• Koopmans Chris
• Dakhane Kapil

Classifications

• G06F17/30902

  Physics · mapped topic

• H04W8/245

  from a network towards a terminal · CPC title

• H04L67/2828 Primary

  Electricity · mapped topic

• H04W80/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)} · CPC title

• H04L67/06

  specially adapted for file transfer, e.g. file transfer protocol [FTP] · CPC title