Random server selection for retrieving fragments under changing network conditions

• US 20100094973A1
• 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,819,260 B2
• Time in Patent Office: Days
• US Class Current: 709/219
• 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

An assembling device obtaining enough erasure-coded fragments from fractional-storage CDN servers for reconstructing a first set of segments including at least one segment. The communication between the assembling device and the servers is subject to at least one type of communication fault, and the assembling device handles the communication faults by approximately randomly selecting on-the-fly servers from which to obtain additional fragments instead of fragments that failed to be obtained.

Claims

1. ) A method for retrieving fragments, comprising:

attempting to retrieve from a plurality of fractional-storage CDN servers, using a fragment pull protocol, enough erasure-coded fragments to reconstruct a first set of segments comprising at least one segment;

approximately randomly selecting on-the-fly fractional-storage CDN servers; and

retrieving on-the-fly, from the randomly selected servers, additional erasure-coded fragments instead of the erasure-coded fragments that failed to be retrieved.

2. ) The method of claim 1, further comprising continuing retrieving fragments from the servers and the randomly selected servers until retrieving enough fragments to reconstruct the first set of segments, wherein the erasure-coded fragments support source-selection diversity.

3. ) The method of claim 1, wherein the erasure-coding is rateless-coding potentially resulting in fragments having a limitless redundancy factor.

4. ) The method of claim 1, wherein the randomly selected servers are servers from which fragments to reconstruct the first set of segments were not attempted to be retrieved.

5. ) The method of claim 1, wherein the randomly selected servers are selected from the entire pool of fractional-storage servers storing the relevant fragments.

6. ) The method of claim 1, further comprising retrieving fragments associated with a next set of segments from at least some of the servers from which fragments associated with the first set of segments were retrieved.

7. ) The method of claim 6, further comprising repairing a congested system condition by selecting servers to replace the servers from which fragments failed to be retrieved.

8. ) An apparatus comprising:

an assembling device configured to obtain enough erasure-coded fragments from fractional-storage CDN servers to reconstruct a first set of segments comprising at least one segment;

wherein the communication between the assembling device and the servers is subject to at least one type of communication fault, and the assembling device is configured to handle the communication faults by approximately randomly selecting on-the-fly servers from which to obtain additional fragments instead of fragments that failed to be obtained.

9. ) The apparatus of claim 8, wherein the assembling device is configured to obtain the fragments using a fragment pull protocol.

10. ) The apparatus of claim 9, wherein the communication fault comprises at least one server not responding to a fragment pull request, causing the assembling device to select another server instead of the non-responsive server.

11. ) The apparatus of claim 9, wherein the assembling device is further configured to retrieve fragments associated with a next set of segments from the responsive servers from which fragments associated with the first set of segments were retrieved, and the erasure-coded fragments support source-selection diversity.

12. ) The apparatus of claim 8, wherein the assembling device is configured to obtain the fragments via at least two sub-transmissions transmitted by the CDN servers.

13. ) The apparatus of claim 8, wherein the communication fault comprises an Internet packet loss condition, causing the assembling device to select at least one of the servers and issue requests for additional fragments;

whereby the average steady-state bandwidth of the transmitted fragments, including the fragments that fail to be obtained, increases approximately proportionally to the packet loss ratio.

14. ) The apparatus of claim 8, wherein the servers are deployed over multiple networks, and the communication fault comprises a failure of one of the networks causing related servers to be inaccessible;

whereby, the assembling device approximately randomly selects the servers from which to obtain the fragments until it communicates with enough accessible servers to reconstruct the first set of segments.

15. ) A system comprising:

assembling devices, and fractional-storage CDN servers configured to store erasure-coded fragments associated with approximately sequential segments of streaming content;

each assembling device is configured to obtain, approximately according to the sequential order of the segments, via the Internet from a sub-set of the servers, enough erasure-coded fragments to reconstruct segments;

wherein the communications between the assembling devices and the servers are subject to at least one type of communication fault, and the sub-sets of the servers are occasionally reselected approximately randomly, while obtaining the erasure-coded fragments associated with the streaming content, in order to handle the communication fault.

16. ) The system of claim 15, wherein the servers are deployed over multiple networks, and the assembling devices are configured to obtain the fragments using a fragment pull protocol.

17. ) The system of claim 16, wherein the communication fault comprises an Internet packet loss condition, the condition causes each affected assembling device to reselect at least one server to replace the server from which packets are lost, and issue requests for additional fragments to the reselected server.

18. ) The system of claim 16, wherein the communication fault comprises at least one server not responding to a fragment retrieval request, and the irresponsiveness causes each affected assembling device to select a server instead of the non-responsive server.

19. ) The system of claim 15, wherein the servers are located close to or on the Internet backbone, and the assembling devices are located at the user premises.

20. ) The system of claim 15, wherein at least one of the assembling devices is a proxy server configured to stream the reconstructed segments to its clients.