Content set based pre-positioning

• US 8,489,673 B2
• Filed: 01/12/2010
• Issued: 07/16/2013
• 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): Ashraf, Waseem
• Application Number:
  US12/685,920
• Publication Number:
  US 20100179987A1
• Time in Patent Office: 1,281 Days
• Field of Search: 709/203, 709/223, 709/224
• US Class Current: 709/203
• 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 are provided for improving utilization of the communications system through various “deltacasting” techniques for handling content sets (e.g., feeds or websites). In some embodiments, within a client-server context, content sets are anticipatorily pre-positioned in client dictionaries using multicasting techniques to share forward link capacity. Pre-positioning determinations are made according to byte-level data, set-level metadata, and/or user preferences. In some embodiments, when locally stored information from the content sets is requested by a user, deltacasting techniques are used to generate fingerprints for use in identifying and exploiting multicasting and/or other opportunities for increased utilization of links of the communications system.

Claims

1. A method for pre-positioning content over a communications system having a communications path between a server side of the communications system and a plurality of clients, the communications path comprising a shared forward link over which bandwidth resources are shared during a multicast communication, the method comprising:

intercepting a data block at the server side of the communications system, the data block comprising a header portion and a content portion and being communicated as part of a content set over the communications path, the content set comprising a plurality of content objects and being identified by a content set identifier, the content set identifier being associated with a set-level profile characterizing the content set;

associating the data block with the content set identifier;

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

generating an anticipatory content value (ACV) metric at least partially according to the set-level profile associated with the content set identifier by estimating a future compression gain achieved by pre-positioning the content set in anticipation of estimated future requests for the content set as a function of a percentage of the content set anticipated to change in relation to the estimated future requests for the content set, the future compression gain being estimated according to the set-level profile associated with the content set identifier, such that the ACV metric is functionally related to the future compression gain;

determining whether to anticipatorily pre-position the content set over the communications path according to the ACV metric; and

when it is determined to anticipatorily pre-position the content set over the communications path according to the ACV metric, determining whether to multicast the data block over the communications path to a client of the plurality of clients according to the fingerprint.

2. The method of claim 1, wherein generating the ACV metric further comprises:

estimating the estimated future requests anticipated for the content set;

estimating a cost of downloading the content set as pre-positioned content over the communications path in relation to the estimated future requests for the content set; and

estimating the percentage of the content set anticipated to change in relation to the estimated future requests for the content set,

such that the future compression gain is functionally related to the estimated number of future requests anticipated for the content set divided by the estimated cost of downloading the content set and the estimated percentage of the content set anticipated to change.

3. The method of claim 1, wherein generating the ACV metric comprises:

generating a cost of content metric indicating an anticipated cost resulting from pre-positioning the content set prior to a request for the content set;

generating a value of content metric indicating an anticipated benefit resulting from pre-positioning the content set prior to a request for the content set; and

performing a cost-benefit analysis according to the cost of content metric and the value of content metric,

wherein at least one of the cost of content metric or the value of content metric is generated according to the set-level profile associated with the content set identifier.

4. The method of claim 1, further comprising:

when it is determined to multicast the data block;

multicasting the data block over the communications path; and

using the content set identifier to determine whether the client of the plurality of clients accepts the data block multicast over the communications path.

5. The method of claim 4, wherein using the content set identifier to determine whether the client of the plurality of clients accepts the data block multicast over the communications path comprises:

determining, at the server side of the communications system, whether to include the client of the plurality of clients in a multicast group,

wherein the data block is multicast over the communications path according to the multicast group.

6. The method of claim 5, further comprising:

detecting a link condition affecting communications over the communications path with at least a portion of the multicast group; and

selecting a modcode as a function of the link condition,

wherein the data block is multicast over the communications path further according to the modcode.

7. The method of claim 4, wherein using the content set identifier to determine whether the client of the plurality of clients accepts the data block multicast over the communications path comprises:

determining, at the client of the plurality of clients, whether to locally store the data block according to the content set identifier.

8. The method of claim 1, wherein the set-level profile comprises set-level metadata.

9. The method of claim 1, wherein:

