Deltacasting for overlapping requests

• US 9,172,748 B2
• Filed: 05/27/2014
• Issued: 10/27/2015
• Est. Priority Date: 01/13/2009
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Sebastian, William B.
• Primary Examiner(s): Tran, Philip B
• Application Number:
  US14/288,188
• Publication Number:
  US 20150026241A1
• Time in Patent Office: 518 Days
• Field of Search: 709/203, 709/231, 709/224
• 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 are provided for improving utilization of a communications system (e.g., a satellite communications system) when handling overlapping content requests. Embodiments use various techniques (e.g., dictionary coding techniques) to create fingerprints of content traversing the links of the communications system. These fingerprints are used to identify and exploit opportunities for using multicasting to share forward-link capacity by collapsing multiple overlapping requests for the same content via multiple content session streams into fewer session streams, including one or more shared session streams.

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:

receiving a content request at the server side from a first client over the communications infrastructure;

communicating content data blocks invoked by the content request to the first client via a first content stream over the communications infrastructure in response to the content request;

determining, by the server side according to a global stream model, whether the content request matches at least an elapsed portion of a second content stream being communicated to a second client,

the global stream model maintaining models of active session streams being communicated over the communications infrastructure, and

the second content stream being one of the active session streams, having the elapsed portion already communicated to the second client, and having a remaining portion not yet communicated to the second client; and

multicasting, when the content request matches the elapsed portion of the content stream, at least some of the remaining portion of the second content stream from the server side to the first and second clients over the communications infrastructure concurrently with communicating the content data blocks to the first client over the first client session stream.

2. The method of claim 1, wherein the communicating comprises unicasting.

3. The method of claim 1, wherein the communicating comprises, for each content data block:

determining, by the server side, whether the content data block is presently stored in a local cache of the first client;

unicasting an uncompressed instance of the content data block to the first client when the content data block is not presently stored in the local cache of the first client; and

unicasting a compressed instance of the content data block to the first client when the content data block is presently stored in the local cache of the first client.

4. The method of claim 3, wherein the determining whether the content data block is presently stored in the local cache is performed according to a client cache model maintained by the server side.

5. The method of claim 1, wherein:

the content request indicates a destination address;

the receiving is in response to the first client having redirected the content request from the destination address to the server side; and

the method further comprises, prior to the communicating;

forwarding the content request to the destination address; and

receiving the content data blocks invoked by the content request from the destination address.

6. The method of claim 1, wherein the determining comprises, for each content data blocks invoked by the content request:

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

using the fingerprint to determine whether the content data blocks matches byte-level information comprised by the elapsed portion of the content stream communicated to the second client over the second client session stream according to the global stream model.

7. The method of claim 1, wherein the multicasting comprises:

converting the remaining portion of the second content stream into a shared content stream; and

directing at least the first and second clients to join the shared content stream.

8. A server-side system for multicasting over a communications system in which the server-side system is in communication with a plurality of clients over a shared communications infrastructure, the system comprising:

a server optimization module configured to receive a content request from a first client-side system over the communications infrastructure;

a modeling module configured to determine, according to a global stream model, whether the content request matches at least an elapsed portion of a second content stream being communicated to a second client-side system,

the global stream model maintaining models of active session streams being communicated over the communications infrastructure, and

the second content stream being one of the active session streams, having the elapsed portion already communicated to the second client-side system, and having a remaining portion not yet communicated to the second client-side system; and

a stream management module, communicatively coupled with the server optimization module and the modeling module, and configured to;

communicate content data blocks invoked by the content request to the first client-side system via a first content stream over the communications infrastructure in response to the content request; and

multicast, when the content request matches the elapsed portion of the content stream, at least some of the remaining portion of the second content stream to the first and second client-side systems over the communications infrastructure concurrently with communication the content data blocks to the first client-side system over the first client session stream.

9. The system of claim 8, wherein the stream management module is configured to communicate the first content stream to the first client-side system by:

determining whether the content data block is presently stored in a local cache of the first client-side system;

unicasting an uncompressed instance of the content data block to the first client-side system when the content data block is not presently stored in the local cache; and

unicasting a compressed instance of the content data block to the first client-side system when the content data block is presently stored in the local cache.

10. 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:

directing a content request from a first client to the server side over the communications infrastructure;

first receiving, at the first client in response to the content request, a client session stream comprising a first portion of a content stream invoked by the content request;

second receiving, at the first client from the server side during the first receiving, a multicast session stream comprising a second portion of the content stream, the multicast session stream received in response to a determination by the server side that the content request matches an elapsed portion of an active session stream being communicated to a second client,

the determination being according to a global stream model that maintains models of active session streams being communicated over the communications infrastructure,

the active session stream having the elapsed portion already communicated to the second client and a remaining portion not yet communicated to the second client, and

the second portion corresponding to at least part of the remaining portion of the second content stream;

displaying the first portion of the content stream from the received client session stream to a customer premises device of the first client; and

storing the second portion of the content stream from the received multicast session stream in a local cache of the first client.

11. The method of claim 10, wherein the client session stream is a unicast communication.

12. The method of claim 10, wherein the displaying is performed substantially as the client session stream is received.

13. The method of claim 10, wherein the storing is performed substantially as the multicast session stream is received.

14. The method of claim 10, wherein:

the client session stream comprises a plurality of content data blocks invoked by the content request; and

the first receiving comprises;

receiving an uncompressed instance of each content data block for which there is a determination by the server side that the content data block is not presently stored in the local cache of the first client; and

receiving a compressed instance of each content data block for which there is a determination by the server side that the content data block is presently stored in the local cache.

15. The method of claim 14, further comprising:

retrieving, by the first client for each received compressed instance, a corresponding uncompressed instance of the content data block from the local cache; and

displaying the uncompressed instance of the content data block to the customer premises device.

16. The method of claim 10, further comprising:

after storing the second portion of the content stream, communicating verification from the first client to the server side of successful receipt of the second portion by the first client.

17. The method of claim 10, wherein the first receiving is from the server side.

18. A client-side system in a communications system having a server-side system and a plurality of client-side systems in communication over a shared communications infrastructure, the method comprising:

a redirector configured to direct a content request to the server-side system over the communications infrastructure;

a client optimizer configured to;

first receive, in response to the content request, a client session stream comprising a first portion of a content stream invoked by the content request;

second receive, from the server-side system during the first receiving, a multicast session stream comprising a second portion of the content stream, the multicast session stream received in response to a determination by the server-side system that the content request matches an elapsed portion of an active session stream being communicated to a second client-side system, wherein;

the determination is according to a global stream model that maintains models of active session streams being communicated over the communications infrastructure,

the active session stream has the elapsed portion already communicated to the second client-side system and a remaining portion not yet communicated to the second client-side system, and

the second portion corresponds to at least part of the remaining portion of the second content stream;

display the first portion of the content stream from the received client session stream to a user system in communication with the client optimizer; and

store the second portion of the content stream from the received multicast session stream in a local cache in communication with the client optimizer.

19. The system of claim 18, wherein:

the client session stream comprises a plurality of content data blocks invoked by the content request; and

the client optimizer is configured to first receive by;

receiving an uncompressed instance of each content data block for which there is a determination by the server side that the content data block is not presently stored in the local cache; and

receiving a compressed instance of each content data block for which there is a determination by the server side that the content data block is presently stored in the local cache.

20. The system of claim 19, wherein the client optimizer is further configured to:

retrieve, for each received compressed instance, a corresponding uncompressed instance of the content data block from the local cache; and

display the uncompressed instance of the content data block to the user system.