Balancing a distributed system by replacing overloaded servers

• US 20100095004A1
• 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,874,775 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• 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 a distributed system by replacing overloaded servers, including the steps of retrieving, by an assembling device using a fragment pull protocol, erasure-coded fragments associated with segments, from a set of fractional-storage servers. Occasionally, while retrieving the fragments, identifying at least one server from the set that is loaded to a degree requiring replacement, and replacing, using the fragment pull protocol, the identified server with a substitute server that is not loaded to the degree requiring replacement. Wherein the substitute server and the remaining servers of the set are capable of delivering enough erasure-coded fragments in the course of reconstructing the segments.

Claims

1. ) A method for load-balancing fractional-storage servers, comprising:

retrieving, by an assembling device using a fragment pull protocol, erasure-coded fragments associated with segments, from a set of fractional-storage servers;

occasionally, while retrieving the fragments, identifying at least one server from the set that is loaded to a degree requiring replacement; and

replacing, using the fragment pull protocol, the identified server with a substitute server that is not loaded to the degree requiring replacement;

wherein the substitute server and the remaining servers of the set are capable of delivering enough erasure-coded fragments needed in the course of reconstructing the segments.

2. ) The method of claim 1, wherein the step of identifying at least one server from the set that is loaded to a degree requiring replacement is based on receiving an indication that the at least one server is loaded to a degree requiring replacement.

3. ) The method of claim 2, further comprising sending the indication, by the server that is loaded to the degree requiring replacement, in response to a fragment request or a load query.

4. ) The method of claim 1, further comprising measuring the latency between the assembling device and at least one of the servers in the set, and identifying the at least one server that is loaded to a degree requiring replacement based on the measured latency, whereby increased latency may suggest that the server is loaded to a degree requiring replacement.

5. ) The method of claim 1, further comprising measuring the variance in the latency in responding to fragment requests, and identifying the at least one server that is loaded to a degree requiring replacement based on the latency variance, whereby increased latency variance may suggest that the server is loaded to a degree requiring replacement.

6. ) The method of claim 1, further comprising obtaining, from time to time, indications about servers, not in the set, which are not loaded to the degree requiring replacement;

and selecting the substitute server using the obtained indications.

7. ) The method of claim 6, wherein the substitute server is approximately the least loaded server, and the erasure-coded fragments support source-selection diversity.

8. ) The method of claim 1, wherein the identified server approximately does not have enough unutilized bandwidth to support a fragment request.

9. ) The method of claim 1, wherein the identified server approximately does not have enough processing resources available to support a fragment request.

10. ) The method of claim 1, wherein the erasure-coding is rateless-coding potentially resulting in fragments having a limitless redundancy factor, whereby high redundancy increases the number of servers from which the substitute server can be selected.

11. ) A method for load balancing fractional-storage servers, comprising:

retrieving, by assembling devices using a fragment pull protocol, erasure-coded fragments from a first set of fractional-storage servers;

identifying a second set of servers that are able to increase their current fragment delivery throughput;

identifying, while retrieving the fragments, at least one server from the first set that is loaded beyond a certain threshold; and

replacing the server loaded beyond the certain threshold with a server selected from the second set according to an algorithm.

12. ) The method of claim 11, wherein the algorithm comprises approximately random selection of the replacement server, and the erasure-coded fragments support source-selection diversity.

13. ) The method of claim 11, wherein the algorithm comprises selecting the least loaded server as the replacement server, and the erasure-coded fragments support source-selection diversity.

14. ) The method of claim 11, wherein the algorithm comprises selecting the server having approximately the lowest latency in relation to the assembling device as the replacement server.

15. ) The method of claim 14, further comprising obtaining data regarding the router hop-count between the assembling device and the servers, and deriving the latencies from the hop-count data;

whereby high hop-count indicates high latency.

16. ) The method of claim 11, further comprising measuring the latencies by the assembling device, and selecting the server having approximately the lowest latency variance in relation to the assembling device as the replacement server.

17. ) The method of claim 11, wherein the servers of the second set of servers are able to increase their current fragment delivery throughput by using currently unutilized bandwidth.

18. ) The method of claim 11, wherein the servers of the second set are able to increase their current fragment delivery throughput by using currently unutilized computational resources.

19. ) A system comprising:

at least 100 fractional-storage CDN servers connected to the public Internet;

the servers store, at an average storage gain >

5, erasure-coded fragments associated with approximately sequential segments of streaming contents, and are configured to respond with fragments to fragment pull protocol requests issued by assembling devices;

wherein the erasure-coded fragments support source-selection diversity, and the system is configured to achieve load-balancing by directing the fragment pull protocol requests towards the less loaded servers.

20. ) The system of claim 19, wherein the system enables each assembling device to select the least loaded servers by itself.