Load-balancing an asymmetrical distributed erasure-coded system

• US 20100094974A1
• Filed: 10/15/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 8,819,261 B2
• Time in Patent Office: Days
• US Class Current: 709/219
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: G06F 16/70 of video data
• CPC Class Codes: H03M 13/37 Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1091 Interfacing with client-server systems or between P2P systems
• 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

Load-balancing an asymmetrical distributed erasure-coded system including fractional-storage CDN servers, storing, at a high storage gain, erasure-coded fragments encoded with a redundancy factor greater than one from segments, and a plurality of assembling devices, each obtaining fragments from a subgroup of the servers. The subgroups are selected from the servers still capable of increasing their fragment delivery throughput. Wherein not all of the servers have the same fragment delivery bandwidth capability, and the storage gain of each segment on each server is usually not strictly proportional to the bandwidth capability of the server, and the aggregated throughput used by the servers to deliver fragments may approach the aggregated bandwidth capabilities of the servers.

Claims

1. ) A distributed system comprising:

fractional-storage CDN servers configured to store, at an average storage gain >

5, erasure-coded fragments associated with segments; and

a plurality of assembling devices, each configured to obtain fragments from a subgroup of the servers;

the subgroups are selected from the servers still capable of increasing their fragment delivery throughput;

wherein not all of the servers have the same fragment delivery bandwidth capability, the storage gain of each segment on each server and the amount of fragments obtained from each server by each assembling device are usually independent of the bandwidth capability of the server, and the aggregated throughput used by the servers to deliver fragments may approach the aggregated bandwidth capabilities of the servers.

2. ) The distributed system of claim 1, wherein the assembling devices are further configured to use a fragment pull protocol to obtain the fragments, and to select the subgroups of servers from which they obtain fragments.

3. ) The distributed system of claim 2, wherein the assembling devices select for the subgroups the servers with the approximately highest unutilized bandwidth, and the erasure-coded fragments support source-selection diversity.

4. ) The distributed system of claim 2, wherein servers approaching their bandwidth usage limits exhibit an increased latency in responding to fragment requests;

and the assembling devices are further configured to detect the increased latency, and to select other servers having lower latencies for the subgroups.

5. ) The distributed system of claim 1, wherein the segments belong to streaming contents, and the assembling devices reselect the subgroups from time to time while obtaining the fragments.

6. ) The distributed system of claim 1, wherein the assembling devices are configured to obtain the fragments using a fragment pull protocol.

7. ) The distributed system of claim 6, wherein servers approaching their bandwidth usage limits exhibit an increased variance in the latency in responding to fragment requests, and the assembling devices are further configured to detect the increased latency variance, and to select other servers having lower latency variance for the subgroups.

8. ) The distributed system of claim 6, wherein the outgoing bandwidth of at least some of the fractional-storage CDN servers is shared by several applications, and the bandwidth capability to providing the fragments varies accordingly.

9. ) The distributed system of claim 6, wherein the bandwidth capability of at least some of the servers changes on-the-fly.

10. ) The distributed system of claim 1, wherein the assembling devices are configured to obtain the fragments using sub-transmissions, and the erasure-coded fragments support source-selection diversity.

11. ) The distributed system of claim 1, wherein the erasure-coding is rateless-coding potentially resulting in fragments having a limitless redundancy factor.

12. ) The distributed system of claim 1, wherein the servers belong to at least two different classes;

the first class comprises high bandwidth CDN servers directly connected to the Internet backbone, and the second class comprises lower bandwidth CDN servers not directly connected to the Internet backbone.

13. ) A distributed system comprising:

fractional-storage CDN servers configured to store, at an average storage gain >

5, erasure-coded fragments associated with segments; and

a plurality of assembling devices, each configured to obtain fragments from a subgroup of the servers;

wherein the servers of the subgroups are selected based on an approximately random selection algorithm weighted according to the unutilized bandwidth of the servers;

wherein not all of the servers have the same fragment delivery bandwidth capabilities, the storage gain of each segment on each server is usually not strictly proportional to the server'"'"'s fragment delivery bandwidth capability, and the aggregated throughput used by the servers to deliver fragments may approach the servers'"'"' aggregated bandwidth capabilities.

14. ) The distributed system of claim 13, wherein the assembling devices are configured to obtain the fragments using a fragment pull protocol.

15. ) A method comprising:

distributing erasure-coded fragments associated with segments between fractional-storage servers not having the same fragment delivery bandwidth capabilities;

selecting for assembling devices subgroups of servers having enough unutilized bandwidth to provide fragments;

retrieving erasure-coded fragments by the assembling devices from the subgroups using a fragment pull protocol; and

allowing additional assembling devices to retrieve fragments from sub-groups of the servers having enough unutilized bandwidth to provide fragments, until the aggregated fragment delivery throughput from the servers approaches their aggregated bandwidth capabilities;

wherein the storage gain of each segment on each server and the amount of fragments obtained from each server by each assembling device are usually independent of the bandwidth capability of the server.

16. ) The method of claim 15, wherein the erasure-coding is rateless-coding.

17. ) The method of claim 15, wherein the segments belong to streaming contents, and further comprising changing the servers in the subgroups from time to time while retrieving the fragments.

18. ) The method of claim 15, wherein the amount of unutilized bandwidth for fragment delivery of at least some of the servers changes on-the-fly, and further comprising compensating for the change by retrieving the fragments from the servers having enough unutilized bandwidth to provide the requested fragments.

19. ) The method of claim 15, wherein distributing the fragments comprises distributing the fragments to at least two different classes of servers;

the first class comprises high bandwidth CDN servers directly connected to the Internet backbone, and the second class comprises lower bandwidth CDN servers not directly connected to the Internet backbone.

20. ) The method of claim 15, further comprising selecting, by the assembling devices, the servers having the highest amount of unutilized fragment delivery bandwidth as their subgroups.