5.4 FEC Encoding & Decoding

In this section, we present our implementation of the core FEC Encoding & Decoding operations, in the most recent FEC draft. We separate these two classes so that the sender only needs to import the FECEncoder and the receiver only needs to import the FECDecoder. These classes are really not classes, as they have no constructor, only static methods. We only use static methods, because there is no need for state. These collections of operations only executes one operation at a time, without internal sideeffects.

5.4.1 FECEncoder

Our FECEncoder class consists of one public method: protectRow. As mentioned previously, this function generates a FEC packet by combining a row of RTP packets. We use four additional helper methods to aid this operation. These are called calculateLongestPayload, generateBitString, getPaddedRTPPayload, and createFECPacket. We present these in the following subsection.

protectRow

The protect row function takes an array of RTP packets (with size) and returns a newly created FEC packet. The idea is that a FEC packet will be computed regardless of the amount of RTP packets. We can then use this logic for both the FEC non-interleaved and interleaved protection schemes, and also others schemes. We begin by finding the longest payload of in the source packet array, by utilizing our calculateLongestPayload method. We need this size to apply optional padding to packets with shorter sizes. This is because the FEC repair scheme requires each packet to be of the same length when we generate the final FEC packet. Next we compute the bit string for every packet in the source packet array, using the generateBitString procedure. This bit string is a representation of the source packet which is used to generate the FEC header.

When we have the bit string representation of all the source packets, we apply the xor operation on every source packet. This includes both the bit strings and source packet payloads. This is the base of the FEC repair scheme, as this process can be reversed to generate any of the source packets, if missing. Before we combine the payloads we pad them to the longest packet size of the source packets, using the getPaddedRTPPayload method. This is necessary to match the length of each payload when we apply the xor operation. After this computation, we end up with one FEC bit string and one FEC payload. Next, we extract the sequence number of the first packet in the array because we include this in the FEC packet to indicate the base sequence number this FEC packet is protecting. Finally, we create a FEC packet by combining the FEC bit string, packet size, FEC payload, sequence number base, l, and d in our createFECPacket procedure.

calculateLongestPayload

We calculate the longest payload of each source packet by comparing their payload lengths. In the most recent FEC draft it is stated that we should pad the payload to the longest source packet size to protect all bits. We also deduct the RTP header size because we are calculating the longest payload.

generateBitString

The bit string is a ten byte string which contains what we need to repair. We generate the source packet bit string by combining several elements from the source packet. In our implementation, we begin by copying the first eight bytes of the RTP header to the FEC bit string. In the FEC draft, the first two bits are skipped, but we copy these bytes directly for simplicity, and we change these bits later. Next, we calculate a sixteen bit number which is the sum of the CRSC list, extension header, RTP- payload and padding. We copy this sum to the last two bits of the bit string.

getPaddedRTPPayload

The padded payload function takes a RTP packet and longest packet size. We compute the padded payload by appending 0x00 bytes at the end of the payload until the length matches the longest payload.

createFECPacket

We begin making the FEC packet by allocating a buffer of the parameter packet size to hold the packet content. Be begin by copying the first two bytes of the FEC bit string into the first two bytes of the buffer. We also add 10 as the first two bits to indicate that this is a 2d parity packet. Next, we copy the aforementioned sum of CRSC list, extension header, RTP- payload and padding into the next two bytes of the buffer. Next, we copy the timestamp, sequence number base, l, and d into the eight bytes of the buffer. Finally, we copy the payload directly onto the end of the FEC header. We now how a buffer containing the FEC packet, and we instantiate a FECPacket object with this buffer and size, before returning.

5.4.2 FECDecoder

Our FECDecoder implementation handles the core operations of FEC decoding, which is to repair a FECCluster. This function, as mentioned previously, is called repairCluster and is the only function used directly outside this class. repairCluster uses an additional nine helper functions which are called: repairNonInterleaved, repairInterleaved...

repairCluster

Our repairCluster procedure is our implementation of the iterative repair algorithm from the most recent FEC draft. The purpose of this function is to loop through the cluster of packets and attempt to repair as many lost packets as possible. In this function, we use two variables: numRecoveredUntilThisIteration and numRecoveredSoFar, both set to 0. We loop through the rows and columns and attempt to repair them, using our repairNonInterleaved and repairInterleaved functions. In these functions, we increase the numRecoveredSoFar if we repair a row or column successfully. At the end of the loop, we compare numRecoveredUntilThisIteration and numRecoveredSoFar. If numRecoveredSoFar is greater than numRecoveredUntilThisIteration, we set numRecoveredUntilThisIteration equal to numRecoveredSoFar. If not, we break out of the loop. Essentially, we loop through the rows and columns and attempt to repair them. If we encounter an iteration where we cannot repair any packet, we stop the repair process.

