Encoding and decoding optimisations
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.
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.