Methods and systems for utilizing delta coding in acceleration proxy servers

• US 8,671,223 B1
• Filed: 07/25/2011
• Issued: 03/11/2014
• Est. Priority Date: 06/04/2008
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Sebastian, William B., Maniscalco, Michael
• Primary Examiner(s): Lin, Wen-Tai
• Application Number:
  US13/189,854
• Time in Patent Office: 960 Days
• Field of Search: None
• US Class Current: 709/247
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04W 4/18 Information format or content conversion, e.g. adaptation by the network of the transmitted or received information for the purpose of wireless delivery to users or terminals
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

The present invention relates to systems, apparatus, and methods of utilizing delta coding in acceleration proxy servers. The method including storing, at a proxy server, a plurality of dictionary pages within a page storage disk and indexing, at the proxy server, the plurality of dictionary pages with fingerprint identifiers. The fingerprint identifiers are configured to uniquely identify data strings within each of the plurality of dictionary pages. The method further includes receiving, at the proxy server, a data request. The request includes a plurality of fingerprints associated with the requested data.

Claims

1. A method of utilizing delta coding in an acceleration proxy server, the method comprising:

storing, at a proxy server, a fingerprint index for a plurality of data pages, wherein a page indexed in the fingerprint index is associated with a first plurality of fingerprints, wherein each data page of the plurality of data pages is assigned a same page size, wherein each fingerprint of the fingerprint index uniquely identifies a string of data within one of the plurality of data pages, and wherein each fingerprint of the fingerprint index comprises a checksum for a separate string of data within one of the plurality of data pages;

receiving, at the proxy server, a data request, wherein the request includes a second plurality of fingerprints;

searching the fingerprint index for the second plurality of fingerprints;

matching a subset of the first plurality of fingerprints with a subset of the second plurality of fingerprints; and

identifying the page indexed in the fingerprint index for response to the data request based on the matching the subset of the first plurality of fingerprints with the subset of the second plurality of fingerprints.

2. The method of claim 1 further comprising:

encoding the response to the data request using the page indexed in the fingerprint index when a number of matching fingerprints from the subset of the first plurality of fingerprints and the subset of the second plurality of fingerprints exceeds a threshold match value.

3. The method of claim 2 wherein the first plurality of fingerprints associated with the page indexed in the fingerprint index comprises 200 fingerprints and wherein the threshold match value is 10 fingerprints.

4. The method of claim 1 wherein each fingerprint of the first plurality of fingerprints comprises a checksum for a different string of data within the page indexed in the fingerprint index.

5. A non-transitory machine-readable storage medium having sets of instructions stored thereon which, when executed by a machine, cause the machine to:

store, at the machine, a plurality of dictionary pages within a page storage disk, wherein each dictionary page of the plurality of dictionary pages is assigned a same page size;

index, at the machine, the plurality of dictionary pages with fingerprint identifiers;

identify a first set of fingerprints associated with a first data set;

search, at the machine, the indexed fingerprint identifiers for matches with the plurality of fingerprints associated with the first data set;

identify one of the plurality of dictionary pages with the greatest number of matching fingerprints from the plurality of fingerprints associated with the requested data, wherein the number of matching fingerprints is less than the number of fingerprints in the first set of fingerprints;

analyze a first file to determine a protocol associated with the first data set prior to storing the first file in the plurality of dictionary pages;

in response to identifying the protocol associated with the first file, parse out a protocol header data from the first file prior to storing the first file in the plurality of dictionary pages;

determine that the first file is above a file size threshold; and

in response to the first file being above a file size threshold, utilize an aligned mode for storing the first file within the dictionary pages, wherein the aligned mode includes storing the first file such that the first file as stored within the plurality of dictionary pages terminates at memory page boundaries.

6. A non-transitory machine-readable storage medium having sets of instructions stored thereon which, when executed by a machine, cause the machine to:

store, at the machine, a plurality of dictionary pages within a page storage disk, wherein each dictionary page of the plurality of dictionary pages is assigned a same page size;

index, at the machine, the plurality of dictionary pages with fingerprint identifiers;

identify a first set of fingerprints associated with a first data set;

search, at the machine, the indexed fingerprint identifiers for matches with the plurality of fingerprints associated with the first data set; and

identify one of the plurality of dictionary pages with the greatest number of matching fingerprints from the plurality of fingerprints associated with the requested data, wherein the number of matching fingerprints is less than the number of fingerprints in the first set of fingerprints;

wherein the sets of instructions which, when further executed by the machine, cause the machine to;

analyze the first file to determine that a protocol associated with the first data set cannot be identified prior to storing the first file within the plurality of dictionary pages; and

in response to determining that the protocol associated with the first file cannot be identified, utilize an unaligned mode for storing the first file within the dictionary pages.