Opportunistic content delivery using delta coding

Patent metadata

Field	Value
Publication number	US-9407355-B1
Application number	US-201213657932-A
Country	US
Kind code	B1
Filing date	Oct 23, 2012
Priority date	Oct 25, 2011
Publication date	Aug 2, 2016
Grant date	Aug 2, 2016

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.

First claim

What is claimed is:

1. A method for communicating content data from a server optimizer to client optimizers over a communications network, the method comprising: determining, by the server optimizer, to communicate content data to a client optimizer; chunking the content data into a first content block and a set of subsequent content blocks; computing server fingerprints of each of the first content block and the set of subsequent content blocks; communicating a first fingerprint corresponding to the first content block from the server optimizer to the client optimizer; receiving a response package at the server optimizer from the client optimizer, the response package comprising a sequence of client fingerprints, wherein the response package is generated by the client optimizer only when the client optimizer determines that it is one of the first set of client optimizers in relation to the content data and in response to determining that a client fingerprint of the first locally stored content block matches the received first fingerprint, the first locally stored content block having been received and stored by the client optimizer prior to receiving the first server fingerprint from the server optimizer, the first locally stored content block being associated with the sequence of client fingerprints representing a set of next content blocks that were received and stored by the client optimizer directly after receipt of the first locally stored content block in sequence; determining, for each of the set of subsequent content blocks, whether the corresponding server fingerprint indicates equivalence to one of the locally stored content blocks according to its respective client fingerprint received as part of the response package; and communicating a subset of the set of subsequent content blocks from the server optimizer to the client optimizer according to the determination by the server optimizer to communicate the content data to the client optimizer, such that the corresponding server fingerprint of each communicated subsequent content block indicates no equivalence to one of the locally stored content blocks according to its respective client fingerprint.

2. The method of claim 1 , further comprising:
for each of a second subset of the set of subsequent content blocks for each of which its corresponding server fingerprint indicates equivalence to one of the locally stored content blocks according to its respective client fingerprint, communicating a message from the server optimizer to the client optimizer indicating that there is an equivalent locally stored content blocks.

3. The method of claim 1 , wherein the set of client fingerprints are associated with locally stored content blocks that were received and stored by the client optimizer sequentially after prior receipt of the matching content block.

4. The method of claim 1 , wherein communicating the first fingerprint corresponding to the first content block from the server optimizer to the client optimizer comprises multicasting the first fingerprint from the server optimizer to a set of user terminals, one of the user terminals being associated with the client optimizer.

5. The method of claim 1 , wherein determining, by the server optimizer, to communicate content data to the client optimizer comprises:
intercepting, by the server optimizer, a request communicated by the client optimizer for content from a content server;
determining to communicate the content data to the client optimizer when the content data is received at the server optimizer from the content server in response to the request.

6. The method of claim 1 , wherein determining, by the server optimizer, to communicate content data to the client optimizer comprises:
receiving the content data at the server optimizer from a content source separate from the server optimizer along with an indication to deliver the content data to the client optimizer; and
determining to communicate the content data to the client optimizer according to the indication.

7. The method of claim 1 , wherein determining, by the server optimizer, to communicate content data to the client optimizer comprises:
receiving the content data at the server optimizer; and
determining to communicate the content data to the client optimizer according to at least one of a client preference previously stored in association with the client optimizer; a client subscription stored in association with the client optimizer; a request history stored in association with the client optimizer; a client demographic stored in association with the client optimizer; or a popularity associated with the content data.

8. The method of claim 1 , further comprising:
multicasting the first content block to the client optimizer and to at least one non-requesting user system.

9. The method of claim 1 , wherein:
the response package further comprises a list of missing packets corresponding to the matching content block; and
communicating the subset of the set of subsequent content blocks from the server optimizer to the client optimizer comprises communicating content blocks from the server optimizer corresponding to the list of missing packets.

10. The method of claim 1 , wherein:
the response package further comprises an indication of an amount of error loss incurred in relation to at least one of the locally stored content blocks; and
communicating the subset of the set of subsequent content blocks from the server optimizer to the client optimizer comprises communicating at least one of packets or error correction codes according to the indication.

11. The method of claim 1 , further comprising:
determining whether the content is streaming media content, and, only when the content is streaming media content, performing the step of determining whether the corresponding server fingerprint indicates equivalence, and performing the step of communicating the subset of the set of subsequent content blocks.

12. The method of claim 1 , wherein communicating the subset of the set of subsequent content blocks comprises multicasting the subset of the set of subsequent content blocks reliably to the client optimizer and opportunistically to at least one non-requesting user system.

13. The method of claim 1 , wherein communicating the subset of the set of subsequent content blocks comprises communicating the subset of the set of subsequent content blocks according to a transport scheme that is reliable with respect to a communications link between the client optimizer and the server optimizer.

14. The method of claim 1 , wherein communicating the subset of the set of subsequent content blocks comprises compressing the subset of the set of the number of subsequent content blocks into compressed content blocks, and communicating the compressed content blocks to the client optimizer.

15. The method of claim 1 , wherein chunking the content data comprises deterministically chunking the content data into content blocks.

16. The method of claim 1 , wherein computing fingerprints of the content blocks comprises computing checksums of the content blocks.

17. A server-side system, disposed in a communications network between client optimizers and content servers, for handling communication of content data from the content servers to the client optimizers over the communications network, the server-side system comprising: an object processing subsystem operable to: chunk content data into a first content block and a set of subsequent content blocks; and compute server fingerprints of each of the first content block and the set

Assignees

• Viasat Inc

Inventors

• Lerner David

Classifications

• H03M7/3091

  Data deduplication · CPC title

• H04L67/06

  specially adapted for file transfer, e.g. file transfer protocol [FTP] · CPC title

• H04L12/18

  for broadcast or conference {, e.g. multicast} · CPC title

• H04L1/0052

  Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables · CPC title

• H04L12/1881

  with schedule organisation, e.g. priority, sequence management · CPC title