Peer-assisted fractional-storage streaming servers

• US 20110055420A1
• Filed: 11/10/2010
• Published: 03/03/2011
• 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,832,295 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

A system including a plurality of fractional-storage servers and a plurality of peer-to-peer devices. Substantially each of the servers and peer-to-peer devices stores less than a minimum amount of erasure-coded fragments needed to decode segments of streaming content. The system delivers at least the minimum amount of erasure-coded fragments needed to decode the segments of streaming content, from any group of the servers, or group of the servers plus peer-to-peer devices, that together store at least the minimum amount of erasure-coded fragments needed to decode the segments of streaming content. Optionally, the system supplements streaming capabilities of the servers during peak traffic periods by sending erasure-coded fragments stored on the peer-to-peer devices during the peak traffic periods.

Claims

1. ) A system comprising:

a plurality of fractional-storage CDN servers connected to the Internet via fixed bandwidth lines, and a plurality of peer-to-peer devices connected to the Internet via Internet service providers (ISP);

substantially each server and peer-to-peer device configured to store less than a minimum amount of erasure-coded fragments needed to decode segments of streaming content; and

the system is configured to deliver at least the minimum amount of erasure-coded fragments needed to decode the segments of streaming content from various combinations of the servers and the peer-to-peer devices that together store at least the minimum amount of erasure-coded fragments needed to decode the segments of streaming content;

wherein during periods that fragment delivery bandwidth demand is higher than the total fragment delivery bandwidth of the fixed bandwidth lines, the peer-to-peer devices are configured to use bandwidth of the ISP to deliver fragments in addition to fragments delivered by the servers, and by that supplementing the fragment delivery bandwidth of the fixed bandwidth lines.

2. ) The system of claim 1, wherein the peer-to-peer devices are used mainly to supplement the streaming capabilities of the servers during peak traffic periods and the erasure-coding is rateless-coding.

3. ) The system of claim 1, wherein the bandwidth utilized to obtain the fragments associated with a content file approaches the aggregated fragment delivery bandwidth of the servers and the peer-to-peer devices on which the fragments associated with the content file are stored.

4. ) The system of claim 1, wherein the streaming content comprises segments, and the system further comprises assembling devices configured to request decodable sets of fragments from the servers, and upon failure or an estimated failure to obtain requested fragments, obtain the additionally needed fragments from one or more of the peer-to-peer devices.

5. ) The system of claim 1, wherein the erasure-coding is rateless-coding, and the system further comprises assembling devices configured to receive an indication whether to use the peer-to-peer devices as additional fragment sources to the servers.

6. ) The system of claim 1, further comprising assembling devices configured to obtain the stored fragments using a fragment pull protocol.

7. ) The system of claim 1, wherein the erasure-coding is rateless-coding, and further comprising assembling devices configured to obtain the stored fragments using a plurality of transmissions, each comprising a fraction of the erasure coded fragments needed to decode the fragments.

8. ) The system of claim 1, wherein the erasure-coding is rateless-coding, and the peer-to-peer devices are configured to store substantially more unique erasure-coded fragments than the serves.

9. ) The system of claim 1, wherein the peer-to-peer devices are located at the user premises, and the erasure-coding is rateless-coding.

10. ) A distributed streaming system, comprising:

fractional-storage CDN servers and user premises peer-to-peer devices configured to receive and store a first and a second corresponding portions of erasure-coded fragments encoded from segments of streaming content, shortly after the segments are progressively made available by a streaming source;

each of most of the servers and the peer-to-peer devices is configured to receive less than the minimum amount of erasure-coded fragments needed to decode the received fragments;

the system configured to deliver sets of fragments usable to decode the fragments associated with the segments, from combinations of servers and peer-to-peer devices storing fragments associated with the segments, shortly after the segments are made available by the streaming source and while still receiving following fragments associated with the streaming content.

11. ) The distributed streaming system of claim 10, wherein the second portion is substantially larger than the first portion, and the first portion comprises enough fragments to reconstruct the streaming content.

12. ) The distributed streaming system of claim 11, further comprising assembling devices configured to request the sets of fragments from the servers, and upon failure or an estimated failure to obtain requested fragments, obtain the additionally needed fragments from one or more of the peer-to-peer devices;

wherein decodable sets of fragments associated with the segments are obtained from combinations of the servers and the peer-to-peer devices storing fragments associated with the segments.

13. ) The distributed streaming system of claim 11, wherein the erasure-coding is rateless-coding, decodable sets of fragments associated with the segments are obtained from combinations of the servers and the peer-to-peer devices storing fragments associated with the segments, and further comprising assembling devices configured to receive an indication whether to use the peer-to-peer devices as additional fragment sources to the servers.

14. ) The distributed streaming system of claim 10, wherein the erasure-coding is rateless-coding, and the first and the second portions comprise unique rateless-coded fragments encoded with a redundancy factor >

10 from the segments.

15. ) The distributed streaming system of claim 10, wherein the erasure-coding is rateless-coding, and the first and the second portions comprise unique rateless-coded fragments encoded with a redundancy factor that is determined according to the estimated popularity of the content being encoded, whereby the higher the popularity of the content, the higher the redundancy factor used to encode the content into fragments, and the larger the number of peer-to-peer devices that store the fragments associated with the content.

16. ) The distributed streaming system of claim 10, further comprising assembling devices configured to obtain the fragments using a fragment pull protocol, whereby the pull protocol fragment requests are issued at a rate that enables real-time presentation of the segments.

17. ) A distributed system comprising:

fractional-storage CDN servers configured to store a first portion of erasure-coded fragments; and

a large number of peer-to-peer bandwidth amplification devices configured to store a second portion of the erasure-coded fragments;

each server and device configured to store less than the minimum amount of fragments needed to decode the fragments; and

when operated in high load, the system configured to deliver to assembling devices sets of fragments belonging to both the first and the second portions, while the second portion fragments obtained predominantly from peer-to-peer devices whose ISP'"'"'s communication lines are estimated not to be overloaded.

18. ) The distributed system of claim 17, wherein the erasure-coding is rateless-coding, the peer-to-peer devices are scattered over different time zones spanning at least three hours, and the second portion fragments are obtained predominantly from peer-to-peer devices located in time zones where the Internet traffic generated does not approach a local peak.

19. ) The distributed system of claim 18, wherein the assembling devices configured to obtain the fragments from the peer-to-peer devices using a fragment pull protocol for high latency.

20. ) The distributed system of claim 18, wherein the fragments are encoded from segments of streaming contents, and the assembling devices configured to obtain the fragments associated with the initial segments of the streaming content before other segments.