the communications system has a first communications path comprising a first shared forward link over which bandwidth resources are shared during a multicast communication between the server side of the communications system and a first set of clients and a second communications path comprising a second shared forward link over which bandwidth resources are shared during a multicast communication between the server side of the communications system and a second set of clients;

the data block is intercepted in response to a request for the content set by one of the first set of clients; and

the determining whether to anticipatorily pre-position the content set comprises determining whether to anticipatorily pre-position the content set over the second communications path according to the ACV metric.

10. The method of claim 1, wherein the content set identified by the content set identifier dynamically changes along with changes to the content objects comprised by the content set.

11. The method of claim 1, wherein determining whether to multicast the data block over the communications path to the client of the plurality of clients according to the fingerprint comprises:

using the fingerprint to determine whether the data block matches byte-level information being communicated to another client of the plurality of clients over the communications path via an active session stream.

12. The method of claim 1, wherein determining whether to multicast the data block over the communications path to the client of the plurality of clients according to the fingerprint comprises:

using the fingerprint to determine whether the traffic is currently stored in the client of the plurality of clients dictionary configured to store data local to the client of the plurality of clients.

13. The method of claim 1, further comprising:

downloading the content set by recursively requesting downloads of the plurality of content objects comprised by the content set,

wherein the intercepting the data block occurs while downloading the content set.

14. The method of claim 1, wherein the content set comprises a content feed or a webpage

15. A server system for multicasting over a communications system having a communications path between a server side of the communications system and a plurality of clients, the communications path comprising a shared forward link over which bandwidth resources are shared during a multicast communication, the server system comprising:

an optimizer module, stored in a memory at the server side of the communications system, the optimizer module, when executed, causing a processor to;

intercept a data block comprising a header portion and a content portion, the data block being communicated as part of a content set over the communications path, the content set comprising a plurality of content objects and being identified by a content set identifier, the content set identifier being associated with a set-level profile characterizing the content set;

associate the data block with the content set identifier; and

generate a fingerprint using byte-level information comprised by the content portion of the data block;

an anticipatory content value (ACV) generator module, stored in the memory, communicatively coupled with the optimizer module, the ACV generator module, when executed, causing the processor to;

generate an ACV metric at least partially according to the set-level profile associated with the content set identifier by estimating a future compression gain achieved by pre-positioning the content set in anticipation of estimated future requests for the content set as a function of a percentage of the content set anticipated to change in relation to the estimated future requests for the content set, the future compression gain being estimated according to the set-level profile associated with the content set identifier, such that the ACV metric is functionally related to the future compression gain; and

a pre-positioning module, stored in the memory, communicatively coupled with the ACV module, the pre-positioning module, when executed, causing the processor to;

determine whether to anticipatorily pre-position the content set over the communications path according to the ACV metric; and

when it is determined to anticipatorily pre-position the content set over the communications path according to the ACV metric, determines whether to multicast the data block over the communications path to a client of the plurality of clients according to the fingerprint.

16. The server system of claim 15, wherein the ACV generator module is further configured to:

generate a cost of content metric indicating an anticipated cost resulting from pre-positioning the content set prior to a request for the content set;

generate a value of content metric indicating an anticipated benefit resulting from pre-positioning the content set prior to a request for the content set; and

perform a cost-benefit analysis according to the cost of content metric and the value of content metric,

wherein at least one of the cost of content metric or the value of content metric is generated according to the set-level profile associated with the content set identifier.

17. The server system of claim 15, wherein the pre-positioning module is further configured to:

multicast the data block over the communications path when it is determined to multicast the data block; and

use the content set identifier to determine whether the client of the plurality of clients accepts the data block multicast over the communications path.

18. The server system of claim 15, wherein the ACV generator module is further configured to:

estimate the estimated future requests anticipated for the content set;

estimate a cost of downloading the content set as pre-positioned content over the communications path in relation to the estimated future requests for the content set; and

estimate the percentage of the content set anticipated to change in relation to the estimated future requests for the content set,

such that the future compression gain is functionally related to the estimated number of future requests anticipated for the content set divided by the estimated cost of downloading the content set and the estimated percentage of the content set anticipated to change.