Fault tolerance in a distributed streaming system

• US 8,874,774 B2
• Filed: 10/15/2009
• Issued: 10/28/2014
• Est. Priority Date: 10/15/2008
• Status: Active Grant

• Current Assignee: Xenogenic Development Limited Liability Company (Intellectual Ventures LLC)
• Original Assignee: Aster RISK Management LLC (Intellectual Ventures LLC)
• Inventors: Zuckerman, Gal, Thieberger, Gil
• Primary Examiner(s): CHAO, MICHAEL W
• Application Number:
  US12/579,662
• Publication Number:
  US 20100095013A1
• Time in Patent Office: 1,839 Days
• Field of Search: 709/231
• US Class Current: 709/231
• 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

Fault tolerance in a distributed streaming system including fractional-storage CDN servers storing erasure-coded fragments encoded with a redundancy factor greater than one from segments of streaming contents. Each server delivers fragments, at a certain fragment delivery throughput, to multiple assembling devices using a fragment pull protocol, wherein a reduction in the fragment delivery throughput of one of the servers triggers a process in which at least some of the other servers approximately immediately increase their fragment delivery throughput as a reaction to the fragment pull protocol, to compensate for the reduced throughput.

Claims

1. A distributed system comprising:

fractional-storage CDN servers configured to store erasure-coded fragments associated with segments of streaming contents;

each fractional-storage CDN server further configured to deliver fragments, essentially concurrently, at a certain fragment delivery throughput, to a plurality of assembling devices as replies to fragment pull protocol requests by the plurality of assembling devices, each fragment pull protocol request associated with a specific segment;

the a total outgoing bandwidth of the fractional-storage CDN servers divided by a number of the fractional-storage CDN servers is at least 100 times a total outgoing bandwidth of the plurality of assembling devices divided by a number of the plurality of assembling devices;

each fractional-storage CDN server further configured to store less than a minimum amount of erasure-coded fragments needed to decode the stored erasure-coded fragments;

wherein a reduction in the certain fragment delivery throughput of one of the fractional-storage CDN servers triggers a process in which other fractional-storage CDN servers increase their certain fragment delivery throughput as a reaction to the fragment pull protocol requests, to compensate for the reduced certain fragment delivery throughput; and

wherein the increased certain fragment delivery throughput on each of the other fractional-storage CDN servers as the reaction to the fragment pull protocol requests from a single assembling device is smaller than the certain fragent delivery throughput at which the fractional-storage CDN server already serves the plurality of devices with the erasure-coded fragments.

2. The distributed system of claim 1, wherein the triggered process comprises fractional-storage CDN servers receiving new requests for fragments, and the newly requested fragments compensate for fragments that failed to be delivered to assembling devices affected by the reduction.

3. The distributed system of claim 2, wherein the new requests for fragments are issued within 5 seconds of the reduction.

4. The distributed system of claim 2, wherein the new requests for fragments are addressed to fractional-storage CDN servers that have enough excess bandwidth to support the increased fragment delivery throughput.

5. The distributed system of claim 2, wherein the new requests for fragments are addressed to least loaded fractional-storage CDN servers.

6. The distributed system of claim 2, wherein the new requests for fragments are addressed to randomly selected fractional-storage CDN servers.

7. The distributed system of claim 2, wherein erasure-coding is rateless-coding.

8. The distributed system of claim 1, wherein each fractional-storage CDN server that increases its fragment delivery throughput stores at least one fragment associated with a segment whose fragments were not delivered due to the reduction.

9. The distributed system of claim 1, wherein the plurality of assembling devices include assembling devices that operate as end-user video streaming client devices, and erasure-coding is rateless-coding.

10. A method comprising:

pulling erasure-coded fragments associated with segments of streaming content from fractional-storage CDN servers by an assembling device, each fragment pull request associated with a specific segment, wherein a total outgoing bandwidth of the fractional-storage CDN servers divided by a number of the fractional-storage CDN servers is at least 100 times a total outgoing bandwidth of a plurality of assembling devices divided by a number of the plurality of the assembling devices, and wherein the assembling device is configured to pull fragments from at least two of the fractional-storage CDN servers to enable decoding of the pulled fragments;

while pulling the fragments, identifying a fractional-storage CDN server that has failed to respond with an erasure-coded fragment to at least one of the fragment pull requests;

thereafter, replacing, using the fragment pull protocol, the identified fractional-storage CDN server with a substitute fractional-storage CDN server storing relevant erasure-coded fragments, wherein the substitute server provides erasure-coded fragments to the plurality of assembling devices and has an outgoing bandwidth of at least 100 times the total outgoing bandwidth of the plurality of assembling devices divided by the number of the plurality of assembling devices; and

wherein replacing the fractional-storage CDN servers does not essentially affect an ongoing presentation of the streaming content by the pulling assembling device because of a high outgoing bandwidth of the substitute server.

11. The method of claim 10, wherein a fractional-storage CDN server that has not responded to a fragment request within a predetermined period of time is identified as a failing fractional-storage CDN server.

12. The method of claim 10, further comprising maintaining a list of substitute servers that are operative to replace the identified fractional-storage CDN servers, prior to the failure.

13. The method of claim 10, wherein the relevant erasure-coded fragments comprise erasure-coded fragments associated with a same segment as the erasure-coded fragments that were not delivered by the identified fractional-storage CDN server.

14. The method of claim 13, wherein the substitute server is not too loaded to provide the relevant erasure-coded fragments.

15. The method of claim 10, wherein erasure-coding is rateless-coding having a limitless redundancy factor above four, whereby a high redundancy creates a wide selection of fractional-storage CDN servers from which the assembling device can choose the substitute server.

16. A streaming system comprising:

a plurality of fractional-storage CDN servers accessed via public Internet, each configured to store erasure-coded fragments associated with segments of streaming contents but less than a minimum amount of the erasure-coded fragments needed to decode the stored erasure-coded fragments, and configured to serve a plurality of assembling devices essentially concurrently, wherein a total outgoing bandwidth of the fractional-storage CDN servers divided by a number of the fractional-storage CDN servers is at least 100 times a total outgoing bandwidth of the plurality of assembling devices divided by a number of the plurality of assembling devices;

a the plurality of assembling devices, each configured to pull the erasure-coded fragments from at least two of the plurality of fractional-storage CDN servers to enable decoding of the pulled erasure-coded fragments for video streaming purposes, and each fragment pull request being associated with a specific segment;

wherein the plurality of assembling devices are further configured to use the fragment pull requests, while retrieving the erasure-coded fragments, to replace a fractional-storage CDN server that is unable to maintain a desired level of fragment delivery with a substitute high-bandwidth server; and

an increased throughput on the substitute high-bandwidth server as a reaction to the fragment pull requests from a single assembling device is smaller than a throughput at which the substitute high-bandwidth server already serves the plurality of assembling devices with fragments, and therefore substantially does not affect the service provided to the already served plurality of assembling devices.

17. The streaming system of claim 16, wherein the plurality of assembling devices include assembling devices that operate as end-user video streaming client devices.

18. The streaming system of claim 17, wherein the substitute high-bandwidth server is one of least loaded servers, and the replacement occurs within 5 seconds.

19. The streaming system of claim 17, wherein the substitute high-bandwidth server is selected randomly from relevant fractional-storage CDN servers.