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

• US 7,844,712 B2
• Filed: 10/14/2009
• Issued: 11/30/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: Zuckerman, Gal, Thieberger, Gil
• Primary Examiner(s): WANG, LIANG CHE A
• Application Number:
  US12/579,327
• Publication Number:
  US 20100094959A1
• Time in Patent Office: 412 Days
• Field of Search: 709/217, 709/218, 709/219, 709/223, 709/230, 709/231, 709/226
• US Class Current: 709/226
• 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 essentially sequential segments, comprising:

requesting, by an assembling device from a plurality of fractional-storage servers, a first set of the erasure-coded fragments, using a fragment pull protocol, each fragment pull request associated with a specific segment;

wherein erasure-coding denotes a process in which a sequence of erasure-coded fragments are generated from a segment such that the segment can be reconstructed from essentially any subset of the erasure-coded fragments having minimum size not smaller than the size of the segment;

wherein each fractional-storage server configured to store at least one erasure-coded fragment but less than the minimum amount of fragments or data required to reconstruct the segments;

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

while requesting the first set of fragments associated with a certain segment, requesting on-the-fly the second set of fragments associated with a prior segment, wherein the first set of fragments associated with the certain segment and the second set of fragments associated with the prior segment are of essentially the same erasure-coding and therefore can be decoded together.

2. The method of claim 1, wherein requesting the first set of fragments comprises requesting the first set of fragments essentially 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 essentially 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 Content Delivery Network (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 essentially 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 essentially sequential segments of streaming content, using a fragment pull protocol, each fragment pull request associated with a specific segment;

wherein erasure-coding denotes a process in which a sequence of erasure-coded fragments are generated from a segment such that the segment can be reconstructed from essentially any subset of the erasure-coded fragments having minimum size not smaller than the size of the segment;

wherein each fractional-storage server configured to store at least one erasure-coded fragment but less than the minimum amount of fragments or data required to reconstruct the segments;

wherein the fragments are requested, by the assembling device, in the following order;

first, requesting at least one fragment associated with a certain segment, then requesting on-the-fly at least one fragment associated with a prior segment, and then requesting at least one additional fragment associated with the certain segment, wherein the fragments associated with the certain segment and the fragments associated with the prior segment are of essentially the same erasure-coding and therefore can be decoded together.

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 Content Delivery Network (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 essentially 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 Content Delivery Network (CDN) servers, each fragment pull request associated with a specific segment; and

a buffer configured to store the received fragments;

wherein erasure-coding denotes a process in which a sequence of erasure-coded fragments are generated from a segment such that the segment can be reconstructed from essentially any subset of the erasure-coded fragments having minimum size not smaller than the size of the segment;

wherein each fractional-storage CDN server configured to store at least one erasure-coded fragment but less than the minimum amount of fragments or data required to reconstruct the segments;

the processor is further configured to detect fragments missing from the buffer and needed to reconstruct the segments, and then issue on-the-fly contiguous requests for missing fragments associated with two or more segments in order to prevent the missing fragments associated with one segment from delaying the retrieval of fragments associated with a later segment, wherein the missing fragments associated with the two or more segments are of essentially the same erasure-coding and therefore can be decoded together.

16. The device of claim 15, wherein the processor issues the fragment pull protocol requests at a rate that is determined essentially 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 essentially 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 essentially 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.