SYSTEMS AND METHODS FOR SHARING COMPRESSION HISTORIES BETWEEN MULTIPLE DEVICES

• US 20080224903A1
• 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 7,532,134 B2
• Time in Patent Office: Days
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

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 and compression history indexes 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 sharing compression histories among a plurality of devices to improve compression of data transmitted via a plurality of connections, the method comprising:

(a) transmitting, by a first device to a second device, a first data stream, the first data stream compressed according to a first compression history shared between the first device and the second device;

(b) receiving, by the first device, a second data stream intended for a third device;

(c) identifying, by the first device, that a portion of the second data stream matches a portion of the first compression history; and

(d) transmitting, by the first device to the second device, information identifying the portion of the first compression history.

2. The method of claim 1, wherein at least one of the first device, the second device, or the third device comprises a transparent proxy.

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

4. The method of claim 1, wherein step (c) comprises identifying, by the first device, that a portion of the second data stream matches within a predetermined threshold a portion of the first compression history.

5. The method of claim 1, wherein step (c) comprises identifying, by the first device using a byte-by-byte comparison, that a portion of the second data stream matches a portion of the first compression history.

6. The method of claim 1, wherein step (c) comprises identifying, by the first device using a byte-by-byte comparison, that a portion of the second data stream matches a predetermined number of bytes of a portion of the first compression history.

7. The method of claim 1, wherein step (c) comprises identifying, by the first device using a data fingerprinting technique, that a portion of the second data stream matches a portion of the first compression history.

8. The method of claim 1, wherein step (c) further comprises identifying, by the first device, that the third device is connected via a local area network to the second device.

9. The method of claim 1, wherein step (d) comprises transmitting, by the first device to the third device, a portion of the second data stream, the portion of the second data stream compressed according to the portion the first compression history.

10. The method of claim 1, wherein step (d) comprises transmitting, by the first device to the third device, a portion of the second data stream, the second data stream compressed according to at least one portion of the first compression history and at least one portion of a second compression history, the second compression history shared between the first device and the third device.

11. The method of claim 1, wherein step (d) comprises transmitting, by the first device to the third device, information identifying a compression history chunk stored on the second device.

12. The method of claim 1, wherein step (d) comprises transmitting, by the first device to the third device, information identifying the portion of the first compression history and identifying at least one subsequent location in the first compression history.

13. The method of claim 1, further comprising

(e) determining, by the third device, a chunk identifier received from the first device corresponds to a chunk located on the second device.

14. The method of claim 1, further comprising:

(e) -determining, by the third device, a chunk identifier received from the first device is within a range of values associated with the second device.

15. The method of claim 1, further comprising:

(e) -transmitting, by the third device to the second device, information identifying the portion of the first compression history and a request to begin transmitting the portion of the first compression history to the third device.

16. The method of claim 15, further comprising:

(f) -receiving, by the third device, the identified portion of the first compression history.

17. The method of claim 15, further comprising:

(f) decompressing, by the third device, a portion of the second data stream using the portion of the first compression history.

18. The method of claim 1, further comprising:

(e) transmitting, by the third device to the second device, information identifying the portion of the first compression history and a request to begin transmitting the portion of the first compression history to the third device and at least one subsequent portion of the first compression history.

19. The method of claim 1, further comprising:

(e) receiving, by the first device from the third device, an indication that the third device is located on the same network as the second device.

20. The method of claim 19, further comprising:

(f) transmitting, by the first device to the third device in response to the indication, the second data stream, the second data stream compressed according to the portion of the first compression history.

21. A first device for sharing compression histories among a plurality of devices to improve compression of data transmitted via a plurality of connections, the first device comprising:

a packet processor which transmits, to a second device, a first data stream, the first data stream compressed according to a first compression history shared between the first device and the second device; and

receives a second data stream intended for a third device; and

a compression engine which identifies that a portion of the second data stream matches a portion of the first compression history; and

transmits, to the second device, information identifying the portion of the first compression history.

22. The system of claim 21, wherein at least one of the first device, second device, or third device comprises a transparent proxy.

23. The system of claim 21, wherein the first device comprises one of a client, a server, or a network appliance.

24. The system of claim 21, wherein the compression engine identifies, using a byte-by-byte comparison, that a portion of the second data stream matches within a predetermined threshold a portion of the first compression history.

25. The system of claim 21, wherein the compression engine identifies, using a byte-by-byte comparison, that a portion of the second data stream matches a predetermined number of bytes of a portion of the first compression history.

26. The system of claim 21, wherein the compression engine identifies, using a data fingerprinting technique, that a portion of the second data stream matches within a predetermined threshold a portion of the first compression history.

27. The system of claim 21, wherein the compression engine identifies that the third device is connected via a local area network to the second device.

28. The system of claim 21, wherein the compression engine transmits, to the third device, the second data stream, the second data stream compressed according to the portion the first compression history.

29. The system of claim 21, wherein the compression engine transmits, to the third device, the second data stream, the second data stream compressed according to at least one portion of the first compression history and at least one portion of a second compression history, the second compression history shared between the first device and the third device.

30. The system of claim 21, wherein the compression engine transmits, to the third device, information identifying a compression history chunk stored on the second device.

31. The system of claim 21, wherein the compression engine transmits, to the third device, information identifying the portion of the first compression history and identifying at least one subsequent location in the first compression history.

32. The system of claim 21, wherein the third device determines a chunk identifier received from the first device corresponds to a chunk located on the second device.

