DELTACASTING

• US 20100180046A1
• Filed: 01/04/2010
• Published: 07/15/2010
• Est. Priority Date: 01/13/2009
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Sebastian, William B., Lepeska, Peter
• Granted Patent: US 9,369,516 B2
• Time in Patent Office: Days
• US Class Current: 709/234
• 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 method for multicasting over a communications system having a communications path between a server side of the communications system and a client side of the communications system, the communications path comprising a shared forward link over which bandwidth resources are shared during a multicast communication, the method comprising:

intercepting traffic using a server optimizer located at the server side of the communications system between a content source and a plurality of client optimizers, the traffic comprising a header portion and a content portion and being communicated from the content source to a content destination associated with a first client optimizer, the first client optimizer being communicatively coupled with a first client dictionary;

generating a fingerprint as a function of byte-level information comprised by the content portion of the traffic;

determining whether to multicast the traffic by using the fingerprint to determine whether the traffic is currently stored in the first client dictionary; and

when it is determined to multicast the traffic, multicasting the traffic over the communications path from the server side of the communications system to at least the content destination associated with the first client optimizer.

2. The method of claim 1, wherein the communications path is configured to implement an optimizer tunnel between the server optimizer and the plurality of client optimizers.

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

applying a hashing function to the byte-level information comprised by the content portion of the traffic.

4. The method of claim 1, wherein using the fingerprint to determine whether the traffic is currently stored in the first client dictionary comprises:

comparing the fingerprint to a model of the first client dictionary communicatively coupled with the server optimizer.

5. The method of claim 1, wherein determining whether to multicast the traffic by using the fingerprint to determine whether the traffic is currently stored in the first client dictionary comprises:

determining not to multicast the traffic when the traffic is currently stored in the first client dictionary.

6. The method of claim 5, further comprising:

when the traffic is currently stored in the first client dictionary, unicasting a highly compressed representation of the traffic over the communications path to at least the content destination associated with the first client optimizer.

7. The method of claim 6, wherein unicasting the highly compressed representation of the traffic over the communications path to at least the content destination associated with the first client optimizer comprises:

communicating a set of indexes over the communications path from the server optimizer to at least the first client optimizer, the set of indexes referring to data blocks currently stored in the first client dictionary.

8. The method of claim 1, wherein determining whether to multicast the traffic by using the fingerprint to determine whether the traffic is currently stored in the first client dictionary comprises:

estimating a multicast cost to the communications system associated with multicasting the traffic from the server optimizer over the communications path to content destinations associated with a set of client optimizers, the set of client optimizers comprising the first client optimizer;

estimating, as a function of the fingerprint, a multicast benefit to the communications system associated with multicasting the traffic from the server optimizer to the content destinations; and

when the multicast benefit exceeds the multicast cost, multicasting the traffic over the communications path from the server optimizer to the content destinations.

9. The method of claim 8, wherein estimating the multicast cost to the communications system comprises:

determining an amount of bandwidth used by multicasting the traffic from the server optimizer over the communications path.

10. The method of claim 8, wherein estimating the multicast benefit to the communications system comprises:

determining a likelihood that, if the traffic were multicast to the content destinations, a second client optimizer of the set of client optimizers will request substantially the same traffic subsequent to the multicasting of the traffic.

11. The method of claim 8, wherein the set of client optimizers is a subset of the plurality of client optimizers.

12. The method of claim 8, further comprising:

when the multicast benefit does not exceed the multicast cost, unicasting the traffic over the communications path from the server optimizer to the content destination associated with the first client optimizer.

13. The method of claim 1, further comprising:

determining at the server optimizer whether the traffic is a multicast candidate according to a pre-filter criteria,

wherein the generating the fingerprint step is performed only when the traffic is a multicast candidate according to the pre-filter criteria.

14. The method of claim 13, wherein the pre-filter criteria relates to a size of the traffic.

15. The method of claim 13, wherein determining at the server optimizer whether the traffic is a multicast candidate according to the pre-filter criteria comprises evaluating metadata comprised by the header portion of the traffic.

16. The method of claim 1, wherein multicasting the traffic over the communications path from the server optimizer to at least the content destination associated with the first client optimizer comprises:

identifying a set of client optimizers to participate in the multicast;

detecting a link condition affecting communications between the server optimizer and content destinations associated with the set of client optimizers;

selecting a modcode as a function of the link condition; and

multicasting the traffic over the communications path from the server optimizer to the content destinations according to the modcode.

