Deltacasting for overlapping requests

• US 8,775,503 B2
• Filed: 01/08/2010
• Issued: 07/08/2014
• 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:
  US12/684,726
• Publication Number:
  US 20100185730A1
• Time in Patent Office: 1,642 Days
• Field of Search: 709/203, 709/231, 709/238, 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 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 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 traffic at the server side of the communications system, the traffic comprising a header portion and a content portion and being part of a first client session stream configured to communicate a content stream comprising the traffic to a first client over the communications path, the server side in communication with a global stream model configured to maintain models of active session streams being communicated over the communications path, one of the active session streams being a second client session stream currently communicating the content stream to a second client over the communications path so that an elapsed portion of the content stream has already been communicated to the second client and a remaining portion of the content stream has not yet been communicated to the second client when the traffic is intercepted;

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

using the fingerprint to identify overlapping requests by determining that the traffic 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; and

when the traffic matches the byte-level information comprised by the elapsed portion of the content stream and thus identifies overlapping requests, configuring the first client session stream, the second client session stream, and a shared session stream to collapse at least some of the remaining portion of the content stream for the first client session stream and the second client session stream by configuring the shared session stream to multicast at least some of the remaining portion of the content stream from the server side of the communications system to the first client and the second client over the communications path.

2. The method of claim 1, further comprising:

multicasting at least some of the remaining portion of the content stream from the server side of the communications system to the first client and the second client over the communications path over the shared session stream.

3. The method of claim 2, wherein:

configuring the shared session stream to multicast at least some of the remaining portion of the content stream from the server side of the communications system to the first client and the second client over the communications path comprises associating a content stream identifier with at least the remaining portion of the content stream being communicated as part of the shared session stream; and

multicasting at least some of the remaining portion of the content stream from the server side of the communications system to the first client and the second client comprises directing the first client and the second client to accept traffic associated with the content stream identifier.

4. The method of claim 1, further comprising:

storing a representation of the traffic in the global stream model.

5. The method of claim 1, further comprising:

communicating the traffic to the first client; and

storing a representation of the traffic in a client model configured to maintain a model of content communicated to the first client.

6. The method of claim 5,

wherein the representation of the traffic is stored in the client model without verification that the traffic was successfully received by the first client.

7. The method of claim 5, further comprising:

after communicating the traffic to the client, receiving verification from the first client of successful receipt of the traffic by the first client; and

wherein the representation of the traffic is stored in the client model only after receiving the verification from the first client.

8. The method of claim 5,

wherein the client model comprises a model of a client dictionary configured to store byte level information local to the first client.

9. The method of claim 5, further comprising:

after configuring the shared session stream;

intercepting shared traffic associated with the shared session stream at the server side of the communications system; and

multicasting the shared traffic over the shared session stream to the first client and the second client.

10. The method of claim 5, further comprising:

after configuring the shared session stream;

intercepting shared traffic associated with the shared session stream at the server side of the communications system;

generating a second fingerprint using byte-level information comprised by a content portion of the shared traffic;

using the second fingerprint to determine whether the shared traffic has been previously communicated to the first client according to the client model; and

when the shared traffic has not been previously communicated to the first client according to the client model, multicasting the shared traffic over the shared session stream.

11. The method of claim 10, further comprising:

when the shared traffic has been previously communicated to the first client according to the client model;

compressing the shared traffic using the client model; and

unicasting the compressed shared traffic from the server side of the communications system to the first client over the communications path.

12. 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.

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

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

a processor;

a memory coupled to the processor;

a modeling module, stored in the memory, which, when executed, causes the processor to maintain a global stream model configured to represent models of active session streams being communicated over the communications path, one of the active session streams being a second client session stream currently communicating a content stream to a second client over the communications path;

a server optimization module, stored in the memory, which, when executed, causes the processor to;

intercept traffic, the traffic comprising a header portion and a content portion and being part of a first client session stream configured to communicate the content stream comprising the traffic to a first client over the communications path, such that an elapsed portion of the content stream has already been communicated to the second client and a remaining portion of the content stream has not yet been communicated to the second client over the second client session stream when the traffic is intercepted;

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

use the fingerprint to identify overlapping requests by determining that the traffic 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; and

a stream management module, stored in the memory, which, when executed, causes the processor to;

configure the first client session stream, the second client session stream, and a shared session stream to collapse at least some of the remaining portion of the content stream for the first client session stream and the second client session stream by configuring the shared session stream to multicast at least some of the remaining portion of the content stream from the server side of the communications system to the first client and the second client over the communications path when the traffic matches the byte-level information comprised by the elapsed portion of the content stream and thus identifies overlapping requests.

15. The server system of claim 14, wherein the stream management module is further configured to:

multicast at least some of the remaining portion of the content stream over the shared session stream from the server side of the communications system to the first client and the second client.

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

