Fault Tolerance in a Distributed Streaming System

• US 20100095013A1
• 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,774 B2
• Time in Patent Office: Days
• 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 server is further configured to deliver 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.

2. ) The distributed system of claim 1, wherein the triggered process comprises servers receiving new requests for fragments, to be delivered to requesting assembling devices affected by the reduction, instead of fragments that failed to be delivered due to the reduction.

3. ) The distributed system of claim 2, wherein approximately all of the new requests are issued within 5 seconds of the reduction.

4. ) The distributed system of claim 2, wherein the new requests for fragments are addressed to 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 the least loaded servers.

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

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

whereby a high redundancy enables a wide selection of servers from which the assembling devices can choose to request new fragments.

8. ) The distributed system of claim 1, wherein each server that immediately 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 reduction occurs as a result of one or more of the following:

a sudden drop in the fragment delivery bandwidth capability of at least one of the servers, a complete failure of at least one of the servers, and Internet congestion limiting the bandwidth capability of at least one of the servers.

10. ) The distributed system of claim 1, wherein at least most of the assembling devices are located at the user premises, and the erasure-coding is rateless-coding.

11. ) A method comprising:

while retrieving erasure-coded fragments associated with segments of streaming content, identifying a fractional-storage server that has failed to respond with an erasure-coded fragment to at least one fragment pull protocol request made by an assembling device; and

approximately immediately thereafter, replacing, using the fragment pull protocol, the identified server with a substitute server storing relevant erasure-coded fragments;

whereby replacing the servers does not affect an ongoing presentation of the streaming content by the retrieving assembling device.

12. ) The method of claim 11, wherein a server that has not responded to a fragment request within a predetermined period of time is identified as a failing server.

13. ) The method of claim 11, further comprising maintaining a list of substitute servers that can replace the identified servers, prior to the failure;

and the erasure-coded fragments support source-selection diversity.

14. ) The method of claim 11, wherein the relevant erasure-coded fragments comprise erasure-coded fragments associated with the same segment as the erasure-coded fragments that were not delivered by the identified server.

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

and the erasure-coded fragments support source-selection diversity.

16. ) The method of claim 11, wherein the erasure-coding is rateless-coding potentially resulting in fragments having a limitless redundancy factor, whereby a high redundancy creates a wide selection of servers from which the assembling device can choose the substitute server.

17. ) A streaming system comprising:

a plurality of fractional-storage CDN servers accessed via the public Internet, each configured to store erasure-coded fragments associated with segments of streaming contents; and

a plurality of assembling devices configured to use a fragment pull protocol to retrieve the fragments from the servers for streaming purposes, and further configured to use the fragment pull protocol, while retrieving the fragments, to replace a server that is unable to maintain a desired level of fragment delivery with a substitute server.

18. ) The streaming system of claim 17, wherein the assembling devices are located at the user premises.

19. ) The streaming system of claim 17, wherein the substitute server is approximately the least loaded server, and the replacement occurs within 5 seconds.

20. ) The streaming system of claim 17, wherein the substitute server is selected randomly from the relevant servers.