Methods and systems combining push and pull protocols

• US 7,822,855 B2
• Filed: 10/14/2009
• Issued: 10/26/2010
• Est. Priority Date: 10/15/2008
• Status: Active Grant

• Current Assignee: Xenogenic Development Limited Liability Company (Intellectual Ventures LLC)
• Original Assignee: Patentvc Limited
• Inventors: Thieberger, Gil, Zuckerman, Gal
• Primary Examiner(s): WANG, LIANG CHE A
• Application Number:
  US12/579,408
• Publication Number:
  US 20100094968A1
• Time in Patent Office: 377 Days
• Field of Search: 709/217, 709/218, 709/219, 709/223, 709/230, 709/231, 709/226
• US Class Current: 709/226
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• 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]

Abstract

Combining push and pull protocols, including the steps of pushing approximately a minimal decodable set of erasure-coded fragments to an assembling device, determining the fragment loss at the assembling device, and pulling additional erasure-coded fragments, using a fragment pull protocol, to compensate for the fragment loss. Optionally, the system includes a CDN streaming server and a fractional-storage CDN server, both storing unique erasure-coded fragments associated with segments of streaming content. The CDN streaming server pushes streams of fragments to a plurality of assembling devices, and the fractional-storage CDN server provides fragments associated with recently pushed segments in response to fragment pull protocol requests by the assembling devices.

Claims

1. A method comprising:

receiving, by an assembling device via a push transmission, less than a decodable set of erasure-coded fragments;

wherein erasure-coding denotes a process in which a sequence of erasure-coded fragments are generated from a segment such that the segment can be reconstructed from essentially any subset of the erasure-coded fragments of size not smaller than the size of the segment;

determining the number of additional erasure-coded fragments needed to reach the decodable set of erasure-coded fragments; and

shortly thereafter pulling on-the-fly, by the assembling device, additional erasure-coded fragments usable to decode several segments, each fragment pull request associated with a specific segment, wherein the received erasure-coded fragments and the additional pulled erasure-coded fragments are of essentially the same erasure-coding and therefore the received erasure-coded fragments and the additional pulled erasure-coded fragments can be decoded together.

2. The method of claim 1, wherein a streaming server is pushing the less than a decodable set of fragments, and the additional fragments are pulled from the streaming server.

3. The method of claim 2, wherein the erasure-coding is rateless-coding, the fragment pull protocol is a fragment pull protocol for high latency, and the streaming server is a Content Delivery Network (CDN) server located close to or on the Internet backbone.

4. The method of claim 1, wherein a streaming server is pushing the less than a decodable set of fragments, and the additional fragments are pulled from at least one fractional-storage Content Delivery Network (CDN) server, wherein each fractional-storage CDN server configured to store at least one erasure-coded fragment but less than the minimum data required to reconstruct the segments.

5. The method of claim 1, wherein the additional fragments are pulled from a fractional-storage Content Delivery Network (CDN) server configured to store at least one erasure-coded fragment but less than the minimum data required to reconstruct the segments.

6. The method of claim 1, wherein the fragments are associated with streaming content, and further comprising receiving the less than a decodable set of fragments via a broadcast or a multicast transmission.

7. The method of claim 6, wherein the broadcast or multicast transmission comprises a TCP/IP session.

8. The method of claim 6, wherein the broadcast or multicast transmission comprises an RTP stream.

9. The method of claim 6, further comprising receiving the broadcast or multicast transmission from at least two streaming servers.

10. The method of claim 1, further comprising receiving the less than a decodable set of fragments via a broadcast transmission, and utilizing for the broadcast transmission at least one type of channel that is not used for pulling the additional fragments.

11. The method of claim 10, wherein the at least one type of channel is selected from:

a satellite channel, a DVB-T channel, an ATSC channel, or a WiMAX broadcasting channel.

12. A system comprising:

a Content Delivery Network (CDN) streaming server and a fractional-storage CDN server, both configured to store unique erasure-coded fragments associated with segments of streaming content;

wherein erasure-coding denotes a process in which a sequence of erasure-coded fragments are generated from a segment such that the segment can be reconstructed from essentially any subset of the erasure-coded fragments of size not smaller than the size of the segment, and the fractional-storage CDN server configured to store at least one erasure-coded fragment but less than the minimum data required to reconstruct the segments;

the CDN streaming server is configured to push streams of the stored fragments, which are associated with the segments of streaming content, to a plurality of assembling devices; and

the fractional-storage CDN server is configured to provide on-the-fly fragments associated with recently pushed segments in response to fragment pull protocol requests transmitted by the assembling devices, each fragment pull request associated with a specific segment, wherein the received erasure-coded fragments and the additional pulled erasure-coded fragments are of essentially the same erasure-coding and therefore the received erasure-coded fragments and the additional pulled erasure-coded fragments can be decoded together.

13. The system of claim 12, wherein the CDN streaming server comprises a plurality of fractional-storage CDN servers.

14. The system of claim 13, wherein the servers that push fragments and the servers that provide fragments in response to pull requests are the same servers.

15. The system of claim 12, wherein the system comprises a plurality of CDN streaming servers and a plurality of fractional-storage CDN servers, and the assembling devices are configured to initiate the fragment pull protocol requests in order to retrieve substitute fragments needed to reconstruct segments instead of fragments lost via the push stream.

16. The system of claim 12, wherein the assembling devices are configured to create intentional delays between reconstructing the segments and displaying the segments in order to have enough time to pull substitute fragments needed to compensate for lost pushed fragments.

17. The system of claim 12, wherein at least two streaming servers synchronously push fragments to each assembling device.

18. The system of claim 12, wherein at least two streaming servers asynchronously push fragments to each assembling device.

19. The system of claim 18, wherein the assembling device compensates for pushed fragments that are late to arrive by requesting substitute fragments using the fragment pull protocol.

20. The system of claim 18, wherein the streaming servers providing pushed fragments that are late to arrive, are replaced by other servers capable of providing the pushed streams.