Systems and methods for identifying long matches of data in a compression history
First Claim
1. A method for matching fingerprints of input data to an index of fingerprints identifying locations of stored data, the method comprising:
- (a) identifying, by the device, that a first fingerprint of a first portion of input data matches a first entry in an index of fingerprints having a plurality of location identifiers, each of the plurality of location identifiers identifying a location in a storage element storing data;
(b) selecting, by the device, a second entry in the index of fingerprints matching a second fingerprint of a second portion of the input data and having a least number of location identifiers of indexes matching fingerprints for the input data; and
(c) matching, by the device, the input data to data in the location identified by the second 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.
243 Citations
20 Claims
-
1. A method for matching fingerprints of input data to an index of fingerprints identifying locations of stored data, the method comprising:
-
(a) identifying, by the device, that a first fingerprint of a first portion of input data matches a first entry in an index of fingerprints having a plurality of location identifiers, each of the plurality of location identifiers identifying a location in a storage element storing data; (b) selecting, by the device, a second entry in the index of fingerprints matching a second fingerprint of a second portion of the input data and having a least number of location identifiers of indexes matching fingerprints for the input data; and (c) matching, by the device, the input data to data in the location identified by the second entry. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A system for matching fingerprints of input data to an index of fingerprints identifying locations of stored data, the system comprising:
-
a device identifies that a first fingerprint of a first portion of input data matches a first entry in an index of fingerprints having a plurality of location identifiers, each of the plurality of location identifiers identifying a location in a storage element storing data; wherein the device selects a second entry in the index of fingerprints matching a second fingerprint of a second portion of the input data and having a least number of location identifiers of indexes matching fingerprints for the input data; and a compression engine matches the input data to data in the location identified by the second entry. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20)
-
Specification