Systems and methods for identifying long matches of data in a compression history

• US 8,832,300 B2
• Filed: 08/06/2012
• Issued: 09/09/2014
• 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 D.
• Primary Examiner(s): JEAN, FRANTZ B
• Application Number:
  US13/567,452
• Publication Number:
  US 20120300993A1
• Time in Patent Office: 764 Days
• Field of Search: 709/203, 709/217, 709/231, 709/247, 709/223, 709/219, 341/51, 382/124, 382/233, 382/232
• US Class Current: 709/231
• 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 comprising:

(a) establishing by a device a compression index comprising indexes of fingerprints of data stored in a plurality of storage locations of a compression history;

(b) identifying, by the device, that a fingerprint of data from network traffic received by the device matches a plurality of indexes in the compression index,

(c) selecting, by the device, an index from the plurality of matching indexes that identifies a number of storage location identifiers less than one or more of the other indexes of the plurality of matching indexes; and

(d) performing, by the device, a match of the data across one or more storage locations subsequent to a storage location identified by a storage location identifier of the selected index the one or more subsequent storage locations identified by one or more storage location identifiers different than the storage location identifier of the selected index.

2. The method of claim 1, wherein step (a) further comprises storing, by the device, data from network traffic received by the device in the plurality of storage locations of the compression history.

3. The method of claim 1, wherein step (a) further comprises establishing, by the device, each index of the plurality of indexes to identify one or more storage location identifiers.

4. The method of claim 1, wherein step (a) further comprises storing, by the device, with each index in the compression index a count of a number of storage location identifiers having matching fingerprints.

5. The method of claim 1, wherein step (c) further comprises selecting, by the device, the index identifying a single storage location identifier.

6. The method of claim 1, wherein step (c) further comprises selecting, by the device, the index having a least number of storage location identifiers.

7. The method of claim 1, wherein step (d) further comprises determining, by the device, a length of the match of the data across one or more storage locations subsequent to a storage location identified by a storage location identifier of the selected index.

8. The method of claim 1, wherein step (d) further comprises performing, by the device, an expansion of the match from the storage location identified by the storage location identifier of the index to the one or more one or more storage locations subsequent to the storage location.

9. The method of claim 1, wherein step (d) further comprises determining, by the device, the length of the match exceeds a threshold.

10. The method of claim 9, further comprising responsive to the determination, compressing by the device the data using data stored in the storage location identified by the selected index and data stored across one or more storage locations subsequent to the storage location identified by the storage location identifier of the index.

11. A system comprising:

a device having a compression index comprising indexes of fingerprints of data stored in the plurality of storage locations of a compression history;

a compression engine identifying that a fingerprint of data from network traffic received by the device matches a plurality of indexes in the compression index and selecting an index identifying a number of storage location identifiers less than one or more of the other indexes of the plurality of matching indexes; and

wherein the compression engine performs a match of the data across one or more storage locations subsequent to a storage location identified by a storage location identifier of the selected index, the one or more subsequent storage locations identified by one or more storage location identifiers different than the storage location identifier of the selected index.

12. The system of claim 11, wherein the device stores data from network traffic received by the device in the plurality of storage locations of the compression history.

13. The system of claim 11, wherein the device establishes each index of the plurality of indexes to identify one or more storage location identifiers corresponding to a storage location of the plurality of storage locations of the compression history.

14. The system of claim 11, wherein the device stores with each index in the compression index a count of a number of storage location identifiers having matching fingerprints.

15. The system of claim 11, wherein the compression engine selects the index identifying a single storage location identifier.

16. The system of claim 11, wherein the compression engine selects the index having a least number of storage location identifiers.

17. The system of claim 11, wherein the compression engine determines a length of the match of the data across one or more storage locations subsequent to a storage location identified by a storage location identifier of the index.

18. The system of claim 11, wherein the compression engine performs an expansion of the match from the storage location identified by the storage location identifier of the index to the one or more one or more storage locations subsequent to the storage location.

19. The system of claim 11, wherein the compression engine determines the length of the match exceeds a threshold.

20. The system of claim 11, further comprising responsive to the determination, the compression engine compresses the data using stored in the storage location identified by the selected index and data stored across one or more storage locations subsequent to the storage location identified by the storage location identifier of the index.