Opportunistic content delivery using delta coding

• US 10,270,842 B2
• Filed: 08/01/2016
• Issued: 04/23/2019
• Est. Priority Date: 10/25/2011
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Lerner, David
• Primary Examiner(s): Patel, Chirag R
• Assistant Examiner(s): McLeod, Marshall M
• Application Number:
  US15/225,538
• Publication Number:
  US 20170034256A1
• Time in Patent Office: 995 Days
• Field of Search: 709201, 709203, 709217, 709227, 709223
• CPC Class Codes: H03M 7/3091 Data deduplication
• CPC Class Codes: H04B 7/18595 Arrangements for adapting broadband applications to satellite systems
• CPC Class Codes: H04L 1/0011 applied to payload information
• CPC Class Codes: H04L 1/0043 Realisations of complexity reduction techniques, e.g. use of look-up tables
• CPC Class Codes: H04L 1/0052 Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9057 Arrangements for supporting packet reassembly or resequencing
• CPC Class Codes: H04L 65/765 intermediate
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/2885 Hierarchically arranged intermediate devices, e.g. for hierarchical caching
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/5683 Storage of data provided by user terminals, i.e. reverse caching
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

Systems and methods are described for avoiding redundant data transfers using delta coding techniques when reliably and opportunistically communicating data to multiple user systems. According to embodiments, user systems track received block sequences for locally stored content blocks. An intermediate server intercepts content requests between user systems and target hosts, and deterministically chucks and fingerprints content data received in response to those requests. A fingerprint of a received content block is communicated to the requesting user system, and the user system determines based on the fingerprint whether the corresponding content block matches a content block that is already locally stored. If so, the user system returns a set of fingerprints representing a sequence of next content blocks that were previously stored after the matching content block. The intermediate server can then send only those content data blocks that are not already locally stored at the user system according to the returned set of fingerprints.

Claims

1. A method of providing a content object to a client device, the method comprising:

receiving at a proxy server from a content server a content object comprising an N^th data block and M additional data blocks, where M is greater than one;

generating, by the proxy server, a fingerprint of the N^th data block;

sending from the proxy server across a communications network to the client device the fingerprint of the N^th data block;

receiving at the proxy server across the communications network from the client device an indication that the N^th data block is stored at the client device and fingerprints of X additional data blocks also stored at the client device;

utilizing the fingerprints of the X additional data blocks, determining by the proxy server, which of the M additional data blocks of the content object received from the content server are not already stored at the client device; and

sending from the proxy server across the communications network to the client device each of the M additional data blocks determined not to be already stored at the client device.

2. The method of claim 1, wherein the M additional data blocks are sequential data blocks that follow the Nth data block.

3. The method of claim 2, wherein the X additional data blocks stored at the client device follow in sequence the Nth data block in the content object.

4. The method of claim 1, wherein the content object is received from the content server in response to a request from the client device for the content object.

5. The method of claim 1, wherein:

receiving the content object from the content server comprises receiving the content object as a data stream, and

the method further comprises chunking, by the proxy server, the data stream into the N^th data block and the M additional data blocks.

6. The method of claim 1, wherein:

sending the fingerprint of the N^th data block comprises multicasting the fingerprint of the N^th data block to a plurality of client devices that share a same communications channel, and the client device is one of the plurality of client devices.

7. The method of claim 1, further comprising:

after sending the fingerprint of the Nth data block and before receiving the indication that the N^th data block is stored at the client device, starting to send over the communications network the N^th data block followed by the M additional data blocks; and

after receiving the indication that the N^th data block is stored at the client device, stopping the sending of the N^th data block followed by the M additional data blocks.

8. The method of claim 1, wherein:

the client device comprises a user terminal and a client optimizer, and

the client optimizer is disposed between the user terminal and the proxy server.

9. A server-side system comprising:

an object processor configured to receive from a content server a content object comprising an N^th data block and M additional data blocks, where M is greater than one;

a coder configured to generate a fingerprint of the N^th data block; and

a communications subsystem configured to;

send the fingerprint of the N^th data block across a communications network to a client device, and

receive from the client device across the communications network an indication that the N^th data block is stored at the client device and fingerprints of X additional data blocks also stored at the client device; and

a determination block configured to utilize the fingerprints of the X additional data blocks to determine which of the M additional data blocks of the content object received from the content server are not already stored at the client device,

wherein the communications subsystem is further configured to send each of the M additional data blocks determined not to be already stored at the client device across the communications network to the client device.

10. The server-side system of claim 9, wherein the object processor is further configured to:

receive the content object from the content server as a data stream, and

chunk the data stream into the N^th data block and the M additional blocks.

11. A non-transitory medium storing computer-readable instructions, which, when executed, cause a processor to perform steps comprising:

receiving at a proxy server from a content server a content object comprising an N^th data block and M additional data blocks, where M is greater than one;

generating, by the proxy server, a fingerprint of the N^th data block;

sending from the proxy server across a communications network to the client device the fingerprint of the N^th data block;

receiving at the proxy server across the communications network from the client device an indication that the N^th data block is stored at the client device and fingerprints of X additional data blocks also stored at the client device;

utilizing the fingerprints of the X additional data blocks, determining by the proxy server, which of the M additional data blocks of the content object received from the content server are not already stored at the client device; and

sending from the proxy server across the communications network to the client device each of the M additional data blocks determined not to be already stored at the client device.

12. The non-transitory medium of claim 11, wherein the M additional data blocks are sequential data blocks that follow the Nth data block.

13. The non-transitory medium of claim 12, wherein the X additional data blocks stored at the client device follow in sequence the Nth data block in the content object.

14. The non-transitory medium of claim 11, wherein the content object is received from the content server in response to a request from the client device for the content object.

15. The non-transitory medium of claim 11, wherein:

receiving the content object from the content server comprises receiving the content object as a data stream, and

the steps further comprise chunking, by the proxy server, the data stream into the N^th data block and the M additional data blocks.

16. The non-transitory medium of claim 11, wherein:

sending the fingerprint of the N^th data block comprises multicasting the fingerprint of the N^th data block to a plurality of client devices that share a same communications channel, and the client device is one of the plurality of client devices.

17. The non-transitory medium of claim 11, wherein the steps further comprise:

after sending the fingerprint of the N^th data block and before receiving the indication that the N^th data block is stored at the client device, starting to send over the communications network the N^th data block followed by the M additional data blocks; and

after receiving the indication that the N^th data block is stored at the client device, stopping the sending of the N^th data block followed by the M additional data blocks.

18. The non-transitory medium of claim 11, wherein:

the client device comprises a user terminal and a client optimizer, and the client optimizer is disposed between the user terminal and the proxy server.