Systems and methods for identifying long matches of data in a compression history
First Claim
1. A method of determining a precedence for matching fingerprints of input data to an index of fingerprints identifying a plurality of instances of data in a compression history, the method comprising the steps of:
- (a) establishing, by a device having a compression history, an index that corresponds fingerprints of a plurality of portions of data of the compression history to location identifiers identifying locations in a storage element having the plurality of portions of data;
(b) identifying, by the device, that a plurality of fingerprints of input data match a plurality of entries in the index having at least one location identifier;
(c) selecting, by the device, an entry of the plurality of entries having a fewest number of location identifiers; and
(d) matching, by the device, a first portion of the input data to data in a first location in the compression history identified by the selected entry.
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
23 Claims
-
1. A method of determining a precedence for matching fingerprints of input data to an index of fingerprints identifying a plurality of instances of data in a compression history, the method comprising the steps of:
-
(a) establishing, by a device having a compression history, an index that corresponds fingerprints of a plurality of portions of data of the compression history to location identifiers identifying locations in a storage element having the plurality of portions of data; (b) identifying, by the device, that a plurality of fingerprints of input data match a plurality of entries in the index having at least one location identifier; (c) selecting, by the device, an entry of the plurality of entries having a fewest number of location identifiers; and (d) matching, by the device, a first portion of the input data to data in a first location in the compression history identified by the selected entry. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. In a network environment including an appliance intercepting and forwarding communications between a client requesting objects and a server responding to client requests, the appliance determining a precedence for matching fingerprints of input data to an index of fingerprints identifying a plurality of instances of data in a compression history, the appliance comprising:
-
an index that corresponds fingerprints of a plurality of portions of data of a compression history to location identifiers identifying locations in a storage element having the plurality of portions of data; and a compression engine which identifies, by the device, that a plurality of fingerprints of input data match a plurality of entries in the index having at least one location identifier;
selects, by the device, an entry of the plurality of entries having a fewest number of location identifiers; and
matches, by the device, a first portion of the input data to data in a first location in the compression history identified by the selected entry. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
Specification