Obtaining Erasure-Coded Fragments Using Push and Pull Protocols

• US 20100095184A1
• 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 7,822,856 B2
• Time in Patent Office: Days
• US Class Current: 714/751
• 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

Obtaining erasure-coded fragments using push and pull protocols, including the steps of receiving a first set of erasure-coded fragments associated with segments via a transmission using push protocol, whereby the first set is not sufficient for reconstructing some of the segments; and retrieving a second set of erasure-coded fragments using a fragment pull protocol, wherein the first and the second sets together are sufficient for reconstructing the segments.

Claims

1. A method comprising:

receiving a first set of erasure-coded fragments associated with segments via a transmission using push protocol, whereby the first set is not sufficient for reconstructing some of the segments; and

retrieving a second set of erasure-coded fragments using a fragment pull protocol;

wherein the first and the second sets together are sufficient for reconstructing the segments.

2. The method of claim 1, wherein the transmission is a broadcast transmission.

3. The method of claim 1, wherein the second set of fragments is retrieved from at least one fractional-storage CDN server.

4. The method of claim 3, wherein the first set of fragments is received from at least two fractional-storage CDN servers.

5. The method of claim 3, wherein the first set of fragments is received from at least one streaming server using an HTTP or an RTP session.

6. The method of claim 3, wherein at least a portion of the first set and at least a portion of the second set are obtained from the same server.

7. The method of claim 3, further comprising determining the magnitude of the second set based on the fragment loss associated with the transmission.

8. The method of claim 1, further comprising reconstructing the segments from the received and retrieved fragments, and starting to present the reconstructed segments while fragments are still being received and retrieved.

9. The method of claim 1, wherein the erasure-coded fragments are rateless-coded fragments associated with segments of streaming content, and the first set of rateless-coded fragments is transmitted according to the sequential order of the segments.

10. The method of claim 9, wherein the push protocol does not require a feedback channel from the receiver.

11. An apparatus comprising:

an assembling device configured to receive a first set of erasure-coded fragments from at least one server using a push protocol, wherein the first set is occasionally insufficient to decode the received fragments;

the assembling device is further configured to retrieve a second set of erasure-coded fragments using a fragment pull protocol;

wherein the first and second sets together comprise enough fragments to decode the fragments.

12. The apparatus of claim 11, wherein the erasure-coded fragments are associated with segments of streaming content, the fragments of the first set are transmitted approximately according to the sequential order of their associated segments, and the assembling device retrieves the second set of fragments from the at least one server.

13. The apparatus of claim 12, wherein the magnitude of the second set is based on the fragment loss associated with the transmission of the first set.

14. The apparatus of claim 11, wherein the fragments are associated with segments of streaming content, the fragments of the first set are transmitted approximately according to the sequential order of their associated segments, and the assembling device retrieves the second set of fragments from a fractional-storage server.

15. The apparatus of claim 14, wherein the fractional-storage server is a fractional-storage CDN server, and the erasure-coding is rateless-coding.

16. The apparatus of claim 14, wherein the first set is received via a broadcast or a multicast transmission.

17. The apparatus of claim 14, wherein the push protocol does not require a feedback channel from the receiver.

18. The apparatus of claim 14, wherein the first set is transmitted using a TCP/IP session or an RTP stream.

19. The apparatus of claim 14, wherein the first set is transmitted using at least one sub-transmission.

20. The apparatus of claim 14, wherein the magnitude of the second set is based on the fragment loss associated with the transmission of the first set.