Recoding DataΒΆ

One of the key features of RLNC is the ability to recode. Recoding means that 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
  • mesh networks.

In this example, a total of three nodes is in the network. At each link a loss can occur with 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
101
102
103
104
105
106
107
108
109
110
// Copyright Steinwurf ApS 2016.
// Distributed under the "STEINWURF RESEARCH LICENSE 1.0".
// See accompanying file LICENSE.rst or
// http://www.steinwurf.com/licensing

#include <cstdint>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <vector>

#include <kodocpp/kodocpp.hpp>

int main()
{
    // Seed the random number generator to produce different data every time
    srand((uint32_t)time(0));

    // 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;

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

    kodocpp::encoder encoder = encoder_factory.build();

    kodocpp::decoder_factory decoder_factory(
        kodocpp::codec::full_vector,
        kodocpp::field::binary8,
        max_symbols,
        max_symbol_size);

    kodocpp::decoder decoder1 = decoder_factory.build();
    kodocpp::decoder decoder2 = decoder_factory.build();
    //! [1]

    std::vector<uint8_t> payload(encoder.payload_size());
    std::vector<uint8_t> data_in(encoder.block_size());
    // Just for fun - fill the data with random data
    std::generate(data_in.begin(), data_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(data_in.data(), encoder.block_size());
    // Create a buffer which will contain the decoded data, and we assign
    // that buffer to the decoder
    std::vector<uint8_t> data_out1(decoder1.block_size());
    std::vector<uint8_t> data_out2(decoder2.block_size());
    decoder1.set_mutable_symbols(data_out1.data(), decoder1.block_size());
    decoder2.set_mutable_symbols(data_out2.data(), decoder2.block_size());

    uint32_t encoded_count = 0;
    uint32_t dropped_count = 0;

    // We switch any systematic operations off so the encoder produces
    // coded symbols from the beginning
    if (encoder.is_systematic_on())
        encoder.set_systematic_off();

    //! [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;

    // Check if we properly decoded the data
    if (data_in == data_out2)
    {
        std::cout << "Data decoded correctly" << std::endl;
    }

    return 0;
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    // In the following we will make an encoder/decoder factory.
    // The factories are used to build actual encoders/decoders
    kodocpp::encoder_factory encoder_factory(
        kodocpp::codec::full_vector,
        kodocpp::field::binary8,
        max_symbols,
        max_symbol_size);

    kodocpp::encoder encoder = encoder_factory.build();

    kodocpp::decoder_factory decoder_factory(
        kodocpp::codec::full_vector,
        kodocpp::field::binary8,
        max_symbols,
        max_symbol_size);

    kodocpp::decoder decoder1 = decoder_factory.build();
    kodocpp::decoder 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 is 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 of this example looks like this (the outcome is randomized):

Encoded count = 28
Dropped count = 19