Methods and systems for broadcast-like effect using fractional-storage servers

• US 7,840,680 B2
• Filed: 10/14/2009
• Issued: 11/23/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: Zuckerman, Gal, Thieberger, Gil
• Primary Examiner(s): WANG, LIANG CHE A
• Application Number:
  US12/579,380
• Publication Number:
  US 20100094963A1
• Time in Patent Office: 405 Days
• Field of Search: 709/217, 709/218, 709/219, 709/223, 709/226, 709/230, 709/231
• 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

Methods and systems for broadcast-like effect using fractional-storage servers that receive and store erasure-coded fragments, which are generated on-the-fly from segments of streaming content arriving in real-time. Shortly thereafter, assembling devices obtain the fragments and reconstruct the segments at a rate that allows approximately real-time presentation of the streaming content including the segments.

Claims

1. A method for broadcast-like content streaming, comprising:

encoding essentially sequential segments of content into erasure-coded fragments after the segments are made available by a streaming source;

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;

thereafter, distributing the fragments for storage on a plurality of fractional-storage servers, each configured to store at least one erasure-coded fragment but less than the minimum amount of fragments or data required to reconstruct the segments; and

thereafter, obtaining a set of the fragments usable for reconstructing the segments from at least two of the fractional-storage servers by an assembling device using a fragment pull protocol, each fragment pull request associated with a specific segment, and the erasure-coded fragments obtained by the assembling device from the at least two fractional-storage servers are of essentially the same erasure-coding and therefore the erasure-coded fragments can be decoded together;

wherein obtaining the fragments occurs on-the-fly and before fragments associated with at least one following segment of the content are being distributed.

2. The method of claim 1, wherein the streaming content comprises video, and obtaining the fragments comprises obtaining the fragments at a rate that at least allows continuous on-the-fly reconstruction and playing of the stream.

3. The method of claim 1, wherein the servers are fractional-storage Content Delivery Network (CDN) servers, and the fragment pull protocol is a fragment pull protocol for high latency.

4. The method of claim 3, further comprising reconstructing the segments from the obtained erasure-coded fragments at a rate that essentially follows the rate used to generate the original segments, whereby the reconstructed segments can be played in real-time.

5. The method of claim 3, wherein obtaining the erasure-coded fragments comprises obtaining the erasure-coded fragments associated with segments that are marked as available for retrieval and not attempting to obtain the erasure-coded fragments associated with segments that are not marked as available for retrieval.

6. The method of claim 1, wherein the erasure-coding is rateless-coding.

7. A method for creating a broadcast-like effect, comprising:

generating erasure-coded fragments on-the-fly from 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;

distributing the fragments in real-time to a plurality of fractional-storage servers, each configured to store at least one erasure-coded fragment but less than the minimum amount of fragments or data required to reconstruct the segments; and

obtaining on-the-fly and in real-time, by assembling devices from at least two of the servers, fragments associated with beginning of the content, wherein the erasure-coded fragments obtained by the assembling devices from the at least two servers are of essentially the same erasure-coding and therefore the erasure-coded fragments can be decoded together;

the fragments associated with the beginning of the content are obtained before fragments associated with ending of the content are generated.

8. The method of claim 7, wherein the step of obtaining the fragments in real-time comprises obtaining the fragments using a fragment pull protocol for high latency at an average rate that enables reconstructing the segments from the obtained fragments at a rate that essentially follows the corresponding rate at which the reconstructed segments are consumed when the streaming content is played.

9. The method of claim 7, wherein the servers are fractional-storage Content Delivery Network (CDN) servers, the fragments are obtained using a fragment pull protocol for high latency, and further comprising reconstructing the segments from the obtained fragments.

10. The method of claim 9, wherein the fractional-storage CDN servers are located close to or on the Internet backbone, and the average rate at which the segments are reconstructed essentially follows the average rate at which the segments are received when generating the fragments from the segments.

11. The method of claim 7, whereby segments are reconstructed from the obtained fragments;

wherein the step of obtaining the fragments in real-time comprises obtaining the fragments using a fragment pull protocol at a rate that essentially maintains a fixed distance in segments between the recently reconstructed segment and the segment whose fragments were most recently distributed to the servers, and each fragment pull request associated with a specific segment.

12. The method of claim 7, wherein the erasure-coded fragments support source-selection diversity;

and further comprising generating the segments on-the-fly essentially sequentially from the streaming content.

13. The method of claim 7, wherein the servers are fractional-storage Content Delivery Network (CDN) servers, and wherein the step of obtaining the fragments in real-time comprises obtaining the fragments associated with segments that are marked as available for retrieval and not attempting to obtain the fragments associated with segments that are not marked as available for retrieval.

14. A system comprising:

fractional-storage servers configured to receive and store erasure-coded fragments, which are generated on-the-fly from segments of streaming content arriving in real-time;

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;

each fractional-storage server configured to store at least one erasure-coded fragment but less than the minimum amount of fragments or data required to reconstruct the segments; and

assembling devices configured to obtain the fragments usable to reconstruct the segments from at least two of the fractional-storage servers on-the-fly wherein the erasure-coded fragments obtained by the assembling devices from the at least two fractional-storage servers are of essentially the same erasure-coding and therefore the erasure-coded fragments can be decoded together;

the assembling devices are further configured to reconstruct the segments after the fragments are received by the fractional-storage servers, at a rate that allows essentially a real-time presentation of the streaming content comprising the segments;

the assembling devices further configured to obtain from the fractional-storage servers fragments associated with beginning of the streaming content before fragments associated with ending of the streaming content are received by the fractional-storage servers.

15. The system of claim 14, wherein the servers are fractional-storage Content Delivery Network (CDN) servers, and the assembling devices use a fragment pull protocol to obtain the fragments, each fragment pull request associated with a specific segment.

16. The system of claim 15, wherein the rate at which the segments are reconstructed essentially follows the rate at which the segments arrive.

17. The system of claim 15, wherein the rate at which the segments are reconstructed is determined according to the rate at which content frames are played, and the erasure-coded fragments support source-selection diversity.

18. The system of claim 15, wherein after the fragments are received by the fractional-storage servers is less than 15 seconds after the fragments are received by the fractional-storage servers.

19. The system of claim 14, further comprising indications of whether the fragments are available to be obtained by the assembling devices, whereby the assembling devices are configured to obtain only the fragments indicated as available.

20. The system of claim 14, wherein system amplification factor (Bout/Bin) receives value close to (Tout/(R*Bstream)), where Bout is the total average output bandwidth at which the fragments are obtained by the assembling devices, Bin is the total average bandwidth needed to deliver the fragments for storage on the servers, Tout is the total aggregated outgoing bandwidth of all servers, R is the redundancy factor, and Bstream is the average bandwidth of the streaming content.