Methods and systems for fast segment reconstruction

• US 7,818,430 B2
• Filed: 10/14/2009
• Issued: 10/19/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,291
• Publication Number:
  US 20100094957A1
• Time in Patent Office: 370 Days
• Field of Search: 709/217, 709/218, 709/219, 709/223, 709/226, 709/230, 709/231
• 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

Fast segment reconstruction from erasure-coded fragments, including the steps of requesting, by an assembling device using a fragment pull protocol, from a plurality of fractional-storage servers, a first quantity of erasure-coded fragments associated with one or more segments of streaming content; the first quantity of fragments is requested approximately according to the sequential order of the segments, and the first quantity of fragments is more than the minimal quantity of fragments needed for reconstructing the one or more segments. And receiving, by the assembling device, a second decodable quantity of fragments as a response; whereby the second quantity of fragments may be smaller than the first quantity due to a failure condition.

Claims

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

requesting, by an assembling device using a fragment pull protocol, from a plurality of fractional-storage servers, a first quantity of erasure-coded fragments associated with one or more segments of streaming content;

the first quantity of fragments is more than the minimal quantity of fragments needed for reconstructing the one or more segments, and 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 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;

receiving as a response, by the assembling device from at least two of the fractional-storage servers, a second decodable quantity of fragments usable for reconstructing the one or more segments;

whereby the second quantity of fragments equals or lower than the first quantity due to a failure condition; and

repeating the step of requesting the fragments such that significantly more fragments associated with segments belonging to the beginning of the content are requested before fragments associated with segments belonging to the ending of the content.

2. The method of claim 1, further comprising adjusting to the first quantity to the failure condition.

3. The method of claim 1, wherein the erasure coding is rateless coding, and requesting the first quantity of fragments comprises requesting at least some of the requests essentially simultaneously.

4. The method of claim 1, further comprising determining the first quantity based on the failure condition, such that the second quantity of fragments is estimated to suffice for reconstructing the one or more segments.

5. The method of claim 4, wherein the fractional-storage servers are fractional-storage Content Delivery Network (CDN) servers, and further comprising requesting additional fragments when the second quantity of fragments is not enough for reconstructing the segments.

6. The method of claim 1, further comprising reconstructing the segments at a rate that at least allows continuous on-the-fly presentation of the streaming content on a display located at the user premises.

7. The method of claim 1, wherein the fragments are requested at a rate that enables a fragment reception rate higher than the average rate at which fragments are consumed in order to reconstruct and present the streaming content.

8. The method of claim 1, wherein the erasure coding is rateless coding, and the fractional-storage servers are fractional-storage Content Delivery Network (CDN) servers accessed via the public Internet.

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

requesting, essentially concurrently, by an assembling device using a fragment pull protocol, from a plurality of fractional-storage servers, a first set of erasure-coded fragments associated with at least one required segment of streaming content;

the first set contains more fragments than the minimal set of fragments needed to reconstruct the at least one required segment, and 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 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;

reconstructing the at least one required segment, by the assembling device, shortly after receiving enough of the first set fragments from at least two of the fractional-storage servers; and

making the streaming content available for presentation from the beginning of the at least one required segment onwards, shortly thereafter.

10. The method of claim 9, wherein requesting the first set of fragments further comprises indicating the need for fast response, and the servers respond to the indication by transmitting the fragments to the assembling device with priority.

11. The method of claim 9, wherein the fractional-storage servers are fractional-storage Content Delivery Network (CDN) servers accessed via the public Internet, and the at least one required segment comprises the beginning of the streaming content.

12. The method of claim 9, wherein the fractional-storage servers are fractional-storage Content Delivery Network (CDN) servers accessed via the public Internet, and further comprising selecting the at least one required segment using a trick play operation.

13. The method of claim 9, further comprising reconstructing additional sequential segments by requesting essentially the minimum set of fragments needed to reconstruct the additional segments, whereby the additional segments are reconstructed at a rate that at least allows continuous on-the-fly presentation of the streaming content.

14. The method of claim 9, further comprising determining the size of the first set of fragments based on fragment loss, such that the quantity of the received fragments is estimated to suffice for reconstructing the at least one segment.

15. The method of claim 14, wherein the erasure coding is rateless coding, and further comprising adjusting the first set to the fragment loss.

16. A distributed streaming system supporting short-delay presentation, comprising:

an assembling device configured to request, essentially concurrently, via a fragment pull protocol from a plurality of fractional-storage servers, a first set of erasure-coded fragments associated with at least one required segment of streaming content;

the first set is greater than the minimal set needed to reconstruct the at least one required segment, and 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 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;

the assembling device is further configured to reconstruct the at least one required segment after enough of the first set fragments have been received from at least two of the fractional-storage servers and before most of the segments following the required segment can be reconstructed, and to make the streaming content available for presentation from the beginning of the at least one required segment onwards shortly thereafter.

17. The distributed streaming system of claim 16, wherein the request comprises an indication for fast response, and the servers respond to the indication by transmitting the fragments to the assembling device with high priority.

18. The distributed streaming system of claim 16, wherein the fractional-storage servers are fractional-storage Content Delivery Network (CDN) servers accessed via the public Internet, and the at least one required segment is determined by a trick play operation.

19. The distributed streaming system of claim 16, wherein the assembling device is further configured to request essentially the minimal set of fragments needed to reconstruct additional sequential segments.

20. The distributed streaming system of claim 16, wherein the erasure coding is rateless coding, the servers are fractional-storage Content Delivery Network (CDN) servers accessed via the public Internet, and the assembling device is configured to determine the first set based on fragment loss, such that the set of received fragments is estimated to suffice for reconstructing the at least one segment.