repairNonInterleaved and repairInterleaved

The repairNonInterleaved and repairInterleaved functions are very similar. The main idea of each function is to loop through either the rows or columns in a cluster and attempt to repair them using the repairRow function. In both functions we loop through the rows or columns accordingly. If one of these is either missing more than one RTP packet or just the FEC packet, we do not attempt to repair it. This is because more than one RTP packet cannot be recovered using the reversed xor scheme. Additionally, we do not care if the FEC packet is missing, because our intention is to repair RTP packets. In repairInterleaved we have to convert each column to a row, because we utilize the repairRow function. If we have a suitable row or column for repair, we perform the repair row function and on completion, we receive a repaired RTPPacket. Finally we insert this RTPPacket into the cluster and increase the numRecoveredSoFar by 1.

repairRow

The repairRow function takes a row of source and repair packets, and returns one repaired RTPPacket, by utilizing several helper functions. We begin by finding the sequence number of the missing packet in the row, using the findSequenceNumber function. Next, we use our calculateRowBitString method to acquire a bit string for the row, and use this bit string to create a repaired RTP header, using the createHeader function. Next we extract the variable y from byte eight through nine in the bit string. The variable y is the sum of CRSC list, extension header, RTP- payload and padding. We use this variable to calculate the payload, using the calculatePayload function.

Next, we calculate the new RTP packet’s size by combining the static RTP header size (12 bytes) and y which accounts for the payload of the packet. We allocate a buffer of this size and copy the header and payload into this array. Finally we create and return a new RTPPacket using this buffer and size.

findSequenceNumber

The findSequenceNumber function finds the sequence number of the missing packet in a row of RTP packets and one FEC packet. We extract the base sequence number from the FEC packet, since we do not know which RTP packet is missing, but we know that the FEC packet is present. We loop through the source packets, and when we find the missing packet we return the iterator count plus the sequence number base. If the packet is protected by an interleaved column, we multiply the iterator by l.

calculateRowBitString

The purpose of the calculateRowBitString is to apply the xor operation to the bit strings of all the available RTP packets and FEC packet. We begin by generating the FEC bit string by utilizing the generateFECBitString method. We do this prior to the RTP packets, because this packet must be present. Next, we iterate over the RTP packets in the row. If a packet is missing, we do nothing. If the packet is present, we calculate the bit string of the packet, using the generateBitString method. We then apply the xor operation on this bit string and the previous bit string. Note that we override the previous bit string, always calculating the xor product of the old and new bit string.

generateFECBitString In generateFECBitString, we calculate the FEC bit string from the provided FEC packet. We firstly allocate a 10 byte array, because the FEC bit string is 10 bytes. We copy the first two bytes and the timestamp from the FEC packet to the FEC bit string at the same offsets. We also copy the length recovery from the FEC packet into the eight and ninth byte of the FEC bit string. Note that we add 12 bytes for each copying on the FEC packet, because the FEC packet is encapsulated within a RTP packet.

generateBitString The generateBitString method generates a bit string for a given RTP packet. This method is identical to the method with the same in FECEncoder, Section 5.4.1. We copy the first eight bytes of the RTP header into the bit string and compute the variable y, which we copy into the last two bytes of the bit string. Note that while these methods are identical, we keep them in separate files to improve code readability.

createHeader

In the createHeader function, we generate the RTP repair packet header, using the acquired bit string, sequence number and ssrc. We begin by allocating a 12 byte buffer, which holds the new RTP header. We copy the first two bytes from the bit string into the RTP header. Note that we also change the first two bits of the first byte to 10, which indicates RTP version 2. Next, we copy the sequence number into byte three and four of the RTP header. We also copy the timestamp and ssrc into the RTP header, respectively. At last we return the new RTP header.

calculatePayload

In calculatePayload, we combine the payloads of the available RTP packets and one FEC packet to create the missing RTP packet payload. We also use the previously computed variable Y, to determine the size of the new payload. We begin by allocating the new payload as a buffer of size Y. As mentioned previously: the payloads of source packets on the sender side are padded 0x00 on the end of each packet, to match the length of the longest packet. This is done prior to generate the FEC bit string. Therefore, we have to pad the FEC and RTP packets to the length of Y to replicate this process. We copy the padded FEC payload into the payload buffer, because the FEC packet must be present. Next we apply the xor operation on this buffer with the available RTP packet payloads.