Systems and methods of compression history expiration and synchronization
First Claim
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 first compression history comprising a plurality of portions of data previously transmitted to a second device, each portion of data having a location identifier, the first compression history maintaining a first quantity of location identifiers;
(b) creating, by the first device, an ordered list of location identifiers ordered by a time the first device last used a portion of data in a location corresponding to each location identifier to compress data streams transmitted to the second device, the first device placing at a front of the ordered list location identifiers to newly used portions of the compression history as the newly used portions are used to compress data streams transmitted to the second device;
(c) receiving, by the first device from the second device, information identifying a second quantity of location identifiers stored on the second device'"'"'s compression history that correspond to the first compression history of the first device;
(d) determining, by the first device, the second quantity is less than the first 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 used portions of data for compression between the first device and the second device.
8 Assignments
0 Petitions
Accused Products
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.
-
Citations
26 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 first compression history comprising a plurality of portions of data previously transmitted to a second device, each portion of data having a location identifier, the first compression history maintaining a first quantity of location identifiers; (b) creating, by the first device, an ordered list of location identifiers ordered by a time the first device last used a portion of data in a location corresponding to each location identifier to compress data streams transmitted to the second device, the first device placing at a front of the ordered list location identifiers to newly used portions of the compression history as the newly used portions are used to compress data streams transmitted to the second device; (c) receiving, by the first device from the second device, information identifying a second quantity of location identifiers stored on the second device'"'"'s compression history that correspond to the first compression history of the first device; (d) determining, by the first device, the second quantity is less than the first 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 used portions of data for compression between the first device and the second device. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
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 first compression history comprising a plurality of portions of data previously transmitted to a second device, each portion of data having a location identifier, the first compression history maintaining a first number of location identifiers; and
a compression engine in communication with the storage element which maintains a list of location identifiers wherein the location identifiers are ordered according to the time last used a portion of data in a location corresponding to each location identifier to compress data streams transmitted to the second device, the compressing engine placing at a front of the list location identifiers to newly used portions of data of the compression history as the newly used portions of data are used to compress data streams transmitted to the second device; receives, from the second device, information identifying a second number of location identifiers stored on the second device'"'"'s compression history that correspond to the first compression history of the device; determines that the second number of location identifiers is less than the first number of location identifiers in the first compression history by an amount; and
selecting for obsolescence from the list of location identifies of the first compression history the amount of location identifiers at the end of the ordered list corresponding to the least recently used portions of data for compression between the first device and the second device. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
- a storage element which stores a first compression history, the first compression history comprising a plurality of portions of data previously transmitted to a second device, each portion of data having a location identifier, the first compression history maintaining a first number of location identifiers; and
-
26. A method for synchronizing compression histories shared between two devices, each device deployed between one or more clients and one or more servers, the method comprising:
-
(a) storing, by a first device deployed between one or more clients and one or more servers, a first compression history, the first compression history comprising a plurality of portions of data previously transmitted to a second device, each portion of data from the plurality of portions of data having a location identifier; (b) creating, by the first device, an ordered list of location identifiers ordered by a last time the first intermediary device used each portion of data for compressing one or more data streams; (c) receiving, by the first device from the second device deployed between one or more clients and one or more servers, information identifying a total number of portions of data stored on the second device'"'"'s compression history that correspond to the first compression history of the first device; (d) determining, by the first device, an amount of difference between the received total number and a total number of portions of data of the first compression history; and (e) selecting for obsolescence, from an end of the ordered list of location identifiers, an amount of location identifiers equal to the determined amount of difference, the selected list of local identifiers corresponding to those portions of data least recently used for compressing one or more data streams.
-
Specification