Source-selection based Internet backbone traffic shaping

• US 20100094986A1
• Filed: 10/15/2009
• Published: 04/15/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: Thieberger, Gil, Zuckerman, Gal
• Granted Patent: US 8,832,292 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• 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:

several groups comprising fractional-storage CDN servers configured to store erasure-coded fragments associated with contents;

the groups are connected to the Internet via Internet backbone tier one networks, wherein not all groups are connected via the same networks; and

a very large number of assembling devices configured to obtain fragments from sub-sets of the servers;

wherein the system has a meaningful effect on the traffic transported via at least one Internet backbone tier one network by determining the sub-sets.

2. ) The content delivery system of claim 1, wherein by determining the sub-sets the system approximately avoids transporting fragments through at least one tier one network loaded above a predefined threshold.

3. ) The content delivery system of claim 1, wherein by determining the sub-sets the system shapes the fragment traffic via Internet backbone tier one networks, such that heavily loaded networks are less affected than less loaded networks by the fragment traffic.

4. ) The content delivery system of claim 3, wherein determining the sub-sets is done by assessing a large number of potential network paths that a fragment may follow from potential servers to potential assembling devices, and preferably selecting the servers estimated to deliver fragments along the less loaded paths.

5. ) The content delivery system of claim 1, wherein the assembling devices are configured to obtain a decodable number of the fragments from the sub-sets of the servers, and are further configured to decode the fragments;

and the erasure-coded fragments support source-selection diversity.

6. ) The content delivery system of claim 1, wherein the contents are streaming contents, the fragments are generated from approximately sequential segments of content, and 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 potentially resulting in a limitless redundancy factor;

whereby high redundancy provides greater freedom in selecting the servers from which to obtain the fragments, and therefore better control over the fragment flow paths.

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 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 from contents and support source-selection diversity.

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 network paths comprise many of the networks in the path of a fragment delivered from a server to the assembling device.

13. ) The method of claim 9, wherein the content is streaming content, the fragments are generated from approximately sequential segments of the content, and the fragments are delivered to the assembling device approximately according to the sequential order of the segments.

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 the storage gain of the servers in regard to an average content is at least 10.

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, whereby the higher the traffic load on the network the higher the cost is, and wherein the load on the network is provided by the network operator.

18. ) A content delivery system, comprising:

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

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

the assembling devices are configured to obtain fragments from the servers; and

the managing component is configured to significantly affect the fragment traffic transported via at least one Internet backbone router by influencing selections of fragment delivering servers.

19. ) The content delivery system of claim 18, wherein a managing server comprises the management component, and the higher the storage gain associated with the servers and the redundancy factor associated with the contents, the higher the degree of influence on the fragment traffic transported via the at least one Internet backbone router.

20. ) The content delivery system of claim 18, wherein the higher the storage gain associated with the servers and the redundancy factor associated with the contents, the higher the degree of influence on the fragment traffic transported via the at least one Internet backbone router, and by selecting which of the servers to use it is possible to approximately avoid transporting fragments via at least one Internet backbone router loaded beyond a certain level.