Packet Loss Protection

Under the hood Rely uses a sliding window RLNC (Random Linear Network Code) algorithm to protect against any packet loss. A sliding window code is similar to traditional FEC/ECC block codes but provides more flexibility and better packet loss correction capabilities.

In the following we will give a high-level description of the difference between traditional block codes and a sliding window code.

Traditional Block Codes

Most ECC/FEC codes today are what we call block codes. This means that they operate over a block containing a fixed amount of data. Within the block the data is divided into k source symbols. From the block of source symbols we may now generate r repair symbols that can be used to reconstruct the original data if any of the source symbols are lost during transmission.

In total we generate n = r + k symbols.

Different ECC algorithms provide different decoding characteristics, however in general we can say the following:

1. If we receive k or more source or repair symbols out of the n generated from a given block we will be able to decode successfully.
2. Source and repair symbols from one block cannot be used in the decoding of a different block.

Bullet number 2 is the key difference between a block code and a sliding window code. Let’s take a look at how a block code would encode an incoming stream of source symbols.

The above figure shows a block encoder where k = 6 and r = 2. As can be seen each six source symbols are grouped in a block. From each block we generate two repair symbols, covering the past 6 source symbols. As new symbols arrive these are grouped in the next block and so forth. As long as no more than two symbols are lost from a block we may decode.

Traditional Sliding Window Codes

A sliding window code does not operate over a fixed amount of data. Instead data “slides” though it and encoding/decoding is performed over the data currently in the coding window. Similar to the parameter k for the block code we can define w as the coding window size. Where w is the number of source symbols included in each repair symbol. For the sliding window code we also define r as the number of repair symbols generated.

To really see the difference let’s see how the sliding window code would encode an incoming stream of source symbols:

As seen above the repair symbols now overlap rather than, as with the block code, being isolated to a specific block.

Note

In Rely overlaps are not fixed but rather based on the timeout and max_stream_size parameters. I.e. the coding window will include source symbols that have not yet expired. See Rely Sliding Window Codes below.

Rely Sliding Window Codes

In Rely the window size w is not fixed but rather determined by two configuration parameters used in rely::encoder::configure() or rely::decoder::configure():

1. The timeout which determines for how long we include a specific source symbol in new repair packets or attempt to decode a specific source symbol at the decoder.
2. The max_stream_size parameter which specifies the maximum number of symbols that can be stored by either the encoder or decoder. Both the encoder and decoder will drop symbols from the encoding or decoding respectively if this limit is reached.

The coding window of Rely will therefore include symbols for as long as they remain valid. The repair pattern will therefore be more dynamic as shown in the figure below.

In the Figure we see that for repair packet r4 all symbols prior to s7 have now expired and are no longer include in the encoding.

Comparison

Depending on the loss pattern observed, the block and sliding window code may perform very similarly. However, as shown in the figure below in certain cases the sliding window code can repair losses not recoverable with a corresponding block code.

In the above figure three losses occur. Since the block code only generates two repair symbols per block we cannot recover from this situation. However, for the sliding window code the three lost symbols are included in three repair symbols and can therefore successfully be recovered.

In general the sliding window code provides stronger loss recovery properties when compared to a block code.

One weakness of the basic sliding window code is that if decoding fails it may take longer to recover compared to a traditional block code. The reason for this is that repair symbols overlap and are not isolated as is the case for block codes. For block codes failure to decode block i does not affect block i+1.

Rely takes a different approach, rather than specifying a fixed block or window size Rely uses the timeout to determine wether a repair symbol should overlap with previous repair symbols. This means that depending on the input traffic Rely can code of isolated “blocks” or allow the coding window to overlap previously sent repair symbols.