Deltacasting

• US 10,547,655 B2
• Filed: 05/06/2016
• Issued: 01/28/2020
• Est. Priority Date: 01/13/2009
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Sebastian, William B., Lepeska, Peter
• Primary Examiner(s): Asres, Hermon
• Assistant Examiner(s): Garcia-Ching, Karina J
• Application Number:
  US15/148,897
• Publication Number:
  US 20160330259A1
• Time in Patent Office: 1,362 Days
• Field of Search: 709234
• CPC Class Codes: H04B 7/185 Space-based or airborne stations; Stations for satellite systemsH04B7/204 takes precedence
• CPC Class Codes: H04L 12/1859 adapted to provide push services, e.g. data channels
• CPC Class Codes: H04L 12/1863 comprising mechanisms for improved reliability, e.g. status reports arrangements for detecting or preventing errors by carrying supervisory signal the return channel H04L1/16
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 65/60 Network streaming of media packets
• CPC Class Codes: H04L 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06
• CPC Class Codes: H04L 67/01 Protocols
• 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 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Methods, apparatuses, and systems for improving utilization of a communications system (e.g., a satellite communications system) are provided, using techniques referred to herein as “deltacasting.” Embodiments operate in a client-server context, in which the server-side of the communication link intercepts requests and responses using a client-server optimizer (e.g., a transparent proxy or in-line optimizer between a client web browser and an Internet content provider). The optimizer uses techniques, such as dictionary coding techniques, to create fingerprints of content traversing the links of the communications system. These fingerprints are used to identify and exploit multicasting and/or other opportunities for increased utilization of the communications links.

Claims

1. A multicasting method comprising:

receiving at a server-side optimizer from a content server a data block of content requested by a first client device of a plurality of client devices connected to the content server by a common communications link, the common communications link comprising one of a plurality of spot beams of a satellite;

applying a multicast filtering criterion to the received data block to determine whether the received data block is a candidate for multicasting, wherein the multicast filtering criterion is a size threshold, and the applying the multicast filtering criterion comprises;

determining that the received data block is a candidate for multicasting if the received data block is greater than the size threshold, and

determining that the received data block is not a candidate for multicasting if the received data block is less than the size threshold;

only if the data block is determined to be a candidate for multicasting, generating at the server-side optimizer a compressed version of the received data block according to a model of a first client dictionary of the first client device such that the data block is not directly accessible by a client from a client dictionary; and

only if the data block is determined to be a candidate for multicasting, determining at the server-side optimizer whether the compressed version of the received data block matches a compressed version of a data block previously received at the server-side optimizer; and

if the determining operation determines that the compressed version of the received data block does not match a compressed version of a data block previously received at the server-side optimizer, multicasting the compressed version of the received data block from the server-side optimizer over the common communications link to the first client device for storage in the first client dictionary and a second client device of the plurality of client devices for storage in a second client dictionary of the second client device, the multicasting comprising multicasting the compressed version of the received data block to the first client device and the second client device on the one of the spot beams and multicasting control data comprising a dictionary reference for the first client dictionary to allow the first client dictionary to recreate the data block for access by the first client device.

2. The method of claim 1 further comprising, if the determining determines that the compressed version of the received data block matches a compressed version of a data block previously received at the server-side optimizer, transmitting the compressed version of the received data block but not the received data block from the server-side optimizer over the common communications link to the first client device.

3. The method of claim 2, wherein compressed versions of data blocks previously received at the server-side optimizer identify data blocks stored in a cache local to the first client device.

4. The method of claim 1, wherein the multicasting further comprises multicasting the compressed version of the received data block over the common communications link to the first client device and the second client device.

5. The method of claim 1, wherein the compressed version of the received data block comprises a fingerprint of the received data block.

6. The method of claim 1, wherein the generating comprises applying a hashing function to the received data block.

7. The method of claim 1, wherein the compressed version of the received data block comprises a check sum of the received data block.

8. The method of claim 1, wherein:

the receiving comprises receiving the data block with a header containing metadata associated with the data block,

the method further comprises stripping the header from the received data block, and

the generating comprises generating the compressed version of the received data block after the stripping.

9. The method of claim 1, wherein:

the receiving comprises receiving the data block with a header containing metadata associated with the data block,

the method further comprises applying a multicast filtering criterion to the metadata to determine whether the received data block is a candidate for multicasting, and

performing the generating and the determining with respect to the received data block only if the data block is determined to be a candidate for multicasting.

10. A machine readable medium in which are stored non-transitory instructions for causing the machine to perform a method comprising:

receiving at a server-side optimizer from a content server a data block of content requested by a first client device of a plurality of client devices connected to the content server by a common communications link, the common communications link comprising one of a plurality of spot beams of a satellite;

