Source-selection based internet backbone traffic shaping

• US 8,832,292 B2
• Filed: 10/15/2009
• Issued: 09/09/2014
• 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,129
• Publication Number:
  US 20100094986A1
• Time in Patent Office: 1,790 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

Source-selection based Internet backbone traffic shaping, including the steps of assessing a large number of network paths through which erasure-coded fragments usually flow when transmitted from a large number of relevant fractional-storage CDN servers to an assembling device; accessing preferences for fragment delivery via many of the paths; and selecting the servers whose assessed paths fit well the preferences for fragment delivery to the assembling device. Wherein the servers are accessed via the Internet, not all servers are connected to the Internet via the same networks, and the erasure-coded fragments are encoded with a redundancy factor greater than one from contents.

Claims

1. A content delivery system, comprising:

a plurality of N fractional-storage CDN servers scattered over at least one continent, the servers configured to store erasure-coded fragments associated with segments of streaming contents, and to communicate with assembling devices via a plurality of tier one Internet networks; and

a plurality of assembling devices, each device configured to obtain at least some of the erasure-coded fragments operative to reconstruct at least one of the segments, from a combination of servers comprising less than the N fractional-storage CDN servers;

the system configured to reduce the volume of the fragments obtained via at least one of the tier one Internet networks, by changing the server combinations of at least some of the assembling devices, to include less servers having a server-to-assembling device fragment delivery path comprising the tier one Internet network.

2. The content delivery system of claim 1, wherein the system is further configured to substantially avoid obtaining fragments via one of the tier one Internet networks by changing the server combinations of the assembling devices to substantially not include servers having a server-to-assembling device fragment delivery path comprising the at least one tier one Internet network.

3. The content delivery system of claim 1, wherein each of the plurality of N fractional-storage CDN servers is configured to store less than the minimum amount of erasure-coded fragments required to decode the fragments, and

the system is further configured to select the server combinations, such that server combination stores an amount of erasure-coded fragments operative to decode the fragments.

4. The content delivery system of claim 3, wherein selecting the combinations is done by assessing a plurality of network paths through which fragments follow when transmitted by the servers to the assembling devices, and selecting the servers estimated to deliver fragments along paths not comprising the at least one Internet tier one network.

5. The content delivery system of claim 4, wherein the erasure-coded fragments support source-selection diversity.

6. The content delivery system of claim 1, wherein the assembling devices are located at the user premises and are configured to reconstruct streams from the obtained fragments.

7. The content delivery system of claim 1, wherein the erasure-coding is rateless-coding resulting in a redundancy factor >

4.

8. The content delivery system of claim 1, wherein the assembling devices are configured to use a fragment pull protocol to obtain the fragments.

9. A method for shaping traffic, comprising:

assessing a plurality of network paths through which erasure-coded fragments associated with segments of streaming content flow when transmitted from a plurality of fractional-storage CDN servers to an assembling device;

accessing preferences associated with using the assessed paths;

selecting the servers whose assessed paths fit well the preferences as the sources from which the fragments are transmitted to the assembling device; and

obtaining, by the assembling device, at least some of the erasure coded fragments operative to reconstruct the segments from the selected serves.

10. The method of claim 9, wherein at least some of the servers are connected to the Internet via Internet backbone tier one networks.

11. The method of claim 10, wherein the network paths consist essentially of tier one networks.

12. The method of claim 9, wherein the erasure-coding is rateless-coding.

13. The method of claim 9, wherein the fragments associated with segments belonging to the beginning of the contents are delivered to the assembling device first.

14. The method of claim 9, wherein the number of network paths is at least 10, the number of relevant servers is at least 20, and each of the servers stores less than one tenth of the quantity of fragments needed to decode the fragments.

15. The method of claim 9, wherein the preferences are a cost function, and the step of selecting the servers comprises minimizing the cost function by determining which servers are to deliver fragments to the assembling device.

16. The method of claim 9, wherein the preferences for selecting a network path are based on the accumulated costs of using the networks through which the path passes, whereby a lower accumulated cost results in a higher preference for the path.

17. The method of claim 16, wherein the cost of delivering fragments via a network is related to the traffic load on the network, and load on the network is provided by the network operator.

18. A content delivery system, comprising:

a plurality of fractional-storage CDN servers, assembling devices, and a managing component;

the servers are topologically scattered across different Internet networks and are configured to store erasure-coded fragments associated with contents;

each of the assembling devices configured to gather fragments and to decode content from a combination of selected servers comprising less than the plurality of servers; and

the managing component configured to control the fragment traffic transported via at least one Internet backbone router participating in transporting at least some of the fragments from servers to the assembling devices, by influencing at least some of the selections made for the combination of servers, such that when the fragment traffic is above a certain level, the managing component is configured to cause at least some assembling devices to stop obtaining fragments from servers having a server-to-assembling device fragment delivery path comprising the at least one router.

19. The content delivery system of claim 18, wherein a managing server comprises the management component, each of the fractional-storage CDN servers is configured to store less than the minimum amount of erasure-coded fragments required to decode the fragments, and the selections of server combinations are done such as to aggregate a number of servers per combination together storing an amount of fragments operative to decode the fragments into content.

20. The content delivery system of claim 18, wherein each of the fractional-storage CDN servers is configured to store less than the minimum amount of erasure-coded fragments required to decode the fragments, and selecting the combinations of servers is done as to avoid transporting fragments via at least one Internet backbone router loaded beyond a certain level.