CONTENT DELIVERY SYSTEM WITH ALLOCATION OF SOURCE DATA AND REPAIR DATA AMONG HTTP SERVERS

• US 20130254631A1
• Filed: 07/31/2012
• Published: 09/26/2013
• Est. Priority Date: 08/19/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: LUBY, Michael George, GHOLMIEH, Ralph Akram, STOCKHAMMER, Thomas, LEUNG, Nikolai Konrad
• Granted Patent: US 9,015,564 B2
• Time in Patent Office: Days
• US Class Current: 714/776
• CPC Class Codes: H03M 13/356 Unequal error protection [UEP]
• 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: H03M 13/6306 Error control coding in combination with Automatic Repeat reQuest [ARQ] and diversity transmission, e.g. coding schemes for the multiple transmission of the same information or the transmission of incremental redundancy H03M13/3761, H03M13/3769 and H03M13/635 take precedence
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/1819 with retransmission of additional or different redundancy
• CPC Class Codes: H04L 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]

Abstract

Data objects are delivered over a packet-switched network and receivers receive encoded symbols, such as repair symbols, broadcast or multicast, with sufficient information to form requests for additional symbols as needed based on what source symbols or sub-symbols are needed or missing. The requests can be made in a unicast or request fashion. Requesting and broadcasting might be done by different entities. A broadcast server can generate and store repair symbols while a source server can store content in source form. A request can be a unicast HTTP byte-range request, such as a URL, starting position and length. Requests might be aligned with starting positions of files. A receiver can calculate starting and ending byte positions of symbols or sub-symbols in a file and get indications that conventional HTTP servers are usable for file repair. Repair servers can request broadcast of repair data when byte-range requests from multiple receivers overlap.

Claims

1. A method of receiving one or more data objects using an electronic device or system coupled to a packet-switched network, wherein source data of the one or more data objects is represented by encoded symbols in packets such that the source data is recoverable, at least approximately, from the encoded symbols, the method comprising:

a) receiving encoded symbols via a broadcast channel, wherein values of encoded symbols are derived, at least in part, from values of source symbols;

b) determining a number of additional symbols needed to recover content to a desired level of completeness;

c) determining a corresponding set of one or more byte ranges of one or more files, wherein the corresponding set corresponds to the additional symbols needed to recover the content;

d) generating a request for at least the number of additional symbols, using a request directed to a server specifying the corresponding set of one or more byte ranges;

e) sending the request;

f) receiving at least some of the requested additional symbols; and

g) using the received additional symbols in combination with the encoded symbols received over the broadcast channel in recovering the content.

2. The method of claim 1, wherein the desired level of completeness is complete recovery of the content.

3. The method of claim 1, wherein the request is an HTTP byte-range requests and at least one request of a plurality of requests is an HTTP byte-range request is for a noncontiguous byte range.

4. The method of claim 1, wherein the request is for a contiguous set of additional symbols.

5. The method of claim 4, wherein the contiguous set of additional symbols starts with a source symbol that is the same starting symbol for each of a plurality of devices that receive content remotely.

6. The method of claim 1, wherein the request is a unicast HTTP byte-range request.

7. The method of claim 1, wherein the additional symbols are source symbols.

8. The method of claim 1, wherein the additional symbols are source symbols and repair symbols.

9. The method of claim 1, wherein the encoded symbols are all repair symbols and the additional symbols are all source symbols.

10. The method of claim 1, wherein the source data comprises an organized set of source blocks of source symbols and is further organized into sets of source sub-blocks and source sub-symbols.

11. The method of claim 10, wherein the request is for byte ranges of sub-symbols.

12. The method of claim 10, wherein the request is for a contiguous set of additional sub-symbols.

13. The method of claim 12, wherein the contiguous set starts with a source sub-symbol that is the same starting sub-symbol for each of a plurality of devices that receive content remotely.

14. The method of claim 10, wherein the request is for source sub-symbols.

15. The method of claim 10, wherein the request is for source sub-symbols and repair sub-symbols.

16. A device that presents content received remotely, comprising:

an electronic interface to receive data from a broadcast channel;

logic for receiving encoded symbols via the broadcast channel, wherein values of encoded symbols are derived, at least in part, from values of source symbols corresponding to the content to be received remotely;

logic for determining a number of additional symbols needed to recover content to a desired level of completeness;

logic for determining a corresponding set of one or more byte ranges of one or more files, wherein the corresponding set corresponds to the additional symbols needed to recover the content;

logic for generating a request for at least the number of additional symbols, using a request directed to a server specifying the corresponding set of one or more byte ranges;

an interface for sending the request;

logic for receiving at least some of the requested additional symbols; and

a decoder that uses the received additional symbols in combination with the encoded symbols received over the broadcast channel in recovering the content.

17. The device of claim 16, wherein the desired level of completeness is complete recovery of the content.

18. The device of claim 16, wherein the request is an HTTP byte-range requests and at least one request of a plurality of requests is an HTTP byte-range request is for a noncontiguous byte range.

19. The device of claim 16, wherein the request is for a contiguous set of additional symbols.

20. The device of claim 19, wherein the contiguous set of additional symbols starts with a source symbol that is the same starting symbol for each of a plurality of devices that receive content remotely.

21. The device of claim 16, wherein the additional symbols are source symbols.

22. The device of claim 16, wherein the additional symbols are source symbols and repair symbols.