33. The system of claim 21, wherein the third device transmits, to the second device, information identifying the portion of the first compression history and a request to begin transmitting the portion of the first compression history to the third device.

34. The system of claim 21, wherein the third device receives the identified portion of the first compression history.

35. The system of claim 21, wherein the third device decompresses a portion of the second data stream using the portion of the first compression history.

36. The system of claim 21, wherein the third device transmits, to the second device, information identifying the portion of the first compression history and a request to begin transmitting the portion of the first compression history to the third device and at least one subsequent portion of the first compression history.

37. A system for sharing compression histories among a plurality of devices to improve compression of data transmitted via a plurality of connections, the system comprising:

means for transmitting, by a first device to a second device, a first data stream, the first data stream compressed according to a first compression history shared between the first device and the second device;

means for receiving, by the first device, a second data stream intended for a third device;

means for identifying, by the first device, that a portion of the second data stream matches a portion of the first compression history; and

means for transmitting, by the first device to the second device, information identifying the portion of the first compression history.

38. A method for sharing compression histories among a plurality of devices to improve compression of data transmitted via a plurality of connections, the method comprising:

(a) transmitting, between a first device and a second device, a first data stream, the first data stream compressed according to a first compression history shared between the first device and the second device;

(b) receiving, by the first device from a third device, information identifying a portion of the first compression history; and

(c) transmitting, by the first device to the third device, the identified portion of the first compression history.

39. The method of claim 38, wherein step (a) comprises transmitting, from the first device to the second device, the-first data stream, the first data stream compressed according to the first compression history shared between the first device and the second device.

40. The method of claim 38, wherein step (b) comprises receiving, by the first device from the second device, the first data stream, the first data stream compressed according to the first compression history shared between the first device and the second device.

41. The method of claim 38, wherein step (c) comprises transmitting, by the first device to the third device, the identified portion of the first compression history and at least one subsequent portion of the first compression history.

42. A first device for sharing compression histories among a plurality of devices to improve compression of data transmitted via a plurality of connections, the first device comprising:

a packet processor which transmits, to a second device, a first data stream, the first data stream compressed according to a first compression history shared between the first device and the second device; and

which receives, from the second device, information identifying a third device and a portion of the first compression history; and

a compression engine in communication with the packet processor which transmits, by the first device to the third device, the identified portion of the first compression history.

43. The system of claim 42, wherein the compression engine transmits, to the third device, the identified portion of the first compression history and at least one subsequent portion of the first compression history.

44. A method for sharing compression histories among a plurality of devices to improve compression of data transmitted via a plurality of connections, the method comprising:

(a) receiving, by a first device from a second device, a data stream, the data stream compressed according to a compression history shared between the first device and a third device;

(b) identifying, by the first device, the third device;

(c) transmitting, by the first device to the third device, a request for a portion of the compression history;

(d) receiving, by the first device from the third device, the requested portion of the compression history; and

(e) decompressing, by the first device, the data stream.

45. The method of claim 44, wherein the data stream is also compressed according to a compression history shared between the first and second devices.

46. The method of claim 44, wherein the data stream comprises a number of location identifiers identifying chunks located in a compression history of the third device.

47. The method of claim 44, wherein step (b) comprises identifying the third device based on a chunk identifier contained in the data stream.

48. The method of claim 44, further comprising:

(f) receiving, from the third device, information identifying a number of chunks residing on the third device.

49. The method of claim 44, wherein step (b) comprises identifying the third device by determining that a location identifier contained in the data stream is within a range of values associated with the third device.

50. The method of claim 44, further comprising:

(f) transmitting, by the first device to the second device, an indication that the third device is connected by a LAN with the first device.

51. The method of claim 44, further comprising:

(f) transmitting the decompressed data stream to a client.

52. A first device for sharing compression histories among a plurality of devices to improve compression of data transmitted via a plurality of connections, the first device comprising:

a packet processor which receives from a second device, a data stream, the data stream compressed according to a compression history shared between the first device and a third device; and

a compression engine, in communication with the packet processor, which identifies the third device;

transmits, to the third device, a request for a portion of the compression history;

receives, from the third device, the requested portion of the compression history; and

decompresses the data stream.

53. The system of claim 52, wherein the data stream is also compressed according to a compression history shared between the first and second devices.

54. The system of claim 52, wherein the data stream comprises a number of location identifiers identifying chunks located in a compression history of the third device.

55. The system of claim 52, wherein the compression engine identifies the third device based on a chunk identifier contained in the data stream.

56. The system of claim 52, wherein the compression engine receives, from the third device, information identifying a number of chunks residing on the third device.

57. The system of claim 52, wherein the compression engine determines that a location identifier contained in the data stream is within a range of values associated with the third device.

58. The system of claim 52, wherein the compression engine transmits, to the second device, an indication that the third device is connected by a LAN with the first device.

59. The system of claim 52, wherein the packet processor transmits the decompressed data stream to a client.

60. A system for sharing compression histories among a plurality of devices to improve compression of data transmitted via a plurality of connections, the system comprising:

means for receiving, by a first device from a second device, a data stream, the data stream compressed according to a compression history shared between the first device and a third device;

means for identifying, by the first device, the third device;

means for transmitting, by the first device to the third device, a request for a portion of the compression history;

means for receiving, by the first device from the third device, the requested portion of the second history; and

means for decompressing, by the first device, the data stream.