Recoding DataΒΆ

One of the key features of RLNC is the ability to recode. Recoding is when the encoded data is re-encoded. This is very useful in scenarios where the data is to be transmitted through a chain of nodes. Here the data can be re-encoded at each node. Examples of such networks include:

  • Relay networks
  • P2P networks,
  • multi-path networks, and
  • mesh networks.

In this example a total of three nodes is in the network. At each link a loss can occure at a 50% chance. The complete example code for this is as follows.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
// Copyright Steinwurf ApS 2013.
// Distributed under the "STEINWURF RESEARCH LICENSE 1.0".
// See accompanying file LICENSE.rst or
// http://www.steinwurf.com/licensing

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <vector>

#include <kodo_rlnc/full_vector_codes.hpp>
#include <kodo_core/is_systematic_on.hpp>
#include <kodo_core/set_systematic_off.hpp>

#include <storage/storage.hpp>

int main()
{
    // Set the number of symbols (i.e. the generation size in RLNC
    // terminology) and the size of a symbol in bytes
    uint32_t max_symbols = 16;
    uint32_t max_symbol_size = 1400;

    using rlnc_encoder = kodo_rlnc::full_vector_encoder<fifi::binary8>;
    using rlnc_decoder = kodo_rlnc::full_vector_decoder<fifi::binary8>;

    //! [0]
    // In the following we will make an encoder/decoder factory.
    // The factories are used to build actual encoders/decoders
    rlnc_encoder::factory encoder_factory(max_symbols, max_symbol_size);
    auto encoder = encoder_factory.build();

    rlnc_decoder::factory decoder_factory(max_symbols, max_symbol_size);
    auto decoder1 = decoder_factory.build();
    auto decoder2 = decoder_factory.build();
    //! [1]

    std::vector<uint8_t> payload(encoder->payload_size());
    std::vector<uint8_t> block_in(encoder->block_size());

    // Just for fun - fill the data with random data
    std::generate(block_in.begin(), block_in.end(), rand);

    // Assign the data buffer to the encoder so that we may start
    // to produce encoded symbols from it
    encoder->set_const_symbols(storage::storage(block_in));

    uint32_t encoded_count = 0;
    uint32_t dropped_count = 0;

    // We switch any systematic operations off so we code
    // symbols from the beginning
    if (kodo_core::is_systematic_on(*encoder))
        kodo_core::set_systematic_off(*encoder);

    //! [2]
    while (!decoder2->is_complete())
    {
        // Encode a packet into the payload buffer
        encoder->write_payload(payload.data());

        ++encoded_count;

        if (rand() % 2)
        {
            ++dropped_count;
        }
        else
        {
            // Pass that packet to the decoder1
            decoder1->read_payload(payload.data());
        }

        // Create a recoded packet from decoder1
        decoder1->write_payload(payload.data());

        if (rand() % 2)
        {
            ++dropped_count;
        }
        else
        {
            // Pass the recoded packet to decoder two
            decoder2->read_payload(payload.data());
        }
    }
    //! [3]
    std::cout << "Encoded count = " << encoded_count << std::endl;
    std::cout << "Dropped count = " << dropped_count << std::endl;

    // Create a buffer which will contain the decoded data
    // For the point of example we use sak::storage on a raw pointer
    uint8_t* block_out = new uint8_t[decoder2->block_size()];
    decoder2->copy_from_symbols(
        storage::storage(block_out, decoder2->block_size()));

    delete[] block_out;

    return 0;
}

Compared to the basic example, the setup and decoding loop has changed. In the setup phase two decoders are now created, instead just one.

1
2
3
4
5
6
7
8
    // In the following we will make an encoder/decoder factory.
    // The factories are used to build actual encoders/decoders
    rlnc_encoder::factory encoder_factory(max_symbols, max_symbol_size);
    auto encoder = encoder_factory.build();

    rlnc_decoder::factory decoder_factory(max_symbols, max_symbol_size);
    auto decoder1 = decoder_factory.build();
    auto decoder2 = decoder_factory.build();

The decoding loop has changed to simulate a lossy multi-hop network.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
    while (!decoder2->is_complete())
    {
        // Encode a packet into the payload buffer
        encoder->write_payload(payload.data());

        ++encoded_count;

        if (rand() % 2)
        {
            ++dropped_count;
        }
        else
        {
            // Pass that packet to the decoder1
            decoder1->read_payload(payload.data());
        }

        // Create a recoded packet from decoder1
        decoder1->write_payload(payload.data());

        if (rand() % 2)
        {
            ++dropped_count;
        }
        else
        {
            // Pass the recoded packet to decoder two
            decoder2->read_payload(payload.data());
        }
    }

The encoder encodes data which is then “transmitted” to decoder1. This data is then both decoded and recoded by decoder1. The resulting recoded data is then finally “transmitted” to decoder2 where it’s decoded. Both the channel from encoder to decoder1 and the channel from decoder1 to decoder2 is simulated to have a 50% success rate.

../../../_images/recoding_setup.svg

In a network without recoding, the overall success rate would be the product of all the networks success rates, i.e., for this network the success rate would be 50% * 50% = 25%. When using recoding the overall success rate will be the minimum success rate for any of the nodes, i.e., 50% in this example.

The output when running this example looks like so:

Encoded count = 28
Dropped count = 19