Hybrid open-loop and closed-loop erasure-coded fragment retrieval process

• US 20100094959A1
• Filed: 10/14/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 7,844,712 B2
• Time in Patent Office: Days
• US Class Current: 709/219
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• 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

Retrieving erasure-coded fragments associated with approximately sequential segments, including the steps of requesting a first set of the fragments, using a fragment pull protocol, by an assembling device from a plurality of fractional-storage servers, and requesting a second set of erasure-coded fragments, using the fragment pull protocol, to compensate for the fragments of the first set that failed to arrive at the assembling device. And wherein while requesting the first-set fragments associated with a certain segment, at least one compensation request is made for a second-set fragment associated with a prior segment.

Claims

1. ) A method for retrieving erasure-coded fragments associated with approximately sequential segments, comprising:

requesting a first set of the erasure-coded fragments, using a fragment pull protocol, by an assembling device from a plurality of fractional-storage servers; and

requesting a second set of erasure-coded fragments, using the fragment pull protocol, to compensate for the fragments of the first-set that failed to arrive at the assembling device;

wherein while requesting the first set fragments associated with a certain segment, at least one compensation request is made for a second set fragment associated with a prior segment.

2. ) The method of claim 1, wherein requesting the first set of fragments comprises requesting the first set of fragments approximately according to the sequential order of the segments, whereby the segments belong to streaming content.

3. ) The method of claim 2, wherein requesting the second set of fragments comprises requesting the second set of fragments approximately according to the sequential order of the segments.

4. ) The method of claim 1, wherein the segments belong to streaming content, the assembling device is located at a user premises, and the servers are fractional-storage CDN servers.

5. ) The method of claim 4, further comprising reconstructing the segments and starting to present the streaming content while still requesting first set fragments associated with the streaming content.

6. ) The method of claim 1, wherein the segments belong to streaming content, and the requests for the fragments associated with the first set are issued regardless of the fragment loss.

7. ) The method of claim 6, further comprising determining the rate of requesting the first set of fragments approximately according to a target fragment-reception rate.

8. ) A method for retrieving erasure-coded fragments, comprising:

requesting, by an assembling device from a plurality of fractional-storage servers, erasure-coded fragments associated with approximately sequential segments of streaming content, using a fragment pull protocol;

wherein the fragments are requested in the following order;

first, at least one fragment associated with a certain segment is requested, then at least one fragment associated with a prior segment is requested, and then at least one additional fragment associated with the certain segment is requested.

9. ) The method of claim 8, wherein the at least one fragment associated with a prior segment is requested as a result of concluding that at least one prior request for a fragment associated with the prior segment has failed to result in a corresponding fragment reception.

10. ) The method of claim 9, wherein the fragments are requested at a rate higher than the rate needed to sustain continuous playing of the streaming content.

11. ) The method of claim 8, wherein the assembling device is located at a user premises, and further comprising reconstructing the segments, decoding the reconstructed segments, and starting to present the resulting streaming content before all of the segments of the streaming content are reconstructed.

12. ) The method of claim 8, wherein the fractional-storage servers are fractional-storage CDN servers, and the assembling device requesting the fragments over the Internet.

13. ) The method of claim 8, wherein the fragments that are associated with the certain segment are requested regardless of whether the requested fragments associated with the prior segment have been successfully received.

14. ) The method of claim 13, further comprising determining the rate of requesting the fragments associated with the certain segment approximately according to a target fragment-reception rate.

15. ) A device comprising:

a processor configured to operate a fragment pull protocol to request erasure-coded fragments associated with segments of streaming content from fractional-storage CDN servers; and

a buffer configured to store the received fragments;

the processor is further configured to detect fragments missing from the buffer, needed to reconstruct the segments;

wherein approximately simultaneous requests for missing fragments associated with two or more segments are allowed in order to prevent the missing fragments associated with one segment from delaying the retrieval of fragments associated with a later segment.

16. ) The device of claim 15, wherein the processor issues the fragment pull protocol requests at a rate that is determined approximately according to a target fragment-reception rate, and the fractional-storage CDN servers are located close to or on the Internet backbone.

17. ) The device of claim 15, wherein the device is located at a user premises and the fractional-storage CDN servers are located close to or on the Internet backbone.

18. ) The device of claim 15, wherein the device is configured to retrieve and store the fragments in the buffer at a rate higher than the rate needed to sustain continuous playing of the streaming content.

19. ) The device of claim 15, wherein the requests for missing fragments are intertwined in an approximately fixed rate stream of requests, such that some sequences of requests comprise requests for fragments associated with a specific segment, then one or more requests for fragments associated with a prior segment, and then additional requests for fragments associated with the specific segment.

20. ) The device of claim 15, wherein the processor is configured to request the fragments that are not the missing fragments approximately according to the sequential order of the segments with which the fragments are associated, whereby the resulting accumulation of fragments resembles the accumulation of data using progressive download.