Transport protocol for anticipatory content

• US 8,897,302 B2
• Filed: 06/14/2012
• Issued: 11/25/2014
• Est. Priority Date: 06/14/2011
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Sebastian, William B.
• Primary Examiner(s): Oveissi, David
• Application Number:
  US13/517,860
• Publication Number:
  US 20120320916A1
• Time in Patent Office: 894 Days
• US Class Current: 370/390
• CPC Class Codes: H04L 1/08 by repeating transmission, e.g. Verdan system H04L1/1858 and H04L1/189 take precedence
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• 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 43/0823 Errors, e.g. transmission errors
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04N 21/2402 Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876
• CPC Class Codes: H04N 21/6375 for requesting retransmission , e.g. of data packets lost or corrupted during transmission from serverARQ protocols H04L1/18; implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP] H04L69/16
• CPC Class Codes: H04N 21/6405 Multicasting data broadcast and multicast in packet switching networks H04L12/18
• CPC Class Codes: H04N 21/6408 Unicasting
• CPC Class Codes: H04N 21/6583 Acknowledgement
• CPC Class Codes: H04N 21/835 Generation of protective data, e.g. certificates protecting software against unauthorised usage in a vending or licensing environment G06F21/10

Abstract

Methods, apparatuses, and systems for improving utilization of a communications system (e.g., a satellite communications system) are provided, using delayed reliability techniques as part of a multicast transport protocol. Embodiments may operate in a client-server context, in which the server-side of the communication link multicasts data to requesting users and to users where the data is being speculatively prepositioned. Requesting users may implement reliability checks to verify receipt of complete data in response to the request while user systems where data is being speculatively prepositioned may receive multicast reliability information in response to reliability requests from other users, but may not request replacement of missing or corrupted data themselves until a request is made for the data by that system.

Claims

1. A method providing reliability in a multicasting 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, the method comprising:

observing a first request for an object, wherein the first request originates from a first user system;

observing, at a server, a response to the first request for the object;

determining, at the server, that the object is a multicast candidate;

multicasting the object over the communications path to the first user system and a second user system, wherein the first user system is different than the second user system;

storing, at the server, packets of the object for retransmission;

receiving, at the server, a reliability message from the first user system identifying holes in a page data map of the object;

communicating a first object repair message to the first user, wherein the first object repair message comprises at least a portion of the packets of the object stored at the server for retransmission;

receiving, at the server, a second request for the object after communicating the first object repair message to the first user system, wherein the second request originates from the second user system; and

communicating a second object repair message to the second user system in response to the second request for the object.

2. The method of claim 1 wherein the first data repair message is multicast to the first user system and the second user system.

3. The method of claim 1 further comprising multicasting a control message to the first user system and the second user system, prior to multicasting the object.

4. The method of claim 1, wherein the reliability message from the first user comprises a set of acknowledgement messages.

5. The method of claim 1, wherein the reliability message from the first user comprises a negative acknowledgement message.

6. The method of claim 1 further comprising:

requesting, by the server, the object from a content server following receipt of the second request;

calculating a set of checksums for a set of blocks of the object; and

communicating the set of checksums from the server to the second user system.

7. The method of claim 6 further comprising receiving a list of missing packets in response to communicating the set of checksums to the second user system;

and wherein communicating the second object repair message to the second user comprises communicating multiple copies of a set of missing packets to the second user system.

8. The method of claim 1 wherein observing the response to the first request comprises intercepting the object using a server optimizer located in the server between a content source and a plurality of client optimizers, the object 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.

9. The method of claim 8 further comprising:

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

determining whether to multicast the object by using the fingerprint to determine whether the object is currently stored in the first client dictionary prior to multicasting the object.

10. The method of claim 9, wherein using the fingerprint to determine whether the object 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.

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

estimating a multicast cost to the communications system associated with multicasting the object 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 object from the server optimizer to the content destinations; and

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

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

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

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

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

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

14. The method of claim 9, wherein multicasting the object 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 object over the communications path from the server optimizer to the content destinations according to the modcode.

15. The method of claim 1 wherein multicasting the object over the communication path to the first user system and the second user system comprises:

dividing the object into blocks and associating each block with a globally unique identifier for each block;

communicating a first block and a first globally unique identifier associated with the first block to the second user system;

storing the first block and the first globally unique identifier at the second user system; and

monitoring, by the second user system, the shared forward link for the first globally unique identifier to determine that a repaired copy of the first block has been sent as part of a multicast object repair message.

16. The method of claim 1 wherein:

the object comprises a first block of information;

the first object repair message and the second object repair message each individually comprise repair information for the first block of data;

wherein the first object repair message is unicast after the server performs a benefit analysis; and

wherein the second object repair message is multicast based at least in part on the first object repair message being unicast.

17. 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;

observe, at the server system, a first request for an object, wherein the first request originates from a first user system;

observe, at the server system, a response to the first request for the object; and

generate a fingerprint using byte-level information comprised by the content portion of the response to the first request; and

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

determine whether to multicast the response to the first request by using the fingerprint to determine whether information associated with the response to the first request is currently stored in a first client dictionary;

multicast the object over the communications path to the first user system and a second user system;

receive, at the server system, a reliability message from the first user system identifying holes in a page data map of the object;

communicate a first object repair message to the first user system;

receive, at the server system, a second request for the object from the second user system after communicating the data repair message to the first user; and

communicate a second object repair message to the second user in response to the second request for the object.

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

determine whether to multicast the response to the first request by;

estimating a multicast cost to the communications system associated with multicasting the response to the first request 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 response to the first request from the server optimizer to the set of client optimizers; and

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

19. A method of prepositioning data at a client system comprising:

observing, at a receiver of a client system, a control channel for a first control packet;

creating, in response to the first control packet a page data map associated with a data file;

storing, in a client storage of the client system, a plurality of packets and associating each packet of the plurality of packets with the page data map, wherein the plurality of packets are received as part of one or more multicast communications;

requesting by a communication from the client system to a content server, the data file after storing the plurality of packets;

receiving, at the client system, a set of checksum data associated with the data file;

communicating, from the client system to a server, a set of holes in the page data map, each hole of the set of holes comprising a position in the page data map without associated data; and

receiving a set of packets corresponding to the set of holes in the page data map.

20. A system for delayed reliability in a multicast communication system 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;

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

a reliability module, configured to communicate a reliability message when missing or corrupted data is identified in response to the content data stored in response to a user request, and to store the content data without error correction when the content data is prepositioned at a user system of the plurality of user systems; 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 the content data coming from the content source and destined for a first client optimizer associated with a respective first client dictionary, the content data 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 content data;

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 content data by using the fingerprint to determine whether a copy of the content data is currently stored in the first client dictionary; and

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