Adaptation of data centers' bandwidth contribution to distributed streaming operations

• US 7,822,869 B2
• Filed: 10/15/2009
• Issued: 10/26/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: Zuckerman, Gal, Thieberger, Gil
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Application Number:
  US12/580,205
• Publication Number:
  US 20100094975A1
• Time in Patent Office: 376 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

Adaptation of data centers'"'"' bandwidth contribution to distributed streaming operations, including data centers comprising fractional-storage CDN servers storing erasure-coded fragments encoded with a redundancy factor R greater than one, assembling devices obtaining the fragments from subsets of the servers, and measuring fragment delivery parameters, and at least one decision component that occasionally changes at least some of the servers of the subsets to generally improve the measured parameters. Wherein the smaller the number of subsets in which the servers of a data center participate, the lower the center'"'"'s fragment delivery throughput, the higher the center'"'"'s cost of delivering a fragment, and the higher the likelihood of reducing the amount of bandwidth acquired from that data center by the operator of the system.

Claims

1. A large scale system, comprising:

data centers comprising fractional-storage CDN servers, each server configured to store less than a minimum amount of data needed to decode its stored erasure-coded fragments;

assembling devices, each configured to obtain erasure-coded fragments from at least one nonempty subset of the servers, and to measure fragment delivery parameters; and

at least one decision component configured to generally improve the measured parameters by occasional change of at least some of the servers of the subsets associated with some of the assembling devices, wherein the occasional change comprises excluding underperforming servers from the subsets;

the system configured to exclude underperforming data center by monitoring the fragment-delivery bandwidth utilized by the servers of each data center, and to reduce the bandwidth available to the servers of a data center that was found to utilize less than a certain bandwidth level;

wherein the erasure-coding is rateless-coding enabling a redundancy factor greater than four;

the system comprises;

more than ten data centers scattered across a wide geographical area, more than one hundred servers, each configured to store less than one fifth the minimum amount fragments needed to decode the fragments, and more than ten thousand assembling devices located at user premises and configured to obtain the fragments from the servers via the Internet.

2. The large scale system of claim 1, wherein the measured fragment delivery parameters comprise at least one of the following:

latency in responding to data requests, variance in latency in responding to fragment requests, fragment loss, and service outage.

3. The large scale system of claim 2, wherein the assembling devices are configured to obtain the fragments using a fragment pull protocol that is used to estimate at least one of the parameters.

4. The large scale system of claim 1, wherein each assembling device comprises its decision component that is configured to occasionally change the servers in the assembling device'"'"'s subset.

5. The large scale system of claim 1, further comprising a control server comprising the decision component that is configured to occasionally change at least some of the servers of the subsets;

wherein the control server is configured to receive at least some of the measured fragment delivery parameters from the assembling devices.

6. The large scale system of claim 1, wherein the fragments are associated with segments of streaming contents, and the assembling devices are configured to obtain the fragments at rates facilitating presentation of the streaming contents.

7. The large scale system of claim 6, wherein the system configured to reduce the cost of the bandwidth available to the data centers by reducing the bandwidth available to data centers utilizing bandwidth below a certain level.

8. The large scale system of claim 6, wherein the system is further configured to exclude a data center having a cost of delivering a fragment above a certain level.

9. The large scale system of claim 6, wherein the erasure-coding is rateless-coding enabling a redundancy factor greater than four, and the measured fragment delivery parameters comprise reported load level encountered by the servers when delivering the fragments.

10. A large scale system, comprising:

data centers comprising fractional-storage CDN servers, each server configured to store less than a minimum amount of data needed to decode its stored erasure-coded fragments; and

assembling devices configured to obtain erasure-coded fragments from nonempty subsets of the servers;

the assembling devices are further configured to measure fragment delivery parameters;

the system configured to generally improve the measured parameters by occasional reselection of the servers of the subsets, wherein the occasional reselection comprises adding to the subsets servers having better fragment delivery parameters compared to the median performance of the servers in the subsets, whereby fragment delivery throughput from a data center is closely related to the number of subsets in which the servers of that data center participate;

the system is further configured to increase the fragment delivery bandwidth available to a data centers whose fragment delivery throughput approaches the center'"'"'s current fragment-delivery bandwidth availability; and

wherein the erasure-coding is rateless-coding enabling a redundancy factor greater than four;

the system comprises;

more than ten data centers spread across a wide geographical area, more than one hundred servers storing fragments with storage gain greater than five, and more than ten thousand assembling devices located at user premises and configured to obtain the fragments from the servers via the Internet.

11. The large scale system of claim 10, wherein the measured fragment delivery parameters comprise at least one of the following:

latency in responding to data requests, variance in latency in responding to fragment requests, fragment loss, and service outage.

12. The large scale system of claim 10, wherein at least one of the data centers is connected to the Interact via a high bandwidth fixed line having a certain fragment delivery capacity, and the system further configured to upgrade the capacity when the fragment delivery throughput from that center approaches the capacity of the fixed line.

13. The large scale system of claim 10, wherein at least one of the centers operative to provide Internet bandwidth services to multiple applications via a shared communication line, and the fragment delivery throughput in that center is limited to a capacity smaller than the bandwidth capacity of the shared line;

the system is further configured to enhanced the limited capacity when the fragment delivery throughput from the center approaches the limited capacity.

14. The large scale system of claim 10, wherein the fragments are associated with erasure-coded segments of streaming contents, and the assembling devices are configured to obtain the fragments at rates facilitating streaming of the contents.

15. The large scale system of claim 14, wherein the system is further configured to monitor the quality of the fragment delivery from at least one of the data centers, and to improve the quality by enhancing the bandwidth available to the center when the fragment delivery throughput approaches a level that lowers the quality.

16. The large scale system of claim 14, wherein the system is further configured to add to the system at least one other center located nearby when the fragment delivery throughput of a data center approaches its fragment delivery bandwidth availability.

17. The large scale system of claim 14, wherein the system is further configured to significantly reduce the bandwidth availability of a data center, when the fragment delivery throughput of the data center significantly decreases below its fragment delivery bandwidth availability.