applying a multicast filtering criterion to the received data block to determine whether the received data block is a candidate for multicasting, wherein the multicast filtering criterion is a size threshold, and the applying the multicast filtering criterion comprises;

determining that the received data block is a candidate for multicasting if the received data block is greater than the size threshold, and

determining that the received data block is not a candidate for multicasting if the received data block is less than the size threshold;

only if the data block is determined to be a candidate for multicasting, generating at the server-side optimizer a compressed version of the received data block according to a model of a first client dictionary of the first client device such that the data block is not directly accessible by a client device from a client dictionary;

only if the data block is determined to be a candidate for multicasting, determining at the server-side optimizer whether the compressed version of the received data block matches a compressed version of a data block previously received at the server-side optimizer; and

if the determining operation determines that the compressed version of the received data block does not match a compressed version of a data block previously received at the server-side optimizer, multicasting the compressed version of the received data block from the server-side optimizer over the common communications link to the first client device for storage in the first client dictionary and a second client device of the plurality of client devices for storage in a second client dictionary of the second client device, the multicasting comprising multicasting the compressed version of the received data block to the first client device and the second client device on the one of the spot beams and multicasting control data comprising a dictionary reference for the first client dictionary to allow the first client dictionary to recreate the data block for access by the first client device.

11. The machine readable medium of claim 10 further comprising, if the determining determines that the compressed version of the received data block matches a compressed version of a data block previously received at the server-side optimizer, transmitting the compressed version of the received data block but not the received data block from the server-side optimizer over the common communications link to the first client device.

12. The machine readable medium of claim 11, wherein compressed versions of data blocks previously received at the server-side optimizer identify data blocks stored in a cache local to the first client device.

13. The machine readable medium of claim 10, wherein the multicasting further comprises multicasting the compressed version of the received data block over the common communications link to the first client device and the second client device.

14. The machine readable medium of claim 10, wherein the compressed version of the received data block comprises a fingerprint of the received data block.

15. The machine readable medium of claim 10, wherein the generating comprises applying a hashing function to the received data block.

16. The machine readable medium of claim 10, wherein the compressed version of the received data block comprises a check sum of the received data block.

17. The machine readable medium of claim 10, wherein:

the receiving comprises receiving the data block with a header containing metadata associated with the data block,

the method further comprises stripping the header from the received data block, and

the generating comprises generating the compressed version of the received data block after the stripping.

18. The machine readable medium of claim 10, wherein:

the receiving comprises receiving the data block with a header containing metadata associated with the data block,

the method further comprises applying a multicast filtering criterion to the metadata to determine whether the received data block is a candidate for multicasting, and

performing the generating and the determining with respect to the received data block only if the data block is determined to be a candidate for multicasting.

19. A multicasting system comprising:

a server-side processor in communication with a server-side cache configured to store compressed versions of data blocks previously received by the server-side processor,

wherein the server-side processor is configured to determine whether a compressed version of a data block of content newly received from a content server matches one of the compressed versions of the data blocks in the server-side cache and apply a multicast filtering criterion to the received data block to determine whether the received data block is a candidate for multicasting, wherein the multicast filtering criterion is a size threshold, and the server-side processor determines that the received data block is a candidate for multicasting if the received data block is greater than the size threshold and determines that the received data block is not a candidate for multicasting if the received data block is less than the size threshold; and

a multicast processor configured to multicast the compressed version of the received data block over a common communications link comprising one of a plurality of spot beams of a satellite to a first client device that requested the content and a second device that did not request the content upon the server-side processor determining that the compressed version of the newly received data block does not match one of the compressed versions of the data blocks in the server-side cache and the data block is a candidate for multicasting;

wherein the compressed version of the received data block is generated according to a model of a first client dictionary of the first client device such that the data block is not directly accessible by a client from a client dictionary, and the multicast processor multicasts control data comprising a dictionary reference for the first client dictionary to allow the first client dictionary to recreate the data block for access by the first client device.

20. The system of claim 19 further comprising a unicast processor configured to transmit the compressed version of the newly received data block but not the newly received data block over the common communications link to the first client device upon the server-side processor determining that the compressed version of the newly received data block matches one of the compressed versions of the data blocks in the server-side cache.

21. The system of claim 19, wherein the compressed version of the data blocks previously received by the server-side processor are part of a model of data blocks stored in a cache local to the first client device.

22. The system of claim 19, wherein the compressed version of the received data block comprises a fingerprint of the received data block.

23. The system of claim 19, wherein the compressed version of the received data block comprises a version of the received data block subjected to a hashing function.

24. The system of claim 19, wherein the compressed version of the received data block comprises a check sum of the received data block.