Compression of data transmitted over a network

• US 9,002,806 B1
• Filed: 12/08/2010
• Issued: 04/07/2015
• Est. Priority Date: 12/30/2005
• Status: Active Grant

• Current Assignee: F5 Networks, Inc. (F5 Incorporated)
• Original Assignee: F5 Networks, Inc. (F5 Incorporated)
• Inventors: Amdahl, Saxon C.
• Primary Examiner(s): LU, KUEN S
• Application Number:
  US12/963,531
• Time in Patent Office: 1,581 Days
• Field of Search: 707/693, 707/697
• US Class Current: 707/693
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A system, method, and apparatus are directed towards identifying adaptive length segments of redundant data for encoding a data structure. Initial boundaries are identified for an input matching segment within input data and for a candidate store matching segment in a synchronized store. The data prior to and after the boundaries are compared to identify matching data. As matching data is identified, at least one of the boundaries of the matching segments is revised. An encoded representation of the resulting input matching segment is then generated based in part on pointers and offsets into the synchronized store. A data structure is generated based on the encoded representation and unmatched portion, which is sent to a receiver. The receiver uses the data structure to extract matching data from the synchronized store, and together with the unmatched input data in the data structure, reconstruct the input data.

Claims

1. A method operating on one or more network devices, comprising:

receiving input data;

selecting a candidate input matching data segment from within the input data by sliding a window over the input data and for each of a plurality of different locations of the sliding window determining a fitness function from a portion of the input data within the sliding window and further selecting a portion of the input data having a determined best fitness function value by performing a comparison between each of the determined fitness functions;

determining a corresponding candidate store matching segment of data in a synchronized store based on an index determined from the selected candidate input matching data segment, the index being used to obtain a file identifier and offset that is then used to locate within the synchronized store the candidate store matching segment;

selectively revising at least one boundary of the candidate input matching data segment by comparing data contiguous with the candidate store matching segment with data contiguous with the candidate input matching data segment to generate an input matching data segment of the input data;

determining an encoded representation of the input matching data segment at least partly based on the synchronized store; and

transmitting over a network a data structure that includes at least a portion of an unmatched portion of the data within the input data and the encoded representation.

2. The method of claim 1, further comprising:

receiving the transmitted data structure;

extracting from the data structure, an other file identifier, an other offset, a matching segment length;

employing the other file identifier, other offset, and matching segment length to extract data from a second synchronized store that matches the input matching data segment; and

combining the unmatched portion of the data with the extracted data.

3. The method of claim 1, wherein selectively revising at least one boundary further comprises selectively revising a corresponding boundary of the candidate store matching segment based on the boundaries of the input matching data segment.

4. The method of claim 1, wherein the input matching data segment includes data prior to the candidate input matching data segment and excludes the candidate input matching data segment.

5. The method of claim 1, wherein the determined input matching data segment includes a first portion of the selected candidate input matching data segment and excludes a second portion of the selected candidate input matching data segment.

6. The method of claim 1, wherein the input matching data segment includes the candidate input matching data segment and data prior to the candidate input matching data segment.

7. The method of claim 1, further comprising:

if the candidate store matching segment is less than a minimum match size, setting the candidate store matching segment to a null length data segment.

8. The method of claim 1, wherein determining the input matching data segment further comprises:

determining a portion of the candidate input matching data segment to include in the input matching data segment based on a comparison of at least a portion of the candidate input matching data segment with the candidate store matching data segment.

9. A network device for use in managing a data transfer over a network, comprising:

a transceiver to send and receive the data over the network; and

a computer processor executing a data reduction component that performs actions, including;

receiving input data;

selecting a candidate input matching data segment from within the input data based on using a sliding window over the input data to select a portion of the input data corresponding to a best fitness function value,

wherein each fitness function value is computed from a portion of the input data within the sliding window and the best fitness function value is determined by performing a comparison between each of the plurality of computed fitness function values;

determining a corresponding candidate store matching segment of data in a synchronized store based on an index determined from the selected candidate input matching data segment, the index being used to obtain a file identifier and offset into the synchronized store;

selectively revising at least one boundary of the candidate input matching data segment by comparing data contiguous with the candidate store matching segment with data contiguous with the candidate input matching data segment to generate an input matching data segment of the input data;

determining an encoded representation of the input matching data segment at least partly based on the synchronized store; and

transmitting over the network a data structure that includes at least a portion of an unmatched portion of the data within the input data and the encoded representation.

10. The network device of claim 9, wherein selectively revising at least one boundary further comprises comparing data that is contiguous with and after a left boundary of the candidate store matching segment with data that is contiguous with and after a left boundary of the input matching segment.

11. The network device of claim 9, wherein selectively revising at least one boundary further comprises comparing data that is contiguous with and after a right boundary of the candidate store matching segment with data that is contiguous with and after a right boundary of the input matching segment.

12. The network device of claim 9, wherein determining the corresponding store matching data segment further comprises revising boundaries of the candidate store matching data segment based on the corresponding boundaries of the input matching data segment.

13. The network device of claim 9, wherein selecting the candidate input matching data segment from input data further comprises:

selecting a portion from the plurality of portions of the input data based on the best fitness function value, the selected portion indicating an initial left boundary of the candidate input matching data segment.

14. The network device of claim 9, wherein the unmatched portion of input data is a null length data segment.

15. The network device of claim 9, wherein the synchronized store is updated to include the unmatched portion of data.

16. A system of managing a data transfer over a network, comprising:

a first network device that is configured to perform actions comprising;

receiving input data;

selecting a candidate input matching data segment from within the input data based on using a sliding window over the input data to select a portion of the input data corresponding to a best fitness function value, wherein each fitness function value is computed from a portion of the input data within the sliding window and the best fitness function value is determined by performing a comparison between each of the plurality of computed fitness function values;

determining a corresponding candidate store matching segment of data in a synchronized store based on an index determined from the selected candidate input matching data segment, the index being used to obtain a file identifier and offset that is then used to locate within the synchronized store the candidate store matching segment;

selectively revising at least one boundary of the candidate input matching data segment by comparing data contiguous with the candidate store matching segment with data contiguous with the candidate input matching data segment to generate an input matching data segment of the input data;

determining an encoded representation of the input matching data segment at least partly based on the synchronized store; and

transmitting over the network a data structure that includes at least a portion of an unmatched portion of the data within the input data and the encoded representation; and

a second network device that is configured to perform actions comprising;

receiving the transmitted data structure;

employing the encoded representation in the data structure to extract, from a second synchronized store, data that matches the input matching data segment; and

combining the unmatched portion of the data with the extracted data.

17. The system of claim 16, wherein determining the corresponding store matching data segment further comprises revising boundaries of the candidate store matching data segment based on the corresponding boundaries of the input matching data segment.

18. The system of claim 16, wherein selecting the candidate input matching data segment from input data further comprises:

selecting a portion from the plurality of portions of the input data based on a best fitness function value, the selected portion indicating an initial left boundary of the candidate input matching data segment.

19. The system of claim 16, wherein the unmatched portion of input data is a null length data segment.

20. The system of claim 16, wherein the synchronized store is updated to include the unmatched portion of data.