Methods and systems for controlling fragment load on shared links

• US 8,949,449 B2
• Filed: 10/15/2009
• Issued: 02/03/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/580,104
• Publication Number:
  US 20100094950A1
• Time in Patent Office: 1,937 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

Controlling fragment load on shared links, including a large number of fractional-storage CDN servers storing erasure-coded fragments encoded with a redundancy factor greater than one from contents, and a large number of assembling devices configured to obtain the fragments from sub-sets of the servers. At least some of the servers share their Internet communication link with other Internet traffic, and the fragment traffic via the shared link is determined by the number of sub-sets in which the servers accessed via the shared link participate. Wherein the maximum number of sub-sets in which the servers accessed via the shared link are allowed to participate is approximately a decreasing function of the throughput of the other Internet traffic via the shared link.

Claims

1. A content delivery system, comprising:

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

wherein a fractional-storage CDN server is configured to store less than a minimum amount of data required to reconstruct the segments,

a large number of assembling devices configured to obtain the erasure-coded fragments from sub-sets of the fraction-storage CDN servers; and

at least one shared link operative to transport data traffic comprising erasure-coded fragment traffic generated by at least one of the fractional-storage CDN servers and other Internet traffic,

wherein the system is configured to utilize not more than a portion of the communication bandwidth of the shared link that is not in use by the other Internet traffic, by restricting the number of assembling devices concurrently served by the fractional-storage CDN server.

2. The content delivery system of claim 1, wherein the system comprises a plurality of shared links, and the system is further configured to increase the number of assembling devices concurrently served by the factional-storage CDN servers that communicate via shared links loaded to a lesser degree than other shared links.

3. The content delivery system of claim 1, wherein the system comprises a plurality of shared links spread over different time zones spanning at least three hours, and the loads of the other Internet traffic on the shared links are characterized by a change that is essentially a function of local time.

4. The content delivery system of claim 3, wherein the amount of erasure-coded fragment traffic approaches zero when the throughput of the other Internet traffic via the shared link exceeds a predetermined threshold.

5. The content delivery system of claim 2, wherein the fractional-storage CDN servers are configured to store enough of the erasure-coded fragments to have a redundancy factor >

1.5.

6. The content delivery system of claim 1, wherein at least some of the fractional-storage CDN servers are connected via different shared links and at least one of the shared links is used by an Internet hosting provider to provide Internet access to at least one of the fractional-storage CDN servers and to other Internet traffic.

7. The content delivery system of claim 1, wherein at least some of the fractional-storage CDN servers are connected via different shared links and at least one of the shared links is part of an Internet backbone network or tier one network used by an Internet backbone provider to provide Internet access to at least one of the fractional-storage CDN servers and to other Internet traffic.

8. The content delivery system of claim 7, wherein the other Internet traffic comprises general Internet traffic transported via the part of the Internet backbone network or tier one network, and the fractional-storage CDN servers are configured to store enough of the erasure-coded fragments to have a redundancy factor >

1.5.

9. The content delivery system of claim 1, wherein at least one of the fractional-storage CDN servers accessed via the shared link also hosts an application that generates at least some of the other Internet traffic transported over the shared link.

10. The content delivery system of claim 1, wherein, when the shared link is loaded below a first level, the system is further configured to increase the number of assembling devices concurrently served by the fractional-storage CDN servers accessed via the shared link in order to increase the fragment consumption from these servers, and when the shared link is loaded beyond a second level, the system is further configured to decrease the number of assembling devices concurrently served by the fractional-storage CDN servers accessed via the shared link.

11. The content delivery system of claim 10, further comprising an Internet bandwidth provider configured to operate the shared link.

12. The content delivery system of claim 10, wherein during a 24-hour period the load on the shared link changes to be below the first level and above the second level, and the second level is at least two times the first level.

13. The content delivery system of claim 1, wherein the assembling devices are further configured to obtain the erasure-coded fragments from the sub-sets of fractional-storage CDN servers using a fragment pull protocol, each fragment pull request associated with a specific segment.

14. The content delivery system of claim 1, wherein the system is further configured to receive an indication regarding the load on the shared link from an operator of the shared link, and to determine the number of the sub-sets of fractional-storage CDN servers based on that indication.

15. The content delivery system of claim 1, wherein the system is further configured to measure latency of responses from the fractional-storage CDN servers accessed via the shared link, and estimate load level on the shared link based on a variance in the measured latencies.

16. A system comprising:

a plurality of data centers;

fractional-storage CDN servers, hosted by the data centers, configured to store erasure-coded fragments associated with segments of contents, wherein a fractional-storage server is configured to store less than a minimum amount of data required to reconstruct the segments; and

shared links operative to connect the plurality of data centers to the Internet and transport the erasure-coded fragments in addition to other traffic not associated with the contents,

wherein the system is configured to prefer a selection of a fractional-storage CDN server communicating via a shared link having more unexploited bandwidth over a fractional-storage CDN server communicating via a shared link having less unexploited bandwidth, when selecting the fractional-storage CDN servers from which to obtain erasure-coded fragments and assuming both fractional-storage CDN servers have enough unexploited fragment delivery bandwidth and similar latencies.

17. The system of claim 16, wherein the erasure-coding is rateless-coding.

18. The system of claim 16, wherein the data centers are configured to provide information regarding the unexploited bandwidth of the shared link that is represented in bits per second or as a percentage value out of the shared link'"'"'s bandwidth capacity.

19. A method for selecting servers for communicating via shared links, comprising:

obtaining data regarding Internet traffic loads on shared links connecting to the Internet a plurality of fractional-storage CDN servers storing erasure-coded fragments associated with content, wherein the shared links transport the erasure-coded fragment traffic and other traffic; and

based on the obtained data, assigning a higher priority to a first fractional-storage CDN server connected to the Internet via a first shared link in relation to a second fractional-storage CDN server connected to the Internet via a second shared link having a high Internet traffic load compared to the first shared link and assuming the first and the second fractional-storage CDN servers have enough unexploited fragment delivery bandwidth and similar latencies.

20. The method of claim 19, wherein the erasure-coding is rateless-coding potentially resulting in erasure-coded fragments having a limitless redundancy factor >

4, and assembling devices obtain the erasure-coded fragments using a fragment pull protocol.