Menu

PML: FEC Encoding and decoding

PML uses UDP multicast packets to distribute resources from a single sender to a (potentially very large) group of receivers. The receivers provide no feedback to the sender whether they have received all the packets or not. Because packet-loss is always to be expected, Forward Error Correction (FEC) is required to prevent certain levels of packet-loss from impacting the complete reception of the original data.  Reed-Solomon codes are used to perform the Forward Error Correction. In short, when an original block of data of 100 bytes is encoded using FEC to 100 + n bytes (where n can be chosen from 1 up to 100 bytes), all the 100 + n bytes are transmitted. The receiver only has to receive any 100 of the bytes and the FEC decoder can then re-construct the original 100 bytes.

Reed-Solomon encoding is currently only `fast' and practical at a symbol size of 8 bits. This gives us a coding block of 2 ** 8 - 1 = 255 symbols that can be decoded at a time. There is no point in sending these 255 symbols in one single packet. The packet itself can (virtually) not be corrupted because of the checksums in the IP and UDP headers. The only thing that can go wrong is that a packet gets lost. If we put the 255 symbols in one single packet and the packet is lost then this would cause a loss all symbols and ofcourse the decoder can't handle the loss of that many symbols. We thus need a way to ensure that the loss of a packet doesn't cause the loss of a large number of symbols in a single coding block.

The way this is solved in PML is that we use a Forward Error Correction code FEC() with 255 (= S = symbols in the coding block) UDP/IP packets with a payload size P. We select an error correction capability E. We encode P coding blocks of (S - E) symbols. We copy each symbol s in coded block FEC(p) to packet s at position p. When all P blocks are encoded in the S packets then we start sending the packets. Because a file is often larger then P * (S - E) bytes we have to divide the file in segments of size P * S bytes. Each packet that we send has indicated in its PMTP header what the segment number is. In the PMTP header is also indicated the sequence number of the packet in the segment. If we now lose a single packet then this causes a single erasure in all P encoding blocks. But that's okay as long as we don't lose more then E out of the S packets then the decoding function can handle the decode (if we defined NROOTS as 8 so 8 packets may be lost out of the 255). Furthermore, because we keep track of sequence numbers in the PMTP header we also now the erasure location, so we can aid the decoder. In the decoder we wait until we have received as much packets with a payload P as possible. We then check that we have received sufficient packets for the decoder to work. If we do then we copy each byte p from packet s to symbol s in coded block p. We then decode each of the coded blocks and, if successful, write the coding block to disk. We will be receiving packets in the receiver. Some of the packets that have been sent will not be received or may be received out of order which we can tell by looking at the sequence number in the PMTP header. We can also receive packets belonging to the next segment before we have received all packets of the current segment. Only when we've received all s packets then we can be sure that there are no more packets to come for the current segment. But ofourse, packets sometimes get lost. That's why we decide that if we have received MAX_PACKETS_LOST packets from the new segment that we don't expect to receive packets of the current segment anymore. We then start the decoding of the current segment, write the segment to disk and make the new segment the current segment.

This scheme is explained more elaborately below. We use in this example a Reed-Solomon code FEC() with a symbol size of 8 resulting in S= 2^8-1= 255 coding symbols and E=8 error correction symbols. We can thus encode 255 - 8 = 247 symbols at a time. The decoding function will be indicated with FEC'(). In this example we will use a P2P Multicast Transport (PMT) payload size of P = 1024 bytes

File to Parts
We split a file into different parts to support partial file sharing in P2P networks

Part to Segment
We split each part into multiple segments, with each segment being payload P times S bytes (= 1024 * 247 = 252928).

Segment to Array
Each segment consists of P blocks of S (=247) symbols

Array encode
We encode each block b (0 <= b < P=1024) of S symbols resulting in FEC(b) and we put each symbol s (0< = s < 255) of FEC(b) in position b of packet s

Send encoded packets
We send each of the S packets

At the receiving side, we receive the S packets and put each byte b (0 <= b < P) of packet s (0 <= s < 255) in in position s of block b

Decode array
We decode each block b resulting in FEC'(b) and put the 247 original bytes into an array

Array to Segment
After we've decoded all packets of the segment, we can reconstruct the segment

Segment to Part
When we've got all the segments, we can recreate the part

Parts to File
When we've got all the parts, we can reconstruct the file


Copyright (C) 2003, 2004 Steven Hessing