Encoding and decoding optimisations

Patent metadata

Field	Value
Publication number	US-9729624-B2
Application number	US-9798006-A
Country	US
Kind code	B2
Filing date	Dec 4, 2006
Priority date	Dec 22, 2005
Publication date	Aug 8, 2017
Grant date	Aug 8, 2017

Abstract

The invention provides methods of encoding content for distribution over a network and methods for decoding encoded content which has been distributed over the network. In a first example in which the content is divided into a plurality of segments and each segment comprising a plurality of blocks of data, the method comprises selecting a segment from the plurality of segments and selecting at least two blocks of the selected segment from a store of blocks. A new encoded block is created from a linear combination of the selected blocks.

First claim

The invention claimed is:

1. A method comprising:
encoding content for distribution over a network, the content being divided into a plurality of segments and each segment comprising a plurality of un-encoded blocks of data, wherein encoding content for distribution over the network comprises:
selecting a segment from the plurality of segments stored in memory;
selecting a target degree for a new encoded block, wherein a degree of an encoded block is a quantity of un-encoded blocks that correspond to the encoded block;
selecting, from a store of previously-encoded blocks, at least two previously-encoded blocks corresponding to the selected segment, wherein each of the at least two previously-encoded blocks has a degree less than or equal to the target degree; and
creating the new encoded block having a degree equal to the target degree from a linear combination of the selected at least two previously-encoded blocks using a processor.

2. A method according to claim 1 , wherein selecting a segment comprises an infrequent but periodic step of selecting all of the plurality of segments.

3. A method according to claim 1 , wherein selecting a segment comprises:
randomly selecting a segment from the plurality of segments.

4. A method according to claim 1 , wherein selecting a segment comprises:
selecting a segment from the plurality of segments according to a specified sequence.

5. A method according to claim 1 , wherein selecting at least two previously-encoded blocks comprises: selecting all available previously-encoded blocks of the selected segment from a store of encoded blocks.

6. A method according to claim 1 , further comprising:
storing the new encoded block.

7. A method according to claim 6 , wherein creating a new encoded block uses a pre-computed look up table.

8. A method according to claim 1 , wherein the content comprises a software update file, and the software update file is to be distributed over the network.

9. A method according to claim 8 , wherein the software update file is to be distributed to nodes in the network.

10. A method according to claim 1 , wherein the content comprises a patch file to be distributed over the network.

11. One or more computer-readable memory to store executable instructions, when the executable instructions are executed by a processor, the processor implements acts for encoding content for distribution over a network, the content being divided into a plurality of un-encoded blocks of data, the acts comprising:
selecting a target degree for a new encoded block, wherein a degree of an encoded block is a number of un-encoded blocks corresponding to the encoded block;
attempting to select a plurality of previously-encoded blocks from a store of previously-encoded blocks to create the new encoded block, the new encoded block and each selected previously-encoded block having a degree which is less than or equal to the target degree;
increasing, if the attempt fails, the target degree by one and repeating the attempting step; and
creating, if the attempt succeeds, the new encoded block from a linear combination of the selected plurality of previously-encoded blocks.

12. The computer-readable memory according to claim 11 , wherein the selected plurality of previously-encoded blocks comprises a maximum number of previously-encoded blocks from which the new encoded block can be created.

13. The computer-readable memory according to claim 12 , the acts further comprising:
storing the new encoded block.

14. The computer-readable memory according to claim 13 , wherein creating the new encoded block uses a pre-computed look up table.

15. A method of encoding content for distribution over a network, the content being divided into a plurality of un-encoded blocks of data, the method comprising:
selecting a plurality of encoded blocks from a store of encoded blocks in the network, each encoded block having a degree that is less than or equal to a target degree, the degree being a number of un-encoded blocks from which each of the encoded blocks are created;
creating a new encoded block from a linear combination of the selected plurality of encoded blocks; and
storing the new encoded block in memory.

16. A method according to claim 15 , wherein the new encoded block is stored in a cache.

17. A method according to claim 16 , wherein storing comprises:
storing the new encoded block for a predetermined period of time.

18. A method according to claim 17 , wherein the store of encoded blocks comprises a first part located in a main memory of a node and a second part located in a cache of the node.

19. A method according to claim 18 , wherein creating the new encoded block uses a pre-computed look up table.

Assignees

• Gkantsidis Christos
• Miller John
• Costa Manuel
• Rodriguez Pablo
• Ranson Stuart
• Microsoft Technology Licensing Llc

Inventors

• Gkantsidis Christos
• Miller John
• Costa Manuel
• Rodriguez Pablo
• Ranson Stuart

Classifications

• H04L67/104 Primary

  Peer-to-peer [P2P] networks · CPC title

• H03M13/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 title

• H04L67/108

  characterised by resources being split in blocks or fragments · CPC title

• H04L67/1076

  Resource dissemination mechanisms or network resource keeping policies for optimal resource availability in the overlay network · CPC title

• H04N19/184 Primary

  the unit being bits, e.g. of the compressed video stream · CPC title