Methods and systems for utilizing delta coding in acceleration proxy servers

• US 8,010,705 B1
• Filed: 06/03/2009
• Issued: 08/30/2011
• Est. Priority Date: 06/04/2008
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Maniscalco, Michael, Sebastian, William B.
• Primary Examiner(s): LIN, WEN TAI
• Application Number:
  US12/477,814
• Time in Patent Office: 818 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 acceleration proxy servers, the method comprising the following computer implemented steps:

storing, at a proxy server, a plurality of dictionary pages within a page storage disk;

indexing, at the proxy server, the plurality of dictionary pages with fingerprint identifiers, wherein the fingerprint identifiers are configured to uniquely identify data strings within each of the plurality of dictionary pages;

receiving, at the proxy server, a data request, wherein the request includes a plurality of fingerprints associated with the requested data;

searching, at the proxy server, the indexed fingerprint identifiers for matches with the plurality of fingerprints associated with the requested data;

identifying, at the proxy server, one of the plurality of pages with the greatest number of matching fingerprints from the plurality of fingerprints associated with the requested data;

removing, at the proxy server, the fingerprints associated with the one of the plurality of pages from the searching of the indexed fingerprints;

searching, at the proxy server, the indexed fingerprint identifiers for matches with the remaining plurality of fingerprints associated with the requested data; and

loading, at a client through a proxy client, the identified pages into memory; and

encoding the requested data using the loaded pages.

2. A method of utilizing delta coding in acceleration proxy servers as in claim 1, further comprising determining that the number of matching fingerprints within the one of the plurality of pages with the greatest number of matching fingerprints from the plurality of fingerprints associated with the requested data is below a minimum threshold value.

3. A method of utilizing delta coding in acceleration proxy servers as in claim 2, further comprising, in response to the number of matching fingerprints being below the threshold value, encoding the data using a previously loaded page.

4. A method of utilizing delta coding in acceleration proxy servers as in claim 1, wherein the storing of the plurality of dictionary pages are stored in a circular buffer.

5. A method of utilizing delta coding in acceleration proxy servers as in claim 4, further comprising sorting the pages stored in the circular buffer by the length of time in which the pages have been stored in the buffer.

6. A method of utilizing delta coding in acceleration proxy servers as in claim 5, further comprising:

receiving an access request for a dictionary page stored in the buffer; and

retrieving the dictionary page from the buffer; and

determining that the retrieved page has been stored in the buffer below a threshold.

7. A method of utilizing delta coding in acceleration proxy servers as in claim 6, further comprising:

in response to the retrieved page being stored in the buffer below the threshold, placing a copy of the page in the front of the buffer; and

loading the page into memory to responds to the access request.

8. A system for utilizing delta coding in acceleration proxy servers, the system comprising:

a proxy server having a first processor and a storage medium which has sets of instructions stored thereon, which when executed by the processor, cause the first processor to execute the following computer implemented steps;

store a plurality of dictionary pages within a page storage disk, index the plurality of dictionary pages with fingerprint identifiers, wherein the fingerprint identifiers are configured to uniquely identify data strings within each of the plurality of dictionary pages,

receive a data request, wherein the request includes a plurality of fingerprints associated with the requested data,

search the indexed fingerprint identifiers for matches with the plurality of fingerprints associated with the requested data, identify one of the plurality of pages with the greatest number of matching fingerprints from the plurality of fingerprints associated with the requested data,

remove the fingerprints associated with the one of the plurality of pages from the searching of the indexed fingerprints, and

search the indexed fingerprint identifiers for matches with the remaining plurality of fingerprints associated with the requested data; and

a client including a proxy client in communication with the proxy server, the proxy client having a second processor and a storage medium which has sets of instructions stored thereon, which when executed by the second processor, cause the client to execute the following computer implemented steps;

load the identified pages into memory, and

render the loaded page.

9. A system for utilizing delta coding in acceleration proxy servers as in claim 8, wherein the proxy server is in communication with the client via a satellite link.

10. A system for utilizing delta coding in acceleration proxy servers as in claim 8, further comprising a content server.

11. A system for utilizing delta coding in acceleration proxy servers as in claim 10, wherein the content server is configured to provide the data to the proxy server in response to the data request.

12. A system for utilizing delta coding in acceleration proxy servers as in claim 11, wherein the content server is one or more of the following:

a file server, a mail server, a web server, and a FTP server.

13. A system for utilizing delta coding in acceleration proxy servers as in claim 12, further comprising a plurality of content servers in communication with the proxy server, wherein the content server is one of the plurality of content servers.

14. A system for utilizing delta coding in acceleration proxy servers as in claim 8, wherein the proxy server is an acceleration server.

15. A system for utilizing delta coding in acceleration proxy servers as in claim 8, further comprising a plurality of clients in communication with the proxy server, wherein the client is one of the plurality of clients.

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

store a plurality of dictionary pages within a page storage disk;

index the plurality of dictionary pages with fingerprint identifiers, wherein the fingerprint identifiers are configured to uniquely identify data strings within each of the plurality of dictionary pages;

receive a data request, wherein the request includes a plurality of fingerprints associated with the requested data;

search the indexed fingerprint identifiers for matches with the plurality of fingerprints associated with the requested data;

identify one of the plurality of pages with the greatest number of matching fingerprints from the plurality of fingerprints associated with the requested data;

remove the fingerprints associated with the one of the plurality of pages from the searching of the indexed fingerprints;

search the indexed fingerprint identifiers for matches with the remaining plurality of fingerprints associated with the requested data;

load the identified pages into memory; and

encoding the requested data using the loaded pages.

17. A non-transitory machine-readable medium as in claim 16, wherein the sets of instructions which, when further executed by the machine, cause the machine to:

analyze the data request to determine if a protocol associated with the data request can be identified.

18. A non-transitory machine-readable medium as in claim 17, wherein the sets of instructions which, when further executed by the machine, cause the machine to:

in response to identifying the protocol associated with the data request, parse out the protocol'"'"'s header data from the file data.

19. A non-transitory machine-readable medium as in claim 18, wherein the sets of instructions which, when further executed by the machine, cause the machine to:

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

in response to the file data being above a file size threshold, utilize an aligned mode for storing the file data within the dictionary pages.

20. A non-transitory machine-readable medium as in claim 19, wherein the aligned mode includes storing the file data such that files within the file data terminate at memory page boundaries.