Reduction of peak-to-average traffic ratio in distributed streaming systems

• US 8,938,549 B2
• Filed: 10/15/2009
• Issued: 01/20/2015
• 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): Jaroenchonwanit, Bunjob
• Application Number:
  US12/579,774
• Publication Number:
  US 20100094969A1
• Time in Patent Office: 1,923 Days
• Field of Search: None
• 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

Reduction of peak-to-average traffic ratio in distributed streaming systems, including a large number of fractional-storage CDN servers accessed via the Internet, and storing erasure-coded fragments encoded with a redundancy factor greater than one from streaming contents, and a very large number of assembling devices obtaining the fragments from the servers in order to reconstruct the streaming contents. The assembling devices are spread over different time zones spanning at least three hours and balance the bandwidth load between the servers.

Claims

1. A streaming system comprising:

a plurality of fractional-storage CDN servers, configured to store erasure-coded fragments associated with streaming contents,

wherein a fractional-storage CDN server is configured to store less than a minimum amount of data required to decode the erasure-coded fragments; and

a plurality of assembling devices configured to obtain the erasure-coded fragments from subsets of the plurality of fractional-storage CDN servers, wherein;

the plurality of assembling devices are scattered over different time zones, and a subset of the plurality of fractional-storage CDN servers comprises less than all of the plurality of fractional-storage CND servers,

at peak times of a day of the most loaded time zone corresponding to the plurality of assembling devices, the plurality of assembling devices belonging to the most loaded time zone are configured to generate a content demand greater than a predefined percent of the total fragment delivery bandwidth available to the plurality of fractional-storage CDN servers, and

the plurality of assembling devices are further configured to generate a content demand greater than the predefined percent over a duration of at least two times the duration of the peak times of the most loaded time zone.

2. The streaming system of claim 1, wherein the plurality of assembling devices located at different time zones are configured to generate their daily peak streaming demand at different times.

3. The streaming system of claim 2, wherein the majority of the plurality of fractional-storage CDN servers are connected to the Internet via a plurality of guaranteed bandwidth connections having an aggregated bandwidth B.

4. The streaming system of claim 3, wherein the plurality of assembling devices are further configured to balance essentially any bandwidth load among the plurality of fractional-storage CDN servers, provided that the throughput at which the plurality of fractional-storage CDN servers provide erasure-coded fragments does not exceed B.

5. The streaming system of claim 3, wherein the streaming system is configured to increase the total amount of fragments transmitted during a day via the guaranteed bandwidth connections and decrease the peak to average streaming traffic ratio as the plurality of assembling devices are scattered over more time zones.

6. The streaming system of claim 3, wherein the streaming system is configured to have a peak to average streaming traffic ratio of the plurality of fractional-storage CDN servers essentially approaching one if the demand created by different assembling devices located around the globe is distributed essentially uniformly over the day.

7. The streaming system of claim 3, wherein the plurality of assembling devices are configured to balance the bandwidth load among the plurality of fractional-storage CDN servers by selecting from which fractional-storage CDN servers to obtain the erasure-coded fragments by themselves.

8. The streaming system of claim 2, wherein the plurality of assembling devices are configured to use a fragment pull protocol to control the obtained fragment rate.

9. The streaming system of claim 2, wherein the plurality of assembling devices are configured to obtain the erasure-coded fragments using multiple streams from multiple fractional-storage CDN servers, each stream containing a fraction of the fragments, and the erasure-coded fragments support source-selection diversity.

10. The streaming system of claim 2, wherein the plurality of fractional-storage CDN servers are located close to or on the Internet backbone, and the plurality of assembling devices are further configured to obtain the erasure-coded fragments from subsets of the plurality of fractional-storage CDN servers essentially regardless of distances between the plurality of fractional-storage CDN servers and the clients.

11. The streaming system of claim 2, wherein the plurality of assembling devices are located at user premises, and the erasure-coding is rateless coding.

12. The streaming system of claim 2, wherein the streaming contents comprise segments from which the fragments are encoded, and the plurality of assembling devices are configured to first obtain fragments associated with segments belonging to the beginning of the content.

13. The streaming system of claim 2, wherein the plurality of fractional-storage CDN servers are scattered over at least two continents, and some of the fractional-storage CDN servers located in different continents are configured to store erasure-coded fragments associated with the same contents.

14. A streaming system comprising:

a plurality of servers connected to the Internet via multiple connections having an aggregated outgoing fragment delivery bandwidth B, configured to individually store at least one erasure-coded fragment associated with segment of streaming content but less than a minimum amount of data needed to decode the stored fragments; and

a plurality of assembling devices scattered over different time zones, wherein;

the plurality of assembling devices are configured to pull the erasure-coded fragments from the plurality of servers, each fragment pull request is associated with a specific segment, and

the plurality of assembling devices are further configured to balance bandwidth load among the plurality of servers via the fragment pull requests as long as the resulting throughput at which the servers provide erasure-coded fragments does not exceed B.

15. The streaming system of claim 14, wherein the at least one of the plurality of assembling devices is further configured to request most of the time fragments having sizes for which the time to transmit each fragment in response to the assembling device request, through the slowest communication link connecting the responding server and the assembling device, is smaller than the round trip communication delay between the assembling device and the responding server, excluding the processing time of the responding server.

16. The streaming system of claim 14, wherein the streaming system is configured to increase the total amount of fragments transmitted during a day via the outgoing bandwidth connections and decrease the peak to average streaming traffic ratio as the plurality of assembling devices are scattered over more time zones.

17. A distributed streaming system, comprising:

servers connected to the Internet via connections having an aggregated outgoing fragment delivery bandwidth B, configured to;

individually store at least one erasure-coded fragment associated with segment of streaming content but less than a minimum amount of data needed to decode the stored fragments, and

deliver the stored fragments at a combined rate that approaches B, to a large number of recipients scattered over at least one continent,

wherein the system is configured to allow a recipient to receive erasure-coded fragments from servers located in different time-zones relative to the recipient, and

the system is further configured to achieve a daily peak to average streaming traffic ratio that is lower than the daily peak to average streaming traffic ratio generated by demand of recipients in a single time zone.

18. The distributed streaming system of claim 17, wherein the recipients are configured to control the received fragment rate and identity using a fragment pull protocol.

19. The distributed streaming system of claim 17, wherein the streaming contents comprise segments from which the fragments are encoded, and the recipients are configured to first obtain the erasure-coded fragments associated with segments belonging to the beginning of the contents.

20. The distributed streaming system of claim 17, wherein the servers are located dose to or on the Internet backbone, the recipients are located at user premises, and erasure coding is rateless coding.