Balancing a distributed system by replacing overloaded servers
First Claim
1. A method for load-balancing fractional-storage CDN servers and assembling devices, comprising:
- pulling essentially concurrently, by an assembling device using a fragment pull protocol, erasure-coded fragments associated with segments of streaming content, from a set of fractional-storage CDN servers;
each fragment pull protocol associated with a specific segment;
each fractional-storage CDN server configured to store erasure-coded fragments but less than a minimum amount of erasure-coded fragments needed to decode the stored erasure-coded fragments;
a total outgoing bandwidth of the set of fractional-storage CDN servers divided by a number of the set of fractional-storage CDN servers is at least 100 times a total outgoing bandwidth of assembling devices divided by a number of the assembling devices;
although each fractional-storage CDN server has a high outgoing bandwidth, the set of fractional-storage CDN servers from which the assembling device is pulling the erasure-coded fragments comprises multiple fractional-storage CDN servers;
occasionally, while pulling the erasure-coded fragments, identifying at least one fractional-storage CDN server from the set of fractional-storage CDN servers, but less than an entire set of fractional-storage CDN servers, which is loaded to a degree requiring replacement; and
while continuing to pull from other fractional-storage CDN servers in the set of fractional-storage CDN servers, replacing, by the assembling device using the fragment pull protocol, the identified at least one fractional-storage CDN server with at least one substitute fractional-storage CDN server that is not loaded to the degree requiring replacement and that is already serving multiple other assembling devices with fragments.
4 Assignments
0 Petitions
Accused Products
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.
71 Citations
20 Claims
-
1. A method for load-balancing fractional-storage CDN servers and assembling devices, comprising:
-
pulling essentially concurrently, by an assembling device using a fragment pull protocol, erasure-coded fragments associated with segments of streaming content, from a set of fractional-storage CDN servers; each fragment pull protocol associated with a specific segment; each fractional-storage CDN server configured to store erasure-coded fragments but less than a minimum amount of erasure-coded fragments needed to decode the stored erasure-coded fragments; a total outgoing bandwidth of the set of fractional-storage CDN servers divided by a number of the set of fractional-storage CDN servers is at least 100 times a total outgoing bandwidth of assembling devices divided by a number of the assembling devices; although each fractional-storage CDN server has a high outgoing bandwidth, the set of fractional-storage CDN servers from which the assembling device is pulling the erasure-coded fragments comprises multiple fractional-storage CDN servers; occasionally, while pulling the erasure-coded fragments, identifying at least one fractional-storage CDN server from the set of fractional-storage CDN servers, but less than an entire set of fractional-storage CDN servers, which is loaded to a degree requiring replacement; and while continuing to pull from other fractional-storage CDN servers in the set of fractional-storage CDN servers, replacing, by the assembling device using the fragment pull protocol, the identified at least one fractional-storage CDN server with at least one substitute fractional-storage CDN server that is not loaded to the degree requiring replacement and that is already serving multiple other assembling devices with fragments. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method for load balancing fractional-storage CDN servers, comprising:
-
retrieving essentially concurrently, by at least one assembling device using a fragment pull protocol, erasure-coded fragments from a first set comprising a plurality of fractional-storage CDN servers; each fragment pull protocol associated with a specific segment; each fractional-storage CDN server configured to store erasure-coded fragments but less than a minimum amount of erasure-coded fragments needed to decode the stored erasure-coded fragments; a total outgoing bandwidth of the plurality of fractional-storage CDN servers divided by a number of the plurality of fractional-storage CDN servers is at least 100 times a total outgoing bandwidth of the assembling devices divided by a number of the assembling devices; identifying a second set of fractional-storage CDN servers that are able to increase their current fragment delivery throughput beyond a throughput already used for delivering erasure-coded fragments to other assembling devices; identifying, while retrieving the erasure-coded fragments, at least one fractional-storage CDN server from the first set that is loaded beyond a certain threshold; and replacing, by an assembling device, the at least one fractional-storage CDN server from the first set that is loaded beyond the certain threshold with a fractional-storage CDN server selected from the second set according to an algorithm. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
19. A system comprising:
- at least 100 fractional-storage CDN servers, comprising processing units and memory units, connected to a public Internet via a physical connection, and at least 100 times more assembling devices;
each fractional-storage CDN server configured to store erasure-coded fragments associated with substantially sequential segments of streaming contents but less than 20% of a minimum amount of erasure-coded fragments needed to decode the stored erasure-coded fragments, and is further configured to respond essentially concurrently with fragments to fragment pull protocol requests issued by the at least 100 times more assembling devices comprising processing units and memory units; a total outgoing bandwidth of the at least 100 fractional-storage CDN servers divided by a number of the at least 100 fractional-storage CDN servers is at least 100 times a total outgoing bandwidth of the at least 100 times more assembling devices divided by a number of the at least 100 times more assembling devices; wherein the system is configured to achieve load-balancing by directing the fragment pull protocol requests towards less loaded fractional-storage CDN servers, wherein an increased throughput on each fractional-storage CDN server as a reaction to directed fragment pull protocol requests from a single assembling device is smaller than a throughput at which the at least 100 fractional-storage CDN server already serves multiple assembling devices with erasure-coded fragments, resulting in system stability during multiple replacement events. - View Dependent Claims (20)
- at least 100 fractional-storage CDN servers, comprising processing units and memory units, connected to a public Internet via a physical connection, and at least 100 times more assembling devices;
Specification