configure the shared session stream to multicast at least some of the remaining portion of the content stream from the server side of the communications system to the first client and the second client over the communications path by associating a content stream identifier with at least the remaining portion of the content stream being communicated as part of the shared session stream; and

multicast at least some of the remaining portion of the content stream over the shared session stream from the server side of the communications system to the first client and the second client by directing the first client and the second client to accept traffic associated with the content stream identifier.

17. The server system of claim 14, wherein the modeling module is further configured to maintain the global stream model by:

storing a representation of the traffic in the global stream model in association with at least the first client.

18. The server system of claim 14, wherein the modeling module is further configured to:

maintain a client model by storing a representation of the traffic in the client model when the traffic is communicated to the first client.

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

store the representation of the traffic in the client stream model without verification that the traffic was successfully received by the first client.

20. The server system of claim 18, wherein the modeling module is further configured to:

receive verification from the first client of successful receipt of the traffic by the first client after communicating the traffic to the client; and

store the representation of the traffic in the client stream model only after receiving the verification from the first client.

21. The server system of claim 18, wherein:

the server optimization module is further configured, after the stream management module configures the shared session stream, to;

intercept shared traffic associated with the shared session stream; and

the stream management module is further configured to;

multicast the shared traffic over the shared session stream to the first client and the second client.

22. The server system of claim 18, wherein:

the server optimization module is further configured, after the stream management module configures the shared session stream, to;

intercept shared traffic associated with the shared session stream;

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

use the second fingerprint to determine whether the shared traffic has previously been communicated to the first client according to the client model; and

the stream management module is further configured to;

multicast the shared traffic over the shared session stream when the shared traffic has not been previously communicated to the first client according to the client model.

23. The server system of claim 22, wherein the stream management module is further configured to:

when the shared traffic has been previously communicated to the first client according to the client model;

compress the shared traffic using the client model; and

unicast the compressed shared traffic from the server side of the communications system to the first client over the communications path.

24. The server system of claim 14, wherein the server optimization module is configured to generate the fingerprint by:

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

25. A non-transitory machine-readable medium for handling 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 machine-readable medium having instructions stored thereon which, when executed by a machine, cause the machine to perform steps comprising:

intercepting traffic at the server side of the communications system, the traffic comprising a header portion and a content portion and being part of a first client session stream configured to communicate a content stream comprising the traffic to a first client over the communications path, the server side in communication with a global stream model configured to maintain models of active session streams being communicated over the communications path, one of the active session streams being a second client session stream currently communicating the content stream to a second client over the communications path so that an elapsed portion of the content stream has already been communicated to the second client and a remaining portion of the content stream has not yet been communicated to the second client when the traffic is intercepted;

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

using the fingerprint to identify overlapping requests by determining that the traffic 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; and

when the traffic matches the byte-level information comprised by the elapsed portion of the content stream and thus identifies overlapping requests, configuring the first client session stream, the second client session stream, and a shared session stream to collapse at least some of the remaining portion of the content stream for the first client session stream and the second client session stream by configuring the shared session stream to multicast at least some of the remaining portion of the content stream from the server side of the communications system to the first client and the second client over the communications path.

26. The non-transitory machine-readable medium of claim 25, the instructions stored thereon, when executed by the machine, causing the machine to perform steps further comprising:

multicasting at least some of the remaining portion of the content stream over the shared session stream from the server side of the communications system to the first client and the second client.

27. The non-transitory machine-readable medium of claim 25, the instructions stored thereon, when executed by the machine, causing the machine to perform steps further comprising:

communicating the traffic to the first client; and

storing a representation of the traffic in a client model configured to maintain a model of content communicated to the first client.

28. The non-transitory machine-readable medium of claim 27, the instructions stored thereon, when executed by the machine, causing the machine to perform steps further comprising:

after configuring the shared session stream;

intercepting shared traffic associated with the shared session stream at the server side of the communications system; and

multicasting the shared traffic over the shared session stream.

29. The non-transitory machine-readable medium of claim 27, the instructions stored thereon, when executed by the machine, causing the machine to perform steps further comprising:

after configuring the shared session stream;

intercepting shared traffic associated with the shared session stream at the server side of the communications system;

generating a second fingerprint using byte-level information comprised by a content portion of the shared traffic;

using the second fingerprint to determine whether the shared traffic has been previously communicated to the first client according to the client model; and

when the shared traffic has not been previously communicated to the first client according to the client model, multicasting the shared traffic over the shared session stream.

30. The non-transitory machine-readable medium of claim 29, the instructions stored thereon, when executed by the machine, causing the machine to perform steps further comprising:

when the shared traffic has been previously communicated to the first client according to the client model;

compressing the shared traffic using the client model; and

unicasting the compressed shared traffic from the server side of the communications system to the first client over the communications path.

31. The non-transitory machine-readable medium of claim 25, the instructions stored thereon, when executed by the machine, causing the machine to perform the step of generating the fingerprint by:

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