23. The device of claim 16, wherein the encoded symbols are all repair symbols and the additional symbols are all source symbols.

24. The device of claim 16, wherein the source data comprises an organized set of source blocks of source symbols and is further organized into sets of source sub-blocks and source sub-symbols.

25. The device of claim 16, wherein the request is for byte ranges of sub-symbols.

26. The device of claim 16, wherein the request is for a contiguous set of additional sub-symbols.

27. The device of claim 26, wherein the contiguous set starts with a source sub-symbol that is the same starting sub-symbol for each of a plurality of devices that receive content remotely.

28. The device of claim 16, wherein the request is for source sub-symbols.

29. The device of claim 16, wherein the request is for source sub-symbols and repair sub-symbols.

30. The device of claim 16, further comprising logic for receiving from the network an indication of whether HTTP byte-range requests are supported by file servers.

31. The device of claim 16, further comprising logic for receiving from the network an indication of which servers support which formats.

32. The device of claim 31, further comprising logic for receiving from the network indications of a prioritization of which servers the device should attempt to make requests from.

33. The device of claim 16, further comprising logic for receiving preferences or requirements indicating which request formats to use when more than one is supported by the device.

34. The device of claim 16, further comprising logic for receiving an indication that only repair symbols are broadcast to the device.

35. The device of claim 34, wherein the device is constrained to always use prefix requests for additional data when receiving the indication.

36. The device of claim 16, further comprising logic for receiving an indication requiring that the device use prefix requests for additional data.

37. The device of claim 16, further comprising logic for calculating a starting byte position in a file of a symbol or sub-symbol and an ending byte position in the file of the symbol or sub-symbol.

38. A method of delivering one or more data objects from an electronic device or system over a packet-switched network, wherein source data of the one or more data objects is represented by encoded symbols in packets such that the source data is recoverable, at least approximately, from the encoded symbols, the method comprising:

a) if the source data is not already organized into source blocks of source symbols, organizing the source data into an organized set of source blocks of source symbols;

b) generating encoded symbols, wherein values of encoded symbols are derived, at least in part, from values of source symbols and wherein encoded symbols that are repair symbols have scopes used for generation that correspond with source blocks; and

c) providing repair symbols and/or source symbols as encoded symbols in a broadcast fashion to destination devices, wherein broadcasting provides sufficient information for a destination device to determine symbol and block structure for broadcasted data,

wherein the sufficient information comprises at least information mapping source symbols in the organized set of source blocks of source symbols to byte ranges usable for making byte range requests from a server supporting file requests with byte range requests.

39. The method of claim 38, further comprising:

d) determining, at the destination device, which source symbols are not decodable from the received broadcast symbols;

e) determining, at the destination device, a set of one or more byte ranges of a file that is requestable using a file request with a byte range qualifier; and

f) making the file request with the byte range qualifier.

40. The method of claim 38, wherein the file requests are HTTP client requests comprising a URL and a byte range.

41. The method of claim 40, wherein the byte range begins at the start of the file being requested.

42. The method of claim 38, further comprising:

d) determining from a received request whether the received request is in response to a repair process to recover for missing repair symbols derived from a broadcast process;

e) determining from the received request whether the received request is in response to a direct request from a client unrelated to a broadcast process; and

f) recording determination results.

43. The method of claim 42, wherein determining is performed by reading all or part of a URL used in the received request.

44. The method of claim 38, wherein the organized set of source blocks of source symbols is further organized into sets of source sub-blocks and source sub-symbols.

45. A non-transitory computer program product for receiving one or more data objects using an electronic device or system coupled to a packet-switched network, wherein source data of the one or more data objects is represented by encoded symbols in packets such that the source data is recoverable, at least approximately, from the encoded symbols, the product comprising:

a) program code for receiving encoded symbols via a broadcast channel, wherein values of encoded symbols are derived, at least in part, from values of source symbols;

b) program code for determining a number of additional symbols needed to recover content to a desired level of completeness;

c) program code for determining a corresponding set of one or more byte ranges of one or more files, wherein the corresponding set corresponds to the additional symbols needed to recover the content;

d) program code for generating a request for at least the number of additional symbols, using a request directed to a server specifying the corresponding set of one or more byte ranges;

e) program code for sending the request to the server;

f) program code for receiving at least some of the requested additional symbols; and

g) program code for recovering the content using the received additional symbols in combination with the encoded symbols received over the broadcast channel.

46. The product of claim 45, wherein the desired level of completeness is complete recovery of the content.

47. The product of claim 45, wherein the request is an HTTP byte-range requests and at least one request of a plurality of requests is an HTTP byte-range request is for a noncontiguous byte range.

48. The product of claim 45, wherein the request is for a contiguous set of additional symbols.

49. The product of claim 48, wherein the contiguous set of additional symbols starts with a source symbol that is the same starting symbol for each of a plurality of devices that receive content remotely.

50. The product of claim 45, wherein the encoded symbols are all repair symbols and the additional symbols are all source symbols.

51. The product of claim 45, wherein the source data comprises an organized set of source blocks of source symbols and is further organized into sets of source sub-blocks and source sub-symbols.

52. The product of claim 51, wherein the request is for a contiguous set of additional sub-symbols.

53. The product of claim 52, wherein the contiguous set starts with a source sub-symbol that is the same starting sub-symbol for each of a plurality of devices that receive content remotely.