17. The method of claim 16, wherein the modcode is selected so that at least the content destination associated with the first client optimizer can reliably decode the traffic received from the multicasting step.

18. The method of claim 1, wherein the communications path comprises a satellite link.

19. A server system for multicasting to a plurality of user systems via a communications link, each user system comprising a client optimizer, the server system comprising:

a server optimizer, in communication with a content source, in communication with the client optimizers via a communications path, and configured to;

intercept traffic coming from the content source and destined for a user associated with a first client optimizer, the traffic comprising a header portion and a content portion, the content portion representing content being communicated from the content source to the user, the first client optimizer being communicatively coupled with a first client dictionary; and

generate a fingerprint using byte-level information comprised by the content portion of the traffic; and

a multicaster module, communicatively coupled with the server optimizer, and configured to;

determine whether to multicast the traffic by using the fingerprint to determine whether the traffic is currently stored in the first client dictionary; and

when the multicaster module determines to multicast the traffic, multicast the traffic over the communications path from the server optimizer to at least the first client optimizer.

20. The server system of claim 19, wherein the server optimizer is further configured to generate the fingerprint by:

applying a hashing function to the byte-level information comprised by the content portion of the traffic.

21. The server system of claim 19, wherein:

the server optimizer is communicatively coupled with a model of the first client dictionary; and

the multicaster module is further configured to determine whether to multicast the traffic by using the fingerprint to determine whether the traffic is currently stored in the first client dictionary by comparing the fingerprint to the model of the first client dictionary.

22. The server system of claim 19, wherein the multicaster module is further configured to:

when the traffic is currently stored in the first client dictionary, unicast a highly compressed representation of the traffic over the communications path from the server optimizer to the first client optimizer.

23. The server system of claim 19, wherein the multicaster module is further configured to:

determine whether to multicast the traffic by;

estimating a multicast cost to the communications system associated with multicasting the traffic from the server optimizer to a set of client optimizers, the set of client optimizers comprising the first client optimizer; and

estimating, as a function of the fingerprint, a multicast benefit to the communications system associated with multicasting the traffic from the server optimizer to the set of client optimizers; and

multicast the traffic over the communications path from the server optimizer to at least the first client optimizer when the multicast benefit exceeds the multicast cost.

24. The server system of claim 19, wherein the server optimizer is further configured to:

determine whether the traffic is a multicast candidate according to a pre-filter criteria; and

generate the fingerprint only when the traffic is a multicast candidate according to the pre-filter criteria.

25. The server system of claim 19, further comprising:

a coding and modulation module, communicatively coupled with the multicaster module, and configured to;

when multicasting the traffic over the communications path from the server optimizer to at least the first client optimizer, identifying a set of client optimizers to receive the multicast;

detect a link condition affecting communication between the server optimizer and the set of client optimizers; and

select a modcode as a function of the link condition,

wherein the multicaster module is further configured to multicast the traffic over the communications path from the server optimizer to the set of client optimizers according to the modcode.

26. A system for deltacasting comprising:

a plurality of user systems, each user system comprising;

a client dictionary configured to store data local to the respective user system as an indexed set of data blocks; and

a client optimizer, configured to receive traffic and control data, and to determine whether to store the received traffic at the respective client dictionary according to the control data; and

a server system, in communication with a content source and in communication with the plurality of user systems over a communications path, and comprising;

a server optimizer in communication with the client optimizers comprised by the plurality of user systems via the communications path, the server optimizer being configured to;

intercept traffic coming from the content source and destined for a first client optimizer associated with a respective first client dictionary, the traffic comprising a header portion and a content portion, the content portion representing content being communicated from the content source to a user associated with the first client optimizer; and

generate a fingerprint from byte-level information comprised by the content portion of the traffic;

a modeling module configured to store dictionary models indicating contents of the client dictionaries; and

a multicaster module, communicatively coupled with the server optimizer and the modeling module, and configured to;

determine whether to multicast the traffic by using the fingerprint to determine whether the traffic is currently stored in the first client dictionary; and

when the multicaster module determines to multicast the traffic, multicast the traffic over the communications path from the server optimizer to at least the user system associated with the first client optimizer.

27. The system of claim 26, wherein the server optimizer is further configured to generate the fingerprint by:

applying a hashing function to the byte-level information comprised by the content portion of the traffic.

28. The system of claim 26, wherein the communications path comprises a shared forward link configured to allow link capacity sharing among the plurality of user systems.

29. The system of claim 28, wherein the shared forward link comprises a spot beam of a satellite link.