Opportunistic content delivery using delta coding

• US 9,407,355 B1
• Filed: 10/23/2012
• Issued: 08/02/2016
• Est. Priority Date: 10/25/2011
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Lerner, David
• Primary Examiner(s): Avellino, Joseph E
• Assistant Examiner(s): McLeod, Marshall
• Application Number:
  US13/657,932
• Time in Patent Office: 1,379 Days
• Field of Search: 709/201, 709/203, 709/217, 709/218, 709/219
• US Class Current: 1/1
• 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 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 of subsequent content blocks; and

a communications subsystem, in communication with the object processing subsystem, and operable to;

communicate a first fingerprint corresponding to the first content block from the server optimizer to a client optimizer;

receive 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;

determine, 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

communicate a subset of the set of subsequent content blocks from the server optimizer 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.

18. The server-side system of claim 17, wherein the communications subsystem is operable to communicate the first fingerprint by 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.

19. The server-side system of claim 17, wherein:

the response package further comprises an indication of packet loss or error loss corresponding to the matching content block; and

the communications subsystem is operable to communicate 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.

20. The server-side system of claim 17, wherein communications subsystem is operable to communicate the subset of the set of subsequent content blocks by 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.

21. A system for opportunistically handling content data delivery from a server optimizer to a plurality of client optimizers over a communications network, the system comprising:

a server optimizer operable to;

select a first set of client optimizers of the plurality of client optimizers for reliable delivery of content data, the plurality of client optimizers in communication with the server optimizer over a shared communications link in such a way that, when the content data is reliably received by the first set of client optimizers over the shared communications link, others of the plurality of client optimizers opportunistically receive the content data over the shared communications link;

multicast a set of fingerprints corresponding to the content data over the shared communications link;

receive a response package at the server optimizer from each of the first set of client optimizers, each response package comprising a respective sequence of client fingerprints that indicates any portions of the content data presently stored local to the respective client optimizer, wherein the response package is generated by the respective client optimizer in response to 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 a first locally stored content block at the respective client optimizer matches at least one of the received set of fingerprints, the first locally stored content block having been received and stored by the respective client optimizer prior to receiving the first server fingerprint from the server optimizer, the first locally stored content block being associated with the respective sequence of client fingerprints representing a set of next content blocks that were received and stored by the respective client optimizer directly after receipt of the first locally stored content block in sequence;

determine a missing portion of the content data according to the portions of the content data not presently stored local to the first set of client optimizers as indicated by their respective response packages; and

multicast the missing portion of the content data over the shared communications link according to the determination.

22. The system of claim 21, further comprising:

a plurality of client optimizers, each in communication with the server optimizer over the shared communications link, each operable to;

receive a fingerprint from the server optimizer corresponding to a portion of content data;

determine whether the corresponding portion of the content data matches locally stored content data according to the fingerprint;

generate the response package indicating any portions of the content data presently stored local to the client optimizer when the corresponding portion of the content data matches locally stored content data according to the fingerprint; and

store the corresponding portion of the content data when subsequently received by the client optimizer when the corresponding portion of the content data does not match locally stored content data according to the fingerprint.

23. The method of claim 21, wherein the server optimizer is further operable to:

determine a transport scheme that is reliable with respect to the first set of client optimizers,

wherein the set of fingerprints and the missing portion of the content data are multicast over the shared communications link according to the transport scheme.

24. A method for handling content communications between a server optimizer and a plurality of client optimizers over a communications network, the method comprising:

receiving, by a client optimizer from the server optimizer, a first server fingerprint corresponding to a first content block, the first content block being one of a plurality of content blocks generated by the server optimizer from content data;

determining, by the client optimizer, whether a first locally stored content block matches the first content block by comparing the first server fingerprint to a client fingerprint of the first locally stored content block, 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 a 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;

when the locally stored content block matches the first content block;

generating a response package by the client optimizer, the response package comprising the sequence of client fingerprints; and

communicating the response package from the client optimizer to the server optimizer in response to receiving the first server fingerprint;

receiving, in response to a request for the content data and in response to communicating the response package, either a second content block from the server optimizer or an indication that a second locally stored content block matches a second content block comprising a portion of the content data requested by the client optimizer from the content source; and

using content data of either the second content block or the second locally stored content block in fulfillment of a corresponding portion of the request for the content data.

25. The method of claim 24, further comprising:

when there is not a first locally stored content block that matches the first content block;

receiving and storing the first content block and a plurality of subsequent content blocks locally to the client optimizer;

storing, locally to the client optimizer, a client fingerprint corresponding to each of the first content block and the plurality of subsequent content blocks; and

tracking a received order of the first content block and the plurality of subsequent content blocks.

26. The method of claim 24, wherein the first content block and the plurality of subsequent content blocks are received opportunistically by the client optimizer.

27. The method of claim 24, wherein the response package is communicated from the client optimizer to the server optimizer at a response rate determined according to a link rate at which the client optimizer is consuming content blocks received from the server optimizer.

28. The method of claim 24, wherein the response package is communicated from the client optimizer to the server optimizer at a response rate determined according to an encoding rate at which an end user is consuming the content data.

29. A client-side system for receiving content data from content servers over a communications network via a server optimizer, the client-side system comprising:

an object processing subsystem operable to;

determine whether a first locally stored content block matches a first content block by comparing a first server fingerprint to a client fingerprint of the first locally stored content block, the first server fingerprint corresponding to a first content block being one of a plurality of content blocks generated by the server optimizer from content data, 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, and the first locally stored content block being associated with a 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; and

generate a response package by the client optimizer when the locally stored content block matches the first content block, the response package comprising the sequence of client fingerprints; and

a communications subsystem, in communication with the object processing subsystem, and operable to;

communicate the response package from the client optimizer to the server optimizer in response to receiving the first server fingerprint;

receive, in response to a request for the content data and in response to communicating the response package, either a second content block from the server optimizer or an indication that a second locally stored content block matches a second content block comprising a portion of the content data requested by the client optimizer from the content source; and

use content data of either the second content block or the second locally stored content block in fulfillment of a corresponding portion of the request for the content data.

30. The client-side system of claim 29, further comprising:

a client dictionary,

wherein the object processing subsystem is further operable, when there is not a first locally stored content block that matches the first content block, to;

receive the first content block and a plurality of subsequent content blocks;

generate a client fingerprint corresponding to each of the first content block and the plurality of subsequent content blocks;

store the client fingerprints in the client dictionary; and

track a received order of the first content block and the plurality of subsequent content blocks.