SYSTEMS AND METHODS FOR IDENTIFYING LONG MATCHES OF DATA IN A COMPRESSION HISTORY

• US 20100254580A1
• Filed: 05/26/2010
• Published: 10/07/2010
• Est. Priority Date: 03/12/2007
• Status: Active Grant

• Current Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Original Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Inventors: Plamondon, Robert
• Granted Patent: US 8,051,127 B2
• Time in Patent Office: Days
• US Class Current: 382/124
• 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 69/04 Protocols for data compression, e.g. ROHC

Abstract

Systems and methods of storing previously transmitted data and using it to reduce bandwidth usage and accelerate future communications are described. By using algorithms to identify long compression history matches, a network device may improve compression efficiently and speed. A network device may also use application specific parsing to improve the length and number of compression history matches. Further, by sharing compression histories, compression history indexes and caches across multiple devices, devices can utilize data previously transmitted to other devices to compress network traffic. Any combination of the systems and methods may be used to efficiently find long matches to stored data, synchronize the storage of previously sent data, and share previously sent data among one or more other devices.

Claims

1. A method for matching fingerprints of input data to an index of fingerprints identifying locations of stored data, the method comprising:

(a) identifying, by the device, that a first fingerprint of a first portion of input data matches a first entry in an index of fingerprints having a plurality of location identifiers, each of the plurality of location identifiers identifying a location in a storage element storing data;

(b) selecting, by the device, a second entry in the index of fingerprints matching a second fingerprint of a second portion of the input data and having a least number of location identifiers of indexes matching fingerprints for the input data; and

(c) matching, by the device, the input data to data in the location identified by the second entry.

2. The method of claim 1, wherein step (a) further comprises identifying, by the device, that a plurality of fingerprints of portions of the input data each match an entry in the index of fingerprints.

3. The method of claim 1, wherein step (b) further comprises selecting, by the device, the second entry for having a single location identifier.

4. The method of claim 1, wherein step (b) further comprises selecting, by the device, the second entry from a plurality of entries having the least number of location identifiers of indexes matching fingerprints for the input data.

5. The method of claim 1, further comprising performing, by the device, an extended match of the input data to data in locations in storage subsequent to the location identified by the second entry.

6. The method of claim 1, further comprising performing, by the device, a run-length expansion of the match to determine a total length of the matching sequence.

7. The method of claim 1, wherein step (c) further comprises matching, by the device, a second portion of the input data to data adjacent to a portion of data of the location identified by the second entry.

8. The method of claim 1, wherein step (c) further comprises matching, by the device, a second portion of the input data to data adjacent to a portion of data of the location identified by the second entry.

9. The method of claim 1, comprising receiving, by the device, data from network traffic, and using the received data as the input data.

10. The method of claim 1, wherein the device comprises one of a client or a server.

11. The method of claim 1, wherein the device is intermediary to a client and a server.

12. A system for matching fingerprints of input data to an index of fingerprints identifying locations of stored data, the system comprising:

a device identifies that a first fingerprint of a first portion of input data matches a first entry in an index of fingerprints having a plurality of location identifiers, each of the plurality of location identifiers identifying a location in a storage element storing data;

wherein the device selects a second entry in the index of fingerprints matching a second fingerprint of a second portion of the input data and having a least number of location identifiers of indexes matching fingerprints for the input data; and

a compression engine matches the input data to data in the location identified by the second entry.

13. The system of claim 12, wherein the device identifies that a plurality of fingerprints of portions of the input data each match an entry in the index of fingerprints.

14. The system of claim 12, wherein the device selects the second entry for having a single location identifier.

15. The system of claim 12, wherein the device selects the second entry from a plurality of entries having the least number of location identifiers of indexes matching fingerprints for the input data.

16. The system of claim 12, wherein the compression engine performs an extended match of the input data to data in locations in storage subsequent to the location identified by the second entry.

17. The system of claim 12, wherein the compression engine performs a run-length expansion of the match to determine a total length of the matching sequence.

18. The system of claim 12, wherein the compression engine performs matches a second portion of the input data to data adjacent to a portion of data of the location identified by the second entry.

19. The system of claim 12, wherein the compression engine performs matches a second portion of the input data to data adjacent to a portion of data of the location identified by the second entry.

20. The system of claim 12, wherein the devices receives data from network traffic, and uses the received data as the input data.