SYSTEMS AND METHODS OF COMPRESSION HISTORY EXPIRATION AND SYNCHRONIZATION

• US 20080229137A1
• Filed: 03/12/2007
• Published: 09/18/2008
• 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: Samuels, Allen, Decasper, Dan, Dittia, Zubin, Jensen, Richard, Plamondon, Robert, Ovsiannikov, Michael
• Granted Patent: US 8,255,570 B2
• Time in Patent Office: Days
• US Class Current: 713/600
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• 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 synchronizing compression histories shared between two devices, the method comprising:

(a) storing, by a first device, a first compression history, the compression history comprising a plurality of portions of data previously transmitted to a second device, each portion of data having a location identifier;

(b) creating, by the first device, an ordered list of location identifiers ordered by a time the first device last accessed a portion of data in a location corresponding to each identifier;

(c) receiving, by the first device from the second device, information identifying a quantity of location identifiers of a corresponding second compression history on the second device;

(d) determining, by the first device, the received quantity is less than a quantity of location identifiers of the first compression history by a first amount; and

(e) selecting for obsolescence, from the list of location identifiers, the first amount of location identifiers at an end of the ordered list corresponding to least recently accessed portions of data.

2. The method of claim 1, further comprising deactivating, by the first device from the first compression history, the portions of data corresponding to the selected identifiers.

3. The method of claim 1, wherein the device comprises a transparent proxy.

4. The method of claim 1, wherein the device comprises a transparent proxy performing wide area network (WAN) acceleration functions.

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

6. The method of claim 1, wherein step (a) comprises storing, by a first device, a first compression history, the compression history comprising a plurality of portions of data previously transmitted to a second device, each portion of data having a globally unique location identifier.

7. The method of claim 1, wherein step (b) comprises inserting, by the first device in response to accessing a portion of data in the first compression history, a location identifier corresponding to the portion of data to the head of the list of identifiers.

8. The method of claim 1, wherein step (b) comprises inserting, by the first device in response to creating a portion of data in the first compression history, a location identifier corresponding to the portion of data to the head of the list of identifiers.

9. The method of claim 1, wherein step (c) comprises receiving, by the first device from the second device in response to establishing a connection with the second device, information identifying a quantity of location identifiers of a corresponding second compression history on the second device.

10. The method of claim 1, further comprising deleting, by the first device from the first compression history, the portions of data corresponding to the selected identifiers.

11. The method of claim 1, further comprising removing, by the first device from the list of location identifiers, the selected identifiers.

12. The method of claim 1, further comprising deactivating, by the first device from the first compression history, the portions of data corresponding to the selected identifiers, and wherein at least one of the deactivated portions is maintained as active with respect to a third compression history on the first device.

13. A device which synchronizes compression histories shared between the device and a second device, the device comprising:

a storage element which stores a first compression history, the compression history comprising a plurality of chunks comprising data previously transmitted to a second device, each chunk having a unique identifier; and

a compression engine in communication with the storage element which maintains a list of chunks wherein the chunks are ordered according to the time last accessed;

receives, from the second device, an indication of the number of chunks in a corresponding second compression history on the second computing device;

determines that the received number is less than the number of chunks in the first compression history by an amount; and

deactivates by the first device from the first compression history, the amount of chunks, wherein the selected chunks comprise the least recently used chunks.

14. The system of claim 13, wherein the compression engine deactivates, from the first compression history, the portions of data corresponding to the selected identifiers.

15. The system of claim 13, wherein the device comprises a transparent proxy.

16. The system of claim 13, wherein the device comprises a transparent proxy performing wide area network (WAN) acceleration functions.

17. The system of claim 13, wherein the device comprises one of a client, a server, or a network appliance.

18. The system of claim 13, wherein the storage element stores a first compression history, the compression history comprising a plurality of portions of data previously transmitted to a second device, each portion of data having a globally unique location identifier.

19. The system of claim 13, wherein the storage element stores a first compression history, the compression history comprising a plurality of chunks comprising data previously transmitted to a second device, each chunk of data having a globally unique location identifier.

20. The system of claim 13, wherein the compression engine inserts, in response to accessing a portion of data in the first compression history, a location identifier corresponding to the portion of data to the head of the list of identifiers.

21. The system of claim 13, wherein the compression engine inserts, in response to creating a portion of data in the first compression history, a location identifier corresponding to the portion of data to the head of the list of identifiers.

22. The system of claim 13, wherein the compression engine receives, from the second device in response to establishing a connection with the second device, information identifying a quantity of location identifiers of a corresponding second compression history on the second device.

23. The system of claim 13, wherein the compression engine deletes, from the first compression history, the portions of data corresponding to the selected identifiers.

24. The system of claim 13, wherein the compression engine removes, from the list of location identifiers, the selected identifiers.

25. The system of claim 13, wherein the compression engine deactivates, from the first compression history, the portions of data corresponding to the selected identifiers, and maintains at least one of the deactivated portions as active with respect to a third compression history on the first device.