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

• US 7,818,441 B2
• Filed: 10/14/2009
• Issued: 10/19/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,044
• Publication Number:
  US 20100094955A1
• Time in Patent Office: 370 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

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 from the servers exceeds at least 85% of the total fragment delivery bandwidth of the servers that are 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;

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

2. The method of claim 1, further comprising repeating the step of selecting the subgroup of servers at least once on-the-fly.

3. The method of claim 2, further comprising distributing the fragments associated with each of the segments among a number of servers greater than the minimal number of fragments needed to reconstruct the segment.

4. The method of claim 3, wherein distributing the fragments to the servers is done using essentially no prior knowledge of the future bandwidth demand for retrieving each of the contents, and the fragments associated with each of the segments are distributed among at least a majority of the servers.

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 the alternative servers, 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.

8. The method of claim 2, wherein the reselection is performed by the assembling devices, the reselection is performed per segments or group of segments, and essentially 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 at least once 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;

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; 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, until the aggregated bandwidth used for obtaining the segments from the servers exceeds at least 85% of the total fragment delivery 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 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 randomly or pseudo randomly from all of the available servers;

and wherein the erasure-coding is rateless-coding.

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 randomly or pseudo 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 essentially 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:

fractional-storage CDN servers configured to store together enough erasure-coded fragments to reconstruct segments of streaming content, wherein the number of the servers configured to store fragments associated with each of the segments is greater than the minimal number of fragments needed to reconstruct the segment;

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

the distributed system is further configured to provide erasure-coded fragments from the servers to assembling devices at a total throughput exceeding at least 85% of the maximum aggregated fragment delivery bandwidth of the distributed system;

wherein one or more of the assembling devices can replace on-the-fly one or more of the servers they retrieve from, with one or more different servers.

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.