Warning: This is an old version. The latest stable version is Version 6.1.0.
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.
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:
k
or more source or repair symbols out of the n
generated from a given block we will be able to decode successfully.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.
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.
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():
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.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.
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.