Maximum bandwidth broadcast-like streams

• US 7,827,296 B2
• Filed: 10/14/2009
• Issued: 11/02/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): Lin, Kenny S
• Application Number:
  US12/579,273
• Publication Number:
  US 20100094956A1
• Time in Patent Office: 384 Days
• Field of Search: 709/223, 709/230, 709/231
• US Class Current: 709/230
• 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 maximum bandwidth broadcast-like streams, including a plurality of assembling devices; each assembling device retrieves, approximately simultaneously, erasure-coded fragments from a plurality of fractional-storage CDN servers, whereby the broadcast-like streaming contents are reconstructed from the fragments, and wherein different mixtures of broadcast-like streaming contents can be retrieved by the assembling devices until the aggregated bandwidth used by the assembling devices to retrieve the fragments approaches the aggregated fragment delivery bandwidth capabilities of the servers.

Claims

1. A system, comprising:

a plurality of assembling devices and a plurality of fractional-storage CDN servers;

the assembling devices configured to obtain decodable sets of erasure-coded fragments associated with segments of streaming contents, from the fractional-storage CDN servers, while following segments of the same contents are on-the-fly essentially sequentially encoded into erasure-coded fragments and distributed to the CDN servers;

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;

wherein different mixtures of contents can be obtained by the assembling devices until the aggregated bandwidth used by the assembling devices to obtain the fragments from the CDN servers exceeds at least 85% of the total fragment delivery bandwidth of the CDN servers.

2. The system of claim 1, wherein the assembling devices use a fragment pull protocol to obtain the fragments associated with the segments from the servers, and the aggregated bandwidth used to deliver each segment does not exceed the aggregated fragment delivery bandwidth of the servers storing the fragments associated with the segment.

3. The system of claim 2, wherein the assembling devices are configured to obtain the fragments from the least loaded servers.

4. The system of claim 2, wherein the erasure-coding is rateless-coding, and the assembling devices are configured to randomly or pseudo randomly select the servers from which to obtain the fragments.

5. The system of claim 1, wherein most of the servers are configured to store at least one fragment per each segment per each content.

6. The system of claim 1, wherein the aggregated bandwidth used by the assembling devices to obtain the fragments exceeds at least 95% of the total fragment delivery bandwidth of the servers, and at least some of the contents are live streams, and the erasure-coding is rateless-coding.

7. The system of claim 1, wherein the bandwidth demands for the contents are not known prior to the actual consumption of the streams by the assembling devices, and the erasure-coding is rateless-coding.

8. The system of claim 1, wherein unutilized bandwidth of the servers can be utilized by the assembling devices to obtain any content.

9. The system of claim 8, wherein starting the distribution of a new content to the servers by a streaming source, causes new, previously inactive assembling devices, to start obtaining fragments associated with the new content.

10. The system of claim 8, wherein at least some of the assembling devices that start obtaining the content do so as a result of switching from a previously obtained stream.

11. A system comprising:

a plurality of fractional-storage servers configured to receive erasure-coded fragments associated with segments of streaming contents;

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

while following segments of the contents are on-the-fly essentially sequentially encoded into erasure-coded fragments and are still received by the servers, the servers are further configured to deliver the fragments according to various mixtures of demand for the contents, and up to a point where the total fragment delivery bandwidth exceeds at least 85% of the total outgoing fragment delivery bandwidth of the servers.

12. The system of claim 11, wherein the servers are fractional-storage CDN servers configured to store at least one erasure-coded fragment per each segment per each content.

13. The system of claim 12, wherein the contents are live channels, at least 10% of devices assembling the live channels obtain the same live channel, and the erasure-coding is rateless-coding.

14. The system of claim 11, further comprising assembling devices configured to use a fragment pull protocol to retrieve the required fragments.

15. The system of claim 14, wherein the servers are fractional-storage CDN servers, and the fragment pull protocol comprises a process for selecting the least loaded fractional-storage CDN servers to serve each assembling device or group of assembling devices.

16. The system of claim 14, wherein the servers are fractional-storage CDN servers, and the fragment pull protocol comprises a process for randomly or pseudo randomly selecting the fractional-storage CDN servers that serve each assembling device or group of assembling devices.

17. The system of claim 11, further comprising assembling devices configured to use a fragment pull protocol to retrieve the erasure-coded fragments, and the fragments are encoded with a redundancy factor greater than 4.

18. A method comprising:

retrieving, by assembling devices, from a plurality of fractional-storage CDN servers, using a fragment pull protocol, erasure-coded fragments associated with segments of contents, which are on-the-fly essentially sequentially erasure coded and received by the servers;

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;

balancing the servers using the fragment pull protocol; and

allowing additional assembling devices to retrieve fragments until the aggregated bandwidth used by the assembling devices to retrieve the fragments from the servers exceeds at least 85% of the aggregated fragment delivery bandwidth of the servers.

19. The method of claim 18, wherein the aggregated bandwidth used by the assembling devices to retrieve the fragments exceeds 95% of the aggregated fragment delivery bandwidth of the servers, and the erasure-coding is rateless-coding.

20. The method of claim 18, wherein the step of balancing the servers comprises retrieving fragments from the servers having lower latencies than most of their alternatives.