Correlative anticipatory deltacasting

• US 9,363,308 B2
• Filed: 08/06/2014
• Issued: 06/07/2016
• 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): Ghowrwal, Omar
• Assistant Examiner(s): BROCKMAN, ANGEL T
• Application Number:
  US14/453,479
• Publication Number:
  US 20150032848A1
• Time in Patent Office: 671 Days
• Field of Search: None
• US Class Current: 1/1
• 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 through techniques referred to herein as “deltacasting.” Some embodiments use a server-side optimizer to intercept and create fingerprints of byte-level content data traversing links of the communications system. The content fingerprints are used to transparently identify communications patterns (e.g., repetitious downloads of the same content, correlations between users, etc.), which may then be used in exploiting multicasting and/or other opportunities for increased utilization of the communication links.

Claims

1. A method for multicasting over a communications system having a server side and a plurality of clients in communication over a shared communications infrastructure, the method comprising:

intercepting a data block at the server side, the data block being communicated from a content source in response to a content request from a requesting client of the communications system;

first determining, by the server side, whether a previously seen data model indicates that at least one instance of the data block was previously intercepted by the server side, the previously seen data model comprising indications of data blocks previously intercepted in relation to previous content requests;

second determining, by the server side, whether a trigger event has occurred with respect to the data block when the previously seen data model indicates that the at least one instance of the data block was previously intercepted according to the first determining; and

multicasting the data block to the requesting client and a set of non-requesting clients over the shared communications infrastructure when the trigger event has occurred according to the second determination.

2. The method of claim 1, further comprising:

generating a user correlation model by calculating correlations between traffic associated with each client and traffic associated with others of the plurality of clients; and

selecting the set of non-requesting clients according to the user correlation model, such that the selected non-requesting clients each correlate with the requesting client and share forward-link resources of the shared communications infrastructure with the requesting client.

3. The method of claim 2, wherein the trigger event is determined to have occurred with respect to the data block when the previously seen data model indicates that the at least one instance of the data block was previously intercepted according to the first determining and/or when the user correlation model indicates that a correlation between the requesting client and at least one of the non-requesting clients is above a threshold level.

4. The method of claim 2, wherein the user correlation model maintains information relating to timing associated with the traffic used to calculate the correlations.

5. The method of claim 1, further comprising:

third determining whether the data block is presently stored in a local storage of the requesting client; and

unicasting a compressed instance of the data block to the requesting client in place of communicating the data block when the data block is presently stored in the local storage according to the third determining,

wherein the first determining, the second determining, and the multicasting are performed only when the data block is not presently stored in the local storage according to the third determining.

6. The method of claim 5, further comprising:

receiving verification from the requesting client that the data block was successfully received by the requesting client after the multicasting; and

updating a client dictionary model to include a representation of the data block in accordance with the receiving,

wherein the third determining is according to the client dictionary model.

7. The method of claim 1, further comprising:

generating a fingerprint using byte-level information comprised by a content portion of the data block,

wherein the first determining is according to the fingerprint.

8. The method of claim 1, wherein the trigger event is determined to have occurred with respect to the data block when the previously seen data model indicates that the at least one instance of the data block was previously intercepted more than a threshold number of times.

9. The method of claim 8, wherein the threshold number of times is one time.

10. The method of claim 1, further comprising:

maintaining a popularity metric indicating popularity of the data block by tracking changes in a number of times the data block is intercepted over a period of time,

wherein the trigger event is determined to have occurred with respect to the data block when the popularity metric crosses a threshold value.

11. The method of claim 1, wherein the trigger event is determined to have occurred with respect to the data block when the popularity metric crosses a threshold value in association with traffic of identified clients, and further comprising:

selecting the set of non-requesting clients according to the identified clients.

12. The method of claim 1, further comprising:

monitoring a link condition associated with communicating from the server system to at least the requesting client;

determining a modcode according to the link condition; and

selecting the set of non-requesting clients according to the determined modcode.

13. A server system for communicating with a plurality of clients in a communications system over a shared communications infrastructure, the system comprising:

an optimizer module that;

intercepts a data block being communicated from a content source in response to a content request from a requesting client of the communications system;

first determines whether a previously seen data model indicates that at least one instance of the data block was previously intercepted by the server side, the previously seen data model comprising indications of data blocks previously intercepted in relation to previous content requests; and

second determines whether a trigger event has occurred with respect to the data block when the previously seen data model indicates that the at least one instance of the data block was previously intercepted according to the first determining; and

a multicaster module that is communicatively coupled with the optimizer module and multicasts the data block to the requesting client and a set of non-requesting clients over the shared communications infrastructure when the trigger event has occurred according to the second determination.

14. The system of claim 13, wherein the optimizer module further:

generates a user correlation model by calculating correlations between traffic associated with each client and traffic associated with others of the plurality of clients; and

selects the set of non-requesting clients according to the user correlation model, such that the selected non-requesting clients each correlate with the requesting client and share forward-link resources of the shared communications infrastructure with the requesting client.

15. The system of claim 14, wherein the trigger event is determined to have occurred with respect to the data block when the previously seen data model indicates that the at least one instance of the data block was previously intercepted according to the first determining and/or when the user correlation model indicates that a correlation between the requesting client and at least one of the non-requesting clients is above a threshold level.

16. The system of claim 13, wherein the optimizer module further:

third determines whether the data block is presently stored in a local storage of the requesting client; and

unicasts a compressed instance of the data block to the requesting client in place of communicating the data block when the data block is presently stored in the local storage according to the third determining,

such that the optimizer module operates to first determine and second determine only when the data block is not presently stored in the local storage.

17. The system of claim 13, wherein the optimizer module further:

generates a fingerprint using byte-level information comprised by a content portion of the data block, such that the optimizer module operates to first determine according to the fingerprint.

18. The system of claim 13, wherein the trigger event is determined to have occurred with respect to the data block when the previously seen data model indicates that the at least one instance of the data block was previously intercepted more than a threshold number of times.

19. The system of claim 13, wherein the optimizer module further:

maintains a popularity metric indicating popularity of the data block by tracking changes in a number of times the data block is intercepted over a period of time,

wherein the trigger event is determined to have occurred with respect to the data block when the popularity metric crosses a threshold value.