Methods and systems for using a distributed storage to its maximum bandwidth

• US 20100094955A1
• Filed: 10/14/2009
• Published: 04/15/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
• Granted Patent: US 7,818,441 B2
• Time in Patent Office: Days
• US Class Current: 709/219
• 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

Using a distributed storage to its maximum bandwidth including the following steps: for each group of at least one assembling device, selecting a subgroup of fractional-storage CDN servers according to at least one criterion, whereby a plurality of server subgroups are selected for a plurality of assembling device groups. And retrieving, using a pull protocol, by the assembling devices from the subgroups of servers, erasure-coded fragments associated with multiple segments of contents, until the aggregated bandwidth used for retrieving the fragments approaches the aggregated bandwidth of the servers included in the subgroups, and as long as the aggregated bandwidth used for delivering each segment does not exceed the aggregated bandwidth of the servers storing the fragments generated from the segment.

Claims

1. ) A method comprising:

for each group of at least one assembling device, selecting a subgroup of fractional-storage CDN servers according to at least one criterion, whereby a plurality of server subgroups are selected for a plurality of assembling device groups; and

retrieving using a fragment pull protocol, by the assembling devices from the subgroups of servers, erasure-coded fragments associated with segments of contents, until the aggregated bandwidth used for retrieving the fragments approaches the aggregated bandwidth of the servers included in the subgroups, and as long as the aggregated bandwidth used for delivering each segment does not exceed the aggregated bandwidth of the servers storing the fragments encoded from the segment.

2. ) The method of claim 1, further comprising repeating the step of selecting the subgroup of servers occasionally on-the-fly.

3. ) The method of claim 2, wherein the fragment pull protocol is a fragment pull protocol for high latency, each server stores at least one fragment per approximately each segment of each content, and whereby it is possible for any content to be retrieved utilizing a bandwidth approaching the aggregated bandwidth of the servers.

4. ) The method of claim 3, further comprising the step of distributing the fragments to the servers with approximately no prior knowledge of the future bandwidth demand for retrieving each content.

5. ) The method of claim 2, wherein the reselection is performed by a control server, whereby the decisions regarding the selected servers are transmitted to the relevant assembling devices.

6. ) The method of claim 2, wherein selecting the subgroup of servers according to at least one criterion comprises selecting the servers having lower loads and lower latencies than most of their alternatives, and the fragment pull protocol is a fragment pull protocol for high latency.

7. ) The method of claim 2, wherein the reselection is performed by each assembling device for itself, and the erasure-coding is rateless-coding potentially resulting in fragments having a limitless redundancy factor.

8. ) The method of claim 2, wherein the reselection is performed by each assembling device, the reselection is performed approximately per each segment or group of segments, and approximately all of the assembling devices use the same criterion for selecting the subgroups.

9. ) The method of claim 2, wherein a first portion of the assembling devices use a first criterion and a second portion of the assembling devices use a second criterion for selecting the servers in the subgroups.

10. ) The method of claim 2, further comprising reselecting the subgroups while retrieving the fragments associated with the beginnings of the contents.

11. ) The method of claim 1, further comprising repeating the step of selecting the servers occasionally on-the-fly for only some of the servers.

12. ) A method comprising:

obtaining by assembling devices, from subgroups of fractional-storage servers, erasure-coded fragments encoded from segments of at least one content; and

changing at least one of the servers in the subgroups on-the-fly from time to time utilizing a fragment pull protocol;

wherein different mixtures of segments can be simultaneously obtained by approximately any number of assembling devices, until the aggregated bandwidth used for obtaining the segments approaches the available aggregated bandwidth of the servers, and as long as the aggregated bandwidth used to deliver each segment does not exceed the aggregated bandwidth of the servers storing the fragments associated with the segment.

13. ) The method of claim 12, wherein each server stores at least one fragment per approximately each segment of each content, and the assembling devices are using a fragment pull protocol for obtaining at least most of the fragments from the servers.

14. ) The method of claim 12, wherein the assembling devices are using a fragment pull protocol for obtaining at least most of the fragments from the servers, and the step of changing at least one of the servers in the subgroups comprises reselecting the servers approximately randomly from all of the available servers;

and wherein the erasure-coding is rateless-coding potentially resulting in fragments having a limitless redundancy factor.

15. ) The method of claim 12, wherein the assembling devices are using a fragment pull protocol for obtaining the fragments from the servers, and the step of changing at least one of the servers in the subgroups comprises changing approximately randomly only a portion of the servers in the subgroups.

16. ) The method of claim 12, wherein the erasure-coding is rateless-coding, the assembling devices are using a fragment pull protocol for obtaining the fragments from the servers, and further comprising the step of distributing the fragments to the servers with approximately no prior knowledge of the future bandwidth demand for obtaining each segment.

17. ) The method of claim 12, wherein the servers are fractional-storage CDN servers located close to or on the Internet backbone, and the assembling devices obtaining the fragments via at least two sub-transmissions transmitted by the servers.

18. ) A distributed system comprising:

CDN servers configured to store enough erasure-coded fragments to reconstruct segments of streaming content;

for each segment, approximately each CDN server is configured to store less than the minimal amount of erasure-coded fragments needed to reconstruct the segment;

the distributed system is further configured to provide erasure-coded fragments to assembling devices at a total throughput approaching its maximum aggregated bandwidth, while supplying erasure-coded fragments to reconstruct approximately any possible mixture of streaming contents;

wherein one or more of the assembling devices can replace one or more of the servers they retrieve from, with different servers, approximately instantaneously.

19. ) The distributed system of claim 18, wherein the assembling devices are configured to use a fragment pull protocol to retrieve at least most of the fragments from the CDN servers.

20. ) The distributed system of claim 18, wherein the CDN servers are located close to or on the Internet backbone, at least most of the fragments are supplied via a plurality of sub-transmissions, and the erasure-coding is rateless-coding.