Methods and apparatus employing fec codes with permanent inactivation of symbols for encoding and decoding processes

A method of receiving data from a source, wherein the data is received at a destination over a packet communication channel, and wherein the data representable by a set of encoded symbols derived from an ordered set of source symbols representing the data sent from the source to the destination, the method comprising:

• obtaining the set of received encoded symbols;
• decoding a set of intermediate symbols from the set of received encoded symbols;
• associating each of the intermediate symbols with a set of intermediate symbols, wherein the intermediate symbols are associated into at least two sets, and wherein one set is designated as a set of permanently inactive symbols for purposes of scheduling a decoding process to recover the intermediate symbols from the received encoded symbols;
• and
• recovering at least some of the source symbols of the ordered set of source symbols from the set of intermediate symbols according to the decoding process.

A method for serving a file using a server coupled to a data network, wherein serving includes organizing data of the file into one or more blocks, generating one or more encoded symbols for a block based on the data of the block, and wherein at least one block is physically or logically organized into a plurality of sub-blocks and at least one encoded symbol is physically or logically organized into a plurality of sub-symbols, the method comprising:

• partitioning an input file into an integer number of blocks, wherein each block includes at least one sub-block, and wherein each sub-block includes at least one source symbol;
• determining a value, WS, representing a maximum size for a sub-block based on a memory constraint;
• determining a value SS, wherein SS*AL represents a lower bound for sub-symbol size, in units of a preferred memory unit size, AL;
• determining which blocks of the integer number of blocks is to be organized into a plurality of sub-blocks, and for each such block, organizing the block into a plurality of sub-blocks having a size determined by the available space within packets for encoded symbols that are to be sent, a symbol size that is to be used within each sent packet, in a manner to ensure that a number of source symbols for source blocks is equal within a threshold and the number is equal to the number, Kt, of source symbols in the file and to ensure that the sub-symbol size of each sub-block is at most SS*AL and to ensure that the size of each sub-block is at most WS;
• generating encoded symbols from blocks, wherein sub-symbols are generated from sub-blocks such that each encoded symbol depends on data from one block;
• and
• outputting the generated encoded symbols.

A method for recovering a block of data at a receiver using a client coupled to a data network, wherein a block includes a grouping of one or more sub-blocks, the method comprising:

• receiving a plurality of encoded symbols generated from the block, wherein each encoded symbol includes a plurality of sub-symbols generated from at least one sub-block using a common set of operations;
• determining a value, WS, representing a maximum size for a sub-block based on a memory constraint;
• determining a value SS, wherein SS*AL represents a lower bound for sub-symbol size, in units of a preferred memory unit size, AL;
• determining which blocks of the integer number of blocks organized into a plurality of sub-blocks, and for each such block, organizing the block into a plurality of sub-blocks having a size determined by a first parameter set by a sender representing available space within packets, a second parameter representing a symbol size used within each packet, the parameters being such that a number of source symbols for source blocks is equal within a threshold and the number is equal to the number, Kt, of source symbols in the file;
• decoding blocks from received encoded symbols, wherein sub-blocks are decoded from sub-symbols and the sub-blocks form blocks, wherein the sub-symbol size of each sub-block is at most SS*AL and the size of each sub-block is at most WS;
• and
• outputting the decoded blocks.